計算機軟件及應(yīng)用線性表

11七月2024第1頁【學(xué)習(xí)目標】1.了解線性表的邏輯結(jié)構(gòu)特性是數(shù)據(jù)元素之間存在著線性關(guān)系，在計算機中表示這種關(guān)系的兩類不同的存儲結(jié)構(gòu)是順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)。用前者表示的線性表簡稱為順序表，用后者表示的線性表簡稱為鏈表。

2.熟練掌握這兩類存儲結(jié)構(gòu)的描述方法以及線性表的基本操作在這兩種存儲結(jié)構(gòu)上的實現(xiàn)。

3.能夠從時間和空間復(fù)雜度的角度綜合比較線性表兩種存儲結(jié)構(gòu)的不同特點及其適用場合。

4.結(jié)合線性表類型的定義增強對抽象數(shù)據(jù)類型的理解。11七月2024第2頁【重點和難點】

鏈表是本章的重點和難點。扎實的指針操作和內(nèi)存動態(tài)分配的編程技術(shù)是學(xué)好本章的基本要求，分清鏈表中指針p和結(jié)點*p之間的對應(yīng)關(guān)系，區(qū)分鏈表中的頭結(jié)點、頭指針和首元結(jié)點的不同所指以及循環(huán)鏈表、雙向鏈表的特點等。

【知識點】線性表、順序表、鏈表、有序表11七月2024第3頁線性結(jié)構(gòu)的基本特征為:1．集合中必存在唯一的一個“第一元素”；2．集合中必存在唯一的一個“最后元素”；3．除最后元素在外，均有唯一的后繼；4．除第一元素之外，均有唯一的前驅(qū)。

線性結(jié)構(gòu)

是一個數(shù)據(jù)元素的有序（次序）集線性表是一種最簡單的線性結(jié)構(gòu)11七月2024第4頁1

線性表的類型定義3線性表類型的實現(xiàn)

鏈式映象4一元多項式的表示2線性表類型的實現(xiàn)

順序映象11七月2024第5頁線性表的類型定義11七月2024第6頁定義：一個線性表是具有相同類型的n（n≧0）個數(shù)據(jù)元素的有限序列，通常記為：例英文字母表（A,B,C,…..Z)例數(shù)據(jù)元素特征：i為元素的序號元素個數(shù)n—表長度，n=0空表1<i<n時ai的直接前驅(qū)是ai-1，a1無直接前驅(qū)ai的直接后繼是ai+1，an無直接后繼1線性表的定義11七月2024第7頁

數(shù)據(jù)對象：D＝{ai|ai∈D0,i=1,2,...,n,n≥0}{稱n

為線性表的表長;

稱n=0

時的線性表為空表。}數(shù)據(jù)關(guān)系：R＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}{設(shè)線性表為(a1，a2,...，ai，...，an),

稱i為ai在線性表中的位序。}11七月2024線性表的基本運算置空表setnull(L)：將線性表L置為空表。求長度length(L)：計算線性表L中數(shù)據(jù)元素的個數(shù)。取元素get(L,i)：取出線性表L中第i個數(shù)據(jù)元素；要求i≤length(L)。取前趨prior(L,x)：取出線性表L中值為x的元素的前趨元素；要求x的位序大于1。取后繼next(L,x)：取出線性表L中值為x的元素的后繼元素；要求x的位序小于length(L)。定位序locate(L,x)：確定元素x在線性表L中的位置，并給出位置序號；若L中無x返回0。11七月2024線性表的基本運算（續(xù)）插入insert(L,x,i)：在線性表L中第i個位置上插入值為x的新元素，使表長增1；要求1≤i≤length(L)+1。刪除delete(L,i)：刪除線性表L中的第i個元素，使表長減1；要求1≤i≤length(L)。11七月2024第10頁利用上述定義的線性表可以實現(xiàn)其它更復(fù)雜的操作例

2-2例

