第2章數(shù)據(jù)結(jié)構(gòu)-線性表

數(shù)據(jù)結(jié)構(gòu)

(Python語言描述)

李粵平

線性表是同一類型數(shù)據(jù)的一個有限序列，數(shù)據(jù)之間在邏輯上存在著線性關(guān)系。線性結(jié)構(gòu)是最常用、最簡單的一種數(shù)據(jù)結(jié)構(gòu)。而其基本特點是線性表中的數(shù)據(jù)元素是有序且是有限的。在這種結(jié)構(gòu)中：①存在一個唯一的被稱為“第一個”的數(shù)據(jù)元素；②存在一個唯一的被稱為“最后一個”的數(shù)據(jù)元素；③除第一個元素外，每個元素均有唯一一個直接前驅(qū)；④除最后一個元素外，每個元素均有唯一一個直接后繼第2章

線性表—順序表和鏈表2.1線性表的定義線性表的定義線性表(LinearList)：是由n(n≧0)個數(shù)據(jù)元素(節(jié)點)a1，a2，…an組成的有限序列。該序列中的所有節(jié)點具有相同的數(shù)據(jù)類型。其中數(shù)據(jù)元素的個數(shù)n稱為線性表的長度。當n=0時，稱為空表。當n>0時，將非空的線性表記作：(a1，a2，…an)a1稱為線性表的第一個(首)節(jié)點，an稱為線性表的最后一個(尾)節(jié)點。a1，a2，…ai-1都是ai(2≦i≦n)的前驅(qū)，其中ai-1是ai的直接前驅(qū);ai+1，ai+2，…an都是ai(1≦i≦n-1)的后繼，其中ai+1是ai的直接后繼。線性表

線性表中的數(shù)據(jù)元素ai所代表的具體含義隨具體應用的不同而不同，在線性表的定義中，只不過是一個抽象的表示符號?！艟€性表中的節(jié)點可以是單值元素(每個元素只有一個數(shù)據(jù)項)。判斷以下結(jié)構(gòu)是否為線性結(jié)構(gòu)結(jié)構(gòu)1結(jié)構(gòu)2結(jié)構(gòu)3結(jié)構(gòu)42.2

順序表

順序存儲：把線性表的節(jié)點按邏輯順序依次存放在一組地址連續(xù)的存儲單元里。用這種方法存儲的線性表簡稱順序表。順序存儲的線性表的特點：

◆線性表的邏輯順序與物理順序一致;

◆數(shù)據(jù)元素之間的關(guān)系是以元素在計算機內(nèi)“物理位置相鄰”來體現(xiàn)。設(shè)有非空的線性表：(a1，a2，…an)。順序存儲如圖2-1所示。線性表的順序存儲結(jié)構(gòu)

在具體的機器環(huán)境下：設(shè)線性表的每個元素需占用L個存儲單元，以所占的第一個單元的存儲地址作為數(shù)據(jù)元素的存儲位置。則線性表中第i+1個數(shù)據(jù)元素的存儲位置LOC(ai+1)和第i個數(shù)據(jù)元素的存儲位置LOC(ai)之間滿足下列關(guān)系：

LOC(ai+1)=LOC(ai)+L

線性表的第i個數(shù)據(jù)元素ai的存儲位置為：

LOC(ai)=LOC(a1)+(i-1)*L

Loc(a1)Loc(ai)+(i-1)*L圖2-1

線性表的順序存儲表示2.2.1

順序表的基本操作

順序存儲結(jié)構(gòu)中，很容易實現(xiàn)線性表的一些操作：初始化、賦值、查找、修改、插入、刪除、求長度等。以下將對幾種主要的操作進行討論。順序線性表初始化

為數(shù)組分配連續(xù)的存儲空間，時間復雜度O(1).

2

順序線性表的插入

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中的第i(1≦i≦n)個位置上插入一個新節(jié)點e，使其成為線性表：

L=(a1，…ai-1，e，ai，ai+1，…，an)

實現(xiàn)步驟(1)

將線性表L中的第i個至第n個節(jié)點后移一個位置。(2)將節(jié)點e插入到節(jié)點ai-1之后。(3)線性表長度加1。

時間復雜度分析

