線性結(jié)構(gòu)[教資材料]

1、線性結(jié)構(gòu)這里將討論一些基本抽象數(shù)據(jù)類型線性結(jié)構(gòu)。所謂基本，只是相對而言，這些數(shù)據(jù)類型是最基本，最簡單的，并且是實現(xiàn)其他抽象數(shù)據(jù)類型的基礎(chǔ)。在下面的討論中，首先我們將給出各種基本數(shù)據(jù)結(jié)構(gòu)（ADT）的數(shù)學(xué)性質(zhì)，然后在其數(shù)學(xué)模型上定義一組運算，最后將討論如何利用基本的數(shù)據(jù)類型（數(shù)組、指針、記錄等）來具體實現(xiàn)各種ADT。下面您將了解到以下常見的基本抽象數(shù)據(jù)類型的ADT操作以及這些操作用不同數(shù)據(jù)描述方法的具體實現(xiàn)：表的定義和性質(zhì)一、表的定義表是由n(n0)個同一類型的元素（結(jié)點）a1,a2,an組成的有限序列。其中，元素的個數(shù)n定義為表的長度。當(dāng)n=0時稱為空表。當(dāng)nl時，我們說元素ai位于該表的第i個

2、位置，或稱ai是表中第i個元素，i=1,2,，n。根據(jù)各元素在表中的不同位置可以定義它們在表中的前后次序。我們稱元素ai在元素ai+1之前或ai是ai+1的前驅(qū)(i=1,2,n-1)。同時，我們也稱元素ai+1在元素ai之后，或ai+1是ai的后繼。另外，稱a1為表頭(head)，an為表尾(tail)。由于表的元素具有線性性質(zhì)，所以又稱為線性表。表是程序設(shè)計中使用得最頻繁的一種ADT，也是實現(xiàn)其他許多ADT的基礎(chǔ)。二、表的性質(zhì)從表的定義不難看出表具有以下數(shù)學(xué)性質(zhì)：除了表頭和表尾外，表中的每一個元素有且僅有唯一的前驅(qū)和唯一的后繼，表頭有且只有一個后繼，表尾有且只有一個前驅(qū)。注意：表和數(shù)組的區(qū)別

3、從概念上來看，表是一種抽象數(shù)據(jù)類型；數(shù)組是一種具體的數(shù)據(jù)結(jié)構(gòu)。從數(shù)學(xué)性質(zhì)上來看，表是一個二元關(guān)系R，R 當(dāng)且僅當(dāng)x是y的前驅(qū)；如果將該二元關(guān)系用關(guān)系圖（將每一個元素用一個點來表示，若x與y有關(guān)系則從x到y(tǒng)連一條有向線段）來表示，則得到的是一條單鏈a1a2an ，因此表也可以看成是特殊的圖或特殊的樹（每個節(jié)點有且僅有一個子節(jié)點）；而數(shù)組是從1.n的自然數(shù)集合到數(shù)組元素集合的一一映射，其中n是數(shù)組的長度，1.n中每一個自然數(shù)唯一地對應(yīng)著一個數(shù)組元素，反之亦然。所以數(shù)組可以用來實現(xiàn)映射。從物理性質(zhì)來看，數(shù)組中相鄰的元素是連續(xù)地存儲在內(nèi)存中的，或者對于程序員來說可以認(rèn)為它們是連續(xù)地存儲在內(nèi)存中的，數(shù)組

4、的存取對程序員來說是透明的；表只是一個抽象的數(shù)學(xué)結(jié)構(gòu)，并不具有具體的物理形式，表需要通過其它有具體物理形式的數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)。在表的具體實現(xiàn)中，表中相鄰的元素不一定存儲在連續(xù)的內(nèi)存空間中，除非表是用數(shù)組來實現(xiàn)的。對于數(shù)組，可以利用其下標(biāo)在一個操作內(nèi)隨機存取任意位置上的元素；對于表，只能根據(jù)當(dāng)前元素找到其前驅(qū)或后繼，因此要存取第i個位置上的元素，一般不能在一個操作內(nèi)實現(xiàn)，除非表是用數(shù)組實現(xiàn)的。在實現(xiàn)表時需要提供足夠的信息以便能夠通過表中元素的位置p來存取表中的元素。表中元素的位置p是指示表中元素位置的信息，通過對p進行處理（可能是從事某種函數(shù)運算計算出該元素在內(nèi)存中的位置，也可能從表頭開始，依次尋