2-111七月2024第11頁求兩個集合的并，即A=A∪B例2-1

11七月2024第12頁

要求對線性表作如下操作：擴大線性表LA，將存在于線性表LB中而不存在于線性表

LA中的數(shù)據(jù)元素插入到線性表LA

中去。上述問題可演繹為：11七月2024第13頁1．從線性表LB中依次察看每個數(shù)據(jù)元素;2．依值在線性表LA中進行查訪;3．若不存在，則插入之。get(LB,i)→e

locate(LA,e)

insert(LA,n+1,e)操作步驟：11七月2024第14頁

e=get(Lb,i);//取Lb中第i個數(shù)據(jù)元素賦給e

if(!locate(La,e))

insert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之voidunion(La,Lb){La_len=length(La);//求線性表的長度

Lb_len=length(Lb);for(i=1;i<=Lb_len;i++){}}//union11七月2024第15頁

已知一個非純集合B，試構(gòu)造一個純集合A，使A中只包含B中所有值各不相同的數(shù)據(jù)元素。仍選用線性表表示集合。例

2-211七月2024第16頁集合B集合A從集合B

取出物件放入集合A要求集合A中同樣物件不能有兩件以上因此，算法的策略應(yīng)該和例2-1相同11七月2024第17頁voidunion(List&La,ListLb){

La_len=length(La);Lb_len=length(Lb);}//unione=get(Lb,i);//取Lb中第i個數(shù)據(jù)元素賦給e

if(!locate(La,e))

insert(La,++La_len,e);

//La中不存在和e相同的數(shù)據(jù)元素，則插入之for(i=1;i<=Lb_len;i++){}setnull(La);//構(gòu)造(空的)線性表LA11七月2024第18頁若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai≥ai-1

或ai≤ai-1(i=2,3,…,n)，則稱該線性表為有序表(OrderedList)。我們再來看看有序表表示的集合。11七月2024第19頁例如：LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)對集合LA和LB而言，

