《數(shù)據(jù)結(jié)構(gòu)與算法分析》課件第2章

第2章線性表2.1線性表的基本概念及運算2.2順序表2.3鏈表

2.1線性表的基本概念及運算

線性表(LinearList)是最常用且最簡單的一種數(shù)據(jù)結(jié)構(gòu)。簡單地講，一個線性表是n個數(shù)據(jù)元素的有限序列(a1，a2，

…，an)。至于一個數(shù)據(jù)元素ai的具體含義，在不同的情況下可以不同。例如，英文字母表(A，B，C，…，Z)是一個線性表，表中的每一個英文字母為一個數(shù)據(jù)元素。表2-1所示的學(xué)生成績登記表，是一個略為復(fù)雜一點的線性表的例子。

例2-1

利用線性表的基本運算實現(xiàn)清除線性表Ｌ中多余的重復(fù)結(jié)點。

實現(xiàn)該運算的基本思想是：從表Ｌ的第一個結(jié)點(i?=?1)開始，逐個檢查i位置以后的任意位置j，若兩個結(jié)點相同，則將位置j上的結(jié)點從表Ｌ中刪除；當(dāng)j遍歷了i后面的所有位置之后，i位置上的結(jié)點就成為當(dāng)前表Ｌ中沒有重復(fù)值的結(jié)點，然后將i向后移動一個位置。重復(fù)上述過程，直至i移到當(dāng)前表Ｌ的最后一個位置為止。該運算可用如下形式的算法描述：

2.2順序表

在計算機內(nèi)，可以用不同的方式來表示線性表，其中最簡單和最常用的方式是用一組地址連續(xù)的存儲單元依次存儲線性表的元素。

假設(shè)線性表的每個元素需占用c個存儲單元，并以所占第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置，如圖2-1所示，則線性表中第i+1個數(shù)據(jù)元素的存儲位置Loc(ai+1)和第

i個數(shù)據(jù)元素的存儲位置Loc(ai)之間滿足下列關(guān)系：

Loc(ai+1)=Loc(ai)+c

(2-1)圖2-1線性表順序存儲結(jié)構(gòu)示意圖一般來說，線性表的第i個元素ai的存儲位置為

Loc(ai)=Loc(a1)+(i－1)

c

1≤i≤n

(2-2)

其中，Loc(a1)是線性表的第一個數(shù)據(jù)元素a1的存儲位置，通常稱做線性表的起始位置或基地址。由于C語言中的向量(一維數(shù)組)也是采用順序存儲表示，因此可以用向量這種數(shù)據(jù)類型來描述順序表。2.2.1順序表的基本運算

1.插入運算

在線性表的第i(1≤i≤n+1)個位置上，插入一個新結(jié)點x，使長度為n的線性表

(a1，…，ai-1，ai，…，an)

變成長度為n+1的線性表

(a1，…，ai-1，x，ai，…，an)圖2-2順序表插入元素的過程下面我們給出一個完整的C程序，其中包括三個子函數(shù)：Create(建立順序表)、Insert(插入元素)、Output(輸出線性表)，并由主函數(shù)調(diào)用。

2.刪除運算

線性表的刪除運算是指將表的第i(1≤i≤n)個結(jié)點ai刪去，使長度為n的線性表

(a1，…，ai-1，ai，ai+1，…，an)

變成長度為n－1的線性表

(a1，…，ai-1，ai+1，…，an)可以看出，數(shù)據(jù)元素ai-1，ai，ai+1的邏輯關(guān)系發(fā)生了變化。為了在存儲結(jié)構(gòu)上反映這個變化，同樣需要移動元素，即若1≤i≤n-1，則必須將順序表中在位置i+1，i+2，…，n上的結(jié)點，依次前移到位置i，i+1，…，n-1上，以填補刪除操作造成的空缺；若i=n，則只要簡單地刪除終端結(jié)點，而無須移動。其刪除過程如圖2-3所示。圖2-3順序表刪除元素的過程

3.算法分析

從上面兩個算法可以看出，順序表的插入與刪除運算，其時間主要耗費在移動順序表中的元素上，而所移動的元素個數(shù)不僅依賴于表長n，而且還與插入及刪除的位置i有關(guān)。

