1、第 1 章 緒 論11.1 本章導學11.2 習題解析2第 2 章 線性表92.1 本章導學92.2 習題解析10第 3 章 棧和隊列193.1 本章導學193.2 習題解析20第 4 章 字符串和多維數組264.1 本章導學264.2 習題解析27第 5 章 樹和二叉樹325.1 本章導學325.2 習題解析33第 6 章 圖436.1 本章導學436.2 習題解析44第 7 章 查找技術567.1 本章導學567.2 習題解析57第 8 章 排序技術678.1 本章導學678.2 習題解析68第 9 章 索引技術789.1 本章導學789.2 習題解析78第 1 章 緒 論1.1 本章導學

2、1. 知識結構圖 本章的知識結構如圖1-1所示，其中第二層的橢圓代表本章的學習主線。數據數據元素數據結構抽象數據類型邏輯結構數據結構的分類存儲結構常用存儲方法算法算法特性評價算法描述算法問題規模基本語句時間復雜度大O記號圖1-1 知識結構圖緒 論數據結構算 法基本概念邏輯結構存儲結構基本概念算法分析關 系2. 學習要點對本章的學習要從兩條主線出發，一條主線是數據結構，包括數據結構的相關概念及含義，另一條主線是算法，包括算法的相關概念、描述方法以及時間復雜度的分析方法。在學習數據結構時要抓住兩個方面：邏輯結構和存儲結構，并注意把握二者之間的關系。在學習算法時，要以算法的概念和特性為基本點，并在以

3、后的學習中注意提高算法設計的能力。對于算法時間性能的分析，要將注意力集中在增長率上，即基本語句執行次數的數量級，在設計算法時，養成分析算法時間性能的習慣，進而有效地改進算法的效率。1.2 習題解析1. 填空（1）（ ）是數據的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。【解答】數據元素（2）（ ）是數據的最小單位，（ ）是討論數據結構時涉及的最小數據單位。【解答】數據項，數據元素【分析】數據結構指的是數據元素以及數據元素之間的關系。（3）從邏輯關系上講，數據結構主要分為（ ）、（ ）、（ ）和（ ）。【解答】集合，線性結構，樹結構、圖結構（4）數據的存儲結構主要有（ ）和（ ）兩種

4、基本方法，不論哪種存儲結構，都要存儲兩方面的內容：（ ）和（ ）。【解答】順序存儲結構，鏈接存儲結構，數據元素，數據元素之間的關系（5）算法具有五個特性，分別是（ ）、（ ）、（ ）、（ ）、（ ）。【解答】有零個或多個輸入，有一個或多個輸出，有窮性，確定性，可行性（6）算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四種，其中，（ ）被稱為算法語言。【解答】自然語言，程序設計語言，流程圖，偽代碼，偽代碼（7）在一般情況下，一個算法的時間復雜度是（ ）的函數。【解答】問題規模（8）設待處理問題的規模為n，若一個算法的時間復雜度為一個常數，則表示成數量級的形式為（ ），若為2n*log25n

5、+ 8n，則表示成數量級的形式為（ ）。【解答】(1)，(nlog2n)【分析】用大O記號表示算法的時間復雜度，需要將低次冪去掉，將最高次冪的系數去掉。2. 選擇題（1）順序存儲結構中數據元素之間的邏輯關系是由（ ）表示的，鏈接存儲結構中的數據元素之間的邏輯關系是由（ ）表示的。A 線性結構 B 非線性結構 C 存儲位置 D 指針【解答】C，D【分析】順序存儲結構就是用一維數組存儲數據結構中的數據元素，其邏輯關系由存儲位置（即元素在數組中的下標）表示；鏈接存儲結構中一個數據元素對應鏈表中的一個結點，元素之間的邏輯關系由結點中的指針表示。（2）假設有如下遺產繼承規則：丈夫和妻子可以相互繼承遺產；