值相同的數(shù)據(jù)元素必定相鄰。要求生成一個新表LC，使LC中的數(shù)據(jù)元素仍按值非遞減有有序排列。11七月2024第20頁voidMergeList(ListLa,ListLb,List&Lc){

//本算法將非遞減的有序表La和Lb歸并為Lc}//merge_listwhile((i<=La_len)&&(j<=Lb_len))

{//La和Lb均不空}while(i<=La_len)

//若La不空while(j<=Lb_len)//若Lb不空setnull(Lc);//構(gòu)造空的線性表Lci=j=1;k=0;La_len=length(La);Lb_len=length(Lb);例

2-311七月2024第21頁

while(i<=La_len){//當La不空時

ai=get(La,i++);insert(Lc,++k,ai);

}

//插入La表中剩余元素

while(j<=Lb_len){//當Lb不空時

bj=get(Lb,j++);insert(Lc,++k,bj);

}//插入Lb表中剩余元素While((i<=La_len)&&(j<=Lb_len)){//當La,Lb都不空時

ai=get(La,i);bj=get(Lb,j);if(ai<=bj){insert(Lc,++k,ai);++i;}else{insert(Lc,++k,bj);++j}

}11七月2024第22頁線性表類型的實現(xiàn)----順序映象11七月2024第23頁

用一組地址連續(xù)的存儲單元

依次存放線性表中的數(shù)據(jù)元素

a1a2

…ai-1ai

…an線性表的起始地址稱作線性表的基地址11七月2024第24頁元素地址計算方法：LOC(ai)=LOC(a1)+(i-1)*d1≦i≦n特點：邏輯上相鄰—物理地址相鄰隨機存取實現(xiàn)：可用C語言的一維數(shù)組實現(xiàn)LOC(a1)+(n-1)*dLOC(a1)LOC(a1)+(i-1)*d存儲地址LOC(a1)+dan…..ai…..a2a1d11七月2024順序表的類型描述

#defineMAXSIZE500typedefstruct{elemtypedata[MAXSIZE];intlast;}sequenlist,seqlist;即把順序表類型sequenlist描述為一個結(jié)構(gòu)體，域data數(shù)組存放表中的數(shù)據(jù)元素，域last存放表長，data[last]存放表中最后一個元素。11七月2024庫函數(shù)提供動態(tài)地開辟和釋放存儲單元的有關(guān)函數(shù)：malloc函數(shù)其函數(shù)原型為void*malloc(unsignedintsize);其作用是在內(nèi)存的動態(tài)存儲區(qū)中分配一個長度為size的連續(xù)空間。此函數(shù)的值（即“返回值”）是一個指向分配域起始地址的指針（類型為void）。如果此函數(shù)未能成功地執(zhí)行（例如內(nèi)存空間不足），則返回空指針(NULL)。

11七月2024(2)calloc函數(shù)其函數(shù)原型為void*calloc（unsignedｎ，unsignedsize）;其作用是在內(nèi)存的動態(tài)存儲區(qū)中分配ｎ個長度為size的連續(xù)空間。函數(shù)返回一個指向分配域起始地址的指針；如果分配不成功，返回NULL。用calloc函數(shù)可以為一維數(shù)組開辟動態(tài)存儲空間，n為數(shù)組元素個數(shù)，每個元素長度為size11七月2024(3)free函數(shù)其函數(shù)原型為voidfree（void*p）;其作用是釋放由ｐ指向的內(nèi)存區(qū)，使這部分內(nèi)存區(qū)能被其他變量使用。ｐ是最近一次調(diào)用calloc或malloc函數(shù)時返回的值。free函數(shù)無返回值.

11七月2024第29頁void

setnull(sequenlist*L)

{//構(gòu)造一個空的線性表

}//InitList_Sqintlength(sequenlistL){returnL.last;}L->last=0;11七月2024第30頁線性表的基本操作在順序表中的實現(xiàn)Locate(L,x)//查找11七月2024第31頁例如：順序表的查找操作23754138546217L.dataL.lastMAXSIZEx=38pppppi12341850p可見，基本操作是：將順序表中的元素逐個和給定值x相比較。11七月2024第32頁

intlocate(sequenlistL,elemtypex){

//

在順序表中查詢第一個滿足判定條件的數(shù)據(jù)元素，

//若存在，則返回它的位序，否則返回0}

O(ListLength(L))算法的時間復(fù)雜度為：inti=1;//i的初值為第1元素的位序while

(i<=L.last&&(L.data[i]!=x))++i;if(i<=L.last)returni;elsereturn0;11七月2024第33頁線性表操作insert(L,i,x)的實現(xiàn)：首先分析:插入元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？11七月2024第34頁

(a1,…,ai-1,ai,…,an)改變?yōu)?/p>

(a1,…,ai-1,x,ai,…,an)a1a2

…ai-1ai

…ana1a2

…ai-1

…aixan<ai-1,ai><ai-1,e>,<e,ai>表的長度增加11七月2024第35頁算法的思想進行合法性檢查（i）檢查線性表是否已滿講第n個至第i個元素逐一后移一個單位在第i個位置上插入表的長度+111七月2024插入運算的算法描述

voidinsert(sequenlist*L;elemtypex;inti){intj;if((i<1)||i>(L->last+1))printf(“插入位置不正確\n”);elseif(L->last>=MAXSIZE)printf(“表已滿，發(fā)生上溢\n”);else{for(j=L->last;j>=i;j--)L->data[j+1]=L->data[j];L->data[i]=x;L->last=L->last+1;}}/*insert*/11七月2024第37頁考慮插入算法的時間復(fù)雜度:11七月2024第38頁線性表操作

delete(&L,i)的實現(xiàn)：首先分析：刪除元素時，線性表的邏輯結(jié)構(gòu)發(fā)生什么變化？11七月2024第39頁

(a1,…,ai-1,ai,ai+1,…,an)改變?yōu)?/p>

