山大《数据结构》讲义02线性表

1、第二章 线性表内容概述线性结构是每一个有意义的程序基本都使用的一种数据结构，也是最简单的数据结构。那么，线性结构如何表示与实现？本章从线性表的抽象数据类型定义、线性表的顺序存储及实现算法、线性表的链式存储及算法实现等三个方面阐述该问题。重点与难点重点为顺序表和单链表的描述和插入、删除运算以及算法的效率分析。难点为单链表的插入、删除运算和链表的应用。思考1线性结构与非线性结构的根本区别是什么？2线性表有哪两种存储结构，各有哪些优缺点？3在单链表和双向链表中，能否从当前结点出发访问任一结点？4当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用何种存储结构为宜？当经常进行的是插入

2、和删除操作时，则应采用存储结构为宜？5在单链表中设置头结点有何作用？6有一个单链表L（至少有1个结点），编写一个算法将L逆置，即最后一个结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。7有一个单链表，其结点的元素值以非递减有序排列，其结点的元素值有可能相同，编写一个算法删除单链表中多余的元素值相同的结点。第一节线性表的类型定义线性表示最常用且最简单的一种数据结构。了解线性表的结构特点、掌握线性表抽象类型定义是运用线性结构解决具体应用问题的基础。1.线性表定义、线性表的结构特点所谓线性表（Linear_List），就是n（n0）个数据元素的集合a1,a2,an，这些数据元素之间有

3、逻辑上的线性关系。线性表结构的特点是：当数据元素集合为非空时（即n0），则（1）有且仅有一个元素作为该结构的第一个元素，即a1；（2）有且仅有一个元素作为该结构的最后一个元素，即an；（3）当1KN时，第k个元素ak有且仅有一个直接前驱，即ak-1，有且仅有一个直接后继，即ak+1；另外，a1的后继为a2，a1无前驱，an的前驱为an-1，an无后继。具有n个元素的线性表，n称为线性表的长度。当长度n为0时，线性表称为空表。当n0时，线性表中每个数据元素ai的位置称为ai在线性表中的位序。线性表中每个数据元素在不同的情况下，可以是一个数或一个符号，也可以是一篇文章，甚至是图片等其他更复杂的信息

4、。例如，2到20的所有质数：（2，3，5，7，11，13，17，19）是一个线性表，表中的数据元素是单个的整数。又如，一个班级的学生姓名集合：（李帅，张伟，王明）表中的数据元素是字符串。在第一章所举的例子中，航班信息表为稍复杂的线性表，一个数据元素可以由若干个数据项（Item）组成。该线性表中的元素，常称为数据记录（DataRecord），简称记录，它是数据处理领域组织数据的基本单位。在日常生活中，学生学籍表、职工档案表、图书馆书目表、医院病历表、库存账目表等都可称为线性表。对于线性表，我们可以按照需求来增加或缩减它的长度，即进行插入或删除操作，也可以对表中的元素进行查找或访问等操作。2.线性

5、表抽象类型定义线性表的抽象数据类型定义如下：ADTList数据对象：D=ai|aiElemSet,i=1,2,n,n0数据关系：R1=|ai-1,aiD,i=2,n基本操作：CreatList(&L)操作结果：生成一个空的线性表L。ListLength(L)初始条件：线性表L已存在。操作结果：返回L中数据元素个数。ListInsert(&L,i,e)初始条件：线性表L已存在，1iListLength(L)+1。操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1iListLength(L)。操作结果：删除L的第