6、子女可以繼承父親或母親的遺產；子女間不能相互繼承遺產。則表示該遺產繼承關系的最合適的數據結構應該是（ ）。A 樹 B 圖 C 線性表 D 集合【解答】B【分析】將丈夫、妻子和子女分別作為數據元素，根據繼承關系畫出邏輯結構圖如圖1-2丈夫妻子子女n子女1圖1-2 遺產繼承邏輯結構圖所示。（3）計算機所處理的數據一般具有某種內在聯系，這是指（ ）。A 數據和數據之間存在某種關系 B 元素和元素之間存在某種關系C 元素內部具有某種結構 D 數據項和數據項之間存在某種關系【解答】B【分析】數據結構是指相互之間存在一定關系的數據元素的集合，數據元素是討論數據結構時涉及的最小數據單位，元素內部各數據項一般

7、不予考慮。（4）對于數據結構的描述，下列說法中不正確的是（ ）。A 相同的邏輯結構對應的存儲結構也必相同B 數據結構由邏輯結構、存儲結構和基本操作三方面組成C 對數據結構基本操作的實現與存儲結構有關D 數據的存儲結構是數據的邏輯結構的機內實現【解答】A【分析】相同的邏輯結構可以用不同的存儲結構實現，一般來說，在不同的存儲結構下基本操作的實現是不同的，例如線性表可以順序存儲也可以鏈接存儲，在順序存儲和鏈接存儲結構下插入操作的實現截然不同。（5）可以用（ ）定義一個完整的數據結構。A 數據元素 B 數據對象 C 數據關系 D 抽象數據類型【解答】D【分析】抽象數據類型是一個數據結構以及定義在該結構

8、上的一組操作的總稱。（6）算法指的是（ ）。A 對特定問題求解步驟的一種描述，是指令的有限序列。B 計算機程序 C 解決問題的計算方法 D 數據處理【解答】A【分析】計算機程序是對算法的具體實現；簡單地說，算法是解決問題的方法；數據處理是通過算法完成的。所以，只有A是算法的準確定義。（7）下面（ ）不是算法所必須具備的特性。A 有窮性 B 確切性 C 高效性 D 可行性【解答】C【分析】高效性是好算法應具備的特性。（8）算法分析的目的是（ ），算法分析的兩個主要方面是（ ）。A 找出數據結構的合理性 B 研究算法中輸入和輸出的關系C 分析算法的效率以求改進 D 分析算法的易讀性和文檔性E 空間

9、性能和時間性能 F 正確性和簡明性G 可讀性和文檔性 H 數據復雜性和程序復雜性【解答】C，E3. 判斷題 算法的時間復雜度都要通過算法中的基本語句的執行次數來確定。【解答】錯。時間復雜度要通過算法中基本語句執行次數的數量級來確定。 每種數據結構都具備三個基本操作：插入、刪除和查找。【解答】錯。如數組就沒有插入和刪除操作。此題注意是每種數據結構。 所謂數據的邏輯結構指的是數據之間的邏輯關系。【解答】錯。是數據之間的邏輯關系的整體。 邏輯結構與數據元素本身的內容和形式無關。【解答】對。因此邏輯結構是數據組織的主要方面。 基于某種邏輯結構之上的基本操作，其實現是唯一的。【解答】錯。基本操作的實現是