(a1,…,ai-1,ai+1,…,an)ai+1…an<ai-1,ai>,<ai,ai+1><ai-1,ai+1>表的長度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

11七月2024第40頁算法的思想進行合法性檢查，i是否滿足要求判定線性表是否為空將第i+1至第n個元素逐一往前移動一個位置將表的長度減少111七月2024刪除運算的算法描述

voiddelete(sequenlist*L，inti){intj;if((i<1)||(i>L->last))printf(“刪除位置不正確\n”);else{for(j=i+1;j<=L->last;j++)L->data[j-1]=L->data[j];L->last=L->last-1;}}/*delete*/11七月2024第42頁考慮刪除算法的時間復(fù)雜度:11七月2024舉例—刪除順序表中的重復(fù)元素一個順序表中可能含有一些值相同的重復(fù)元素，題目要求對于值相同的重復(fù)元素只保留位序最小的一個而刪除其它多余的元素。如（5，2，2，3，5，2）經(jīng)刪除重復(fù)元素后變?yōu)椋?，2，3）

11七月2024刪除順序表中的重復(fù)元素的算法描述

voidPurge(L)sequenlist*L;{inti,j,k;i=1;while(i<L->last){j=i+1;while(j<=L->last)if(L->data[j]==L->data[i]){for(k=j+1;k<=L->last;k++)L->data[k-1]=L->data[k];L->last=L->last-1;}elsej++;

i++;}}/*Purge*/11七月2024舉例—有序表的合并順序表A和B的元素均按由小到大的升序排列，編寫算法將它們合并成為順序表C，要求C中元素也是從小到大的升序排列。算法思路：依次掃描A和B中元素，比較當前兩個元素值，將較小的元素賦給C，直到其中一個順序表掃描完畢，然后將另一個順序表中剩余元素賦給C即可。

11七月2024有序表的合并的算法描述

voidmerge(C,A,B)sequenlist*C,*A,*B;{inti,j,k;i=1;j=1;k=1;while(i<=A->last&&j<=B->last)if(A->data[i]<B->data[j])C->data[k++]=A->data[i++];elseC->data[k++]=B->data[j++];While(i<A->last)C->data[k++]=A->data[i++];While(j<B->last)C->data[k++]=B->data[j++];C->last=k-1;}/*merge*/11七月2024第47頁線性表類型的實現(xiàn)---鏈式映象11七月2024第48頁

用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。一、單鏈表以數(shù)據(jù)域(數(shù)據(jù)元素的信息)

+指針(指示后繼元素存儲位置)=結(jié)點以“結(jié)點的序列”表示線性表

稱作鏈表11七月2024第49頁

以線性表中第一個數(shù)據(jù)元素的存儲地址作為線性表的地址，稱作線性表的頭指針。

a1a2…...an^頭指針空指針11七月2024第50頁

typedefstructnode{elemtypedata;//數(shù)據(jù)域

structnode*next;//指針域

}

LinkList;

二、結(jié)點和單鏈表的C語言描述LinkList*H,*P；//H,P為單鏈表的頭指針11七月2024第51頁頭結(jié)點

a1a2…...an^頭指針頭指針

有時為了操作方便，在第一個結(jié)點之前虛加一個“頭結(jié)點”，以指向頭結(jié)點的指針為鏈表的頭指針?？罩羔樉€性表為空表時，頭結(jié)點的指針域為空

11七月2024第52頁1.元素的查找按序號查找11七月2024第53頁L

線性表的操作

GetLinkList(L,i)在單鏈表中的實現(xiàn)(找到第3個元素):211830754256∧pppj12311七月2024第54頁

因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較j和i。

單鏈表不是一種順序存取的結(jié)構(gòu)，為找第i個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素。

令指針p

始終指向線性表中第j

個數(shù)據(jù)元素。11七月2024

