《数据结构 教学课件 ppt 作者 周颜军 王玉茹 关伟洲 编著 第3章 链表》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 周颜军 王玉茹 关伟洲 编著 第3章 链表（25页珍藏版）》请在金锄头文库上搜索。
1、 第 3 章 链 表 上一章介绍的顺序表是线性表的顺序存储结构，采用顺序存储结构，内存的存储密度高；当结点等长时，可以随机地存取表中的结点。但是，在顺序表中进行插入和删除结点的运算时，往往会造成大量结点的移动，效率较低；顺序表的存储空间常采用静态分配，在程序运行前就必须明确规定它的存储规模，如果线性表的长度n变化较大，则存储规模很难预先确定。估计过大将导致空间的浪费，估计小了，随着结点的不断插入，所需的存储空间超出了预先分配的存储空间，就会发生空间溢出。为了有效地克服顺序存储的不足，可以采用链接存储的方式。链接存储适合于结点插入或删除频繁，存储空间需求不能预先确定的情形。链接存储是最常用的存储
2、方式之一，它不仅可以用来存储线性表，而且也可以用来存储各种非线性结构。在后续章节将要讨论的各种复杂的数据结构(如树形结构、图结构等)，都可以采用链表来进行存储。本章仅介绍几种存储线性表的链接存储方式。首先讨论单链表，以及基于单链表的栈与队列的表示方法，然后讨论单循环链表与双链表。最后给出结点类与链表类的描述。3.1 单链表单链表(singly linked list)是一种最简单的链表，又称为线性链表。它是最基本的链表结构，也是学习其他链表的基础。3.1.1单链表的概念用单链表来表示线性表时，每个数据元素占用一个结点(node)。每个结点均由两个域(字段)组成：一个域存放数据元素(data)；
3、另一个域存放指向结点后继的指针(next)。终端结点没有后继，它next域为空(NULL)，在图示中用表示。另外还需要一个表头指针head指向表的第一个结点。单链表中的结点形式为：一个线性表(a0, a1, , an-1)的单链表结构如图3-1所示。图3-1(a)是非空链表，它所表示的线性表为 L = ( a0, a1, , an-1 )图3-1(b)是空链表，是链表一种特殊情况。此时它所表示的的线性表为空表： L = ( ) 这种链表中的每个结点只有一个指针域，所以称之为单链表(或线性链表)。3.1.2 单链表的存储描述假设data字段均为相同的数据类型。用C语言描述的的单链表如下：type
4、def int datatype; / 假设结点的数据域的类型为整型typedef struct node / 结点类型定义 datatype data; / 结点的数据域 struct node *next; / 结点的指针域 ListNode, *LinkList;ListNode *p, *q, *r; LinkList head;datatype x; 这里需要注意以下几点： 在上面的类型定义和变量说明中，ListNode* 和LinkList是不同名字的同一个指针类型，不同的命名使得含义更加明确。例如，ListNode* 类型的指针变量p表示它是指向某一结点的指针，而LinkList
5、类型的指针变量head则表示它是单链表的头指针。 要严格区分指针变量与结点变量这两个概念。指针变量是一种特殊的变量，它的值是所指结点(在说明部分即类型定义和变量说明中已明确)的地址；而结点变量就是通常意义下的变量。例如：上面的定义的变量p是类型为ListNode* 的指针变量，若p的值非空(p!=NULL)，则它的值是类型为ListNode的某一个结点的地址。而结点变量的类型则是ListNode。通常p所指的结点变量并非在变量说明部分明显的定义，而是在程序执行的过程中，当需要时才通过申请空间而产生，因此把这种变量称为动态变量。 存储空间的动态申请(分配)与释放(归还)：C语言提供了两个标准函数
6、malloc( )和free( )来完成这两项工作。申请时使用malloc( )函数，例如：p = (ListNode* ) malloc(sizeof ( ListNode );表示分配了一个类型为ListNode的结点变量的空间，并把其首地址放入指针变量p中。再例如：int *s;s = ( int* ) malloc( sizeof ( int );表示分配了一个类型为int的结点变量的空间，并把其首地址放入指针变量s中。当指针变量所指的结点变量空间不再需要，可以通过标准函数free( )来释放(即把使用后的存储空间归还给系统)。对于上面的两个申请，释放时可写成：free( p );fr
7、ee( s );C+ 提供了更为简洁的方式: 使用两个运算符 new 和delete来完成空间的申请(分配)与释放(归还)。上面的例子用C+ 等价地描述为申请空间： p = new ListNode;s = new int;释放空间： delete p; delete s;由于C+ 提供的方式使用简单且功能又强，因此，我们使用new 和delete来实现空间的申请与释放。 由于这种结点变量是动态申请的，因此无法利用预先定义的标识符去访问它，而只能通过指针变量来访问它。如前面的说明中有：ListNode *p;这里指针变量为p，结点变量为 *p，即用 *p作为该结点变量的名字来访问。由于结点类型
8、ListNode是结构类型，因而 *p是结构名，还需用成员选择符“.”来访问该结构的两个分量(*p).data和(*p).next。这种表示形式比较繁琐，可选用另一种成员选择符“-”来访问指针所指结构的成员更为方便，即p-data和p-next。3.1.3 在单链表上实现的基本运算下面我们讨论用单链表作为存储结构时，如何实现线性表的一些基本运算。1. 访问单链表中的第i个结点在顺序存储时，我们根据下标(索引)值，可以按公式：LOC( ai ) = LOC( a0 ) + i*c，直接计算求得第i个结点的地址，而时间与i的大小无关。在链接存储时，需要从指针变量head所指的头结点开始沿着next
9、字段组成的链，一个一个结点地向后搜索，直到第i个结点为止。因此，查找ai所需的时间代价与i的大小成正比。说明：在后面的单链表的算法中，假定结点都为ListNode 类型。进入算法前，指针head已经指向单链表的首结点。变量p和q是两个指针(变量)。这里，0 i n-1, 算法结束时，p中存放着要找的第i个结点的地址。当单链表中结点数小于i或i 0时，函数返回值为NULL。 算法3.1 查找链表第i个结点地址 Locate( head, i )1. 若 i next3. return p;4. 算法结束 算法的执行时间主要花费在循环语句上，它显然与i的大小有关。在等概率的情况下，查找的平均时间复
10、杂度为： AMN( 或 Mavg ) = 请读者自行与顺序存储结构进行对照比较。2. 单链表的插入在链表中，结点间的关系是通过指针的链接实现的，而与结点在存储器的位置无关。只须改变相应结点的next字段的值就行了。当需要一个新结点时，通过执行q = new ListNode;就可以能得到一个新结点，它的地址存放在指针变量q中，空间的大小与q所指结点类型ListNode的大小相同。插入运算是将值为x的新结点插入到表的第i个结点的位置上，即插入在ai-1和a i之间。因此首先需要找到ai -1的存储地址p，然后生成一个值为x的新结点 *q，并通过调整指针来完成结点的插入工作。插入过程见图3-3。具
11、体算法如下：算法3.2 单链表的插入 Insert( head, i, x )1. q = new ListNode;q -data x2. 若i = 0 则q -next head; headq 否则 p Locate(head,i-1); 若 p = NULL 则 print(error);算法结束 q-next p -next; p -next q3. 算法结束 设单链表的长度为n，合法的插入位置是 0in。算法所花费的时间主要分为两部分： 该算法调用了查找第i-1个结点地址的过程：Locate(head,i-1,p)，在前面的算法分析中我们已知道它的时间代价为O(n)； 当确定了插入位
12、置(根据返回的指针p )后，接下来的工作就是通过调整指针将生成的值为x的新结点插入，这时，无论是插入在表的什么位置，都是由两条赋值语句就可完成。因此，就插入动作来说，它的时间代价仅为O(1)。综合以上的分析，虽然对整个算法来说时间代价为O( n)，但是它的主要的执行时间是花费在查找上，而真正进行插入的时间仅为常量级。所以，一般地说，插入操作的时间代价为O(1)。3. 单链表的删除删除运算是将表的第i个结点删去。由于在单链表中结点ai的存储地址是在前驱结点ai -1的指针域next中，因此需要先找到结点ai -1的存储位置并用指针p指向它。然后让p-next指向ai 的后继结点，即把ai 从链上
13、摘掉。最后释放结点ai 的存储空间，可以使用C+ 的delete操作符来完成，把删除结点的地址放于q中，执行delete q; 就把此结点的存储空间释放掉了，即归还给了可利用空间表(list of available space)，也叫作存储池(storage pool)。删除过程见图3-4。具体算法如下：算法3.3 单链表的删除 Delete( head, i )1. 若i = 0则q head; head q-next否则 p Locate( head, i-1); 若p = NULL则print(error);算法结束 若 p-next = NULL则 print(no ith node
14、); 算法结束 q p -next; p-next q-next2. delete q 3. 算法结束 设单链表的长度为n，合法的删除位置是 0in-1。与插入算法的分析类似，该算法的时间代价为O( n)，它主要的执行时间也是花费在查找定位上，而用在删除操作上的时间代价仍为O( 1 )。3.1.4 带表头结点的单链表为了运算的方便，在实际应用中，可以在链表的表头指针和开始结点之间附加一个称作表头结点的特殊结点，如图3-5所示。表头结点的data域并不存放线性表的数据元素，它常为空，有时也可以存放一些辅助信息(如表中的结点个数等)。增加表头结点的好处是使得运算简单、处理方便。具体来说，有以下两条： 由于开始结点的
