第08章+指针的应用----链表(黑体).ppt

1、1,本章的学习目标: 了解数组的缺点和动态数组的概念； 了解链表和数组的区别； 掌握动态分配函数的应用； 掌握静态链表和简单的动态链表; 能利用链表实现动态数组。,第八章 指针的应用-链表,2,本章概要,8.1 链表概述 8.2 简单静态链表 8.3动态链表和动态内存分配函数 8.4 建立动态链表 8.5 对链表的插入与删除操作 8.6 链表综合应用,3,数组作为存放同类数据的集合，给我们在程序设计时带来很多的方便，增加了灵活性，比如批量处理数据、通过下标支持随机存取等。但数组也同样存在一些弊病。,第八章 指针的应用-链表,4,数组的大小在定义时要事先规定，不能在程序中进行调整，这样一来，在程

2、序设计中针对不同问题有时需要3 0个元素的数组，有时需要5 0个元素的数组，大小难于统一。我们只能够根据可能的最大需求来定义数组，常常会造成一定存储空间的浪费。 数组的大小是固定的，缺乏使用弹性。 数组中的数据支持随机存取，但是数据毕竟是顺序存放的。当要对数组中的数据进行添加、删除等操作的时候，常常需要大量的搬动其他元素。,第八章 指针的应用-链表,5,我们希望构造动态的数组，随时可以调整数组的大小，以满足不同问题的需要。这可以做到吗？ 答案是肯定的，通过动态链表就可以做到！,第八章 指针的应用-链表,6,所谓链表，是由具有指针域的结构体（在链表中把它叫作节点）构成的，节点之间通过各自的指针域

3、连接起来（第n个节点的地址等于第n-1个节点的指针域）形成的一种链式结构，链表之名由此而得。,8.1 链表概述,7,下面是链表的图示，有助于理解上面的内容。,8.1 链表概述,8,观察图8-1可以发现，如果想在第x个节点和第x+1个节点之间插入新节点，只需要让第x个节点的指针域指向新节点而新节点的指针域指向第x+1个节点，其他的节点不需要移动。如果要删除第x个节点，只需要把第x-1个节点的指针域指向第x+1个节点，也不需要移动其他节点。 这是由于链表中的数据不是顺序存放的，因此给数据的插入和删除带来了方便，进行节点的插入和删除不再总是需要大量地移动其他数据。,8.1 链表概述,9,其实链表根据

4、数据节点的存储空间是否动态开辟还可以分为静态链表和动态链表。它们的区别在这里先简单的提出，后续章节将详加讨论：,静态链表：数据节点静态生成。 动态链表：数据节点根据需要动态开辟而生成。,8.1 链表概述,10,一个链表如果它的节点不是根据需要动态产生的，那么它就是静态链表。 就是说有多少节点要事先确定，且在程序的开头进行开辟，程序结束存储空间才释放，不能在程序中根据需要动态地增加和开辟节点，也不能动态地删除和回收节点的存储空间。 由于所有节点事先静态生成，因此它可以和数组一样支持随机存取。在对数据的存取效率上和数组一样。但作为链表它支持快速插入和快速删除（插入和删除节点时不需要大量搬动其他数据

5、）,这是数组所不具备的优点。,8.2 简单静态链表,11,例8-1一个简单链表，用于存储3个学生的基本信息。,/*8_1.c*/ #define NULL 0 struct student long num; float score; struct student *next; ;,main() struct student a, b, c, *head, *p; a. num=99101; a.score=89.5; b. num=99103; b.score=90; c. num=99107; c.score=85; head= ,8.2 简单静态链表,运行结果: 99101 89.5 9

6、9103 90.0 99107 85.0,12,8.2 简单静态链表,13,有3个学生的信息需要存储，于是这个程序里面定义了3个结构体变量。如果又新来了一个学生呢？那么就要在程序中定义4个结构体变量。可是事先是不可预知到底有多少学生的信息需要存储的（比如在学籍管理的过程中学生转学、退学等情况是突发的），唯一的解决方法就是事先尽可能多地开辟一些存储空间。可以看到静态链表和数组一样，同样缺乏弹性、浪费空间、不够灵活！,8.2 简单静态链表,14,8.3.1动态链表 所谓动态链表是指能在程序执行过程中动态建立和动态变化的链表。其实动态链表如果除去动态分配内存空间的因素，就是一个静态链表。,8.3 动

