第二章线性表1.教学目标通过线性表的学习，熟悉本书对每种数据结构的描述方法，掌握线性表的定义、特点、典型算法及实际中的实用。2.教学要
求①了解线性表的逻辑结构特性。②熟练掌握线性表的两种存储结构的描述方法。③熟练掌握线性表在顺序存储结构上基本操作的实现④熟练掌握线
性表在各种链式存储结构上基本操作的实现；⑤能够从时间和空间复杂度的角度比较线性表两种存储结构的特点3．教学重点：①线性表顺序存储结
构的特点及基本操作。②线性表链式存储结构的特点及基本操作。4．教学难点：①链表的概念。②链式存储结构上算法的实现。2.1线性表的
定义及逻辑结构2.1.1线性表的定义十二属相歌：“小老鼠打头来，牛把蹄儿抬；老虎回头一声吼，兔儿跳得快；龙和蛇尾巴甩，马羊步儿
迈；小猴机灵蹦又跳，鸡唱天下白；狗儿跳猪儿叫，请把顺序排!”线性表——是n个相同类型数据元素组成的有限序列。记作：（a1
,a2,…，ai-1，ai，ai+1，…，an）其中a1称作起始结点，an称作终端结点。i称为ai在线性表中的位置或序
号。n为表长，n=0时，称为空表。举例例1、26个英文字母组成的字母表（A，B，C、…、Z）例2、某学院从2008年到2013
年拥有的学生人数的变化情况表：(800，1000，2000，3600，3800，4500)例3、在校学生的健康信息表是一个线性
表，表中每个学生的信息由学号、姓名、性别、年龄、班级和健康状况等组成学号姓名性别年龄班级健康状况1204101钱
小明男19计科12健康1204108周维男18计科12一般1204111杨丽女20计科12健康1204112赵武男23
计科12差………………1204135张丽女17计科12一般线性表——是n个相同类型数据元素组成的有限序列。记作：（a1,
a2,…，ai-1，ai，ai+1，…，an）其中a1称作起始结点，an称作终端结点。i称为ai在线性表中的位置或序号
。n为表长，n=0时，称为空表。表中相邻元素间存在着顺序关系，对于任一对相邻结点ai称为ai+1的前驱，a
i+1称为ai的后继线性表的特点：线性表由同一类型的数据元素组成，每个ai必须属于同一数据类型线性表中的数据元素个数是有限的，表长
就是表中数据元素的个数存在唯一的“第一个”数据元素；存在唯一的“最后一个”数据元素除第一个数据元素外，每个数据元素均有且只有一个前
驱元素除最后一个数据元素外，每个数据元素均有且只有一个后继元素案例引入Pn(x)?=?p0?+?p1x?+?p2x2?+?…?+?
pnxn线性表P?=?(p0,p1,p2,…,pn)数组表示（每一项的指数i隐含在其系数pi的序号中）P(x)?=?10?+?5x
?-?4x2?+?3x3?+?2x4指数（下标i）01234系数p[i]105-432一元多项式的运算案例引入稀疏多项式的运算多
项式非零项的数组表示（a）A(x)?=?7?+?3x?+?9x8?+?5x17（b）(x)?=?8x?+?22x7???9x8下
标i0123下标i012系数a[i]7395系数b[i]822-9指数01817指数178创建一个新数组c分别从头遍历比较a和b的
每一项指数相同，对应系数相加，若其和不为零，则在c中增加一个新项指数不相同，则将指数较小的项复制到c中一个多项式已遍历完毕时，将另
一个剩余项依次复制到c中即可papb链式存储结构顺序存储结构存在问题存储空间分配不灵活运算的空间复杂度高多项式非零项的数组表示A1
7(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8A-1703198517B-181227-98多项式相加多项
式非零项的数组表示A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8paA-1703198517B-181
227-98pb多项式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8pa-17011198517-
181227-98pb多项式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8pa-170111985
17-181227-98pb多项式相加A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8pa-170111
98517-181227-98pb图书信息管理系统（1）查找（2）插入（3）删除（4）修改（5）排序（6）计数图书顺序表图书链表总
结线性表中数据元素的类型可以为简单类型，也可以为复杂类型。许多实际应用问题所涉的基本操作有很大相似性，不应为每个具体应用单独编写一
个程序。从具体应用中抽象出共性的逻辑结构和基本操作（抽象数据类型），然后实现其存储结构和基本操作。2.1.2线性表的基本操作
(1)初始化InitList(L)//构造一个空的线性表(2)线性表判空EmptyList(L)//为空返回真值，否则
返回假值(3)求长度LengthList(L)(4)取元素函数GetList(L,i)(5)按值查找LocatLi
st(L,x)(6)插入操作InsertList(L,i,x)(7)删除操作DeleteList(L,i)2
.1.2线性表的基本操作续DestroyList(&L)//销毁一个已存在的线性表ClearList（
&L）//清空线性表中的内容PriorElem（L，cur_e,&pre_e）//返回cur_e元素前一个元素的
值NextElem（L，cur_e,&next_e）//返回cur_e下一个元素的值ListDelete_data(&L,e,
order)//删除元素e，order决定删除一个，还是全部。Connect_two_List(L_a,L_b,&
L_c)//连接两个线性表，除去重复的内容print(L)//打印线性表2.2线性表的顺序存储结构2.2.1顺
序表线性表的顺序存储结构是指在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素，元素之间的逻辑关系通过存储位置来反
映，用这种存储形式存储的线性表称其为顺序表。设a1的存储地址为Loc(a1)，每个数据元素占L个存储单元，则第i个数据元素的地址
为：Loc(ai)=Loc(a1)+(i-1)×L1≤i≤n按数据元素的序号随机存取线性表的顺序存储结构可用C语言
定义如下：#defineMAXSIZE100typedefstructLinear_list{datatype
elem[MAXSIZE]; intlast;}SeqList;存放数据元素线性表中最后一个元素在数组中的位置Se
qListL;顺序存储结构三个重要属性：存储数据元素的空间：数组elem，用于存放数据元素。线性表的最大容量：MAXSI
ZE。线性表当前长度：由last+1确定，last：最后一个数据元素在数组中的下标。强调两个问题：“数组的长度”和“线性表的长
度”是两个概念：前者不变，后者可变注意区分数据元素的位序和数组的下标。SeqListL;SeqListL；表长：L
.last+1数据元素：L.elem[0]~L.elem[L.last]。表长：（L）.last+1或L->last+1数据
元素：L->elem[0]~L->elem[L->last]2.2.2顺序表上插入与删除操作的实现1初始化SeqLis
tInitList(){SeqListL;L=(SeqList)malloc(sizeof(SeqList
));L->last=-1;returnL;}主函数对初始化函数的调用如下：main(){SeqListL
;L=InitList();……}补充：C语言的动态分配函数（）sizeof(x)free(p
)malloc(m)释放指针p所指变量的存储空间，即彻底删除一个变量开辟m字节长度的地址空间，并返回这段空间的首地址计算变量x的长
度。2按值查找intLocatList(SeqListL,datatypex){inti=0;while(
i<=L->last&&L->elem[i]!=x)i++;if(i>L->last)return-1;
elsereturni;/返回的是存储位置/}本算法的主要运算是比较。平均比较次数为(n+1)/2，时间复杂度为
O(n)。3插入运算线性表的插入是指在表的第i个位置上插入一个值为x的新元素,i的取值范围为1≤i≤n+1。步骤：①将ai
～an顺序向下移动，为新元素让出位置；②将x置入空出的第i个位置；③修改last指针（相当于修改表长），使之仍指向最后一个
元素。插入运算1234567892512478936142512478936142512478936142512478936142
5124799893614算法实现：算法设计时请注意：1intInsertList(SeqListLp,inti
,datatypex)2{intj;3if(Lp->last==MAXSIZE-1)4
{printf(″表满″);5return(-1);6}
if(i<1||i>Lp->last+2){printf(″位置错″);9retur
n(0);10}for(j=Lp->last;j>=i-1;j--)Lp->elem[j+1]=
Lp->elem[j];13Lp->elem[i-1]=x; /新元素插入/14Lp-
>last++; /last仍指向最后元素/15return(1);
/插入成功，返回/16}在表满的情况下不能再做插入检验插入位置的有效性：1≤i≤n+1注意数据的移动方向时间
性能分析：在顺序表中插入一个数据元素时，其时间主要耗费在移动数据元素上。在第i个位置上插入x，从ai到an都要向下移动一个位
置，共需要移动n-i+1个元素，而i的取值范围为1≤i≤n+1，即有n+1个位置可以插入。设在第i个位置上插入元素的概率为Pi，则
平均移动数据元素的次数为假设在每个位置插入元素的概率相等，即Pi?=?1/(n+1)，则说明在顺序表上作插入运算平均需要移动表中一
半的数据元素时间复杂度为：O（n）4.删除操作指将表中第i个元素从线性表中去掉,i的取值范围为:1≤i≤n①将ai+1～an
顺序向上移动。步骤：②修改last指针使之仍指向最后一个元素。删除运算1234567892512478936142512473
61425124736142512473614删除注意：算法描述①当表空时不能做删除，否则产生下溢错误。②要检查删除位置的有
效性1≤i≤n。③删除ai之后，该数据已不存在，如果需要，先取出ai，再做删除。④注意数据的移动方向。①判断删除位置i
是否合法（合法值为1≤i≤n）。②将欲删除的元素保留在e中。（可选）③将第i+1至第n位的元素依次向前移动一个位置。④表长
减1，删除成功返回OK。注意：算法如下：①当表空时不能做删除，否则产生下溢错误。②要检查删除位置的有效性1≤i≤n。③删除
ai之后，该数据已不存在，如果需要，先取出ai，再做删除。④注意数据的移动方向。1intDeleteList(Seq
ListLp,inti)2{intj;if(i<1||i>Lp->last+1){pri
ntf(″不存在第i个元素″);5return(0);6}7f
or(j=i;j<=Lp->last;j++)Lp->elem[j-1]=Lp->elem[j]; Lp->last
--;10return(1); /删除成功/11}/检查删除位置的合法性
//向上移动//删除成功/算法性能分析：删除算法的时间性能分析：与插入运算相同，其时间主要消耗在移动表中元素上，删除第
i个元素时，其后面的元素ai+1～an都要向上移动一个位置，共移动了n-i个元素，所以平均移动数据元素的次数：等概率情况下，Ｐi
＝1/n则平均移动数据元素的次数为时间复杂度为：O（n）线性表顺序表示的优缺点对比优点缺点无需为表示结点间的逻
辑关系而增加额外的存储空间可方便地随机存取表中的任一元素插入或删除需要移动大量的数据元素当线性表长度变化较大时难以确定存储空间的
容量造成存储空间浪费并Union差交Intersection2.2.3顺序表应用举例例2-4利用两个线性表La和Lb分
别表示两个集合A和B，现要求一个新的集合A?=?A∪B。假设集合中的数据元素属于整型数据。算法思路：扩大线性表La，将存在于线性
表Lb中而不在La中的数据元素加入到线性表La中。逐一取出Lb中的元素，判断是否在La中，若不在，则插入。由于La是集合，数据元素
之间没有顺序关系，所以插入时，可以插入到La的最后一个元素后面，这样，就不用移动大量数据元素。A=(23,45,78,91,
55)B=(47,23,8,55)A∪B=(23,45,78,91,55,47,8)存储结构即为2.2.1节中的S
eqList；其中datatype定义为int。A∪B=A+(B?A)算法如下：1voidunin(SeqLi
stLa,SeqListLb)2{inti,j,La_len,Lb_len;3data
typee;4La_len=La->last;5Lb_len=Lb->last;6
for(i=0;i<=Lb_len;i++)7{e=lb.elem[i];8j
=0;9while(j<=La_len&&e!=la->elem[j])j++;10if(j>La
_len) 11if(La_lenLa->elem[++(la->last)]=e; /插入到La的最后/13}14}un
ion在la中查找e元素la中不存在和e相同的元素，则插入之语句6循环次数是Lb的表长，语句9循环次数最多是La的表长，所以，
此算法的时间复杂度为O(ListLength(La)?×?ListLength(Lb))。例2-5有顺序表A和B，其元素均按从
小到大的升序排列，编写一个算法将它们合并成一个顺序表C，要求C的元素也是从小到大的升序排列。例如A?=?(2,2,3),B?
=?(1,3,3,4)，则C?=?(1,2,2,3,3,3,4)。算法思路：依次扫描A和B的元素，比较当前的
元素的值，将较小值的元素赋给C，如此直到一个线性表扫描完毕，然后将未完的那个顺序表中余下部分赋给C即可。C的容量要能够容纳A、B两
个线性表。设表C是一个空表，设两个指针i、j分别指向表A和B中的元素，若A.elem[i]?>?B.elem[j]，则将B.ele
m[j]插入到表C中；若A.elem[i]≤B.elem[j]，则当前先将A.elem[i]插入到表C中，如此进行下去，直到其中一
个表被扫描完毕，然后再将未扫描完的表中剩余的所有元素放到表C中。1voidmerge(SeqListA,SeqLis
tB,SeqListC)2{inti,j,k;3i=0;j=0;k=0;4
while(i<=A.last&&j<=B.last) /A表、B表都不为空/5
if(A.elem[i]<=B.elem[j])6C->elem[k++]=A.elem[i++];
/将A表中i指针指向记录插入到C中/7else8C->elem[k+
+]=B.elem[j++];/将B表中i指针指向记录插入到C中/9while(i<=A.last)
/将A表剩余部分插入到C中/10C->elem[k++]=A.elem[i
++];11while(j<=B.last) /将B表剩余部分插入到C中/12C->e
lem[k++]=B.elem[j++];13C->last=k-1;14}包含有三个并列的循环，语句4～语句8
循环次数为表A的长度或者表B的长度，语句9～语句12是两个并列的循环，这两个中只有可能做一个，循环次数为表A或表B剩余的部分。因此
，该算法的时间复杂度是O(A.last?+?B.last)。习题：将顺序表(a1，a2，...，an)重新排列为以a1为界
的两部分：a1前面的值均比a1小，a1后面的值均比a1大（这里假设数据元素的类型具有可比性，不妨设为整型）。这一操作称为划分，a1
也称为基准。划分前23456103576185620划分后20186102376355645线性表顺序表示的优点：①无需为表
示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻的）；②可方便地随机存取表中的任一元素。
线性表顺序表示的缺点：①插入或删除运算不方便，除表尾位置外，在其它位置上进行插入或删除操作都必须移动大量的数据元素，其效率较低；
②由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确定合适的存储规模。数据域指针域d
atanext2.3线性表的链式存储2.3.1单链表用一组任意的存储单元来存储线性表中的数据元素。（a1,a2,…，
ai-1，ai，ai+1，…，an）数据域——用来存储结点的值；指针域——用来存储数据元素的直接后继的地址;…Ha2a1an^通
常，我们关心的是结点间的逻辑结构，而对每个结点的实际地址并不关心，所以通常单链表用下图所示的形式表示。1)链表每个结点只有一个指
针域，这种链表又称为单链表。2)单链表第一个结点无前趋，设一个头指针H指向第一个结点。3)表中最后一个结点没有直接后继，则最后
一个结点的指针域为“空”（NULL）。H∧a2a1…Han∧单链表的存储结构描述用C语言如下：typedefstructnod
e{datatypedata;structnodenext;}LNode，LinkList；通常我们用头
指针来标识一个单链表，如单链表L、单链表H等，是指某链表的第一个结点的地址放在了指针变量L或H中，头指针为NULL，则表示一个空表
，即H==NULL为真。定义结构体变量：LinkListH；H是一个结构体指针，即单链表的头指针通常在线性链表的第一结点之前附
设一个称为头结点的结点。H->next==NULL（带头结点）对于带头结点的单链表若定义LinkListp;且p=H-
>next那么p->data=a1p->next->data=a2其余依此类推。头指针和头结点的异同头指针头
结点指向第一个结点的指针，若链表有头结点，则是指向头结点的指针具有标示作用，常用头指针作为链表的名字放在第一个元素之前，其
数据域一般无意义(也可以放链表的长度)有了头结点，在第一个元素结点之前插入和删除第一个结点，其操作与其他结点的操作就统一了造成存储
空间浪费不带头结点的链表和带头结点的链表的区别不带头结点带头结点链表为空：L==NULL为真链表的第一个数据元素由L指向
在第一个元素之前插入一个元素和删除第一个元素要单独处理，和在其他位置插入、删除操作不同链表为空：L->next==NULL为真链表
的第一个数据元素由L->next指向插入、删除操作统一H∧2.3.2单链表上的基本运算1.初始化如果malloc分配空间失败
，返回的是NULL指针，于是h=NULL,返回falseLinkListInitList(LinkListh){if(
(h=(LinkList)malloc(sizeof(LNode)))==NULL)return(0);(h)->ne
xt=NULL;return(1);}初始化操作即建立一个空表。１头插法２尾插法逆序创建链表顺序创建链表2.3.2单链
表上的基本运算1建立单链表建立过程是一个动态生成的过程，即从“空表”起，依次建立结点，并逐个插入链表1）用头插法建立单链表的
算法Step0:Step1:Step2:Step3:建立只有头结点的单链表申请一块空间，s指向将L->next的值赋给
s->next将L->next的值改为s在链表的头部插入，读入数据的顺序和线性表的逻辑顺序是相反的单链表的建立（头插法）从一个空
表开始，重复读入数据：生成新结点将读入数据存放到新结点的数据域中将该新结点插入到链表的前端1LinklistCreate
FromHead()2{LinkListL;3LNodes;4char
c;5intflag=1;/设置一个标识变量flag，初值为1，当输入“$”时，将flag置为0，建表结束
/6L=(Linklist)malloc(sizeof(LNode));/为头结点分配存储空间/7L
->next=NULL;8while(flag)9{c=getchar();10
if(c!=''$'')11{s=(Linklist)malloc(sizeof(LNode)
);/为读入的字符分配存储空间/12s->data=c;/数据域赋值/13
s->next=L->next;/将s插入到链表中第一个数据元素之前/14L->next=
s;15}16else17flag=0;/读入符号为“$”，
修改结束标识/18}19returnL;20}2）尾插法建表算法中必须维持一个始终
指向已建立的链表表尾的指针。单链表的建立（尾插法）从一个空表L开始，将新结点逐个插入到链表的尾部，尾指针r指向链表的尾结点。初始时
，r同L均指向头结点。每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r指向新结点。1LinklistCre
ateFromHead()2{LinkListL;3LNodes;4ch
arc;5intflag=1;6L=(Linklist)malloc(sizeof(LNode
)); /为头结点分配存储空间/7L->next=NULL; /建带头结点的空链
表/8r=L; /尾指针r指向表尾/9while(fl
ag)10{c=getchar();11if(c!=''$'')12
{s=(Linklist)malloc(sizeof(LNode));/为读入的字符分配存储空间/13
s->data=c; /数据域赋值/14r->next=s
; /插入到表尾/15r=s;/r指向新的表尾结点s/16
}17else18{flag=0;19r->nex
t=NULL;20}21}22returnL;23}２.求链表长度的
操作求单链表的长度可以采用“数”结点的方法，从第一个元素开始“数”，一直“数”到最后一个结点(p->next=NULL)，就可
求得单链表的长度。pintListLength(LinkListL){3LinkListp;
4p=L;j=0;while(p->next!=NULL)7{8
p=p->next;9j++;10}11r
eturnj;12}j=0pj=1pj=n３.查找1)按序号查找（求线性表中的第ｉ个元素的运算）要查找表中第i
个结点，该如何做？需要从单链表的头指针L出发，开始顺着链域，一个接一个找，直到找到第ｉ个结点。提问：单链表像顺序表那样实现随机存取
吗？LL212118183030757542425656∧∧pppi=3j0pi=3j3按位查找算法实现如下：LinkListG
etlist(LinkListL,inti){intj；LNodep；p=L；j=0；
while(p->next!=NULL&&jnext；j++；}if（i==j）retur
np；elsereturnNULL；}从头结点开始扫描计数器找到了第i个结点这个算法的基本操作是移动指针，移动的次数最
大值和线性表的表长相当。时间复杂度：O(n)2)按值查找要查找结点值等于给定值的结点算法描述：查找过程从单链表的头指针指向的头
结点出发，顺着链表逐个将结点的值和给定值e作比较。若找到，返回找到的值为e的结点的存储位置，否则，返回空。算法实现如下：1
LinkListLocate(LinkListL,chare)2{LinkListp;3
p=L->next;/从表中第一个结点比较/4while(p!=NULL&&p->data!=e)5
p=p->next;6returnp;7}由于线性链表失去了随机存取的特性，所以按序号查找算法
、按值查找算法的时间复杂度均为O(n)。４.单链表插入操作分析：当用指针指示后继元素时，实现关系的改变只需要修改指针即可算法描述
：首先在单链表中找到第i-1个结点，然后申请一个新的结点，使它的指针域指向原第i个结点。s=(LinkList)malloc(s
izeof(Node));s->data=e;s->next=p->next;p->next=s;s=(LinkL
ist)malloc(sizeof(Node));s->data=e;s->next=p->next;p->next=s
;（1）找到ai-1存储位置p（2）生成一个新结点s（3）将新结点s的数据域置为x（4）新结点s的指针域指向结点ai（
5）令结点p的指针域指向新结点s1intInsList(LinkListL,inti,chare)2{
/在带头结点的单链表L中第i个位置插入值为e的新结点/3LinkListpre,s;4intk
;5pre=L;k=0;6while(pre!=NULL&&k第i-1个数据元素的存储位置/7{pre=pre->next;8k=k+1;
9}10if(k!=i-1) /插入位置不合理/11{pri
ntf(″插入位置不合理!″);12returnERROR;13}14
s=(LinkList)malloc(sizeof(LNode));/为e申请一个新的结点并由s指向它/15
s->data=e; /将待插入结点的值e赋给s的数据域/16
s->next=pre->next; /完成插入操作/17pre->next=s;
18returnOK;19}５.删除和插入类似，删除操作改变了元素之间的关系，因此需要修改元素所在
结点的指针。基本思想与插入相同，需要找到前驱结点。r=p->next;p->next=p->next->next;e=r
->data;free(r);注意：删除的是前驱结点的next结点，因此不仅要求结点的前驱存在，而且要求被删除的结点在链表中确
实存在（1）找到ai-1存储位置p（2）临时保存结点ai的地址在r中，以备释放（3）令p->next指向ai的直接后继结点（4）将
ai的值保留在e中（5）释放ai的空间1intDelList(LinkListL,inti,chare)2
{/在带头结点的单链表L中删除第i个元素/3LinkListp,r;4intk;5
pre=L;k=0;6while(pre->next!=NULL&&k点i的前驱结点i-1/7{pre=pre->next;8k=k+1;9
}10if(k!=i-1)/while循环是因为p->next=NULL或i
<1而跳出的/11{printf(″删除结点的位置i不合理!″);12return
ERROR;13}14r=pre->next;15pre->next=pre->next->n
ext; /删除结点r/16e=r->data;/将删除的元素保存到变量e中/17free(
r); /释放被删除的结点所占的内存空间/18returnOK;19
}链表的运算时间效率分析链表的运算时间效率分析1.查找:因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度
为O(n)。2.插入和删除:因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)。但是，如果要在单链表中
进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为O(n)。说明：删除算法中的循环条件(pre->next!
?=?NULL&&k?+1个(n为当前单链表中数据元素的个数)。i=n+1是指在第n+1个位置前插入，即在单链表的末尾插入。而删除操作中删除的合法位置只
有n个，若使用与前插操作相同的循环条件，则会出现指针指空的情况，使删除操作失败。在线性链表中插入、删除元素虽然不需要移动数据元素
，但需要查找插入、删除的位置，所以时间复杂度仍然是Ｏ(n)。通过上面的基本操作我们得知：①在单链表上插入、删除一个结点，必须
知道其前驱结点。②单链表不具有按序号随机访问的特点，插入位置的查找只能从头指针开始一个一个顺序进行。从上述操作可以看到：链表中
结点所占的空间，是?动态分配总结：链式存储结构的特点在于？1动态分配存储空间，不需要事先估计表的长度。2单链表不具有按序号
随机访问的特点，顺序存取元素。3插入、删除操作不需要移动数据元素，只需修改指针域。必须知道其前驱结点。L…a…aa1niLa2
2.3.3循环单链表将单链表最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，
并称为循环链表。为了使某些操作实现起来方便，在循环单链表中也可设置一个头结点。这样，空循环链表仅由一个自成循环的头结点表示。
假设P指向链表最后一个结点。单链表：p->next==NULL为真。循环单链表：p->next==?L为真。判断链表是否
为空的条件：单链表：p!?=?L循环单链表：p->next!?=?L。对于单链表只能从头结点开始遍历整个链表，而对于循环单
链表则可以从表中任意结点开始遍历整个链表。对链表常做的操作是在表尾、表头进行时，用一个指向尾结点的指针R来标识，可以提高操作效率
。循环链表中没有明显的尾端如何避免死循环2.3.3循环单链表从循环链表中的任何一个结点的位置都可以找到其他所有结点，而单链
表做不到；说明循环条件：p!=NULL?p!=Lp->next!=NULL?p->next!=L例：有两个带头结点的循环单链表L
A、LB，编写一个算法，将两个循环单链表合并为一个循环单链表，其头指针为LA。算法步骤：1找到两个链表的尾，并分别由指针p、q指
向它们p=LA;q=LB;while(p->next!=LA)p=p->next;while(q
->next!=LB)q=q->next;2将第一个链表的尾与第二个表的第一个结点链接起来p->next=LB->n
ext;free(LB);3修改第二个表的尾Q，使它的链域指向第一个表的头结点。q->next=LA;算法实现如下：Li
nkListmerge--1(LinkListLA,LinkListLB){LNodep,q;p
=LA;q=LB;while(p->next!=LA)p=p->next;while(q-
>next!=LB)q=q->next;q->next=LA;p->next=LB->next;
free(LB);return(LA);}采用上面的方法，需要遍历链表，找到表尾，其执行时间是O(n)。如何查找开
始结点和终端结点？ai-1aiana1rear对循环链表，有时不给出头指针，而给出尾指针可以更方便的找到第一个和最后一个结
点说明开始结点：rear->next->next终端结点：rear两个用尾指针标识的循环单链表的连接1LinkList
merge2(LinkListR1,LinkListR2)2{3Nodep;4
p=R1->next;5R1->next=R2->next->next; 6free(R2->ne
xt);7R2->next=p;8returnR1;9}若在尾指针表示的单循环链表上实现，
则只需要修改指针，无需遍历，其执行时间是O(1)。约瑟夫问题著名犹太历史学家Josephus在罗马人占领乔塔帕特后39个犹
太人与Josephus及他的朋友躲到一个洞中39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式41个人排成一个圆圈，由
第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止然而Josephus和他的朋友并
不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏例如n=
8m=3约瑟夫问题的解法voidJosephus(intn,intm){Firster();//检验指
针指向第一个结点for(inti=0;i0;j”<点}2.3.4静态链表没有指针的编程语言，可以用数组替代指针，来描述链表数组的每个元素由data和cur两部分组成，其中
cur相当于链表的next指针，这种用数组描述的链表叫做静态链表，这种描述方法叫做游标实现法数组的第一个和最后一个元素做特殊处理，
不存数据。数组的第一个元素cur存放第一个备用元素（未被占用的元素）下标，而数组的最后一个元素cur存放第一个有值的元素下标，相当
于头结点作用。2.3.4静态链表借用一维数组来存储线性链表。定义一个较大的结构数组作为备用结点空间(即存储池)，每个结
点应包含两个域data域和next域，data域用来存放结点的数据信息，而next域不再是指针而是指示其后继结点在结构数组中的相对
位置(即数组下标)，通常称为游标。我们把用这种方式实现的单链表叫做静态链表(StaticLinkedList)。＃define
Maxsize=链表可能达到的最大长度typedefstruct{datatypedata;int
next;}Component,StaticList[Maxsize];StaticListS;intSL,
AV; /两个头指针变量/1.初始化设space为静态单链表的备用结点空间(即存储池)。StaticList
space;1voidinitial(intAV)2{3intk;4for(
k=0;k/6space[Maxsize-1].next=-1; /标记链尾/7AV=0;
/设置备用链表头指针初值/8}2.分配结点分配结点是从备用链表摘下一个结点空间分
配给待插入静态链表中的元素。1intgetnode(intAV)2{inti;3i
=AV;4AV=space[AV].next;5returni;6}3.
结点回收结点回收是将下标为k的空闲结点插入到备用链表AV中。1voidfreenode(intAV,in
tk)2{space[k].next=AV;3AV=k;4}4.前插操作
算法描述：(1)先从备用单链表上取一个可用的结点；(2)寻找第i-1个元素的位置。(3)修改游标域，实现插入。算法如
下：1voidinsbefore(inti,intSL,datatypex,intAV)2{/
AV为备用表/3intj,k,m;4if(i<1||i>ListLength(SL
)+1) /插入位置不合理/5{printf(″插入位置不合理!″);6r
eturnERROR;7}8else9{j=getnode(AV);/j为从
备用表中取到的可用结点空间的下标/10space[j].data=x;11k=sp
ace[SL].next;/k为静态单链表的第一个元素的下标值/12for(m=1;m++) /寻找第i-1个元素的位置k/13k=space[k.].next;14sp
ace[j].next=space[k].next; /修改游标域，实现插入操作/15space[k].next=j;
16}17}(A,B,D,E,F)在i=3的位置插入值C，插入后的线性表为（A,B,C,D,E,F）下标d
atanext下标datanextSL=004SL=0041E51E52B32B3->6修改游标Step23D13D14A24A2
5F-15F-1AV=6676C7->3修改游标Step178AV=77889899109101011101111-111-15.
删除(1)寻找第i-1个元素的位置，然后通过修改相应的游标域进行删除；(2)将被删除的结点空间连到可用静态单链表中，实
现回收。算法如下：1voiddelete(inti,intAv,intSL)2{intj,
k,m;3if(i<1||i>ListLength(SL))/删除位置不合理/4
{printf(″删除位置不合理!″);5returnERROR;6}7
else8{k=space[SL]->next; /k为静态单链表的第一个元素的下标值/9
for(m=1,mpace[k]->next;11j=space[k]->next;12space[k]->
next=space[j]->next;/从静态单链表中删除第i个元素/13freenode(AV,
j) /将第i个元素占据的空间回收，即将其连入备用表/14}15}线性表（A,B,E,C,D）
删除i=3位置的数据元素，删除后的线性表为（A,B,C,D）下标datanext下标datanextSL=004SL=0041C5
1C52B32B3->1①找到i-1元素的位置k3E1AV=33E1->7②free被删除的结点4A24A25D-15D-1AV=
66767787889899109101011101111-111-1前驱指针域数据域后继指针域proirdatanext2.3.
5双向链表在单链表的每个结点里再增加一个指向其前驱的指针域prior。这样形成的链表中就有两条方向不同的链，我们可称之为双
(向)链表(DoubleLinkedList)。双链表的结构定义如下:typedefstructDLnode{dat
atypedata;structDLnodeprior,next;}DLNode,DLinkList;Pa
i-1aiai+1由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点和直接后继结点变得非常方便。设指针p指向双链表
中某一结点，则有下式成立：p->prior->next=p=p->next->prior如图所示：eS1.双向链表的
插入操作在ai结点后插入值为e的新结点Paiai+1s->next=p->next;p->next->prio
r=s;p->next=s;s->prior=p;图2.16双向链表插入操作算法实现：intDlinkIns(
DoubleListL,inti,ElemTypee)先检查待插入的位置i是否合法，若位置i合法，则让指针p指向它
{…………DNodes,p;s=(DNode)malloc(sizeof(DNode));if
(s){s->data=e;s->next=p->next;p->next=s;s->next->prior
=s;s->prior=p;return1;}elsereturn0;}rPai2.双向链表的删除操
作删除ai结点算法描述：e=p->data;p->next=r->next;r->next->prior=p;fre
e(r);ai-1ai+1图2.17双向链表删除操作算法实现：intDlinkDel(DoubleListL,in
ti,ElemTypee){…………DNoder=p->next;e=p->data;p-
>next=r->next;r->next->prior=p;free(p);return1;}先检查待
插入的位置i是否合法，若位置i合法，则让指针p指向它【算法2.16双向链表的删除操作】例2.6如果以单链表表示集合，假设
集合A用单链表LA表示，集合B用单链表LB表示，设计算法求两个集合的差，即A-B。算法思想：由集合运算的规则可知，集合的差A-B
中包含所有属于集合A而不属于集合B的元素。具体做法是：对于集合A中的每个元素e，在集合B的链表LB中进行查找，若存在与e相同的元素
，则从LA中将其删除。pre=LA;p=LA->next;q=LB->next;while(q!=NULL&&q-
>data!=p->data)q=q->next;r=p;pre->next=p->next;p=p->n
ext;free(r);pre=p;p=p->next;算法步骤：1p指向LA中的某一结点，pre始终指向p的前驱
2依次扫描LB中结点，看是否有与LA中p的值相同的结点。若相同，则删除p结点若不相同，则p指向下个结点，重复步骤21
voidDifference(LinkListLA,LinkListLB)2{/此算法求两个集合的
差集/3LinkListpre,p,r;4pre=LA;p=LA->next;
/p指向LA表中的某一结点，而pre始终指向p的前驱/5while(p!=NULL)6{
q=LB->next;7while(q!=NULL&&q->data!=p->data)8q=q->next;9if(q!=NULL)10{r=p;11pre->next=p->next;12p=p->next;13free(r);14}15else16{pre=p;17p=p->next;18}19}/while(p!=NULL)/20}该算法的时间性能为O(m×n)。2.4顺序表和链表的比较顺序存储有三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。但它也有两个缺点：(1)在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。(2)需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。顺序表链表空间存储空间预先分配，会导致空间闲置或溢出现象动态分配，不会出现闲置或溢出现象存储密度不用为表示结点间的逻辑关系而增加额外的存储开销，存储密度等于1需要借助指针来体现元素间的逻辑关系，存储密度小于1时间存取元素随机存取，时间复杂度为O(1)顺序存取，时间复杂度为O(n)插入、删除平均移动约表中一半元素，时间复杂度为O(n)不需移动元素，确定插入、删除位置后，时间复杂度为O(1)适用情况①表长变化不大，且能事先确定变化的范围②很少进行插入或删除操作，经常按元素序号访问数据元素①长度变化较大②频繁进行插入或删除操作小结01掌握线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构（顺序表）和链式存储结构（链表）。OPTION02OPTION熟练掌握这两类存储结构的描述方法，掌握链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。小结熟练掌握顺序表的查找、插入和删除算法熟练掌握链表的查找、插入和删除算法能够从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合040503OPTIONOPTIONOPTION链表的优缺点恰好与顺序表相反。在实际中怎样选取存储结构呢？通常有以下几点考虑：1.基于空间的考虑在链表中的每个结点，除了数据域外，还要额外设置指针（或光标）域，从存储密度来讲，这是不经济的。存储密度=结点数据所占的存储量/结点结构所占的存储总量顺序表和链表的比较一般地，存储密度越大，存储空间的利用率就越高。显然，顺序表的存储密度为1，而链表的存储密度小于1。2.基于时间的考虑顺序表是一种随机存取结构，存取:O(1)链表中的结点，需从头指针起顺着链找才能取得。操作:查找、插入和删除3.基于环境的考虑顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。总之，两种存储结构各有长短，选择那一种由实际问题中的主要因素决定。通常“较稳定”的线性表选择顺序存储，而频繁做插入删除的即动态性较强的线性表宜选择链式存储。 |
|
