数据结构第十章构造类型.ppt

第十章 构造类型第一节 C数据类型概述 简单类型 结构类型.编译系统预定义;.用户自己定义.只赋单值;.可赋多值.数据独立;.数据之间相互关联如:日期:1999,5,30 商品:W3024,洗衣机,2000.0元,C语言描述关联数据的方法:数组:元素为同一类型.如:double test302;结构体:元素为不同类型.如:struct student long number;char name6;int grade;枚举类型:如:enum sex male,femal;说明:枚举类型中为常量标识符,从左至右用数值0,1,2来表示其值.,第二节 结构体类型的定义 形式:struct 结构名 成员说明表列;说明:1.结构名为用户自定义标识符;2.成员表列也称为域表列;3.可以嵌套定义例10.1 分别定义代表日期,商品,学生信息的结构体类型.日期结构体类型:struct date int year;int month;int day;,商品结构体类型:struct product char*partname;double price;int stock;学生结构体类型:struct date int year,month,day;struct student long number;char*name;struct date birthday;int grade;,嵌套,等价于,struct student long number;char*name;struct int year,month,day;birthday;int grade;student的结构:出生年月 学号 姓名 年 月 日 总分,第三节 结构体变量 一.结构体变量的定义 方法1.先定义类型,后说明变量 如:struct date int year;int month;int day;struct date x,y;方法2.在定义类型的同时说明变量 如:struct date int year;int month;int day;x,y;含义:x:x.year x.month x.day y:y.year y.month y.day,方法3:定义的结构类型仅供程序一处引用,即只定义一次变量.如:struct long num;double score;a,b;注意:1.一个结构体变量的存储开销(内存字节总数)为所有成员字节数的总和;2.当两个结构变量具有完全相同的结构类型时,a=b赋值正确,即把a中的每一个成员的值一一赋给b.如上a变量的存储字节为4+8=12.,二.结构体变量的引用 形式:结构体变量名.成员名例10.4 假设有如下说明:struct student long num;char name10;structint year,month,day;birth;int score;li,hu,tao;以下均正确的引用语句:(1)scanf(“%ld”,成员运算符,(2)hu.birth.year=1973;(3)sum=sum+tao.score;(4)tao.num+;说明:多级引用成员运算符逐级引用其最底层的成员。,三.结构体变量的初始化形式:结构体变量名=初值表;例10.5 struct student long num;char name10;structint year,month,day;birth;int score;li,ma=2001,“马红”,1973,5,6;602;,有分号,无分号,第四节 结构数组 当结构变量有许多时,用结构数组来表示,数组的每一个元素均为结构体.一.结构体数组的定义 形式:结构类型 数组名常量表达式,例10.6 struct char*name;long num;char sex;struct int year,month,days;birth;p30;即描述如下:name num sex year month daysp0p1 p29,birth,二.结构体数组的引用 形式:数组名下标.成员名 例7 设有如下数组说明语句#define F“%s,%sn”struct char*code;char*name;float price;char*place;struct int year,month,day;validay;x100;则 for(i=0;i=100;i+)if(xi.validay.year=2001)printf(F,xi.code,xi.name);功能:输出药品库中有效期为2001年之前所有药品清单.,三.结构数组的初始化 形式:数组说明亮=初值表1,初值表2.初值表n;例10.8 struct studentlong num;char name10;structint year,month,day;birth;int score;p3=200111,“马红”,1973,5,6,602,200112,“刘阳”,1974,1,3,571,200113,“刘海”,1972,2,1,551;,四.结构数组应用举例 例10.9 输入n位学生的学号和数学,物理考试成绩,输出每人的学号和平均分以及全班总平均分.#define F1“%ld%d%d”#define F2“n%ld%4.1f”#define P printf#define S scanf#define N 10,main()int i;double sum=0;struct long nu;int ma,ph;float av;xN;for(i=0;iN;i+)S(F1,等价于,第五节 结构指针 指向结构体的指针变量,是一个地址.一.结构指针的定义 形式:struct 结构名*指针名 如:struct date int year;int month;int day;struct date today,*p=图示:today p year month day,p=&today.year,效果图,二.通过结构指针引用结构体 形式:(*结构指针名).成员名 或:结构指针名-成员名 说明:1.-为指向运算符,其运算优先级与“.”相同.但-常用;2.变向理解:*图示:p 1999 year month day,效果图,三.使用注意(1).结构体指针只能指向结构体变量的第一个成员:p=1999 5 22107 1999 11,today0,today1,p=today;p的当前指针为101,p+;p的当前指针为107即:101+2+2+2=107,四.结构指针作为函数的参数 两种数据传递方式:1.传值:形,实参所占的内存不同,不带回值;2.传地址:形,实同占一个地址的内存单元,实际上,形参不占内存空间,返回值.结构指针作为函数的参数的功能是使结构体变量实现传地址的调用.例10.10 输入n位学生的学号和数学,物理考试成绩,输出每人的学号和平均分以及全班总平均分.#define F1“%ld%d%d”#define F2“n%ld%4.1f”#define P printf#define S scanf#define N 10,main()int i;double sum=0;struct long nu;int ma,ph;float av;xN，*p;for(p=x;pav=(p-ma+p-ph)/2.0;sum+=p-av;for(p=x;pnu,p-av);P(“nn”);P(“average of total is:%.2f”,sum/N);,第六节 动态数据结构几点说明：1.以前的变量都是先定义后使用,这样它们的存储空间大小不能再改变;易造成系统资源的浪费;2.动态数据结构的特点是“需之则有,不需则无”,存储空间按需得到改变.一.数据的存储结构 1.顺序存储:将逻辑上相邻的两个数据分配在物理上相邻的两个存储单元中;典型的数据结构:数组,如:int a10 a a0 ffc0 a1 ffc2 a2 ffc4 a9 ffd3 特点:存储单元连续 表长固定 静态存储,2.链表存储:将存储单元分成两部分,其一存放数据本身,另一存放逻辑上相邻者的存储地址,通过地址的链接勾勒数据之间的逻辑关系.特点:存储单元允许离散,见缝插针;动态存储(需之则有,不需则无);表长可动态伸缩.head 1079 1153 1286,1079,111153,131286,17NULL,理解几个名词：结点 头结点 未结点 头指针 数据域 指针域 见P176页 二.单链表的结点类型定义 形式:struct 结构名 数据域表列;struct 结构名*指针变量名;递归定义:结构中的某成员又是一个指向自身结构的结构类型.如:素数链表:head 3 5 97,.,结点类型:struct obj int data;struct obj*next;学生链表:base struct student long number;char name10;char come12;int score;struct student*next;,990001聂佳兰江西569,990002谢爱平江苏580,990003东东上海432,三.链表的创建 结点的存储空间都是在需要时临时向系统申请获得的 1.用于链表创建的函数和运算符(1)malloc函数 形式:(数据类型*)malloc(size)功能:申请一块长度为size字节的连续内存空间,并返回该区域的首地址,若调用失败就返回空指针NULL 如:int*p;p p=malloc(10);p=(int*)malloc(10);,分配一个占10个字节的存储空间,并指向第一个字节,10byte,(2).free函数 形式：void free(void*p)功能:收回指针p所指向内存区域.如:void*p;p=malloc(10);.free(p);(3).sizeof运算符 形式:sizeof(类型标志符/变量名)功能:计算指定数据类型的长度,如:sizeof(int)2 double x;sizeof(x)8 struct part char name20;float price;int stock;sizeof(struct part)26 注意:运用sizeof运算符,文件头必须包含宏命令:#include“stdio.h”,2.创建栈式键表 建表规则:结点从表首插入,也从表首退 出,即为栈结构或“先进后出”式结构.指针变量设置:head 头指针 p生成新结点 算法大意:(1).建空表 head=NULL;(2).开辟新结点:p=(结点类型*)malloc(结点长度);(3).新结点进栈:p-next=head;head=p;(4).重复(2)(3)若干次.,未结点,头结点,例 建立一个存储学生考试信息的链表,结点有两个成员:学号和学分.当输入学号为-1时结束建表,但该结点不加入链表,最后对链表遍历输出全部结点的内容./*预处理*/#include#define L sizeof(struct student)#define F1“%ld%d”#define F2“%ldt%dn”/*定义链表的结点类型*/struct student long num;int score;struct student*next;,/*主函数*/main()struct student*head,*p;int k=0;head=NULL;/*建空表*/for(;)/*无限循环*/p=(struct student*)malloc(L);scanf(F1,3.创建队列式链表 建表规则:结点从表尾插入.从表首退出.head头指针:一旦指向了首结点后,就永远 不再变动;p:生成的新结点,插入链表时必须与未结 点拉链;last:跟踪未结点,即跟踪未结点的指针.算法大意:(1).创建首结点:head=(结点类型)malloc(结点长度),(2).对last指针初始化:last=head;(3).开辟后继新结点:p=(结点类型)malloc(结点长度)(4).新结点入队列:last-next=p;(5).last指针后移至未结点:last=last-next;(6).重复(3)(4)若干次(7).终止链表的延伸last-next=NULL;,例 创建一个队列式链表用于存储字符ASCII对照表,结点包含两个成员:字符和ASCII码,最后对其遍历输出全部结点的内容.如:运行程序进输入:F8!x$程序输出：F 70 8 56！33 x 120$36,F70,856,$36,head,遇空格循环结束,#include#include#define L sizeof(struct letter)struct letter char x;int asc;struct letter*next;main()struct letter*head,*p,*last;head=(struct letter*)malloc(L);scanf(“%c”,将字符转换成ASCII码,for(;)p=(struct letter*)malloc(L);scanf(“%c”,