為了不失一般性，假設(shè)pi是在第i個位置上插入一個元素的概率，則在長度為n的線性表中插入一個元素須移動元素次數(shù)的期望值(平均次數(shù))為

(2-3)假設(shè)qi是刪除第i個元素的概率，則在長度為n的線性表中刪除一個元素須移動元素次數(shù)的期望值(平均次數(shù))為

(2-4)為了不失一般性，假設(shè)在線性表中任何位置上插入或刪除元素的概率相等，則

故

(2-5)

(2-6)2.2.2順序表的應(yīng)用實例——學(xué)生學(xué)籍檔案管理

1．問題描述及要求

現(xiàn)有若干學(xué)生的學(xué)籍檔案信息，要求編寫一個應(yīng)用軟件對其進行日常管理，以實現(xiàn)學(xué)生檔案信息的插入和刪除，并能根據(jù)學(xué)生姓名查詢。

2．?dāng)?shù)據(jù)結(jié)構(gòu)

我們將所有學(xué)生的檔案信息存放在一個順序表中，其中的每個結(jié)點是一個學(xué)生的檔案信息，并假設(shè)每個學(xué)生的數(shù)據(jù)包括以下內(nèi)容：學(xué)號、姓名、性別、籍貫，則數(shù)據(jù)結(jié)構(gòu)定義如下：

3．算法設(shè)計

根據(jù)問題的要求，整個軟件分成四個子模塊：按姓名的字典順序插入學(xué)生數(shù)據(jù)，數(shù)據(jù)的刪除，按姓名查詢，打印學(xué)生檔案。其程序結(jié)構(gòu)如圖2-4所示。圖2-4程序結(jié)構(gòu)示意圖

2.3鏈表

鏈式存儲是最常用的存儲方法之一，它不僅可以用來表示線性表，而且還可以用來表示各種非線性的數(shù)據(jù)結(jié)構(gòu)。本節(jié)將討論幾種用于存儲線性表的鏈接方式：單鏈表、雙鏈表和循環(huán)鏈表，統(tǒng)稱為鏈表(Linkedlist)。2.3.1單鏈表

在順序表中，我們是用一組地址連續(xù)的存儲單元來依次存放線性表的結(jié)點，因此結(jié)點的邏輯次序和物理次序一致。而鏈表是用一組任意的存儲單元來存放線性表的元素，這組存儲單元既可以是連續(xù)的，也可以是不連續(xù)的。因此，為了正確地表示元素間的邏輯關(guān)系，在存儲每個元素值的同時，還必須存儲指示其后繼元素的地址(或位置)信息。這兩部分信息組成數(shù)據(jù)元素的存儲映像，即結(jié)點。它包括兩個域，存儲數(shù)據(jù)元素信息的域稱做數(shù)據(jù)域；存儲后繼元素存儲位置的域稱做指針域。指針域中存儲的信息稱做指針或鏈。結(jié)點的結(jié)構(gòu)為圖2-5線性單鏈表示意圖圖2-6單鏈表的一般圖示法單鏈表是由頭指針唯一確定的，因此單鏈表可以用頭指針的名字來命名。例如，若頭指針名是head，則把鏈表稱為表head。用C語言描述單鏈表如下：實際上，以上定義的指針變量p所指向的結(jié)點變量是通過標(biāo)準函數(shù)生成的，即

p?=?malloc(sizeof(linklist))；圖2-7指針變量p(其值是結(jié)點地址)和結(jié)點變量

p(其值是結(jié)點內(nèi)容)的關(guān)系2.3.2單鏈表的基本運算

1．單鏈表的建立

1)頭插法建表

頭插法建表是從一個空表開始，重復(fù)讀入數(shù)據(jù)，生成新結(jié)點，將讀入數(shù)據(jù)存放到新結(jié)點的數(shù)據(jù)域中，然后將新結(jié)點插入到當(dāng)前鏈表的表頭上，直至讀入結(jié)束標(biāo)志為止。例如，在空鏈表head中依次插入結(jié)點a、結(jié)點b、結(jié)點c之后，將結(jié)點d插入到當(dāng)前鏈表的表頭，其指針的修改情況如圖2-8所示。其中序號①～④表明了結(jié)點插入時的操作次序。其算法描述如下：圖2-8將新結(jié)點

