《資料結構與算法：Python語言描述》一3.5表的應用

本節書摘來自華章出版社《資料結構與算法：python語言描述》一書中的第3章，第3.5節，作者 裘宗燕，更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視

本節通過一個簡單的例子展示表結構的使用。這裡給出了同一個問題的幾種不同實作，其中使用了不同的表結構。

josephus問題是資料結構教材中一個常見的執行個體：假設有n個人圍坐一圈，現在要求從第k個人開始報數，報到第m個數的人退出。然後從下一個人開始繼續報數并按同樣規則退出，直至所有人退出。要求按順序輸出各出列人的編号。

本節考慮第一種解決方法：基于python的list和固定大小的“數組”概念，也就是說，在這裡把list看作元素個數固定的對象，隻修改元素的值，不改變表的結構（不用加入或删除元素的操作）。這相當于擺了一圈n把椅子，人可以走但椅子在那裡且位置不變。基于這種設計可以有多種實作方法。下面的方法是給每個人賦予一個編号，沒有人的情況用0表示，各list的元素記錄這些編号。算法梗概：

初始：

建立一個包含n個人（的編号）的表。

找到第k個人，從那裡開始。

處理過程中采用把相應表元素修改為0的方式表示已出列，反複做：

數m個（尚在坐的）人，遇到表的末端就轉回下标0繼續。

把表示第m個人的表元素修改為0。

n個人出列即結束。

下面算法裡用i表示數組下标，其初值取k-1，内層循環中每次加一并通過取模n保持i的取值範圍正确。大循環一次疊代出列一人，共計執行n次疊代。循環體裡的count計數直至m（通過内層循環），計數中跳過空椅子。其他部分都很容易了解。

這裡函數名中的a表示數組實作。函數的使用執行個體如下：

josephus_a(10, 2, 7)

定義這個函數的主要麻煩是表下标的（循環）計數i和表中有效元素的計數count互相脫節。計數變量count達到m時輸出表元素下标i，并将該元素置0，表示這個人已經出列。輸出了最後一個元素後讓print輸出一個換行符。

這個算法的複雜度不容易分析。内層循環的總疊代次數是i加1的次數，應該與n和m有關，因為m影響到找到下一進制素的操作步數。考慮兩個特殊情況：

當m＝1時，每次内循環隻執行一次疊代，總的時間開銷是o(n)。

當m＝n時，先考慮計算到最後表中隻剩一個元素的情況。不難看到，内層循環需要周遊整個表n遍，每一遍隻能把count的值加1，是以，為了删除這個元素，花費的時間就是o(n2)。整個計算中i加1的次數大約是

可見這個算法分析中的麻煩，這裡不進一步讨論了。

現在考慮另一個算法：把儲存人員編号的list按表的方式處理，一旦确定了應該退出的人，就将表示其編号的表元素從表中删除。

這樣，随着計算的進行，所用的表将變得越來越短。下面用num表示表的長度，每退出一人，表的長度num減一，至表長度為0時計算工作結束。采用這種想法和設計，表中的元素全是有效元素（不再出現表示沒人的0），元素計數與下标計數得到統一，是以下标更新可以用i=(i+m-1)%num統一描述。

基于這些想法寫出的程式非常簡單：

函數體是一個簡單的循環計數，很容易了解。其中用list的pop操作删除元素。最後的輸出語句值得說一下，其中用了一個條件表達式确定一次輸出的結束字元串：如果整個計算還沒完成（num的值大于1時），就在輸出了出列人的編号後加上一個逗号；如果所有人的編号都已輸出，就輸出一個換行符。

函數調用的形式與前一函數相同，如：josephus_l(10, 2, 7)。

這個算法的複雜度比較容易考慮。雖然函數循環隻執行n次，但由于輸出語句調用了list的pop操作，它需要線性時間，是以算法複雜度是o(n2)。由于這裡直接加m計算位置，是以算法的複雜度與m無關。

現在考慮基于循環單連結清單實作一個算法。

