课件第二章线性表

1、学习要点学习要点1. 了解线性表的逻辑结构特性是数据元素之间存在着线性关系，了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。示的线性表简称为链表。2. 熟练掌握这两类存储结构的描述方法以及线性表的基本操作在熟练掌握这两类存储结构的描述方法以及线性表的基本操作在这两种存储结构上的实现。这两种存储结构上的实现。3. 能够从时间和空间复杂度的角度综合比

2、较线性表两种存储结构能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。的不同特点及其适用场合。 线性表是一种最简单的线性结构。线性表是一种最简单的线性结构。什么是线性结构？简单地说，线性结构是一个数据什么是线性结构？简单地说，线性结构是一个数据元素的有序（次序）集合。它有四个基本特征：元素的有序（次序）集合。它有四个基本特征：1集合中必存在唯一的一个集合中必存在唯一的一个第一元素第一元素；2集合中必存在唯一的一个集合中必存在唯一的一个最后元素最后元素；3除最后元素之外，其它数据元素均有唯一的除最后元素之外，其它数据元素均有唯一的后继后继；4除第一元素之外，其它数据元

3、素均有唯一的除第一元素之外，其它数据元素均有唯一的前驱前驱。 2.1.1 线性表的定义线性表的定义 线性表线性表是由是由n（n0）个类型相同的数据元素组）个类型相同的数据元素组成的有限序列。通常表示成下列形式：成的有限序列。通常表示成下列形式： L=( a1, a2,.,ai-1,ai,ai+1,.,an) 其中：其中：L为线性表名称，习惯用大写书写；为线性表名称，习惯用大写书写； ai为组成该线性表的数据元素，习惯用小写书写；为组成该线性表的数据元素，习惯用小写书写； 线性表中数据元素的个数线性表中数据元素的个数n被称为被称为表长表长，当，当n=0时，时，线性表为空，又称为线性表为空，又称为

4、空表空表。称。称 i 为为ai在线性表中的在线性表中的位序位序。 举例举例 La=（34，89，765，12，90，-34，22） 数据元数据元素类型为素类型为int。 Ls=( Hello , World , China , Welcome ) 数据数据元素类型为元素类型为string。 Lb=(book1,book2,.,book100) 数据元素类型为下列数据元素类型为下列所示的结构类型：所示的结构类型： struct bookinfo int No; /图书编号图书编号 char *name; /图书名称图书名称 char *auther; /作者名称作者名称 .; 同一线性表中的元素

5、必定具有相同特性同一线性表中的元素必定具有相同特性不同的数据结构其操作集不同，但下列操不同的数据结构其操作集不同，但下列操作必不可缺：作必不可缺：1) 结构的生成；结构的生成；2) 结构的销毁；结构的销毁；3) 在结构中查找满足规定条件的数据在结构中查找满足规定条件的数据元素；元素；4) 在结构中插入新的数据元素；在结构中插入新的数据元素；5) 删除结构中已经存在的数据元素；删除结构中已经存在的数据元素；6) 遍历。遍历。若线性表中的数据元素相互之间可以比比较较，并且数据元素在表中依值非递减或依值非递减或非递增有序非递增有序排列，即 aiai-1 或 aiai-1(i = 2,3, n)，则称

6、该为有序表有序表(Ordered List)(Ordered List)。以有序表有序表表示集合，来解决有关集合运算方面的问题。 2.2.1 线性表的顺序存储结构线性表的顺序存储结构 线性表的线性表的顺序存储结构顺序存储结构(简称简称顺序表顺序表)是指用一组是指用一组地址连续地址连续的存储单元的存储单元依次存储依次存储线性表中的每个数据元线性表中的每个数据元素。即以素。即以“存储位置相邻存储位置相邻”表示表示“位序相继的两个数位序相继的两个数据元素之间的前驱和后继的关系据元素之间的前驱和后继的关系”，表中第一个元素，表中第一个元素的存储位置作为线性表的起始地址，称作线性表的的存储位置作为线性表

7、的起始地址，称作线性表的基基地址地址。如下图。如下图2-1所示：所示： 存储地址内存单元.da1d+La2d+2La3.d+(i-1)Lai.d+(n-1)Lan.图图2-1 线性表顺序存储结构示意图线性表顺序存储结构示意图 其中，其中，L为每个数据元素所占据的存储单元数目。为每个数据元素所占据的存储单元数目。 相邻两个数据元素的存储位置计算公式相邻两个数据元素的存储位置计算公式 LOC(ai+1)=LOC(ai)+L 线性表中任意一个数据元素的存储位置的计算公线性表中任意一个数据元素的存储位置的计算公式为：式为： LOC(ai)=LOC(a1)+(i-1)*L 顺序存储结构的特点顺序存储结构

