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

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来表示其值,第二节

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 *n

3、ame; 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 in

4、t 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 假设有如下说明:

5、 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 yea

6、r, 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 days p0 p1 p29,birth,二.结构体数组的引用 形式: 数组名

7、下标.成员名 例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, ); 功能:输出药品库中有效期为2001年之前所有药品清单,三.结构数组的初始化 形式: 数组说明亮=初值表1,初值表2 .初值表n; 例10.8 struct studentlo

8、ng 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(

9、) 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= 2.变向理解: * 图示: p 1999 year month day,效果图,三.使用注意 (1). 结构体指

10、针只能指向结构体变量的第一个成员: p= 1999 5 22 107 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” #defi

11、ne 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.以前的变量都是先定义后使用,这样它们的存储空间大小不能再改变;易造成系统资源的

12、浪费; 2. 动态数据结构的特点是“需之则有,不需则无”,存储空间按需得到改变. 一.数据的存储结构 1.顺序存储: 将逻辑上相邻的两个数据分配在物理上相邻的两个存储单元中; 典型的数据结构: 数组,如:int a10 a a0 ffc0 a1 ffc2 a2 ffc4 a9 ffd3 特点: 存储单元连续 表长固定 静态存储,2.链表存储: 将存储单元分成两部分,其一存放数据本身,另一存放逻辑上相邻者的存储地址,通过地址的链接勾勒数据之间的逻辑关系. 特点: 存储单元允许离散,见缝插针; 动态存储(需之则有,不需则无); 表长可动态伸缩. head 1079 1153 1286,1079,1

13、1 1153,13 1286,17 NULL,理解几个名词： 结点 头结点 未结点 头指针 数据域 指针域 见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 stud

14、ent *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函数 形式： v

15、oid 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.创建栈式键表 建表规则: 结点从

16、表首插入,也从表首退 出,即为栈结构或“先进后出”式结构. 指针变量设置: head 头指针 p生成新结点 算法大意: (1).建空表 head=NULL; (2).开辟新结点: p=(结点类型 *)malloc(结点长度); (3). 新结点进栈: p-next=head; head=p; (4).重复(2)(3)若干次,未结点,头结点,例 建立一个存储学生考试信息的链表,结点有两个成员: 学号和学分.当输入学号为-1时结束建表,但该结点不加入链表,最后对链表遍历输出全部结点的内容. /*预处理*/ #include #define L sizeof(struct student) #def

17、ine 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 :生成的新结点,

18、插入链表时必须与未结 点拉链; 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 ！