第二章线性表

第二章线性表简介：最简单、最常用的数据结构，线性表的顺序表示和实现线性表的链式表示和实现线性表的应用实例---

一元多项式的表示和运算重点：线性表的基本概念和术语线性表的顺序表示和链式表示方法及其上的基本操作相关算法的时间复杂度分析难点：线性表的链式表示和基本操作

线性结构的特点存在唯一的一个被称作"第一个"的数据元素；存在唯一的一个被称作"最后一个"的数据元素；相邻数据元素之间存在序偶关系，若将线性表记为（a1,a2,…,ai-1,ai,ai+1,…,an）表中ai-1领先于ai,称ai-1

是ai的直接前驱元素；

ai+1

是ai的直接后继元素。除第一个之外，线性表中的每个数据元素均只有一个直接前驱；除最后一个之外，线性表中每个数据元素均只有一个直接后继；2.1线性表类型定义线性表(LinearList):n个数据元素的有限序列。表长空表位序记录文件如:学生健康情况表：总之：线性表的数据元素可由若干数据项组成。同一线性表中的元素必定具有相同特性姓名学号性别年龄数学王小林790631男1898陈红790632女2078……..……..…….…….….关非790632女2078线性表的操作：例2-1需求：线性表LA和LB分别表示集合A和B，求A=A∪B。解决方案：把存在于LB且不存在于LA的元素插入LA。算法描述：

voidunion(List&La，ListLb) {La_len=ListLength(La);Lb_len=ListLength(Lb); for(i=1;i<=lb_len;i++) {

//①从Lb中依次取得每一个元素

//②与La的每一个元素比较

//③如不存在，则插入之

}}//union

voidunion(List&La，ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i<=lb_len;i++){

GetElem(Lb,i,e)

if(!LocateElem(La,e,equal);

ListInsert(La,++La_len,e);}}//union时间复杂度为O(ListLength(LA)×ListLength(LB))无序线性表合并的算法需求：线性表LA和LB的数据元素按值非递减有序，归并LA和LB为LC，LC元素仍按值非递减有序排列。解决方案:设指针i和j分别指向LA和LB的元素，比较i和j所指当前元素ai和bj，选min(ai,bj)插入为LC的元素算法框架：

voidMergeList(ListLa，ListLb，List&Lc){InitList(Lc);

La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=la_len)&&(j<=lb_len)){//①分别获取LA和LB的元素比较，将值小的插入LC}//②将LA或LB的剩余数据元素，插入LC中。

}//MergeList线性表应用：例2-2有序线性表合并的算法

