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

《数据结构第十章构造类型.ppt》由会员分享，可在线阅读，更多相关《数据结构第十章构造类型.ppt（37页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第十章 构造类型第一节 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 结构名 成员说明

2、表列;说明: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

3、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.m

4、onth 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,ta

5、o;以下均正确的引用语句:(1)scanf(“%ld”,&li.num);成员运算符(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;有分号无分号第四节 结构数组 当结构变量有许多时,用结构数组来表示,数组的每一个元素

6、均为结构体.一.结构体数组的定义 形式:结构类型 数组名常量表达式 例10.6 struct char *name;long num;char sex;struct int year,month,days;birth;p30;即描述如下:name num sex year month daysp0p1 p29birth二.结构体数组的引用 形式:数组名下标.成员名 例7 设有如下数组说明语句#define F “%s,%sn”struct char *code;char *name;float price;char *place;struct int year,month,day;valida

7、y;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;四

8、.结构数组应用举例 例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,&xi.nu,&xi.ma,&xi.ph);xi.av=(xi.ma+xi.ph)/2.0;sum+=xi.av;for(i=0;i成员名 说明:1.-为

9、指向运算符,其运算优先级与“.”相同.但-常用;2.变向理解:*&today=today,即地址中的值为变量.如:(*p).year=1999;p-year=1999;图示:p 1999 year month day效果图三.使用注意 (1).结构体指针只能指向结构体变量的第一个成员:p=&today.month 是错误的;(2).若结构指针p指向结构数组,则p+即是使指针后移一个结构体元素的总字节数.如:struct date int year;int month;int day;today10,*p;1011999 102 5103 22104107 1999105 11106 today

10、0today1p=today;p的当前指针为101p+;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 m

11、ain()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.顺序存储:将逻辑上相邻的两个数据分配在物理上相邻的两个存储单

12、元中;典型的数据结构:数组 如:int a10 a a0 ffc0 a1 ffc2 a2 ffc4 a9 ffd3 特点:存储单元连续 表长固定 静态存储2.链表存储:将存储单元分成两部分,其一存放数据本身,另一存放逻辑上相邻者的存储地址,通过地址的链接勾勒数据之间的逻辑关系.特点:存储单元允许离散,见缝插针;动态存储(需之则有,不需则无);表长可动态伸缩.head 1079 1153 1286 107911115313128617NULL理解几个名词：结点 头结点 未结点 头指针 数据域 指针域 见P176页 二.单链表的结点类型定义 形式:struct 结构名 数据域表列;struct 结

13、构名 *指针变量名;递归定义:结构中的某成员又是一个指向自身结构的结构类型.如:素数链表: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聂佳兰江西569990002谢爱平江苏580990003东东上海432三.链表的创建 结点的存储空间都是在需要时临时向系统申请获得的 1.用于链表创建的函数和运算符 (1)malloc函数 形式:(数据类型

14、 *)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

15、)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)若干次.未结点头结点例 建立一个存储学生

16、考试信息的链表,结点有两个成员:学号和学分.当输入学号为-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

17、 student*)malloc(L);scanf(F1,&p-num,&p-score);if(p-num=-1)break;p-next=head;head=p;k+;/*对链表遍历*/printf(“There are%d records:n”,k);for(p=head;k;k-)printf(F2,p-num,p-score);p=p-next;3.创建队列式链表 建表规则:结点从表尾插入.从表首退出.head头指针:一旦指向了首结点后,就永远 不再变动;p:生成的新结点,插入链表时必须与未结 点拉链;last:跟踪未结点,即跟踪未结点的指针.算法大意:(1).创建首结点:head=

18、(结点类型)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$36F70856$36head遇空格循环结束#incl

19、ude#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”,&head-x);head-asc=toascii(head-x);last=head;将字符转换成ASCII码 for(;)p=(struct letter *)malloc(L);scanf(“%c”,&p-x);if(p-x=)break;p-asc=toascii(p-x);last-next=p;last=last-next;last-next=NULL;/*终止链表的延伸*/p=head;while(p!=NULL)printf(“%c%dn”,p-x,p-asc);p=p-next;