数据结构第十章构造类型.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来表示其值.第二节 结构体类型的定义

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 d

3、ate 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 mon

4、th; 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 lo

5、ng num; char name10; structint year, month,day; birth; int score; li,hu, tao; 以下均正确的引用语句: (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

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

8、10; 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

9、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.-为指向运算符,其运算优先级与“.”相同.但-常用; 2.变向理解: *&today=today,即地址中的值为变量. 如: (*p).year=1999; p-year=1999;图示: p 1999 year month day效果图三.使用注意 (1). 结构体指针只能指向结构体变量的第一

10、个成员: p=&today.month 是错误的; (2).若结构指针p指向结构数组, 则p+即是使指针后移一个结构体元素的总字节数.如: struct date int year; int month; int day; today10,*p; 1011999 5 22107 1999 11 today0today1p=today; p的当前指针为101p+;p的当前指针为107即:101+2+2+2=107四.结构指针作为函数的参数 两种数据传递方式: 1.传值: 形,实参所占的内存不同,不带回值; 2.传地址: 形,实同占一个地址的内存单元,实际上,形参不占内存空间,返回值. 结构指针作

11、为函数的参数的功能是使结构体变量实现传地址的调用.例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(“n

12、n”); P(“average of total is:%.2f”, sum/N);第六节 动态数据结构几点说明： 1.以前的变量都是先定义后使用,这样它们的存储空间大小不能再改变;易造成系统资源的浪费; 2. 动态数据结构的特点是“需之则有,不需则无”,存储空间按需得到改变. 一.数据的存储结构 1.顺序存储: 将逻辑上相邻的两个数据分配在物理上相邻的两个存储单元中; 典型的数据结构: 数组 如:int a10 a a0 ffc0 a1 ffc2 a2 ffc4 a9 ffd3 特点: 存储单元连续 表长固定 静态存储2.链表存储: 将存储单元分成两部分,其一存放数据本身,另一存放逻辑上相邻

13、者的存储地址,通过地址的链接勾勒数据之间的逻辑关系. 特点: 存储单元允许离散,见缝插针; 动态存储(需之则有,不需则无); 表长可动态伸缩. head 1079 1153 1286 107911115313128617NULL理解几个名词： 结点 头结点 未结点 头指针 数据域 指针域 见P176页 二.单链表的结点类型定义 形式: struct 结构名 数据域表列; struct 结构名 *指针变量名; ; 递归定义: 结构中的某成员又是一个指向自身结构的结构类型. 如: 素数链表: head 3 5 97 .结点类型: struct obj int data; struct obj *n

14、ext; 学生链表: base struct student long number; char name10; char come12; int score; struct student *next;990001聂佳兰江西569990002谢爱平江苏580990003东东上海432三.链表的创建 结点的存储空间都是在需要时临时向系统申请获得的 1.用于链表创建的函数和运算符 (1) malloc函数 形式: (数据类型 *) malloc(size) 功能: 申请一块长度为size字节的连续内存空间,并返回该区域的首地址,若调用失败就返回空指针NULL 如: int *p; p p=mal

15、loc(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(stru

16、ct 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时结束建表,但该结点不加入链表

17、,最后对链表遍历输出全部结点的内容. /*预处理*/ #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

18、(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).创建首结点: hea

19、d=(结点类型)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 $ 36F70

20、856$36head遇空格循环结束 #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”, &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;