在線性表L中的第i個元素之前插入新節(jié)點，其時間主要耗費在表中節(jié)點的移動操作上，因此，可用節(jié)點的移動來估計算法的時間復雜度。

設(shè)在線性表L中的第i個元素之前插入節(jié)點的概率為Pi，不失一般性，設(shè)各個位置插入是等概率，則Pi=1/(n+1)，而插入時移動節(jié)點的次數(shù)為n-i+1。總的平均移動次數(shù)：Einsert=∑pi*(n-i+1)(1≦i≦n)∴Einsert=n/2。即在順序表上做插入運算，平均要移動表上一半節(jié)點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復雜度為O(n)。3順序線性表的刪除

在線性表L=(a1，…ai-1，ai，ai+1，…，an)中刪除節(jié)點ai(1≦i≦n)，使其成為線性表：

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

實現(xiàn)步驟(1)

將線性表L中的第i+1個至第n個節(jié)點依此向前移動一個位置。(2)線性表長度減1。

時間復雜度分析

刪除線性表L中的第i個元素，其時間主要耗費在表中節(jié)點的移動操作上，因此，可用節(jié)點的移動來估計算法的時間復雜度。

設(shè)在線性表L中刪除第i個元素的概率為Pi，不失一般性，設(shè)刪除各個位置是等概率，則Pi=1/n，而刪除時移動節(jié)點的次數(shù)為n-i。則總的平均移動次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。即在順序表上做刪除運算，平均要移動表上一半節(jié)點。當表長n較大時，算法的效率相當?shù)?。因此算法的平均時間復雜度為O(n)。4順序線性表的查找定位刪除

在線性表L=(a1，a2，…，an)中刪除值為x的第一個節(jié)點。實現(xiàn)步驟(1)在線性表L查找值為x的第一個數(shù)據(jù)元素。(2)將從找到的位置至最后一個節(jié)點依次向前移動一個位置。(3)線性表長度減1。

時間復雜度分析

時間主要耗費在數(shù)據(jù)元素的比較和移動操作上。首先，在線性表L中查找值為x的節(jié)點是否存在;其次，若值為x的節(jié)點存在，且在線性表L中的位置為i，則在線性表L中刪除第i個元素。設(shè)在線性表L刪除數(shù)據(jù)元素概率為Pi，不失一般性，設(shè)各個位置是等概率，則Pi=1/n。

◆比較的平均次數(shù)：Ecompare=∑pi*i(1≦i≦n)∴Ecompare=(n+1)/2。

◆刪除時平均移動次數(shù)：Edelete=∑pi*(n-i)(1≦i≦n)∴Edelete=(n-1)/2。平均時間復雜度：Ecompare+Edelete=n，即為O(n)有序線性表的定義和實現(xiàn)有序線性表是指線性表中的元素是按照值或關(guān)鍵字的大小先后有序排列。有序線性表的運算除了繼承一般線性表的所有運算外，還有按值或關(guān)鍵字進行插入、刪除和查找元素等的特殊運算。查找元素的方法：二分查找。時間復雜度為O(log2n)。而一般線性表為O(n)。有關(guān)線性表的順序存儲，下列表述正確的是：順序就是線性表的元素按值排好序線性表元素從前往后存儲的地址是遞增的線性表元素從前往后存儲的地址是遞減的線性表元素從前往后存放在連續(xù)的地址空間ABCD2.3單鏈表

2.3.1

線性表的鏈式存儲結(jié)構(gòu)

鏈式存儲：用一組任意的存儲單元存儲線性表中的數(shù)據(jù)元素。用這種方法存儲的線性表簡稱線性鏈表。存儲鏈表中節(jié)點的一組任意的存儲單元可以是連續(xù)的，也可以是不連續(xù)的，甚至是零散分布在內(nèi)存中的任意位置上的。鏈表中節(jié)點的邏輯順序和物理順序不一定相同。

為了正確表示節(jié)點間的邏輯關(guān)系，在存儲每個節(jié)點值（值域）的同時，還必須存儲指示其直接后繼節(jié)點的地址（指針域），稱為指針(pointer)或鏈(link)，這兩部分組成了鏈表中的節(jié)點結(jié)構(gòu)。每一個節(jié)點只包含一個指針域的鏈表，稱為單鏈表，否則稱為多鏈表。為操作方便，總是在鏈表的第一個節(jié)點之前附設(shè)一個表頭節(jié)點(head)指向第一個節(jié)點。表頭節(jié)點的值域可以不存儲任何信息。datanext圖2-2