5、找當(dāng)前元素的后繼，重復(fù)i次找到第i個位置的元素）可以得到表中元素在內(nèi)存中的物理位置，因此不能簡單地將位置p理解為類似數(shù)組下標(biāo)的自然數(shù)，實際上p可以是各種類型的變量，在數(shù)學(xué)上可將p定義為一個偏序集上的變量。在具體實現(xiàn)表及其運算時，應(yīng)區(qū)分p與p所表示的位置，以及該位置上的元素三者之間的不同含義。ADT表的操作表是一種非常簡便的結(jié)構(gòu)，我們可以根據(jù)需要改變表的長度，也可以在表中任何位置對元素進行訪問、插人或刪除等操作。我們還可以將兩個表連接成一個表，或把一個表拆成幾個表。表的結(jié)構(gòu)在信息檢索，程序設(shè)計語言的編譯等許多方面有廣泛的應(yīng)用。在表的數(shù)學(xué)模型上，我們還要定義一組運算，才能使這一數(shù)學(xué)模型成為一個抽象

6、數(shù)據(jù)類型表即ADT表。下面我們將給出一組典型的表運算。其中L是由類型為 TElement 的元素組成的一個表。x表示一個元素，p表示元素在表中的位置，其類型為TPosition。在表的不同實現(xiàn)方式下，TPosition可能有不同的類型定義，作為位置變量的p也可能有不同的含義。但是TPosition必須是一個偏序集，即任何兩個TPosition類型的變量x,y之間可以進行比較運算，且結(jié)果只有xy,x=y,x=y五種。下面我們將ADT表看作一個抽象類TList，L是該類的一個實體，ADT表的操作將定義成L的屬性和方法。ADT表的基本運算運算含義L.end為了方便，我們假定表L的結(jié)束元素an之后還有

7、一個位置，用屬性end的值來表示這個位置。該屬性的值為TPosition類型。L.piquet為了方便，我們假定表L的開始元素a1之前還有一個位置，該為值稱為哨兵位置，該位置上的元素稱為哨兵元素，用屬性Piquet的值來表示這個位置。該屬性的值為TPosition類型。L.first這是一個屬性，其值為表L中第一個元素的位置。當(dāng)L為空表時，值為L.end。L.last這是一個屬性，其值為表L中最后一個元素的位置。當(dāng)L為空表時，值為L.end。L.length返回表L的長度，即元素個數(shù)。L.IsEmpty()如果表L為空表(長度為0)則返回true，否則返回false。L.next(p)這是一個

8、函數(shù)，函數(shù)值為表L中位置p的后繼位置。如果p是L中結(jié)束元素的位置，則L.Next(p)=L.end。當(dāng)L中沒有位置p或p=L.end時，該運算無定義。L.prev(p)這是一個函數(shù)，函數(shù)值為表L中位置p的前驅(qū)位置。當(dāng)L中沒有位置p或p是L中開始元素的位置時，該運算無定義。L.get(p)這是一個函數(shù)，函數(shù)值為L中位置p處的元素。當(dāng)p=L.end或L中沒有位置p時，該運算無定義。L.put(x,p)該方法將元素x放置到表L的位置p處，如果位置p處已有元素，則用x取代該元素；如果p=L.end或者L中沒有位置p，則該運算無定義。L.insert(x,p)在表L的位置p處插入元素x，并將原來占據(jù)位置

9、p的元素及其后面的元素都向后推移一個位置。例如，設(shè)L為a1,a2,an，那么在執(zhí)行L.insert(x,p)后，表L變?yōu)閍1,a2,ap-1,x,ap,an 。若p為L.end，那么表L變?yōu)閍1,a2,an,x 。若表L中沒有位置p，則該運算無定義。L.delete(p)從表L中刪除位置p處的元素。例如，當(dāng)L為a1,a2,an時，執(zhí)行L.delete(p)后，L變?yōu)閍1,a2,ap-1,ap+1,an 。當(dāng)L中沒有位置p或p=L.end時，該運算無定義。L.locate(x)這是一個函數(shù)，函數(shù)值為元素x在L中的位置。若x在L中重復(fù)出現(xiàn)多次，則函數(shù)值為x第一次出現(xiàn)的位置。當(dāng)x不在L中時，函數(shù)值為

