C语言实用教程（第4版）教案 33 7.6 链表

沈阳职业技术学院教案用纸第11周总第33次学时：2教学班级：软件专业各班课程：C语言程序设计授课教师：刘畅课题：7.5链表教学方法：启发式、讲授式教具：常规教具教学目标：1．掌握链表的动态存储分配函数、链表的定义；2．熟练掌握链表的基本结构以及链表的简单操作教学重点：链表的新建、链表结点的插入、删除及查找链表长度操作教学难点：链表结点的插入、删除操作主要教学内容：7.5链表7.5.1链表基础知识及动态分配函数7.5.2链表的操作小结：课后回顾：沈阳职业技术学院教案用纸四个一：提问：结构体的三种定义方式导入：前面我们讲过，如果想将学生的信息存入到计算机中，可以设一个结构体类型的数组，但在实际应用过程中，有时很难在开始的时候就能确定下要输入的信息数量。这样的为题如何解决呢？正文：*7.6链表链表的知识对于复杂编程很有用处，在后面的数据结构课程中还会继续深入学习，所以链表内容对于要求编程能力高的软件其相关专业的学生为必学内容，对于其他专业的学生为选学内容。7.6.1链表基础知识及动态分配函数图7-4单链表的结点示意图前面讲过，如果想将学生的信息存入到计算机中，可以设一个结构体类型的数组，但在实际应用过程中，有时很难在开始时就确定要输入的信息数量。能不能有一种方法，可以不用事先确定存储容量的大小，随心地将每个学生的信息输入进去呢？C语言提供一种动态存储分配的数据结构，事先不必确定其长度，且各元素不必顺序存放，各元素之间以指针相互链接，称为单链表，其结点结构如图7-4所示。其中，data部分称为数据域，用于存储一个数据元素的信息。next部分称为指针域，用于存储其直接后继的存储地址的信息。在图7-5中，head为头指针，该指针指向链表的第一个结点，该结点称为头结点，不存放任何信息。其中，“∧”表示空指针，在程序中可用常量NULL来表示，它表示链表的结束。单链表分为带头结点（其next域指向链表第一个结点的存储地址）和不带头结点两种类型。带头结点的链表中每个结点的存储地址均放在其前驱结点中，这样算法对所有的结点处理可一致化，因此，本书讨论的单链表均指带头结点的单链表。带头结点的空单链表如图7-5（a）所示，带头结点的非空单链表如图7-5（b）所示。图7-5单链表示意图单链表的结构体类型及指针定义如下：typedefstructnode{intdata; /*定义数据域*/structnode*next; /*定义指针域*/}NODE;/*定义单链表存储类型并重命名为NODE*/NODE*head; /*定义结构体类型的头指针*/C语言提供了动态分配函数来实现变量的动态存储分配，常用的动态存储分配函数有以下2个。应注意的是在程序中若使用这3个函数，应在程序的开始处用文件包含命令#include包含头文件"stdio.h"或"malloc.h"，因版本不同而使用不同的包含文件。1．分配一个内存空间函数mallocmalloc函数的调用格式如下：指针名指针名=(类型名*）malloc(size);在内存中分配一个长度为size的连续存储空间，返回值是新分配存储空间的首地址，若内存不足，则返回NULL。例如：int*pt;pt=(int*)malloc(sizeof(int));/*动态生成一个整型变量并将pt指向它*/该程序段表示分配了一个int型的内存空间，并将pt指向该空间的首地址。其中的(int*)是强制将其后面的变量转换为整型指针，赋给左边的指针变量pt。2．分配n个内存空间函数calloccalloc函数的调用格式如下：指针名指针名=(类型名*）calloc(n,size);在内存中分配n块长度为size的连续存储空间，返回值是新分配存储空间的首地址，若内存不足，则返回NULL。calloc函数与malloc函数均用于动态分配存储空间，区别在于calloc函数可以一次分配n块区域。例如：char*p;p=(char*)calloc(5,sizeof(char));表示分配5个且每个大小为1个字节的连续空间，将其类型强制转换为字符类型并赋给p，结果即让p指向该存储空间的首地址。3．释放内存空间函数freefree函数的调用格式如下：free(指针名);SHAPE 释放该指针所指的一块存储空间，该空间系统可另作它用。注意这个指针所指的空间必须是由malloc函数分配的才行，free函数无返回值。free(指针名);例如：int*pt; /*定义一个整型指针pt*/pt=(int*)malloc(sizeof(int)); /*动态生成一个整型变量并将pt指向它*/free(pt); /*释放pt所指的内存单元*/7.6.2链表的操作链表常用的操作有链表的初始化、链表的建立、求链表长度、元素的查找、元素的插入、删除操作等。1．单链表的初始化单链表的初始化即构造一个仅包含头结点的空单链表。其过程是首先申请一个结点并让指针head指向该结点，然后将它的指针域赋为空（NULL），最后返回头指针head。2．单链表的建立设一个尾指针last，使其指向当前链表的尾结点。每读入有效的数据则申请一个结点s，并将读取的数据存放到新结点s的数据域中，将s的尾指针设为空指针（NULL），然后将新结点插入到当前链表尾部（last指针所指的结点后面），直到循环结束为止。3．求链表长度操作因为链表是链式结构，所以链表中元素个数不是已知的。想求表中元素个数还要设一个计数变量j（初值为0），将一个指针p先指向链表中第一个元素，当p不为空时，循环将p指针后移，j加1，循环结束后j值即为链表长度。4．元素的按值查找操作从链表的第一个元素结点开始，由前向后依次比较单链表中各结点数据域中的值，若某结点数据域中的值与给定的值x相等，则循环结束；否则继续向后比较直到表结束，然后判断指针p，若p不为空表示单链表中有x结点，输出查找成功的信息并输出x所在表中的位置；否则输出查找失败的信息。5．插入操作顺序表的插入操作需要移动大量的数据元素，而链表的插入只需修改指针而无需移动原来表中元素，那链表的插入操作是如何实现呢？在指针所指的结点后插入新结点。若要在链表中指针p所指位置后面插入一个结点，则插入操作步骤如下。（1）先将结点s的指针域指向结点p的下一个结点（执行语句s->next=p->next）。（2）再将结点p的指针域改为指向新结点s（执行语句p->next=s）。6．删除操作顺序表的删除操作同样需要移动大量的数据元素，而链表的删除只需修改指针而无需移动原来表中元素，那链表的删除操作是如何实现呢？首先通过循环定位求出第i结点的前驱结点（第i-1结点）p的地址，然后将指针s指向被删除结点，修改p->next指针，使其指向s后的结点，最后释放指针s所指结点。算法中注意if(p->next!=NULL&&j==i-1)语句，只有当第i-1结点存在（j==i-1）而p又不是终端结点即（p->next!=NULL）时，才能确定被删除结点存在。7．单链表的输