第九章结构与其它自定义类型.

1第九章结构与其他自定义类型29.1结构类型的认识回顾：使用数组的好处是可以用一个变量定义逻辑上相关的一批数据，使每个分量具有相同的名字、不同的下标，但有一个限制，即一个数组变量包含的所有成分元素必须为同一类型，例如：inta[3]。3学号姓名性别高考分数生源010031张三女567北京010032李四女539深圳010033王五男460上海……………思考：如果要存储若干学生的信息（如下表）使用数组可以吗？4定义结构类型student：structstudent{longnum;/*学号*/charname[6];/*姓名*/charsex;/*性别*/intscore;/*高考分数*/char*place;/*生源*/};59.2结构类型的定义形式：struct结构名{成员表列；};structdate{intyear,month,day;};【例】定义代表日期信息、药品信息的结构类型。structdate{intyear;intmonth;intday;};6structmedicine{char*code;char*name;floatprice;char*place;structdatevalidity;};codenamepriceplacevalidityyearmonthday结构类型medicine：79.3结构变量9.3.1结构变量1.结构变量的定义structstudent{longnum;charname[6];charsex;intscore;charplace[12];};（1）先定义结构类型，再引用该类型定义的变量structstudentxia,ding,li;8（2）定义结构类型的同时说明变量structstudent{longnum;charname[6];charsex;intscore;charplace[12];}xia,ding,li;92.结构变量的引用结构变量通常都以成员的形式加以引用，结构变量成员的标记形式为：成员运算符【例】设有如下说明：structdate{intyear,month,day;};结构变量名.成员名10以下语句序列是对药品结构变量drug1、drug2进行赋值、输入和输出运算：structmedicine{char*code;char*name;floatprice;char*place;structdatevalidity;}drug1,drug2;11drug1.name=“penicillin”;drug1.price=6.38;drug2.name=“vitamineC”;if(drug2.code＝＝“99103x”)drug2.price=drug2.price-7.5;scanf(“%d%d%d”,&drug1.validity.year,&drug1.validity.month,&drug1.validity.day);puts(drug1.name);puts(drug2.name);123.结构变量的初始化【例】结构变量在定义时被赋初值。structmedicine{char*code;char*name;floatprice;char*place;structdatevalidity;};structmedicinedrug1,drug2={“01-56p”,“vitamineC”,22.65,“Shanghai”,{2002,12,31}};139.3.2结构数组1.结构数组的定义形式：结构类型数组名[常量表达式]structdate{intyear,month,day;};structmedicine{char*code;char*name;floatprice;char*place;structdatevalidity;};structmedicinedrug[10];142.结构数组的引用结构数组是以下标变量的成员名形式加以引用的。其标记形式为：for(i=0;iN;i++){gets(&p[i].name);scanf(“%ld%d”,&p[i].num,&p[i].score);}结构数组名[下标].成员名【例】#defineN100structstudent{char*name;longnum;intscore;}p[N];对数组p[N]赋初值的语句如下：153.结构数组的初始化与结构变量一样，结构数组也允许定义时被初始化。【例】structstudent{char*name;longnum;intscore;}p[]={{“Zhangsan”,1001,536},{“Lisi”,1002,494},{“Wangwu”,1003,501}};16经过初始化以后，p数组的存储结构和内容如下图所示：Zhangsan1001536Lisi1002494Wangwu1003501p[0]p[1]p[2]174.结构数组应用举例【例】已知若干学生的姓名、学号和某单科考试成绩，试编写程序，对学生记录按考试成绩从高分至低分排序，程序输出排序以后的学生表，并报告姓名为××（由键盘随即输入）的同学的名次号。具体源程序代码见书P157，例9.5。189.3.3结构指针定义一个指针，使其指向结构变量，这样的指针称为“结构指针”。1.结构指针的定义形式：结构类型*指针名【例】structproduct{charcode[5];charname[20];floatprice;intstock;};structproductx,y[2],*px=&x,*py=y;19F0103电冰箱2050.00160T0216电视机1900.00290W3008洗衣机768.5093pxxpyyy[0]y[1]*px=&x,具体的执行过程为：structproductx,y[2],*py=y;20形式：指针名-成员名或（*指针名）.成员名【例】以上图为例，则以下语句都是通过结构指针引用结构变量的成员。2.通过结构指针引用结构变量21F0103电冰箱2050.00160T0216电视机1900.00290W3008洗衣机768.5093pxxpyyy[0]y[1](*px).price-=200;px－price-=200;(++py)－stock+=10;1850/*电冰箱降价200元*//*洗衣机库存加10*/10322结构指针作为函数的参数使得结构变量也能像普通变量一样实现“传地址”调用。调用发生时，实参传递给形参的是自身结构的存储地址，使形式参数直接指向了实在实参，形参不再另占内存单元，从而使函数体中对形式参数所作的改变就是对实在参数所作。3.结构指针作为函数的参数23【例】已知10名学生的三门单科考试成绩，求每一门课程的总平均分。242526运行结果为：27习题集28【例1】运行结果为：29【例2】运行结果为：30【例3】31【例4】见实验教程P66-程序改错。【例5】见实验教程P66-程序填空。【例6】见实验教程P59-程序填空。329.4动态数据结构“链表”常用的动态数据结构(特点：需之则有，不需则无)有链表、树、图等等。9.4.1链表概述1.什么是链表顺序存储——将逻辑上相邻的数据分配在物理上相邻的存储单元中，数据之间的逻辑关系通过存储单元的邻接关系来体现；链接存储——将逻辑上相邻的数据分配在物理上离散的存储单元中，然后在每一个存储单元中粘贴一张标有相邻者存储地址的标签，使数据之间的逻辑关系通过地址的链接关系来体现。332.链表实例下图表示存放整数11，13，17，19的链表：head1079115312861390头结点末结点头指针数据域指针域1079115312861390NULL13171911349.4.2单链表结点的类型定义111153数据域：存储数据指针域：存储后续结点的地址35单链表结点的类型定义：struct结构名{数据成员表列；struct结构名*指针名；};head1079115312861390107911115313128617139019NULL36【例】定义素数链表的结点类型structprime。素数链表：head11131719NULL要求素数链表结点只包含一个数据成员，因此结点类型可定义为：structprime{intdata；structprime*next;};37【例】定义学生链表的结点类型structstudent。假设一个学生记录包括学号、姓名、性别和高考成绩，则学生链表的结点类型可定义为：structstudent{longnum;char*name;charsex;intscore;structstudent*next;};structstudent*p,*q;38structstudent{longnum;char*name;charsex;intscore;structstudent*next;};010201倪桂兰女568structstudent*p,*q;p-num=010201;p-name=“倪桂兰”；p-sex=‘女’;p-score=568;010202刘宁宁女544pq-num=010202;q-name=“刘宁宁”；q-sex=‘女’;q-score=544;qp-next=q;399.4.3动态存储分配函数2.calloc函数函数原型：void*calloc(unsignedn,unsignedsize)1.malloc函数函数原型：void*malloc(unsignedsize)函数功能：在内存的动态存储区中分配一块长度为size字节的连续空间，并返回该存储区域的首地址；若函数调用失败，返回空指针NULL。40函数功能：在内存的动态存储区中分配长度为size字节的连续空间n块，并返回该存储区域的首地址。若函数调用失败，就返回空指针NULL。3.free函数函数原型：voidfree(void*p)函数功能：释放当前正被指针p所指向的内存区域，将它归还给系统以作它用。419.4.4创建链表创建链表从空表开始，循环地将新结点逐一产生出来，并按预定的链接关系插入到链表中去的过程。010201倪桂兰女568010202刘宁宁女544010230潘俊男626NULLhead…42结点插入通常有两种预定关系：“栈”式结构——新结点总是从表首插入，使得最先插入到链表中去的结点被挤压到链尾，成为末结点，而最后插入的结点成为链表的头结点；“队列”式结构——新结点总是从表尾插入；1）创建“栈”式链表43p3设head为链表头指针，p为创建动态结点的工作指针，则：①建空表：head＝NULL；②创建新结点，p=(结点类型*)malloc(结点长度)并对结点的数据域赋值：③新结点进栈：p-next=head;head=p;④重复②、③步骤若干次；headNULLheadp3NULLheadp3NULLhead^44【例】用上述步骤往链表中插入两个结点：head^p3headp3NULL①②③③‘②‘3NULLheadp553NULLheadp45【例】编写程序，建立一个存储字符及其ASCII码的链表，规定ASCII码的范围为[m，n]（32mn126）,程序最后输出链表中全部结点的内容。字符的ASCII码字符46“栈”式链表的特点：先进后出47指针后移48运行程序：492.创建“队列”式链表队列式链表结点插入位置在链尾，头指针一旦指向了首结点后，就不会再动，而新结点插入链表时必须与末结点拉链，这就需要增加一个跟踪末结点的指针last。现在假设head为头指针，p为创建新结点的工作指针，last为跟踪末结点的指针。创建队列式链表的算法步骤：50②对末结点指针last初始化：last＝head；head3headlast3p5①创建首结点，并对数据域赋值：head＝（结点类型*）malloc（结点长度）；③开辟后续新结点：p=(结点类型*)malloc(结点长度)；51④新结点插入表尾：last-next=p；3headlast5p3head5