线性表的链式存储表示和实现

1、第二章 线性表第三节 线性表的链式存储表示和实现2.3.1 单链表和指针前面已经提到，由于在顺序表中插入或删除一个数据元素，平均约需移动表中一半元素。因此，对于需要经常进行插入和删除操作、表中元素相对不稳定的线性表，不应该采用顺序存储表示，而应该采用链式存储表示。 何谓"链式存储表示"?链式存储表示指的是以"附加信息(指针)" 表示数据元素之间的逻辑关系。线性表的链式存储表示的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。因此，为了表示每个数据元素与其直接后继数据元素之间的逻辑关系，对数据元素来说，除了存储

2、其本身的信息之外，还需存储一个指示其直接后继的信息（即直接后继的存储位置）。由这两部分信息组成一个"结点"（如下图所示），表示线性表中一个数据元素。数据域 m_Data指针域 m_pNext其中存储数据元素信息的域称作数据域（设域名为m_pData），存储直接后继存储位置的域称为指针域（设域名为m_pNext）。指针域中存储的信息又称做指针或链。 由分别表示, 的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表，如下图所示。由于链式存储不要求线性表的元素依次"紧挨"存放，因此在进行插

3、入和删除操作改变元素之间的关系时就不需要移动元素，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优点。和顺序表类似，在链式存储结构中仍以第一个数据元素的存储地址作为线性表的基地址，通常称它为头指针，线性表中所有数据元素都可以从头指针出发找到。因为线性表的最后一个数据元素没有后继，因此最后一个结点中的"指针"是一个特殊的值 "NULL" （在图上用表示），通常称它为"空指针"。头指针的值为第一个结点的存储位置，第一个结点中的"指针"指向第二个结点，即它的值为第二个结点的存储位置，第二个结点中的&

4、quot;指针"指向第三个结点，依次类推，直至最后一个结点。 为了便于处理一些特殊情况，在第一个结点之前附加一个"头结点"，令该结点中指针域的指针指向第一个元素结点，并令头指针指向头结点，如下图所示。头结点的结构和链表中其它结点相同，只是它的数据域中不存放任何信息，但它的指针域存放的是第一个数据元素的存储地址，即线性表的基地址。此时称指向头结点的指针为头指针。通常称这类单链表为"带头结点的单链表"。 值得注意的是，若线性表为空，在不带头结点的情况下，头指针为空(NULL)，但在带头结点的情况下，链表的头指针不为空，而是其头结点中指针域的指针为空

5、，如下图所示。 如果不特别声明的话，那么以后各节中讨论的单链表都指的是这种带头结点的链表。可以用 C 语言中的"结构指针"来描述链表结构。struct ListNode ElemType m_Data;ListNode * m_pNext;从C语言的类型定义可见，在链表中，"结点" 和 "指针" 是相互紧密关联的两个概念，不同的结点结构对应有不同的指针类型。若设ListNode *p,*q; 则 p和q 均为以上定义的指针型变量。若 p 的值非空，则表明 p 指向某个结点，p->m_Data 表示 p 所指结点中的数据域，p-&

6、gt;m_pNext 表示 p 所指结点中的指针域，若非空，则指向其"后继"结点。对变量 p 和 q 定义之后，它们的值是什么？和其它变量相同，在没有对它们进行赋值之前，它们是"没有值"的。 p->m_Data 即为(*p).m_Data，类似地，p->m_pNext 即为(*p).m_pNext。注意：只有在 p "有值" 且"值不为空"的情况下，p->m_Data 和 p->m_pNext 才有意义。指针型变量只能作同类型的指针赋值与比较操作。并且，指针型变量的"值"

7、除了由同类型的指针变量赋值得到外，都必须用 C 语言中的动态分配函数得到。例如，p = new ListNode; 表示在运行时刻系统动态生成了一个ListNode 类型的结点，并令指针 p "指向"该结点。反之，当指针 p 所指结点不再使用，可用 delete p; 释放此结点空间。 注意：一旦执行了delete p; 的语句，(*p)不再存在，自然 p->m_Data 和 p->m_pNext 也就没有意义了。2.3.2 单链表中基本操作的实现以下重点讨论线性表的五个基本操作在链式存储结构中的实现。一、初始化操作根据上一节的约定，初始化建一个空的链表即为建立