10、L.end。L.MakeEmpty這是一個將L變?yōu)榭毡淼姆椒?。L.print將表L中所有元素按位置的先后次序打印輸出。在表的數(shù)學(xué)模型上，定義了上述運算后，我們就定義了抽象數(shù)據(jù)類型（抽象類）TList。當(dāng)然，并非任何時候都需要同時執(zhí)行以上運算。在有些問題中只需要上述的一部分運算，因此也可以用上述運算的其中幾個來定義適合特殊目的的抽象數(shù)據(jù)類型。上述表的運算是一些最基本的運算，對于實際問題中涉及的關(guān)于表的更復(fù)雜的運算，可以用這些基本運算的組合來實現(xiàn)。例如，我們可以利用上述基本運算寫一個過程Purge，來清除一個表L中重復(fù)出現(xiàn)的元素。其中 p,q為TPosition類型的變量。=下面是Pascal語言

11、描述的代碼=Procedure Purge(var L:TList) var p,q:TPosition; begin 1 p:=L.first; 2 while pL.end do begin 3 q:=L.next(p); 4 while qL.end do 5 if Equal(L.get(p),L.get(q) then L.delete(q) 6 else q:=L.next(q); 7 p:=L.next(p); end end;=下面是C+語言描述的代碼=void Purge(TList& L) TPosition p,q;1. p=L.first();2. while (p!=

12、L.end() 3. q=L.next(p);4. while (q!=L.end() 5. if (Equal(L.get(p),L.get(q) L.delete(q);6. else q=L.next(q); 7. p=L.next(p); 上述過程的參數(shù)是一個表L，其元素類型為TElement。過程中用到的函數(shù)Equal(x,y)的兩個自變量均為TElement類型的元素。若x與y相同，則函數(shù)值為true，否則為false。這里所說的相同的含義要根據(jù)具體元素的類型來確定。例如，當(dāng)TElement為實型時，當(dāng)且僅當(dāng)x=y時Equal(x,y)=true。但是如果TElement是一個有用

13、戶帳號、姓名及地址等多個域的記錄，如:=下面是Pascal語言描述的代碼=type TElement=record ID: integer; Name: string20; Address: string50; end;=下面是C+語言描述的代碼=typedef struct TElement int ID; char Name20; char Address50;這時我們可以規(guī)定，Equal(x,y)=true當(dāng)且僅當(dāng)x.ID=y.ID，即x與y的帳號相同時成立；也可以規(guī)定3個域的值都相同時Equal(x,y)=true。在Purge過程中，變量p與q是表L的兩個位置變量，第2-7行是關(guān)于變

14、量p的循環(huán)。在循環(huán)中逐個檢查位置p后面的每一個位置q，如果這兩個位置上的元素相同，則將位置q的元素從表L中刪去。當(dāng)q遍歷了p后面的所有位置之后，p變?yōu)橄乱粋€位置，再開始新的循環(huán)。在過程的第4-6行的內(nèi)循環(huán)中，有一點值得注意：當(dāng)執(zhí)行到第5行刪除了位置q的元素以后，表中原來在位置q+l,q+2，的各元素都要向前移動一個位置。特別地，如果q恰好是結(jié)束元素的位置，那么在第5行刪除了位置q的元素后，q值將變?yōu)長.end。因此內(nèi)循環(huán)體第5和第6行的語句必須并行而不能串行，不然，可能會出現(xiàn)無定義的語句q=L.next(L.end)（即第6行的語句不用else而單獨作為一個語句會出錯）。在后文中，我們要給出T

15、List和TPosition的適當(dāng)類型說明，并討論實現(xiàn)表運算的方法。下面我們用抽象類來定義ADT表。=下面是C+語言描述的代碼=template class TLiearList public: virtual bool IsEmpty() const = 0; virtual int length() const = 0; virtual bool locate(int k, T& x) const = 0; /return the kth element of list in variable x virtual int Search(const T& x) const = 0; /ret

16、urn position of x virtual AbstractList& Delete(int k, T& x) = 0; /delete kth element of list and return in x virtual AbstractList& Insert(int k, const T& x) = 0; /insert x just after kth element virtual void Output(ostream& out) const = 0;表的數(shù)組實現(xiàn)將一個表存儲到計算機中，可以采用許多不同的方法，其中既簡單又自然的是順序存儲方法，即將表中的元素逐個存放于數(shù)組

17、的一些連續(xù)的存儲單元中。在這種表示方式下，容易實現(xiàn)對表的遍歷。要在表的尾部插入一個新元素，也很容易。但是要在表的中間位置插入一個新元素，就必須先將其后面的所有元素都后移一個單元，才能騰出新元素所需的位置。執(zhí)行刪除運算的情形類似。如果被刪除的元素不是表中最后一個元素，則必須將它后面的所有元素前移一個位置，以填補由于刪除所造成的空缺。用數(shù)組實現(xiàn)表時，我們將表類型TList定義為一個記錄。它有兩個域，第一個域是一個數(shù)組，用于存儲表中的元素，數(shù)組的大小根據(jù)表可能達到的最大長度而定；第二個域是一個整型變量last，用于指出表中結(jié)束元素在數(shù)組中的位置。表中第i個元素(1ilast)存儲在數(shù)組的第i個單元中

18、。在這種情況下，位置變量的類型TPosition是整型，位置變量p表示數(shù)組的第p個單元即表中第p個元素的位置。End(L)的函數(shù)值為last+1。這些類型可用Pascal語言說明如下: Const MaxLength=100; 數(shù)組的最大長度，即表的最大單元數(shù)目Type TPosition = Integer; TElement= . TElement要根據(jù)具體情況而定 TList = Record Elements: Array 1.MaxLength of TElement; last: TPosition; End;定義了實現(xiàn)表的數(shù)組結(jié)構(gòu)后，我們就可以討論在這種結(jié)構(gòu)上如何具體地實現(xiàn)表的基

19、本運算了。過程 Insert(x,p,L) 功能在表L的位置p處插入元素x，并將原來占據(jù)位置p的元素及其后面的元素都向后推移一個位置。例如，設(shè)L為a1,a2,an，那么在執(zhí)行Insert(x,p,L)后，表L變?yōu)閍1,a2,ap-1,x,ap,an。若p為End(L)，那么表L變?yōu)閍1,a2,an,x 。若表L中沒有位置p，則該運算無定義。實現(xiàn) Procedure Insert(x:TElement;p:TPosition;L:TList);Var q: TPosition;begin if Length(L)=MaxLength then Error(List is Full) else i

20、f (pEnd(L)or(pEnd(L) or (pFirst(L) then Error(Position does not exist.) else begin L.last L.last-1; for q p to L.last do L.Elementsq L.Elementsq+1; end;說明算法Delete通過將位于p+1,p+2,last中的元素分別移到位置p,p+1，, last-1來刪除原來位置p處的元素。復(fù)雜性該算法的時間分析與插入算法類似，元素的移動次數(shù)也是由表長n和位置p決定的。若p=n，則由于循環(huán)變量的初值大于終值，前移語句將不執(zhí)行，無須移動元素；若p=1，則前移

21、語句將循環(huán)執(zhí)行n-1次，需要移動表中除刪除元素外的所有元素。因此，算法在最好情況下需要O(1)時間，而在最壞情況下需要O(n)時間。刪除運算的平均性能分析與插入運算類似。設(shè)在長度為n的表中刪除一個元素所需的平均移動次數(shù)為EDE(N)。由于刪除表中第i個位置上的元素需要的移動次數(shù)為n-i，故其中，pi表示刪除表中第i個位置上元素的概率。在等概率的假設(shè)下，這時也就是說用數(shù)組實現(xiàn)表時，在表中做刪除運算，平均要移動表中約一半的元素，因而刪除運算所需的平均時間為O(n)。 函數(shù) Locate(x,L)功能這是一個函數(shù)，函數(shù)值為元素x在L中的位置。若x在L中重復(fù)出現(xiàn)多次，則函數(shù)值為x第一次出現(xiàn)的位置。當(dāng)x

22、不在L中時，函數(shù)值為End(L)。實現(xiàn) Function Locate(x:TElement;var L:TLIST):TPosition;var q:TPosition;begin for q:=1 to L.last do if L.elementsq=x then return (q); return(L.last+1);end;說明算法Locate在數(shù)組中從前向后通過比較來查找給定元素的位置。如果在表中沒有找到這樣的元素，則返回last+1。復(fù)雜性該算法中的基本運算是兩個元素的比較。若在表中位置i找到給定元素，則需要進行i次比較，否則需要進行n次比較，n為表的長度。與算法Insert和

23、Delete的時間分析類似，算法Locate在最好情況下需要O(l)時間，在最壞情況和平均情況下都需要O(n)時間。用數(shù)組來實現(xiàn)表時，我們利用了數(shù)組單元在物理位置上的鄰接關(guān)系來表示表中元素之間的邏輯關(guān)系。由于這個原因，用數(shù)組來實現(xiàn)表有如下的優(yōu)缺點。優(yōu)點是：1. 無須為表示表中元素之間的邏輯關(guān)系增加額外的存儲空間； 2. 可以方便地隨機訪問表中任一位置的元素。 缺點是：1. 插入和刪除運算不方便，除表尾的位置外，在表的其他位置上進行插入或刪除操作都必須移動大量元素，其效率較低； 2. 由于數(shù)組要求占用連續(xù)的存儲空間，存儲分配只能預(yù)先進行靜態(tài)分配。因此，當(dāng)表長變化較大時，難以確定數(shù)組的合適的大小。

24、確定大了將造成浪費。 例：已知線性表以一維數(shù)組a（1：n）方式存儲，其a中存放有n個數(shù)據(jù)元素。假設(shè)a=（1，2，3，35，45，57，78），現(xiàn)要求完成以下操作：1）在線性表a中的第3個位置插入元素777，結(jié)果為（1，2，777，3，35，45，57，78）；2）刪除當(dāng)前線性表的第3個元素，結(jié)果為（1，2，3，35，45，57，78）；3）查找線性表中是否有值為65的元素，結(jié)論是X=65不存在。 線性表的輸入、插入、刪除、查找以及輸出程序：programlist(input,output);const MAX=10;type arr=array0.MAX of integer;var a:ar

25、r;n,i:integer;b,x:integer;procedure insert(var a:arr;var n:integer;i,b:integer);varj:integer;beginif(in+1)then writeln(position does not exist)else beginfor j:=n downto i do aj+1:=aj;ai:=b;n:=n+1; end;end;procedure delete(var a:arr;var n:integer;i:integer);varj:integer;begin if(in)then writeln(posit

26、ion does not exist)else beginfor j:=i+1 to n do aj-1:=aj;n:=n-1; end;end;function locate(var a:arr;n,x:integer):integer;vari:integer;begin i:=1; while(iN)AND(AIx) do i:=i+1; if(ai=x) then locate:=1 else locate:=0;end;procedure input_array(var a:arr;n:integer);vari:integer;begin for i:=1 to n do read

27、(ai);end;procedure print_array(var a:arr;n:integer);vari:integer;begin for i:=1 to n do write(ai,);end;begin writeln(please input(n10),n=?); read(n); writeln(please input,a1.n); input_array(a,n); write(print array,a1.n); print_array(a,n); i:=3; b:=777; write(inset a,i,=,b, result:); insert(a,n,i,b);

28、 print_array(a,n); i:=3; b:=777; write(delete ai,i,result:); delete(a,n.i); print_array(a,n); writeln(input the number(x) for locate:); read(x); write(print_array;); print_array(a,n); write(locate x=,x,: result:); if(locate(a,n,x)=0) then writeln(x does not exist.) else writeln(locate=,locate(a,n,x)

29、;end.表的指針實現(xiàn)單鏈表（參考）用數(shù)組來實現(xiàn)表很容易， 但表的數(shù)組實現(xiàn)卻存在著明顯的缺點：插入和刪除運算不方便；數(shù)組要求占用連續(xù)的存儲空間， 存儲分配只能預(yù)先進行靜態(tài)分配。有沒有什么辦法來克服這些缺點呢？下面我們來討論表的指針實現(xiàn)。 用指針將存儲表元素的那些單元依次串聯(lián)（邏輯串聯(lián)）在一起實現(xiàn)表的方法稱為表的指針實現(xiàn)。 這種方法避免了在數(shù)組中用連續(xù)的單元存儲元素的缺點，因而在執(zhí)行插入或刪除運算時， 不再需要移動元素來騰出空間或填補空缺。然而我們?yōu)榇烁冻龅拇鷥r是， 需要在每個單元中設(shè)置指針來表示表中元素之間的邏輯關(guān)系，因而增加了額外的存儲空間的開銷。為了將存儲表元素的所有單元用指針串聯(lián)起來，我

30、們對每個單元除了設(shè)置一個元素域存儲元素的值以外， 還要設(shè)置一個指針域來存儲各單元之間的邏輯關(guān)系，其中的指針指向表中下一個元素所在的單元。例如，如果表是a1,a2,an ，那么含有元素ai的那個單元中的指針應(yīng)指向含有元素ai+1的單元(i=1,2,n-1)；含有an的那個單元中的指針是空指針nil。此外，通常我們還為每一個表設(shè)置一個表頭單元header，其中的指針指向開始元素中所在的單元，但表頭單元header中不含任何元素。設(shè)置表頭單元的目的是為了使表運算中的一些邊界條件更容易處理。這一點我們在后面可以看到。如果我們愿意單獨地處理諸如在表的第一個位置上進行插人與刪除操作等邊界情況，也可以簡單地

31、用一個指向表的第一個單元的指針來代替表頭單元。 上述這種用指針來表示表的結(jié)構(gòu)通常稱為單鏈接表，或簡稱為單鏈表或鏈表。單鏈表的邏輯結(jié)構(gòu)如圖1所示。表示空表的單鏈表只有一個單元，即表頭單元header，其中的指針是空指針nil。圖1 單鏈表示意圖 注意，在單鏈表中，位置變量的意義與用數(shù)組實現(xiàn)的表不同。在單鏈表中位置i是一個指針，它所指向的單元是元素ai-1所在的單元，而不是元素ai所在的單元(i=2,3,n)。位置1是指向表頭單元header的指針。位置End(L)是指向單鏈表L中最后一個單元的指針。這樣做的目的是為了避免在修改單鏈表指針時需要找一個元素的前驅(qū)元素的麻煩，因為在單鏈表中只設(shè)置指向后

32、繼元素的指針，而沒有設(shè)置指向前驅(qū)元素的指針。 在單鏈表中，表類型TList和位置類型TPosition一樣，都是指向某一單元的指針。尤其可以是指向表頭單元的指針。單鏈表結(jié)構(gòu)的主要類型可形式地定義為:typeCellType=record element:TElement; next:CellType; end;TList=CellType;TPosition=CellType;在單鏈表中，函數(shù)End(L)可實現(xiàn)如下Function End(L:TList):TPosition;var q: TPosition;begin q:=L; while q.nextnil do q:=q.next;

33、return(q)end; 上述算法中的指針q指向需要檢查的單元。由于檢查要從header開始，而L是指向表頭單元header的指針，所以q的初值為L。如果q所指的單元中的指針不是空指針，說明該單元不是表中的結(jié)束單元，因此要將q移向該單元的指針?biāo)傅南乱粏卧员銠z查下一個單元。直到q所指的單元中的指針為nil時，那時的q值才是應(yīng)返回的函數(shù)值。若表的長度為n,按這樣計算End(L)需要掃描整個鏈表，因此需要O(n)時間，效率很低。如果需要頻繁地調(diào)用函數(shù)End，我們可以采用下面的兩種方法之一來提高效率。1. 在鏈表結(jié)構(gòu)中多設(shè)一個指向鏈表結(jié)束單元的表尾指針。對此，通過表尾指針就可以在O(1)時間內(nèi)

34、實現(xiàn)End(L)。 2. 盡可能避免調(diào)用End(L)。例如Purge程序的第(2)行中判斷條件pEnd(L)應(yīng)該用p.nextnil來代替。 下面討論單鏈表中Insert,Delete和Locate三種運算的實現(xiàn)。過程 Insert(x,p) 功能在表L的位置p后處插入元素x，并將原來占據(jù)位置p后面的元素都向后推移一個位置。例如，設(shè)L為a1,a2,an，那么在執(zhí)行Insert(x,p)后，表L變?yōu)閍1,a2,ap,x,ap+1,an 。若p為End(L)，那么表L變?yōu)閍1,a2,an,x 。若表L中沒有位置p，則該運算無定義。實現(xiàn)Procedure Insert(x:TElement;p:TP

35、osition);var temp:TPosition;begin temp:=p.next; new(p.next); p.next.element:=x; p.next.next:=temp;end;說明上述算法中，鏈表指針的修改情況見圖2。(a)(b)圖2 Insert過程的指針修改示意圖圖2(a)是執(zhí)行Insert運算之前的情況。我們要在指針p所指的單元之后插入一個新元素x。圖2(b)是執(zhí)行Insert運算以后的結(jié)果，其中的虛線表示新的指針。在上述Insert算法中，位置變量p指向單鏈表中一個合法位置，要插入的新元素x應(yīng)緊接在p所指單元的后面。指針p的合法性應(yīng)在執(zhí)行Insert運算之前

36、判定。往一個單鏈表中插入新元素通常在表頭或表尾進行，因此p的合法性容易判定。復(fù)雜性Insert運算所需的時間顯然為O(1)。過程 Delete(p)功能從表L中刪除位置p后處的元素。例如，當(dāng)L為a1,a2,an時，執(zhí)行Delete(p)后，L變?yōu)閍1,a2,ap,ap+1,an 。當(dāng)L中沒有位置p或p=End(L)時，該運算無定義。實現(xiàn)Procedure Delete(p:TPosition);var q:TPosition;begin q:=p.next; p.next:=p.next.next; dispose(q);end;說明這個過程很簡單，其指針的修改如圖3所示。圖3 Delete過