LinkList*getLinkList(LinkList*L，inti){LinkList*P;intj=0;P=L;while((j<i)&&(P->next!=NULL)){P=P->next;j++;}if(j==i)returnP;elsereturnNULL;}11七月2024elemtypeGetLinkList(LinkList*L，inti){LinkList*P;intj=0;P=L;while((j<i)&&(P->next!=NULL)){P=P->next;j++;}if(j==i)returnP->data;elsereturn0;}11七月2024

intGetLinkList(LinkList*L，inti,elemtype*e){LinkList*P;intj=0;P=L;while((j<i)&&(P->next!=NULL)){P=P->next;j++;}if(j==i){*e=P->data;return1;}elsereturn0;}11七月2024第58頁p=L;j=0;//p指向頭結(jié)點，j為計數(shù)器while(j<i&&p->next!=NULL){p=p->next;++j;}這兩種情況有六種組合1.p->next=NULL且j<i空表且i>0或者i>表長，異常2.p->next=NULL且j=i空表且i=0或者i=表長3.p->next=NULL且j>i空表且i<0，異常出循環(huán)4.p->next

!=NULL且j<i繼續(xù)循環(huán)5.p->next

!=NULL且j=i確定第i個結(jié)點正常出循環(huán)6.p->next!

=NULL且j>i異常出循環(huán)11七月2024第59頁1.元素的查找按值查找L211830754256∧pLocateLinkList(L,x)

11七月2024LinkList*LocateLinkList(LinkList*L，elemtypex){LinkList*P;P=L->next;while((P!=NULL)&&(P->data!=x))P=P->next;returnP;/*返回找到的結(jié)點位置或NULL*/}如果要返回位序，程序怎么修改11七月2024第61頁2.插入操作11七月2024第62頁ai-1

線性表的操作

insertLinkList(L,x,i)在單鏈表中的實現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,x>和<x,ai>xaiai-111七月2024第63頁s->data=e;s->next=p->next;p->next=s;//插入eai-1aiai-1sp11七月2024第64頁

因此，在單鏈表中第i個結(jié)點之前進行插入的基本操作為:

找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。

可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第i個結(jié)點之前插入元素，修改的是第i-1個結(jié)點的指針。11七月2024插入算法描述voidinsertLinkList(LinkList*L,elemtypex,inti){LinkList*P,*S;P=getLinkList(L,i-1);/*查找第i-1個結(jié)點*/if(P==NULL)Printf(“第i-1個元素不存在，參數(shù)i有錯\n”);else{S=(LinkList*)malloc(sizeof(LinkList));S->data=x;S->next=P->next;P->next=S;}}11七月2024第66頁intinsertLinkList(LinkList*L,ElemTypee,inti)

{

}……LinkList*p=L;intj=0;while(p&&j<i-1)

{p=p->next;++j;}

//

尋找第i-1個結(jié)點if(!p||j>i-1)

return0;//

i大于表長或者小于111七月2024第67頁s=(LinkList*)malloc(sizeof(node));

//生成新結(jié)點s->data=e;s->next=p->next;p->next=s;//插入return1;eai-1aiai-1sp11七月2024第68頁循環(huán)條件的分析第一次循環(huán)p!=NULL,j有三種可能1.j<i-1繼續(xù)循環(huán)2.j=i-1,此時i=1，在第一個元素插入3.j>i-1i<1不合法1.p=!NULL且j<i-1繼續(xù)循環(huán)2.p=!NULL且j=i-1已經(jīng)定位正常出循環(huán)3.p=NULL且j<=i-1i不合法(i>=表長+2），出循環(huán)第二次循環(huán)后，p有可能NULL,但是j>i-1不可能，出現(xiàn)的各種可能情況：11七月2024第69頁3.刪除操作11七月2024第70頁線性表的操作deleteLinkList(L,i)在鏈表中的實現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-111七月2024第71頁

在單鏈表中刪除第

i個結(jié)點的基本操作為:找到線性表中第i-1個結(jié)點，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq11七月2024刪除單鏈表L中的第i個結(jié)點算法