鏈表節(jié)點結(jié)構(gòu)data：值域，存放節(jié)點的值。next：指針域，存放節(jié)點的直接后繼的地址。

3695headfat1100bat1300…………cat1305eat3700hatNULL…………1100370013001305batcateatfat

hat?head

圖2-3

帶頭節(jié)點的單鏈表的邏輯狀態(tài)、物理存儲方式

單鏈表是由表頭唯一確定，因此單鏈表可以用表頭的名字來命名。例1、線性表L=(bat，cat，eat，fat，hat)其帶表頭節(jié)點的單鏈表的邏輯狀態(tài)和物理存儲方式如圖2-3所示。單鏈表的各種不同形式一般形式的單鏈表循環(huán)單鏈表帶附加表頭結(jié)點的單鏈表單鏈表的各種不同形式帶表頭附加結(jié)點的空表帶附加表頭結(jié)點的循環(huán)單鏈表帶表頭附加結(jié)點的循環(huán)空表雙向鏈表的各種不同形式一般形式的雙向鏈表循環(huán)雙向鏈表只有一個結(jié)點的循環(huán)雙向鏈表雙向鏈表的各種不同形式帶附加表頭結(jié)點的循環(huán)雙向空表帶附加表頭結(jié)點的循環(huán)雙向鏈表比較線性表順序存儲與鏈接存儲順序存儲通常直接用數(shù)組實現(xiàn)，因此各元素的存儲空間是連續(xù)的，可以直接用下標訪問。例如，A[3]。鏈接存儲結(jié)構(gòu)中，表的各元素存儲空間不一定是連續(xù)的。要依賴節(jié)點里面的引用（指針）來記錄下一節(jié)點。一般來說，訪問表的元素要從表頭元素開始，逐個往后尋找current=current.next有關(guān)線性表的鏈式存儲，下列表述正確的是：線性表元素從前往后存儲的地址肯定不連續(xù)線性表元素從前往后存儲的值是連續(xù)的線性表元素從前往后存儲的地址不一定是連續(xù)的線性表元素從前往后存儲的地址是遞增的ABCD鏈表結(jié)構(gòu)中常見的引用（指針）操作①

q=ppa……操作前pa……q操作后②

q=p.nextbpa……操作前操作后qbpa……③

p=p.nextbpa……操作前操作后pba……④

q.next=pc…pbqa……操作前操作后qb……ac…p2.3.2線性單鏈表的基本操作1

建立單鏈表頭插入法建表尾插入法建表2

單鏈表的查找按序號查找對于單鏈表，不能象順序表中那樣直接按序號i訪問節(jié)點，而只能從鏈表的頭節(jié)點出發(fā)，沿鏈域next逐個節(jié)點往下搜索，直到搜索到第i個節(jié)點為止。因此，鏈表不是隨機存取結(jié)構(gòu)。設(shè)單鏈表的長度為n，要查找表中第i個節(jié)點，僅當1≦i≦n時，i的值是合法的。按值查找不帶表頭的鏈表，在頭部插入節(jié)點p建立鏈表。下面代碼是正確的是：head=p.next;p=head.nextp=p.next;head=pp.next=head;head=pa1=ak.next;head=a1.nextABCDheada1akp帶表頭的鏈表，在頭部插入節(jié)點p建立鏈表。下面代碼是正確的是：head.next=p;p.next=headp.next=head.next;head.next=phead=p;p.next=headak.next=a1;head.next=akABCDheada1akp在尾部插入節(jié)點p建立鏈表。下面代碼是正確的是：head.next=p;p.next=headp.next=tail.next;tail=ptail.next=p;tail=pai.next=ak;tail=akABCDheada1akpaitail…NoneNone3

單鏈表的插入插入運算是將值為p的新節(jié)點插入到表的第i個節(jié)點的位置上，即插入到ai-1與ai之間。因此，必須首先找到ai-1所在的節(jié)點e，新節(jié)點p的后繼設(shè)置為e的后繼（ai所在的節(jié)點），新節(jié)點p作為e的直接后繼節(jié)點。4