37、程的指針修改示意圖若要從一個表中刪除一個元素x，但不知道它在表中的位置，則應(yīng)先用Locate(x,L)找出指示要刪除的元素的位置，然后再用Delete刪除該位置指示的元素。復(fù)雜性Delete過程所需的時間顯然也為O(1)。函數(shù) Locate(x,L) 功能這是一個函數(shù)，函數(shù)值為元素x在L中的位置。若x在L中重復(fù)出現(xiàn)多次，則函數(shù)值為x第一次出現(xiàn)的位置。當(dāng)x不在L中時，函數(shù)值為End(L)。實現(xiàn)Function Locate(x:TElement;L:TList):TPosition;Var p:TPosition;begin p:=L; while p.nextnil do if p.next.

38、element = x then return(p) else p:=p.next; return(p);end;說明在單鏈表中實現(xiàn)LOCATE的過程與用數(shù)組實現(xiàn)表時的LOCATE過程是類似的。復(fù)雜性容易看出，在最壞情況下和平均情況下，LOCATE所需的時間均為O(n)。 對于其他基本的表運算實現(xiàn)起來都比較簡單，這里從略。至于時間復(fù)雜性，在最壞情況下，PrintList顯然需要O(n)，而Previous由于單鏈表沒有設(shè)置指向前驅(qū)的指針，得從頭到尾掃描，因此也需要O(n)。表的游標(biāo)實現(xiàn) 所謂游標(biāo)就是指示數(shù)組單元地址的下標(biāo)值，它屬整數(shù)類型。我們可以用游標(biāo)來模擬指針，將TElement類型的元素所