8、的特点 （1）利用数据元素的存储位置表示线性表中相邻）利用数据元素的存储位置表示线性表中相邻数据元素之间的前后关系，即线性表的逻辑结构与存数据元素之间的前后关系，即线性表的逻辑结构与存储结构（物理结构）一致；储结构（物理结构）一致； （2）在访问线性表时，可以利用上述）在访问线性表时，可以利用上述给出的数学公式，快速地计算出任何一给出的数学公式，快速地计算出任何一个数据元素的存储地址。因此，我们可个数据元素的存储地址。因此，我们可以粗略地认为，访问每个数据元素所花以粗略地认为，访问每个数据元素所花费的时间相等。这种存取元素的方法被费的时间相等。这种存取元素的方法被称为称为随机存取法随机存取法，

9、使用这种存取方法的，使用这种存取方法的存储结构被称为存储结构被称为随机存储结构随机存储结构。 用用C语言描述的顺序表类型如下所示：语言描述的顺序表类型如下所示：#define MAXLISTSIZE 100 /预设的存储空间最大容量预设的存储空间最大容量 typedef struct ElemType *elem;/ 存储空间基址存储空间基址 int length; / 当前长度当前长度 int listsize;/ 允许的最大存储容量允许的最大存储容量(以以sizeof(ElemType)为单位为单位) SqList;/ 俗称俗称 顺序表顺序表 基本操作接口基本操作接口(函数声明函数声明)v

10、oid InitList ( SqList &L, int maxsize ); /构造一个构造一个最大存储容量为最大存储容量为 maxsize 的空的顺序表的空的顺序表 L。 void DestroyList ( SqList &L )/销毁顺序表销毁顺序表 L。bool ListEmpty ( SqList L )/若顺序表若顺序表 L 为空表，则返回为空表，则返回TRUE，否则返回，否则返回 FALSE。int ListLength ( SqList L )/返回顺序表返回顺序表 L 中元素个数。中元素个数。 int PriorElem ( SqList L, ElemT

11、ype cur_e ) /若若 cur_e 是顺序表是顺序表 L 的元素，则返回其前驱的位序的元素，则返回其前驱的位序(设第一个元设第一个元素的前驱的位序为素的前驱的位序为0)，否则返回，否则返回 -1。 int NextElem ( SqList L, ElemType cur_e )/若若 cur_e 是顺序表是顺序表 L 的元素，则返回其后继的位的元素，则返回其后继的位序序(设最后一个元素的后继的位序为设最后一个元素的后继的位序为L的表长的表长+1)，否则，否则返回返回 -1。bool GetElem ( SqList L, int pos, ElemType &e )/若若1p

12、osLengthList(L)，则用，则用 e 带回顺序表带回顺序表 L 中第中第 pos 个元素的值且返回函数值为个元素的值且返回函数值为TRUE，否则返，否则返回函数值为回函数值为FALSE。 int LocateElem ( SqList L, ElemType e, bool (*compare)(ElemType, ElemType ) ) /返回顺序表返回顺序表L中第中第1个与个与 e 满足关系满足关系 compare( ) 的数据元素的位序。的数据元素的位序。/若这样的元素不存在，则返回值为若这样的元素不存在，则返回值为0。compare( )为数据元素的判定函数。为数据元素的判

