C语言程序设计课件第章

1、2022-3-231C语言程序设计 2022-3-232第十二章 高级程序设计主讲主讲: : 计算机学院计算机学院 朱立华朱立华n本章介绍单链表的相关知识以及一个管理系统的模块化本章介绍单链表的相关知识以及一个管理系统的模块化设计方法设计方法, , 综合运用所学知识实现一个完整的系统综合运用所学知识实现一个完整的系统n关于单链表掌握以下知识：关于单链表掌握以下知识：为什么需要单链表为什么需要单链表如何通过指针和结构体的定义实现单链表结构如何通过指针和结构体的定义实现单链表结构单链表常用操作的实现方法单链表常用操作的实现方法:建立、遍历、插入、删除、查找、建立、遍历、插入、删除、查找、逆置逆置其

2、他类型的链表结构简介其他类型的链表结构简介n学生档案成绩管理系统的设计与实现：学生档案成绩管理系统的设计与实现：如何划分模块，每一个模块的具体功能是什么如何划分模块，每一个模块的具体功能是什么数据类型的定义数据类型的定义用文件实现数据的永久存储用文件实现数据的永久存储系统的完整实现系统的完整实现n为什么需要链表结构？为什么需要链表结构？一批类型相同的数据用数组存储所存在的问题：一批类型相同的数据用数组存储所存在的问题：(1)(1)定义静态数组时必须指定数组的元素个数，此后无法更定义静态数组时必须指定数组的元素个数，此后无法更改数组大小，可能造成空间浪费或不足改数组大小，可能造成空间浪费或不足(

3、2)(2)用指针可以申请动态数组，空间不会浪费或不足，但仍用指针可以申请动态数组，空间不会浪费或不足，但仍然是需要连续的存储空间然是需要连续的存储空间(3)(3)在数组中插入或删除元素时需要大量移动元素，效率低在数组中插入或删除元素时需要大量移动元素，效率低n什么是链表结构什么是链表结构？与数组不同，数组元素逻辑上相邻物理地址上也相邻，而链与数组不同，数组元素逻辑上相邻物理地址上也相邻，而链表结构其数据元素作为一个个表结构其数据元素作为一个个结点结点的的数据域数据域，结点中另有，结点中另有指指针域针域存储逻辑上相邻的其他元素的起始地址，存储逻辑上相邻的其他元素的起始地址，单链表单链表较常用较常

4、用数据域数据域指针域指针域单链表的单链表的一个结点一个结点n一个单链表一个单链表示例：示例：n n链表结构的优点是：链表结构的优点是：系统不必为应用程序分配一组连续的空间，可以充分利用系系统不必为应用程序分配一组连续的空间，可以充分利用系统的零散空间；有一个元素就生成一个结点，空间不浪费统的零散空间；有一个元素就生成一个结点，空间不浪费如果内存空间足够大，理论上这一批数据的容量不受限制如果内存空间足够大，理论上这一批数据的容量不受限制对于插入、删除等操作不必通过移动元素实现，效率高对于插入、删除等操作不必通过移动元素实现，效率高n单链表的结点定义单链表的结点定义-用结构体和指针递归定义而成用结

5、构体和指针递归定义而成1 12 23 34 40 0这是最重要这是最重要的头指针的头指针最后一个结点的指最后一个结点的指针域值为针域值为0(NULL)0(NULL)n单链表结点定义的格式：单链表结点定义的格式：ntypedef typedef intint Type; Type;nstruct Node struct Node n nType data; Type data; nstruct Node struct Node * *next;next;n; ; n特别提醒特别提醒：nextnext前的前的* *号不能丢失，否则就成为死循环定义啦号不能丢失，否则就成为死循环定义啦! !n（一）单

6、链表的建立：（一）单链表的建立：常用的有常用的有3 3种建立方法：种建立方法：后插法：后插法：新结点插入在链表的最尾部，作为新的尾结点新结点插入在链表的最尾部，作为新的尾结点前插法：前插法：新结点插入在链表的最前部，作为新的第一个结点新结点插入在链表的最前部，作为新的第一个结点按序插入法：按序插入法：新结点插入在链表的特定部位保持元素值有序新结点插入在链表的特定部位保持元素值有序结点的结构体类型定义结点的结构体类型定义单链表结点的数据成员类型不同只需要将单链表结点的数据成员类型不同只需要将intint替换成数替换成数据成员实际的类型，下面结点的类型定义不变据成员实际的类型，下面结点的类型定义不