6、i个数据元素，并用e返回其值，L的长度减1。GetElem(L,i,&e)初始条件：线性表L已存在，1iListLength(L)。操作结果：用e返回L中第i个数据元素的值。LocateElem(L,e,compare()初始条件：线性表L已存在，compare()是数据元素判定函数。操作结果：返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在，则返回值为0。ListEmpty(L)初始条件：线性表L已存在。操作结果：若L为空表，则返回TRUE，否则返回FALSE。ClearList(&L)初始条件：线性表L已存在。操作结果：将L重置为空表。DestroyLi

7、st(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ADTList对于以上定义的抽象数据类型线性表，除了对其进行的基本操作外，还可进行一些更复杂的操作。如：对线性表进行排序；在一个有序的线性表中插入元素；将两个或两个以上有序的线性表归并成为一个有序的线性表等。这些复杂的操作可建立在基本操作的基础上完成，即它们可通过调用基本操作来实现。若操作环境或操作要求发生变化（例如，存储结构的变化），只需要修改基本操作的实现算法，而通过调用基本操作实现的其它算法则不必修改或只做很少的修改，这在一定程度上可以达到软件模块复用的目的。第二节线性表的顺序表示和实现顺序存储结构是线性表存储结构的选择之一。

8、当线性表很少涉及插入和删除操作时，优先选择顺序结构表示线性表。1、顺序表数据类型定义顺序表数据类型定义线性表的顺序表示是利用一组地址连续的内存空间依次存储线性表的各个数据元素，即以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。因为顺序存储结构是一种随机存取的存储结构，所以通常利用C语言中动态分配的一组连续的存储单元作为顺序存储结构所需要的存储空间。首先定义一个指针表示存储空间的基地址，为了保存线性表的长度需要定义一个整型变量，此外为了指示顺序表当前分配的存储空间大小还需要定义一个整型变量，即当前线性表的最大容量。所需要的具体数据类型描述如下：#defineMAXLEN10

9、0#defineLIST_INCREASE10/线性表存储空间的动态分配增量typedefstructElemType*list;/线性表的存储空间的基地址intlength;/线性表的当前长度intmaxsize;/线性表当前分配的存储容量List_Sq;结构体类型List_Sq用于实现线性表的动态分配顺序存储结构。由于存储空间为动态分配，在对线性表进行插入等操作时，若原有的存储空间已满而不能满足进一步操作，可进行空间再分配，存储空间的增加量用LIST_INCREASE表示。下面我们将给出各种典型的线性表操作的算法。2、顺序表的生成算法生成线性表线性表的生成算法主要是为其准备所需要的存储空间

10、（这可通过malloc函数动态申请空间实现），同时为参数L的成员L.list、L.length、L.maxsize赋以相应的值。StatusCreatList_S(List_Sq&L)/构造一个空的线性表LL.list=(ElemType*)malloc(MAXLEN*sizeof(ElemType);if(!L.list)exit(OVERFLOW);/若存储空间分配失败，则退出程序L.length=0;/初始化表的长度为0L.maxsize=MAXLEN;/初始化表的存储容量returnOK;/初始化成功/CreatList_S算法2-1线性表的生成算法3、返回线性表中第i个元素值的算法返

11、回线性表中第i个元素值的算法在顺序存储线性表的连续单元中，第i个元素位于地址从L.list向后偏移i1的位置上（或处于L.list为基地址的连续单元中，下标为i1的位置上），我们可直接通过下标返回该元素的值。本算法的时间复杂度为O(1)。StatusGetElem_S(List_SqL,inti,ElemType&e)if(iL.length)returnERROR;/若i为无效值，返回错误e=L.listi1;/通过参数e返回第i个元素值returnOK;/GetElem_S算法2-2返回线性表中第i个元素的值4、线性表的插入算法在线性表的第i个位置插入元素该操作是指在线性表的第i个位置之前

12、插入新的数据元素，插入后线性表的长度增加1个单位，插入的元素分别与原线性表的第i1个元素、第i个元素在逻辑上是相邻的关系。由于顺序存储结构是通过元素之间存储位置的关系来反映逻辑关系，为了完成插入操作，满足插入元素与其前驱元素、后继元素之间的相邻关系，我们需要把原线性表第i个到第n个元素依次向后移动一个单位。如图2.2所示，在第4个和第5个元素之间插入元素，需要将第5个到第7个元素依次向后移动一个单位。StatusListInsert_S(List_Sq&L,inti,ElemTypee)if(iL.length+1)returnERROR;/若i为无效值，返回错误if(L.length=L.m

13、axsize)/若存储容量已满，则增加分配空间newbase=(ElemType*)realloc(L.list,(L.maxsize+LIST_INCREASE)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/若增加分配空间失败，退出程序L.list=newbase;/新基址L.maxsize+=LIST_INCREASE;/存储容量增加/ifq=&(L.listi1);/插入位置。q=L.list+i1;也可。for(p=&(L.listL.length1);p=q;p)/p=L.list+L.Length1;也可。*(p+1)=*p;/将插入元

14、素位置之后的元素依次后移一个位置*q=e;/插入元素e+L.length;/线性表长度增加1returnOK;/插入操作成功/ListInsert_S算法2-3线性表的插入算法该算法的主要操作和影响算法效率的步骤为：将插入位置其后的元素依次向后移一个位置。执行此算法时，假定线性表的长度为n，当向第i个位置（1in+1）插入元素时，需要后移ni+1个元素，所以进行每次插入平均需要移动元素的次数的数量级为n，故此算法的时间复杂度为O(n)。5、线性表的删除算法删除线性表中的第i个元素和插入操作的原理相同，当删除第i个元素之后，为了满足原线性表第i+1个和第i1个元素之间的相邻关系，我们需要将原第i

15、+1个到第n个元素依次向前移动一个单位。如图2.3所示，删除第4个元素后，需要将第5个到第7个元素依次向前移动一个单位。StatusListDelete_S(List_Sq&L,inti,ElemType&e)if(iL.length)returnERROR;/若i为无效值，返回错误p=&(L.listi1);/被删元素的位置，p=L.list+i1;也可e=*p;/通过e返回被删除的元素的值q=L.list+L.length1;/线性表的最后一个元素的位置for(+p;p=q;+p)*(p1)=*p;/被删除元素之后的元素依次前移L.length;/线性表长度减少1returnOK;/删除操

16、作成功/ListDelete_S算法2-4线性表的删除算法该算法的主要操作和影响算法效率的步骤是将所删除元素位置后的数据元素依次向前移一个位置。执行此算法时，假定线性表的长度为n，当删除第i个位置（1in）上的元素时，需要前移ni个元素，所以进行每次删除平均需要移动元素的次数的数量级为n，故此算法的时间复杂度为O(n)。6、线性表中查找元素的算法在线性表中查找满足条件的元素本算法从线性表的第一个数据元素开始，依次和给定元素进行比较，直至找到满足条件的元素为止，若未找到，则函数返回0。intLocateElem_S(List_SqL,ElemTypee,Status(*compare)(Elem

17、Type,ElemType)i=1;p=L.list;/线性表的第一个元素while(iL.lengthif(i=L.maxsize)/若存储容量已满，则增加分配空间newbase=(ElemType*)realloc(L.list,(L.maxsize+LIST_INCREASE)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);/若增加分配空间失败，退出程序L.list=newbase;/新基址L.maxsize+=LIST_INCREASE;/存储容量增加/ifq=L.list;/起始位置while(q=*q)q+;/找到元素的适当的插入位置for

18、(p=&(L.listL.length1);p=q;p)*(p+1)=*p;/将插入元素位置之后的元素依次后移一个位置*q=e;/插入元素e+L.length;/线性表长度增加1returnOK;/插入操作成功/List_Sorted_Insert_S算法2-6有序表的插入算法该算法的主要操作和影响算法效率的步骤为查找到新元素的插入位置，并将其后的元素依次向后移一个位置。执行此算法时，假定线性表的长度为n，则进行查找元素插入位置时平均需要比较元素次数的数量级为n，当插入元素时，需要后移ni+1个元素（若记插入位置为i），故此算法的时间复杂度为O(n)。8、有序表的合并算法有序表的合并在有序线性

19、表的合并中，通过对两个线性表的元素比较大小，选择较小的元素插入。当其中一个线性表的元素插入完成后，将另一个线性表的剩余元素直接插入即可。本算法适用于非递减排列的线性表的合并。voidMergeList_S(List_SqLa,List_SqLb,List_Sq&Lc)/非递减排列的有序线性表的合并pa=La.list;pb=Lb.list;Lc.maxsize=Lc.length=La.length+Lb.length;/新表的存储容量为两个表的长度之和pc=Lc.list=(ElemType*)malloc(Lc.maxsize*sizeof(ElemType);/为新表申请空间if(!Lc

20、.list)exit(OVERFLOW);/若申请空间失败，则退出程序pa_last=La.list+La.length1;pb_last=Lb.list+Lb.length1;/以表尾元素为标记进行合并while(pa=pa_last&pb=pb_last)/在未到达两表的表尾时，按照元素大小顺序进行合并if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;/插入剩余元素/MergeList_S算法2-7有序线性表的合并算法该算法的主要操作和影响算法效率的步骤为依次比较

21、两个线性表的元素，选择符合条件的元素进行插入，然后插入剩余元素。执行此算法时，假定两个线性表的长度分别为n和m，则进行比较后插入元素平均需要执行的次数的数量级为n+m，当插入剩余元素时，需要执行插入操作的数量级为n或m，故此算法的时间复杂度为O(n+m)。9、线性表排序算法线性表的排序本算法采用“起泡法”对线性表的数据元素进行排序，排序方式同数组排序方式类似。voidSortList_S(List_Sq&L)/排序成非递减线性表，使用“起泡法”a=L.listfor(j=0;jL.LENGTH1;J+)for(i=0;iai+1)t=ai;ai=ai+1;ai+1=t;/SortList_S算

22、法2-8线性表的排序算法该算法的主要操作和影响算法效率的步骤为起泡法的使用。执行此算法时，假定线性表的长度为n，则通过两层循环比较元素并且完成元素交换操作的数量级为n2，故此算法的时间复杂度为O(n2)。第三节线性表的链式表示和实现链式存储结构具有逻辑上相邻的元素在物理结构上可不相邻，灵活、简单地插入或删除结点而不必移动大量元素等特点。因此，当线性表经常进行插入和删除操作时，应采用链式存储结构表示线性表。1、线性表链式存储结构的数据类型定义线性表链式存储结构的数据类型定义链式存储结构具有以下特点：不要求逻辑上相邻的元素在物理结构上也相邻；允许迅速简单地插入或删除结点，而不必移动大量元素；但只能

23、顺序存取而不能随机存取线性表中任一元素。线性表的链式存储结构可通过单链表来实现。此时，线性表中的每个元素对应单链表中的一个结点，每个结点的数据域存储线性表的数据元素，每个结点的指针域存储其后继元素所在结点的地址，可以通过每个结点的指针域访问到其后继结点，如图2.4所示因此，单链表中每个结点都是由包含这个数据元素的信息和一个指示其直接后继的指针组成的一个结构体类型，具体描述如下：typedefstructLNodeElemTypedata;structLNode*next;LNode,*List_Link;每个单链表的头指针L是List_Link型的变量，指向链表中第一个结点。由表头指针出发可以

24、依次访问到每个结点，存取相应的数据元素值。线性表中数据元素间的线性关系都可以通过单链表中结点指针域的链接关系反映出来。当L=NULL时，意味着所表示的线性表为“空”表，其长度n为“零”。2、单链表设置头结点的作用为操作方便，在单链表的第一个结点之前，我们可附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等附加信息，头结点的指针域存储指向第一个结点的指针（即第一个结点的存储位置），如图2.5所示。带有头结点的单链表将给我们提供操作上的方便。因为若无头结点，则线性表中第一个结点的删除、在第一个结点之前插入元素等操作将和其他结点相应的操作有所不同。因此，为了操作

25、的方便，以下介绍的单链表均为带有头结点的单链表。与顺序存储结构不同，当我们使用链式存储结构的线性表时，不需要考虑线性表的存储容量，插入、删除元素时，只需要申请或释放线性表中结点的空间即可。下面我们将给出各种典型的线性表操作的算法。3、链式存储的线性表的生成算法生成线性表StatusCreatList_L(List_Link&L)L=(List_Link)malloc(sizeof(LNode);/为头结点申请空间if(!L)exit(OVERFLOW);/若申请空间失败，则退出程序Lnext=NULL;returnOK;/CreatList_L算法2-9链式存储的线性表的生成算法4、链式存储结

26、构下返回线性表中第i个元素值的算法返回线性表中第i个元素的值在单链表中返回指定元素的值，和顺序表不同，不能按下标值来随机存取其中的元素，只能顺序存取，即要从头结点开始，通过每个结点的指针域依次访问其后继结点，直到访问到第i个结点为止。StatusGetElem_L(List_LinkL,inti,ElemType&e)p=Lnext;j=1;/p指向第一个结点，j为计数器while(p&j/通过指针依次查找后继结点，直到第i个元素或遍历完线性表为止p=pnext;+j;if(!p|ji)returnERROR;/无第i个元素，即i线性表长度或idata;returnOK;/GetElem_L算

27、法2-10返回线性表中第i个元素的值的算法该算法的主要操作和影响算法效率的步骤为通过顺序访问的方式查找到第i个元素的位置。进行顺序访问元素的平均次数的数量级为n，故此算法的时间复杂度为O(n)。5、链式存储的线性表的插入算法在线性表的第i个位置插入元素同返回第i个元素算法类似，都需要通过顺序访问结点的方式找到插入元素的前驱的位置，而后申请空间，插入结点。如图2.6，在数据元素a和数据元素b之间插入数据元素e，插入后e所在结点*s的指针域为其前驱结点*p的原来指针域的值，以实现*s结点的后继为*p结点原来的后继，同时*p的指针域指向结点*s。StatusListInsert_L(List_Lin

28、k&L,inti,ElemTypee)p=L;j=0;/p指向头结点，j为计数器while(p&jnext;+j;/到第i1个结点if(!p|ji1)returnERROR;s=(List_Link)malloc(sizeof(LNode);/为插入元素申请空间sdata=e;/插入元素snext=pnext;pnext=s;returnOK;/ListInsert_L算法2-11链式存储的线性表的插入算法该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法相同，为查找到第i1个元素的位置，进行顺序访问元素的平均次数的数量级为n，故此算法的时间复杂度为O(n)。6、链式存储的线性表的删除

29、算法删除线性表中的第i个元素删除元素的操作是将要删除结点的前驱结点的指针值设置为其后继结点的位置，然后释放删除结点的空间。如图2.7所示，删除结点a和结点c之间的结点b，则将结点a的指针指向结点b的后继即结点c的位置，然后释放结点b的空间。StatusListDelete_L(List_Link&L,inti,ElemType&e)p=L;j=0;/p指向头结点，j为计数器while(pnext&jnext;+j;/到第i1个结点if(!(pnext)|ji1)returnERROR;q=pnext;/完成删除元素操作pnext=qnext;e=qdata;free(q);returnOK;/

30、ListDelete_L算法2-12链式存储的线性表的删除算法该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法相同，为查找到第i1个元素的位置，进行顺序访问元素的平均次数的数量级为n，故此算法的时间复杂度为O(n)。7、在链式存储的线性表中查找元素的算法在线性表中查找满足条件的元素同返回第i个元素算法类似，也需要通过顺序访问结点的方式找到满足条件的元素并返回该元素的位置。若直到线性表尾还未找到满足条件的元素，则返回空。intLocateElem_L(List_LinkL,ElemTypee,Status(*compare)(ElemType,ElemType)p=Lnext;j=1;

31、/p指向第一个结点，j为计数器while(p&(*compare)(pdata,e)p=pnext;+j;/若p-data、e满足关系则compare为0/查找相匹配的结点if(!p)return0;elsereturnj;/LocateElem_L算法2-13在链式存储的线性表中查找元素的算法该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法类似，为查找到满足条件的元素的位置，进行顺序访问元素的平均次数的数量级为n，故此算法的时间复杂度为O(n)。8、链式存储的有序线性表的插入算法有序表的插入有序表的插入也是通过顺序访问结点的方式找到满足条件的插入位置，然后插入元素即可，插入过程中进

32、行的操作同普通插入操作相同。StatusList_Sorted_Insert_L(List_Link&L,ElemTypee)/非递减排列的有序线性表的插入p=L;/p指向头结点while(pnext&e=pnextdata)p=pnext;/或者找到表尾（此时pnext为0）/或者找到第一个比e的值大的数据元素结点：*（pnext）/对上述两种情况，都意味着新元素插入到p结点之后s=(List_Link)malloc(sizeof(LNode);sdata=e;snext=pnext;/插入元素pnext=s;returnOK;/插入操作成功List_Sorted_Insert_L算法2-1

33、4链式存储的有序线性表的插入算法该算法的主要操作和影响算法效率的步骤同在线性表中查找满足条件的元素类似，进行顺序访问元素的平均次数的数量级为n，故此算法的时间复杂度为O(n)。9、链式存储的有序线性表的合并算法有序表的合并在有序表的合并中，通过比较两个线性表的元素的大小，选择元素从小到大依次插入。当其中一个线性表的元素插入完成后，将另一个线性表的剩余元素直接插入即可。voidMergeList_L(List_Link&La,List_Link&Lb,List_Link&Lc)pa=Lanext;pb=Lbnext;/pa,pb分别指向La，Lb的第一个结点Lc=pc=La;/La为最终合并表，

34、实际上是将Lb的元素结点插入到La中while(pa&pb)/通过比较选择插入元素if(padatadata)pcnext=pa;pc=pa;pa=panext;elsepcnext=pb;pc=pb;pb=pbnext;pcnext=pa?pa:pb;/将比较完后的剩余元素插入free(Lb);/MergeList_L算法2-15链式存储的有序线性表的合并算法该算法的主要操作和影响算法效率的步骤同顺序表中有序表的合并类似，为依次比较两个线性表的元素，选择符合条件的元素进行插入，然后插入剩余元素。假定两个线性表的长度分别为n和m，则此算法的时间复杂度为O(n+m)。10、链式存储的线性表的排序

35、算法线性表的排序本算法采用“起泡法”对线性表的数据元素进行排序，排序方式同数组排序方式类似。本算法中利用指向表尾结点的指针p作为结束标记；利用end表示每一遍处理范围中最后一结点，即每遍的结束标记。如果元素需要交换位置，则仅需交换两个结点的数据元素的数据即可。voidSortList_L(List_Link&L)/将原来无序的线性表排序为非递减线性表，使用“起泡法”if(L-next=NULL)return;p=Lnext;/p指向第一个结点while(p-next)p=pnext;/p为表尾结点，作为结束标记end=p;/end为每遍处理范围的结束标记for(s=Lnext;s!=p;s=s

36、next)/只意味循环n-1次for(q=Lnext;q!=end;temp=q,q=qnext)/使用“起泡法”进行排序if(qdata)(qnextdata)t=qdata;qdata=qnextdata;qnextdata=t;end=temp;/SortList_L算法2-16链式存储的线性表的排序算法该算法的主要操作和影响算法效率的步骤同顺序表中线性表的排序类似，都是使用起泡法进行主要的操作。执行此算法时，假定线性表的长度为n，则通过两层循环比较元素并且完成元素交换操作的数量级为n2，故此算法的时间复杂度为O(n2)。第四节线性表的其他链式表示在特定的运行环境下或针对一些特定操作，线

37、性表也可以采用其他链式表示。比如，运用不设“指针”类型的高级语言实现单链表，就应采用静态链表；对于线性表的合并操作，采用循环链表则操作更容易实现；采用双向链表则有助于查找结点的前驱元素。1、静态链表的生成算法静态链表（StaticLinkedList）是利用一组地址连续的内存空间来描述线性链表，把数组元素作为存储结点，数组元素类型包含数值域data和游标指示器cur。游标定义为整型，指示结点在数组中的相对位置。通常下标为零的元素被看成是头结点，其游标指示器指示线性链表的第一个结点。这种存储结构同样具有链式存储结构的主要优点，即在插入和删除元素时只需要修改游标而不用移动元素，但也有一些缺点，例如

38、要预先分配一个较大的空间。静态链表描述如下：#defineMAXSIZE1000typedefstructElemTypedata;intcur;component,List_StMAXSIZE;在静态链表中，插入、删除元素的算法为修改游标，与单链表中要通过修改指针实现插入、删除操作不同的是，malloc和free两个函数使用的是静态链表本身的已声明的空间，即静态链表中未使用的部分，静态链表的这个部分称为“备用链表”。设S为List_St型变量，如图2.8，S1为线性表的头结点（“1”为该结点的游标，即头指针），i=S1.cur为第一个结点的位置，Si.data存储线性表的第一个元素，Si.c

39、ur指示第二个结点的位置。一般地，若i指示第k个结点位置，则Si.data为第k个结点的值，Si.cur为下一结点（第k+1个结点）的位置。对于备用链表（也带有头结点，通常为S0），我们可以通过S0.cur指向备用链表的第一个结点，如图2.8，游标指示器指向S8，则S8是备用链表的第一个结点，而后通过每个结点的游标将备用链表的结点连接起来。下面我们将给出几个典型的静态链表操作的算法。将整个数组空间初始化成一个空闲链表voidInitSpace_St(List_St&S)/将一维数组S中各分量链成一个备用链表/S0.cur指向备用链表的第一个结点/0为空闲链表头指针for(i=0;iMAXSIZ

40、E1;+i)Si.cur=i+1;SMAXSIZE1.cur=0;/InitSpace_St算法2-18空闲链表的初始化算法2、静态链表的插入算法在静态链表中实现的定位函数LocateElem本算法通过静态链表各个结点的游标指示器依次顺序访问每个结点，找到满足条件的元素，或者直到静态链表尾为止。intLocateElem_St(List_StS,ElemTypee)/在静态的单链线性表中查找1个值为e的元素/若找到，则返回它在S中的下标，否则返回0i=S1.cur;while(i&Si.data!=e)i=Si.cur;returni;/LocateElem_St算法2-19静态链表的定位函数

41、该算法的主要操作和影响算法效率的步骤为通过静态链表的结点游标依次顺序访问每个结点，与线性表的长度有关，故此算法的时间复杂度为O(n)。在静态链表的指定位置插入元素在静态链表中插入元素，首先使用Malloc_St(List_StS)函数从备用链表中取出一个结点的单元，即将备用链表头结点的游标指向的单元取出。如图2.9(a)所示，使用S0.cur指向的S8结点，令S0.cur=S8.cur，使头结点S0指向S8的后继元素，完成取出S8的操作。然后通过顺序访问找到插入位置，在i=7的位置即元素a6之后插入S8结点，如图2.9(b)所示，则S8.cur=S7.cur，S7.cur=8，使S7的后继元素

42、为S8，S8的后继元素为原S7的后继元素。intMalloc_St(List_StS)/若备用空间链表非空，则返回分配的结点的下标，否则返回0i=S0.cur;if(S0.cur)S0.cur=Si.cur;returni;/Malloc_StStatusInsert_St(List_St&S,inti,ElemTypee)/在静态的单链线性表中查找第i1个元素的位置/若找到，则在它的下一个位置插入元素，否则返回ERRORj=1;for(k=0;j&ki1)returnERROR;m=Malloc_St(S);if(!m)exit(OVERFLOW);Sm.data=e;Sm.cur=Sj.c

43、ur;Sj.cur=m;returnOK;/Insert_St算法2-20静态链表的插入算法该算法的的主要操作和影响算法效率的步骤为通过静态链表的结点的游标顺序访问每个结点找到插入位置，与线性表的长度有关，故此算法的时间复杂度为O(n)。3、静态链表的删除算法删除静态链表中指定位置的元素在静态链表中删除指定位置的元素，首先需要通过顺序访问找到删除元素的位置，如图2.9(b)所示，删除第2个位置的元素，即元素a2，则令S2.cur=S3.cur，使S2.cur指向S3的后继元素。然后使用Free_St(List_St&S,intn)函数将结点S3放回备用链表的头结点之后，如图2.9(c)所示，使

44、S3.cur=S0.cur，S0.cur=3，把S3插入到备用链表，从而完成操作。voidFree_St(List_StS,intn)/将下标为n的结点回收到备用链表Sn.cur=S0.cur;S0.cur=n;/Free_StStatusDelete_St(List_St&S,inti,ElemType&e)/在静态的单链线性表L中查找第i1个元素的位置/若找到，且存在它的下一个位置的元素，则删除；否则返回ERRORj=1;for(k=0;Sj.cur&ki1)returnERROR;m=Sj.cur;e=Sm.data;Sj.cur=Sm.cur;Free_St(S,m)returnOK;

45、/Delete_St算法2-21静态链表的删除算法该算法的主要操作和影响算法效率的步骤为通过静态链表的结点的游标顺序访问每个结点找到删除位置，与线性表的长度有关，故此算法的时间复杂度为O(n)。4、循环链表结构循环链表（CircularLinkedList）的表尾结点的指针域非空，它指向表头结点的位置，整个链表形成一个环。对于循环单链表来说，只要知道表内任意一个结点的地址，通过它都可访问表内其余所有结点。虽然在循环链表中没有一个结点的指针域能够标志某类操作对表中所有结点是否执行完毕，但从循环链表具有的对称性来看，可以指定其中任何一个结点，从其出发依次对每个结点进行操作，当再次回到这个结点时就应

46、停止操作。通过引入一个特殊的可识别的额外结点作为表头也可以解决这个问题。这类循环链表的表头指针不是直接指向第一个结点，而是指向一个“无意义”的结点，再由该结点的指针域指向真正的第一个结点，此外表尾结点的指针域不是空而是指向头结点，见图2.10。类似地，在循环链表中引入尾指针替代头指针，可使某些操作简化。例如将两个线性表合并成一个表的例子中，若指定了尾指针，仅需将一个线性表的表尾和另一个表的表头相接即可。循环链表的操作和线性链表的操作基本一致，差别仅在于算法中的循环条件改为p或pnext是否等于头指针。关于循环链表各种操作实现的算法我们不在此一一列举。5、双向链表结构单向链表的每一个结点只有一个

47、指向其后继结点的指针域，此时对每一个结点可以方便地查找到其后继结点，但要操作它的前驱结点，则必须从头结点开始依次搜索一遍。若某一个线性表的操作常常涉及到某一结点的前驱结点，则可以利用双向链表。双向链表（DoubleLinkedList）的每一个结点由本身的数据元素信息、指向前驱结点的指针域和指向后继结点的指针域三部分组成。双向链表也可以带头结点，也可以采用循环链接。其存储结构描述如下：TypedefstructDbLNodeElemTypedata;structDbLNode*prior;structDbLNode*next;DbLNode,*DbLinkList;双向链表具有以下优点：可以从

48、正反两个方向对线性表进行搜索，对每一个结点可以方便地操作其前驱结点和后继结点；当线性表的某一链被破坏时，可以通过正反两个方向读这个链以重新恢复链表。双向链表很容易进行插入和删除操作，如图2.11所示。删除操作：要求删除p指向的结点，并假定存在其前驱和后继结点：ppriornext=pnext;pnextprior=pprior;插入操作：在p指向的结点前插入一个s指针指向的结点，并假定存在其前驱：sprior=pprior;ppriornext=s;snext=p;pprior=s;第五节线性表的应用举例在现实生活中，线性表的应用比比皆是。本节以物流管理中的仓库管理为例说明线性表的应用。1、仓

49、库初始化和销毁算法初始化仓库voidCreatWhouse(Whouse&W,intn)/创建仓库，输入n种货物的数据CreatList_L(W);for(i=1;i=n;+i)/依次输入货物数据printf(“n请输入货物的种类（az）：”);scanf(&kinds);printf(“n请输入货物的数量：”);scanf(&number);e.kind=kinds;e.num=number;if(!LocateElem_L(W,e,cmp)ListInsert_L(W,i,e);/若输入货物的种类在链表中不存在，则插入数据，否则会造成种类重复/CreatWhouseintcmp(ElemTypea,ElemTypeb)/比较货物数据中的货物的种