voidMergeList(ListLa，ListLb，List&Lc){InitList(Lc);

La_len=ListLength(La);Lb_len=ListLength(Lb);while((i<=la_len)&&(j<=lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);

if(ai<=bj)//La中当前指针所指元素值较小

{ListInsert(Lc,++k,ai);++i;}//将La中当前指针所指元素插入Lc，指针后移一个位置

else{ListInsert(Lc,++k,bj);++j;}//将Lb中当前指针所指元素插入Lc，指针后移一个位置

}while(i<=La_len)//如果当前La中有剩余元素

{GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//获取La中元素直接插入Lcwhile(j<=Lb_len)

//如果当前Lb中有剩余元素

{GetElem(Lb,i++,bj);ListInsert(Lb,++k,bj);}

//获取Lb中元素直接插入Lc}//MergeList时间复杂度：O(ListLength(LA)+ListLength(LB))；2.2线性表的顺序表示和实现线性表的顺序表示：用一组地址连续的存储单元依次存储线性表的数据元素。特点:逻辑上相邻的数据元素在物理位置上相邻。线性表顺序存储结构是一种随机存取的存储结构 设线性表的每个元素占l个存储单元，LOC(a1)为线性表的起始地址，bb+l……b+(i-1)*l……b+(n-1)*l存储地址12…i…n位序内存状态an……ai……a2a1线性表顺序表示的实现线性表的顺序实现：动态分配的一维数组线性表的动态分配顺序存储结构#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量#defineLISTINCREMENT10//线性表存储空间的分配增量typedef

struct{Elemtype*elem;//存储空间的基地址。

intlength;//当前长度

int

listsize;

//当前分配的存储容量}Sqlist;基本操作的实现举例：InitList_Sq(Sqlist&L)顺序表的基本操作—插入线性表的插入操作：原线性表:(a1,…ai-1,ai,…,an)插入后:(a1,…ai-1,x,ai,…,an)

插入的情况有两种：

a、不移动元素：在表尾插入（i=n+1）

b、移动元素：在第i(1≤i≤n+1）个数据元素前插入需将第n个到第i个数据元素共

个依次向后移动一个位置。操作演示

1、在表中任意位置插入新的数据元素

2、表满情况下，在表尾插入新的数据元素n-i+1顺序表插入操作的时间复杂度分析在顺序表中某个位置插入元素的时间耗费移动元素移动元素的个数取决于插入元素位置。设pi是在第i个元素之前插入一个元素的概率，不失一般性，假定在线性表的任何位置上插入元素都是等概率的

在长度是n的线性表中插入一个元素时所需移动元素次数的数学期望值(平均次数)为

pi=1/(n+1)

线性表的插入算法的时间复杂度为O(n)

Eis=∑pi×(n-i+1)=n/2n+1i=1顺序表的基本操作—删除线性表的删除操作:删除前:(a1,…ai-1,ai,ai+1,…,an)删除后:(a1,…ai-1,ai+1,…,an)。删除的情况有两种：

a、不移动元素：在表尾删除i=nb、移动元素：删除第i（1≤i≤n）个数据元素需将第i+1到第n个数据元素共

个依次向前移动一个位置。操作演示

1、在非表尾删除n-i顺序表删除操作的时间复杂度分析

在顺序表中某个位置删除元素的时间耗费移动元素移动元素的个数取决于删除元素的位置。假设qi是删除第i个元素的概率，不失一般性，假定在线性表的任何位置上删除元素都是等概率的qi=1/n

在长度为n的线性表中删除一个元素时所需移动元素次数的数学期望值

线性表的删除算法的时间复杂度为O(n)。Edl=∑qi×(n-i)=(n-1)/2n+1i=1顺序表的归并无序顺序表归并算法：类似于算法2.1时间复杂度：O(ListLength(LA)×ListLength(LB))有序顺序表的归并算法：算法2.7时间复杂度：O(ListLength(LA)+ListLength(LB))总之，以线性表表示集合并进行集合的各种运算，应先对表中元素进行排序。顺序表小结特点：逻辑关系上相邻的两个元素在物理位置上也相邻优点：可以随机存取表中任一元素，它的存储位置可用一个简单、直观的公式表示。缺点：线性表在作插入和删除操作时，需要移动大量元素,浪费大量时间。线性表的顺序表示:动态分配的一维数组思考题：设顺序表va中数据元素递增有序，试写一算法，将x插入到顺序表中的适当位置，以保持该表的有序性。针对一个具体应用如何写程序认清具体问题的逻辑结构选定其存储结构具体实现声明你自定义的数据类型初始化一段存储空间用于存放你的数据对象构造一个有真实数据元素存在的写出针对问题的操作的具体实现写出主程序检查语法错误，编译、链接、执行、看结果修改程序的逻辑错误2.3线性表的链式表示和实现线性表链式表示（链表）的特点链表的结点结构和存储结构链表的基本操作取元素插入一个元素删除一个元素线性表的链式表示的特点特点：用一组任意的存储单元（可连续可不连续）存储线性表中的数据元素。线性表（a1，a2，a3，a4）(a)一段可用空间(b)经过一段运行的顺序表a1a2a3a4(c)经过一段运行的链表a3a2a4a1＾链表的结点结构线性单链表存储结构(C语言中结构指针来描述)typedef

struct

LNode{

ElemTypedata;//数据域

Struct

LNode*next;//指针域}LNode,*LinkList;线性表的链式表示的结点结构数据域指针域线性单链表线性单链表：n个结点(每个结点只包含一个指针域)链构成的链表。不带头结点的线性单链表a1a4^a2a3头指针LL判空条件：Ｌ==NULL首元结点尾元结点指示链表首元结点的存储位置线性单链表线性单链表：n个结点(每个结点只包含一个指针域)链构成的链表。带头结点的线性单链表a1a4^a2a3头指针L判空条件：Ｌnext==NULL首元结点尾元结点4^L指示链表头结点的存储位置头结点线性链表示例线性表(ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)的链式存储结构ZHAO^线性链表的逻辑状态QIANSUNLIZHOU存储地址数据域指针域1LI437QIAN1313SUN119WANGNULL25WU3731ZHAO737ZHENG1943ZHOU2531头指针HWUZHENGWANG^H在单链表中任何两个元素的存储位置没有固定的联系每个元素的存储位置可由其直接前驱结点的指针指出

GetElem_L(LinkList

L,int

i,ElemType&e)线性单链表的基本操作-取值a1pan^…nLaiai+1…在单链表中获取第i个数据元素必须从头指针出发，沿指针链依次向后查找。因此，单链表是顺序存取的存储结构。线性单链表的基本操作—插入插入前的表L：（a1,…,ai-1,ai,…,an)ListInsert(&L,i,e)GetElem(L,i-1,e)插入后的表L：（a1,…,ai-1,e,ai,…,an)

实现步骤：用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中线性单链表的基本操作—插入用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中a1an^ai-1aiL……线性单链表的基本操作—插入用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中a1an^ai-1aiL……p线性单链表的基本操作—插入用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中a1an^ai-1aiL……pes线性单链表的基本操作—插入用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中a1an^ai-1aiL……pes①①s->next=p->next;线性单链表的基本操作—插入用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中a1an^ai-1aiL……pes①s->next=p->next;②p->next=s;

②①线性单链表的基本操作—插入用指针p定位到第i-1个元素所在的结点生成一个数据域为e的结点，用指针s指向它将s所指结点插入到单链表中a1an^ai-1aiL……e①s->next=p->next;②p->next=s;

线性单链表的基本操作—删除删除前的表L：（a1,…,ai-1,ai,ai+1…,an)ListDelete(&L,i,&e)GetElem(L,i-1,e)删除后的表L：（a1,…,ai-1,ai+1,…,an)

实现步骤：用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间线性单链表的基本操作—删除a1an^ai-1aiL……ai+1用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间线性单链表的基本操作—删除pa1an^ai-1aiL……ai+1用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间线性单链表的基本操作—删除pqa1an^ai-1aiL……ai+1①q=p->next;①用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间线性单链表的基本操作—删除pq②p->next=q->next;②a1an^ai-1aiL……ai+1①q=p->next;①用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间线性单链表的基本操作—删除p③free(q);a1an^ai-1L……ai+1②p->next=q->next;①q=p->next;②用指针p定位到第i-1个元素所在的结点用指针q指向被删除结点修改p所指结点的指针域为其直接后继的直接后继释放被删结点所占空间线性单链表的基本操作—删除a1an^ai-1L……ai+1p③free(q);②p->next=q->next;①q=p->next;逆位序创建线性单链表特点：简单，生成的链表中结点的数据元素值次序和输入数据的顺序相反。实现：从空表开始，依次建立各元素结点，逐个插入单链表的头结点后。操作演示时间复杂度分析线性表的链式表示小结特点：用一组任意的存储单元（可以连续也可以不连续）存储线性表的数据元素。优点：实现插入和删除运算无须移动结点，仅需修改指针。缺点：由于是非随机存取的存储结构，某些操作如GetElem(&L,i,&e)、LocateElem(L,e,compare())等算法的复杂度较大。适用场合：频繁插入和删除，存储空间需求不定的应用。2.3.2循环链表循环链表(CircularLinkedList)：特点：将单链表的最后一个结点指针指向链表的表头结点，整个链表形成一个环。优点：从表中任一结点出发都可找到表中其他结点。操作：和线性链表基本一致，差别仅在于判空条件(b)循环链表的一般形式Lp(a)循环链表的空表形式p->next==L…Lpa0a1an2.3.2循环链表在带头结点的循环链表中设置头指针查找首元结点的时间复杂度是，由head指出查找尾元结点需从头遍历整个链表，时间复杂度是在带头结点的循环链表中设置尾指针查找首元结点的时间复杂度是查找尾元结点的时间复杂度是应用：两个循环链表合并rear->next->nextrear…heada0a1an…reara0a1anO(1)O(n)O(1)O(1)合并后的循环链表p=A->next;A->next=B->next->next;B->next=p;仅设尾指针的循环链表…Aa0a1an…Ba0a1anA…a0a1an…Ba0a1an循环链表的合并2.3.3双向链表线性单链表和循环链表的缺点寻找结点的直接后继，NextElem()的复杂度是O(1)。寻找结点的直接前驱，PriorElem()的复杂度是O(n)。双向链表:在单链表的每个结点里增加一个指向其直接前趋的指针域prior。双向链表C语言描述为：typedef

struct

DulNode{

ElemTypedata;

Struct

DulNode*prior;//指向其直接前驱的指针域

Struct

DulNode*next;//指向其直接后继的指针域}DulNode,*DuLinkList;双向链表结点结构和示意图结点结构：设指针p指向某一结点，则双向链表结构的对称性：

在双向链表中某些操作算法与线性单链表的操作相同；插入、删除等操作需同时修改两个方向的指针^^priornextL(a)空双向链表^a0a1……

an-1

^

L(b)非空的双向链表priordatanext(p—>prior)—>next=p=(p—>next)—>prior双向链表的基本操作举例在双向链表中插入一个结点生成一个结点空间，为数据域赋值完成插入在双向链表中删除一个结点找到被删除结点的前驱结点删除结点释放空间线性表实现方法的比较一、存储空间的分配方面：顺序存储开辟连续的，固定长度的存储空间。出现溢出情况时，不能动态扩充。链式存储中，结点的存储空间是通过malloc函数来动态分配，可以不连续，不存在溢出情况。

结论：事先能确定线性表的大致长度，应选择顺序存储方式，否则为了避免造成分配空间过大或过小，宜采用链式存储方式。线性表实现方法的比较二、操作方面：顺序存储，可以随机访问，经常访问线性表中元素的操作非常方便。但要进行插入和删除操作每次都会出现元素的大量移动。链式存储，只能顺序访问，访问链表中的任意元素时，必须都从第一个结点开始顺序查找。要进行插入和删除操作时，只需修改结点的指针域。

结论：如果线性表频繁地进行插入和删除操作，宜采用链式存储；若频繁访问线性表中元素，宜采用顺序存储。在实际中怎样选取存储结构的几点考虑：(1)基于存储的考虑

顺序表的存储空间是静态分配的，在程序执行之前必须明确规定“MAXSIZE”大小，估计过大，造成浪费，过小造成溢出。

链表不用事先估计存储规模，但链表的存储密度较低。

存储密度是指一个结点中数据元素所占的存储单元数和整个结点所占的存储单元之比。显然顺序表的存储密度为1，链式存储结构的存储密度小于１。在实际中怎样选取存储结构的几点考虑：(2)基于运算的考虑

如果对线性表的主要操作是查找，适宜采用顺序表结构。对于频繁进行插入和删除操作的线性表，适宜采用链表结构。(3)基于环境的考虑

顺序表的实现基于数组类型，链表的操作是基于指针。2.4一元多项式的表示一元多项式在计算机的表示：采取顺序存储结构，例：Pn(x)=p0+p1x+p2x2……+pnxn

可表示成P=(p0,p1,…,pn)

抽象数据类型一元多项式的定义和实现书40-42页优点：算法简洁缺点：在实现某些基本操作时不够方便，且浪费空间解决办法：用数据元素为(系数项，指数项)的线性表来表示一元多项式，称为多项式的非零项系数-指数对。例如:S(x)=1+3x109-5x231+6x354

可用((1,0),(3,109),(-5,231),(6,354))表示。

2.4一元多项式的实现一元多项式在计算机的实现：采取链式存储结构typedef

struct

{floatcoef;

int

expn;}term,ElemType;typedef

LinkListpolynomial;

一元多项式的相加两个多项式相加的运算规则（算法策略）：和多项式中结点从两个多项式链表中摘取，无须另生成。所有指数不同的项分别复抄到和多项式中。指数相同，对应系数相加，若和不为0则构成和多项式中一项两个多项式相加的算法：设qa和qb分别指向多项式A、B中当前进行比较的结点，则比较两个结点中指数项有三种情况：

①qa.expn<qb.expn，取qa所指结点插入和多项式链表。

②qa.expn=qb.expn，系数相加，若和为0，删除结点，释放qa和qb，若和不为0，修改qa系数值，释放qb③qa.expn>qb.expn，取qb所指结点插入和多项式链表中。算法2.23多项式加法:Pa=Pa+Pb的框架voidAddPolyn(polynomail&Pa,polynomail&Pb){ha=Pa;hb=Pb;qa=ha->next;qb=hb->next;

while(qa&&qb){ switch(cmp(qa->data.expn,qb->data.expn)){case–1:qa指针后移//(qa->expn<qb->expn)case0://(qa->expn==qb->expn) {if(qa->data.coef+qb->data.coef!=0)

qa->data.coef+=qb->data.coef; else//当系数和为0时

删除qa所指结点;}//if

删除qb所指结点，qa,qb指针均后移

case1:将qb所指结点插入Pa，qb指针后移

}}

if(qb)所指结点链入Pa;

free(Pb)}//addpolyn第二章知识结构图链表特点和实现插入和删除特点和实现线性表抽象类型定义顺序表应用归并逆置归并插入删除插入删除多项式相加多项式相乘单链表循环链表双链表归并第二章的类型题一、顺序及链式存储结构的概念及特点二、插入、删除算法性能分析三、单、双向链表的基本算法（插入/删除/判空）四、单链表逆置五、两个有序或无序线性表归并六、链表相邻结点交换算法应掌握的知识点类型题一、顺序及链式存储结构的概念及特点。1顺序存储方式只能用于存储线性结构。(对/错）2线性表是具有n个

的有限序列。3向长度为n的线性表中的第i个元素（1≤i≤n〉之前，插入一个元素时，需向后移动

个元素，删除第i个元素时，需向前移动

个元素。4表长为n的顺序存储的线性表，当在任何位置插入和删除一个元素概率相等时，插入一个元素所需移动元素的平均个数为

，删除一个元素需移动元素的平均个数为

。5顺序查找法适用于存储结构为顺序或链式存储的线性表。（对/错）应掌握的知识点类型题7线性表采用链表存储时结点和结点内部的存储空间可以不连续。(正确/错误)8若频繁地对一个线性表进行插入和删除操作，该线性表宜采用何种存储结构？为什么？二、算法性能分析2.1若长度为n的线性表采用顺序存储结构，在其第i（1≤i≤n+1）个位置插入一个新元素的算法的时间复杂度为

。三、单链表及双向链表的基本算法（插入、删除、判空）3.1将s所指结点加到p所指结点后，语句是

。应掌握的知识点类型题四、单链表逆置（原地、可构造新表、递归）4.1写一算法，在原链表上实现逆置。五、两个有序或无序线性表归并5.1将两个各有n个元素的有序表归并为一个有序表，其最少的比较次数为

。

5.2设两个按值递增的有序线性表A和B，编写算法将A和B归并成一个按元素值递减有序排列的线性表C，要求利用原表的结点空间存放C。六、链表相邻结点交换算法6.1有一个由正整数组成的无序单链表，编写算法完成：①找出最小值结点，打印它②若该数值是奇数，将它与直接后继结点的数值交换，若是偶数，将其直接后继结点删除③交换该结点（不是链表最后的结点）和其直接后继结点

……L…qpvoidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r; ②p->next=r->next; ③r->next=p; }六、链表相邻结点交换