7、变结点的指针成员名结点的指针成员名nextnext，类，类型为型为struct Nodestruct Node* *结点的数据成员名结点的数据成员名datadata，类型为类型为TypeType 用用TypeType作为类型别名，使结点类作为类型别名，使结点类型的定义具有更好的通用性型的定义具有更好的通用性n无论是哪一种建立方法无论是哪一种建立方法, ,共同的操作是共同的操作是: :最主要的是指向第一个结点的最主要的是指向第一个结点的头指针头指针,有时需要设一个指向有时需要设一个指向最后一个结点的最后一个结点的尾指针尾指针以方便操作以方便操作,注意头指针该如何修改注意头指针该如何修改逐个逐个申

8、请结点空间申请结点空间对每个结点的对每个结点的数据域赋值数据域赋值每个结点的每个结点的指针域指针域如何如何赋值赋值取决于建立方法取决于建立方法将新结点加入到链表中将新结点加入到链表中,即修改链表中某一个结点的指针域即修改链表中某一个结点的指针域n方法方法1:后插法的关键是后插法的关键是:新结点的指针域值一定为空新结点的指针域值一定为空,因为它是新的最后一个结点因为它是新的最后一个结点头指针只要修改一次头指针只要修改一次,即在空链状态下插入第一个点时修改即在空链状态下插入第一个点时修改保证保证tail指针始终指在当前链表的最后一个结点处指针始终指在当前链表的最后一个结点处,即新结点即新结点p插入

9、链表之后插入链表之后,要做赋值要做赋值: tail=p; 以后通过以后通过tail-next=p;就就可以实现在尾部插入新结点可以实现在尾部插入新结点动动态态演示演示过过程程n方法方法2:2:前插法的关键是前插法的关键是: : 新结点的指针域值一定赋值为新结点的指针域值一定赋值为head,head,成为新的第一个结点成为新的第一个结点 头指针每插入一个新结点就要修改一次头指针每插入一个新结点就要修改一次, ,保证永远指向新的保证永远指向新的第一个结点处第一个结点处 这种插入方法这种插入方法无需定义无需定义tailtail指向最后一个结点指向最后一个结点, ,代码最简洁代码最简洁n方法方法3:3

10、:按序插入法的关键是按序插入法的关键是: : 首先要通过搜索找到新结点的插入位置首先要通过搜索找到新结点的插入位置, ,这在后面有序插入这在后面有序插入算法中介绍算法中介绍 假设找到的插入位置是在假设找到的插入位置是在p1p1指针所指的结点后指针所指的结点后, ,在在p2p2指针所指针所指的结点前插入指的结点前插入 则关键的语句为则关键的语句为: :p1-next=p;p1-next=p; 和和 p-next=p2;p-next=p2; 动动态态演示演示过过程程动动态态演示演示过过程程n单链表的遍历：单链表的遍历：从头指针开始，顺着各个指针，依次访从头指针开始，顺着各个指针，依次访问链表中的各

11、个结点问链表中的各个结点 关键关键是确定遍历的条件是确定遍历的条件, ,即何时循环即何时循环, ,何时终止何时终止根据单链表的根据单链表的最后一个指针域为空最后一个指针域为空, ,可以让一个工作指针指向可以让一个工作指针指向当前结点当前结点, ,不断后移不断后移, ,如果该指针为空如果该指针为空, ,则链表遍历结束则链表遍历结束关键代码关键代码: :for(p = head; p; p = p-next) printNode(p-data); n单链表的查找：单链表的查找：在单链表中搜索是否存在这样的结点，在单链表中搜索是否存在这样的结点，其数据域或数据域的某一项等于给定待搜索的值。其数据域或