10、基于某種存儲結構設計的，因而不是唯一的。4. 分析以下各程序段，并用大O記號表示其執行時間。 i = 1; k = 0; while (i = n) k = k + 10 * i;i+; i = 1; k = 0; do k = k + 10 * i;i+; while (i = n); y = 0; while (y + 1) *(y + 1) = n) y = y + 1; i = 1; j = 0;while (i + j j) j+; else i+; for (i = 1; i = n; i+) for (j = 1; j = i; j+) for (k = 1; k = j; k+

11、) x+;【解答】 基本語句是k=k+10*i，共執行了n-2次，所以T(n)=O(n)。 基本語句是k=k+10*i，共執行了n次，所以T(n)=O(n)。 分析條件語句，每循環一次，i+j 整體加1，共循環n次，所以T(n)=O(n)。 設循環體共執行T(n)次，每循環一次，循環變量y加1，最終T(n)=y，即： (T(n)+1)2n，所以T(n)=O(n1/2)。 x+是基本語句，所以 5解答下列問題（1）設有數據結構（D，R），其中D = 1, 2, 3, 4, 5, 6，R = (1, 2),(2, 3),(2, 4),(3, 4),(3, 5),(3, 6),(4, 5),(4,

12、6)。試畫出其邏輯結構圖并指出屬于何種結構。142563圖1-3 邏輯結構圖【解答】其邏輯結構圖如圖1-3所示，它是一種圖結構。（2）為整數定義一個抽象數據類型，包含整數的常見運算，每個運算對應一個基本操作，每個基本操作的接口需定義前置條件、輸入、功能、輸出和后置條件。【解答】整數的抽象數據類型定義如下： ADT integer Data 整數：可以是正整數(1, 2, 3, )、負整數(-1, -2, -3, )和零 Operation Constructor 前置條件：整數a不存在 輸入：一個整數b 功能：構造一個與輸入值相同的整數 輸出：無 后置條件：整數a具有輸入的值 Set 前置條件

13、：存在一個整數a 輸入：一個整數b 功能：修改整數a的值，使之與輸入的整數值相同 輸出：無 后置條件：整數a的值發生改變 Add 前置條件：存在一個整數a 輸入：一個整數b 功能：將整數a與輸入的整數b相加 輸出：相加后的結果 后置條件：整數a的值發生改變 Sub 前置條件：存在一個整數a 輸入：一個整數b 功能：將整數a與輸入的整數b相減 輸出：相減的結果 后置條件：整數a的值發生改變 Multi 前置條件：存在一個整數a 輸入：一個整數b 功能：將整數a與輸入的整數b相乘 輸出：相乘的結果 后置條件：整數a的值發生改變 Div 前置條件：存在一個整數a 輸入：一個整數b 功能：將整數a與輸

14、入的整數b相除 輸出：若整數b為零，則拋出除零異常，否則輸出相除的結果 后置條件：整數a的值發生改變 Mod 前置條件：存在一個整數a 輸入：一個整數b 功能：求當前整數與輸入整數的模，即正的余數 輸出：若整數b為零，則拋出除零異常，否則輸出取模的結果 后置條件：整數a的值發生改變 Equal 前置條件：存在一個整數a 輸入：一個整數b 功能：判斷整數a與輸入的整數b是否相等 輸出：若相等返回1，否則返回0 后置條件：整數a的值不發生改變endADT（3）求多項式A(x)的算法可根據下列兩個公式之一來設計： A(x)=anxn+an-1xn-1+a1x+a0 A(x)=(anx+an-1)x+

15、a1)x)+a0根據算法的時間復雜度分析比較這兩種算法的優劣。【解答】第二種算法的時間性能要好些。第一種算法需執行大量的乘法運算，而第二種算法進行了優化，減少了不必要的乘法運算。（4）選擇和評價數據結構的標準與方法是什么？【解答】首先，對給定的實際問題可以建立不同的數據結構；其次，對于給定的數據結構，可以選擇不同的存儲實現，即采用不同的存儲結構；再次，在給定數據結構和存儲結構的條件下，對同一基本操作可以設計出不同算法。因此，數據的邏輯結構、存儲結構和操作（特別是基本操作）的實現這三者是密切相關的。一般地，在建立數據結構時應該考慮以下三個方面： 確定表示問題所需的數據及其特性； 確定必須支持的基