7、态链表和动态内存分配函数,15,现在让我们通过表7-1描述一下数组、静态链表和动态链表的不同：,表 8-1数组、静态链表和动态链表的特性,8.3 动态链表和动态内存分配函数,16,8.3.2动态内存分配函数 想要动态地根据需要开辟和回收存储空间，通过调用动态内存分配函数可以做到这一点。因此要学习动态链表，首先就要学习能实现动态开辟存储空间功能的几个函数。,8.3 动态链表和动态内存分配函数,17,1.malloc函数 (1) 函数原型： void *malloc(unsigned int size); (2)作用 在内存的动态存储区中分配一个长度为size的的连续空间。 (3)函数返回值 返回

8、一个指向分配域起始地址的指针（类型为void*），若未能成功执行则返回空指（NULL）。,8.3 动态链表和动态内存分配函数,18,2.calloc函数 (1) 函数原型： void *calloc(unsigned int n, unsigned int size); (2)作用 在内存的动态存储区中分配n个长度为size的的连续空间。 (3)函数返回值 返回一个指向分配域起始地址的指针(类型为void*)，若未能成功执行则返回空指针(NULL)。,8.3 动态链表和动态内存分配函数,19,3.free函数 (1) 函数原型： void free(void *p); (2)作用 释放由p指向

9、的内存区，使这部分内存区能被其他变量所使用。 (3)函数返回值 无,8.3 动态链表和动态内存分配函数,20,8.3.3利用指针和动态内存分配函数实现不定长数组 我们知道，数组的长度是个常量表达式，这就决定了数组的长度不能根据程序的上下文而定，缺乏基本的灵活性。通过前面的学习，我们知道指针和数组的关系很密切，事实上利用指针和动态内存分配函数可以实现不定长的数组，即长度是变量表达式的数组。,8.3 动态链表和动态内存分配函数,21,对于程序段 int a=2; int ba*3; 在编译的时候是通不过的，因为C语言规定数组的长度是常量表达式。现在希望数组b的长度根据变量a的值的变化而变化，单纯地

10、利用数组是不能得到实现的。,8.3 动态链表和动态内存分配函数,22,但是请看下面的程序段： int a=2; int *b=(int *)malloc(sizoof(a*3); 该程序段将会开辟以b为首地址的连续的a*3个int空间，而b就相当于数组名，因为数组名也就是内存中连续多个同种类型数据的首地址，而此时的b亦然。,8.3 动态链表和动态内存分配函数,23,这个知识点是很有利用价值的，这已经是一种动态数组的简单实现（因为开辟空间的长度不再必须是常量表达式），有些书籍上（如95年的电脑报合订本的一篇文章）就称这种实现为动态数组!,但请注意，这个数组虽然长度不定，但还不是真正意义上的动态数

11、组。因为其元素尚不能动态地插入和删除，确定长度的时候可以“动态”，但是一旦确定之后，长度就不能再动态了变化（除非再次动态分配内存）。可见要实现真正的动态数组，还得利用动态链表！,8.3 动态链表和动态内存分配函数,24,掌握了动态内存分配函数，要实现动态链表就不难了。动态链表和静态链表在数据节点的结构和连接上是没有区别的，唯一的区别是节点存储单元的开辟方式和时机不同。因此建立动态链表和建立静态链表的方式是很相似的。,8.4 建立动态链表,25,一个动态链表（以后就简称为链表）的结点，其结构体的内容分为两部分：,数据域：用来存储本身数据。 链域或称为指针域：用来存储下一个结点地址或者说指向其直接

12、后继的指针。,8.4 建立动态链表,26,例如： typedef struct student long num; /*学号*/ char name20; /*姓名*/ int age; /*年龄*/ char sex; /*性别*/ float score; /*分数*/ struct student *next; /*用来存储它的直接后继节点的地址*/ stud; 这样就定义了一个链表的节点结构体。,8.4 建立动态链表,27,定义好了链表的节点结构之后，在程序运行的时候在数据域中存储适当的数据，如有后继结点，则把链域指向其直接后继，若没有，则置为NULL。,8.4 建立动态链表,28,动

13、态链表的创建过程有以下几步： 1)定义链表的数据节点的结构体类型。创建一个空表。 2) 利用m a l l o c ( )函数向系统申请分配一个节点。 3) 将新节点的指针成员赋值为空。若是空表，将新节点连接到表头；若是非空表，将新节点接到表尾。 4) 判断一下是否有后续节点要接入链表，若有转到3)，否则结束。,8.4 建立动态链表,29,8.4 建立动态链表,30,注意：在链表的创建过程中，链表的头指针是非常重要的参数。因为对链表的输出和查找都要从链表的头开始，所以链表创建成功后，要返回一个链表头节点的地址，即头指针。,8.4 建立动态链表,31,例8-2 创建一个存放学生信息（学号，性别，

