补充资料结构与自定义类型.ppt

《补充资料结构与自定义类型.ppt》由会员分享，可在线阅读，更多相关《补充资料结构与自定义类型.ppt（69页珍藏版）》请在三一办公上搜索。

1、1,第 九 章结构与其他自定义类型,2,9.1 结构类型的认识,回顾：使用数组的好处是可以用一个变量定义逻辑上相关的一批数据，使每个分量具有相同的名字、不同的下标，但有一个限制，即一个数组变量包含的所有成分元素必须为同一类型，例如：int a3。,3,思考：如果要存储若干学生的信息（如下表）使用数组可以吗？,4,定义结构类型student：,struct student long num;/*学号*/char name6;/*姓名*/char sex;/*性别*/int score;/*高考分数*/char*place;/*生源*/;,5,9.2 结构类型的定义 形式：struct 结构名 成

2、员表列；;,struct date int year,month,day;,【例】定义代表日期信息、药品信息的结构类型。struct date int year;int month;int day;,6,struct medicine char*code;char*name;float price;char*place;struct date validity;,结构类型medicine：,7,9.3 结构变量 9.3.1 结构变量 1.结构变量的定义,struct student long num;char name6;char sex;int score;char place12;,（1）

3、先定义结构类型，再引用该类型定义的变量,struct student xia,ding,li;,8,（2）定义结构类型的同时说明变量,struct student long num;char name6;char sex;int score;char place12;xia,ding,li;,9,2.结构变量的引用 结构变量通常都以成员的形式加以引用，结构变量成员的标记形式为：,成员运算符,【例】设有如下说明：struct date int year,month,day;,结构变量名.成员名,10,以下语句序列是对药品结构变量drug1、drug2进行赋值、输入和输出运算：,struct me

