C语言程序设计PPT.ppt
《C语言程序设计PPT.ppt》由会员分享,可在线阅读,更多相关《C语言程序设计PPT.ppt(31页珍藏版)》请在三一文库上搜索。
1、第10章 指针,15.2 链表的相关概念 15.2 链表的操作,15.2 链表的相关概念,链表是由一个个结点顺序连接起来构成的表,称为链表。其中,结点用来存放元素信息和下一个元素的地址。链表中的元素在逻辑上相邻,在物理上不一定相邻。而数组中的元素逻辑上相邻,在物理上也一定相邻。本节主要讲解链表的基本概念和动态内存分配。,15.1 链表的相关概念,15.1.1 链表 1链表 链表是由结点连接而成,结点就表示一个元素的信息。链表就是通过地址(指针)将每个结点(元素)连接起来的表。例如,链表中的元素包括A、B、C、D,如图15.1所示。,15.1 链表的相关概念,在图15.1中,链表由4个结点构成,
2、每个结点包括两个域:数据域和指针域。数据域用来存放数据信息,指针域表示地址信息,指向下一个结点的地址。数据域存放的是A、B、C、D。在C语言中,通常用箭头表示结点之间的先后关系,一个结点的指针指向下一个相邻的元素。这样利用指针将结点连接起来的表就构成了链表。,15.1 链表的相关概念,如果要访问链表中的元素,需要先找到第一个结点,为了找到链表的第一个结点,还需要一个指针指向第一个结点,我们称这样的指针为头指针,记作head。另外,最后一个元素D的结点没有其它结点,将最后一个结点的指针域置为NULL。如图15.2所示。,15.1 链表的相关概念,2定义链表的结点 链表是由结点构成,结点包括数据域
3、和指针域。一个结点可以包括一个或多个数据域,因此,需要将结点定义为结构体类型。因为指针域是指向自身一样的结构体类型数据,如图15.2中的元素A所在结点的指针域指向元素B所在的结点,而A和B都是同一个类型。,15.1 链表的相关概念,struct student /*定义结点类型*/ char data; /*数据域*/ struct student *next; /*next是指针域,指向结构体类型struct student*/ ; 其中,指针域是一个指向struct student的结构体指针类型。我们将这种存在指针指向自己的结构体类型称为自引用类型。,15.1 链表的相关概念,如果有如下
4、的结构体类型定义: struct student int no; /*学号*/ char name20; /*姓名*/ char addr30; /*地址*/ struct student *next; /*next是指向struct student的指针*/ ;,15.1 链表的相关概念,这种结点构成的链表如图15.3所示。,15.1 链表的相关概念,15.1.2 动态存储分配 链表中的结点是动态存储分配的,而不是由系统自动分配的。动态存储分配是在使用前才进行分配内存空间,使用完毕就可以释放内存空间。内存空间的分配和释放由用户自己决定。 1。malloc函数动态内存分配函数 函数malloc
5、的主要作用是分配一块长度为size的内存空间。函数原型如下: void *malloc(unsigned int size);,15.1 链表的相关概念,函数malloc常常与运算符sizeof配合使用。例如,要分配一个大小为40的int型的内存空间,代码如下: int *p; p=(int*)malloc(sizeof(int)*40);,15.1 链表的相关概念,2。free函数动态内存释放函数 函数free的主要作用是将动态分配的内存空间释放。它的函数原型如下: void free(void *p); 其中,参数p指向要释放的内存空间。函数free没有返回值。 函数原型malloc和fr
6、ee都在头文件stdlib.h和alloc.h中定义。,15.2 链表的操作,链表的主要操作包括:创建链表、输出链表、链表的查找、链表的插入和链表的删除。 15.2.1 链表的创建 链表的创建就是将一个个结点连接在一起。创建链表的步骤如下: 动态生成结点。 输入结点的数据。 将结点连接在一起。,15.2 链表的操作,例如,要将3个字符X、Y和Z依次存放到结点中,构成一般链表。需要先定义一个结点类型,代码如下: struct node char ch; struct node *next; ListNode;,15.2 链表的操作,1将第一个字符X插入到链表中 先动态生成一个结点,用p指向该结点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 语言程序设计 PPT
链接地址:https://www.31doc.com/p-2037521.html