voiddeleteLinkList(LinkList*L,inti){LinkList*P,*S;P=getLinkList(L,i-1);/*查找第i-1個結(jié)點*/if(P==NULL)Printf(“第i-1個元素不存在，參數(shù)i有錯\n”);else{S=P->next;P->next=S->next;free(S);}}11七月2024第73頁intdeleteLinkList(LinkList*L,inti,ElemType&e){}

LinkList*p=L;intj=0;while(p->next!=NULL&&j<i-1){p=p->next;//尋找第i個結(jié)點，并令p指向其前趨

++j;

}

if(!(p->next)||j>i-1)

return0;//刪除位置不合理q=p->next;p->next=q->next;

//刪除并釋放結(jié)點e=q->data;free(q);return1;11七月2024第74頁刪除算法討論：刪除范圍為[1,表長]，不能刪除頭結(jié)點出循環(huán)的五種可能情況：p->next=NULL且j<i-1空表或i>表長p->next=NULL且j=i-1空表且i=1，或i=表長+1p->next=NULL且j>i-1空表且i<1p->next!=NULL且j=i-1非空表且定位p->next!=NULL且j>i-1非空表且i<111七月20244.求表長只要設(shè)一個移動指針掃描整個單鏈表，就可以統(tǒng)計出元素個數(shù)即表長。其算法描述如下：

intLengthLinkList(LinkList*L){LinkList*P=L;intj=0;While(P->next!=NULL){P=P->next;j++;}returnj;/*返回表長*/}該算法掃描整個單鏈表，時間復(fù)雜度為O(n)。

11七月2024第76頁5.建立單鏈表11七月2024第77頁如何從得到單鏈表？鏈表是一個動態(tài)的結(jié)構(gòu)，它不需要予分配空間，因此生成鏈表的過程是一個結(jié)點“逐個插入”的過程。11七月2024第78頁例如：逆位序輸入n個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。(頭插法)操作步驟：一、建立一個“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入；ananan-1四、依次類推，直至輸入a1為止。11七月2024第79頁adcbi=0i=1i=2i=3∧head采用頭插法建立單鏈表的過程heada∧headda∧headcda∧headbcda∧第1步:建頭結(jié)點第2步:i＝0,新建a結(jié)點,插入到頭結(jié)點之后第3步:i＝1,新建d結(jié)點,插入到頭結(jié)點之后第4步:i＝2,新建c結(jié)點,插入到頭結(jié)點之后第5步:i＝3,新建b結(jié)點,插入到頭結(jié)點之后11七月2024第80頁voidCreateList(LinkList*&L,intn){//逆序輸入n個數(shù)據(jù)元素，建立帶頭結(jié)點的單鏈表}算法的時間復(fù)雜度為:O(Listlength(L))L=(LinkList*)malloc(sizeof(node));L->next=NULL;

//先建立一個帶頭結(jié)點的單鏈表for(i=n;i>0;--i){p=(LinkList*)malloc(sizeof(node));

scanf(“%d”,&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}11七月2024第81頁正序插法11七月2024具體的算法描述如下：LinkList*CreateLinkList(){charch;intx;LinkList*head;LinkList*r,*P;head=(LinkList*)malloc(sizeof(LinkList));head->next=NULL;

r=head;/*尾指針初始化*/ch=getchar();while(ch!=’*’)//“*”為輸入數(shù)據(jù)結(jié)束符號*/{scanf(“%d”,&x);P=(LinkList*)malloc(sizeof(LinkList));P->data=x;P->next=NULL;r->next=P;r=r->next;ch=getchar();}returnhead;}11七月2024單鏈表建立過程示例線性表（25，45，18，76，29）的單鏈表動態(tài)建立過程如下圖：11七月2024第84頁LinkList*CreateList(intn){/*正位序(插在表尾)輸入n個元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表*/ inti; LinkList*L; LinkList*p,*r; L=(LinkList*)malloc(sizeof(LinkList));/*生成頭結(jié)點*/ L->next=NULL; r=L; printf("請輸入%d個數(shù)據(jù)\n",n); for(i=1;i<=n;i++) { p=(LinkList*)malloc(sizeof(LinkList));

scanf("%d",&p->data); p->next=NULL; r->next=p; r=p; } returnL}11七月2024第85頁歸并兩個有序表Lb26891115∧La35811∧11七月2024第86頁LinkList*MergeList(LinkList*&La,LinkList*&Lb)pa=La->next;pb=Lb->next;Lc=pc=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;}}if(pa)pc->next=pa;elsepc->next=pb;

