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

第二章線性表線性結(jié)構(gòu)構(gòu)是一個數(shù)據(jù)據(jù)元素的的有序（次次序）集線性表的的基本特特征存在惟一一的一個個被稱做做“第一個個”的數(shù)據(jù)元元素；存在惟一一的一個個被稱做做“最后一一個”的數(shù)據(jù)元元素；除第一個個之外，，集合中中的每個個數(shù)據(jù)元元素均只有一個個前驅(qū)；除最后一一個之外外，集合合中的每每個數(shù)據(jù)據(jù)元素均均只有一個個后繼。2.1線性表的的類型定定義2.2線性表類類型的實實現(xiàn)——順序映像像2.3線性表類類型的實實現(xiàn)——鏈式映像像2.4一元多項項式的表表示抽象數(shù)據(jù)據(jù)類型線性表的定義ADTList{數(shù)據(jù)對象象：D={ai|aiElemSeti=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)構(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ù)數(shù)據(jù)元素素的位序序。若不不存在這這樣的元元素，則則返回0ListTraverse((L,visit()))操作結(jié)果果：遍歷歷線性表表L，對每個個元素執(zhí)執(zhí)行函數(shù)數(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假設(shè)有兩兩個集合合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);;//設(shè)置空的的線性表表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);;//設(shè)置空的的線性表表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設(shè)La=((a1,….,,ai,….,,an)Lb=((b1,….,,bj,….,,bn)Lc=((c1,….,,ck,….,,cm+n)則ck中的k為1，2，……m++n

1、分別從從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)構(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ù)元元素GetElem(LA,i,,ai)),GetElem((LB,,i,bi)比較ai和bi是否相等等，若相相等繼續(xù)續(xù)取第i+1個數(shù)據(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ù)續(xù)取第i+1個數(shù)據(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)的的元素。。要求：(1)、用學到到的線性性表抽象象數(shù)據(jù)類類型中提提供的操操作編寫寫算法，，完成上上述兩題題功能。。(2)、分析所所寫算法法的時間間復雜度度2.2線性表類類型的實實現(xiàn)——順序映像像用一組地地址連續(xù)續(xù)的存儲儲單元依依次存放放線性表表中的數(shù)數(shù)據(jù)元素素a1a2ai-1aian…………線性表的的起始地地址稱作線性性表的基基地址線性表的的起始地地址稱作線性性表的基基地址以“存儲儲位置相相鄰”表表示有序序?qū)?lt;ai-1,ai>即：LOC((ai)=LOC(ai-1)+C所有數(shù)據(jù)據(jù)元素的的存儲位位置均取取決于第第一個數(shù)數(shù)據(jù)元素素的存儲儲位置LOC((ai)=LOC(a1)+((i--1)××C一個數(shù)據(jù)據(jù)元素所所占存儲儲量基地址即在順序序存儲結(jié)結(jié)構(gòu)中，，線性表表中每一一個數(shù)據(jù)據(jù)元素在在計算機機存儲空空間中的的存儲地地址由該該元素在在線性表表中的序序號惟一一確定。。一般來來說，長長度為n的線性表表(a1，a2，…，an)在計算機機中的結(jié)結(jié)構(gòu)如下下：順序存儲儲結(jié)構(gòu)的的特點（1）利用數(shù)數(shù)據(jù)元素素的存儲儲位置表表示線性性表中相相鄰數(shù)據(jù)據(jù)元素之之間的前前后關(guān)系系，即線線性表的的邏輯結(jié)結(jié)構(gòu)與存存儲結(jié)構(gòu)構(gòu)（物理理結(jié)構(gòu)））一致；；（2）在訪問問線性表表時，可可以利用用上述給給出的數(shù)數(shù)學公式式，快速速地計算算出任何何一個數(shù)數(shù)據(jù)元素素的存儲儲地址。。因此，，我們可可以粗略略地認為為，訪問問每個數(shù)數(shù)據(jù)元素素所花費費的時間間相等。。這種存存取元素素的方法法被稱為為隨機存取取法，使用這這種存取取方法的的存儲結(jié)結(jié)構(gòu)被稱稱為隨機存儲儲結(jié)構(gòu)。在具體實實現(xiàn)時，，一般用用高級語語言中的的數(shù)組來對應(yīng)連連續(xù)的存存儲空間間。設(shè)最最多可存存儲MaxLen個元素，，在C語言中可可用數(shù)組組data[MaxLen]來存儲數(shù)數(shù)據(jù)元素素，為保保存線性性表的長長度需定定義一個個整型變變量length。線性表表的第l，2，…，n個元素分分別存放放在此數(shù)數(shù)組下標標為0，1，…，length--1數(shù)組元素素中，如如下圖所所示順序映像像的C語言描述述#defineMaxLen80//線性表存存儲空間間的初始始分配量量typedefintElemType//在實際應(yīng)應(yīng)用中，，將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的有效效值應(yīng)大大于等于于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ù)據(jù)據(jù)元素的的平均值值。設(shè)在在第i個位置上上作插入入的概率率為Pi，則平均均移動數(shù)數(shù)據(jù)元素素的次數(shù)數(shù)：假設(shè)表中中任何位位置插入入概率是是均等的的,即Pi=1/((n++1),Em==n//2由此可以以看出，，在線性性表上做做插入操操作需要要移動表表中一半半的數(shù)據(jù)據(jù)元素，，當n較大時，，算法的的效率是是比較低低的，所所以在線線性表上上進行插插入操作作的時間間復雜度度為Ｏ(n)。7．順序表表的刪除除運算ListDelete(L,,i)的實現(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)現(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ù)數(shù)據(jù)元素素的期望望值，即即平均移移動數(shù)據(jù)據(jù)元素的的次數(shù)為為：由此可以以看出，，在線性性表上刪刪除數(shù)據(jù)據(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é)構(gòu)構(gòu)中任意意數(shù)據(jù)元元素的存存儲地址址可由公公式直接接導出，，因此順順序存儲儲結(jié)構(gòu)的的線性表表是可以以隨機存存取其中中的任意意元素。。但是，順順序存儲儲結(jié)構(gòu)也也有一些些不方便便之處，，主要表表現(xiàn)在：：（1）數(shù)據(jù)元元素最大大個數(shù)需需預先確確定，使使得高級級程序設(shè)設(shè)計語言言編譯系系統(tǒng)需預預先分配配相應(yīng)的的存儲空空間；（2）插入與與刪除運運算的效效率很低低。為了了保持線線性表中中的數(shù)據(jù)據(jù)元素順順序，在在插入操操作和刪刪除操作作時需移移動大量量數(shù)據(jù)。。對于插插入和刪刪除操作作頻繁的的線性表表、將導導致系統(tǒng)統(tǒng)的運行行速度難難以提高高。（3）存儲空空間不便便于擴充充。當一一個線性性表分配配順序存存儲空間間后，若若線性表表的存儲儲空間已已滿，但但還需要要插入新新的元素素，則會會發(fā)生““上溢””錯誤。。2.2線性表類類型的實實現(xiàn)——鏈式映像像線性表的的順序表表示的特特點是用用物理位位置上的的鄰接關(guān)關(guān)系來表表示結(jié)點點間的邏邏輯關(guān)系系，故可可以隨機機存取表表中的任任一結(jié)點點；但在在插入和和刪除操操作時需需移動大大量的結(jié)結(jié)點。為避免大大量結(jié)點點的移動動，介紹紹線性表表的另一一種存儲儲方式:鏈式存儲儲結(jié)構(gòu)，簡稱鏈表(LinkedList))。線性表的的鏈式存存儲結(jié)構(gòu)構(gòu)就是用用一組任任意的存存儲單元元（可以以是不連連續(xù)的））存儲線線性表的的數(shù)據(jù)元元素。對對線性表表中的每每一個數(shù)數(shù)據(jù)元素素，都需需用兩部部分來存存儲：一一部分用用于存放放數(shù)據(jù)元元素值，，稱為數(shù)據(jù)域；另一部部分用于于存放直直接前驅(qū)驅(qū)或直接接后繼結(jié)結(jié)點的地地址（指指針），，稱為指針域，稱這種種存儲單單元為結(jié)點。鏈式存儲儲方式可可用于表表示線性性結(jié)構(gòu)，，也可用用于表示示非線性性結(jié)構(gòu)。。鏈式存儲儲結(jié)構(gòu)是是利用任任意的存存儲單元元來存放放線性表表中的元元素，存存儲數(shù)據(jù)據(jù)的單元元在內(nèi)存存中可以以連續(xù)，，也可以以零散分分布。由于線性性表中各各元素間間存在著著線性關(guān)關(guān)系，每每一個元元素有一一個直接接前驅(qū)和和一個直直接后繼繼。為了了表示元元素間的的這種線線性關(guān)系系，在這這種結(jié)構(gòu)構(gòu)中不僅僅要存儲儲線性表表中的元元素，還還要存儲儲表示元元素之間間邏輯關(guān)關(guān)系的信信息。所所以用鏈鏈式存儲儲結(jié)構(gòu)表表示線性性表中的的一個元元素時至至少需要要兩部分分信息，，除了存存儲每一一個數(shù)據(jù)據(jù)元素值值以外，，還需存存儲其后后繼或前前驅(qū)元素素所在內(nèi)內(nèi)存的地地址。兩兩部分信信息一起起構(gòu)成鏈鏈表中的的一個結(jié)結(jié)點。結(jié)結(jié)點的結(jié)結(jié)構(gòu)如下下所示。。C#語言言采用類的嵌套套數(shù)據(jù)類型型描述結(jié)結(jié)點如下下：publicclassListNode{privateintdata;////數(shù)據(jù)域域privateListNodenext;;///指針針域}在此結(jié)構(gòu)構(gòu)中，用用數(shù)據(jù)域域data存儲儲線性表表中數(shù)據(jù)據(jù)元素。。指針針域next，，它給出出下一個個結(jié)點的的存儲地地址。結(jié)點的指指針域?qū)⑺薪Y(jié)結(jié)點按線線性表的的邏輯次次序鏈接接成一個個整體，，形成一一個鏈表表。由于鏈表表中第一一個結(jié)點點沒有直直接前驅(qū)驅(qū)，所以以必須設(shè)設(shè)置一個頭指針針head存儲第一一個結(jié)點點的地址址。最后后一個結(jié)結(jié)點沒有有直接后后繼，其其指針域域應(yīng)為空空指針，，C#語語言用NULL來表示示，在圖圖中表示示為“∧”。假設(shè)有一一個線性性表為（（A,B,,C,D,E），存儲儲空間具具有10個存儲結(jié)結(jié)點，該該線性表表在存儲儲空間中中的存儲儲情況如如下圖所所示。頭指針headABCDE47291∧(b)線性表的邏輯狀態(tài)從圖中可可見，每每個結(jié)點點的存儲儲地址存存放在直直接前驅(qū)驅(qū)的指針針域中。。

鏈表這種種順著指指針鏈依依次訪問問數(shù)據(jù)元元素的特特點，表表明鏈表表是一種種順序存取取結(jié)構(gòu)，只能順順序操作作鏈表中中元素。。不能像像順序表表（數(shù)組組）那樣樣可以按按下標隨機存取。在鏈表存存儲結(jié)構(gòu)構(gòu)中，不不要求存存儲空間間的連續(xù)續(xù)性，數(shù)數(shù)據(jù)元素素之間的的邏輯關(guān)關(guān)系由指指針來確確定。由由于鏈式式存儲的的靈活性性，這種種存儲方方式既可可用于表表示線性性結(jié)構(gòu)，，也可以以用來表表示非線線性結(jié)構(gòu)構(gòu)。怎樣才能能訪問到到數(shù)據(jù)元元素C？單向鏈表表每個結(jié)點點只有一一個指向向后繼的的指針。。也就是是說訪問問數(shù)據(jù)元元素只能能由鏈表表頭依次次到鏈表表尾，而而不能做做逆向訪訪問。稱稱這種鏈鏈表為單單向鏈表表或線性性鏈表。。這是一一種最簡簡單的鏈鏈表。單鏈表是是由表頭頭唯一確確定。（a）為帶頭頭結(jié)點的的空鏈(b)為帶頭結(jié)結(jié)點的單單鏈表C語言描述述單鏈表表：typedefcharElemType;;typedefstructLNode{ElemTypedata;//結(jié)點值structLNode**next;;//存儲下一一個結(jié)點點的地址址}LNode;;typedefLNode*LinkList;LNode**p;LinkListhead;publicclassListNode{privateintdata;////數(shù)據(jù)域域privateListNodenext;;///指針針域publicintData///數(shù)數(shù)據(jù)域?qū)賹傩詛get{{returndata;}}set{{data=value;;}}publicListNodeNext///指針域域?qū)傩詛get{{returnnext;}}set{{next=value;;}}}C#語言描述述單鏈表表的結(jié)點點：publicListNode((intval,ListNodep){//構(gòu)構(gòu)造一個個有數(shù)據(jù)據(jù)域和指指針域的的普通節(jié)節(jié)點data=val;next=p;}publicListNode((intval){//構(gòu)構(gòu)造一個個有數(shù)據(jù)據(jù)域但沒沒有指針針域的節(jié)節(jié)點，一一般為線線性表的的最后一一個元素素data=val;next=null;}publicListNode((ListNodep){//構(gòu)構(gòu)造一個個沒有數(shù)數(shù)據(jù)域只只有指針針域的節(jié)節(jié)點，一一般用作作線性表表的頭節(jié)節(jié)點data=0;next=p;}publicListNode((){//構(gòu)構(gòu)造一個個沒有數(shù)數(shù)據(jù)域，，沒有指指針域的的節(jié)點，，一般為為構(gòu)造空空線性表表時使用用data=0;next=null;}重載概念：重重載是在在一個類類中用相相同的名名稱但是是不同的的參數(shù)類類型創(chuàng)建建一個以以上的過過程、實實例構(gòu)造造函數(shù)或或?qū)傩浴Ｖ剌d（overroad）：構(gòu)造造函數(shù)的的重載，，需要遵遵守一下下的規(guī)則則：方法的名名稱一定定要一樣樣傳遞的參參數(shù)類型型一定要要不一樣樣C#語言描述述單鏈表表：publicclassLinkList{privateListNodehead;;//單單鏈表的的頭引用用//構(gòu)造造函數(shù)publicLinkList(()//求單單鏈表的的長度publicintGetLength())//清空空單鏈表表publicvoidClear())//判斷斷單鏈表表是否為為空publicboolIsEmpty()//將單單鏈表中中的第i個數(shù)據(jù)據(jù)元素的的值改為為itempublicvoidPutElem(intitem,inti)//獲得得單鏈表表的第i個數(shù)據(jù)據(jù)元素publicintGetElem((inti))//獲得得第i個個數(shù)據(jù)元元素的前前驅(qū)publicListNodePriorElem(inti)//獲得得第i個個數(shù)據(jù)元元素的后后繼publicListNodeNextElem((inti))//查找找運算，，查找數(shù)數(shù)值為item的數(shù)據(jù)據(jù)元素的的位置publicintLocateElem((intitem))//在單單鏈表的的第i個個數(shù)據(jù)節(jié)節(jié)點的位位置前插插入一個個值為item的結(jié)點點publicvoidInsert((intitem,,inti)//刪除除單鏈表表的第i個數(shù)據(jù)據(jù)元素publicintDelete(inti)}由于鏈表表是一種種動態(tài)管管理的存存儲結(jié)構(gòu)構(gòu)，每個個結(jié)點需需動態(tài)產(chǎn)產(chǎn)生。1．初始始化鏈表表Initlist((L)的的實現(xiàn)建立一個個空的帶帶頭結(jié)點點的單鏈鏈表。所所謂空鏈鏈表就是是指表長長為0的的表。在在這種情情況下，，鏈表中中沒有元元素結(jié)點點。但應(yīng)應(yīng)有一個個頭結(jié)點點，其指指針域為為空。publicLinkList((){head=newListNode();;}2．求線線性表長長度Getlength(L)的實實現(xiàn)設(shè)計思路路：設(shè)置置一個初初值為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)設(shè)計思路路：設(shè)置置一個跟跟蹤鏈表表結(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é)點點returnp.Data;}時間復雜雜度為O(n))5．鏈表的的插入算算法ListInsert(inti,intitem)的實現(xiàn)單鏈表結(jié)結(jié)點的插插入是利利用修改改結(jié)點指指針域的的值，使使其指向向新的鏈鏈接位置置來完成成的插入入操作，，而無需需移動任任何元素素。假定在鏈鏈表中值值為ai的結(jié)點之之前插入入一個新新結(jié)點，，要完成成這種插插入必須須首先找找到所插插位置的的前一個個結(jié)點，，再進行行插入。。假設(shè)指指針q指向待插插位置的的前驅(qū)結(jié)結(jié)點，指指針s指向新結(jié)結(jié)點，則則完成該該操作的的過程如如下圖所所示。a1a2…………ai-1ai……an^head1、首先找找到插入入位置2、申請新新節(jié)點s，數(shù)據(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é)點點，并用用指針q指向它，，指針p指向要刪刪除的結(jié)結(jié)點。將將q的指針域域修改為為待刪除除結(jié)點p的后繼結(jié)結(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ù)數(shù)據(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ù)據(jù)結(jié)點接接到La的尾部部。操作作時需要要從La的頭指指針開始始找到La的尾尾結(jié)點。。staticpublicvoidMergeList(LinkListlistA,LinkListlistB){ListNodep=listA..Head;while((p.Next!==null))p=p.Next;///找找到listA中的最最后一個個結(jié)點p.Next==listB.Head.Next;;//listA的將將最后一一個結(jié)點點的指針針域指向向listB的的第一個個結(jié)點}循環(huán)鏈表表在單鏈表表中，最最后一個個結(jié)點的的指針域域為空（（NULL）。訪問問單鏈表表中任何何數(shù)據(jù)只只能從鏈鏈表頭開開始順序序訪問，，而不能能進行任任何位置置的隨機機查詢訪訪問。如如要查詢詢的結(jié)點點在鏈表表的尾部部也需遍遍歷整個個鏈表。。所以單單鏈表的的應(yīng)用受受到一定定的限制制。循環(huán)鏈表表(CircularLinkedList))是另一種種形式的的鏈式存存儲結(jié)構(gòu)構(gòu)。它將將單鏈表表中最后后一個結(jié)結(jié)點的指指針指向向鏈表的的頭結(jié)點點，使整整個鏈表表頭尾相相接形成成一個環(huán)環(huán)形。這這樣，從從鏈表中中任一結(jié)結(jié)點出發(fā)發(fā)，順著著指針鏈鏈都可找找到表中中其它結(jié)結(jié)點。循循環(huán)鏈表表的最大大特點是是不增加加存儲量量，只是是簡單地地改變一一下最后后一個結(jié)結(jié)點的指指針指向向，就可可以使操操作更加加方便靈靈活。帶頭結(jié)點點的單循循環(huán)鏈表表的操作作算法和和帶頭結(jié)結(jié)點的單單鏈表的的操作算算法很相相似，差差別僅在在于算法法中的循循環(huán)條件件不同。。在循環(huán)環(huán)單鏈表表上實現(xiàn)現(xiàn)上述基基本運算算的改動動如下：：1．初始化化鏈表initlist(L)創(chuàng)建的頭頭結(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é)結(jié)點。在在實際應(yīng)應(yīng)用中，，使用尾尾指針來來代替頭頭指針進進行某些些操作往往往會更更簡單。。publicclassCirLinkList{privateListNodehead;;//循循環(huán)鏈表表的頭引引用privateListNodetail;;//循循環(huán)鏈表表的尾引引用publicListNodeHead///頭引引用屬性性{get{{returnhead;}}set{{head=value;;}}publicListNodeTail///尾引用用屬性{get{{returntail;}}set{{tail=value;;}}}【例2-2】將兩個循循環(huán)鏈表表首尾相相接進行行合并，，La為第一個個循環(huán)鏈鏈表表尾尾指針，，Lb為第二個