资源描述：
《C语言程序设计 教学课件 作者 朱立华 王立柱 C语言程序设计课件第12章091122.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、C语言程序设计2021/8/141第十二章高级程序设计主讲:计算机学院朱立华内容提要本章介绍单链表的相关知识以及一个管理系统的模块化设计方法,综合运用所学知识实现一个完整的系统关于单链表掌握以下知识：为什么需要单链表如何通过指针和结构体的定义实现单链表结构单链表常用操作的实现方法:建立、遍历、插入、删除、查找、逆置其他类型的链表结构简介学生档案成绩管理系统的设计与实现：如何划分模块，每一个模块的具体功能是什么数据类型的定义用文件实现数据的永久存储系统的完整实现2021/8/143单链表为什么需要链表结构？一批类型
2、相同的数据用数组存储所存在的问题：(1)定义静态数组时必须指定数组的元素个数，此后无法更改数组大小，可能造成空间浪费或不足(2)用指针可以申请动态数组，空间不会浪费或不足，但仍然是需要连续的存储空间(3)在数组中插入或删除元素时需要大量移动元素，效率低什么是链表结构？与数组不同，数组元素逻辑上相邻物理地址上也相邻，而链表结构其数据元素作为一个个结点的数据域，结点中另有指针域存储逻辑上相邻的其他元素的起始地址，单链表较常用数据域指针域单链表的一个结点2021/8/144单链表一个单链表示例：链表结构的优点是：系统不
3、必为应用程序分配一组连续的空间，可以充分利用系统的零散空间；有一个元素就生成一个结点，空间不浪费如果内存空间足够大，理论上这一批数据的容量不受限制对于插入、删除等操作不必通过移动元素实现，效率高单链表的结点定义----用结构体和指针递归定义而成12340这是最重要的头指针最后一个结点的指针域值为0(NULL)2021/8/145单链表单链表结点定义的格式：typedefintType;structNode{Typedata;structNode*next;};特别提醒：next前的*号不能丢失，否则就成为死循环定
4、义啦!（一）单链表的建立：常用的有3种建立方法：后插法：新结点插入在链表的最尾部，作为新的尾结点前插法：新结点插入在链表的最前部，作为新的第一个结点按序插入法：新结点插入在链表的特定部位保持元素值有序结点的结构体类型定义单链表结点的数据成员类型不同只需要将int替换成数据成员实际的类型，下面结点的类型定义不变结点的指针成员名next，类型为structNode*结点的数据成员名data，类型为Type用Type作为类型别名，使结点类型的定义具有更好的通用性2021/8/146单链表无论是哪一种建立方法,共同的操作
5、是:最主要的是指向第一个结点的头指针,有时需要设一个指向最后一个结点的尾指针以方便操作,注意头指针该如何修改逐个申请结点空间对每个结点的数据域赋值每个结点的指针域如何赋值取决于建立方法将新结点加入到链表中,即修改链表中某一个结点的指针域方法1:后插法的关键是:新结点的指针域值一定为空,因为它是新的最后一个结点头指针只要修改一次,即在空链状态下插入第一个点时修改保证tail指针始终指在当前链表的最后一个结点处,即新结点p插入链表之后,要做赋值:tail=p;以后通过tail->next=p;就可以实现在尾部插入新结
6、点动态演示过程2021/8/147单链表方法2:前插法的关键是:新结点的指针域值一定赋值为head,成为新的第一个结点头指针每插入一个新结点就要修改一次,保证永远指向新的第一个结点处这种插入方法无需定义tail指向最后一个结点,代码最简洁方法3:按序插入法的关键是:首先要通过搜索找到新结点的插入位置,这在后面有序插入算法中介绍假设找到的插入位置是在p1指针所指的结点后,在p2指针所指的结点前插入则关键的语句为:p1->next=p;和p->next=p2;动态演示过程动态演示过程2021/8/148单链表单链表的
7、遍历：从头指针开始，顺着各个指针，依次访问链表中的各个结点关键是确定遍历的条件,即何时循环,何时终止根据单链表的最后一个指针域为空,可以让一个工作指针指向当前结点,不断后移,如果该指针为空,则链表遍历结束关键代码:for(p=head;p;p=p->next)printNode(p->data);单链表的查找：在单链表中搜索是否存在这样的结点，其数据域或数据域的某一项等于给定待搜索的值。查找返回:若存在则返回指向该结点的指针,否则返回空指针关键代码:while(p&&!equal(p->data,data,1))
8、p=p->next;该函数是根据结点的数据域类型定义的一个输出函数动态演示过程动态演示过程该函数是根据结点的数据域类型定义的一个判断元素值是否相等的函数2021/8/149单链表单链表的插入:向一个单链表中插入以给定值为数据域信息的结点。常见的插入方法有两种：①直接在链表尾部插入②依照数据域的值有序（非递减有序或非递增有序）插入无论哪一种方法的插入，都需要通过指针申请一个