free(Lb);returnLc}

。11七月2024第87頁

例設(shè)C={a1,b1,a2,b2,…,an,bn}為一線性表,采用帶頭結(jié)點的hc單鏈表存放,編寫一個算法,將其拆分為兩個線性表,使得:A={a1,a2,…,an},B={b1,b2,…,bn}

解:設(shè)拆分后的兩個線性表都用帶頭結(jié)點的單鏈表存放。先建立兩個頭結(jié)點*ha和*hb,它們用于存放拆分后的線性表A和B,ra和rb分別指向這兩個單鏈表的表尾。 用p指針掃描單鏈表hc,將當前結(jié)點*p鏈到ha未尾,p沿next域下移一個結(jié)點,若不為空,則當前結(jié)點*p鏈到hb未尾,p沿next域下移一個結(jié)點,如此這樣,直到p為空。最后將兩個尾結(jié)點的next域置空。11七月2024第88頁

voidfun(LinkList*hc,LinkList*&ha,LinkList*&hb){LinkList*p=hc->next,*ra,*rb;ha=hc;

/*ha的頭結(jié)點利用hc的頭結(jié)點*/

ra=ha;

/*ra始終指向ha的末尾結(jié)點*/

hb=(LinkList*)malloc(sizeof(LinkList));

/*創(chuàng)建hb頭結(jié)點*/

rb=hb;

/*rb始終指向hb的末尾結(jié)點*/

本算法實際上是采用尾插法建立兩個新表。所以,尾插法建表算法是很多類似習(xí)題的基礎(chǔ)！11七月2024第89頁

while(p!=NULL){ra->next=p; ra=p;/*將*p鏈到ha單鏈表未尾*/p=p->next;if(p!=NULL){rb->next=p;rb=p; /*將*p鏈到hb單鏈表未尾*/p=p->next;}}ra->next=rb->next=NULL;/*兩個尾結(jié)點的next域置空*/}11七月2024舉例——將單鏈表H逆置所謂逆置是指結(jié)點間的關(guān)系相反，即前趨變后繼而后繼變前趨。如圖(a)的單鏈表逆置后成為圖(b)的單鏈表。算法思路：依次從原鏈表中取出每個結(jié)點，每次都把它作為第一個結(jié)點插入到新鏈表中去。為此要借用兩個指針變量P和q，P用來指向原鏈表中的當前第一個結(jié)點，q用來指向從原表取出的每一個結(jié)點并利用它插入到新鏈表中去，當P為空時完成逆置。

11七月2024將單鏈表H逆置的算法描述

