數(shù)據(jù)結(jié)構(gòu)之線性表

第二章線性表線性結(jié)構(gòu)

是

一個數(shù)據(jù)元素的有序（次序）集線性表的基本特征存在惟一的一個被稱做“第一個”的數(shù)據(jù)元素；存在惟一的一個被稱做“最后一個”的數(shù)據(jù)元素；除第一個之外，集合中的每個數(shù)據(jù)元素均只有一個前驅(qū)；除最后一個之外，集合中的每個數(shù)據(jù)元素均只有一個后繼。2.1線性表的類型定義2.2線性表類型的實現(xiàn)

——順序映像2.3線性表類型的實現(xiàn)

——鏈式映像2.4一元多項式的表示抽象數(shù)據(jù)類型線性表的定義ADTList{

數(shù)據(jù)對象：

D={ai|ai

ElemSeti=1,2,..,nn≥0}{稱n為線性表的表長，稱n=0時的線性表為空表}

數(shù)據(jù)關(guān)系：

R1={<ai,ai+1>|ai,ai+1ElemSet,i=1,2,..,n-1≥0}{稱i為ai在線性表中的位序}(a1,a2,...,ai-1,ai,ai+1,…,an)基本操作：

{結(jié)構(gòu)初始化}

InitList(&L)

操作結(jié)果：構(gòu)造一個空的線性表L{銷毀結(jié)構(gòu)}

DetroyList(&L)

初始條件：線性表L已經(jīng)存在操作結(jié)果：銷毀線性表L{引用型操作}ListEmpty(L)ListLength(L)

PriorElem(L,cur_e,&pre_e)

NextElem(L,cur_e,&next_e)GetElem(L,i,&e)

LocateElem(L,e,compare())ListTraverse(L,visit())

ListEmpty(L)

操作結(jié)果：若線性表L為空表，則返回True，否則返回FalseListLength(L)

操作結(jié)果：返回線性表L中元素的個數(shù)

PriorElem(L,cur_e,&pre_e)

操作結(jié)果：若cur_e是L的元素，但不是第一個，則用pre_e返回它的前驅(qū)，否則操作失敗

NextElem(L,cur_e,&next_e)

操作結(jié)果：若cur_e是L中的元素，但不是最后一個，則用next_e返回它的后繼，否則操作失敗

GetElem(L,i,&e)

操作結(jié)果：用e返回L中第i個元素的值，其中1<=i<=ListLength(L)

LocateElem(L,e,compare())

操作結(jié)果：返回第一個與e滿足compare()關(guān)系的數(shù)據(jù)元素的位序。若不存在這樣的元素，則返回0ListTraverse(L,visit())

操作結(jié)果：遍歷線性表L，對每個元素執(zhí)行函數(shù)visit(){加工型操操作}ClearList(&L)PutElem(L,i,&e)ListInsert(&L,i,e)ListDelete(&l,i,&e)ClearList(&L)初始條件件：線性性表L已經(jīng)存在在操作結(jié)果果：將L重至為空空表PutElem(L,i,&e)初始條件件：線性性表L已存在，，其中1<=i<=LengthList(L)操作結(jié)果果：L中的第i個元素賦賦值為e的值ListInsert(&L,i,e)初始條件件：線性性表L已存在，，其中1<=i<=LengthList(L)+1操作結(jié)果果：在L的第i個元素之之前插入入一個新新的元素素e，L的長度增增加1ListDelete(&l,i,&e)初始條件件：線性性表L已存在并并且非空空，其中中1<=i<=LengthList(L)操作結(jié)果果：將L的第i個元素刪刪除，并并將之，，L的長度增增加1利用上述述定義的的線性表可以完成成更復雜雜的操作作例2-1假設有兩兩個集合合A和B，分別用用兩個線線性表LA和LB來表示（（即：線線性表中中的數(shù)據(jù)據(jù)元素為為集合中中的成員員）現(xiàn)求一個個新的集集合A=A∪∪B上述問題題可以演演繹為，，要求對線線性表作作如下操操作：擴大線性性表LA，將存在在于線性性表LB中而不存存在于線線性表LA中的數(shù)據(jù)據(jù)元素插插入到線線性表LA中EBFHVDALAASFGLBVSGijjjjjjiiii從線性表表LB中依次取取得每個個數(shù)據(jù)元元素：GetElem(LB,i)→e依值在線線性表LA中進行查查訪：LocateElem(LA,e,Equal())若不存在在，則插插入之，，ListInsert(LA,n+1,e)VoidUnion(List&La,ListLb){La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表表的長度度for(i=0;i<Lb_len;i++){GetElem(Lb,i,e);//取Lb中的第i個元素賦賦給eif(!LocateElem(La,e,equal()))ListInsert(La,La_len++,e)//若La中不存在在和e相同的值值，則插插入之}}例2-2已知一個個非純集集合B，試構(gòu)造造一個純純集合A，使A中只包含含B中所有值值各不相相同的數(shù)數(shù)據(jù)元素素EBEHDALBBDBELAEBHDAVoidPurge(List&La,ListLb){InitList(La);//設置空的的線性表表LaLa_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表表的長度度for(i=0;i<Lb_len;i++){GetElem(Lb,i,e);//取Lb中的第i個元素賦賦給eif(!LocateElem(La,e,equal()))ListInsert(La,La_len++,e)//若La中不存在在和e相同的值值，則插插入之}}EBEHDALBBDBELAEBHDAVoidPurge(List&La,ListLb){InitList(La);//設置空的的線性表表LaLa_len=ListLength(La);Lb_len=ListLength(Lb);//求線性表表的長度度for(i=0;i<Lb_len;i++){GetElem(Lb,i,e);//取Lb中的第i個元素賦賦給eif(!ListEmpty(La)||!equal(en,e)){ListInsert(La,La_len++,e);//若La中不存在在和e相同的值值，則插插入之en=e;}}}例2-3歸并兩個個“其數(shù)數(shù)據(jù)元素素按值非非遞減有有序排列列的”線線性表LA和LB，求求得線性性表LC也具有有同樣特特性。不會BLEBLBDLGCGIFALADHLCABBCDDEFGGHILL設La=(a1,….,ai,….,an)Lb=(b1,….,bj,….,bn)Lc=(c1,….,ck,….,cm+n)則ck中的k為1，2，……m+n1、分別從La和Lb中取得當前元元素ai和bj2、若ai≤bj，則將ai插入Lc中去，否則將將bj插入到Lc中VoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;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){ListInsert(Lc,k++,ai);i++;}else{ListInsert(Lc,k++,bj);j++;}}while()While(i<=la_len){GetElem(La,i++,ai);ListInsert(Lc,k++,ai);}While(j<=lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,k++,aj);}}習題：1、有線性表LA和LB均為有序線性性表，試構(gòu)造造線性表LA1和LB1分別為LA和LB中除去最大共共同前綴后的的子表。比如：LA=(a,b,c,e,f)LB=(a,b,d,e,f)則LA1=(c,e,f)LB1=(d,e,f)注意：LA和LB有一個是空表表LA和LB相等構(gòu)造線線性表表LA1和LB1InitList(LA1),InitList(LB1)分別從從LA和LB中取得得第i個數(shù)據(jù)據(jù)元素素GetElem(LA,i,ai),GetElem(LB,i,bi)比較ai和bi是否相相等，，若相相等繼繼續(xù)取取第i+1個數(shù)據(jù)據(jù)元素素；若若不相相等，，則已已經(jīng)找找到最最大前前綴，，為前前i-1項，退退出將從第第i項開始始的LA和LB分別存存放到到LA1和LB1中即可可VoidwipePrefix(ListLA,ListLB,List&LA1,List&LB1){InitList(LA1);InitList(LB1);//初始化化LA1和LB1inti=1;La_len=ListLength(La);Lb_len=ListLength(Lb);//求線性性表的的長度度while(i<=La_len||i<=Lb_len){GetElem(LA,i,ai);GetElem(LB,i,bi);if(ai==bi)i++;//比較ai和bi是否相相等，，若相相等繼繼續(xù)取取第i+1個數(shù)據(jù)據(jù)元素素,否則退退出elsebreak;}j=i;While(j<=La_len){GetElem(LA,j,aj);ListInsert(LA1,j,aj);}j=i;While(j<=Lb_len){GetElem(LB,j,bj);ListInsert(LB1,j,bj);}}2、線性性表LA和LB均為遞遞增有有序的的線性性表，，要求求對LA做如下下操作作，刪刪除在在LB中出現(xiàn)現(xiàn)的元元素。。要求：(1)、用學學到的的線性性表抽抽象數(shù)數(shù)據(jù)類類型中中提供供的操操作編編寫算算法，，完成成上述述兩題題功能能。(2)、分析析所寫寫算法法的時時間復復雜度度2.2線性表表類型型的實實現(xiàn)——順序映映像用一組組地址址連續(xù)續(xù)的存存儲單單元依依次存存放線線性表表中的的數(shù)據(jù)據(jù)元素素a1a2ai-1aian…………線性表表的起起始地地址稱作線線性表表的基基地址址線性表表的起起始地地址稱作線線性表表的基基地址址以“存存儲位位置相相鄰””表示示有序序?qū)?lt;ai-1,ai>即：LOC(ai)=LOC(ai-1)+C所有數(shù)數(shù)據(jù)元元素的的存儲儲位置置均取取決于于第一一個數(shù)數(shù)據(jù)元元素的的存儲儲位置置LOC(ai)=LOC(a1)+(i-1)×C一個數(shù)數(shù)據(jù)元元素所所占存存儲量量基地址即在順順序存存儲結(jié)結(jié)構(gòu)中中，線線性表表中每每一個個數(shù)據(jù)據(jù)元素素在計計算機機存儲儲空間間中的的存儲儲地址址由該該元素素在線線性表表中的的序號號惟一一確定定。一一般來來說，，長度度為n的線線性性表表(a1，a2，…，an)在計計算算機機中中的的結(jié)結(jié)構(gòu)構(gòu)如如下下：：順序序存存儲儲結(jié)結(jié)構(gòu)構(gòu)的的特特點點（1）利利用用數(shù)數(shù)據(jù)據(jù)元元素素的的存存儲儲位位置置表表示示線線性性表表中中相相鄰鄰數(shù)數(shù)據(jù)據(jù)元元素素之之間間的的前前后后關(guān)關(guān)系系，，即即線線性性表表的的邏邏輯輯結(jié)結(jié)構(gòu)構(gòu)與與存存儲儲結(jié)結(jié)構(gòu)構(gòu)（（物物理理結(jié)結(jié)構(gòu)構(gòu)））一一致致；；（2）在在訪訪問問線線性性表表時時，，可可以以利利用用上上述述給給出出的的數(shù)數(shù)學學公公式式，，快快速速地地計計算算出出任任何何一一個個數(shù)數(shù)據(jù)據(jù)元元素素的的存存儲儲地地址址。。因因此此，，我我們們可可以以粗粗略略地地認認為為，，訪訪問問每每個個數(shù)數(shù)據(jù)據(jù)元元素素所所花花費費的的時時間間相相等等。。這這種種存存取取元元素素的的方方法法被被稱稱為為隨機機存存取取法法，使使用用這這種種存存取取方方法法的的存存儲儲結(jié)結(jié)構(gòu)構(gòu)被被稱稱為為隨機機存存儲儲結(jié)結(jié)構(gòu)構(gòu)。在具具體體實實現(xiàn)現(xiàn)時時，，一一般般用用高高級級語語言言中中的的數(shù)組組來對對應應連連續(xù)續(xù)的的存存儲儲空空間間。。設設最最多多可可存存儲儲MaxLen個元元素素，，在在C語言言中中可可用用數(shù)數(shù)組組data[MaxLen]來存存儲儲數(shù)數(shù)據(jù)據(jù)元元素素，，為為保保存存線線性性表表的的長長度度需需定定義義一一個個整整型型變變量量length。線線性性表表的的第第l，2，…，n個元元素素分分別別存存放放在在此此數(shù)數(shù)組組下下標標為為0，1，…，length-1數(shù)組組元元素素中中，，如如下下圖圖所所示示順序序映映像像的的C語言言描描述述#defineMaxLen80//線性性表表存存儲儲空空間間的的初初始始分分配配量量typedefintElemType//在實實際際應應用用中中，，將將ElemType定義義成成實實際際類類型型typedefstruct{ElemTypedata[MaxLen];//定義存儲儲表中元元素的數(shù)數(shù)組intlength;//當前長度度}SqList;sqListL;//定義表結(jié)結(jié)構(gòu)的變變量順序映像像的C#語言描述述publicclassSqList{privateintmaxSize;//順序表表的容量量privateint[]data;//數(shù)組，，用于存存儲數(shù)據(jù)據(jù)元素privateintlast;//指示順順序表最最后一個個元素的的位置publicintLast//最最后一個個數(shù)據(jù)元元素位置置屬性{get{returnlast;}}publicintMaxSize//最最大容量量{get{returnmaxSize;}set{maxSize=value;}}publicSqList(intsize)//構(gòu)造造器{data=newint[size];maxSize=size;last=-1;}}線性表在在順序存存儲結(jié)構(gòu)構(gòu)下的運運算實現(xiàn)現(xiàn)1．初始始化順序序表Initlist(L)的實現(xiàn)現(xiàn)順序表的的初始化化即構(gòu)造造一個空空表，順順序表L是否為為空取決決于其元元素個數(shù)數(shù)是否為為0，因因此，要要將表L中的表表長度置置為0publicSqList(intsize)//構(gòu)造造器{data=newint[size];maxSize=size;last=-1;}該算法的的時間復復雜度為為O(1)2．求線線性表長長度Getlength(L)的實實現(xiàn)求線性表表的長度度算法如如下：publicintGetLength(){returnlast+1;}該算法的的時間復復雜度為為O(1)3．判斷斷線性表表是否為為空IsEmpty()的實實現(xiàn)判斷線性性表是否否為空算算法如下下：publicboolIsEmpty(){if(last==-1)returntrue;elsereturnfalse;}該算法的的時間復復雜度為為O(1)4．按序序號取元元素GetElem(L,i)的實實現(xiàn)按前面的的約定，，序號為為i的元元素存儲儲在數(shù)組組下標為為i-1的數(shù)組組元素中中，所以以可直接接從該數(shù)數(shù)組元素素中取得得值。i的有效效值應大大于等于于1和小小于等于于線性表表的實際際長度。。publicintGetElem(inti){if(IsEmpty()||(i<1)||(i>last+1)){Console.WriteLine("ListisEmptyorPositioniserror!");return0;}elsereturndata[i-1];}5．查找運運算LocateElem(L,e)的實現(xiàn)publicintLocate(intitem){if(IsEmpty()){Console.WriteLine("ListisEmpty!");return-1;}inti=0;for(i=0;i<=last;i++)if(item.Equals(i))break;if(i>last)return-1;returni+1;}要確定值值為e的元素在在L表中的位位置，需需要依次次比較各各元素。。當查詢詢到第一一個滿足足條件的的數(shù)據(jù)元元素時，，返回其其序號，，否則返返回-1，表示查查找失敗敗。算法復雜雜度：在查找過過程中，，數(shù)據(jù)元元素比較較次數(shù)最最少為1，最多為為n元素比較較次數(shù)的的平均值值為(n+1)/2時間復雜雜度為O(n)6．順序表表的插入入算法InsertElem(L,i,x)的實現(xiàn)順序表的的插入是是指在表表的第i個位置上上插入一一個值為為x的新元素素，插入入后使原原表長為為n的表：(a0，a1，…，ai-2，ai-1，ai，…，an-1)，成為表表長為n+1的表：(a0，a1，…，ai-2，x，ai-1，ai，…，an),i的取值范范圍為1≤i≤n+1。下圖表表示一個個順序表表中的數(shù)數(shù)組在進進行插入入運算前前后，數(shù)數(shù)據(jù)元素素在數(shù)組組中的下下標變化化。

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

ai-1

i+1

ai

i+2

ai+1┇┇

n

an-1

插入x插入前插入后

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

x

i+1

ai-1

i+2

ai┇┇

n+1

an-1

publicvoidInsert(intitem,inti){if(IsFull()){Console.WriteLine("TheListisfull!");return;}if(i<1||i>last+2){Console.WriteLine("Thepositioniserror!");return;}if(i==last+2)//若是是向最后后一個元元素之后后插入,直接插插入即可可data[last+1]=item;else//若若在中間間插入,則需要要將后面面的所有有元素一一一后撤撤{for(intj=last;j>=i-1;--j)data[j+1]=data[j];data[i-1]=item;}last++;}該算法的的時間主主要花費費在移動動數(shù)據(jù)元元素上，，移動個個數(shù)取決決于插入入位置i和表的的長度度n。所以以可以以用數(shù)數(shù)據(jù)元元素的的移動動操作作來估估計算算法的的時間間復雜雜度。。在第第i個位置置上插插入x，共需需要移移動n-i+1個元素素，i的取值值范圍圍為：：1≤i≤n+1，即有有n+1個位置置可以以插入入。當i=n+1時，不不需要要移動動結(jié)點點；當i=1時需要要移動動n個結(jié)點點。。由此可可以看看出，，算法法在最最好的的情況況下時時間復復雜性性為O(1)，最壞壞的時時間復復雜性性是O(n)。由于插插入的的位置置是隨隨機的的，因因此，，需要要分析析執(zhí)行行該算算法移移動數(shù)數(shù)據(jù)元元素的的平均均值。。設在在第i個位置置上作作插入入的概概率為為Pi，則平平均移移動數(shù)數(shù)據(jù)元元素的的次數(shù)數(shù)：假設表表中任任何位位置插插入概概率是是均等等的,即Pi=1/(n+1),Em=n/2由此可可以看看出，，在線線性表表上做做插入入操作作需要要移動動表中中一半半的數(shù)數(shù)據(jù)元元素，，當n較大時時，算算法的的效率率是比比較低低的，，所以以在線線性表表上進進行插插入操操作的的時間間復雜雜度為為Ｏ(n)。7．順序序表的的刪除除運算算ListDelete(L,i)的實現(xiàn)現(xiàn)順序表表的刪刪除運運算是是指將將表中中第i個元素素從線線性表表中去去掉，，原表表長為為n的線性性表(a1，a2，…，ai-1，ai，ai+1，…，an)。進行行刪除除以后后的線線性表表表長長變?yōu)闉閚-1的表(a1，a2，…，ai-1，ai+1，…，an)，i的取值值范圍圍為：：1≤i≤n。刪除刪除前前刪除后后

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

ai-1

i+1

ai

i+2

ai+1┇┇

n

an-1

1

a0

2

a1

3

a2┇┇

i-1

ai-2

i

ai

i+1

ai+1

i+2

ai+2┇┇

n-1

an-1

在線性性表上上完成成上述述運算算通過過以下下兩個個操作作來實實現(xiàn)：：(1)線性表表中第第i+1個至第第n個元素素（共共n-i個元素素）依依次向向前移移動一一個位位置。。將所所刪除除的元元素ai-1覆蓋掉掉，從從而保保證邏邏輯上上相鄰鄰的元元素物物理位位置也也相鄰鄰。(2)修改線線性表表長度度，使使其減減1。publicintDelete(inti){inttemp=newint();if(IsEmpty()){Console.WriteLine("TheListisempty!");returntemp;}if(i<1||i>last+1){Console.WriteLine("Positioniserror!");returntemp;}if(i==last+1)//如如果是最后后一個元素素，則直接接刪除即可可temp=data[last];else//若不是是最后一個個元素，則則刪除后須須將后面元元素一一前前移{temp=data[i-1];for(intj=i-1;j<last;++j)data[j]=data[j+1];}last--;returntemp;}刪除算法的的時間性能能分析：與插入運算算相同，刪刪除運算的的時間也主主要消耗在在移動表中中數(shù)據(jù)元素素上，刪除除第i個元素時，，其后面的的元素ai+1～an都要向前移移動一個位位置，共移移動了n-i個元素，所所以在等概概率的情況況下，在線線性表中刪刪除數(shù)據(jù)元元素所需移移動數(shù)據(jù)元元素的期望望值，即平平均移動數(shù)數(shù)據(jù)元素的的次數(shù)為：：由此可以看看出，在線線性表上刪刪除數(shù)據(jù)元元素時大約約需要移動動表中一半半的元素，，顯然該算算法的時間間復雜度為為Ｏ(n)。通常情況下下，我們認認為在線性性表中任何何位置刪除除元素是等等概率的，，即pi=1/n，則：【例2-1】利用線線性表的基基本運算，，編寫在線線性表A中中刪除線性性表B中出出現(xiàn)的元素素的算法。?！窘狻勘颈绢}的算法法思路是：：依次檢查查線性表B中的每個個元素，看看它是否在在線性表A中。若在在線性表A中，則將將其從A中中刪除。本題的算法法如下：staticpublicvoidDelete(SqListlistA,SqListlistB){for(inti=1;i<=listB.GetLength();i++){intx=listB.GetElem(i);//依次查查找ListB中的的值，存入入x中intp=listA.Locate(x);//判斷x是否在ListA中，若不不在返回-1，若在在返回位置置if(p!=-1)listA.Delete(p);}}線性表的順順序存儲結(jié)結(jié)構(gòu)中任意意數(shù)據(jù)元素素的存儲地地址可由公公式直接導導出，因此此順序存儲儲結(jié)構(gòu)的線線性表是可可以隨機存存取其中的的任意元素素。但是，順序序存儲結(jié)構(gòu)構(gòu)也有一些些不方便之之處，主要要表現(xiàn)在：：（1）數(shù)據(jù)元素素最大個數(shù)數(shù)需預先確確定，使得得高級程序序設計語言言編譯系統(tǒng)統(tǒng)需預先分分配相應的的存儲空間間；（2）插入與刪刪除運算的的效率很低低。為了保保持線性表表中的數(shù)據(jù)據(jù)元素順序序，在插入入操作和刪刪除操作時時需移動大大量數(shù)據(jù)。。對于插入入和刪除操操作頻繁的的線性表、、將導致系系統(tǒng)的運行行速度難以以提高。（3）存儲空間間不便于擴擴充。當一一個線性表表分配順序序存儲空間間后，若線線性表的存存儲空間已已滿，但還還需要插入入新的元素素，則會發(fā)發(fā)生“上溢溢”錯誤。。2.2線性表類型型的實現(xiàn)——鏈式映像線性表的順順序表示的的特點是用用物理位置置上的鄰接接關(guān)系來表表示結(jié)點間間的邏輯關(guān)關(guān)系，故可可以隨機存存取表中的的任一結(jié)點點；但在插插入和刪除除操作時需需移動大量量的結(jié)點。。為避免大量量結(jié)點的移移動，介紹紹線性表的的另一種存存儲方式:鏈式存儲結(jié)結(jié)構(gòu)，簡稱鏈表(LinkedList)。線性表的鏈鏈式存儲結(jié)結(jié)構(gòu)就是用用一組任意意的存儲單單元（可以以是不連續(xù)續(xù)的）存儲儲線性表的的數(shù)據(jù)元素素。對線性性表中的每每一個數(shù)據(jù)據(jù)元素，都都需用兩部部分來存儲儲：一部分分用于存放放數(shù)據(jù)元素素值，稱為為數(shù)據(jù)域；另一部分分用于存放放直接前驅(qū)驅(qū)或直接后后繼結(jié)點的的地址（指指針），稱稱為指針域，稱這種存存儲單元為為結(jié)點。鏈式存儲方方式可用于于表示線性性結(jié)構(gòu)，也也可用于表表示非線性性結(jié)構(gòu)。鏈式式存存儲儲結(jié)結(jié)構(gòu)構(gòu)是是利利用用任任意意的的存存儲儲單單元元來來存存放放線線性性表表中中的的元元素素，，存存儲儲數(shù)數(shù)據(jù)據(jù)的的單單元元在在內(nèi)內(nèi)存存中中可可以以連連續(xù)續(xù)，，也也可可以以零零散散分分布布。。由于于線線性性表表中中各各元元素素間間存存在在著著線線性性關(guān)關(guān)系系，，每每一一個個元元素素有有一一個個直直接接前前驅(qū)驅(qū)和和一一個個直直接接后后繼繼。。為為了了表表示示元元素素間間的的這這種種線線性性關(guān)關(guān)系系，，在在這這種種結(jié)結(jié)構(gòu)構(gòu)中中不不僅僅要要存存儲儲線線性性表表中中的的元元素素，，還還要要存存儲儲表表示示元元素素之之間間邏邏輯輯關(guān)關(guān)系系的的信信息息。。所所以以用用鏈鏈式式存存儲儲結(jié)結(jié)構(gòu)構(gòu)表表示示線線性性表表中中的的一一個個元元素素時時至至少少需需要要兩兩部部分分信信息息，，除除了了存存儲儲每每一一個個數(shù)數(shù)據(jù)據(jù)元元素素值值以以外外，，還還需需存存儲儲其其后后繼繼或或前前驅(qū)驅(qū)元元素素所所在在內(nèi)內(nèi)存存的的地地址址。。兩兩部部分分信信息息一一起起構(gòu)構(gòu)成成鏈鏈表表中中的的一一個個結(jié)結(jié)點點。。結(jié)結(jié)點點的的結(jié)結(jié)構(gòu)構(gòu)如如下下所所示示。。C#語語言言采采用用類的的嵌嵌套套數(shù)據(jù)據(jù)類類型型描描述述結(jié)結(jié)點點如如下下：：publicclassListNode{privateintdata;//數(shù)數(shù)據(jù)據(jù)域域privateListNodenext;//指指針針域域}在此此結(jié)結(jié)構(gòu)構(gòu)中中，，用用數(shù)數(shù)據(jù)據(jù)域域data存存儲儲線線性性表表中中數(shù)數(shù)據(jù)據(jù)元元素素。。指指針針域域next，，它它給給出出下下一一個個結(jié)結(jié)點點的的存存儲儲地地址址。。結(jié)點點的的指指針針域域?qū)⑺杏薪Y(jié)結(jié)點點按按線線性性表表的的邏邏輯輯次次序序鏈鏈接接成成一一個個整整體體，，形形成成一一個個鏈鏈表表。。由于于鏈鏈表表中中第第一一個個結(jié)結(jié)點點沒沒有有直直接接前前驅(qū)驅(qū)，，所所以以必必須須設設置置一一個頭頭指指針針head存儲儲第第一一個個結(jié)結(jié)點點的的地地址址。。最最后后一一個個結(jié)結(jié)點點沒沒有有直直接接后后繼繼，，其其指指針針域域應應為為空空指指針針，，C#語語言言用用NULL來來表表示示，，在在圖圖中中表表示示為為““∧”。。假設有一個線線性表為（A,B,C,D,E），存儲空間間具有10個存儲結(jié)點，，該線性表在在存儲空間中中的存儲情況況如下圖所示示。頭指針headABCDE47291∧(b)線性表的邏輯狀態(tài)從圖中可見，，每個結(jié)點的的存儲地址存存放在直接前前驅(qū)的指針域域中。鏈表這種順著著指針鏈依次次訪問數(shù)據(jù)元元素的特點，，表明鏈表是是一種順序存取結(jié)構(gòu)構(gòu)，只能順序操操作鏈表中元元素。不能像像順序表（數(shù)數(shù)組）那樣可可以按下標隨機存取。在鏈表存儲結(jié)結(jié)構(gòu)中，不要要求存儲空間間的連續(xù)性，，數(shù)據(jù)元素之之間的邏輯關(guān)關(guān)系由指針來來確定。由于于鏈式存儲的的靈活性，這這種存儲方式式既可用于表表示線性結(jié)構(gòu)構(gòu)，也可以用用來表示非線線性結(jié)構(gòu)。怎樣才能訪問問到數(shù)據(jù)元素素C？單向鏈表每個結(jié)點只有有一個指向后后繼的指針。。也就是說訪訪問數(shù)據(jù)元素素只能由鏈表表頭依次到鏈鏈表尾，而不不能做逆向訪訪問。稱這種種鏈表為單向向鏈表或線性性鏈表。這是是一種最簡單單的鏈表。單鏈表是由表表頭唯一確定定。（a）為帶頭結(jié)點點的空鏈(b)為帶頭結(jié)點的的單鏈表C語言描述單鏈鏈表：typedefcharElemType;typedefstructLNode{ElemTypedata;//結(jié)點值structLNode*next;//存儲下一個結(jié)結(jié)點的地址}LNode;typedefLNode*LinkList;LNode*p;LinkListhead;publicclassListNode{privateintdata;//數(shù)據(jù)域privateListNodenext;//指針域publicintData//數(shù)據(jù)域域?qū)傩詛get{returndata;}set{data=value;}}publicListNodeNext//指針域?qū)賹傩詛get{returnnext;}set{next=value;}}}C#語言描述單鏈鏈表的結(jié)點：：publicListNode(intval,ListNodep){//構(gòu)造一一個有數(shù)據(jù)域域和指針域的的普通節(jié)點data=val;next=p;}publicListNode(intval){//構(gòu)造一一個有數(shù)據(jù)域域但沒有指針針域的節(jié)點，，一般為線性性表的最后一一個元素data=val;next=null;}publicListNode(ListNodep){//構(gòu)造一一個沒有數(shù)據(jù)據(jù)域只有指針針域的節(jié)點，，一般用作線線性表的頭節(jié)節(jié)點data=0;next=p;}publicListNode(){//構(gòu)造一一個沒有數(shù)據(jù)據(jù)域，沒有指指針域的節(jié)點點，一般為構(gòu)構(gòu)造空線性表表時使用data=0;next=null;}重載概念：重載是是在一個類中中用相同的名名稱但是不同同的參數(shù)類型型創(chuàng)建一個以以上的過程、、實例構(gòu)造函函數(shù)或?qū)傩浴Ｖ剌d（overroad）：構(gòu)造函數(shù)數(shù)的重載，需需要遵守一下下的規(guī)則：方法的名稱一一定要一樣傳遞的參數(shù)類類型一定要不不一樣C#語言描述單鏈鏈表：publicclassLinkList{privateListNodehead;//單鏈鏈表的頭引用用//構(gòu)造函數(shù)數(shù)publicLinkList()//求單鏈表表的長度publicintGetLength()//清空單鏈鏈表publicvoidClear()//判判斷斷單單鏈鏈表表是是否否為為空空publicboolIsEmpty()//將將單單鏈鏈表表中中的的第第i個個數(shù)數(shù)據(jù)據(jù)元元素素的的值值改改為為itempublicvoidPutElem(intitem,inti)//獲獲得得單單鏈鏈表表的的第第i個個數(shù)數(shù)據(jù)據(jù)元元素素publicintGetElem(inti)//獲獲得得第第i個個數(shù)數(shù)據(jù)據(jù)元元素素的的前前驅(qū)驅(qū)publicListNodePriorElem(inti)//獲獲得得第第i個個數(shù)數(shù)據(jù)據(jù)元元素素的的后后繼繼publicListNodeNextElem(inti)//查查找找運運算算，，查查找找數(shù)數(shù)值值為為item的的數(shù)數(shù)據(jù)據(jù)元元素素的的位位置置publicintLocateElem(intitem)//在在單單鏈鏈表表的的第第i個個數(shù)數(shù)據(jù)據(jù)節(jié)節(jié)點點的的位位置置前前插插入入一一個個值值為為item的的結(jié)結(jié)點點publicvoidInsert(intitem,inti)//刪刪除除單單鏈鏈表表的的第第i個個數(shù)數(shù)據(jù)據(jù)元元素素publicintDelete(inti)}由于于鏈鏈表表是是一一種種動動態(tài)態(tài)管管理理的的存存儲儲結(jié)結(jié)構(gòu)構(gòu)，，每每個個結(jié)結(jié)點點需需動動態(tài)態(tài)產(chǎn)產(chǎn)生生。。1．．初初始始化化鏈鏈表表Initlist(L)的的實實現(xiàn)現(xiàn)建立立一一個個空空的的帶帶頭頭結(jié)結(jié)點點的的單單鏈鏈表表。。所所謂謂空空鏈鏈表表就就是是指指表表長長為為0的的表表。。在在這這種種情情況況下下，，鏈鏈表表中中沒沒有有元元素素結(jié)結(jié)點點。。但但應應有有一一個個頭頭結(jié)結(jié)點點，，其其指指針針域域為為空空。。publicLinkList(){head=newListNode();}2．．求求線線性性表表長長度度Getlength(L)的的實實現(xiàn)現(xiàn)設計思路路：設置置一個初初值為0的計數(shù)數(shù)器變量量和一個個跟蹤鏈鏈表結(jié)點點的指針針p。初初始時p指向鏈鏈表中的的頭結(jié)點點，然后后順著next域依次次指向每每個結(jié)點點，每指指向一個個結(jié)點計計數(shù)器變變量加1。當p的指針針域為Null時，結(jié)結(jié)束該過過程。publicintGetLength(){ListNodep=head;intlength=0;while(p.Next!=null){length++;p=p.Next;}returnlength;}時間復雜雜度為O(n)3．按序序號取元元素GetElem(L,i)的實實現(xiàn)根據(jù)前面面的討論論，對單單鏈表中中的結(jié)點點只能順順序存取取，即訪訪問前一一個結(jié)點點后才能能接著訪訪問后一一個結(jié)點點。所以以要訪問問單鏈表表中第i個元素素值，必必須從頭頭指針開開始遍歷歷鏈表，，依次訪訪問每個個結(jié)點，，直到訪訪問到第第i個結(jié)結(jié)點為止止。同順順序表一一樣，也也需注意意存取的的位置是是否有效效。publicintGetElem(inti){if(IsEmpty()||i<1||i>GetLength()){//首首先判斷斷線性表表是否為為空，i的位置置是否正正確Console.WriteLine("ListisEmptyorPositioniserror!");return0;}ListNodep=head;for(intj=1;j<=i;j++)p=p.Next;returnp.Data;}時間復雜雜度為O(n)4．查找運運算LocateElem(intitem)的實現(xiàn)設計思路路：設置置一個跟跟蹤鏈表表結(jié)點的的指針p，初始時時p指向鏈表表中的頭頭結(jié)點，，然后順順著next域依次指指向每個個結(jié)點，，每指向向一個結(jié)結(jié)點就判判斷其值值是否等等于item，若是則則返回該該結(jié)點地地址。否否則繼續(xù)續(xù)往后搜搜索，直直到p.Next為Null，表示鏈鏈表結(jié)束束，返回回0。publicintLocateElem(intitem){if(IsEmpty()){//首首先判斷斷是否為為空鏈表表Console.WriteLine("ListisEmpty!");return0;}ListNodep=head;intj=1;intlen=GetLength();//獲獲得鏈鏈表長長度for(j=1;j<=len;j++)p=p.Next;//依次次訪問問每一一個結(jié)結(jié)點returnp.Data;}時間復復雜度度為O(n)5．鏈表表的插插入算算法ListInsert(inti,intitem)的實現(xiàn)現(xiàn)單鏈表表結(jié)點點的插插入是是利用用修改改結(jié)點點指針針域的的值，，使其其指向向新的的鏈接接位置置來完完成的的插入入操作作，而而無需需移動動任何何元素素。假定在在鏈表表中值值為ai的結(jié)點點之前前插入入一個個新結(jié)結(jié)點，，要完完成這這種插插入必必須首首先找找到所所插位位置的的前一一個結(jié)結(jié)點，，再進進行插插入。。假設設指針針q指向待待插位位置的的前驅(qū)驅(qū)結(jié)點點，指指針s指向新新結(jié)點點，則則完成成該操操作的的過程程如下下圖所所示。。a1a2…………ai-1ai……an^head1、首先先找到到插入入位置置2、申請請新節(jié)節(jié)點s，數(shù)據(jù)據(jù)域置置為x3、修改改指針針域，，將s插入到到線性性表中中qpxspublicvoidInsert(intitem,inti){if(i<1||i>(GetLength()+1)){Console.WriteLine("Positioniserror!");return;}ListNodeq=head;ListNodeInVal=newListNode(item);ListNodes=newListNode();intj=1;for(j=1;j<i&&q.Next!=null;j++)//找到要要插入元素素的前一個個元素//當q.Next為空時，，表示在最最后一個元元素之后插插入新元素素q=q.Next;if(j==i){s=q.Next;q.Next=InVal;InVal.Next=s;}elseq.Next=InVal;}6．鏈表的刪刪除運算ListDelete(inti)的實現(xiàn)要刪除鏈表表中第i個結(jié)點，首首先在單鏈鏈表中找到到刪除位置置前一個結(jié)結(jié)點，并用用指針q指向它，指指針p指向要刪除除的結(jié)點。。將q的指針域修修改為待刪刪除結(jié)點p的后繼結(jié)點點的地址。。如下圖所所示：x=p->data；(b)返回被刪除結(jié)點數(shù)據(jù)xxpheada1a2...ai-1q...aian∧(a)找到刪除位置pheada1...(c)修改指針域，將結(jié)點p刪除qai-1pai...an∧ai+1①②關(guān)鍵語句：q->next=p->next；publicListNodeDelete(inti){if(IsEmpty()||i<1||i>GetLength()){Console.WriteLine("ListisEmptyorPositioniserror!");return0;}ListNodep=head;intj=1;while(j<i)//查找找要刪除的的元素的前前一個數(shù)據(jù)據(jù)元素{p=p.Next;j++;}ListNodes=p.Next;p.Next=s.Next;returns;}7．鏈表元元素遍歷運運算ListTraverse(L)的實實現(xiàn)從第一個結(jié)結(jié)點開始，，順著指針針鏈依次訪訪問每一個個結(jié)點。publicvoidTraverse(){ListNodep=head.Next;intlen=1;while(p!=null){Console.WriteLine("第{0}個數(shù)數(shù)據(jù)元素的的值為{1}",len,p.Data);p=p.Next;len++;}}【例2-1】將兩個個單鏈表首首尾相接進進行合并，，La為第第一個單鏈鏈表頭指針針，Lb為為第二個單單鏈表頭指指針，合并并后La為為新鏈表的的頭指針。?！窘狻克惴ǚㄋ悸罚簩蓚€單循循環(huán)鏈表La，Lb進行的連連接操作，，是將Lb的第一個個數(shù)據(jù)結(jié)點點接到La的尾部。。操作時需需要從La的頭指針針開始找到到La的尾尾結(jié)點。staticpublicvoidMergeList(LinkListlistA,LinkListlistB){ListNodep=listA.Head;while(p.Next!=null)p=p.Next;//找到到listA中的最最后一個結(jié)結(jié)點p.Next=listB.Head.Next;//listA的的將最后一一個結(jié)點的的指針域指指向listB的第第一個結(jié)點點}循環(huán)鏈表在單鏈表中中，最后一一個結(jié)點的的指針域為為空（NULL）。訪問單單鏈表中任任何數(shù)據(jù)只只能從鏈表表頭開始順順序訪問，，而不能進進行任何位位置的隨機機查詢訪問問。如要查查詢的結(jié)點點在鏈表的的尾部也需需遍歷整個個鏈表。所所以單鏈表表的應用受受到一定的的限制。循環(huán)鏈表(CircularLinkedList)是另一種形形式的鏈式式存儲結(jié)構(gòu)構(gòu)。它將單單鏈表中最最后一個結(jié)結(jié)點的指針針指向鏈表表的頭結(jié)點點，使整個個鏈表頭尾尾相接形成成一個環(huán)形形。這樣，，從鏈表中中任一結(jié)點點出發(fā)，順順著指針鏈鏈都可找到到表中其它它結(jié)點。循循環(huán)鏈表的的最大特點點是不增加加存儲量，，只是簡單單地改變一一下最后一一個結(jié)點的的指針指向向，就可以以使操作更更加方便靈靈活。帶頭結(jié)點的的單循環(huán)鏈鏈表的操作作算法和帶帶頭結(jié)點的的單鏈表的的操作算法法很相似，，差別僅在在于算法中中的循環(huán)條條件不同。。在循環(huán)單單鏈表上實實現(xiàn)上述基基本運算的的改動如下下：1．初始化鏈鏈表initlist(L)創(chuàng)建的頭結(jié)結(jié)點指針域域next不為空，而而是指向自自身，L->next=L2．求線性表表長度Getlength(L)函數(shù)、查找找運算LocateElem(L,x)函數(shù)、鏈表表元素輸出出運算ListTraverse(L)函數(shù)中，循循環(huán)遍歷是是否進行的的條件由p!=NULL改為p!=L;在循環(huán)鏈表表中，除了了有頭指針針head外，有時還還可加上一一個尾指針針tail。尾指針tail指向最后一一結(jié)點，沿沿最后一個個結(jié)點的指指針又可立立即找到鏈鏈表的第一一個結(jié)點。。在實際應應用中，使使用尾指針針來代替頭頭指針進行行某些操作作往往會更更簡單。publicclassCirLinkList{privateListNodehead;//