s插入到單鏈表head的頭上

2)尾插法建表

頭插法建表雖然簡單，但是生成的鏈表中結(jié)點的次序和輸入的順序相反。若希望兩者次序一致，可利用尾插法建表。尾插法建表是將新結(jié)點插到當(dāng)前鏈表的表尾上，為此必須增加一個尾指針r，使其始終指向當(dāng)前鏈表的尾結(jié)點。例如，在空鏈表head中插入結(jié)點a、結(jié)點b、結(jié)點c之后，將結(jié)點d插入到當(dāng)前鏈表的表尾，其指針的修改情況如圖2-9所示。圖2-9將新結(jié)點

s插入到單鏈表head的尾上其中序號①～④表明插入結(jié)點時的操作順序。其算法描述如下：這種帶有頭結(jié)點的單鏈表如圖2-10所示，其中，#部分表示頭結(jié)點的數(shù)據(jù)域不存儲信息，但是在有的應(yīng)用中，可利用該域來存放表的長度等附加信息。圖2-10帶頭結(jié)點的單鏈表head

2．單鏈表的查找

1)按序號查找

在單鏈表中，即使知道被訪問結(jié)點的序號i，也不能像順序表中那樣直接按序號i訪問結(jié)點，而只能從鏈表的頭指針出發(fā)，順著鏈域next逐個結(jié)點往下搜索，直至搜索到第i個結(jié)點為止。因此，單鏈表不是隨機存取結(jié)構(gòu)。

2)按值查找

按值查找是從開始結(jié)點出發(fā)，順著鏈逐個將結(jié)點的值和給定值key做比較，來完成結(jié)點的查找。

3．鏈表的插入

在線性表的順序存儲結(jié)構(gòu)中，由于具有邏輯位置與物理位置一致的特點，使得在進行元素插入和刪除運算時有大量的元素參加移動，而在單鏈表存儲結(jié)構(gòu)中，元素的插入或刪除，只須修改有關(guān)的指針內(nèi)容，無須移動元素。圖2-11在*p之后插入*s

例2-2

在單鏈表上，將值為x的新結(jié)點插入在結(jié)點

p前。

分析：由題意知道該插入操作為前插操作。前插操作必須修改

p的前趨結(jié)點的指針域，需要確定其前趨結(jié)點的位置。但單鏈表中沒有前趨指針，一般情況下必須從頭指針起，順鏈找到

p的前趨結(jié)點

q。前插過程如圖2-12所示，其中的序號①～⑤表示插入結(jié)點時的操作順序。圖2-12在

p之前插入

s

例2-3

在單鏈表上實現(xiàn)線性表的插入運算Insert(L,x,i)。

分析：根據(jù)題意，該運算是生成一個值為x的新結(jié)點，并插入到鏈表中第i個結(jié)點之前，也就是插入到第i－1個結(jié)點之后。因此可以先用函數(shù)Get求得第i－1個結(jié)點的存儲位置p：

P?=?Get(L,i－1)

4．鏈表的刪除

要刪除單鏈表中的結(jié)點?

p，就應(yīng)修改?

p的前趨結(jié)點?

q的指針域。一般情況下，要從頭指針開始順著鏈找到?

p的前趨結(jié)點?

q，然后刪去?

p。其刪除過程如圖2-13所示，其中的序號①～③表示刪除結(jié)點的操作順序。圖2-13刪除結(jié)點

p

例2-4

在單鏈表上實現(xiàn)線性表的刪除運算Delete(L,i)。

要使刪除運算簡單，就必須得到被刪除結(jié)點的前趨，即第i-1個結(jié)點?

p，然后刪去?

p的后繼。其算法描述如下：

例2-5

將兩個遞增單鏈表合并為一個遞增單鏈表，要求不另外開辟空間。

此題的算法描述如下：2.3.3循環(huán)鏈表