39、組成的表用一個數(shù)組來實現(xiàn)，數(shù)組單元是記錄類型，記錄中包含一個表元素和一個作為游標(biāo)的整數(shù)；具體說明如下:VarSPACE: array1.maxlength of record element:TElement; next:integer; end; 對于一個表L，我們用一個整型變量Lhead作為L的表頭游標(biāo)。SPACELhead就是L的表頭單元，其中的elemnt域是空的，next域中的游標(biāo)指示L的第一個元素在數(shù)組SPACE中的存儲地址(數(shù)組下標(biāo)值)。這樣，我們就可以用游標(biāo)來模擬指針，實現(xiàn)單鏈表中的各種運算。照此，我們雖然是用數(shù)組來存儲表中的元素，但在作表的插人和刪除運算時，不需要移動元素，只

40、要修改游標(biāo)，從而保持了用指針實現(xiàn)表的優(yōu)點。因此，有時也將這種用游標(biāo)實現(xiàn)的表稱為靜態(tài)鏈表。 下面我們介紹用游標(biāo)實現(xiàn)表的另一種方式。這種方式不用表頭單元，因此在表的第一個位置進行插入或刪除時，需要進行特殊處理。這與在單鏈表中不用表頭單元的情形類似。設(shè)L是一個表。我們用Lhead指示L的第一個元素，即L的第一個元素存放于SPACELhead.element中，而SPACELhead.next為L的第二個元素所在單元的下標(biāo)值。其后每個元素的后繼元素所在單元以類似的方式給出。如果Lhead或者某單元中next域的值為0，則表示這是一個空指針，即該游標(biāo)不指示任何單元。表L可以用它的表頭變量Lhead來代表

