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

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

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

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

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

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

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

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

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

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

鏈?zhǔn)接诚?一元多項(xiàng)式的表示2線性表類型的實(shí)現(xiàn)

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

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

為線性表的表長(zhǎng);

稱n=0

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

稱i為ai在線性表中的位序。}11七月2024線性表的基本運(yùn)算置空表setnull(L)：將線性表L置為空表。求長(zhǎng)度length(L)：計(jì)算線性表L中數(shù)據(jù)元素的個(gè)數(shù)。取元素get(L,i)：取出線性表L中第i個(gè)數(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中的位置，并給出位置序號(hào)；若L中無(wú)x返回0。11七月2024線性表的基本運(yùn)算（續(xù)）插入insert(L,x,i)：在線性表L中第i個(gè)位置上插入值為x的新元素，使表長(zhǎng)增1；要求1≤i≤length(L)+1。刪除delete(L,i)：刪除線性表L中的第i個(gè)元素，使表長(zhǎng)減1；要求1≤i≤length(L)。11七月2024第10頁(yè)利用上述定義的線性表可以實(shí)現(xiàn)其它更復(fù)雜的操作例

2-2例

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

11七月2024第12頁(yè)

要求對(duì)線性表作如下操作：擴(kuò)大線性表LA，將存在于線性表LB中而不存在于線性表

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

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

locate(LA,e)

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

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

if(!locate(La,e))

insert(La,++La_len,e);

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

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

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

2-211七月2024第16頁(yè)集合B集合A從集合B

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

La_len=length(La);Lb_len=length(Lb);}//unione=get(Lb,i);//取Lb中第i個(gè)數(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頁(yè)若線性表中的數(shù)據(jù)元素相互之間可以比較，并且數(shù)據(jù)元素在線性表中依值非遞減或非遞增有序排列，即ai≥ai-1

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

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

//本算法將非遞減的有序表La和Lb歸并為L(zhǎng)c}//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頁(yè)

while(i<=La_len){//當(dāng)La不空時(shí)

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

}

//插入La表中剩余元素

while(j<=Lb_len){//當(dāng)Lb不空時(shí)

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

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

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頁(yè)線性表類型的實(shí)現(xiàn)----順序映象11七月2024第23頁(yè)

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

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

a1a2

…ai-1ai

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

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

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

11七月2024第29頁(yè)void

setnull(sequenlist*L)

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

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

intlocate(sequenlistL,elemtypex){

//

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

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

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

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

(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>表的長(zhǎng)度增加11七月2024第35頁(yè)算法的思想進(jìn)行合法性檢查（i）檢查線性表是否已滿講第n個(gè)至第i個(gè)元素逐一后移一個(gè)單位在第i個(gè)位置上插入表的長(zhǎng)度+111七月2024插入運(yùn)算的算法描述

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頁(yè)考慮插入算法的時(shí)間復(fù)雜度:11七月2024第38頁(yè)線性表操作

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

(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>表的長(zhǎng)度減少a1a2

…ai-1ai

ai+1

…ana1a2

…ai-1

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

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頁(yè)考慮刪除算法的時(shí)間復(fù)雜度:11七月2024舉例—?jiǎng)h除順序表中的重復(fù)元素一個(gè)順序表中可能含有一些值相同的重復(fù)元素，題目要求對(duì)于值相同的重復(fù)元素只保留位序最小的一個(gè)而刪除其它多余的元素。如（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中元素，比較當(dāng)前兩個(gè)元素值，將較小的元素賦給C，直到其中一個(gè)順序表掃描完畢，然后將另一個(gè)順序表中剩余元素賦給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頁(yè)線性表類型的實(shí)現(xiàn)---鏈?zhǔn)接诚?1七月2024第48頁(yè)

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

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

稱作鏈表11七月2024第49頁(yè)

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

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

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

structnode*next;//指針域

}

LinkList;

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

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

有時(shí)為了操作方便，在第一個(gè)結(jié)點(diǎn)之前虛加一個(gè)“頭結(jié)點(diǎn)”，以指向頭結(jié)點(diǎn)的指針為鏈表的頭指針?？罩羔樉€性表為空表時(shí)，頭結(jié)點(diǎn)的指針域?yàn)榭?/p>

11七月2024第52頁(yè)1.元素的查找按序號(hào)查找11七月2024第53頁(yè)L

線性表的操作

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

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

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

令指針p

始終指向線性表中第j

個(gè)數(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頁(yè)p=L;j=0;//p指向頭結(jié)點(diǎn)，j為計(jì)數(shù)器while(j<i&&p->next!=NULL){p=p->next;++j;}這兩種情況有六種組合1.p->next=NULL且j<i空表且i>0或者i>表長(zhǎng)，異常2.p->next=NULL且j=i空表且i=0或者i=表長(zhǎng)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個(gè)結(jié)點(diǎn)正常出循環(huán)6.p->next!

=NULL且j>i異常出循環(huán)11七月2024第59頁(yè)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é)點(diǎn)位置或NULL*/}如果要返回位序，程序怎么修改11七月2024第61頁(yè)2.插入操作11七月2024第62頁(yè)ai-1

線性表的操作

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

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

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

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

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

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

{

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

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

//

尋找第i-1個(gè)結(jié)點(diǎn)if(!p||j>i-1)

return0;//

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

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

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

在單鏈表中刪除第

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

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

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

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

++j;

}

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

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

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

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

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

//先建立一個(gè)帶頭結(jié)點(diǎn)的單鏈表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頁(yè)正序插法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é)束符號(hào)*/{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單鏈表建立過(guò)程示例線性表（25，45，18，76，29）的單鏈表動(dòng)態(tài)建立過(guò)程如下圖：11七月2024第84頁(yè)LinkList*CreateList(intn){/*正位序(插在表尾)輸入n個(gè)元素的值，建立帶表頭結(jié)構(gòu)的單鏈線性表*/ inti; LinkList*L; LinkList*p,*r; L=(LinkList*)malloc(sizeof(LinkList));/*生成頭結(jié)點(diǎn)*/ L->next=NULL; r=L; printf("請(qǐng)輸入%d個(gè)數(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頁(yè)歸并兩個(gè)有序表Lb26891115∧La35811∧11七月2024第86頁(yè)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頁(yè)

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

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

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

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

ra=ha;

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

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

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

rb=hb;

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

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

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;/*兩個(gè)尾結(jié)點(diǎn)的next域置空*/}11七月2024舉例——將單鏈表H逆置所謂逆置是指結(jié)點(diǎn)間的關(guān)系相反，即前趨變后繼而后繼變前趨。如圖(a)的單鏈表逆置后成為圖(b)的單鏈表。算法思路：依次從原鏈表中取出每個(gè)結(jié)點(diǎn)，每次都把它作為第一個(gè)結(jié)點(diǎn)插入到新鏈表中去。為此要借用兩個(gè)指針變量P和q，P用來(lái)指向原鏈表中的當(dāng)前第一個(gè)結(jié)點(diǎn)，q用來(lái)指向從原表取出的每一個(gè)結(jié)點(diǎn)并利用它插入到新鏈表中去，當(dāng)P為空時(shí)完成逆置。

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

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

改進(jìn)鏈表的設(shè)置

1．單鏈表的表長(zhǎng)是一個(gè)隱含的值；

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

ElemTypedata;

structnode*next;}Link;typedefstruct

{//鏈表類型

Link*head,*tail;