從形式上看，循環單連結清單可以很直覺地表示圍坐一圈的人，順序數人頭可以自然地反映為在循環表中沿着next鍊掃描，一個人退出可以用删除相應結點的操作模拟。在這樣做之後，又可以沿着原方向繼續數人頭了。

根據上面分析，這個算法應該分為兩個階段：

1）建立包含指定個數（和内容）的結點的循環單連結清單，這件事可以通過從空表出發，在尾部逐個加入元素的方式完成。

2）循環計數，找到并删除應該退出的結點。

具體實作可以有多種方式，例如：為原循環單連結清單增加一個循環數數的函數，然後寫一段程式建立所需的循環單連結清單，并完成操作。下面的實作采用了另一種方式，即基于循環單連結清單類派生出一個專門的類，用其初始化方法完成全部工作。

派生類josephus的實作中沒有增加“目前人指針”一類設定，采用了另一種考慮，把計數過程看作人圈的轉動（結點環的轉動）。這個類裡定義了新方法turn，它将循環表對象的rear指針沿next方向移m步（相當于結點環旋轉）。

這個類的初始化函數首先調用基類lclist的初始化函數建立一個空表，然後通過一個循環建立包含n個結點和相應資料的初始循環表。最後的循環反複調用turn方法，找到并逐個彈出結點，輸出結點裡儲存的編号。

雖然這裡用了一個類作為基礎，其使用的方式卻與調用一個函數類似，建立這個類的對象就是完成一次計算，如josephus(10, 2, 7)。所建立對象本身并不重要。

這個算法的時間複雜度比較容易考慮：建立初始表的複雜度是o(n)，後面循環的算法複雜度為o(m×n)，因為總共做了m×n次一步旋轉，每次是o(1)。

本章讨論了線性表的概念、其基本運算和抽象資料類型，以及兩種實作技術（順序表和連結表實作）。線性表是一種比較簡單的資料結構，是n個資料元素的有限序列，各元素在表中有特定的排列位置和前後順序關系。

順序表

線上性表的順序存儲實作（順序表）中，元素存儲在一塊大存儲區裡，它們之間的邏輯順序關系通過實際存儲位置直接反映。順序表裡隻需要存放資料元素本身的資訊，是以存儲密度大，空間使用率高。另外，元素的存儲位置可以基于下标通過簡單的算式算出，是以可以在o(1) 時間内随機存取。這些是順序存儲結構的優點。

另一方面，由于采用連續方式存儲元素，順序表技術的靈活性不足。為了有效支援元素的插入和删除，順序表中需要預留一些空閑的空間。如果順序表的長度變化較大，通常需要按最大需要安排存儲空間。這些情況帶來的空置存儲位置也形成額外的存儲開銷。此外，在順序表裡插入和删除都可能需要移動許多元素，操作的代價通常都比較高。這些是線性表順序存儲結構的缺點。特殊情況是表的尾端插入和删除為o(1)操作。

由于采用連續方式存儲元素，需要首先安排确定大小的存儲空間。這樣，如果程式運作中不斷加入元素，最終會填滿整個元素空間，這時再插入元素的操作就無法完成了。動态順序表技術可以解決這個問題，避免由于表滿而導緻程式被迫終止。采用這種技術出現了一個新問題：原本高效的後端插入操作，也可能由于擴存而比較耗時。這種偶發的情況可能影響程式的行為，在開發對時間效率要求高的程式時，需要特别注意。另一情況是擴存政策，需要在平均操作效率和閑置存儲量之間權衡。

連結表

在連結實作（連結表）裡，表元素儲存在一批較小的存儲塊裡，通過顯式的連結将這些塊連成一串，形成一種鍊式結構。結點的連結結構直接反映元素的順序關系。

在連結表中，表元素之間的順序由它們所在的結點之間的連結顯式表示，是以表結點可以任意安排位置，靈活地調整結構，通過調整連結完成表元素的插入、删除和各種重整順序的操作。這些情況說明，連結表實作的靈活性較強，操作的實作方式更加靈活多樣。對于一些應用，這種靈活性是非常重要的。