41、。由于表頭變量是整型變量，所以表的類型為整型。位置變量類型TPosition也是整型。與單鏈表中位置變量的意義相類似。我們約定，當(dāng)i1時，表示第i個位置的位置變量pi的值是數(shù)組SPACE中存儲表L的第i-1個元素的單元的下標(biāo)值，即SPACEpi.next是指示第i個元素在SPACE中的下標(biāo)。當(dāng)i=1時，pi=O。類型定義如下：Type TList=integer; TPosition=integer; SPACEd74c06a80e0b3102圖4 用游標(biāo)實現(xiàn)表 在圖4中，兩個表L（包含元素依次為a,b,c）和M（包含元素依次為d,e）存放于同一數(shù)組SPACE中，其中的maxlength=10

42、。數(shù)組SPACE中末被占用的所有單元組成了另一個表available，由這個表提供L和M的備用單元。當(dāng)我們要在表L或M中插入一個元素時，所用的新單元就取自表available。反之，從兩個表中刪除的單元要回收(插入)到表available中備用。 初始時，我們將數(shù)組SPACE中所有單元鏈接成表available備用。這個過程可實現(xiàn)如下。procedure Initialize;Var i:Integer;begin for i:=maxlength-l downto 1 do SPACEi.next:=i+l; available:=1; 表available的第一個可用單元即表頭在SPACE

