C语言程序设计.ppt

第10章 指针 v15.2 链表的相关概念 v15.2 链表的操作 15.2 链表的相关概念 v链表是由一个个结点顺序连接起来构成的表，称为链表。 其中，结点用来存放元素信息和下一个元素的地址。链表 中的元素在逻辑上相邻，在物理上不一定相邻。而数组中 的元素逻辑上相邻，在物理上也一定相邻。本节主要讲解 链表的基本概念和动态内存分配。 15.1 链表的相关概念 v15.1.1 链表 v1链表 v链表是由结点连接而成，结点就表示一个元素的信息。 链表就是通过地址（指针）将每个结点（元素）连接起 来的表。例如，链表中的元素包括A、B、C、D，如图 15.1所示。 15.1 链表的相关概念 v在图15.1中，链表由4个结点构成，每个结点包括两个域 ：数据域和指针域。数据域用来存放数据信息，指针域表 示地址信息，指向下一个结点的地址。数据域存放的是A 、B、C、D。在C语言中，通常用箭头表示结点之间 的先后关系，一个结点的指针指向下一个相邻的元素。这 样利用指针将结点连接起来的表就构成了链表。 15.1 链表的相关概念 v如果要访问链表中的元素，需要先找到第一个结点，为了 找到链表的第一个结点，还需要一个指针指向第一个结点 ，我们称这样的指针为头指针，记作head。另外，最后一 个元素D的结点没有其它结点，将最后一个结点的指针域 置为NULL。如图15.2所示。 15.1 链表的相关概念 v2定义链表的结点 v链表是由结点构成，结点包括数据域和指针域。一个结 点可以包括一个或多个数据域，因此，需要将结点定义 为结构体类型。因为指针域是指向自身一样的结构体类 型数据，如图15.2中的元素A所在结点的指针域指向元 素B所在的结点，而A和B都是同一个类型。 15.1 链表的相关概念 struct student/*定义结点类型*/ char data; /*数据域*/ struct student *next; /*next是指针域，指向结 构体类型struct student*/ ; v其中，指针域是一个指向struct student的结构体指针类 型。我们将这种存在指针指向自己的结构体类型称为自 引用类型。 15.1 链表的相关概念 v如果有如下的结构体类型定义： struct student int no; /*学号*/ char name20; /*姓名*/ char addr30;/*地址*/ struct student *next;/*next是指向struct student的指针*/ ; 15.1 链表的相关概念 v这种结点构成的链表如图15.3所示。 15.1 链表的相关概念 v15.1.2 动态存储分配 v链表中的结点是动态存储分配的，而不是由系统自动分配 的。动态存储分配是在使用前才进行分配内存空间，使用 完毕就可以释放内存空间。内存空间的分配和释放由用户 自己决定。 v1。malloc函数动态内存分配函数 v函数malloc的主要作用是分配一块长度为size的内存空间 。函数原型如下： vvoid *malloc(unsigned int size); 15.1 链表的相关概念 v函数malloc常常与运算符sizeof配合使用。例如，要分配 一个大小为40的int型的内存空间，代码如下： vint *p; vp=(int*)malloc(sizeof(int)*40); 15.1 链表的相关概念 v2。free函数动态内存释放函数 v函数free的主要作用是将动态分配的内存空间释放。它的 函数原型如下： void free(void *p); v其中，参数p指向要释放的内存空间。函数free没有返回值 。 函数原型malloc和free都在头文件stdlib.h和alloc.h中定义。 15.2 链表的操作 v链表的主要操作包括：创建链表、输出链表、链表的查 找、链表的插入和链表的删除。 15.2.1 链表的创建 v链表的创建就是将一个个结点连接在一起。创建链表的 步骤如下： v 动态生成结点。 v 输入结点的数据。 v 将结点连接在一起。 15.2 链表的操作 v例如，要将3个字符X、Y和Z依次存放到结点中，构成 一般链表。需要先定义一个结点类型，代码如下： struct node char ch; struct node *next; ListNode; 15.2 链表的操作 v1将第一个字符X插入到链表中 v先动态生成一个结点，用p指向该结点。代码如下： vp=(ListNode*)malloc(sizeof(ListNode); v然后将X存放到结点的数据域ch中，代码如下： vp-ch=X; v让头指针head指向第一个结点，代码如下： vhead=p; v这样就将第一个结点的插入到链表中。 15.2 链表的操作 v插入第一个结点的过程如图15.4所示。 15.2 链表的操作 v2将第二个字符Y插入到链表中 v动态生成一个结点，将字符Y存放到该结点中，代码如下 ： p=(ListNode*)malloc(sizeof(ListNode); p-ch=Y; v将第2个结点连接在第1个结点之后。代码如下： q-next=p; v让q指向第二个结点，即当前链表的最后一个结点。代码 如下： q=p; 15.2 链表的操作 v插入第二个结点的过程如图15.5所示。 15.2 链表的操作 v3将第三个字符Z插入到链表中 v与前两步类似，先动态生成一个结点，并将字符C存 放到该结点，代码如下： p=(ListNode*)malloc(sizeof(ListNode); p-ch=Z; v然后将q指向结点*p，代码如下： q-next=p; v因为p指向的结点是最后一个结点，所以将该结点的 指针域置为NULL。代码如下： p-next=NULL; 15.2 链表的操作 v插入最后一个结点的过程如图15.6所示。 15.2 链表的操作 v15.2.2 链表的输出 v链表的输出就是将链表中的各个结点的数据依次输出。输 出链表的操作非常简单，定义一个指针变量p，使其指向 链表的第一个结点。然后输出p指向的结点，并让p指向下 一个结点。依次类推，直到输出所有结点的元素。 15.2 链表的操作 v输出链表的函数如下： void displist(struct node *h) struct node *p=h; while(p!=NULL) printf(“%4c“,p-ch); p=p-next; 15.2 链表的操作 15.2.3 链表的查找 v链表的查找操作就是在链表中查找指定值的元素，如果找 到，返回该结点的指针，否则返回NULL。链表的查找操 作必须从链表的头指针开始，依次与结点的值进行比较。 直到找到结点或到达链表的末尾，查找操作结束。 15.2 链表的操作 v链表的查找操作与链表的输出操作是类似的，只是多 了一个比较的过程。链表的查找操作实现如下： struct node *findnode(struct node *h,char x) struct node *p=h; while(p!=NULL return p; 15.2 链表的操作 v15.2.4 链表的插入操作 v链表的插入操作是在链表中指定位置插入一个新结点。要将 一个结点插入到链表中，需要解决以下两个问题： v（1）查找插入点。 v（2）将新结点插入到链表中。 15.2 链表的操作 v插入过程如图15.7所示。 15.2 链表的操作 v将新结点插入到*r之后需要两步操作，代码如下： p-next=r-next;/*将*p的指针域指向*r的下一个结 点*/ r-next=p; /*将*r的指针域指向*p*/ v说明：在链表中插入新结点并不需要移动链表中的元素， 只需要修改指针的指向即可。 15.2 链表的操作 15.2.5 链表的删除操作 v删除链表中元素值为a的结点，操作过程如图15.8所示。 15.2 链表的操作 v删除元素值为a的结点的关键代码如下： r=findnode2(h,a);/*查找要删除的结点，返回 值r指向要删除结点的前一个结点*/ p=r-next; /*p指向要删除的结点*/ r-next=p-next; /*删除p指向的结点，使*p脱链*/ free(p); /*释放p指向的结点的内存空间*/ 15.2 链表的操作 15.2.6 链表的应用举例学生信息管理系统 【例15.2】建立一个学生信息管理系统，管理系统有一 个目录菜单，包括6个选项： v1.建立学生信息链表 v2.插入一名新的学生 v3.从链表中删除学生 v4.在链表中查找学生; v5.在链表中浏览信息; v6.退出程序结束操作 v根据需要选择其中