14、年龄）（输入负数做结束标志）的链表，并打印输出。,8.4 建立动态链表,32,#include /*包含ma l l o c( )原型的头文件*/ #include struct student /* 链表节点的结构*/ int num; char sex; int age; struct student *next; ; void main ( ) struct student *creat(); /*函数声明*/ void print(); struct student *head=NULL; /* 定义头指针*/ /*建一个空表*/ head=creat(head); /*创建链表*/

15、print(head); /*打印链表*/ ,8.4 建立动态链表,33,struct student *creat(struct student *head)/*函数返回的是与节点相同类型的指针*/ struct student *p1, *p2; p1=p2=(struct student *)malloc(sizeof(struct student); /*申请新节点*/ scanf(%d, %c, %d, /*返回链表的头指针*/ ,8.4 建立动态链表,34,void print(struct student *head) /*输出以head为头的链表各节点的值*/ struct s

16、tudent *temp; temp=head; /*取得链表的头指针*/ if(head!=NULL) while(temp!=NULL) printf(%6d, %c, %dn, temp-num, temp-sex, temp-age); temp=temp-next; return ; ,8.4 建立动态链表,35,注意：写动态内存分配的程序时应注意，请尽量对分配是否成功进行检测。,8.4 建立动态链表,36,链表建立好后，当又需要保存新的数据时向系统申请存储空间，并将数据接入链表中。对链表而言，表中的数据可以依次接到表尾或连结到表头，也可以视情况插入表中，对不再需要的数则进行删除操作

17、。,8.5 对链表的插入与删除操作,37,8.5.1 对链表的删除操作,图 8_5 动态链表节点的删除,DATA,pointer,节点x-1,DATA,pointer,节点x,DATA,pointer,DATA,pointer,节点n,节点x+1,NULL,pointer,head,8.5 对链表的插入与删除操作,38,注：很显然，原来的节点x+1应变成了新的节点x，节点总数从n变成n-1。,节点的删除操作是比较简单的，如图8_5可以看到，要删除节点x只需要让节点x-1的指针域指向节点x+1即可，此时节点x所占据的内存还没有回收，但是节点x在链表中已经被删除了。从链表中删除该节点后，可以用fr

18、ee函数来释放该节点所占据的内存。,8.5 对链表的插入与删除操作,39,8.5.2对链表的插入操作,DATA,pointer,图 8_6 动态链表节点的插入,新节点,DATA,pointer,节点x,DATA,pointer,DATA,pointer,节点n,节点x+1,NULL,pointer,head,DATA,pointer,节点x,DATA,pointer,DATA,pointer,节点n,节点x+1,NULL,pointer,head,新节点,DATA,pointer,8.5 对链表的插入与删除操作,40,注：很显然，新节点成了节点x+1，节点x+1应变成了新的节点x+2，节点总数从n变成n+1,节点的插入操作是接点的删除操作的逆过程，但是比删除操作要稍微麻烦点。如图8_6可以看到，要在节点x和x+1之间插入一个新的节点，只需要让节点x的指针域指向新节点而新节点的指针域指向节点x+1即可。,8.5 对链表的插入与删除操作,41,例8-3 以链表作为主数据结构，以结构体数组作为辅助空间设计一个学籍管理系统。可以实现学生信息的输入、插入、删除、输出查看的功能。（很明显是个不完善、不合理的学籍管理系统，因为每次数据都