單鏈表的刪除刪除單鏈表中的第i個節(jié)點。為了刪除第i個節(jié)點ai，必須找到節(jié)點的存儲地址。該存儲地址是在其直接前趨節(jié)點ai-1的next域中，因此，必須首先找到ai-1的存儲位置p，然后令p.next指向ai的直接后繼節(jié)點，即把ai從鏈上摘下。將新節(jié)點p插入到ai-1與ai之間。下面代碼是正確的是：p.next=e.next;e.next=pp=p.next;e.next=pe=p.next;p=ee.next=p;p.next=e.nextABCDai-1akepai將節(jié)點f刪除。下面代碼是正確的是：e.next=f;f.next=ee=e.next;f.next=ef.next=e.nexte.next=f.nextABCDai-1eaif2.3.3鏈表與順序表的比較空間

順序表在初始化時需要分配好存儲空間，即順序表存儲空間大小時固定的。當線性表長度變化較大時，即不知道需要存儲多少元素，這時就難以確定存儲空間的大小，存儲空間分小了，不能夠存儲足夠的元素，容易造成溢出。存儲空間分大了，又會造成空間浪費。采用線性存儲時，按需分配，不用去考慮表的存儲空間開多大比較合適。時間

順序表查找元素操作時間復雜度為O(1)，因為順序表是用一組連續(xù)的存儲單元來存儲數(shù)據(jù)元素，所以在插入和刪除元素的時候，需要向后或者向前移動一個元素的位置，時間復雜度為O(n)。而單鏈表，由于是用一組任意的存儲單元來存儲數(shù)據(jù)元素，所以在查找元素操作的時間復雜度為O(n)，插入和刪除元素操作不需要移動表中的元素，需要用改變指針的指向即可，因此時間復雜度為O(1)。2.4

雙鏈表

雙鏈表(DoubleLinkedList):指的是構(gòu)成鏈表的每個節(jié)點中設(shè)立兩個指針域：一個指向其直接前趨的指針域prior，一個指向其直接后繼的指針域next。這樣形成的鏈表中有兩個方向不同的鏈，故稱為雙鏈表。和單鏈表類似，雙向鏈表一般增加頭指針也能使雙鏈表上的某些運算變得方便。將頭節(jié)點和尾節(jié)點鏈接起來也能構(gòu)成循環(huán)鏈表，并稱之為雙向循環(huán)鏈表。雙向鏈表是為了克服單鏈表的單向性的缺陷而引入的。2.4.1雙鏈表的節(jié)點及其類型定義datanextprior圖2-4雙向鏈表節(jié)點形式……非空雙向鏈表head?a2a1an?空雙向鏈表head??圖2-5帶頭節(jié)點的雙向鏈表形式雙向鏈表結(jié)構(gòu)具有對稱性，設(shè)p指向雙向鏈表中的某一節(jié)點，則其對稱性可用下式描述：(p.prior).next=p=(p.next).prior2.4.2雙向鏈表的基本操作雙向鏈表的插入

將值為e的節(jié)點插入雙向鏈表中。插入前后鏈表的變化如圖2-6所示。注意：

與單鏈表的插入和刪除操作不同的是，在雙向鏈表中插入和刪除必須同時修改兩個方向上的指針域的指向。Sep…………aiai+1Sep…………aiai+1圖2-6雙向鏈表的插入在鏈表任意位置插入新節(jié)點

將新節(jié)點插入鏈表中第i個位置，首先要遍歷到鏈表的第i-1個位置的節(jié)點，然后需要進行兩部分的操作:第一部分是將第i-1個位置節(jié)點的后繼指針指向新節(jié)點，新節(jié)點的前驅(qū)指針指向第i-1個位置的節(jié)點；第二部分是將新節(jié)點的后繼指針指向第i個位置的節(jié)點，第i個位置節(jié)點的直接前驅(qū)指針指向新節(jié)點。新節(jié)點插入成功，算法結(jié)束。foriinrange(index-1):

pre=pre.next#第index個節(jié)點的后繼節(jié)點next=pre.next#將新節(jié)點的后繼指針指向鏈表中第index+1個節(jié)點newNode.next=next#鏈表中第index+1個節(jié)點的前驅(qū)指針指向新節(jié)點next.prev=newNode