循環(huán)鏈表(Circularlinkedlist)是另一種形式的鏈式存儲結(jié)構(gòu)，它的特點是表中最后一個結(jié)點的指針域指向頭結(jié)點，整個鏈表形成一個環(huán)。顯然，從表中任意結(jié)點出發(fā)均可找到表中其他結(jié)點，圖2-14所示為單循環(huán)鏈表。圖2-14單循環(huán)鏈表圖2-15僅設(shè)尾指針rear的單循環(huán)鏈表

例2-6

在循環(huán)鏈表的第i個元素之后插入元素x。

此題的具體算法如下：2.3.4雙向鏈表

用單鏈表表示線性表，從任意一個結(jié)點出發(fā)能通過next域找到它的后繼結(jié)點，若要尋查結(jié)點的前趨，則須從表頭指針出發(fā)。換句話說，在單鏈表中，Next(L，ai)的執(zhí)行時間復(fù)雜度為O(1)，而Prior(L，ai)的執(zhí)行時間復(fù)雜度為O(n)。如果在每個結(jié)點中增加一個指向直接前趨的指針，處理就靈活得多，它可以克服鏈表的這種單向性的缺點，這種鏈表稱為雙向鏈表(Doublelinkedlist)。顧名思義，在雙向鏈表的結(jié)點中有兩個指針域，其中一個指向直接后繼，另一個指向直接前趨，其結(jié)構(gòu)可描述如下：圖2-16雙向循環(huán)鏈表示意圖圖2-17雙向鏈表上刪除結(jié)點圖2-18雙向鏈表上的前插操作刪除結(jié)點的算法描述如下：插入結(jié)點的算法描述如下：以上詳細介紹了線性表及其兩種存儲結(jié)構(gòu)，在實際應(yīng)用中究竟如何選擇，主要根據(jù)具體問題的要求和性質(zhì)，再結(jié)合順序和鏈式兩種存儲結(jié)構(gòu)的特點來決定，通常從以下三個方面考慮。

(1)存儲空間。

(2-7)

(2)運算時間。順序存儲結(jié)構(gòu)是一種隨機存取結(jié)構(gòu)，便于元素的隨機訪問，即順序表中每一個元素都可以在時間復(fù)雜度為O(1)的情況下迅速存??；而在鏈式存儲結(jié)構(gòu)中為了訪問某一個結(jié)點，必須從頭指針開始順序查找，時間復(fù)雜度為O(n)。所以對于一個表，只進行查找操作而很少做插入和刪除操作時，采用順序存儲結(jié)構(gòu)為宜。

(3)程序設(shè)計語言。從計算機語言來看，絕大多數(shù)高級語言都提供了指針類型，但也有沒有提供指針類型的，為此，可以采用靜態(tài)鏈表的方法來模擬動態(tài)存儲結(jié)構(gòu)。如果問題規(guī)模較小，采用靜態(tài)鏈表來實現(xiàn)可能會更加方便。2.3.5鏈表應(yīng)用實例——多項式的表示及運算

1．問題描述及分析

在數(shù)學(xué)上，一個一元n次多項式可寫成：

Pn(x)=p0+p1x+p2x2+?…?+pnxn

(2-8)

它由n+1個系數(shù)唯一確定。因此，在計算機中，一元n次多項式Pn(x)可用一個線性表P來表示：

P=(p0，p1，p2，…，pn)

(2-9)

每一項的指數(shù)i隱含在其系數(shù)pi的序號里。假設(shè)Qm(x)是一元m次多項式，用線性表Q來表示：

Q=(q0，q1，q2，…，qm)

(2-10)

為了不失一般性，設(shè)m<n，則兩個多項式相加的結(jié)果Rn(x)=Pn(x)+Qm(x)可用線性表R表示：

R=(p0+q0，p1+q1，p2+q2，…，pm+qm，…，pn)

(2-11)顯然，我們可以對P、Q、R采用順序存儲結(jié)構(gòu)表示，使得多項式算法定義十分簡潔。至此，一元多項式的表示及相加問題似乎解決了。然而，由于在通常的應(yīng)用中，多項式的次數(shù)可能較高且變化較大，使得順序存儲結(jié)構(gòu)的最大長度很難確定。特別是在處理形如