12、数据域的某一项等于给定待搜索的值。 查找返回查找返回: :若存在则返回指向该结点的若存在则返回指向该结点的指针指针, ,否则返回否则返回空指针空指针关键代码关键代码:while(p&!equal(p-data,data,1) p=p-next; 该函数是根据结点该函数是根据结点的数据域类型定义的数据域类型定义的一个输出函数的一个输出函数动动态态演示演示过过程程动动态态演示演示过过程程该函数是根据结点的数据该函数是根据结点的数据域类型定义的一个判断元域类型定义的一个判断元素值是否相等的函数素值是否相等的函数n单链表的插入单链表的插入: :向一个单链表中插入以给定值为数据域向一个单链表中插

13、入以给定值为数据域信息的结点。信息的结点。n常见的插入方法有常见的插入方法有两种两种： 直接在链表尾部插入直接在链表尾部插入 依照数据域的值有序（非递减有序或非递增有序）插入依照数据域的值有序（非递减有序或非递增有序）插入 无论哪一种方法的插入，都需要通过指针申请一个新结点空无论哪一种方法的插入，都需要通过指针申请一个新结点空间间, ,然后将该结点通过修改特定结点的指针域插入链表中然后将该结点通过修改特定结点的指针域插入链表中 n单链表的删除单链表的删除: :从单链表中删除指定值的结点从单链表中删除指定值的结点 首先要用遍历的思想查找该值的结点是否在单链表存在首先要用遍历的思想查找该值的结点是

14、否在单链表存在 一定要有一个指向待删除结点一定要有一个指向待删除结点前趋结点位置的指针前趋结点位置的指针以便删除以便删除尾尾插插演示演示过过程程序序插插演示演示过过程程删删除除演示演示过过程程n单链表的逆置单链表的逆置: :将原单链表中各结点的指向关系置反将原单链表中各结点的指向关系置反原来的前趋变后继原来的前趋变后继原来的第一个结点变成最后一个结点原来的第一个结点变成最后一个结点原来的最后一个结点变成第一个结点原来的最后一个结点变成第一个结点并且所有相邻结点的指向关系都要置反并且所有相邻结点的指向关系都要置反 n单链表的完整操作单链表的完整操作: :完整程序由完整程序由4 4个文件组成：个文

15、件组成：(1)node.h(1)node.h: :定义链表结点的类型定义链表结点的类型,Type,Type代表结点的数据域类型代表结点的数据域类型(2)prepare.h(2)prepare.h: :定义结点的数据成员类型中需要的一些基本操定义结点的数据成员类型中需要的一些基本操作作, ,从而保证无论从而保证无论TypeType代表何种类型代表何种类型, ,链表的基本操作不变链表的基本操作不变(3)list.h:(3)list.h:定义了单链表的各种操作定义了单链表的各种操作, ,包括用包括用3 3种方法建立链种方法建立链表、插入、删除、查找、遍历、逆置等基本操作表、插入、删除、查找、遍历、逆

16、置等基本操作(4)li12_1.c(4)li12_1.c：测试单链表各种应用的完整程序，包含了以上：测试单链表各种应用的完整程序，包含了以上3 3个文件，其中定义了菜单函数，运行函数和主函数个文件，其中定义了菜单函数，运行函数和主函数逆逆置置演示演示过过程程请在请在VC+VC+下运行完下运行完整程序进行演示整程序进行演示n（1 1）单循环链表）单循环链表: :为什么要循环为什么要循环：单链表如果丢失了头指针则无法访问链表：单链表如果丢失了头指针则无法访问链表改进方法改进方法：将单链表最后一个结点的指针域由空指针改为指：将单链表最后一个结点的指针域由空指针改为指向链表的第一个结点形成一个循环链向

17、链表的第一个结点形成一个循环链好处好处：从任意一个结点位置开始均可以遍历整个单链表：从任意一个结点位置开始均可以遍历整个单链表变化：变化：用遍历思想进行访问时链表结束的终止条件不是用遍历思想进行访问时链表结束的终止条件不是p=NULLp=NULL而是而是p p在向后移动过一次以后，再一次满足在向后移动过一次以后，再一次满足p=headp=head。n（2 2）带表头结点的单链表）带表头结点的单链表: :为什么要带表头为什么要带表头：单链表中插入或删除一个结点时一定要考：单链表中插入或删除一个结点时一定要考虑是否需要修改头指针虑是否需要修改头指针, ,操作不方便操作不方便改进方法改进方法：在单链

18、表真正的第一个结点前面增加一个附加结：在单链表真正的第一个结点前面增加一个附加结点点, ,其其数据域通常不放什么有用信息，该结点称为数据域通常不放什么有用信息，该结点称为表头结点表头结点好处好处：插入或删除时无需考虑修改头指针的问题：插入或删除时无需考虑修改头指针的问题变化：变化：用遍历思想访问时终止条件不变但多用遍历思想访问时终止条件不变但多1 1次指针的移动次指针的移动n（3 3）带表头结点的单循环链表）带表头结点的单循环链表: :改进方法改进方法：将前两种结合起来，既带表头结点又将最后一个：将前两种结合起来，既带表头结点又将最后一个结点的指针域指向头结点处结点的指针域指向头结点处好处好处

19、：既解决了丢失头指针无法访问整个链表的问题，又解：既解决了丢失头指针无法访问整个链表的问题，又解决了插入、删除操作时的便利性问题。决了插入、删除操作时的便利性问题。变化：变化：在编程时，进行插入和删除操作时无需考虑是否在第在编程时，进行插入和删除操作时无需考虑是否在第一个元素结点前面插入，同时遍历链表结束的条件不是一个元素结点前面插入，同时遍历链表结束的条件不是p=NULLp=NULL，而是，而是p p在向后移动过一次以后，再一次满足在向后移动过一次以后，再一次满足p=headp=headn引申：双链表引申：双链表（选讲）（选讲）区别：区别：如果一个链表中各个结点的指针域有两个，分别指向如果一

20、个链表中各个结点的指针域有两个，分别指向其直接前趋和直接后继，就成为双向链表其直接前趋和直接后继，就成为双向链表, ,第一个结点指向前第一个结点指向前趋的指针和最后一个结点指向后继的指针均为空指针趋的指针和最后一个结点指向后继的指针均为空指针变化：变化：在插入和删除时需要修改的指针数量比单链表要加倍在插入和删除时需要修改的指针数量比单链表要加倍类比类比: :双链表也可以有双链表也可以有带表头的、循环的、带表头的循环带表头的、循环的、带表头的循环n功能：功能：读入学生信息、以数据文件的形式存储学生信息；可以增加、读入学生信息、以数据文件的形式存储学生信息；可以增加、修改、删除学生的信息；按学号、

21、姓名、名次查询学生信息；修改、删除学生的信息；按学号、姓名、名次查询学生信息；可以依学号顺序浏览学生信息；可以统计每门课的最高分、可以依学号顺序浏览学生信息；可以统计每门课的最高分、最低分以及平均分；计算每个学生的总分并排名。最低分以及平均分；计算每个学生的总分并排名。n用结构化程序设计的思想，将系统分成用结构化程序设计的思想，将系统分成5 5大功能模块大功能模块: : 显示基本信息显示基本信息基本信息管理基本信息管理: : 插入、删除、修改学生记录插入、删除、修改学生记录3 3个子模块个子模块 学生成绩管理学生成绩管理：计算学生总分：计算学生总分、根据总分排名两个子模块根据总分排名两个子模块

22、 考试成绩统计考试成绩统计：求课程最高分、最低分、平均分：求课程最高分、最低分、平均分3 3个子模块个子模块 根据条件查询根据条件查询：根据学号、姓名、名次查询：根据学号、姓名、名次查询3 3个子模块个子模块 n为实现该系统，需要解决以下问题：为实现该系统，需要解决以下问题： 数据的表示，用什么样的数据类型能正确、合理、全面地数据的表示，用什么样的数据类型能正确、合理、全面地表示学生的信息，每个学生必须要有哪些信息。表示学生的信息，每个学生必须要有哪些信息。 数据的存储，用什么样的结构存储学生的信息，有利于可数据的存储，用什么样的结构存储学生的信息，有利于可扩充性并方便操作。扩充性并方便操作。

23、 数据的永久保存问题，数据以怎样的形式保存在磁盘上，数据的永久保存问题，数据以怎样的形式保存在磁盘上，避免数据的重复录入。避免数据的重复录入。 如何能做到便于操作，即人机接口的界面友好，方便使用如何能做到便于操作，即人机接口的界面友好，方便使用者的操作。者的操作。n数据类型的定义数据类型的定义: : 用结构类型表示每个学生的信息用结构类型表示每个学生的信息 struct Student long num;char name20;char sex10;int score3;int total;int rank; ; typedef struct Student Type;n存储结构的选择存储结构

24、的选择：一维数组还是单链表？：一维数组还是单链表？ 无论从内存空间的使用效率上，还是操作的便捷程度上，单无论从内存空间的使用效率上，还是操作的便捷程度上，单链表结构要优于数组结构，以链表结构要优于数组结构，以TypeType为结点的数据域类型为结点的数据域类型 n为直接使用为直接使用list.h中定义的各种单链表操作的函数，需中定义的各种单链表操作的函数，需要对要对node.h和和prepare.h两个文件中的内容作两个文件中的内容作相应改造相应改造n文件的选择：文件的选择：用二进制文件存储学生的信息用二进制文件存储学生的信息 在在file.h中定义中定义3个主要的函数：个主要的函数： voi

25、d createFile( )：建立初始的数据文件建立初始的数据文件 struct node * readFile(struct node *head)：将文件中的内将文件中的内容读出置于单链表中容读出置于单链表中 void saveFile(struct node *head)：将链表中各结点的值依将链表中各结点的值依次写入文件次写入文件n完整的程序用两级菜单四层多个函数完整的程序用两级菜单四层多个函数5 5个文件实现：个文件实现： 修改后的修改后的node.hnode.h（见节）（见节） 修改后的修改后的prepare.hprepare.h（见节）（见节） file.hfile.h（见节）（见节） list.hlist.h（见节的第（见节的第3 3个文件，无需改动）个文件，无需改动） li12_2.cli12_2.c，系统实现的最主要文件，系统实现的最主要文件n在在VC+VC+下运行程序进行演示下运行程序进行演示n本章主要介绍了单链表的各种操作及一个管理系统本章主要介绍了单链表的各种操作及一个管理系统的实现。的实现。n关于单链表：关于单链表：（1 1）如何用指针和结构体递归定义形成单链表，对单链）如何用指针和结构体递归定义形成单链表，对单链表的各种操作：建立、遍历、插入、删除、查找、逆置等表的各种操作：建立、遍历、插入、删除、查找、逆置等方法进行了详细介绍