16、本操作，并度量每種操作所受的時、空資源限制，某些重要的操作，例如查找、插入和刪除的資源限制通常決定了數據結構的選擇； 選擇（或設計）最接近這些開銷的數據結構。6. 算法設計（要求：用偽代碼和C+描述兩種方法描述算法，并分析時間復雜度） 對一個整型數組An設計一個排序算法。【解答】下面是簡單選擇排序算法的偽代碼描述。 1. 對n個記錄進行n-1趟簡單選擇排序： 1.1 在無序區i，n-1中選取最小記錄，設其下標為index； 1.2 將最小記錄與第i個記錄交換； 下面是簡單選擇排序算法的C+描述。void SelectSort(int r , int n) for (i = 0; i n - 1

17、; i+) /對n個記錄進行n-1趟簡單選擇排序 index = i; for (j = i + 1; j n; j+) /在無序區中選取最小記錄 if (rj max，則Ai為最大值，原來的最大值為次最大值；2.2 否則，如果Ainmax，則最大值不變，Ai為次最大值；3. 輸出最大值max，次最大值nmax； 算法的C+描述如下：void Max_NextMax(int A , int n, int & max, int & nmax)if (A0 = A1) max = A0; nmax = A1;else max = A1; nmax = A0; for (i = 2; i = max

18、) nmax = max; max = Ai; else if (Ai nmax) nmax = Ai; cout最大值為：maxn次最大值為：nmaxnext=(p-next)-next 單鏈表中設置頭結點的作用是（ ）。【解答】為了運算方便【分析】例如在插入和刪除操作時不必對表頭的情況進行特殊處理。 非空的單循環鏈表由頭指針head指示，則其尾結點（由指針p所指）滿足（ ）。【解答】p-next=head【分析】如圖2-8所示。heada1a2an p圖2-8 尾結點p與頭指針head的關系示意圖 在由尾指針rear指示的單循環鏈表中，在表尾插入一個結點s的操作序列是（ ）；刪除開始結點的

19、操作序列為（ ）。【解答】s-next =rear-next; rear-next =s; rear =s; q=rear-next-next; rear-next-next=q-next; delete q;【分析】操作示意圖如圖2-9所示：a1a2an rear sq圖2-9 帶尾指針的循環鏈表中插入和刪除操作示意圖rear 一個具有n個結點的單鏈表，在指針p所指結點后插入一個新結點的時間復雜度為（ ）；在給定值為x的結點后插入一個新結點的時間復雜度為（ ）。【解答】(1)，(n)【分析】在p所指結點后插入一個新結點只需修改指針，所以時間復雜度為(1)；而在給定值為x的結點后插入一個新結點

20、需要先查找值為x的結點，所以時間復雜度為(n)。 可由一個尾指針唯一確定的鏈表有（ ）、（ ）、（ ）。【解答】循環鏈表，循環雙鏈表，雙鏈表2. 選擇題 線性表的順序存儲結構是一種（ ）的存儲結構，線性表的鏈接存儲結構是一種（ ）的存儲結構。A 隨機存取 B 順序存取 C 索引存取 D 散列存取【解答】A，B【分析】參見2.2.1。 線性表采用鏈接存儲時，其地址（ ）。A 必須是連續的 B 部分地址必須是連續的C 一定是不連續的 D 連續與否均可以【解答】D【分析】線性表的鏈接存儲是用一組任意的存儲單元存儲線性表的數據元素，這組存儲單元可以連續，也可以不連續，甚至可以零散分布在內存中任意位置。

21、 單循環鏈表的主要優點是（ ）。A 不再需要頭指針了 B 從表中任一結點出發都能掃描到整個鏈表；C 已知某個結點的位置后，能夠容易找到它的直接前趨；D 在進行插入、刪除操作時，能更好地保證鏈表不斷開。【解答】B 鏈表不具有的特點是（ ）。A 可隨機訪問任一元素 B 插入、刪除不需要移動元素C 不必事先估計存儲空間 D 所需空間與線性表長度成正比【解答】A 若某線性表中最常用的操作是取第i 個元素和找第i個元素的前趨，則采用（ ）存儲方法最節省時間。A 順序表 B 單鏈表 C 雙鏈表 D 單循環鏈表【解答】A【分析】線性表中最常用的操作是取第i 個元素，所以，應選擇隨機存取結構即順序表，同時在順

22、序表中查找第i個元素的前趨也很方便。單鏈表和單循環鏈表既不能實現隨機存取，查找第i個元素的前趨也不方便，雙鏈表雖然能快速查找第i個元素的前趨，但不能實現隨機存取。 若鏈表中最常用的操作是在最后一個結點之后插入一個結點和刪除第一個結點，則采用（ ）存儲方法最節省時間。A 單鏈表 B 帶頭指針的單循環鏈表 C 雙鏈表 D 帶尾指針的單循環鏈表【解答】D【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、帶頭指針的單循環鏈表、雙鏈表都不合適，考慮在帶尾指針的單循環鏈表中刪除第一個結點，其時間性能是O(1)，所以，答案是D 。 若鏈表中最常用的操作是在最后一個結點之后插

23、入一個結點和刪除最后一個結點，則采用（ ）存儲方法最節省運算時間。A 單鏈表 B 循環雙鏈表 C單循環鏈表 D 帶尾指針的單循環鏈表【解答】B【分析】在鏈表中的最后一個結點之后插入一個結點需要知道終端結點的地址，所以，單鏈表、單循環鏈表都不合適，刪除最后一個結點需要知道終端結點的前驅結點的地址，所以，帶尾指針的單循環鏈表不合適，而循環雙鏈表滿足條件。 在具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】B【分析】首先應順序查找新結點在單鏈表中的位置。 對于n個元素組成的線性表，建立一個有序單鏈表的時

24、間復雜度是（ ）。A O(1) B O(n) C O(n2) D O(nlog2n)【解答】C【分析】該算法需要將n個元素依次插入到有序單鏈表中，而插入每個元素需O(n)。 使用雙鏈表存儲線性表，其優點是可以（ ）。A 提高查找速度 B 更方便數據的插入和刪除C 節約存儲空間 D 很快回收存儲空間【解答】B【分析】在鏈表中一般只能進行順序查找，所以，雙鏈表并不能提高查找速度，因為雙鏈表中有兩個指針域，顯然不能節約存儲空間，對于動態存儲分配，回收存儲空間的速度是一樣的。由于雙鏈表具有對稱性，所以，其插入和刪除操作更加方便。 在一個單鏈表中，已知q所指結點是p所指結點的直接前驅，若在q和p之間插入

25、s所指結點，則執行（ ）操作。A s-next=p-next; p-next=s; B q-next=s; s-next=p; C p-next=s-next; s-next=p; D p-next=s; s-next=q;【解答】B【分析】注意此題是在q和p之間插入新結點，所以，不用考慮修改指針的順序。 在循環雙鏈表的p所指結點后插入s所指結點的操作是（ ）。A p-next=s; s-prior=p; p-next-prior=s; s-next=p-next; B p-next=s; p-next-prior=s; s-prior=p; s-next=p-next;C s-prior=p

26、; s-next=p-next; p-next=s; p-next-prior=s;D s-prior=p; s-next=p-next; p-next-prior=s; p-next=s【解答】D【分析】在鏈表中，對指針的修改必須保持線性表的邏輯關系，否則，將違背線性表的邏輯特征，圖2-10給出備選答案C和D的圖解。(a) 備選答案C操作示意圖(第4步指針修改無法進行) (b) 備選答案D操作示意圖 圖2-10 雙鏈表插入操作修改指針操作示意圖sai-1aixpsai-1aixp（13）用數組r存儲靜態鏈表，結點的next域指向后繼，工作指針j指向鏈中某結點，則j后移的操作語句為（ ）。A

27、j = rj.next B j = j + 1 C j = j-next D j = rj- next【解答】A【分析】注意next是數組下標，因此排除C和D，對于備選答案B，假設工作指針j指向某結點p，則j+1不一定指向結點p的后繼結點。（14）設線性表有n個元素，以下操作中，（ ）在順序表上實現比在鏈表上實現的效率更高。A 輸出第i（1in）個元素值 B 交換第1個和第2個元素的值C 順序輸出所有n個元素 D 查找與給定值x相等的元素在線性表中的序號【解答】A【分析】在順序表上輸出第i（1in）個元素值需要O(1)時間，在鏈表上輸出第i（1in）個元素值需要O(n)時間；在順序表上和鏈表上

28、交換第1個和第2個元素的值都需要O(1)時間；在順序表上和鏈表上順序輸出所有n個元素都需要O(n)時間；在順序表上和鏈表上查找與給定值x相等的元素都需要進行順序查找，需要O(n)時間。3. 判斷題 線性表的邏輯順序和存儲順序總是一致的。【解答】錯。順序表的邏輯順序和存儲順序一致，鏈表的邏輯順序和存儲順序不一定一致。 線性表的順序存儲結構優于鏈接存儲結構。【解答】錯。兩種存儲結構各有優缺點。 設p，q是指針，若p=q，則*p=*q。【解答】錯。p=q只能表示p和q指向同一起始地址，而所指類型則不一定相同。 線性結構的基本特征是：每個元素有且僅有一個直接前驅和一個直接后繼。【解答】錯。每個元素最多

29、只有一個直接前驅和一個直接后繼，第一個元素沒有前驅，最后一個元素沒有后繼。 在單鏈表中，要取得某個元素，只要知道該元素所在結點的地址即可，因此單鏈表是隨機存取結構。【解答】錯。要找到該結點的地址，必須從頭指針開始查找，所以單鏈表是順序存取結構。4請說明順序表和單鏈表各有何優缺點，并分析下列情況下，采用何種存儲結構更好些。 若線性表的總長度基本穩定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素。 如果n個線性表同時并存，并且在處理過程中各表的長度會動態發生變化。 描述一個城市的設計和規劃。【解答】順序表的優點： 無需為表示表中元素之間的邏輯關系而增加額外的存儲空間； 可以快速地

30、存取表中任一位置的元素（即隨機存取）。順序表的缺點： 插入和刪除操作需移動大量元素； 表的容量難以確定； 造成存儲空間的“碎片”。單鏈表的優點： 不必事先知道線性表的長度； 插入和刪除元素時只需修改指針，不用移動元素。單鏈表的缺點： 指針的結構性開銷； 存取表中任意元素不方便，只能進行順序存取。 應選用順序存儲結構。因為順序表是隨機存取結構，單鏈表是順序存取結構。本題很少進行插入和刪除操作，所以空間變化不大，且需要快速存取，所以應選用順序存儲結構。 應選用鏈接存儲結構。鏈表容易實現表容量的擴充，適合表的長度動態發生變化。 應選用鏈接存儲結構。因為一個城市的設計和規劃涉及活動很多，需要經常修改、

31、擴充和刪除各種信息，才能適應不斷發展的需要。而順序表的插入、刪除的效率低，故不合適。5算法設計 設計一個時間復雜度為(n)的算法，實現將數組An中所有元素循環左移k個位置。【解答】算法思想請參見主教材第一章思想火花。下面給出具體算法。void Converse(int A , int n, int k) Reverse(A, 0, k-1); Reverse(A, k, n-1); Reverse(A, 0, n-1);void Reverse(int A , int from, int to) /將數組A中元素從from到to逆置 for (i = 0; i (to from + 1)/2;

32、 i+)Afrom + iAto - i; /交換元素 循環左移算法Converse 分析算法，第一次調用Reverse函數的時間復雜度為O(k)，第二次調用Reverse函數的時間復雜度為O(n-k)，第三次調用Reverse函數的時間復雜度為O(n)，所以，總的時間復雜度為O(n)。 已知數組An中的元素為整型，設計算法將其調整為左右兩部分，左邊所有元素為奇數，右邊所有元素為偶數，并要求算法的時間復雜度為(n)。【解答】從數組的兩端向中間比較，設置兩個變量i和j，初始時i=0，j=n-1，若Ai為偶數并且Aj為奇數，則將Ai與Aj交換。具體算法如下： void Adjust(int A ,

33、 n) i = 0; j = n - 1; while (i j) while (Ai % 2 != 0) i+; while (Aj % 2 = 0) j- if (i j) AiAj; 數組奇偶調整算法Adjust 分析算法，兩層循環將數組掃描一遍，所以，時間復雜度為(n)。 試編寫在無頭結點的單鏈表上實現線性表的插入操作的算法，并和帶頭結點的單鏈表上的插入操作的實現進行比較。【解答】參見2.2.3。 試分別以順序表和單鏈表作存儲結構，各寫一實現線性表就地逆置的算法。【解答】順序表的逆置，即是將對稱元素交換，設順序表的長度為length，則將表中第i個元素與第length-i-1個元素相交

34、換。具體算法如下： template void Reverse(T data , int length) for (i = 0; i = length/2; i+) temp = datai; datai = datalength i - 1; datalength i - 1 = temp;順序表逆置算法Reverse單鏈表的逆置請參見2.2.4算法2-4和算法2-6。 假設在長度大于1的循環鏈表中，即無頭結點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前趨結點。【解答】利用單循環鏈表的特點，通過指針s可找到其前驅結點r以及r的前驅結點p，然后將結點r刪除，如圖2-11所

35、示，具體算法如下：template void Del(Node *s) p = s; /工作指針p初始化，查找s的前驅結點的前驅結點，用p指示 while (p-next-next != s) p = p-next; r = p-next; /r為p的前驅結點，q為r的前驅結點 p-next = s; /刪除r所指結點 delete r; 循環鏈表刪除算法Dela1a2an 圖2-11 刪除結點s的前驅結點操作示意圖a3a4spr 已知一單鏈表中的數據元素含有三類字符：字母、數字和其他字符。試編寫算法，構造三個循環鏈表，使每個循環鏈表中只含同一類字符。【解答】在單鏈表A中依次取元素，若取出的元

36、素是字母，把它插入到字母鏈表B 中，若取出的元素是數字，則把它插入到數字鏈表D中，直到鏈表的尾部，這樣表B，D，A中分別存放字母、數字和其他字符。具體算法如下：template void Adjust(Node *A, Node *D, Node *B) D = new Node; D-next = D; /創建空循環鏈表D，存放數字 B = new Node; B-next = B; /創建空循環鏈表B，存放字符 p = A; q = p-next; /工作指針q初始化 while (q != NULL) if (Adata)&(q-data=Z)|(a data)&(q-data=z) p

37、-next = q-next; q-next = B-next; B-next = q; /采用頭插法插在循環鏈表B的頭結點的后面 else if (0data)&(q-data=9) p-next = q-next; q-next = D-next; D-next = q; /采用頭插法插在循環鏈表D的頭結點的后面 else p = q; q = p-next;p-next = A; R = A; /將鏈表A構造為循環鏈表，為除字母和數字的其他字符單鏈表拆分算法Adjust 設單鏈表以非遞減有序排列，設計算法實現在單鏈表中刪去值相同的多余結點。【解答】從頭到尾掃描單鏈表，若當前結點的元素值與

38、后繼結點的元素值不相等，則指針后移；否則刪除該后繼結點。具體算法如下：void Purge(Node *first) p = first-next; while (p-next != NULL) if (p-data = p-next-data) q = p-next; p-next = q-next; delete q; else p = p-next; 單鏈表刪除相同值算法Purge 判斷帶頭結點的雙循環鏈表是否對稱。【解答】設工作指針p和q分別指向循環雙鏈表的開始結點和終端結點，若結點p和結點q的數據域相等，則工作指針p后移，工作指針q前移，直到指針p和指針q指向同一結點（循環雙鏈表中結

39、點個數為奇數），或結點q成為結點p的前驅（循環雙鏈表中結點個數為偶數）。如圖2-12所示。a1an-1anfirstpq圖2-12 判斷循環雙鏈表對稱的操作示意圖template struct DulNode T data; DulNode *prior, *next;template bool Equal (DulNode *first) p = first-next; q = first-prior; while (p != q & p-prior != q) if (p-data = q-data) p = p-next; /工作指針p后移 q = q-prior; /工作指針q前移 e

40、lse return 0; return 1; 判斷雙鏈表對稱算法Equal 第 3 章 棧和隊列3.1 本章導學1. 知識結構圖 本章的知識結構如圖3-1所示，其中第二層的橢圓表示本章的學習主線。特殊線性表 棧隊 列棧的定義操作特性ADT定義隊列定義操作特性ADT定義順序棧鏈棧循環隊列鏈隊列邏輯結構存儲結構邏輯結構存儲結構比 較圖3-1 知識結構圖比較比較基本操作的實現時間性能基本操作的實現時間性能2. 學習要點對于本章的學習要從兩條主線出發，一條主線是棧，另一條主線是隊列，要以棧和隊列的操作特性為切入點，并注意將棧和隊列進行對比。這部分有較多的經典應用，如漢諾塔問題、迷宮問題、八皇后問題、

41、車廂重排問題、開關盒布線、舞伴問題等等。要有意識地接觸這些經典問題，深刻理解棧和隊列在程序設計中的重要作用，在實踐中培養數據結構應用能力和算法設計能力。 3.2 習題解析1. 填空 設有一個空棧，棧頂指針為1000H，每個元素需要1個單位的存儲空間，則執行push、push、pop、push、pop、push、push后，棧頂指針為（ ）。【解答】1003H 棧結構通常采用的兩種存儲結構是（ ）；其判定棧空的條件分別是（ ），判定棧滿的條件分別是（ ）。【解答】順序存儲結構和鏈接存儲結構（或順序棧和鏈棧），棧頂指針top= -1和top=NULL，棧頂指針top等于數組的長度和內存無可用空間（

42、 ）可作為實現遞歸函數調用的一種數據結構。【解答】棧【分析】遞歸函數的調用和返回正好符合后進先出性。 表達式a*(b+c)-d的后綴表達式是（ ）。【解答】abc+*d-【分析】將中綴表達式變為后綴表達式有一個技巧：將操作數依次寫下來，再將算符插在它的兩個操作數的后面。 棧和隊列是兩種特殊的線性表，棧的操作特性是（ ），隊列的操作特性是（ ），棧和隊列的主要區別在于（ ）。【解答】后進先出，先進先出，對插入和刪除操作限定的位置不同 循環隊列的引入是為了克服（ ）。【解答】假溢出 數組Qn用來表示一個循環隊列，front為隊頭元素的前一個位置，rear為隊尾元素的位置，計算隊列中元素個數的公式為

43、（ ）。【解答】（rear-front+n）% n【分析】也可以是（rear-front）% n，但rear-front的結果可能是負整數，而對一個負整數求模，其結果在不同的編譯器環境下可能會有所不同。 用循環鏈表表示的隊列長度為n，若只設頭指針，則出隊和入隊的時間復雜度分別是（ ）和（ ）。【解答】(1)，(n)【分析】在帶頭指針的循環鏈表中，出隊即是刪除開始結點，這只需修改相應指針；入隊即是在終端結點的后面插入一個結點，這需要從頭指針開始查找終端結點的地址。2. 選擇題（1）一個棧的入棧序列是1、2、3、4、5，則棧的不可能的輸出序列是（ ）。A 54321 B 45321 C 43512 D 12345 【解答】C【分析】此題有一個技巧：在輸出序列中任意元素后面不能出現比該元素小并且是升序（指的是元素的序號）的兩個元素。（2）若一個棧的輸入序列是1，2，3，n，輸出序列的第一個元素是n，則第i個輸出元素是（ ）。A 不確定 B n-i C n-i-1 D n-i+1【解答】D【分析】此時，輸出序列一定是輸入序列的逆序。（3）若一個棧的輸入序列是1，2，3，n，其輸出序列是p1, p2, , pn，若p1=3，則p2的值（ ）。A 一定是2 B 一定是1 C 不可能是1 D 以上都不對【解答】C【分析】由于p1=