8、一个只有头结点的链表。 算法2.13void InitList(ListNode &L )/ 创建一个带头结点的空链表,L 为指向头结点的指针L.m_pNext = 0; = NULL; / InitList算法的时间复杂度为O (1)。"空"链表的头指针是否为NULL? 若链表不带头结点，则以头指针L=NULL表示空表，在带头结点的情况下，则需建立一个其指针域的指针为NULL的头结点，并令头指针指向该结点。 链表是一个进行动态存储管理的结构，因此在初始化时不需要按照线性表实际所需最大容量进行预分配。 二、销毁结构操作 算法2.14void DestroyList(

9、ListNode &L)/ 销毁以L为头指针的单链表，释放链表中所有结点空间while(L.m_pNext)ListNode *p = L.m_pNext;L.m_pNext = p->m_pNext;delete p; / while / DestroyList算法的时间复杂度为O (Listlength(L)。 "销毁结构"的操作是在该链表的使命已经完成之后进行的，则应将它占有的空间"释放"。但在C+语言中，析构函数是在类对象生命期结束的时候由系统自动调用。三、存取元素操作单链表是一种"顺序存取"的结构，即：为取第

10、i 元素，首先必须先找到第 i-1 个元素。因此不论 i 值为多少，都必须从头结点开始起"点数"，直数到第 i 个为止。头结点可看成是第0个结点。可见算法中应设一个指针变量p和一个整数变量 j，并使 p 和 j 同步变化，始终保持指针 p 指向第j的结点的状态。算法2.15int GetElem(const ListNode& L, int pos, ElemType &e )/ 若1posLengthList(L)，则用 e 带回指针L指向头结点的单链表/ 中第 pos 个元素的值且返回函数值为TRUE,否则返回函数值为FALSE ListNode *p

11、= L.m_pNext; / 变量初始化，p 指向第一个结点int j =1; while ( p && j< pos ) / 顺结点的指针向后查找，直至 p 指到第pos个结点或 p 为空止 p = p->m_pNext; +j; if ( !p | j>pos )return 0; / 链表中不存在第 pos 个结点 e = p->m_Data; / 取到第 pos 个元素 return 1;算法的时间复杂度为O (ListLength(L)。由于链表的长度是个隐含值，因此无法预先判别参数pos是否超过表长，只能在"数结点" 过程

12、中，j还没有达到 pos 时而指针变为空时才能判断出参数不合法。什么情况下会出现 j>pos 的情况？ j>pos 的情况即为 pos<1 的情况，注意：因算法中j的初值为"1"，若 pos=1，则 while 循环一次也不执行。 能否将变量初始化改为"p=L; j=0;"? 对 pos 为正常值的情况没有影响，只是使 while 循环多执行一次吧了。但此时无法用 j>pos 判别出 pos<1 的错误，当然也可以在函数一开始就加上 pos 是否大于0的判别？ 算法时间复杂度的分析：控制结构只有 while 一个单循环，基本

13、操作为"移动指针"，最坏情况是 pos>=表长的情况，指针需从头移到尾。四、插入元素操作前面已经分析过，在线性表中"插入"一个元素时，使元素之间的关系<,>改变为<,e>和<e,>。当用指针指示后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可。因为新的元素插入在线性表的第i个元素之前，使得不再是 的后继，而是新的元素e的后继，因此需要修改元素e和元素所在结点的指针。由此，算法的基本思想就是，首先找到第i-1个结点，然后修改相应指针。 算法2.16int ListInsert (ListNode &a

14、mp;L, int pos, ElemType e)/ 若1posLengthList(L)+1，则在指针L指向头结点的单链表/ 的第 pos 个元素之前插入新的元素 e，且返回函数值为 TRUE,/ 否则不进行插入且返回函数值为 FALSE ListNode *p = L.m_pNext;int j=0; while(p && j<pos-1) / 查找第pos-1个结点，并令指针p指向该结点 p = p->m_pNext;+j; if(!p | j>pos-1) return 0; / 参数不合法，pos 小于1或者大于表长+1 ListNode *s =

15、 new ListNode; if (!s)return 0; / 存储空间分配失败 s->m_Data=e; / 创建新元素的结点 s->m_pNext = p->m_pNext; p->m_pNext = s; / 修改指针 return 1;算法时间复杂度为O (ListLength(L)。这里的变量初始化能否改为 "p=L->m_pNext; j=1;"? 不行!因为插入时修改的是前驱结点的指针，因此算法中的目标是找第 pos 个结点的前驱，如果一开始，p 就指向第一个结点，那么当pos=1时就找不到它的前驱了。你想到了吗? 如果单链表

16、没有头结点，应该如何修改算法2.16? 需对在第一个结点之前进行插入的情况单独进行处理。是不是很麻烦呀？ 算法时间复杂度的分析：在插入算法中，修改指针的时间复杂度仅为O(1)，但为了修改前驱结点的指针首先要找到这个结点，因此插入算法的时间主要消耗在查询结点上，因此，其时间复杂度和"存取元素"的操作相同。五、删除元素操作和插入类似，由于删除元素改变了元素之间的关系，使不再是的后继，而是的后继，因此需要修改元素所在结点的指针。因此在单链表中删除元素操作的算法基本思想和插入相同，也是：首先找到第 i-1 个结点，然后修改相应指针。算法2.17int ListDelete(List

17、Node &L, int pos, ElemType &e)/ 若1posLengthList(L)，则删除指针L指向头结点的单链表/ 中第 pos 个元素并以 e 带回其值，返回函数值为 TRUE，/ 否则不进行删除操作且返回函数值为 FALSE ListNode *p = L.m_pNext;int j=0; while(p && j<pos-1) / 寻找第pos个结点，并令p指向其前驱 p = p->m_pNext;+j; if(!p->m_pNext | j > pos-1) return 0; / 删除位置不合理 ListNo

18、de *q = p->m_pNext; / 修改指针p->m_pNext = q->m_pNext; e = q->m_Data;delete(q); / 释放结点空间 return 1; 算法时间复杂度为O (ListLength(L)。你是否注意到了，在删除算法中参数不合理的判断条件和插入的情况不同？为什么？因为对插入而言，只要"前驱"存在即可，而对删除而言，不仅"前驱"要存在，被删结点也必须存在。你是否也想到了？ 如果单链表没有头结点，应该如何修改算法2.17? 需对删除第一个结点的情况进行单独处理。你一定也想到了，因为和插

19、入是一样的问题，对吧？ 算法时间复杂度的分析：显然，和插入一样，其时间消耗在查询前驱结点上。2.3.3 单链表其它算法举例例2-7 逆序创建链表假设线性表(,，)的数据元素存储在一维数组 An中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为"空"的链表中。解题分析：由于链表是一种动态存储管理的结构，链表中每个结点占用的存储空间不需预先分配划定，而是在运行时刻由系统应需求即时生成，因此，建立链表的过程是一个动态生成的过程。即从 "空表"起，依次建立结点，并逐个插入链表。所谓"逆序"创建链表指的是，依和线性表的逻辑顺序相

20、"逆"的次序输入元素。例如线性表 (a,b,c,d,e) 的逆序创建的过程。由于链表的生成是从最后一个结点起逐个插入，因此每个新生成的结点都是插入在链表的"第一个"结点之前，即头结点之后，使新插入的结点成为插入之后的链表中的第一个结点。 算法2.19int InsertToList_Head(ListNode& L, ElemType data)ListNode *p = new ListNode;if(!p)return 0; / 存储空间分配失败p->m_Data = data; / 赋元素值p->m_pNext = L.m_pN

21、ext; L.m_pNext = p; / 插入在头结点之后return 1;int CreateList_L(ListNode &L, int n, ElemType a) / 已知数组 A 中存有线性表的 n 个数据元素，/ 逆序建立带头结点的单链表。for(int i=0; i<n; i+)if(!InsertToList_Head(L, ai)return 0;return 1;容易看出，算法的时间复杂度为O (ListLength(L)。控制结构只有一个单循环，循环次数和表长相同。 如果是"顺序"创建单链表，那么算法该如何写呢？ 因为每个新生成的结点

22、的插入位置在表尾，则算法中必须维持一个始终指向已建立的链表表尾的指针。其实也很简单，对吗？ 例2-8 以链表作存储结构解例2-5的问题，即将线性表(,)改变成(, , , )。在以顺序表作存储结构时，我们曾分析过它的一个简单算法就是，将从起到的数据元素从原地删除后再插入到之前，而在以顺序表作存储结构时因为需要大量移动元素而不能采用。那么在以链表作存储结构时能否采用这个算法呢？ 解题分析：因为对链表来说，"插入"和"删除"仅需修改指针即可完成，并且由于前 m 个元素之间和后 n 个元素之间的链接关系分别都不需要改变，则算法的实际操作为：(1) 从链表中删除

23、(, )；(2) 将(, )链接到头结点之后；(3) 将(, )链接到之后。算法2.20void Exchange_L(ListNode &L, int m)/ 本算法实现单链表中前 m 个结点和后 n 个结点的互换 if ( m && L.m_pNext) / 链表不空且 m!=0 ListNode *p = L.m_pNext;int k = 1; while(k<m && p ) / 查找 am 所在结点 p = p->m_pNext;+k; if(p && p->m_pNext) / n!=0 时才需要修改指针

24、ListNode *ha = L.m_pNext; / 以指针 ha 记 a1 结点的位置 L.m_pNext = p->m_pNext; / 将 b1 结点链接在头结点之后 p->m_pNext = 0; / 设 am 的后继为空 ListNode *q = L.m_pNext; / 令q 指向 b1 结点 while (q->m_pNext) / 查找 bn 结点q = q->m_pNext; q->m_pNext = ha; / 将 a1 结点链接到 bn 结点之后 算法的时间复杂度为O (ListLength(L)。循环的条件中为什么要有p!=NULL的判

25、断？ 因为单链表的长度是个隐含值，在此无法如顺序表那样事先判别参数 m 是否合法，如果参数不合适，则在没有找到第 m 个结点时，p=NULL，while 循环中的语句就会出问题。 由于参数中没有给出 n 的值，只有在找到 am 之后加以判别。如果这里不加 p-> m_pNext是否为空的判别条件，下面哪一个语句会出问题？ 算法执行到 q-> m_pNext 时会出问题，因为当p-> m_pNext =NULL 时，q=NULL，q-> m_pNext 也就不成立了。这种情况对初学链表的人是最容易出问题的地方，但千万要注意避免。 整个算法就是对链表从头巡视到尾，两个单循环

26、次数之和恰为表长。因此算法的时间复杂度为O(ListLength(L)。此例充分显示了用"指针"指示"后继"的灵活性。例2-9 编写算法删除单链表中"多余"的数据元素，即使操作之后的单链表中所有元素的值都不相同。解题分析：可以和顺序表采用同样算法，即设想新建一个链表，然后顺序考察原链表中每一个结点的数据元素，在"新表"中进行查找，如果有相同的则舍弃之，否则就插入到新表中。算法2.21void Purge_L(ListNode &L )/ 删除单链表L中的冗余元素，即使操作之后的单链表中只保留/ 操作之前表中

27、所有值都不相同的元素 ListNode *p = L.m_pNext; L.m_pNext = NULL; / 设新表为空表 while (p) / 顺序考察原表中每个元素 ListNode *succ = p->m_pNext; / 记下结点 *p 的后继 ListNode *q = L.m_pNext; / q 指向新表的第一个结点 while( q && p->m_Data != q->m_Data) / 在新表中查询是否存在和p->m_Data 相同的元素q = q->m_pNext; if (!q) / 将结点 *p 插入到新的表中 p-

28、>m_pNext = L.m_pNext; L.m_pNext = p; else delete p; / 释放结点 *p p = succ; 此算法的时间复杂度为O (ListLength2(L)。假设已知链表中的数据元素为(5,2,5,3,3,4,2,5,7,5,4,3),则经算法2.21操作之后的链表表示的线性表是什么？ 是(7,4,3,2,5)。因为算法中的"插入"操作是将元素"倒序"插入新表中的，由于考虑集合中的元素没有次序关系，而"倒插"不需要加辅助指针变量。 试比较算法2.21和算法2.12，你将得出什么结论？ 你

29、一定发现这两个算法极为相似，因为它们处理的是例2-2提出的同一个问题。由此可见，顺序表和链表只是存储结构的不同，不影响问题求解的算法。 由于对原表中每个元素都需要在新的链表中进行查询，因此最坏情况下的时间复杂度仍为平方级的，和顺序表相同，正好说明这个时间复杂度是由算法决定的。从以上对链表的各种操作的讨论可知，链式存储结构的优势在于：(1) 能有效利用存储空间；因为它是动态存储分配的结构，不需要预先为线性表分配足够大的空间，而是向系统"随用随取"，并且在删除元素时可同时释放空间。(2) 用"指针"指示数据元素之间的后继关系，便于进行"插入&quo

30、t;、"删除"等操作；插入或删除时只需要修改指针，而不需要进行大量元素的移动。而其劣势则是不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的"表长"和数据元素在线性表中的"位序"，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。表长和位序是线性表中两个重要属性，在本节设置的单链表中表长是一个隐含值，必须从前到后遍历整个表才能得到。为了更突出链表的优势，需改进单链表结构的定义。除了保留指向头结点的指针外，还应增设"尾指针"和"表长"两个属性

31、，同时，我们从上面讨论的链表基本操作的实现算法中可以看出，在对链表进行操作时，经常需要一个指针在链表中巡游，由此可以设想，如果将这个在操作中进行巡游的"指针"以及它所指结点的数据元素在线性表中的"位序"纳入链表结构中，作为链表定义中的两个成员，必然会对链表的操作带来很多方便。如算法2.1和2.2中都需要进行"在最后一个结点之后插入元素"的操作。本来顺序表因插入元素要移动元素是个缺点，但当插入位置在表尾时不需要移动元素，所需时间是个常量，反过来，由于链表进行插入操作只需要修改指针本是个优点，然而为了查找插入位置却要遍历整个表，所需时间反而多。由此，在实际使用链表时需重新考虑链表结构的定义并重新设计操作界面。详细情况将留在2.5节进行讨论。2.3.4 循环链表循环链表(Circular Linked List)是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个自成循环的头结点表示。头指针指向表尾的好处是既能立即找到链表的尾结点，也容易找到链表中的第一个结点。循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点