4、dicine char*code;char*name;float price;char*place;struct date validity;drug1,drug2;,11,drug1.name=“penicillin”;,drug1.price=6.38;,drug2.name=“vitamine C”;,if(drug2.code“99103x”)drug2.price=drug2.price-7.5;,scanf(“%d%d%d”,puts(drug1.name);puts(drug2.name);,12,3.结构变量的初始化【例】结构变量在定义时被赋初值。,struct medicin

5、e char*code;char*name;float price;char*place;struct date validity;,struct medicine drug1,drug2=“01-56p”,“vitamine C”,22.65,“Shanghai”,2002,12,31;,13,9.3.2 结构数组 1.结构数组的定义,形式：结构类型 数组名常量表达式 struct date int year,month,day;struct medicine char*code;char*name;float price;char*place;struct date validity;,s

6、truct medicine drug10;,14,2.结构数组的引用 结构数组是以下标变量的成员名形式加以引用的。其标记形式为：,for(i=0;iN;i+)gets(,结构数组名下标.成员名,【例】#define N 100 struct student char*name;long num;int score;pN;,对数组pN赋初值的语句如下：,15,3.结构数组的初始化,与结构变量一样，结构数组也允许定义时被初始化。,【例】struct student char*name;long num;int score;p=“Zhang san”,1001,536,“Li si”,1002,4

7、94,“Wang wu”,1003,501;,16,经过初始化以后，p数组的存储结构和内容如下图所示：,p0,p1,p2,17,4.结构数组应用举例【例】已知若干学生的姓名、学号和某单科考试成绩，试编写程序，对学生记录按考试成绩从高分至低分排序，程序输出排序以后的学生表，并报告姓名为（由键盘随即输入）的同学的名次号。具体源程序代码见书P157，例9.5。,18,9.3.3 结构指针,定义一个指针，使其指向结构变量，这样的指针称为“结构指针”。,1.结构指针的定义 形式：结构类型*指针名,【例】struct product char code5;char name20;float price;i

8、nt stock;,struct product x,y2,*px=,19,px,x,py,y,y0,y1,*px=&x,具体的执行过程为：struct product x,y2,*py=y;,20,形式：指针名-成员名 或（*指针名）.成员名【例】以上图为例，则以下语句都是通过结构指针引用结构变量的成员。,2.通过结构指针引用结构变量,21,px,x,py,y,y0,y1,(*px).price-=200;,pxprice-=200;,(+py)stock+=10;,1850,/*电冰箱降价200元*/,/*洗衣机库存加10*/,103,22,结构指针作为函数的参数使得结构变量也能像普通变量

9、一样实现“传地址”调用。调用发生时，实参传递给形参的是自身结构的存储地址，使形式参数直接指向了实在实参，形参不再另占内存单元，从而使函数体中对形式参数所作的改变就是对实在参数所作。,3.结构指针作为函数的参数,23,【例】已知10名学生的三门单科考试成绩，求每一门课程的总平均分。,24,25,26,运行结果为：,27,习题集,28,【例1】,运行结果为：,29,【例2】,运行结果为：,30,【例3】,31,【例4】见实验教程P66-程序改错。【例5】见实验教程P66-程序填空。【例6】见实验教程P59-程序填空。,32,9.4 动态数据结构“链表”常用的动态数据结构(特点：需之则有，不需则无)

10、有链表、树、图等等。,9.4.1 链表概述 1.什么是链表,顺序存储将逻辑上相邻的数据分配在物理上相邻的存储单元中，数据之间的逻辑关系通过存储单元的邻接关系来体现；,链接存储将逻辑上相邻的数据分配在物理上离散的存储单元中，然后在每一个存储单元中粘贴一张标有相邻者存储地址的标签，使数据之间的逻辑关系通过地址的链接关系来体现。,33,2.链表实例 下图表示存放整数11，13，17，19的链表：,head,1079,1153,1286,1390,头结点,末结点,头指针,数据域,指针域,1079,1153,1286,1390,NULL,13,17,19,11,34,9.4.2 单链表结点的类型定义,数

11、据域：存储数据,指针域：存储后续结点的地址,35,单链表结点的类型定义：,struct 结构名 数据成员表列；struct 结构名*指针名；;,head,1079,1153,1286,1390,36,【例】定义素数链表的结点类型struct prime。,素数链表：,head,要求素数链表结点只包含一个数据成员，因此结点类型可定义为：struct prime int data；struct prime*next;,37,【例】定义学生链表的结点类型struct student。假设一个学生记录包括学号、姓名、性别和高考成绩，则学生链表的结点类型可定义为：,struct student long

12、 num;char*name;char sex;int score;struct student*next;,struct student*p,*q;,38,struct student long num;char*name;char sex;int score;struct student*next;,struct student*p,*q;,p-num=010201;p-name=“倪桂兰”；p-sex=女;p-score=568;,q-num=010202;q-name=“刘宁宁”；q-sex=女;q-score=544;,p-next=q;,39,9.4.3 动态存储分配函数,2.ca

13、lloc函数 函数原型：void*calloc(unsigned n,unsigned size),1.malloc函数 函数原型：void*malloc(unsigned size)函数功能：在内存的动态存储区中分配一块长度为size字节的连续空间，并返回该存储区域的首地址；若函数调用失败，返回空指针NULL。,40,函数功能：在内存的动态存储区中分配长度为size字节的连续空间n块，并返回该存储区域的首地址。若函数调用失败，就返回空指针NULL。,3.free函数 函数原型：void free(void*p)函数功能：释放当前正被指针p所指向的内存区域，将它归还给系统以作它用。,41,9.

14、4.4 创建链表,创建链表从空表开始，循环地将新结点逐一产生出来，并按预定的链接关系插入到链表中去的过程。,head,42,结点插入通常有两种预定关系：“栈”式结构新结点总是从表首插入，使得最先插入到 链表中去的结点被挤压到链尾，成为末结点，而最后插入 的结点成为链表的头结点；,“队列”式结构新结点总是从表尾插入；,1）创建“栈”式链表,43,设head为链表头指针，p为创建动态结点的工作指针，则：,建空表：headNULL；,创建新结点，p=(结点类型*)malloc(结点长度)并对结点的数据域赋值：,新结点进栈：p-next=head;head=p;,重复、步骤若干次；,head,44,【

15、例】用上述步骤往链表中插入两个结点：,head,45,【例】编写程序，建立一个存储字符及其ASCII码的链表，规定ASCII码的范围为m，n（32mn126）,程序最后输出链表中全部结点的内容。,字符的ASCII码,字符,46,“栈”式链表的特点：先进后出,47,指针后移,48,运行程序：,49,2.创建“队列”式链表,队列式链表结点插入位置在链尾，头指针一旦指向了首结点后，就不会再动，而新结点插入链表时必须与末结点拉链，这就需要增加一个跟踪末结点的指针last。,现在假设head为头指针，p为创建新结点的工作指针，last为跟踪末结点的指针。,创建队列式链表的算法步骤：,50,对末结点指针l

16、ast初始化：lasthead；,创建首结点，并对数据域赋值：head（结点类型*）malloc（结点长度）；,开辟后续新结点：p=(结点类型*)malloc(结点长度)；,51,新结点插入表尾：last-next=p；,last指针后移至末结点：lastlast-next；,52,重复、步骤若干次，如下所示；,开辟后续新结点：p=(结点类型*)malloc(结点长度)；,新结点插入表尾：last-next=p；,53,终止链表的延伸：last-nextNULL；,last指针后移至末结点：lastlast-next；,head,last,54,9.4.5 结点的删除与插入,1.删除结点 删除

17、结点解除该结点的链接关系，使之与链表脱钩，再调用free函数收回它的存储空间。,（1）被删结点p为链表首结点,p=head;/*使p指针指向首结点*/,head=head-next;/*头指针后移一个结点*/,free(p);/*收回首结点的存储空间*/,55,删除学生链表的首结点,56,（2）被删结点为链表的中间结点或末结点,head,prenext=pnext;,借助两个工作指针p和pre，寻找被删结点的过程如下：p指针从头至尾对链表的结点逐一扫描，而pre指针总是跟踪p当前所指结点的前驱结点，与p指针保持同步移动，p指针一旦找到了被删结点，执行下面的语句即可实现删除：,free(p);,

18、57,【例】结点删除的例子见书P171页。【例】创建偶数（210之间）链表，并删除指定偶数，要求输出创建的链表以及删除后的结果。,58,2.结点的插入,head,insert,【例】将下图中的insert指针指向的结点插入到头指针为head的链表中，且指针p已经指向插入点。,59,（1）在已知结点之后插入,head,insert,pnext=insert;,insertnext=pnext;,思考：上述两个拉链语句的次序能颠倒吗？,60,（2）在已知结点之前插入,head,insert,insertnext=p;,pre,p,prenext=insert;,思考：上述两个拉链语句的次序能颠倒吗

19、？,【例】结点插入的例子见书P173页例9.11。,61,9.5 共用体类型,共用体同一块内存区域在不同时刻存储不同类型的数据，是一种内存覆盖技术。共用体能使多个类型不同的变量共享一块内存区域，这些变量在不同的时间去占用这一片内存。,9.5.1 共用体类型的定义 形式：union 共用体名 成员表列;,关键字，代表共用体类型,有时也会省略,62,【例】union student long num;char name10;int score;zhang,lin;,这种类型使长度为10个字节的内存区域（最长成员所占的字节数）既能存储long型数据，又能存储字符串和int型数据，并在定义类型的同时也

20、定义了两个union student类型的变量zhang和lin。,【思考题】zhang和lin所占据的存储字节均为多少？如果将上述类型改为struct student，则变量zhang和lin又占据多少字节？,63,9.5.2 共用体变量的引用 形式：共用体变量名.成员名,【例】zhang.name=“wangfen”;lin.score=83;,【例】union student long num;char name10;int score;zhang,lin;,64,（1）任何时刻，只有一个成员的值被存储：lin.num=990011;lin.score=83;,（2）共用体变量和各成员具

21、有相同的存储地址，即&zhang与&zhang.num、&zhang.name、&zhang.score为同一个地址值；,（3）不能对共用体变量以整体形式引用，下面语句均错：scanf(“%ld%s%d”,共用体变量的所有成员共享一段内存，长度为最长成员的字节数，使用时要注意以下一些问题：,65,9.6 枚举类型 9.6.1 枚举类型的定义,形式：enum 枚举名 枚举值表列;,enum为关键字，代表枚举类型,花括号中列出的枚举值均为常量标识符，代表具有该枚举类型的变量可以取的全部值。,66,【例】enum weekday Sunday,Monday,Tueday,Wedday,Thrday,

22、Friday,Satday;,【例】enum color red,green,blue,yellow col1,col2;,【思考】上面的枚举定义代表什么意思？,【思考】上面的枚举定义又代表什么意思呢？,67,9.6.2 枚举类型的使用规则,（1）枚举类型是用户标识符，不是字符串，不能加双引号；【例】enum sex“male”,“female”;,（2）枚举值表列中的每一个枚举值对应于一个整数序号,在C语言中，枚举值按自左向右的顺序依次被编号为0，1，2但能够以初始化方式指定特别值，如：,应改写为enum sex male,female;,【例】enum color red,green,blue=8,yellow;,68,9.7 类型自定义,9.7.1 typedef语句的形式,形式：typedef 现有类型名 新类型名；,为现有的类型取一个新的别名,【问题】为什么要引入类型自定义？,69,【例】typedef struct student long num;char name10;int score;STUD;,9.7.2 typedef语句使用说明（见书P183）,typedef int ARR34;,typedef char*STRING;,STRING x,y;,ARR a,b,c;,