……L…qprvoidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r; ②p->next=r->next; ③r->next=p; }六、链表相邻结点交换

……L…qpr①voidChangeListNode(LinkList

L,LNode*p){

r=p->next;

①q->next=r; ②p->next=r->next; ③r->next=p; }六、链表相邻结点交换

……L…qpr①②voidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r;

②p->next=r->next; ③r->next=p; }六、链表相邻结点交换

……L…qpr①②③voidChangeListNode(LinkList

L,LNode*p){

r=p->next; ①q->next=r; ②p->next=r->next;

③r->next=p;

}六、链表相邻结点交换上机语法错误上机调试逻辑错误正确结果成功=1%错误结果对象没有返回死循环无错误具体应用算法模型数据结构线性结构非线性结构存储表示顺序存储结构链式存储结构加法、乘法比较、移动定位（查找）写程序rundebugtoggleabreakpointaddwatchgotocursorstepintodeclarationsytaxerror、argumentlisterrortypemismatch、unexpectedfileend第二章作业讲评基本习题：2.1,2.2,2.3,2.4,2.5,2.6,2.7,2.8,2.9上机习题：2.11,2.19,2.22,2.24算法设计：2.11,2.12,2.19,2.21,2.22,2.242.11将x插入到递增有序的顺序表L中，插入后L仍然递增有序intInsertOrderList1(Sqlist&L,intx){if(L.length>=L.listsize){newbase=(int*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(int));if(!newbase) exit(OVERFLOW);

//分配不成功

L.elem=newbase;L.listsize+=LISTINCREMENT;}

p=&(L.elem[L.length-1]);//指向表尾元素位置

while(p>=&(L.elem[0])&&*p>x){*(p+1)=*p;--p;}*(p+1)=x; ++L.length;//完成插入，线性表长度增1returnOK;}InsertOrderList12.11将x插入到递增有序的顺序表L并保持L有序intInsertOrderList2(SqList&L,intx){

inti;

i=1;//数组下标从1开始

while((i<=L.length)&&(x>L.elem[i]))

i++;//查找i是插入位置

ListInsert_Sq(L,i,x);//插在第i个元素之前

returnOK;}//InsertOrderList22.12设A=（a1,……,am）,B=（b1,……,bn）均为顺序表，A’和B’分别是A和B中除去最大共同前缀后的子表，若A’和B’都是空表则A=B，若A’是空表，B’不空，或两者均不为空，且A’的首元小于B’的首元则A<B，否则A>B，写一个比较A、B大小的算法，注意在算法中不要破坏原表A和B，也不必求得A’,B’才进行比较。A=(x,y,y,z,x,z)B=(x,y,y,z,y,x,x,z)2.12