也應該看到另一些情況。為了實作連結表，每個結點都需要增加一個連結域，付出額外的存儲空間代價。但是表中并不需要預留白閑位置，有多少元素就建立多少結點。對于一個連結清單，能直接掌握的隻是其中一兩個結點（首結點，以及可能的尾結點），要通路其他結點，隻能順着連結一步步去查找。是以連結清單中的元素不能随機通路，按位置通路的代價很高。由于這種情況，使用連結清單的最合理方式是前端操作和按元素順序通路。增加了尾結點引用後，可以支援受限的後端操作，包括表元素通路和新元素插入，但不包括删除。引入相反方向的連結（雙連結清單的前向連結），可以增加一種資料通路順序，也使表中間結點的操作更加友善，但并沒有改變連結表的本質。

連結清單的另一個特點是存在很多變形。為突破簡單單連結清單帶來的操作限制，可以引入尾結點指針，建立循環連結，或者為每個結點增加一個反向連結（形成雙連結清單）。每種變形都能使一些操作的實作更直接，提高操作的效率；但要付出存儲的代價，也給一些操作的實作帶來新問題，如尾指針的維護、前向連結的維護等。

讨論

實際上，順序表與連結表并不是決然相對的兩種技術。本章讨論的連結表采用一個結點裡存放一個表元素的方式，是最常見的方式，也是一種極端的安排。實際上，完全可以在一個連結結點裡存儲多個表元素，形成連續存儲和連結存儲的一種混合形式。從這個角度看，順序表也是連結表的一種特殊形式，這種連結表隻有一個結點，所有表元素都儲存在這個結點裡。回憶一下圖3.6的分離式實作，情況可以看得很清楚。

順序表的另一個優點是通路的局部性。表元素順序映射到記憶體中連續的單元裡，下一個元素的實際存儲位置與目前元素很近。由于目前各種新型計算機體系結構的特點，順序通路記憶體中相近位置的效率比較高，而真正的随機記憶體通路效率較低。對于連結表，邏輯上的下一個結點可能被安排在記憶體中的任何位置，邏輯上的順序通路實際上可能是對計算機記憶體中許多不同地方的随機通路，效率比較低。

另一方面，順序表需要較大的連續空間，這一情況有時也會帶來問題。如果需要建立儲存很多元素的巨大的表，采用順序表可能給python解釋器的存儲管理帶來麻煩。連結表的結點是小塊存儲，無論表有多麼大，存儲管理問題都容易處理。

如前所述，順序結構和連結結構是程式裡構造複雜資料結構的兩種基本技術，順序表和連結表是這兩種技術的典型代表。對這兩種表的操作技術也是最典型的複雜資料結構操作技術，以及最重要的設計和程式設計技術。通過對這兩種表結構的操作練習，能夠大大提升初學者的程式設計水準。本章學習的一個重點是連結表操作，這是進階程式設計技術的一個難點，也是（幾乎）一切進階程式設計技術的基礎。

此外，本章内容還展示了一些重要的面向對象程式設計技術，讨論了如何通過繼承已有的類構造新的具有類似功能（或結構）的類，以滿足實際需要。

練習

一般練習

1.複習下面概念：線性表（表），基本元素集合，元素集合和序列，下标，空表，（表的）長度，順序關系（線性關系），首元素，尾元素，前驅和後繼，資料抽象的實作者和使用者，順序表（連續表）和連結表（連結清單），順序表的元素布局，索引和索引結構，容量，（元素）周遊，查找（檢索），定位，加入和删除元素，尾端加入（插入）和删除，保序插入和删除，表的一體式實作和分離式實作，動态順序表，元素存儲區的增長政策（線性增長，加倍增長），元素反轉和排序，連結結構，單連結清單（單向連結表），連結，表頭變量（表頭指針），空連結，連結清單處理的掃描模式，彙集對象，尾結點引用，循環單連結清單，雙向連結表（雙連結清單），循環雙連結清單，連結清單反轉，連結清單排序，josephus問題，随機存取，順序存取，通路的局部性，類定義的内在一緻性。