voidreverse(H)LinkList*H;{LinkList*P,*q;P=H->next;H->next=NULL;while(P!=NULL){q=P;P=P->next;q->next=H->next;H->next=q;}}*reverse*/該算法沒有開辟新的存儲空間，對鏈表順序掃描一遍就完成了逆置，時間開銷為O(n)。11七月2024第92頁作業(yè)：1.給定一個單鏈表L，編寫一個刪除L中值為x的結(jié)點的直接前驅(qū)結(jié)點算法。2.有一個單鏈表（不同的結(jié)點的數(shù)據(jù)域值可能相同），其頭指針為head,編寫一個函數(shù)計算數(shù)據(jù)域為x的結(jié)點個數(shù)。11七月2024第93頁作業(yè)2：1.給定一個單鏈表L，編寫一個刪除L中值為x的結(jié)點的算法。2.設(shè)計一個算法，在一個單鏈表中值為y的結(jié)點前面插入一個值為x的結(jié)點。11七月2024第94頁優(yōu)點邏輯相鄰，物理相鄰可隨機存取任一元素存儲空間使用緊湊缺點插入、刪除操作需要移動大量的元素預(yù)先分配空間需按最大空間分配，利用不充分表容量難以擴充順序存儲結(jié)構(gòu)的優(yōu)缺點11七月2024第95頁單鏈表特點它是一種動態(tài)結(jié)構(gòu)，整個存儲空間為多個鏈表共用不需預(yù)先分配空間指針占用額外存儲空間不能隨機存取，查找速度慢11七月2024第96頁循環(huán)鏈表是表中最后一個結(jié)點的指針指向頭結(jié)點，使鏈表構(gòu)成環(huán)狀h空表循環(huán)鏈表(circularlinkedlist)特點：從表中任一結(jié)點出發(fā)均可找到表中其他結(jié)點，提高查找效率操作與單鏈表基本一致,循環(huán)條件不同單鏈表p或p->next==NULL循環(huán)鏈表p或p->next==Hh…11七月2024第97頁r空表設(shè)置尾指針的循環(huán)鏈表設(shè)置尾指針的循環(huán)鏈表，在對兩個單循環(huán)鏈表進行連接使可以提高效率。r2b1bnr1a1anr1->next=r2->next->next;r2->next=p;r…pp=r1->next;11七月2024第98頁單鏈表具有單向性的缺點，找前驅(qū)不方便！結(jié)點定義typedefstructdupnode{elemtypedata;structdupnode*prior,*next;}duplinklist;priordatanextL空雙向循環(huán)鏈表：非空雙向循環(huán)鏈表：LABbcapp->prior->next=p=p->next->proir;雙向鏈表（doublelinkedlist）11七月2024第99頁雙向鏈表的操作特點：“查詢”和單鏈表相同?！安迦搿焙汀皠h除”時需要同時修改兩個方向上的指針。11七月2024第100頁voidins_dlinklist(duplinklist*p,intx){duplinklist*s;s=(duplinklist*)malloc(sizeof(duplinklist));s->data=x;

s->prior=p->prior;

p->prior->next=s;

s->next=p;

p->prior=s;}算法描述算法評價：T(n)=O(1)xSbaP插入p->prior->next=s;s->prior=p->prior;s->next=p;p->prior=s;11七月2024第101頁ai-1aies->next=p->next;p->next=s;s->next->prior=s;s->prior=p;psai-1ai插入11七月2024第102頁bcaPvoiddel_dlinklist(duplinklist*p){p->prior->next=p->next;

p->next->prior=p->prior;free(p);}刪除算法描述算法評價：T(n)=O(1)p->prior->next=p->next;p->next->prior=p->prior;11七月2024第103頁ai-1刪除aiai+1p->next=p->next->next;p->next->prior=p;pai-111七月2024第104頁用上述定義的單鏈表實現(xiàn)線性表的操作時，存在的問題：

改進鏈表的設(shè)置

1．單鏈表的表長是一個隱含的值；

1．增加“表長”、“表尾指針”和“當前位置的指針”三個數(shù)據(jù)域；2．在單鏈表的最后一個元素之后插入元素時，需遍歷整個鏈表；3．在鏈表中，元素的“位序”概念淡化，結(jié)點的“位置”概念加強。2．將基本操作中的“位序i”改變?yōu)椤爸羔榩”。11七月2024第105頁一個帶頭結(jié)點的線性鏈表類型typedefstructnode{//結(jié)點類型

ElemTypedata;

structnode*next;}Link;typedefstruct

{//鏈表類型

Link*head,*tail;