第08章 指针的应用 链表黑体.ppt

1
本章概要
链表概述
简单静态链表
动态链表和动态内存分配函数
建立动态链表
对链表的插入与删除操作
链表综合应用
2
数组作为存放同类数据的集合,给我们在程序设计时带来很多的方便,增加了灵活性,比如批量处理数据、通过下标支持随机存取等。但数组也同样存在一些弊病。
第八章指针的应用----链表
3
数组的大小在定义时要事先规定,不能在程序中进行调整,这样一来,在程序设计中针对不同问题有时需要3 0个元素的数组,有时需要5 0个元素的数组,大小难于统一。我们只能够根据可能的最大需求来定义数组,常常会造成一定存储空间的浪费。
数组的大小是固定的,缺乏使用弹性。
数组中的数据支持随机存取,但是数据毕竟是顺序存放的。当要对数组中的数据进行添加、删除等操作的时候,常常需要大量的搬动其他元素。
第八章指针的应用----链表
4
我们希望构造动态的数组,随时可以调整数组的大小,以满足不同问题的需要。这可以做到吗? 答案是肯定的,通过动态链表就可以做到!
第八章指针的应用----链表
5
所谓链表,是由具有指针域的结构体(在链表中把它叫作节点)构成的,节点之间通过各自的指针域连接起来(第n个节点的地址等于第n-1个节点的指针域)形成的一种链式结构,链表之名由此而得。
链表概述
6
下面是链表的图示,有助于理解上面的内容。
DATA
pointer
节点1
DATA
pointer
节点2
DATA
pointer
节点n-1
图8_1 链表
DATA
pointer
节点n
…………..
链表概述
7
观察图8-1可以发现,如果想在第x个节点和第x+1个节点之间插入新节点,只需要让第x个节点的指针域指向新节点而新节点的指针域指向第x+1个节点,其他的节点不需要移动。如果要删除第x个节点,只需要把第x-1个节点的指针域指向第x+1个节点,也不需要移动其他节点。
这是由于链表中的数据不是顺序存放的,因此给数据的插入和删除带来了方便,进行节点的插入和删除不再总是需要大量地移动其他数据。
链表概述
8
其实链表根据数据节点的存储空间是否动态开辟还可以分为静态链表和动态链表。它们的区别在这里先简单的提出,后续章节将详加讨论:
静态链表:数据节点静态生成。
动态链表:数据节点根据需要动态开辟而生成。
链表概述
9
一个链表如果它的节点不是根据需要动态产生的,那么它就是静态链表。
就是说有多少节点要事先确定,且在程序的开头进行开辟,程序结束存储空间才释放,不能在程序中根据需要动态地增加和开辟节点,也不能动态地删除和回收节点的存储空间。
由于所有节点事先静态生成,因此它可以和数组一样支持随机存取。在对数据的存取效率上和数组一样。但作为链表它支持快速插入和快速删除(插入和删除节点时不需要大量搬动其他数据),这是数组所不具备的优点。
简单静态链表
10
例8-1一个简单链表,用于存储3个学生的基本信息。
/**/
#define NULL 0
struct student
{
long num;
float score;
struct student *next;
};
main()
{ struct student a, b, c, *head, *p;
a. num=99101; =;
b. num=99103; =90;
c. num=99107; =85;
head=&a; =&b; =&c;
=NULL; p=head;
do
{ printf("%ld %\n", p->num, p->score);
p=p->next;
} while(p!=NULL);
}
简单静态链表
运行结果:
99101
99103
99107