2.下面哪些事物的相關資訊适合用線性表存儲和管理，為什麼？

a）在銀行排隊等候服務的顧客；

b）書架上的一排書籍；

c）計算機桌面上的各種圖示及其相關資訊；

d）計算機的檔案和目錄（檔案夾）系統；

e）個人的電話簿；

f）工廠流水線上的一系列工位；

g）個人銀行賬戶中的多筆定期存款；

h）一輛汽車的所有部件和零件。

3.假設需要頻繁地線上性表的一端插入/删除元素。如果用順序表實作，應該用哪一端作為操作端？如果用連結表實作呢？為什麼？

4.假設線性表的一個應用場景是基于位置通路表中元素和在表的最後插入/删除元素，采用哪種結構實作線性表最為合理，為什麼？

5.在某種連結表使用場景中，最常用操作是在表首元素之前插入或删除元素，以及在表尾元素之後插入元素。此時采用哪種實作技術最為合适？為什麼？

6.請列舉出順序表的主要缺點，如果改用連結表能否避免這些缺點？請交換兩者的角色并重新考慮類似的問題。

7.請仔細總結順序表和連結表的特點，并設法提出一些操作場景，在其中采用一種結構比較合适而采用另一種則非常不合适。

8.設法總結出一些設計和選擇的原則，說明在什麼情況下應該優先使用順序表，在什麼情況下應該優先使用連結表。

9.請考慮兩個排序序列（例如元素按“＜”關系從小到大排序）的合并操作，稱為歸并，并設計一種算法實作這種序列的歸并。分析你設計的算法，如果其複雜性不是o(max(m, n))，請修改算法使之達到o(max(m, n))（其中m和n是兩個序列的長度）。

10.請從操作實作的友善性和效率的角度比較帶尾結點指針的單連結清單和循環單連結清單，以及它們相對于簡單單連結清單的優點和缺點等，并總結在什麼情況下應該使用這兩種結構，或應優先使用其中某一種。

11.請全面比較循環單連結清單和雙連結清單的各方面特點。

程式設計練習

1.檢查本章開始定義的線性表抽象資料類型和3.3節定義的連結清單類llist，給llist加入在抽象資料類型中有定義，但llist類沒定義的所有操作。

2.請為llist類增加定位（給定順序位置的）插入和删除操作。

3.給llist增加一個元素計數值域num，并修改類中操作，維護這個計數值。另外定義一個求表中元素個數的len函數。python的内置标準函數len可以自動調用使用者定義類裡的相關函數__len__，也可以用它作為方法名。請比較這種實作和原來沒有元素計數值域的實作，說明兩者各自的優缺點。

4.請基于元素相等操作“==”定義一個單連結清單的相等比較函數。另請基于字典序的概念，為連結表定義大于、小于、大于等于和小于等于判斷。

5.請為連結表定義一個方法，它基于一個順序表參數構造一個連結表；另請定義一個函數，它從一個連結表構造出一個順序表。

6.請為單連結清單類增加一個反向周遊方法rev_visit(self, op)，它能按從後向前的順序把操作op逐個作用于表中元素。你定義的方法在整個周遊中通路結點的總次數與表長度n是什麼關系？如果不是線性關系，請設法修改實作，使之達到線性關系。這裡要求周遊方法的空間代價是o(1)。（提示：你可以考慮為了周遊而修改表的結構，隻要能在周遊的最後将表結構複原。）

7.請為單連結清單類定義下面幾個元素删除方法，并保持其他元素的相對順序：

a）del_minimal()删除當時連結清單中的最小元素；

b）del_if(pred)删除目前連結清單裡所有滿足謂詞函數pred的元素；

c）del_duplicate()删除表中所有重複出現的元素。也就是說，表中任何元素的第一次出現保留不動，後續與之相等的元素都删除。

