搜索
2020/1/281C语言程序设计2020/1/282第十二章高级程序设计主讲:计算机学院朱立华2020/1/283内容提要本章介绍单链表的相关知识以及一个管理系统的模块化设计方法,综合运用所学知识实现一个完整的系统关于单链表掌握以下知识：•为什么需要单链表•如何通过指针和结构体的定义实现单链表结构•单链表常用操作的实现方法:建立、遍历、插入、删除、查找、逆置•其他类型的链表结构简介学生档案成绩管理系统的设计与实现：•如何划分模块，每一个模块的具体功能是什么•数据类型的定义•用文件实现数据的永久存储•系统的完整实现2020/1/284单链表为什么需要链表结构？•一批类型相同的数据用数组存储所存在的问题：•(1)定义静态数组时必须指定数组的元素个数，此后无法更改数组大小，可能造成空间浪费或不足•(2)用指针可以申请动态数组，空间不会浪费或不足，但仍然是需要连续的存储空间•(3)在数组中插入或删除元素时需要大量移动元素，效率低什么是链表结构？•与数组不同，数组元素逻辑上相邻物理地址上也相邻，而链表结构其数据元素作为一个个结点的数据域，结点中另有指针域存储逻辑上相邻的其他元素的起始地址，单链表较常用数据域指针域单链表的一个结点2020/1/285单链表一个单链表示例：链表结构的优点是：•系统不必为应用程序分配一组连续的空间，可以充分利用系统的零散空间；有一个元素就生成一个结点，空间不浪费•如果内存空间足够大，理论上这一批数据的容量不受限制•对于插入、删除等操作不必通过移动元素实现，效率高单链表的结点定义----用结构体和指针递归定义而成12340这是最重要的头指针最后一个结点的指针域值为0(NULL)2020/1/286单链表单链表结点定义的格式：typedefintType;structNode{Typedata;structNode*next;};特别提醒：next前的*号不能丢失，否则就成为死循环定义啦!（一）单链表的建立：•常用的有3种建立方法：•后插法：新结点插入在链表的最尾部，作为新的尾结点•前插法：新结点插入在链表的最前部，作为新的第一个结点•按序插入法：新结点插入在链表的特定部位保持元素值有序结点的结构体类型定义单链表结点的数据成员类型不同只需要将int替换成数据成员实际的类型，下面结点的类型定义不变结点的指针成员名next，类型为structNode*结点的数据成员名data，类型为Type用Type作为类型别名，使结点类型的定义具有更好的通用性2020/1/287单链表无论是哪一种建立方法,共同的操作是:•最主要的是指向第一个结点的头指针,有时需要设一个指向最后一个结点的尾指针以方便操作,注意头指针该如何修改•逐个申请结点空间•对每个结点的数据域赋值•每个结点的指针域如何赋值取决于建立方法•将新结点加入到链表中,即修改链表中某一个结点的指针域方法1:后插法的关键是:•新结点的指针域值一定为空,因为它是新的最后一个结点•头指针只要修改一次,即在空链状态下插入第一个点时修改•保证tail指针始终指在当前链表的最后一个结点处,即新结点p插入链表之后,要做赋值:tail=p;以后通过tail-next=p;就可以实现在尾部插入新结点动态演示过程2020/1/288单链表方法2:前插法的关键是:•新结点的指针域值一定赋值为head,成为新的第一个结点•头指针每插入一个新结点就要修改一次,保证永远指向新的第一个结点处•这种插入方法无需定义tail指向最后一个结点,代码最简洁方法3:按序插入法的关键是:•首先要通过搜索找到新结点的插入位置,这在后面有序插入算法中介绍•假设找到的插入位置是在p1指针所指的结点后,在p2指针所指的结点前插入•则关键的语句为:p1-next=p;和p-next=p2;动态演示过程动态演示过程2020/1/289单链表单链表的遍历：从头指针开始，顺着各个指针，依次访问链表中的各个结点•关键是确定遍历的条件,即何时循环,何时终止•根据单链表的最后一个指针域为空,可以让一个工作指针指向当前结点,不断后移,如果该指针为空,则链表遍历结束•关键代码:•for(p=head;p;p=p-next)•printNode(p-data);单链表的查找：在单链表中搜索是否存在这样的结点，其数据域或数据域的某一项等于给定待搜索的值。•查找返回:若存在则返回指向该结点的指针,否则返回空指针•关键代码:•while(p&&!equal(p-data,data,1))•p=p-next;该函数是根据结点的数据域类型定义的一个输出函数动态演示过程动态演示过程该函数是根据结点的数据域类型定义的一个判断元素值是否相等的函数2020/1/2810单链表单链表的插入:向一个单链表中插入以给定值为数据域信息的结点。常见的插入方法有两种：•①直接在链表尾部插入•②依照数据域的值有序（非递减有序或非递增有序）插入•无论哪一种方法的插入，都需要通过指针申请一个新结点空间,然后将该结点通过修改特定结点的指针域插入链表中单链表的删除:从单链表中删除指定值的结点•首先要用遍历的思想查找该值的结点是否在单链表存在•一定要有一个指向待删除结点前趋结点位置的指针以便删除尾插演示过程序插演示过程删除演示过程2020/1/2811单链表单链表的逆置:将原单链表中各结点的指向关系置反•原来的前趋变后继•原来的第一个结点变成最后一个结点•原来的最后一个结点变成第一个结点•并且所有相邻结点的指向关系都要置反单链表的完整操作:完整程序由4个文件组成：•(1)node.h:定义链表结点的类型,Type代表结点的数据域类型•(2)prepare.h:定义结点的数据成员类型中需要的一些基本操作,从而保证无论Type代表何种类型,链表的基本操作不变•(3)list.h:定义了单链表的各种操作,包括用3种方法建立链表、插入、删除、查找、遍历、逆置等基本操作•(4)li12_1.c：测试单链表各种应用的完整程序，包含了以上3个文件，其中定义了菜单函数，运行函数和主函数逆置演示过程请在VC++下运行完整程序进行演示2020/1/2812其他类型的单链表（1）单循环链表:•为什么要循环：单链表如果丢失了头指针则无法访问链表•改进方法：将单链表最后一个结点的指针域由空指针改为指向链表的第一个结点形成一个循环链•好处：从任意一个结点位置开始均可以遍历整个单链表•变化：用遍历思想进行访问时链表结束的终止条件不是p==NULL而是p在向后移动过一次以后，再一次满足p==head。（2）带表头结点的单链表:•为什么要带表头：单链表中插入或删除一个结点时一定要考虑是否需要修改头指针,操作不方便•改进方法：在单链表真正的第一个结点前面增加一个附加结点,其数据域通常不放什么有用信息，该结点称为表头结点•好处：插入或删除时无需考虑修改头指针的问题•变化：用遍历思想访问时终止条件不变但多1次指针的移动2020/1/2813其他类型的单链表（3）带表头结点的单循环链表:•改进方法：将前两种结合起来，既带表头结点又将最后一个结点的指针域指向头结点处•好处：既解决了丢失头指针无法访问整个链表的问题，又解决了插入、删除操作时的便利性问题。•变化：在编程时，进行插入和删除操作时无需考虑是否在第一个元素结点前面插入，同时遍历链表结束的条件不是p==NULL，而是p在向后移动过一次以后，再一次满足p==head引申：双链表（选讲）•区别：如果一个链表中各个结点的指针域有两个，分别指向其直接前趋和直接后继，就成为双向链表,第一个结点指向前趋的指针和最后一个结点指向后继的指针均为空指针•变化：在插入和删除时需要修改的指针数量比单链表要加倍•类比:双链表也可以有带表头的、循环的、带表头的循环2020/1/2814学生成绩档案管理系统的设计与实现功能：•读入学生信息、以数据文件的形式存储学生信息；可以增加、修改、删除学生的信息；按学号、姓名、名次查询学生信息；可以依学号顺序浏览学生信息；可以统计每门课的最高分、最低分以及平均分；计算每个学生的总分并排名。用结构化程序设计的思想，将系统分成5大功能模块:•显示基本信息•基本信息管理:插入、删除、修改学生记录3个子模块•学生成绩管理：计算学生总分、根据总分排名两个子模块•考试成绩统计：求课程最高分、最低分、平均分3个子模块•根据条件查询：根据学号、姓名、名次查询3个子模块2020/1/2815为实现该系统，需要解决以下问题：•①数据的表示，用什么样的数据类型能正确、合理、全面地表示学生的信息，每个学生必须要有哪些信息。•②数据的存储，用什么样的结构存储学生的信息，有利于可扩充性并方便操作。•③数据的永久保存问题，数据以怎样的形式保存在磁盘上，避免数据的重复录入。•④如何能做到便于操作，即人机接口的界面友好，方便使用者的操作。学生成绩档案管理系统的设计与实现2020/1/2816数据类型的定义:用结构类型表示每个学生的信息•structStudent•{longnum;•charname[20];•charsex[10];•intscore[3];•inttotal;•intrank;•};•typedefstructStudentType;存储结构的选择：一维数组还是单链表？•无论从内存空间的使用效率上，还是操作的便捷程度上，单链表结构要优于数组结构，以Type为结点的数据域类型学生成绩档案管理系统的设计与实现2020/1/2817为直接使用list.h中定义的各种单链表操作的函数，需要对node.h和prepare.h两个文件中的内容作相应改造文件的选择：用二进制文件存储学生的信息•在file.h中定义3个主要的函数：•voidcreateFile()：建立初始的数据文件•structnode*readFile(structnode*head)：将文件中的内容读出置于单链表中•voidsaveFile(structnode*head)：将链表中各结点的值依次写入文件学生成绩档案管理系统的设计与实现2020/1/2818完整的程序用两级菜单四层多个函数5个文件实现：•①修改后的node.h（见12.2.1节）•②修改后的prepare.h（见12.2.2节）•③file.h（见12.2.3节）•④list.h（见12.1.8节的第3个文件，无需改动）•⑤li12_2.c，系统实现的最主要文件在VC++下运行程序进行演示学生成绩档案管理系统的设计与实现2020/1/2819本章小结本章主要介绍了单链表的各种操作及一个管理系统的实现。关于单链表：•（1）如何用指针和结构体递归定义形成单链表，对单链表的各种操作：建立、遍历、插入、删除、查找、逆置等方法进行了详细介绍并用完整的代码实现•（2）强调代码重用思想，对结点的数据类型用自定义类型标识符Type来表示，定义特定的基本操作，从而保证了单链表各种操作的实现函数的代码的通用性•（3）单链表的定义与实现过程中可能会用到C语言的所有知识：基本数据类型、自定义类型，为实现各种操作，需要运用函数的定义与调用、流程控制、动态结点空间的申请与释放、递归思想等2020/1/2820本章小结关于学生成绩档案管理系统：•（1）如何用模块化程序设计思想对系统的功能进行合理划分，再用相应的函数对应实现相关功能•（2）开发一个实用系统首先需要分析所处理的数据的类型定义，以及选择合理的数据存储方式•（3）用文件实现数据的永久保存是开发一个实用系统必须提供的功能•（4）代码重用的考虑：本系统的实现基于单链表结构，因此考虑直接使用单链表处理的所有函数，根据元素类型的特殊性，定义并实现一些基本操作•（5）以菜单方式提供操作的选择，界面友好操作便捷并具一定的容错性，也是开发一个实用系统需要考虑的问题2020/1/2821Theendofchapter12