對于單鏈表，由于每個節(jié)點只存儲了后繼指針，到了尾部就停止了向后的操作也就是說，按照這樣的方式，只能索引后繼結(jié)點不能索引前驅(qū)結(jié)點。

這會帶來什么問題呢？

例如不從頭節(jié)點出發(fā)，就無法訪問到全部節(jié)點。事實上要解決這個問題只需要：

將單鏈表中尾部節(jié)點的后繼指針由空改為指向頭節(jié)點。

這種頭尾相接的單鏈表成為單循環(huán)鏈表，簡稱循環(huán)鏈表。2.5

循環(huán)鏈表2.5.1循環(huán)鏈表的基本操作循環(huán)鏈表的尾插入法情況一：鏈表為空，將頭、尾指針指向新節(jié)點。情況二：鏈表不為空，將尾節(jié)點的直接后繼指針指向新節(jié)點，新節(jié)點的直接后繼指針指向頭節(jié)點，如下圖所示。循環(huán)鏈表的刪除節(jié)點情況一：鏈表為空，無法刪除節(jié)點，拋出異常。情況二：鏈表不為空且鏈表只有一個節(jié)點，將頭、尾指向空。情況三：鏈表不為空且鏈表有多個節(jié)點，將鏈表中倒數(shù)第二個節(jié)點的直接后繼指向頭節(jié)點，將尾指點的直接后繼指向空。如下圖所示。有序線性表節(jié)點的關(guān)鍵字有序的線性表稱為有序線性表有序線性表與一般線性表主要差異在于節(jié)點插入操作首先要找到合適位置的節(jié)點插入到該節(jié)點的前方或者與該節(jié)點合并（更新值域）例題

一元多項式的表示和相加一元多項式p(x)=p0+p1x+p2x2+…

+pnxn，由n+1個系數(shù)唯一確定。則在計算機中可用線性表(p0

，p1

，p2

，…

，pn

)表示。既然是線性表，就可以用順序表和鏈表來實現(xiàn)。兩種不同實現(xiàn)方式的元素類型定義如下：(1)順序存儲表示的類型ClassNode:def__init__(self): self.cof=None#系數(shù)部分self.exp=None#指數(shù)部分(2)鏈式存儲表示的類型ClassNode:def__init__(self): self.cof=None#系數(shù)部分self.exp=None#指數(shù)部分self.next=None#后繼的引用一元多項式的相加不失一般性，設(shè)有兩個一元多項式：P(x)=p0+p1x+p2x2+…

+pnxn，Q(x)=q0+q1x+q2x2+…

+qmxmR(x)=P(x)+Q(x)

R(x)由線性表R((p0+q0)，(p1+q1)，(p2+q2)，…

，(pm+qm)，…

，

pn)唯一表示。兩種存儲結(jié)構(gòu)的實現(xiàn)方式⑴

順序存儲表示的相加用順序表示的相加非常簡單。訪問第5項可直接訪問：L.a[4].cof，

L.a[4].exp(2)

鏈式存儲表示的相加

當采用鏈式存儲表示時，根據(jù)節(jié)點類型定義，凡是系數(shù)為0的項不在鏈表中出現(xiàn)，從而可以大大減少鏈表的長度。一元多項式的相加一元多項式相加的實質(zhì)是：

指數(shù)不同：是鏈表的合并。

指數(shù)相同：系數(shù)相加，和為0，去掉節(jié)點，和不為0，修改節(jié)點的系數(shù)域。算法之一：就在原來兩個多項式鏈表的基礎(chǔ)上進行相加，相加后原來兩個多項式鏈表就不在存在。當然再要對原來兩個多項式進行其它操作就不允許了。一元多項式的相加算法之二：對兩個多項式鏈表進行相加，生成一個新的相加后的結(jié)果多項式鏈表，原來兩個多項式鏈表依然存在，不發(fā)生任何改變，如果要再對原來兩個多項式進行其它操作也不影響。下面哪些情形是單鏈表形成了圈？NoneNone微軟面試題（初級難度）如何用最少個數(shù)的額外變量去判斷一個單鏈表形成圈？請給出需要額外變量的個數(shù)和你算法的時間復雜度。微軟面試題（中級難度）如何用最少個數(shù)的額外變量去判斷兩條單鏈表是否相交？請給出需要額外變量的個數(shù)和你算法的時間復雜度。