13、定函数。void ListTraverse ( SqList L, void (*visit)(ElemType )/依次对顺序表依次对顺序表 L 的每个元素调用函数的每个元素调用函数 visit( )。/一旦一旦 visit( ) 失败，则操作失败。失败，则操作失败。void ClearList( SqList &L )/将顺序表将顺序表 L 重置为空表。重置为空表。 bool PutElem ( SqList L, int pos, ElemType &e )/若若1posLengthList(L)，则对顺序表，则对顺序表 L 中第中第 pos 个元素个元素/赋值同赋值同

14、e 的值且返回函数值为的值且返回函数值为 TRUE，否则返回，否则返回函数值为函数值为 FALSE。 bool ListInsert ( SqList &L, int pos, ElemType e )/若存储空间未满且若存储空间未满且1posLengthList(L)+1，则，则在顺序表在顺序表 L 的的/第第 pos 个元素个元素之前之前插入新的元素插入新的元素 e，L的长度增的长度增1，且返回函数值为且返回函数值为TRUE，/否则不改变顺序表且返回函数值为否则不改变顺序表且返回函数值为 FALSE。 bool ListDelete ( SqList &L, int pos

15、, ElemType &e)/若若1posLengthList(L)，则删除顺序表，则删除顺序表 L 的第的第 pos 个元素个元素 e，/L的长度增的长度增1，且返回函数值为，且返回函数值为TRUE，否则不改，否则不改变顺序表且返回函数值为变顺序表且返回函数值为FALSE。 2.2.2 顺序表中基本操作的实现顺序表中基本操作的实现 从顺序表的存储结构定义容易看出，由于顺序表从顺序表的存储结构定义容易看出，由于顺序表的的“长度长度”是个是个“显值显值”，且由于第，且由于第i个元素恰好存储个元素恰好存储在数组的第在数组的第 i 个分量个分量(数组下标为数组下标为 i-1)中，因此其中，因

16、此其“求求长长”、“判空判空”以及以及“存取第存取第 i 个数据元素个数据元素”等操作等操作都很容易实现。下面重点讨论顺序表类型定义中五个都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。操作的实现。 一、初始化操作一、初始化操作二、元素定位操作二、元素定位操作三、插入元素操作三、插入元素操作四、删除元素操作四、删除元素操作五、销毁结构操作五、销毁结构操作一、初始化操作一、初始化操作 对顺序表而言，对顺序表而言，“初始化初始化”的实的实质是为它分配一个质是为它分配一个“足够应用足够应用”的元的元素存储空间，由用户根据它对线性表素存储空间，由用户根据它对线性表的使用要求定义一个最大存储容

17、量的使用要求定义一个最大存储容量 maxsize，并约定当用户没有提出特殊，并约定当用户没有提出特殊需求需求(maxsize=0) 时，按予设的最大存时，按予设的最大存储量储量 MAXLISTSIZE 进行分配。进行分配。 一、初始化操作一、初始化操作 void InitList(SqList &L, int maxsize) / 构造一个空的线性表构造一个空的线性表 Lif ( maxsize = 0 ) maxsize = MAXLISTSIZE; L.elem = new ElemTypemaxsize; if (!L.elem) exit(1); / 存储分配失败存储分配失败L

18、.length = 0;/ 顺序表的初始长度为顺序表的初始长度为0L.listsize = maxsize;/ 该顺序表可以存储元素该顺序表可以存储元素的最大容量的最大容量 / InitList 此算法的时间复杂度为此算法的时间复杂度为O (1)。 二、元素定位操作二、元素定位操作 在顺序表中在顺序表中“查询查询”是否存在一是否存在一个和给定值满足判定条件的元素的最个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每简单的办法是，依次取出结构中的每个元素和给定值进行比较。个元素和给定值进行比较。 二、元素定位操作二、元素定位操作 int LocateElem(SqList L, E

19、lemType e,bool (*compare)(ElemType, ElemType)/ 在顺序表在顺序表L中查找第中查找第1个值与个值与 e 满足判定条件满足判定条件compare( )的的元素，若找到，则返回其在元素，若找到，则返回其在 L 中的位序，否则返回中的位序，否则返回0。i = 1;/ i 的初值为第的初值为第1元素的位序元素的位序p = L.elem; / p 的初值为第的初值为第1元素的存储位置元素的存储位置while (i = L.length & !(*compare)(*p+,e)+i; / 依次进行判定依次进行判定if (i = L.length) ret

20、urn i; / 找到满足判定条件的数据元素为找到满足判定条件的数据元素为第第 i 个元素个元素else return 0; / 该线性表中不存在满足判定的数据元素该线性表中不存在满足判定的数据元素 / LocateElem 此算法的时间复杂度为：此算法的时间复杂度为：O ( ListLength(L) 演示三、插入元素操作三、插入元素操作 首先分析，首先分析，“插入元素插入元素”使线性表的逻辑结构发使线性表的逻辑结构发生什么变化？生什么变化？假设在线性表的第假设在线性表的第i个元素之前插入一个元素个元素之前插入一个元素e，使得线性表使得线性表( a1, , ai-1 , ai , , an

21、) 改变为改变为 ( a1, , ai-1 , e, ai , , an )即：即：(1) 改变了表中元素之间的关系，使改变了表中元素之间的关系，使 改改变为变为和和 (2) 表长增表长增1由于顺序表是以由于顺序表是以存储位置相邻存储位置相邻 表示表示元素之间元素之间的前驱和后继关系的前驱和后继关系，则，则必须必须移动元素移动元素来体现来体现元素元素之间发生的变化之间发生的变化。三、插入元素操作三、插入元素操作 bool ListInsert(SqList &L, int pos, ElemType e)/ 若存储空间不满且若存储空间不满且1posListlength(L)+1，则在顺

22、序表，则在顺序表 L 的的 第第 pos 个元素个元素之前之前插入新的元素插入新的元素 e 且返回且返回TRUE，否则返，否则返回回FALSEif (pos L.length+1) return FALSE ; / 插入位置插入位置不合法不合法if (L.length = L.listsize) return FALSE;/ 当前存储空间已当前存储空间已满，无法插入满，无法插入for (j=L.length-1; j=pos-1; -j)L.elemj+1 = L.elemj; / 插入位置及之后的元素右移插入位置及之后的元素右移L.elempos-1 = e; / 插入插入 e+L.leng

23、th; / 表长增表长增1return TRUE; / ListInsert 此算法的时间复杂度为：此算法的时间复杂度为：O (ListLength(L)演示四、删除元素操作四、删除元素操作 假设删除线性表中第假设删除线性表中第i个元素个元素，对，对顺序表而言，需要改变从第顺序表而言，需要改变从第 i+1 个元个元素起到第素起到第 n 个元素的存储位置，即进个元素的存储位置，即进行行从第从第 i+1 到第到第 n 个元素往前移动一个元素往前移动一个位置个位置。 四、删除元素操作四、删除元素操作 bool ListDelete(SqList &L, int pos, ElemType &

24、amp;e)/ 若若1posListlength(L)，则以，则以 e 带回从顺序表带回从顺序表 L 中删除中删除的的 第第 pos 个元素且返回个元素且返回 TRUE，否则返回，否则返回 FALSEif (pos L.length) return FALSE ; / 删除位置不删除位置不合法合法for (j = pos; jL.length; +j) L.elemj-1 = L.elemj; / 被删除元素之后的元素左被删除元素之后的元素左移移 -L.length; / 表长减表长减1return TRUE; / ListDelete 此算法的时间复杂度为：此算法的时间复杂度为：O (Lis

25、tLength(L)演示五、销毁结构操作五、销毁结构操作void DestroyList( SqList &L )/ 释放顺序表释放顺序表 L 所占存储空间所占存储空间delete L.elem;L.listsize = 0;L.length = 0; / DestroyList_Sq 此算法的时间复杂度为：此算法的时间复杂度为：O (1)插入和删除操作的性能分析插入和删除操作的性能分析 在顺序表中任何一个合法位置上进在顺序表中任何一个合法位置上进行行一次一次插入或删除操作时，需要移动插入或删除操作时，需要移动的元素个数的平均值是多少？的元素个数的平均值是多少？ 插入算法的分析插入算法

26、的分析 假设线性表中含有假设线性表中含有n个数据元素，在进行插入操作个数据元素，在进行插入操作时，若假定在时，若假定在n+1个位置上插入元素的可能性均等，则个位置上插入元素的可能性均等，则平均移动元素的个数为：平均移动元素的个数为：1n1iis2n1)i(n1n1E 删除算法的分析删除算法的分析 在进行删除操作时，若假定删除每个元素的可能在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：性均等，则平均移动元素的个数为： n1idl21ni)(nn1E 分析结论分析结论 在顺序存储表示的线性表中插入或在顺序存储表示的线性表中插入或删除一个数据元素，平均约需移动表中删除一个

27、数据元素，平均约需移动表中一半元素。这个数目在线性表的长度较一半元素。这个数目在线性表的长度较大时是很可观的。这个大时是很可观的。这个缺陷缺陷完全是由于完全是由于顺序存储要求线性表的元素依次紧挨存顺序存储要求线性表的元素依次紧挨存放造成的。因此，这种顺序存储表示仅放造成的。因此，这种顺序存储表示仅适用于适用于不常进行插入和删除操作、表中不常进行插入和删除操作、表中元素相对稳定的线性表。元素相对稳定的线性表。例例1 试编写算法试编写算法“比较比较”两个顺序表的大小。两个顺序表的大小。算法的基本思想为：若算法的基本思想为：若 aj = bj，则，则 j 增增 1，之，之后继续比较后继元素；否则即可

28、得出比较结后继续比较后继元素；否则即可得出比较结果。显然，果。显然，j 的初值应为的初值应为 0，循环的条件是，循环的条件是 j 不超出其中任何一个表的范围不超出其中任何一个表的范围。若在循环内。若在循环内不能得出比较结果，则循环结束时有三种可不能得出比较结果，则循环结束时有三种可能出现的情况需要区分。能出现的情况需要区分。int compare( SqList A, SqList B )/ 若若 AB，则返回，则返回 1j=0;while ( jA.length & jB.length )if ( A.elemj B.elemj ) return(1);else j+;if ( A.

29、length = B.length ) return (0);else if ( A.length B.length ) return(-1);else return(1); / compare上述算法中只有一个上述算法中只有一个 while 循环，它的执行次数依赖于待比较的顺序循环，它的执行次数依赖于待比较的顺序表的表长，因此，算法表的表长，因此，算法2.9 的时间复杂度为的时间复杂度为 O (Min(A.length, B.length)例例2试设计一个算法，用尽可能少的辅助空间将顺序表中前试设计一个算法，用尽可能少的辅助空间将顺序表中前 m 个元素和后个元素和后 n 个元素进行互换，即将

30、线性表个元素进行互换，即将线性表( a1,a2 ,am ,b1 ,b2 ,bn ) 改变成改变成( b1, b2, bn, a1 , a2, am )。此题的一种比较简单的算法是，从表中第此题的一种比较简单的算法是，从表中第 m+1 个元素起依次个元素起依次插入到元素插入到元素 a1之前。则首先需将该元素之前。则首先需将该元素 bk(k=1，2，n)暂存在一个辅助变量中，然后将它之前的暂存在一个辅助变量中，然后将它之前的 m 个元素个元素( a1 , a2, am )依次后移一个位置。显然，由于对每一个依次后移一个位置。显然，由于对每一个 bk都都需要移动需要移动 m 个元素，因此算法的时间复

31、杂度为个元素，因此算法的时间复杂度为 O (mn)。 演示演示也可采用另一种算法为，对顺序表进行三次也可采用另一种算法为，对顺序表进行三次逆置逆置，第一次，第一次是对整个顺序表进行逆置，之后分别对前是对整个顺序表进行逆置，之后分别对前 n 个和后个和后 m 个元个元素进行逆置。素进行逆置。 演示演示void invert( ElemType &R , int s, int t )/ 本算法将数组本算法将数组 R 中下标自中下标自 s 到到 t 的元素逆置，即将的元素逆置，即将/ （Rs,Rs+1,Rt-1,Rt）改变为（）改变为（Rt,Rt-1,Rs+1,Rs）for ( k=s; k

32、 0 & m A.length )n = A.length - m;invert( A.elem, 0, m+n-1 );invert( A.elem, 0, n-1 );invert( A.elem, n, m+n-1 ); / exchange由于逆置顺序表可以利由于逆置顺序表可以利交换交换相应元素进行，其时间复杂度相应元素进行，其时间复杂度为线性级别，则三次调用逆置算法完成的操作的时间复杂为线性级别，则三次调用逆置算法完成的操作的时间复杂度仍然是线性级别的，即为度仍然是线性级别的，即为O (m+n)。 例例3编写算法删除顺序表中编写算法删除顺序表中“多余多余”的数据元素，即使操作

33、的数据元素，即使操作之后的顺序表之后的顺序表中所有元素的值都不相同。中所有元素的值都不相同。容易想到此题的一个简单算法是：容易想到此题的一个简单算法是：对表中任一个元素对表中任一个元素 ai，令，令 j 从从 i+1 到到 n，将，将aj 和和 ai 进行进行比较，若相等，则从顺序表中删除该元素比较，若相等，则从顺序表中删除该元素 ，即令从，即令从 j+1 到到 n 的元素均向前移动一个位置。的元素均向前移动一个位置。演示演示 由于顺序存储结构的特点，在删除元素时必然会引起一由于顺序存储结构的特点，在删除元素时必然会引起一连串的元素向前移动，但在上述算法中连串的元素向前移动，但在上述算法中“每

34、发现一个和每发现一个和 相相同的元素，立即将在它之后的元素向前移动一个位置同的元素，立即将在它之后的元素向前移动一个位置”的的做法，将会使那些值和做法，将会使那些值和 不同的元素重复多次移动操作，而不同的元素重复多次移动操作，而每次都只移动一个位置（试设想在此元素之后还有很多和每次都只移动一个位置（试设想在此元素之后还有很多和 值相同的元素）。算法的时间复杂度将是值相同的元素）。算法的时间复杂度将是O (n2)（n为表为表长）。长）。但如果不是从但如果不是从“删除删除”而是从而是从“插入插入”来考虑问题，这个题的来考虑问题，这个题的解法就会有不同的结果。解法就会有不同的结果。设想另建立一个顺序

35、表，表中只包含原表中所有值不设想另建立一个顺序表，表中只包含原表中所有值不同的元素，对原顺序表中每一个当前考察的数据元素，在同的元素，对原顺序表中每一个当前考察的数据元素，在“新表新表”中进行查找，如果有相同的则舍弃之，否则就插中进行查找，如果有相同的则舍弃之，否则就插入到入到“新表新表”中。由于问题的实质是中。由于问题的实质是“删除删除”，因此所谓，因此所谓“新表新表”，在存储结构上并非是新建的表，它和原表可以，在存储结构上并非是新建的表，它和原表可以共享存储空间，只须新建一个指针来指示其表尾的当前位共享存储空间，只须新建一个指针来指示其表尾的当前位置即可。置即可。 演示演示void pur

36、ge_Sq( SqList &L )/ 删除顺序表删除顺序表L中的冗余元素，即使操作之后的顺序表中的冗余元素，即使操作之后的顺序表中只保留中只保留/ 操作之前表中所有值都不相同的元素操作之前表中所有值都不相同的元素 k = -1; / k 指示新表的表尾指示新表的表尾for (i=0; iL.length; +i) / 顺序考察表中每个元素顺序考察表中每个元素j=0;while(jk )/ k=-1 表明当前考察的是第一个表明当前考察的是第一个元素元素L.elem+k = L.elemi; / forL.length = k+1;/ 修改表长修改表长 / purge_Sq此算法的此算法

37、的时间复杂度时间复杂度为为O (ListLength2(L) 分析：分析：算法中的基本操作为算法中的基本操作为比较比较，控制结构为两重循环，控制结构为两重循环，外循环的执行次数和顺序表的表长相同，内循环的执行次外循环的执行次数和顺序表的表长相同，内循环的执行次数则不超过表长。此外，数则不超过表长。此外，比较比较操作相对于操作相对于移动移动操作所操作所需的时间也少。需的时间也少。从这个题的算法可以得到一些有益的启示，某种情况从这个题的算法可以得到一些有益的启示，某种情况下，下，删除删除操作也可利用操作也可利用插入插入来实现。来实现。 例例4 教材教材P26 算法算法2.7 顺序表的合并顺序表的合

38、并 线性表顺序存储结构的特点线性表顺序存储结构的特点 它是一种简单、方便的存储方式。它要求线性表它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。方式属于静态存储形式。 暴露的问题暴露的问题 l l在做插入或删除元素的操作时，会产生大在做插入或删除元素的操作时，会产生大量的数据元素移动；量的数据元素移动； l l对于长度变化较大的线性表，要一次性地对于长度变化较大的线性表，要一次性地分配足够的存储空

39、间，但这些空间常常又得不到充分分配足够的存储空间，但这些空间常常又得不到充分的利用；的利用； l l线性表的容量难以扩充。线性表的容量难以扩充。 线性表的链式存储结构线性表的链式存储结构 线性表的线性表的链式存储结构链式存储结构是指用一组任意的存储单是指用一组任意的存储单元（可以连续，也可以不连续）存储线性表中的数据元（可以连续，也可以不连续）存储线性表中的数据元素。为了反映数据元素之间的逻辑关系，对于每个元素。为了反映数据元素之间的逻辑关系，对于每个数据元素不仅要表示它的具体内容，还要附加一个表数据元素不仅要表示它的具体内容，还要附加一个表示它的直接后继元素存储位置的信息。假设有一个线示它的

40、直接后继元素存储位置的信息。假设有一个线性表（性表（a,b,c,d），可用下图），可用下图2-2所示的形式存储：所示的形式存储：存储地址内容直接后继存储地址100b120.120c160.144a100.160dNULL.首元素位置图图2-2 线性表链式存储结构示意图线性表链式存储结构示意图 术语术语 表示每个数据元素的两部分信息组合在一起被称表示每个数据元素的两部分信息组合在一起被称为为结点结点； 其中表示数据元素内容的部分被称为其中表示数据元素内容的部分被称为数据域数据域（data）；）； 表示直接后继元素存储地址的部分被称为表示直接后继元素存储地址的部分被称为指针指针或或指针域指针域（n

41、ext）。）。 单链表简化的图单链表简化的图2-3描述形式描述形式headd cba图图 2-3 单链表结构示意图单链表结构示意图 其中，其中，head是是头指针头指针，它指向单链表中的第一个，它指向单链表中的第一个结点，这是单链表操作的入口点。由于最后一个结点结点，这是单链表操作的入口点。由于最后一个结点没有直接后继结点，所以，它的指针域放入一个特殊没有直接后继结点，所以，它的指针域放入一个特殊的值的值NULL。NULL值在图示中常用（值在图示中常用（）符号表示。）符号表示。 带头结点的单链表带头结点的单链表 为了简化对链表的操作，人们经常在链表的第一为了简化对链表的操作，人们经常在链表的第

42、一个结点（个结点（首元结点首元结点）之前附加一个结点，并称为）之前附加一个结点，并称为头结头结点点。这样可以免去对链表第一个结点的特殊处理。如。这样可以免去对链表第一个结点的特殊处理。如下图下图2-4所示：所示：headd cba图图 2-4 带头结点的单链表结构示意图带头结点的单链表结构示意图 链式存储结构的特点链式存储结构的特点 （1）线性表中的数据元素在存储单元中的存放顺）线性表中的数据元素在存储单元中的存放顺序与逻辑顺序不一定一致；序与逻辑顺序不一定一致； （2）在对线性表操作时，只能通过头指针进入链）在对线性表操作时，只能通过头指针进入链表，并通过每个结点的指针域向后扫描其余结点，这

43、表，并通过每个结点的指针域向后扫描其余结点，这样就会造成寻找第一个结点和寻找最后一个结点所花样就会造成寻找第一个结点和寻找最后一个结点所花费的时间不等，具有这种特点的存取方式被称为费的时间不等，具有这种特点的存取方式被称为顺序顺序存取方式。存取方式。用用 C 语言中的语言中的“结构指针结构指针”来描述链表结来描述链表结构。构。 typedef struct LNode ElemType data;struct LNode *next; LNode, *SLink;若设若设 LNode *p,*q;SLink H; 则则 p，q 和和 H 均为以上定义的指针型变量。若均为以上定义的指针型变量。若

44、 p 的值非空，则表明的值非空，则表明 p 指向某个结点，指向某个结点，p-data 表示表示 p 所指结点中的数据域，所指结点中的数据域，p-next 表示表示 p 所指结点中的指所指结点中的指针域，若非空，则指向其针域，若非空，则指向其“后继后继”结点。结点。 指针型变量只能作同类型的指针赋值与比较操作。指针型变量只能作同类型的指针赋值与比较操作。并且，指针型变量的并且，指针型变量的值值除了由同类型的指针变量赋除了由同类型的指针变量赋值得到外，都必须用值得到外，都必须用 C 语言中的动态分配函数得到。语言中的动态分配函数得到。例如，例如，p = new LNode; 表示在运行时刻系统动态

45、生成表示在运行时刻系统动态生成了一个了一个 LNode 类型的结点，并令指针类型的结点，并令指针 p 指向指向该结点。该结点。反之，当指针反之，当指针 p 所指结点不再使用，可用所指结点不再使用，可用 delete p; 释释放此结点空间。放此结点空间。2.3.2 单链表中基本操作的实现单链表中基本操作的实现1. 初始化操作初始化操作 初始化建一个空的链表即为建立一个只有头结点的链表初始化建一个空的链表即为建立一个只有头结点的链表void InitList( SLink &L ) / 创建一个带头结点的空链表创建一个带头结点的空链表,L 为指向头为指向头结点的指针结点的指针(头指针头指

46、针)L = new LNode;if (!L) exit(1); / 存储空间分配失败存储空间分配失败L-next = NULL; / InitList 算法的时间复杂度为算法的时间复杂度为O (1)。2. 销毁链表销毁链表void DestroyList( SLink &L)/ 销毁以销毁以L为头指针的单链表，释放链表中所有结点空间为头指针的单链表，释放链表中所有结点空间while (L)p = L;L = L-next;delete p; / whileL = NULL; /虽然头结点占有的空间已经释放，但指针变虽然头结点占有的空间已经释放，但指针变量量L中的值没有改变，为安全起见

47、，置中的值没有改变，为安全起见，置L为为 空空，以防止对，以防止对系统空间的访问。系统空间的访问。 / DestroyList 算法的时间复杂度为算法的时间复杂度为O (Listlength(L)。3. 存取元素操作存取元素操作 单链表是一种单链表是一种“顺序存取顺序存取”的结构，的结构，即：为取第即：为取第 i 元素，首先必须先找到第元素，首先必须先找到第 i-1 个元素。因此不论个元素。因此不论 i 值为多少，都必须值为多少，都必须从头结点开始起从头结点开始起“点数点数”，直数到第，直数到第 i 个为止。头结点可看成是第个为止。头结点可看成是第0个结点。个结点。3. 存取元素操作存取元素操

48、作 bool GetElem ( SLink L, int pos, ElemType &e )/ 若若1posLengthList(L)，则用，则用 e 带回指针带回指针L指向头结点的单链指向头结点的单链表中第表中第 pos 个元素的值且返回函数值为个元素的值且返回函数值为TRUE,否则返回函数值为否则返回函数值为FALSEp = L-next; j =1; / 变量初始化，变量初始化，p 指向第一个结点指向第一个结点while ( p & jnext; +j; / whileif ( !p | jpos ) return FALSE; / 链表中不存在第链表中不存在第 po

49、s 个结点个结点e = p-data; / 取到第取到第 pos 个元素个元素return TRUE; / GetElem 算法的时间复杂度为算法的时间复杂度为O (ListLength(L)。演示4. 插入元素操作插入元素操作 算法的基本思想就是，首先找到第算法的基本思想就是，首先找到第i-1个结点，个结点，然后修改相应指针。然后修改相应指针。 4. 插入元素操作插入元素操作 bool ListInsert ( SLink &L, int pos, ElemType e )/ 若若1posLengthList(L)+1，则在指针，则在指针L指向头结点的单链表的第指向头结点的单链表的第

50、 pos 个元素个元素之前之前插入新的元素插入新的元素 e，且返回函数值为，且返回函数值为 TRUE, 否则不进行插入且否则不进行插入且返回函数值为返回函数值为 FALSEp=L; j=0;while(p & jnext; +j; / whileif(!p|jpos-1)return FALSE; / 参数不合法，参数不合法，pos 小于小于1或者大于表长或者大于表长+1s=new LNode;if (!s) exit(1); / 存储空间分配失败存储空间分配失败s-data=e; / 创建新元素的结点创建新元素的结点s-next=p- next; p-next=s; / 修改指针修改

51、指针return TRUE; / ListInsert 算法时间复杂度为算法时间复杂度为O (ListLength(L)。演示5. 删除元素操作删除元素操作bool ListDelete ( SLink &L, int pos, ElemType &e)/ 若若1posLengthList(L)，则删除指针，则删除指针L指向头结点的单链表指向头结点的单链表 中第中第 pos 个元素个元素并以并以 e 带回其值，返回函数值为带回其值，返回函数值为 TRUE，否则不进行删除操作且返回函数值为，否则不进行删除操作且返回函数值为 FALSEp = L; j = 0;while (p-n

52、ext & j next; +j;if (!(p-next) | j pos-1)return FALSE; / 删除位置不合理删除位置不合理q = p-next; p-next = q-next;/ 修改指针修改指针e = q-data; delete(q);/ 释放结点空间释放结点空间 return TRUE; / ListDelete 算法时间复杂度为算法时间复杂度为O (ListLength(L)。演示例例1. 逆序创建链表逆序创建链表（头插法建立单链表）（头插法建立单链表） 假设线性表假设线性表( a1，a2 ，an )的数据元素存储在一的数据元素存储在一维数组维数组 An中

53、，则中，则从数组的最后一个分量起，依次生从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为成结点，并逐个插入到一个初始为“空空”的链表中。的链表中。算法思想：算法思想： 所谓所谓“逆序逆序”创建链表指的是，依和线性表的逻创建链表指的是，依和线性表的逻辑顺序相辑顺序相“逆逆”的次序输入元素。的次序输入元素。 由于链表的生成是从最后一个结点起逐个插入，由于链表的生成是从最后一个结点起逐个插入，因此每个新生成的结点都是插入在链表的因此每个新生成的结点都是插入在链表的“第一个第一个”结点之前，即头结点之后，使新插入的结点成为插入结点之前，即头结点之后，使新插入的结点成为插入之后的链表中的第一

54、个结点。之后的链表中的第一个结点。例如动画演示了线性表例如动画演示了线性表 (a,b,c,d,e) 的逆序创建的过程。的逆序创建的过程。演示具体算法：具体算法：void CreateList_L(SLink &L, int n, ElemType A ) / 已知数组已知数组 A 中存有线性表的中存有线性表的 n 个数据元素，个数据元素，/ 逆序建立带头结点的单链表。逆序建立带头结点的单链表。L = new LNode;if (!L) exit(1); / 存储空间分配失败存储空间分配失败L-next = NULL; / 先建立一个带头结点的空的先建立一个带头结点的空的单链表单链表fo

55、r (i = n; i 0; -i) p = new LNode;if (!p) exit(1); / 存储空间分配失败存储空间分配失败 p-data = Ai-1; / 赋元素值赋元素值 p-next = L-next; L-next = p; / 插入在头插入在头结点之后结点之后 / for / CreateList_L 容易看出，算法的容易看出，算法的时间复杂度时间复杂度为为O (ListLength(L)。思考：如何用尾插法创建链表？例例2. 以链表作存储结构以链表作存储结构将线性表中前将线性表中前 m 个元素和后个元素和后 n 个个元素进行互换，即将线性表元素进行互换，即将线性表(

56、a1,a2 ,am ,b1 ,b2 ,bn ) 改变成改变成( b1, b2, bn, a1 , a2, am )。因为对链表来说，因为对链表来说，插入插入和和删除删除仅需修改指针即可完仅需修改指针即可完成，并且由于前成，并且由于前 m 个元素之间和后个元素之间和后 n 个元素之间的链个元素之间的链接关系分别都不需要改变，则算法的实际操作为：接关系分别都不需要改变，则算法的实际操作为： (1) 从链表中删除从链表中删除(a1,a2 ,am )；(2) 将将(b1 ,b2 ,bn )链接到头结点之后；链接到头结点之后；(3) 将将(a1,a2 ,am )链接到链接到 bn 之后。之后。演示voi

57、d exchange_L( SLink &L，int m )/ 本算法实现单链表中前本算法实现单链表中前 m 个结点和后个结点和后 n 个结点的互换个结点的互换if ( m & L-next ) / 链表不空且链表不空且 m!=0 p = L-next; k = 1;while( knext; +k; / while if (p & p-next) / n!=0 时才需要修改指针时才需要修改指针ha = L-next; / 以指针以指针 ha 记记 a1结点的位置结点的位置L-next = p-next; / 将将 b1 结点链接在头结点之后结点链接在头结点之后p-ne

58、xt = NULL;/ 设设 am的后继为空的后继为空q = L-next; / 令令q 指向指向 b1 结点结点while (q-next) q = q-next; / 查找查找 bn 结点结点q-next = ha; / 将将 a1 结点链接到结点链接到 bn 结点之后结点之后 / if(p) / if(m) / exchange_L 算法的时间复杂度为算法的时间复杂度为O (ListLength(L)。例例3. 编写算法删除单链表中编写算法删除单链表中“多余多余”的数据元素，即使的数据元素，即使操作之后的单链表中所有元素的值都不相同。操作之后的单链表中所有元素的值都不相同。void pu

59、rge_L(SLink &L )/ 删除单链表删除单链表L中的冗余元素，即使操作之后的单链表中只保留中的冗余元素，即使操作之后的单链表中只保留/ 操作之前表中所有值都不相同的元素操作之前表中所有值都不相同的元素 p = L-next;L-next = NULL;/ 设新表为空表设新表为空表while ( p ) / 顺序考察原表中每个元素顺序考察原表中每个元素succ = p-next;/ 记下结点记下结点 *p 的后继的后继q = L-next; / q 指向新表的第一个结点指向新表的第一个结点while( q & p-data!=q-data ) q = q-next; /

60、 在新表中查询是否存在和在新表中查询是否存在和p-data相同的元素相同的元素if ( !q ) / 将结点将结点 *p 插入到新的表中插入到新的表中p-next = L-next;L-next = p;else delete p;/ 释放结点释放结点 *pp = succ; / for / purge_L此算法的时间复杂度为此算法的时间复杂度为O (ListLength2(L)。 例例4.4.两个链表的归并两个链表的归并算法要求：算法要求：已知：线性表已知：线性表 A、B，分别由单链表，分别由单链表 LA , LB 存储，存储，其中数据元素按值非递减有序排列，其中数据元素按值非递减有序排列，要求：将要求：将 A ，B 归并为一个新的线性表归并为一个新的线性表C , C 的数据的数据元素仍按值非递减排列元素仍按值非递减排列 。设线性表。设线性表 C 由单链表由单链表 LC 存储。存储。假设：假设：A=（3，5，8，11），），B=（2，6，8，9，11）预