int

Compare_List(Sqlista,Sqlistb){//若a<b，返回-1；a=b，返回0；a>b，返回1while((i<=a.length-1)&&(i<=b.length-1)&&a.elem[i]==b.elem[i])){++i;}if(a.length==i&&b.length==i){ printf("A=B"); return0; }elseif((i==a.length&&i<=b.length-1)||(i<=a.length-1&&i<=b.length-1&&a.elem[i]<b.elem[i])){ printf("A<B"); return-1; }else{ printf("A>B"); return1; }}2.21顺序表的就地逆置算法思想：依靠下标变换来实现voidreverse1(Sqlist&A){

inttemp,i,j;for(i=0,j=A.length-1;i<=j;i++,j--) {

}}//reverse1temp=A.elem[i];A.elem[i]=A.elem[j];A.elem[j]=temp;2.21顺序表的就地逆置voidreverse2(Sqlist&A){

inttemp,i;for(i=0;i<=(A.length-1)/2;i++){

}}//reverse2temp=A.elem[i];A.elem[i]=A.elem[A.length-1-i];A.elem[A.length-1-i]=temp;2.19算法框架LinkList

DeleteBetween(LinkList*L,int

mink,int

maxk){//删除大于mink小于maxk的元素并释放结点空间。

if(mink>maxk)returnERROR; q=L->next;

while(q->data<=mink)//当结点值小于等于mink时

while(q->data<maxk) //当结点值小于maxk时

returnL;}

La0a1an-1a2…pq指针后移；删除该结点；2.19算法实现LinkList

DeleteBetween(LinkList

L,int

mink,int

maxk){ if(mink>maxk)//判断输入的边界值是否合法

{

printf("the

Llue

iswrong");exit(OVERFLOW);} q=L->next; p=L; while(q->data<=mink) {//寻找要删除结点所在的下边界位置

}while(q&&q->data<maxk)

{//寻找要删除结点所在的上边界位置

} returnL;}

p=q;q=p->next;

p->next=p->next->next;free(q);q=p->next;算法思想：在头结点和首元结点之间插入后继结点int

InvertLinkList(LinkListL){//