要求這些操作的複雜度均為o(n)，其中n為表長。

8.請為單連結清單類定義一個變動方法interleaving(self,　another)，它把另一個單連結清單another的元素交錯地加入本單連結清單。也就是說，結果單連結清單中的元素是其原有元素與單連結清單another中元素的一一交錯的序列。如果某個表更長，其剩餘元素應位于修改後的單連結清單的最後。

9.考慮實作單連結清單插入排序的另一個想法：插入排序也就是把要排序的元素一個個按序插入到一個元素已經排好序的連結清單裡，從空連結清單開始。請根據這個想法實作另一個完成單連結清單排序的插入排序函數。

10.定義一個單連結清單剖分函數partition(lst, pred)，其參數為單連結清單lst和謂詞函數pred，函數partition傳回一對單連結清單（一個序對），其中第一個單連結清單包含着原連結清單lst裡所有值滿足pred的結點，第二個連結清單裡是所有其他結點。注意，兩個表裡的結點還應保持原表裡結點的相對順序。也就是說，如果在某結果表裡結點a的後繼結點是b，在原表lst裡a一定位于b之前。

11.擴充本章給出的循環單連結清單類cllist，實作llist1中有定義的所有方法。

12.請為循環單連結清單類擴充一個方法interleaving(self, another)，要求見上面針對簡單單連結清單的有關習題。

13.請為循環單連結清單類定義前面各習題中針對簡單單連結清單類提出的方法。

14.請基于python的list實作一個元素排序的順序表類，其中元素按“＜”關系從小到大排序存放。考慮需要定義的方法并給出定義，包括一個方法merge(self, another)，其參數another是另一個排序順序表。該方法将another的元素加入本順序表，并保證結果表中的資料仍是正确排序的。

15.請從簡單單連結清單類派生一個排序單連結清單類，表中元素按“＜”關系從小到大排序存放。首先考慮需要覆寫的方法并給出定義。為該類增加方法merge(self, another)，參數another也是排序單連結清單。該方法将連結清單another的元素加入本連結清單，并保證結果連結清單中的資料仍是正确排序的。

16.請為雙連結清單類定義reverse方法和sort方法，要求通過搬移結點中資料的方式實作這兩個操作。

17.請為雙連結清單類定義reverse1方法和sort1方法，要求操作中不移動結點中的資料，隻修改結點之間的連結。

18.實作雙連結清單排序的一種可能做法是直接利用單連結清單的排序函數，隻将結點按next方向正确排序連結，最後重建立立prev連結關系。請基于這個想法為雙連結清單類實作一個排序方法，其中直接調用單連結清單類的插入排序方法。

19.請實作一個循環雙連結清單類。

20.請考慮一種在一個結點裡存儲16個元素的單向連結表，定義一個類實作這種連結清單，為這個類定義各種重要的線性表操作。請從各方面比較這種實作與每個結點存儲一個元素的簡單實作。

21.利用（順序或連結）表和第2章的人事記錄類，實作一個簡單的學校人事管理系統。首先分析問題，描述一個人事管理adt，而後實作這個系統。由于不需生成多個執行個體，可以用類的資料屬性儲存人事資訊（的表），用一組類方法實作必要操作。這是一種在python語言中建立單例（singleton）資料抽象的技術。

22.利用連結表實作一種大整數類bigint。用一個連結清單表示一個大整數，表中每個結點儲存一位十進制整數，這樣，任意長的連結清單就可以儲存任意長的整數了。請實作這種大整數的各種重要運算。

23.連結表裡的結點都是獨立存在的對象，有可能脫離原來所在的表，或者從一個表轉移到另一個表。從表對象出發通過周遊可以通路表中的每個結點（及其資料），而從一個表結點出發則無法确定它屬于哪個表（或者不屬于任何一個表）。請分析這個問題，考慮在什麼場景下确定結點的歸屬問題有重要意義。考慮下面的技術：為每個結點增加一個“表指針”指向其所屬的表。定義一個類實作這種表。