山东大学《数据结构》讲义02线性表.docx

第二章线性表
内容概述线性结构是每一个有意义的程序基本都使用的一种数据结构，也是最简单的数 据结构。那么，线性结构如何表示与实现？本章从线性表的抽象数据类型定义、 线性表的顺序存储及实现算法、线性表的链式存储及算法实现等三个方面阐述该 问题。
重点与难点重点为顺涓表和单链表的描述和插入、删除运算以及算法的效率分析。难点为 单链表的插入、删除运算和链表的应用。
思考.线性结构与非线性结构的根本区别是什么？
1 .线性表有哪两种存储结构，各有哪些优缺点？
2 .在单链表和双向链表中，能否从当前结点出发访问任一结点？
3 .当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，那么 采用何种存储结构为宜？当经常进行的是插入和删除操作时，那么应采用存储结构 为宜？
4 .在单链表中设置头结点有何作用？
5 .有一个单链表L (至少有1个结点)，编写一个算法将L逆置，即最后一个 结点变成第一个结点，原来倒数第二个结点变成第二个结点，如此等等。
6 .有一个单链表，其结点的元素值以非递减有序排列，其结点的元素值有可能 相同，编写一个算法删除单链表中多余的元素值相同的结点。
第一节线性表的类型定义线性表示最常用且最简单的一种数据结构。了解线性表的结构特点、掌握线性表 抽象类型定义是运用线性结构解决具体应用问题的基础。
1.线性表定义、线性表的结构特点所谓线性表(Linear_List),就是n (n>0)个数据元素的集合{al,a2,…,an}, 这些数据元素之间有逻辑上的线性关系。
线性表结构的特点是：当数据元素集合为非空时(即n>0),那么(1)有且仅 有一个元素作为该结构的第一个元素，即al； (2)有且仅有一个元素作为该结 构的最后一个元素，即an； (3)当l时，第k个元素ak有且仅 有一个直接前驱，即ak-1,有且仅有一个直接后继，即ak+1；另外，al的后继 为a2, al无前驱，an的前驱为an-1, an无后继。
具有n个元素的线性表，n称为线性表的长度。当长度n为。时，线性表称为 空表。当n>0时，线性表中每个数据元素ai的位置称为ai在线性表中的位序。
线性表中每个数据元素在不同的情况下，可以是一个数或一个符号，也可以是 一篇文章，甚至是图片等其他更复杂的信息。例如，2到20的所有质数：
(2, 3, 5, 7, 11, 13, 17, 19)是一个线性表，表中的数据元素是单个的整数。又如，一个班级的学生姓名集合： (李帅，张伟，……，王明)
表中的数据元素是字符串。
在第一章所举的例子中，航班信息表为稍复杂的线性表，一个数据元素可以由 在数据元素a和数据元素b之间插入数据元素金插入后e所在结点*s的指针域 为其前驱结点*p的原来指针域的值,以实现*s结点的后继为*p结点原来的后继, 同时*P的指针域指向结点*s。
StatusListInsert_ L (List_ Link&L, inti, Elem Typee){
p=L;j=O;〃p指向头结点,j%计数器
while(p&&jnext;++j;}//^iJM i-1 个结点
if(!pllj>i-l)returnERROR;
s=(List_ Link)malloc(sizeof(LNode));〃为插入元素申请空间
s->data=e;〃插入元素
s->next=p->next;
p->next=s;
returnOK;}//ListInsert_L
算法2-11链式存储的线性表的插入算法
该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法相同,为查 找到第i-1个元素的位置,进行顺序访问元素的平均次数的数量级为n,故止匕算 法的时间复杂度为O(n)o6、链式存储的线性表的删除算法
删除线性表中的第/个元素
删除元素的操作是将要删除结点的前驱结点的指针值设置为其后继结点的位 置,然后释放删除结点的空间。如图2.7所示,删除结点a和结点c之间的结点 b,那么将结点a的指针指向结点b的后继即结点c的位置,然后释放结点b的空 间。
StatusListDelete_ L (List_ Link&L, inti, Elem Type&e){
p=L;j=O;〃p指向头结点，j为计数器
while(p->next&&jnext;++j;}〃到第 i-1 个结点 if(!(p->next)Hj>i-l)returnERROR;
q=p_>next力完成血除元素操作
p->next=q->next;
e=q->data;
free(q);
returnOK;}//ListDelete_L
算法屋12链式存储的线性表的删除算法
该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法相同,为查 找到第i-l个元素的位置,进行顺序访问元素的平均次数的数量级为n,故此算法的时间复杂度为0(n)o_
7、在链式存储的线性表中查找元素的算法
在线性表中查找满足条件的元素
同返回第i个元素算法类似，也需要通过顺序访问结点的方式找到满足条件的 元素并返回该元素的位置。假设直到线性表尾还未找到满足条件的元素,那么返回空。 intLocateElem_ L(List_ LinkL, Elem Typee,Status(*compare)(Elem Type.Elem Type ))(
p=L->next;j=l;〃p指向第一个结点，j为计数器
while(p&&(*compare)(p->data/ e)){p=p->next;++j;}
〃假设p・>data、e满足茨系贝U compare/0
〃查找相匹配的结点
if(!p)returnO;
elsereturnj;}//LocateElem_L
算法2-13在链式存储的线性表中查找元素的算法
该算法的主要操作和影响算法效率的步骤同返回第i个元素的算法类似,为查 找到满足条件的元素的位置,进行顺序访问元素的平均次数的数量级为",故此 算法的时间复杂度为0(n)o8、链式存储的有序线性表的插入算法
有序表的插入
有序表的插入也是通过顺序访问结点的方式找到满足条件的插入位置,然后插 入元素即可,插入过程中进行的操作同普通插入操作相同。
Status List_ Sorted_ Insert_ L (List_ Link&L, Elem Typee){
〃非递次排列的看序线屉表的钻入
p=L;//p指向头结点
while(p->next&&e> =p->next->data)p=p->next;
〃或鲁找到表尾(此时p->next为0)
〃或者找到第一个比e的值大的数据元素结点:* (p—>next)
〃对上述两种情况,都意味着新元素插入到p结点之后
s=(List_ Link)malloc(sizeof(LNode));
s->data=e;
s-> next=p-> next;〃插入 元素

p->next=s;
retumOK;〃插入操作成功}List_Sorted_Insert_L
算法2-14链氐存储的有序线性表的插入算法
该算法的主要操作和影响算法效率的步骤同在线性表中查找满足条件的元素 类似,进行顺序访问元素的平均次数的数量级为",故此算法的时间复杂度为 0(n)o9、链式存储的有序线性表的合并算法
有序表的合并
在有序表的合并中,通过比拟两个线性表的元素的大小,选择元素从小到大依 次插入。当其中一个线性表的元素插入完成后,将另一个线性表的剩余元素直接 插入即可。
voidMergeList_ L(List_ Link&La, List_ Link&Lb, List_ Link&L c){
pa=La-> next;pb=Lb-> next;
〃pa,pb分别指向La, Lb的第一个结点
Lc=pc=La;
〃La为最终合并表，实际上是将Lb的元素结点插入到La中
while(pa&&pb){〃通过比拟选择插入元素
if(pa->data <=pb->data){
pc->next=pa;pc=pa;pa=pa->next;
}
else{pc->next=pb;pc=pb;pb=pb->next;}
} _
pc->next=pa?pa:pb;〃将比拟完后的剩余元素插入
free(Lb);}//MergeList_L
算法2-15链式存储的有序线性表的合并算法
该算法的主要操作和影响算法效率的步骤同顺序表中有序表的合并类似,为依 次比拟两个线性表的元素,选择符合条件的元素进行插入,然后插入剩余元素。 假定两个线性表的长度分别为n和m,那么此算法的时间复杂度为O(n+m)。
10、链式存储的线性表的排序算法线性表的排序
本算法采用''起泡法〃对线性表的数据元素进行排序,排序方式同数组排序方式 类似。本算法中利用指向表尾结点的指针p作为结束标记;利用end表示每一 遍处理范围中最后一结点,即每遍的结束标记。如果元素需要交换位置,那么仅需 交换两个结点的数据元素的数据即可。
voidSortList_L(List_ Link&L){
〃将原来完序的纺性表排序为非递减线性表,使用''起泡法〃
if(L ->next==NULL)return;
p=L->next;//p指向第一个结点
while(p->next)p=p->next;〃p为表尾结点,作为结束标记
end=p;//end为每遍处理范围的结束标记
fo「(s=L->next;s!=p;s=s->next){〃只意味循环 n-1 次
for(q=L->next;q!=end;temp=q/ q=q->next)
〃使用''起泡法〃进行排序
if((q->data)>(q->next->data))
{t=q->data;q->data=q->next->data;q->next->data=t;}
end=temp;
}}//SortList_L
算法2-16链式存储的线性表的排序算法
该算法的主要操作和影响算法效率的步骤同顺序表中线性表的排序类似,都是 使用起泡法进行主要的操作。执行此算法时,假定线性表的长度为n,那么通过两 层循环比拟元素并且完成元素交换操作的数量级为n2,故此算法的时间复杂度 为。(n2)。
第四节线性表的其他链式表示在特定的运行环境下或针对一些特定操作,线性表也可以采用其他链式表示。比 如,运用不设''指针〃类型的高级语言实现单链表,就应采用静态链表;对于线性 表的合并操作,采用循环链表那么操作更容易实现;采用双向链表那么有助于查找结 点的前驱元素。
1.静态链表的生成算法
静态链表（StaticLinkedList）是利用一组地址连续的内存空间来描述线性链表, 把数组元素作为存储结点,数组元素类型包含数值域data和游标指示器cur。游 标定义为整型,指示结点在数组中的相对位置。通常下标为零的元素被看成是头 结点,其游标指示器指示线性链表的第一个结点。这种存储结构同样具有链式存 储结构的主要优点,即在插入和删除元素时只需要修改游标而不用移动元素,但 也有一些缺点,例如要预先分配一个较大的空间。静态链表描述如下:
#defineMAXSIZE1000typedefstruct{ ElemTypedata;
intcur;
}component,List_St[MAXSIZE];
在静态链表中,福入、删除元素的算法为修改游标,与单链表中要通过修改指 针实现插入、删除操作不同的是,malloc和free两个函数使用的是静态链表本 身的已声明的空间,即静态链表中未使用的局部,静态链表的这个局部称为''备 用链表〃。
设S为List_St型变量,如图2.8, S[l]为线性表的头结点（“〃为该结点的游标, 即头指针），i=S[l].cu「为第一个结点的位置,S[i].data存储线性表的第一个元 素,S[i].cur指示第二个结点的位置。一般地,假设i指示第k个结点位置,那么S[i].data 为第k个结点的值,S[i],cu「为下一结点（第k+1个结点）的位置。对于备用链 表（也带有头结点,通常为S[0]）,我们可以通过S[O].cur指向备用链表的第 一个结点，如图2.8,游标指示器指向S[8],那么S[8]是备用链表的第一个结点, 而后通过每个结点的游标将备用链表的结点连接起来。下面我们将给出几个典型 的静态链表操作的算法。
1头指针
图2.8静态饿表例如
缶刖信我的 第一个结点

