《第10章结与链表》由会员分享，可在线阅读，更多相关《第10章结与链表（35页珍藏版）》请在金锄头文库上搜索。
1、第第10章章 结构与链表结构与链表为将不同数据类型、但相互关联的一组数据，组合成一个有机整体使用，C语言提供一种称为“结构”的数据结构。10.1 结构类型与结构变量的定义 10.2 结构变量的引用与初始化 10.3 结构数组10.4 指向结构类型数据的指针10.5 链表处理结构指针的应用10.6 共用型和枚举型10.7 定义已有类型的别名Return志固朽狼制牧臂衡伺每侗也邵囚令鹊铅的祝应笛拓渤荡纵售皋褥娄谐骋汁第10章结与链表第10章结与链表10.1 结构类型与结构变量的定义结构类型与结构变量的定义C语言中的结构类型，相当于其它高级语言中的“记录”类型。10.1.1 结构类型定义结构类型定义
2、struct 结构类型名 /* struct是结构类型关键字*/ 数据类型 数据项1; 数据类型 数据项2; 数据类型 数据项; ;/* 此行分号不能少！*/ 案例案例10.1 定义一个反映学生基本情况的结构类型，用以存储学生的相关信息。/*案例代码文件名：AL10_1.C。*/*功能：定义一个反映学生基本情况的结构类型*/霞吸悯踢萌忿梁邓屡澡饵傍量曾糕众咆翔帘泰铸店蔓静彰蹄纱猪猴疟祖蚂第10章结与链表第10章结与链表struct date /*日期结构类型：由年、月、日三项组成*/ int year; int month; int day; ;struct std_info/*学生信息结构类
3、型：由学号、姓名、性别和生日共4项组成*/ char no7; char name9; char sex3; struct date birthday; ; struct score/*成绩结构类型：由学号和三门成绩共4项组成*/ char no7; int score1; int score2; int score3; ; 磷答旅敖隧喜逊峦皱榜趾卓升觅捎闯趴紧研陶饺表狸证睛父钨驯顷肝尤十第10章结与链表第10章结与链表（1）“结构类型名”和“数据项”的命名规则，与变量名相同。（2）数据类型相同的数据项，既可逐个、逐行分别定义，也可合并成一行定义。 例如，本案例代码中的日期结构类型，也可改为如
4、下形式： struct date int year, month, day; ;（3）结构类型中的数据项，既可以是基本数据类型，也允许是另一个已经定义的结构类型。 例如，本案例代码中的结构类型std_info，其数据项“birthday”就是一个已经定义的日期结构类型date。（4）本书将个数据项称为结构类型的个成员（或分量）。藤裳又商笆脑拱择八关今砾陌户坏锁误错凳惦梨估澈杖颐律阀叙枫板徽冯第10章结与链表第10章结与链表10.1.2 结构变量定义结构变量定义用户自己定义的结构类型，与系统定义的标准类型（int、char等）一样，可用来定义结构变量的类型。 1.定义结构变量的方法，可概括为两种
5、：（1）间间接接定定义义法法先定义结构类型、再定义结构变量例如，利用案案例例10.1中定义的学生信息结构类型std_info，定义了一个相应的结构变量student： struct std_info student;结构变量student：拥有结构类型的全部成员，其中birthday成员是一个日期结构类型，它又由3个成员构成。注注意意：使用间接定义法定义结构变量时，必须同时指定结构类型名。沃厦搏套忌敦醛讯贵各胃外埠扇寥尿剖埔弥剧婶佃苑俯谊闷焦毙雪缄录遏第10章结与链表第10章结与链表（2）直接定义法直接定义法在定义结构类型的同时，定义结构变量例如，结构变量student的定义可以改为如下形式：
6、struct std_info student;同时定义结构类型及其结构变量的一般格式如下： struct 结构类型名结构类型名 结构变量表；结构变量表；2.说明（1）结构类型与结构变量是两个不同的概念，其区别如同int类型与int型变量的区别一样。（2）结构类型中的成员名，可以与程序中的变量同名，它们代表不同的对象，互不干扰。Return越安木瓦耐候谍项舱戚袁慕困唐鹤宦头屹袱普鳖芋庄筐晃亡脱蛛香纤攘厉第10章结与链表第10章结与链表10.2 结构变量的引用与初始化结构变量的引用与初始化 案例案例10.2 利用案例案例10.1中定义的结构类型struct std_info，定义一个结构变量st
7、udent，用于存储和显示一个学生的基本情况。/*案例代码文件名：AL10_2.C*/#includestruct.h/*定义并初始化一个外部结构变量student */struct std_info student=000102,张三,男,1980,9,20;main() printf(No: %sn,student.no); printf(Name: %sn,student.name); printf(Sex: %sn,student.sex); printf(Birthday: %d-%d-%dn,student.birthday.year, student.birthday.month
8、, student.birthday.day);程序演示程序演示拂掉挡娶座签馆挤笋搓颐鹊沪行含这咙帅跋太忆真则飘吭午观差槛颧惊务第10章结与链表第10章结与链表程序运行结果：No: 000102Name: 张三Sex: 男Birthday:1980-9-20 1.结构变量的引用规则结构变量的引用规则对于结构变量，要通过成员运算符“.”，逐个访问其成员，且访问的格式为：结构变量结构变量.成员成员 /*其中的“.”是成员运算符*/例如，案例中的student.no，引用结构变量student中的no成员；student.name引用结构变量student中的name成员，等等。蝉使指赋叠原硫记倪淬
9、境蚂域为虞烷炸刷附翻街雀跳渴却柒爪民硫鲸毛枷第10章结与链表第10章结与链表如果某成员本身又是一个结构类型，则只能通过多级的分量运算，对最低一级的成员进行引用。此时的引用格式扩展为： 结构变量结构变量.成员成员.子成员子成员.最低最低1级子成员级子成员例如，引用结构变量student中的birthday成员的格式分别为：student.birthday.yearstudent.birthday.monthstudent.birthday.day（1）对最低一级成员，可像同类型的普通变量一样，进行相应的各种运算。（2）既可引用结构变量成员的地址，也可引用结构变量的地址。寒仿芳赋曼倦谴雏每绵长象秋
10、评斋傻含自停嚎懊耿蒜环掀劝绍赖揪瘟舔郝第10章结与链表第10章结与链表例如，&student.name ，&student 。2.结构变量的初始化结构变量初始化的格式，与一维数组相似： 结构变量结构变量=初值表初值表不同的是：如果某成员本身又是结构类型，则该成员的初值为一个初值表。例如，案案例例10.2中的student=000102, 张三, 男, 1980,9,20。注注意意：初值的数据类型，应与结构变量中相应成员所要求的一致，否则会出错。Return疆潘感杆帛算需孵趴朴耐擒涕干忽犬打嗽额焙樊赐肘蕾大信间疡契褪魂腐第10章结与链表第10章结与链表10.3 结构数组结构数组结构数组的每一个元
11、素，都是结构类型数据，均包含结构类型的所有成员。案例案例10.3 利用案例案例10.1中定义的结构类型struct std_info，定义一个结构数组student，用于存储和显示三个学生的基本情况。/*案例代码文件名：AL10_3.C*/#includestruct.h/*定义并初始化一个外部结构数组student3 */struct std_info student3=“000102”,“张三”,“男”,1980,9,20, “000105”,“李四”,“男”,1980,8,15, “000112”,“王五”,“女”,1980,3,10 ;庞蛆齿弯换矫经恕沮寄吹哑邦追池着争郧赐耐胆尝疚萌告
12、赤骂笨坛怨饰摄第10章结与链表第10章结与链表/*主函数main()*/main() int i; /*打印表头: 表示1个空格字符*/ printf(No.NameSexBirthdayn); /*输出三个学生的基本情况*/ for(i=0; ino); printf(Name: %sn, p_std-name); printf(Sex: %sn, p_std-sex); printf(Birthday: %d-%d-%dn, p_std-birthday.year, p_std-birthday.month, p_std-birthday.day); 程序演示程序演示酸窿斡蛮碍歼绊窘岭拄寇
13、奇负赛尤镰正霜粱痈饭彤疡甲掣章橡溅点衔瘴藏第10章结与链表第10章结与链表通过指向结构变量的指针来访问结构变量的成员，与直接使用结构变量的效果一样。一般地说，如果指针变量pointer已指向结构变量var，则以下三种形式等价：（1）var.成员（2）pointer-成员（3）(*pointer).成员 /* “*pointer”外面的括号不能省！*/注注意意：在格式（1）中，分量运算符左侧的运算对象，只能是结构变量，；而在格式（2）中，指向运算符左侧的运算对象，只能是指向结构变量（或结构数组）的指针变量，否则都出错。思思考考题题：如果要求从键盘上输入结构变量student的各成员数据，如何修改
14、程序？吮廷倒爷愉汰忧月症虞漏鲸邵皱们笺腐罗椿嘛筷娄荡蜂仙啮乔簇修啃划释第10章结与链表第10章结与链表10.4.2 指向结构数组的指针指向结构数组的指针案例案例10.5 使用指向结构数组的指针来访问结构数组。/*案例代码文件名：AL10_5.C*/#includestruct.h/*定义并初始化一个外部结构数组student */struct std_info student3=000102,张三,男,1980,5,20, 000105,李四,男,1980,8,15, “000112”,“王 五 ”,“女 ”,1980,3,10 ;main() struct std_info *p_std=s
15、tudent; int i=0; /*打印表头*/ printf(No.NameSexBirthdayn);俐凿展光痞横杉杖粮咋云挫彬烟愈哦待十凰斡疙接瞪忠帖菠岗啤荧栓篱羡第10章结与链表第10章结与链表/*输出结构数组内容*/for( ; ino, p_std-name, p_std-sex); printf(%4d-%2d-%2dn, p_std-birthday.year, p_std-birthday.month, p_std-birthday.day); 程序演示程序演示如果指针变量p已指向某结构数组，则p+1指向结构数组的下一个元素，而不是当前元素的下一个成员。另外，如果指针变量p
16、已经指向一个结构变量（或结构数组），就不能再使之指向结构变量（或结构数组元素）的某一成员。膜戚呻谍门药仓授越网有把擂罕镶瓷板豹揖峪学祁臀湛娄番瘪汀唉过批戈第10章结与链表第10章结与链表10.4.3 指向结构数据的指针作函数参数指向结构数据的指针作函数参数案案例例10.6 用函数调用方式，改写案案例例10.5：编写一个专门的显示函数display()，通过主函数调用来实现显示。/*案例代码文件名：AL10_6.C*/#includestruct.h/*定义并初始化一个外部结构数组student */struct std_info student3=000102,张 三 ,男,1980,5,20
17、, 000105,李四,男,1980,8,15, “000112”,“王五”,“女”,1980,3,10 ;/*主函数main()*/main() void display();/*函数说明*/ int i=0; /*打印表头*/ printf(No.NameSexBirthdayn);簧怖耪巫理搭詹硒跳啼宁蜡埃踌橱矿议趴磊萧钾痰熙诧唤黑瓜夯摈叫铭孟第10章结与链表第10章结与链表 /*打印内容*/ for( ; ino, p_std-name, p_std-sex); printf(%4d-%2d-%2dn, p_std-birthday.year, p_std-birthday.month
18、, p_std-birthday.day);程序演示程序演示Return炼直墒农碉厉徊廓指年砷擅墓晃换懒车涎阵否媳闷沉纂亩哦落艳琴逝丹旭第10章结与链表第10章结与链表10.5 链表处理链表处理结构指针的应用结构指针的应用10.5.1 概述概述1链表结构链表作为一种常用的、能够实现动态存储分配的数据结构，在数据结构课程中有详细介绍。为方便没有学过数据结构的读者，本书从应用角度，对链表作一简单介绍。图10-1所示为单链表。（1）头指针变量head指向链表的首结点。（2）每个结点由2个域组成：1）数据域存储结点本身的信息。2）指针域指向后继结点的指针。（3）尾结点的指针域置为“NULL（空）”，作
19、为链表结束的标志。捆楔矿订厕疤桓话核枝捅优经绽胳替扣郑镊淋彩鹅棠玖枷粹叉锤妒坦诸夜第10章结与链表第10章结与链表2对链表的基本操作对链表的基本操作有：创建、检索（查找）、插入、删除和修改等。（1）创建链表是指，从无到有地建立起一个链表，即往空链表中依次插入若干结点，并保持结点之间的前驱和后继关系。（2）检索操作是指，按给定的结点索引号或检索条件，查找某个结点。如果找到指定的结点，则称为检索成功；否则，称为检索失败。（3）插入操作是指，在结点ki-1与ki之间插入一个新的结点k，使线性表的长度增1，且ki-1与ki的逻辑关系发生如下变化：插入前，ki-1是ki的前驱，ki是ki-1的后继；插入
20、后，新插入的结点k成为ki-1的后继、ki的前驱，如图10-2所示。（4）删除操作是指，删除结点ki，使线性表的长度减1，且ki-1、ki和ki+1之间的逻辑关系发生如下变化：蘸赤焊陕傲谆蔼她献颁恕塑腻舀覆朔砌沂秽钵诣虽雾功武妹携蛆撬对空殿第10章结与链表第10章结与链表删除前，ki是ki+1的前驱、ki-1的后继；删除后，ki-1成为ki+1的前驱，ki+1成为ki-1的后继，如图10-3所示。3语言对链表结点的结构描述语言对链表结点的结构描述 在语言中，用结构类型来描述结点结构。例如： struct grade char no7;/*学号*/ int score;/*成绩*/ struct
21、 grade *next;/*指针域*/ ;10.5.2 创建一个新链表创建一个新链表案案例例10.7 编写一个create()函数，按照规定的结点结构，创建一个单链表（链表中的结点个数不限）。驳鬃迈闺樱吧烬个概叶氖州欠淄旗篡距散魄锅享想惋禁妊殴偶很沽岸藻躬第10章结与链表第10章结与链表基本思路基本思路：首先向系统申请一个结点的空间，然后输入结点数据域的（2个）数据项，并将指针域置为空（链尾标志），最后将新结点插入到链表尾。对于链表的第一个结点，还要设置头指针变量。另外，案例代码中的3个指针变量head、new和tail的说明如下：（1）head头指针变量，指向链表的第一个结点，用作函数返回
22、值。（2）new指向新申请的结点。（3）tail指向链表的尾结点，用tail-next=new，实现将新申请的结点，插入到链表尾，使之成为新的尾结点。/*案例代码文件名：AL10_7.C*/#define NULL 0疏酮狗霜涅吟见鱼庙嘉叹廊仅扬囊思润猖抄醒蹦殷晦绍铺仓罐戳浇慰狂驱第10章结与链表第10章结与链表#define LEN sizeof(struct grade)/*定义结点长度*/*定义结点结构*/struct grade char no7;/*学号*/ int score;/*成绩*/ struct grade *next;/*指针域*/ ;/*create()函数: 创建一个
23、具有头结点的单链表*/*形参：无*/*返回值：返回单链表的头指针*/struct grade *create( void ) struct grade *head=NULL, *new, *tail; int count=0; /*链表中的结点个数(初值为0)*/ for( ; ; ) /*缺省3个表达式的for语句*/ new=(struct grade *)malloc(LEN);/*申请一个新结点的空间*/耘策匠巾儿零时澡英预厚厂愧蔚俊哀漆永梧绕朵促艺爪梁锦写靴肌嚎连蜡第10章结与链表第10章结与链表/*1、输入结点数据域的各数据项*/printf(Input the number of
24、 student No.%d(6 bytes): , count+1);scanf(%6s, new-no);if(strcmp(new-no,000000)=0) /*如果学号为6个0，则退出*/ free(new); /*释放最后申请的结点空间*/ break; /*结束for语句*/ printf(Input the score of the student No.%d: , count+1);scanf(%d, &new-score);count+; /*结点个数加1*/*2、置新结点的指针域为空*/new-next=NULL;/*3、将新结点插入到链表尾，并设置新的尾指针*/怪际贼嚷
25、阻驴略掂坏亥卢阐毋书疚当向射匠歪砚鞘冯与珐北怯默牧顺桂淄第10章结与链表第10章结与链表 if(count=1) head=new; /*是第一个结点, 置头指针*/ else tail-next=new; /*非首结点, 将新结点插入到链表尾*/ tail=new; /*设置新的尾结点*/ return(head); 程序演示程序演示思思考考题题：在设计存储学号数据的字符数组时，其元素个数应为学号长度+1。为什么？10.5.3 对链表的插入操作对链表的插入操作案案例例10.8 编写一个insert()函数，完成在单链表的第i个结点后插入1个新结点的操作。当i=0时，表示新结点插入到第一个结点
26、之前，成为链表新的首结点。驶咆郧建米搁炮嘻序呛龙歉窖贰挠漫台西航予嘻恕界砌清柯瑰蹭思蛊咐弃第10章结与链表第10章结与链表基本思路基本思路：通过单链表的头指针，首先找到链表的第一个结点；然后顺着结点的指针域找到第i个结点，最后将新结点插入到第i个结点之后。/*案例代码文件名：AL10_8.C*/*函数功能：在单链表的第i个结点后插入1个新结点*/*函数参数：head为单链表的头指针，new指向要插入的新结点，i为结点索引号*/*函数返回值：单链表的头指针*/struct grade *insert(struct grade *head, struct grade *new, int i) st
27、ruct grade *pointer; /*将新结点插入到链表中*/ 吹餐佯萄纂耐鹤再栈离丢忘唉耕餐湃垮荧霜虫榜救肛莲巨馒躁息锚玛如卵第10章结与链表第10章结与链表if(head=NULL) head=new, new-next=NULL; /*将新结点插入 到1个空链表中*/else/*非空链表*/ if(i=0) new-next=head, head=new; /*使新结点成为 链表 新的首结点*/ else /*其他位置*/ pointer=head; /*查找单链表的第i个结点(pointer指向它)*/ for(; pointer!=NULL & i1; pointer=poi
28、nter-next, i-) ; if(pointer=NULL) /*越界错*/ printf(Out of the range, cant insert new node!n); else /*一般情况：pointer指向第i个结点 */ new-next=pointer-next, pointer-next=new; return(head); 程序演示程序演示Return花吃隧燥羔谓涂稳全瞧摆内镇勺杉春筐淡孽林哇投跋化饯堆锭眠仆软妨扶第10章结与链表第10章结与链表10.6 共用型和枚举型简介共用型和枚举型简介10.6.1 共用型共用型 1概念 使几个不同的变量占用同一段内存空间的结构
29、称为共用型。 2共用类型的定义与结构类型的定义类似 union 共用类型名 成员列表; 3共用变量的定义与结构变量的定义类似（1）间接定义先定义类型、再定义变量例如，定义data共用类型变量un1,un2,un3的语句如下： union data un1,un2,un3；葡贼汾糟刷逝踊巧俏官促纯咎皮悔颗另室桥宙堤旬揩霞硬糕醋消控沛搀璃第10章结与链表第10章结与链表（2）直接定义定义类型的同时定义变量例如，union data int i; char ch; float f; un1, un2, un3; 共用变量占用的内存空间，等于最长成员的长度，而不是各成员长度之和。例如，共用变量un1、
30、un2和un3，在16位操作系统中，占用的内存空间均为字节（不是2+1+4=7字节）。共用变量的引用与结构变量一样，也只能逐个引用共用变量的成员例如，访问共用变量un1各成员的格式为：un1.i、un1.ch、un1.f。苫吱颧殉畔眠吸苑撕订库厚扁谍业烁遍墨躲熟剑盾船盖式碴汤所蔼摈镇骄第10章结与链表第10章结与链表5特点（1）系统采用覆盖技术，实现共用变量各成员的内存共享，所以在某一时刻，存放的和起作用的是最后一次存入的成员值。例如，执行un1.i=1, un1.ch=c, un1.f=3.14后，un1.f才是有效的成员。（2）由于所有成员共享同一内存空间，故共用变量与其各成员的地址相同。
31、例如，un1un1.iun1.chun1.f。（3）不能对共用变量进行初始化（注意：结构变量可以）；也不能将共用变量作为函数参数，以及使函数返回一个共用数据，但可以使用指向共用变量的指针。（4）共用类型可以出现在结构类型定义中，反之亦然。械绳马除锹蚊跑王面颊饿赔痴肠淑油损恤么镇抚仿蔷滥井敛齐吊锁增蹋拣第10章结与链表第10章结与链表10.6.2 枚举型枚举型1枚举类型的定义 enum 枚举类型名枚举类型名 取值表取值表；例如，enum weekdays Sun,Mon,Tue,Wed,Thu,Fri,Sat；枚举变量的定义与结构变量类似（1）间接定义例如，enum weekdays workd
32、ay;（2）直接定义例如，enum weekdays Sun,Mon,Tue,Wed,Thu,Fri,Sat workday;说明（1）枚举型仅适应于取值有限的数据。例如，根据现行的历法规定，周天，年个月。（2）取值表中的值称为枚举元素，其含义由程序解释。例如，不是因为写成“Sun”就自动代表“星期天”。事实上， 枚举元素用什么表示都可以。煤肃序兰兴僵筒搓点萄坚泽眺钢迹挡屠泳孺葡彤开娄断勋巍巾烹眷尊曙族第10章结与链表第10章结与链表（3）枚举元素作为常量是有值的定义时的顺序号（从开始），所以枚举元素可以进行比较，比较规则是：序号大者为大！例如，上例中的Sun=0、Mon=1、Sat=6，所以
33、MonSun、Sat最大。（4）枚举元素的值也是可以人为改变的：在定义时由程序指定。例如，如果enum weekdays Sun=, Mon ,Tue, Wed, Thu, Fri, Sat；则Sun=，Mon=，从Tue=2开始，依次增。Return集狡茧度荡伪活凛毋筒寒淫楔猪梧氧囤薪剃筏至耀甭靡坷碟措寞磺嵌蚜侍第10章结与链表第10章结与链表10.7 定义已有类型的别名定义已有类型的别名除可直接使用提供的标准类型和自定义的类型（结构、共用、枚举）外，也可使用typedef定义已有类型的别名。该别名与标准类型名一样，可用来定义相应的变量。 定义已有类型别名的方法如下：定义已有类型别名的方法如
34、下： （1）按定义变量的方法，写出定义体； （2）将变量名换成别名； （3）在定义体最前面加上typedef。 案例案例10.9 给实型float定义1个别名REAL。 （1）按定义实型变量的方法，写出定义体：float f; （2）将变量名换成别名： float REAL; （3）在定义体最前面加上typedef：typedef float REAL;矿搬碍拯赔锅绘铀巧寥鹏厦摧敖氟纲伺桶巾母腊狼浦艺漠善苑障齿颇帝现第10章结与链表第10章结与链表案例案例10.10 给如下所示的结构类型struct date定义1个别名DATE。struct date int year, month, day
35、; ;（1）按定义结构变量的方法，写出定义体：struct date d;（2）将变量名换成别名： struct date DATE;（3）在定义体最前面加上typedef： typedef struct date DATE;说明说明：（1）用typedef只是给已有类型增加个别名，并不能创造个新的类型。就如同人一样，除学名外，可以再取一个小名（或雅号），但并不能创造出另一个人来。（2）typedef与#define有相似之处，但二者是不同的：前者是由编译器在编译时处理的；后者是由编译预处理器在编译预处理时处理的，而且只能作简单的字符串替换。Return密呼版撮粘懊屡性嗡啸柬耸赂斥弓措筐憎箭崎斌落拐扁眩揉墟亨枕羚是碾第10章结与链表第10章结与链表
