《C语言程序设计1实用教案》由会员分享，可在线阅读，更多相关《C语言程序设计1实用教案（32页珍藏版）》请在金锄头文库上搜索。
1、15.2 链表的相关(xinggun)概念链表是由一个个结点顺序连接起来构成的表，称为链表。其中，结点用来存放元素信息和下一个元素的地址(dzh)。链表中的元素在逻辑上相邻，在物理上不一定相邻。而数组中的元素逻辑上相邻，在物理上也一定相邻。本节主要讲解链表的基本概念和动态内存分配。第1页/共31页第一页，共32页。15.1 链表的相关(xinggun)概念15.1.1 链表1链表链表是由结点连接而成，结点就表示一个元素的信息。链表就是通过地址（指针(zhzhn)）将每个结点（元素）连接起来的表。例如，链表中的元素包括A、B、C、D，如图15.1所示。第2页/共31页第二页，共32页。15.1
2、链表的相关(xinggun)概念在图15.1中，链表由4个结点构成，每个结点包括两个域 ： 数 据 域 和 指 针 域 。 数 据 域 用 来 存 放 数 据 信 息(xnx)，指针域表示地址信息(xnx)，指向下一个结点的地址。数据域存放的是A、B、C、D。在C语言中，通常用箭头表示结点之间的先后关系，一个结点的指针指向下一个相邻的元素。这样利用指针将结点连接起来的表就构成了链表。第3页/共31页第三页，共32页。15.1 链表的相关(xinggun)概念如果要访问链表中的元素，需要(xyo)先找到第一个结点，为了找到链表的第一个结点，还需要(xyo)一个指针指向第一个结点，我们称这样的指针
3、为头指针，记作head。另外，最后一个元素D的结点没有其它结点，将最后一个结点的指针域置为NULL。如图15.2所示。第4页/共31页第四页，共32页。15.1 链表的相关(xinggun)概念2定义(dngy)链表的结点链表是由结点构成，结点包括数据域和指针域。一个结点可以包括一个或多个数据域，因此，需要将结点定义(dngy)为结构体类型。因为指针域是指向自身一样的结构体类型数据，如图15.2中的元素A所在结点的指针域指向元素B所在的结点，而A和B都是同一个类型。 第5页/共31页第五页，共32页。15.1 链表的相关(xinggun)概念struct student/*定义结点类型*/ch
4、ar data; /*数据域*/struct student *next; /*next是指针域，指向结构体类型struct student*/;其中，指针域是一个指向struct student的结构体指针类型。我们(w men)将这种存在指针指向自己的结构体类型称为自引用类型。第6页/共31页第六页，共32页。15.1 链表的相关(xinggun)概念如果(rgu)有如下的结构体类型定义：struct studentint no; /*学号*/char name20; /*姓名*/char addr30;/*地址*/struct student *next;/*next是指向struct
5、student的指针*/;第7页/共31页第七页，共32页。15.1 链表的相关(xinggun)概念这种结点(ji din)构成的链表如图15.3所示。 第8页/共31页第八页，共32页。15.1 链表的相关(xinggun)概念15.1.2 动态存储分配链表中的结点是动态存储分配的，而不是由系统自动分配的。动态存储分配是在使用前才进行分配内存空间，使用完毕(wnb)就可以释放内存空间。内存空间的分配和释放由用户自己决定。1。malloc函数动态内存分配函数函数malloc的主要作用是分配一块长度为size的内存空间。函数原型如下：void *malloc(unsigned int size
6、);第9页/共31页第九页，共32页。15.1 链表的相关(xinggun)概念函数malloc常常与运算符sizeof配合使用。例如，要分配一个大小为40的int型的内存空间，代码(di m)如下：int *p;p=(int*)malloc(sizeof(int)*40); 第10页/共31页第十页，共32页。15.1 链表的相关(xinggun)概念2。free函数(hnsh)动态内存释放函数(hnsh)函数(hnsh)free的主要作用是将动态分配的内存空间释放。它的函数(hnsh)原型如下： void free(void *p);其中，参数p指向要释放的内存空间。函数(hnsh)fre
7、e没有返回值。函数(hnsh)原型malloc和free都在头文件stdlib.h和alloc.h中定义。第11页/共31页第十一页，共32页。15.2 链表的操作(cozu)链表的主要操作包括：创建链表、输出链表、链表的查找(ch zho)、链表的插入和链表的删除。15.2.1 链表的创建链表的创建就是将一个个结点连接在一起。创建链表的步骤如下： 动态生成结点。 输入结点的数据。 将结点连接在一起。第12页/共31页第十二页，共32页。15.2 链表的操作(cozu)例如，要将3个字符X、Y和Z依次存放到结点中，构成一般链表。需要先定义一个(y )结点类型，代码如下：struct nodec
8、har ch;struct node *next;ListNode;第13页/共31页第十三页，共32页。15.2 链表的操作(cozu)1将第一个字符X插入到链表中先动态(dngti)生成一个结点，用p指向该结点。代码如下：p=(ListNode*)malloc(sizeof(ListNode);然后将X存放到结点的数据域ch中，代码如下：p-ch=X;让头指针head指向第一个结点，代码如下：head=p;这样就将第一个结点的插入到链表中。 第14页/共31页第十四页，共32页。15.2 链表的操作(cozu)插入第一个结点(ji din)的过程如图15.4所示。第15页/共31页第十五页
9、，共32页。15.2 链表的操作(cozu)2将第二个字符Y插入到链表中动态生成一个结点，将字符Y存放到该结点中，代码如下：p=(ListNode*)malloc(sizeof(ListNode);p-ch=Y;将第2个结点连接在第1个结点之后。代码如下： q-next=p;让q指向(zh xin)第二个结点，即当前链表的最后一个结点。代码如下： q=p;第16页/共31页第十六页，共32页。15.2 链表的操作(cozu)插入第二个结点(ji din)的过程如图15.5所示。第17页/共31页第十七页，共32页。15.2 链表的操作(cozu)3将第三个字符Z插入到链表中与前两步类似，先动态
10、生成一个结点，并将字符C存放(cnfng)到该结点，代码如下：p=(ListNode*)malloc(sizeof(ListNode);p-ch=Z;然后将q指向结点*p，代码如下： q-next=p;因为p指向的结点是最后一个结点，所以将该结点的指针域置为NULL。代码如下： p-next=NULL;第18页/共31页第十八页，共32页。15.2 链表的操作(cozu)插入最后一个(y )结点的过程如图15.6所示。第19页/共31页第十九页，共32页。15.2 链表的操作(cozu)15.2.2 链表的输出链表的输出就是(jish)将链表中的各个结点的数据依次输出。输出链表的操作非常简单，
11、定义一个指针变量p，使其指向链表的第一个结点。然后输出p指向的结点，并让p指向下一个结点。依次类推，直到输出所有结点的元素。第20页/共31页第二十页，共32页。15.2 链表的操作(cozu)输出链表的函数(hnsh)如下：void displist(struct node *h)struct node *p=h;while(p!=NULL)printf(%4c,p-ch);p=p-next;第21页/共31页第二十一页，共32页。15.2 链表的操作(cozu)15.2.3 链表的查找链表的查找操作就是在链表中查找指定值的元素，如果找到，返回该结点的指针，否则返回NULL。链表的查找操作必
12、须从链表的头指针开始，依次与结点的值进行(jnxng)比较。直到找到结点或到达链表的末尾，查找操作结束。第22页/共31页第二十二页，共32页。15.2 链表的操作(cozu)链表的查找操作与链表的输出操作是类似(li s)的，只是多了一个比较的过程。链表的查找操作实现如下：struct node *findnode(struct node *h,char x)struct node *p=h;while(p!=NULL&p-ch!=x)p=p-next;return p;第23页/共31页第二十三页，共32页。15.2 链表的操作(cozu)15.2.4 链表的插入操作链表的插入操作是在链表
13、中指定(zhdng)位置插入一个新结点。要将一个结点插入到链表中，需要解决以下两个问题：（1）查找插入点。（2）将新结点插入到链表中。第24页/共31页第二十四页，共32页。15.2 链表的操作(cozu)插入(ch r)过程如图15.7所示。第25页/共31页第二十五页，共32页。15.2 链表的操作(cozu)将新结点插入到*r之后需要两步操作，代码如下：p-next=r-next;/*将*p的指针域指向(zh xin)*r的下一个结点*/r-next=p; /*将*r的指针域指向(zh xin)*p*/说明：在链表中插入新结点并不需要移动链表中的元素，只需要修改指针的指向(zh xin)
14、即可。第26页/共31页第二十六页，共32页。15.2 链表的操作(cozu)15.2.5 链表的删除操作(cozu)删 除 链 表 中 元 素 值 为 a的 结 点 ， 操 作(cozu)过程如图15.8所示。 第27页/共31页第二十七页，共32页。15.2 链表的操作(cozu)删除元素值为a的结点的关键代码如下(rxi)：r=findnode2(h,a);/*查找要删除的结点，返回值r指向要删除结点的前一个结点*/p=r-next; /*p指向要删除的结点*/r-next=p-next; /*删除p指向的结点，使*p脱链*/free(p); /*释放p指向的结点的内存空间*/第28页/
15、共31页第二十八页，共32页。15.2 链表的操作(cozu)15.2.6 链表的应用举例学生信息管理系统【例15.2】建立一个学生信息管理系统，管理系统有一个目录菜单(ci dn)，包括6个选项：1.建立学生信息链表2.插入一名新的学生3.从链表中删除学生4.在链表中查找学生;5.在链表中浏览信息;6.退出程序结束操作根据需要选择其中一项，来实现链表的创建、结点插入、信息查找、删除结点、浏览信息、退出功能。学生信息包括学号和姓名。第29页/共31页第二十九页，共32页。15.3 小结(xioji)使用链表有两个好处：不需要像数组一样事先分配存储单元，不必担心空间定义过小无法适应程序的需要，也
16、不必担心定义过大造成空间浪费；在插入和删除操作过程中，不需要移动大量的元素。链表是一种顺序存取的结构(jigu)，因此，要访问链表中的某个结点，必须从头指针开始。第30页/共31页第三十页，共32页。感谢您的欣赏(xnshng)！第31页/共31页第三十一页，共32页。内容(nirng)总结15.2 链表的相关概念。其中，结点用来存放元素信息和下一个元素的地址(dzh)。而数组中的元素逻辑上相邻，在物理上也一定相邻。链表就是通过地址(dzh)（指针）将每个结点（元素）连接起来的表。我们将这种存在指针指向自己的结构体类型称为自引用类型。动态存储分配是在使用前才进行分配内存空间，使用完毕就可以释放内存空间。函数malloc的主要作用是分配一块长度为size的内存空间。函数free的主要作用是将动态分配的内存空间释放第三十二页，共32页。
