《C语言程序设计》PPT课件(I)

《《C语言程序设计》PPT课件(I)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第10章指针15.2链表的相关概念15.2链表的操作15.2链表的相关概念链表是由一个个结点顺序连接起来构成的表，称为链表。其中，结点用来存放元素信息和下一个元素的地址。链表中的元素在逻辑上相邻，在物理上不一定相邻。而数组中的元素逻辑上相邻，在物理上也一定相邻。本节主要讲解链表的基本概念和动态内存分配。15.1链表的相关概念15.1.1链表1．链表链表是由结点连接而成，结点就表示一个元素的信息。链表就是通过地址（指针）将每个结点（元素）连接起来的表。例如，链表中的元素包括A、B、C、D，如图15.1所示。15.1链表的相

2、关概念在图15.1中，链表由4个结点构成，每个结点包括两个域：数据域和指针域。数据域用来存放数据信息，指针域表示地址信息，指向下一个结点的地址。数据域存放的是’A’、’B’、’C’、’D’。在C语言中，通常用箭头表示结点之间的先后关系，一个结点的指针指向下一个相邻的元素。这样利用指针将结点连接起来的表就构成了链表。15.1链表的相关概念如果要访问链表中的元素，需要先找到第一个结点，为了找到链表的第一个结点，还需要一个指针指向第一个结点，我们称这样的指针为头指针，记作head。另外，最后一个元素’D’的结点没有其它结点，将

3、最后一个结点的指针域置为NULL。如图15.2所示。15.1链表的相关概念2．定义链表的结点链表是由结点构成，结点包括数据域和指针域。一个结点可以包括一个或多个数据域，因此，需要将结点定义为结构体类型。因为指针域是指向自身一样的结构体类型数据，如图15.2中的元素’A’所在结点的指针域指向元素’B’所在的结点，而’A’和’B’都是同一个类型。15.1链表的相关概念structstudent/*定义结点类型*/{chardata;/*数据域*/structstudent*next;/*next是指针域，指向结构体类型str

4、uctstudent*/};其中，指针域是一个指向structstudent的结构体指针类型。我们将这种存在指针指向自己的结构体类型称为自引用类型。15.1链表的相关概念如果有如下的结构体类型定义：structstudent{intno;/*学号*/charname[20];/*姓名*/charaddr[30];/*地址*/structstudent*next;/*next是指向structstudent的指针*/};15.1链表的相关概念这种结点构成的链表如图15.3所示。15.1链表的相关概念15.1.2动态存储分配

5、链表中的结点是动态存储分配的，而不是由系统自动分配的。动态存储分配是在使用前才进行分配内存空间，使用完毕就可以释放内存空间。内存空间的分配和释放由用户自己决定。1。malloc函数──动态内存分配函数函数malloc的主要作用是分配一块长度为size的内存空间。函数原型如下：void*malloc(unsignedintsize);15.1链表的相关概念函数malloc常常与运算符sizeof配合使用。例如，要分配一个大小为40的int型的内存空间，代码如下：int*p;p=(int*)malloc(sizeof(int

6、)*40);15.1链表的相关概念2。free函数──动态内存释放函数函数free的主要作用是将动态分配的内存空间释放。它的函数原型如下：voidfree(void*p);其中，参数p指向要释放的内存空间。函数free没有返回值。函数原型malloc和free都在头文件stdlib.h和alloc.h中定义。15.2链表的操作链表的主要操作包括：创建链表、输出链表、链表的查找、链表的插入和链表的删除。15.2.1链表的创建链表的创建就是将一个个结点连接在一起。创建链表的步骤如下：动态生成结点。输入结点的数据。将结点连接在

7、一起。15.2链表的操作例如，要将3个字符’X’、’Y’和’Z’依次存放到结点中，构成一般链表。需要先定义一个结点类型，代码如下：structnode{charch;structnode*next;}ListNode;15.2链表的操作1．将第一个字符’X’插入到链表中先动态生成一个结点，用p指向该结点。代码如下：p=(ListNode*)malloc(sizeof(ListNode));然后将’X’存放到结点的数据域ch中，代码如下：p->ch=’X’;让头指针head指向第一个结点，代码如下：head=p;这样就将第

8、一个结点的插入到链表中。15.2链表的操作插入第一个结点的过程如图15.4所示。15.2链表的操作2．将第二个字符’Y’插入到链表中动态生成一个结点，将字符’Y’存放到该结点中，代码如下：p=(ListNode*)malloc(sizeof(ListNode));p->ch=’Y’;将第2个结点连接在第1个结点之后。