将整个数组空间初始化成一个空闲链表 voidInitSpace_St（List_St&S）{
〃将一维数组S中各分量链成一个备用链表 //S[O].cur指向备用链表的第一个结点
〃。为空闲链表头指针
for(i=0;iee){
〃在静态的串链线栓宝中查找1个值为e的元素〃假设找到,那么返回它在S中的下标,否那么返回0
i=S[l].cur;
while(i&&S[i]. data!=e)i=S[i]. cur;
returni;}//LocateElem_St
算法2-历静态链表的定位函数
该算法的主要操作和影响算法效率的步骤为通过静态链表的结点游标依次顺 序访问每个结点,与线性表的长度有关,故此算法的时间复杂度为0(〃)。 在静态链表的指定位置插入元素
在静态链表中插入元素,首先使用Malloc_St(List_StS)函数从备用链表中取出 一个结点的单元,即将备用链表头结点的游标指向的单元取出。如图2.9(a)所示, 使用S[O].cu/指向的S[8]结点,令S[0],CUr=S[8].CU/,使头结点S[0]指向S[8] 的后继元素，完成取出S[8]的操作。然后通过顺序访问找到插入位置,在i=7 的位置即元素a6之后插入S[8]结点，如图2.9(b)所示,S[8].cur=S[7].cur, S[7].cu「=8,使S[7]的后继元素为S[8], S[8]的后继元素为原S[7]的后继元素。 intMalloc_St(List_StS){
〃假设备用空间铺表非空,那么返回分配的结点的下标,否那么返回0
i=S[O].cur;
if(S[O]. cur)S[O]. cur=S[i].cur;
returni;}//Malloc_St
StatusInsert_St(List_St&SJntifE!em Typee){
〃在静态面单链线屉表中查找第i-l个元素的位置
〃假设找到,那么在它的下一个位置插入元素,否那么返回ERROR
j=l；
for(k=0;j&&ki-l)returnERROR;
m=Malloc_St(S);
if(!m)exit(OVERFLOW);
S[m].data=e;
S[m]. cur=S{j]. cur;S[j]. cur=m;
returnOK;}//Insert_St
算法2-20静态链表的插入算法该算法的的主要操作和影响算法效率的步骤为通过静态链表的结点的游标顺
序访问每个结点找到插入位置,与线性表的长度有关,故此算法的时间复杂度为
O(n)o表的

表的
表尾
3
4
7
9
(b)
(c)
图2.9
3、静态链表的删除算法删除静态链表中指定位置的元素
在静态链表中删除指定位置的元素,首先需要通过顺序访问找到删除元素的位 置，如图2.9(b)所示,删除第2个位置的元素,即元素a2,贝U令S[2].cur=S[3].cu「, 使S[2],cu「指向S[3]的后继元素。然后使用Free_St(List_St&S,intn)函数将结点 S[3]放回备用链表的头结点之后，如图2.9(c)所示,使S[3],cur=S[0].Cur, S⑼,cur=3,把S[3]插入到备用链表,从而完成操作。
voidFree_ St(L ist_ StS, intn){
〃将下标为n而结点回收到备用链表
S[n]. cur=S[O]. cur;S[O]. cur=n;}〃Free_St
StatusDelete_St(List_St&SJnti,Elem Type&e){
〃在静态而单链线程表L中查找第i-l个元素的位置
〃假设找到,且存在它的下一个位置的元素,那么删除;否贝U返回ERROR
j=l；
for(k=0;S[j]. cur&&ki-l)returnERROR;
m=S[j]. cur;e=S[m]. data;
S[j]. cur=S[m]. cur;Free_St(Sfm)
returnOK;}//Delete_St
算法2-21静态链表的删除算法
该算法的主要操作和影响算法效率的步骤为通过静态链表的结点的游标顺序 访问每个结点找到删除位置,与线性表的长度有关,故此算法的时间复杂度为 0(n)o4、循环链表结构
循环链表(CircularLinkedList)的表尾结点的指针域非空,它指向表头结点的 位置,整个链表形成一个环。
对于循环单链表来说,只要知道表内任意一个结点的地址,通过它都可访问表 内其余所有结点。虽然在循环链表中没有一个结点的指针域能够标志某类操作对 表中所有结点是否执行完毕,但从循环链表具有的对称性来看,可以指定其中任 何一个结点,从其出发依次对每个结点进行操作，当再次回到这个结点时就应停 止操作。通过引入一个特殊的可识别的额外结点作为表头也可以解决这个问题。 这类循环链表的表头指针不是直接指向第一个结点,而是指向一个''无意义〃的结 点,再由该结点的指针域指向真正的第一个结点,此外表尾结点的指针域不是空 而是指向头结点,见图210。

类似地,在循环链表中引入尾指针替代头指针,可使某些操作简化。例如将两 个线性表合并成一个表的例子中,假设指定了尾指针,仅需将一个线性表的表尾和 另一个表的表头相接即可。
循环链表的操作和线性链表的操作基本一致，差异仅在于算法中的循环条件改 为p或p->next是否等于头指针。关于循环链表各种操作实现的算法我们不在 此列举。
5、双向链表结构
单向链表的每一个结点只有一个指向其后继结点的指针域,此时对每一个结点 可以方便地查找到其后继结点,但要操作它的前驱结点,那么必须从头结点开始依 次搜索一遍。假设某一个线性表的操作常常涉及到某一结点的前驱结点,那么可以利 用双向链表。
双向链表(DoubleLinkedList)的每一个结点由本身的数据元素信息、指向前驱 结点的指针域和指向后继结点的指针域三局部组成。双向链表也可以带头结点, 也可以采用循环链接。其存储结构描述如下:
TypedefstructDbLNode{
ElemTypedata;
structDbLNode *prior;
structDbLNode *next;
}DbLNodef *DbLinkList;
双向链表具有以下优点:可以从正反两个方向对线性表进行搜索,对每一个结 点可以方便地操作其前驱结点和后继结点;当线性表的某一链被破坏时,可以通 过正反两个方向读这个链以重新恢复链表。
双向链表很容易进行插入和删除操作,如图2.11所示。
BreakNewLine]~>
图2. 11在双向燧表中删除和插入一个结点
删除操作：要求删除p指向的结点，并假定存在其前驱和后继结点:
p->prior->next=p->next;
p->next->prior=p->prior;插入操作:在p指向的结点前插入一个s指针指向的结点,并假定存在其前驱:
s->prior=p->prior;p->prior->next=s;s->next=p;
p->prior=s;第五节线性表的应用举例
在现实生活中,线性表的应用比比皆是。本节以物流管理中的仓库管理为例说明 线性表的应用。
1 .仓库初始化和销毁算法初始化仓库
voidCreatWhouse(Whouse&W,intn){
〃创立仓库,输入n种货物的数据
CreatList_L(W);
for(i=l;i<=n;++i){〃依次输入货物数据
printf(''\n请输入货物的种类(a~z)：
scanf(&kinds);
printf(''\n请输入货物的数量：〃);
seanf(&n umber);
e. kind=kinds;e. num=number;
if(!Locate曰em_L(W, e, cmp))ListInsert_L(W/i, e);
〃假设输入货物而种类在链表中不存在,那么插入数据,否那么会造成种类重复
)}//CreatWhouse
intcmp(Elem Typea.Elem Typeb){〃比拟货物数据中的货物的种类
if(a.kindvB,KIND)
else(a. kind= =b, kind)returnO;
elseretuml;}//cmp
销毁仓库voidDestroyWHouse(WHouse& W){
ClearList_L(W);
free(W);}//DestroyWHouse
2货车初始化和销毁算法初始化货车
voidCreatTruck(Truck& T){
〃创立货车,输入3个车厢的货物的数据
CreatList_L(T);
for(i=l;i<=3;++i){〃依次输入货物数据
printfC\n请输入货物的种类(a〜z)：
scanf(&kinds);
printf(''\n请输入货物的数量：〃);
seanf(&n umber);
e. kind=kinds;e. num=number;
if(!LocateElem_ L (Tf ef cmp))ListInsert_L(Tfif e);
〃假设输入货物而种类在链表中不存在,那么插入数据,否那么会造成种类重复}//CreatTruck
在初始化仓库和货车线性链表的操作中,影响算法时间复杂度的主要操作为LocateElem_L(List_LinkL,Elem Typee7Status(*compa「e)())和
ListInsert_L(List_Link&Ljnti,ElemTypee)函薮 该算法的时间复杂度为 0(n)。 销毁货车voidDestroyTruck(Truck& T){
ClearList_L(T);
free(T);}//DestroyTruck
3、入货操作的算法整理货物
voidGoodsSort(List_ Link&L){
〃通过输入不同岛参数L,可对仓库和货车的货物进行排列
SortList_L(L);〃对货物依据种类按照字母顺序a〜z进行排列)
整理货物数据时,需要使用SortListL(List_Link&L)函数,它的时间复杂度为O(n2)o
显示货物数据voidPrintData(List_ LinkL){
〃通过输入不同而参数L,可对仓库和货车的货物数据进行打印
p=L;//p指向头结点
printfC'n货物数据如下：、n〃)
while(p=p->next){〃依次打印货物数据货物 ％c: %d 件 \n f\p->data. kind,p->data. num);
}//PrintData在显示货物数据的操作中,主要进行的是对线性链表的结点的顺序访问,访问频 数和线性链表的长度成正比。该算法的时间复杂度为0(n)。
入货voidInput(WHouse& Wf Truck& T){
〃将货车中的货物放入仓库
pw= W;qw= W->next;qt= T->next;//qw, qt 分别指向第一个结点
while(qw&&qt){
a=qw->data;b=qt->data;//a. b 为货物数据
switch(cmp(a, b)){
〃通过比拟决定是插入数据元素还是改变仓库链表数据元素中货物的数量 值
case-1 :〃qw数据中的种类小于qt数据中的种类
pw=qw;qw=qw->next;break;
case。:力qw数据中的种类和qt数据中的种类相同
sum=a.num+b. num;
if(sum!=O. 0){qw->data. num=sum;pw=qw;qw=qw->next;}
〃修改仓库中该货物数据else{
pw->next=qw->next;//M/^ qw 结点f「ee(qw);〃完成删除元素操作
qw=pw->next
}
qt=qt->next;
break;
easel:
〃qw数据中种类大于qt数据中的种类,即仓库中没有该种类的货物
List_Sorted」nsert_L(W,b);〃直接将该货物放入仓库
qt=qt->next;
break;
}//switch}//while
while(qt){〃将货车中剩余的货物放入仓库
bqt->data;
List_Sorted」nsert_L(W,b);
qt=qt->next;
}
DestroyTruck(T);}//Input
4、出货操作的算法出货
voidOutput(WHouse& Truck& T){
〃将仓库中的货物装入货车,假设仓库中无货，记为缺货
pw= W;qw= W->next;//qw 指向第一个结点
qt=T;〃qt指向头结点
while(qt=qt->next)qt->data->num=-qt->data->num;
〃将货车的需要装入货物数据中的数量记为负值,表示从仓库中取出货物
qt= T->next;//qt指向第一个结点
while(qw&&qt){
a=qw->data;b=qt->data;
//a. b为货物数据假设干个数据项(Item)组成。该线性表中的元素，常称为数据记录(DataRecord), 简称记录，它是数据处理领域组织数据的基本单位。

皿号
W时间
起3(市
就班K价
果价折扣
是利It

1001
830-10X)0
法商一5
7«
防
否

1002
930-11 40
格鬲一北京
630
六折

1003
900-1130
广州一种南
1590
五折
否

!004
800-1000
济1H 一或都
I刈
八折
否

•

图2.1航班信息表
在日常生活中，学生学籍表、职工档案表、图书馆书目表、医院病历表、库存账 目表等都可称为线性表。对于线性表，我们可以按照需求来增加或缩减它的长度, 即进行插入或删除操作，也可以对表中的元素进行查找或访问等操作。
2 .线性表抽象类型定义线性表的抽象数据类型定义如下：
ADTList{
数据对象：D={ai|aiGEIemSet,i=lz2z...,nzn>0}
数据关系：Rl={|ai-l,aiGD,i=2,...,n)
基本操作：
CreatList(&L)操作结果：生成一个空的线性表L。
ListLength(L)
初始条件：线性表L已存在。
操作结果：返回L中数据元素个数。
ListInsert(&L,i,e)
初始条件：线性表L已存在，lWWListLength(L)+l。
操作结果：在L中第i个位置之前插入新的数据元素e, L的长度加1。
ListDelete(&L,i,&e)
初始条件：线性表L已存在且非空，lWWListLength(L)。
操作结果：删除L的第i个数据元素，并用e返回其值，L的长度减1。
GetElem(L,i,&e)
初始条件：线性表L已存在，lWiWListLength(L)。
操作结果：用e返回L中第i个数据元素的值。
LocateElem(L,e,compare())
初始条件：线性表L已存在，compare。是数据元素判定函数。
操作结果：返回L中第1个与e满足关系compare。的数据元素的位序。假设 这样的数据元素不存在，那么返回值为0。
ListEmpty(L)
初始条件：线性表L已存在。
操作结果：假设L为空表，那么返回TRUE否那么返回FALSE。
ClearList(&L)
初始条件：线性表L已存在。
switch(cmp(a,b)){〃通过比拟决定是否将货物装入货车
case-l:〃qw数据中的种类小于qt数据中的种类
pw=qw;qw=qw->next;break;
caseO:〃qw数据中的种类与qt数据中的种类相同
sum=a. num+b. num;
if(sum!=O. 0){qw->data. num=sum;pw=qw;w=qw->next;}
〃修改仓库中该货物数据
else{pw- > next=qw-> next;〃删除 qw 结点
free(qw);〃完成删除元素操作qw=pw->next
}
qt=qt->next;
break;
easel:
〃qw数据中种类大于qt中的种类,即仓库中没有该种类的货物
List_Sorted」nsert_L(W/b);〃记为缺货
qt=qt->next;
break;
}//switch
}//while
while(qt){〃将仓库中没有的货物记为缺货
b=qt->data;
List_Sorted_Insert_L(Wfb);
qt=qt->next;
)}//Output
仓库的出货和入货时,主要操作为顺序访问线性链表结点,对数据元素进行比 较并处理,最后将货车线性链表中的剩余元素插入到仓库链表中,访问的频数和 线性链表的长度成正比,时间复杂度为
操作结果：将L重置为空表。
DestroyList(&L)
初始条件：线性表L已存在。
操作结果：销毁线性表L。
}ADTList
对于以上定义的抽象数据类型线性表，除了对其进行的基本操作外，还可进行 一些更复杂的操作。如：对线性表进行排序；在一个有序的线性表中插入元素； 将两个或两个以上有序的线性表归并成为一个有序的线性表等。这些复杂的操作 可建立在基本操作的基础上完成，即它们可通过调用基本操作来实现。假设操作环 境或操作要求发生变化(例如，存储结构的变化)，只需要修改基本操作的实现 算法，而通过调用基本操作实现的其它算法那么不必修改或只做很少的修改，这在 一定程度上可以到达软件模块复用的目的。
第二节线性表的顺序表示和实现顺序存储结构是线性表存储结构的选择之一。当线性表很少涉及插入和删除操作 时，优先选择顺序结构表示线性表。
工、顺序表数据类型定义顺序表数据类型定义
线性表的顺序表示是利用一组地址连续的内存空间依次存储线性表的各个数 据元素，即以元素在计算机内''物理位置相邻〃来表示线性表中数据元素之间的逻 辑关系。因为顺序存储结构是一种随机存取的存储结构，所以通常利用C语言中 动态分配的一组连续的存储单元作为顺序存储结构所需要的存储空间。首先定义 一个指针表示存储空间的基地址，为了保存线性表的长度需要定义一个整型变量, 此外为了指示顺序表当前分配的存储空间大小还需要定义一个整型变量，即当前 线性表的最大容量。所需要的具体数据类型描述如下：
#defineMAXLEN100
#defineLIST」NCREASE10 〃线性表存储空间的动态分配增量
typedefstruct{
日emType*list; 〃线性表的存储空间的基地址intlength; 〃线性表的当前长度 intmaxsize; 〃线性袤当前分配的存储容量
}List_Sq;
结构标美型List_Sq用于实现线性表的动态分配顺序存储结构。由于存储空间 为动态分配，在对线性表进行插入等操作时，假设原有的存储空间已满而不能满足 进一步操作，可进行空间再分配，存储空间的增加量用LIST_INCREASE表示。 下面我们将给出各种典型的线性表操作的算法。
2、顺序表的生成算法生成线性表
线性表的生成算法主要是为其准备所需要的存储空间(这可通过malloc函数动 态申请空间实现)，同时为参数L的成员L.list、L.lengths L.maxsize赋以相应 的值。
StatusCreatList_S(List_Sq&L){
〃构造一个空的线屉表L
LJist=(ElemType*)malloc(MAXLEN*sizeof(ElemType));
if(!L.list)exit(OVERFLOW);〃假设存储空间分配失败，那么退出程序
L.length=0;〃初始化表的长度为0
L.maxsize=MAXLEN; 〃初始化表的存储容量
returnOK; 〃初始化成功}//CreatList_S
算法5-1线性表的生成算法3、返回线性表中第i个元素值的算法
返回线性表中第i个元素值的算法
在顺序存储线性表的连续单元中，第i个元素位于地址从LJist向后偏移i-1的 位置上(或处于L.list为基地址的连续单元中，下标为i-l的位置上)，我们可 直接通过下标返回该元素的值。本算法的时间复杂度为0(1)。
StatusGetElem_S(List_SqL,inti,ElemType&e){
if(i< 111i>L.Iength)returnERROR;//^ i 为无效值,返回错误
e=L.list[i-l];〃通过参数e返回第i个元素值 returnOK;}//GetElem_S
算法2-2返回线性表中第i个元素的值4、线性表的插入算法
在线性表的第i个位置插入元素
该操作是指在线性表的第i个位置之前插入新的数据元素，插入后线性表的长 度增加1个单位，插入的元素分别与原线性表的第i-1个元素、第i个元素在逻 辑上是相邻的关系。由于顺序存储结构是通过元素之间存储位置的关系来反映逻 辑关系，为了完成插入操作，满足插入元素与其前驱元素、后继元素之间的相邻 关系，我们需要把原线性表第i个到第n个元素依次向后移动一个单位。如图2.2 所示，在第4个和第5个元素之间插入元素，需要将第5个到第7个元素依次向 后移动一个单位。
StatusListInsert_S(List_Sq&L,inti,ElemTypee){
|i>L』ength+l)retu「nERROR;〃假设 i 为主效值，返回错误 if(L」ength==L.maxsize){〃假设存储容量已满,那么增加分配空间 newbase=(ElemType*)realloc(L.list,(L.maxsize+LIST_INCREASE)*sizeof(ElemType));
if(!newbase)exit(OVERFLOW);〃假设增加分配空间失败，退出程序
L.list=newbase; 〃新基址
L.maxsize+=LIST_INCREASE;〃 存储容量增力口
}//if
q=&(L.list[i-l]);〃插