43、中的下標(biāo)為1 SPACEmaxlength.next:=0;end; 要在表L中插入一個元素x，可將表available的第一個單元摘除，并將這個備用單元插入L的適當(dāng)位置，再將這個新單元的element域賦值為x。procedure Insert(x:TElement;p:TPosition;var L:TLIST);beginif p=O then (在第一個位置插入) begin if move(available,L) then SPACEL.element:=x else error; end else 不在第一個位置插入 if move(available,SPACEp.next)

44、then SPACESPACEp.next.element:=x else errorend; 由于我們沒有使用表頭單元，所以必須單獨處理在第一個位置插入的情形。另外，上述過程中用到了一個函數(shù)move(p,q)，其功能是從某一鏈表中將游標(biāo)p所指的單元C摘除，并將這個單元C插入到另一鏈表中游標(biāo)q所指的單元之前，成功則返回true。我們可以先將q改為指向單元C，然后再將p改為指向單元C的下一單元，最后再將C中的游標(biāo)改為指向q原來所指的單元即可。這個游標(biāo)的修改過程如圖5所示。圖5 兩個鏈表之間的單元轉(zhuǎn)移 圖5中的實線和虛線分別表示單元轉(zhuǎn)移前后的游標(biāo)。當(dāng)單元C存在時，函數(shù)move取值為true，并施行

