第二章線性表簡介：最簡單、最常用的數據結構，線性表的順序表示和實現線性表的鏈式表示和實現線性表的應用實例---

一元多項式的表示和運算重點：線性表的基本概念和術語線性表的順序表示和鏈式表示方法及其上的基本操作相關算法的時間復雜度分析難點：線性表的鏈式表示和基本操作

線性結構的特點存在唯一的一個被稱作"第一個"的數據元素；存在唯一的一個被稱作"最后一個"的數據元素；相鄰數據元素之間存在序偶關系，若將線性表記為（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){//