45、單元C的轉(zhuǎn)移;當(dāng)單元C不存在時，函數(shù)move取值為false。function move(var p,q;integer):boolean;var temp:integer;begin if p=0 then return(false) e1se begin temp:=q; q:=p; p:=SPACEp.next; SPACEq.next:=temp; return(true); endend; 要從表中刪除位置p的元素，可以將L中位置p所指示的那個單元摘除，并將它插入表available的頭一個位置備用。procedrue Delete(p:TPosition;var L:TList);

46、beginif p=O then move(L，available) else move(SPACEp.next，available)end; 與單鏈表中的情形類似，為要刪除表L中的一個元素x，先要找到x在表L中的位置。這可以用下面的函數(shù)Locate來實現(xiàn)。在表L中找到第一個與x相同的元素時，Locate返回x所在單元的位置，否則返回表尾位置。function Locate (x:TElement;L:TList):TPosition;Var p:TPosition;begin p:=L; if p=0 then error(List is empty.); if SPACEp.element

47、=x then return(0); while SPACEP.next0 do if SPACESPACEP.next.element=x then return(p) else p:=SPACEP.next;return(p);end; 由于我們是用游標(biāo)來模擬指針的，上述各運算的復(fù)雜性分析與單鏈表中的情形是類似的。另外，上述程序中都省略了檢查錯誤的語句。循環(huán)鏈表我們在用指針實現(xiàn)表時，表中最后一個元素所在單元的指針域(next)為空指針nil。如果將這個空指針改為指向表頭單元的指針就使整個鏈表形成一個環(huán)。這種首尾相接的鏈表稱為循環(huán)鏈表。在循環(huán)鏈表中，從任意一個單元出發(fā)可以找到表中其他單元。圖

48、6所示的是一個單鏈的循環(huán)鏈表或簡稱為單循環(huán)鏈表。(a)非空表(b)空表圖6單循環(huán)鏈表在單循環(huán)鏈表上實現(xiàn)表的各種運算的算法與單鏈表的情形是類似的。它們僅在循環(huán)終止條件上有所不同:前者是p或p.next指向表頭單元；后者是p或p.next指向空(nil)。在單鏈表中我們用指向表頭單元的指針表示一個表L，這樣就可以在O(1)時間內(nèi)找到表L中的第一個元素。然而要找到表L中最后一個元素就要花O(n)時間遍歷整個鏈表。在單循環(huán)鏈表中，我們也可以用指向表頭單元的指針表示一個表L。但是，如果我們用指向表尾的指針表示一個表L時，我們就可以在O(1)時間內(nèi)找到表上中最后一個元素。同時通過表尾單元中指向表頭單元的指針，我們也可以在O(1)時間內(nèi)找到表L中的第一個元素。在許多情況下，用這種表示方法可以簡化一些關(guān)于表的運算。例如要將圖7(a)中兩個表L1和L2合并成一個表時，只要修改兩個指針值即可，運算時間為O(1)。雙鏈表在單循環(huán)鏈表中，雖然從任一單元出發(fā)，可以找到其前驅(qū)單元，但需要O(n)時間。如果我們希望能