1、數(shù)據(jù)結(jié)構(gòu)設(shè)計與技巧數(shù)據(jù)結(jié)構(gòu)設(shè)計與技巧講義【考查目標(biāo)】1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。2.掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。3.能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。一、線性表（一）線性表的定義和基本操作（二）線性表的實現(xiàn)1.順序存儲結(jié)構(gòu)2.鏈?zhǔn)酱鎯Y(jié)構(gòu)3.線性表的應(yīng)用二、棧、隊列和數(shù)組（一）棧和隊列的基本概念（二）棧和隊列的順序存儲結(jié)構(gòu)（三）棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)（四）棧和隊列的應(yīng)用（五）特殊矩陣的壓縮存儲三、樹與二叉樹（一）樹的概念（二）二叉樹1.二叉樹的定義及其主要特征2.二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)?/p>

2、存儲結(jié)構(gòu)3.二叉樹的遍歷4.線索二叉樹的基本概念和構(gòu)造5.二叉排序樹6.平衡二叉樹（三）樹、森林1.書的存儲結(jié)構(gòu)2.森林與二叉樹的轉(zhuǎn)換3.樹和森林的遍歷（四）樹的應(yīng)用1.等價類問題2.哈夫曼（Huffman）樹和哈夫曼編碼四、 圖（一） 圖的概念（二） 圖的存儲及基本操作1. 鄰接矩陣法2. 鄰接表法（三） 圖的遍歷1. 深度優(yōu)先搜索2. 廣度優(yōu)先搜索（四） 圖的基本應(yīng)用及其復(fù)雜度分析1. 最小（代價）生成樹2. 最短路徑3. 拓?fù)渑判?. 關(guān)鍵路徑五、 查找（一） 查找的基本概念（二） 順序查找法（三） 折半查找法（四） B-樹（五） 散列（Hash）表及其查找（六） 查找算法的分析及應(yīng)用六

3、、 內(nèi)部排序（一） 排序的基本概念（二） 插入排序1. 直接插入排序2. 折半插入排序（三） 氣泡排序（bubble sort）（四） 簡單選擇排序（五） 希爾排序（shell sort）（六） 快速排序（七） 堆排序（八） 二路歸并排序（merge sort）（九） 基數(shù)排序（十） 各種內(nèi)部排序算法的比較（十一） 內(nèi)部排序算法的應(yīng)用【知識點解析】 1.線性表 線性表是一種最簡單的數(shù)據(jù)結(jié)構(gòu)，在線性表方面，主要考查線性表的定義和基本操作、線性表的實現(xiàn)。在線性表實現(xiàn)方面，要掌握的是線性表的存儲結(jié)構(gòu)，包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，特別是鏈?zhǔn)酱鎯Y(jié)構(gòu)，是考查的重點。另外，還要掌握線性表的基本應(yīng)用。

4、2.棧、隊列和數(shù)組 棧和隊列是兩種特殊的線性表，在這方面，要求我們掌握棧和隊列的基本概念，以及他們之間的區(qū)別。對于棧和隊列的存儲結(jié)構(gòu)(包括順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu))要有較深的理解，對于棧和隊列的應(yīng)用，例如，排隊問題、子程序調(diào)用問題、表達式問題等，要搞清楚。 一維數(shù)組屬于線性表范疇，但多維數(shù)組不屬于線性表。在這方面，主要掌握數(shù)組的存儲結(jié)構(gòu)，例如按行優(yōu)先、按列優(yōu)先等，某個元素存在的地址是什么。對于特殊矩陣(二維數(shù)組)的壓縮存儲原理也要搞清楚。 3、樹與二叉樹 二叉樹和樹是兩種不同的概念，這一點是必須要搞清楚的。在這個部分，我們要掌握樹的定義、二叉樹的定義及主要特征(特殊的二叉樹、二叉樹的性質(zhì))。

5、在二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)方面，特別是鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為很多應(yīng)用都是建立在鏈?zhǔn)酱鎯A(chǔ)上，例如，二叉樹的遍歷(前序遍歷、中序遍歷、后序遍歷)就是一種典型的應(yīng)用。 在特殊的二叉樹中，完全二叉樹的概念是必須要搞清楚的，其次，線索二叉樹的基本概念和構(gòu)造、二叉排序樹、平衡二叉樹的基本概念和應(yīng)用，特別是二叉排序樹的基本性質(zhì)和特點要能很好地理解。 多棵獨立的樹就組成了森林，樹的存儲結(jié)構(gòu)和遍歷、森林的遍歷、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換等知識，也要有了了解。 最后就是樹的應(yīng)用，通常會作為綜合應(yīng)用類試題出現(xiàn)，包括等價類問題、哈夫曼(Huffman)樹和哈夫曼編碼等。 4、圖 在數(shù)據(jù)結(jié)構(gòu)中，圖的

6、結(jié)構(gòu)是最復(fù)雜的，這里的概念也是最多的。我們要掌握圖的基本概念(有向圖、無向圖、連通、路徑、子圖、出度、入度、生成樹、最短路徑、關(guān)鍵路徑等)。 圖的存儲及基本操作主要有鄰接矩陣法和鄰接表法，我們要掌握這有向圖和無向圖的這2種存儲方法，要清楚圖的連通和存儲方法之間的關(guān)系。例如，一個頂點的出度和臨界矩陣中1的個數(shù)有什么關(guān)系，等等。 圖的遍歷方法有深度優(yōu)先搜索和廣度優(yōu)先搜索，我們要掌握這2種遍歷方法的算法實現(xiàn)。給出一個具體的圖，要能知道它的遍歷次序。 在數(shù)據(jù)結(jié)構(gòu)課程中，圖的基本應(yīng)用是最多的，也是最復(fù)雜的，我們要掌握這些應(yīng)用的復(fù)雜度分析。要掌握的具體應(yīng)用主要包括最小(代價)生成樹、最短路徑、拓?fù)渑判颉㈥P(guān)

7、鍵路徑。在給出的一個具體的圖中，我們要會利用已知條件，求出上述應(yīng)用的結(jié)果。 5、查找 在給定的數(shù)據(jù)集合中查找某個關(guān)鍵值就是查找，查找的基本方法主要有順序查找法、折半查找法、B-樹、散列(Hash)表及其查找。考的比較多的是折半查找和散列表，我們要掌握它們的基本概念和方法，例如散列表的碰撞如何解決，裝載因子的概念等。 另外，我們要掌握各種查找算法的分析及應(yīng)用，最好能把各種查找在查找成功、查找失敗的情況下的最好、平均、最壞的平均查找次數(shù)的計算方法搞清楚。 6、內(nèi)部排序 根據(jù)考試大綱，只考查內(nèi)部排序。所謂內(nèi)部排序，就是在內(nèi)存中進行排序。在這一部分中，主要要掌握直接插入排序、折半插入排序、冒泡排序(b

8、ubble sort)、簡單選擇排序、希爾排序(shell sort)、快速排序、堆排序、二路歸并排序(merge sort)、基數(shù)排序的基本概念和方法。搞清楚這些排序方法的流程，以及它們之間的區(qū)別。 在這個知識點，一個很重要的考查點就是各種內(nèi)部排序算法的比較，一般的書上都會有這樣的一個表格，列出了所有排序在各種情況下(最好、最壞、平均)的時間復(fù)雜度和空間復(fù)雜度，這個表是需要我們記下來的。當(dāng)然，如果我們能掌握復(fù)雜度的計算方法，自己能推算出來，那就更好了。 最后，就是要掌握內(nèi)部排序算法的基本應(yīng)用，以及算法的實現(xiàn)。 【復(fù)習(xí)方法】 1、教材的選擇 從考試大綱來看，所要求的知識在一般的大學(xué)數(shù)據(jù)結(jié)構(gòu)教材

9、中都已經(jīng)包含，所以，選擇哪本書并不是最重要的事情。不過，根據(jù)希賽教育推薦，對于數(shù)據(jù)結(jié)構(gòu)的復(fù)習(xí)，可以選擇清華大學(xué)出版社的數(shù)據(jù)結(jié)構(gòu)(第二版)(嚴(yán)蔚敏主編)。這本書有多種語言的版本，建議選擇C語言的版本，在復(fù)習(xí)的過程中，還可以配以相應(yīng)的習(xí)題集。 2、學(xué)習(xí)方法 對于數(shù)據(jù)結(jié)構(gòu)的學(xué)習(xí)，難在其中的算法及實現(xiàn)。有條件的考生，可以在計算機上編寫程序，自己實現(xiàn)教材上的算法(要注意，書上的算法通常都采用偽代碼編寫，需要我們自己用某種程序設(shè)計語言去具體實現(xiàn))。如果沒有條件，那就只有在心里進行推導(dǎo)了，可以使用實際的例子，手工“實現(xiàn)”算法。數(shù)據(jù)結(jié)構(gòu)【考查目標(biāo)】 1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及

10、其差異，以及各種基本操作的實現(xiàn)。 2. 掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM行設(shè)計與分析。 3. 能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。 一、線性表大綱要求：（一） 線性表的定義和基本操作 （二） 線性表的實現(xiàn) 1. 順序存儲結(jié)構(gòu) 2. 鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 線性表的應(yīng)用 知識點：1 深刻理解數(shù)據(jù)結(jié)構(gòu)的概念，掌握數(shù)據(jù)結(jié)構(gòu)的“三要素”：邏輯結(jié)構(gòu)、物理（存儲）結(jié)構(gòu)及在這種結(jié)構(gòu)上所定義的操作“運算”。2 時間復(fù)雜度和空間復(fù)雜度的定義，常用計算語句頻度來估算算法的時間復(fù)雜度。以下六種計算算法時間的多項式是最常用的。其關(guān)系為：O(1)<O(logn)<O(n)<O(nl

11、ogn) <O(n2)<O(n3)指數(shù)時間的關(guān)系為： O(2n)<O(n!)<O(nn)3 線性表的邏輯結(jié)構(gòu)，是指線性表的數(shù)據(jù)元素間存在著線性關(guān)系。主要是指：除第一及最后一個元素外，每個結(jié)點都只有一個前趨和只有一個后繼。在順序存儲結(jié)構(gòu)中，元素存儲的先后位置反映出這種邏輯關(guān)系，而在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，是靠指針來反映這種邏輯關(guān)系的。4 順序存儲結(jié)構(gòu)用向量（一維數(shù)組）表示，給定下標(biāo)，可以存取相應(yīng)元素，屬于隨機存取的存儲結(jié)構(gòu)。5 線性表的順序存儲方式及其在具體語言環(huán)境下的兩種不同實現(xiàn)：表空間的靜態(tài)分配和動態(tài)分配。掌握順序表上實現(xiàn)插入、刪除、定位等運算的算法。6 盡管“只要知道某結(jié)點

12、的指針就可以存取該元素”，但因鏈表的存取都需要從頭指針開始，順鏈而行，故鏈表不屬于隨機存取結(jié)構(gòu)。要理解頭指針、頭結(jié)點、首元結(jié)點和元素結(jié)點的差別。頭結(jié)點是在插入、刪除等操作時，為了算法的統(tǒng)一而設(shè)立的（若無頭結(jié)點，則在第一元素前插入元素或刪除第一元素時，鏈表的頭指針總在變化）。對鏈表（不包括循環(huán)鏈表）的任何操作，均要從頭結(jié)點開始，頭結(jié)點的指針具有標(biāo)記作用，故頭指針往往被稱為鏈表的名字，如鏈表head是指鏈表頭結(jié)點的指針是head。理解循環(huán)鏈表中設(shè)置尾指針而不設(shè)置頭指針的好處。鏈表操作中應(yīng)注意不要使鏈意外“斷開”。因此，若在某結(jié)點前插入一個元素或刪除某元素，必須知道該元素的前驅(qū)結(jié)點的指針。7 鏈表是

13、本部分學(xué)習(xí)的重點和難點。重點掌握以下幾種常用鏈表的特點和運算：單鏈表、循環(huán)鏈表、雙向鏈表、雙向循環(huán)鏈表的生成、插入、刪除、遍歷以及鏈表的分解和歸并等操作。并能夠設(shè)計出實現(xiàn)線性表其它運算的算法。8 從時間復(fù)雜度和空間復(fù)雜度的角度綜合比較線性表在順序和鏈?zhǔn)絻煞N存儲結(jié)構(gòu)下的特點，即其各自適用的場合。小結(jié)：順序表和鏈表的比較通過對它們的討論可知它們各有優(yōu)缺點，順序存儲有三個優(yōu)點：（1）方法簡單，各種高級語言中都有數(shù)組，容易實現(xiàn)。（2）不用為表示結(jié)點間的邏輯關(guān)系而增加額外的存儲開銷。（3）順序表具有按元素序號隨機訪問的特點。 但它也有兩個缺點：（1）在順序表中做插入刪除操作時，平均移動大約表中一半的元素

14、，因此對n較大的順序表效率低。（2）需要預(yù)先分配足夠大的存儲空間，估計過大，可能會導(dǎo)致順序表后部大量閑置；預(yù)先分配過小，又會造成溢出。鏈表的優(yōu)缺點恰好與順序表相反。在實際中怎樣選取存儲結(jié)構(gòu)呢？（1）基于存儲的考慮對線性表的長度或存儲規(guī)模難以估計時，不宜采用順序表；鏈表不用事先估計存儲規(guī)模，但鏈表的存儲密度較低，顯然鏈?zhǔn)酱鎯Y(jié)構(gòu)的存儲密度是小于的。（2）基于運算的考慮在順序表中按序號訪問ai的時間性能時O(1)，而鏈表中按序號訪問的時間性能O(n)，所以如果經(jīng)常做的運算是按序號訪問數(shù)據(jù)元素，顯然順序表優(yōu)于鏈表；而在順序表中做插入、刪除時平均移動表中一半的元素，當(dāng)數(shù)據(jù)元素的信息量較大且表較長時，這

15、一點是不應(yīng)忽視的；在鏈表中作插入、刪除，雖然也要找插入位置，但操作主要是比較操作，從這個角度考慮顯然后者優(yōu)于前者。（3）基于環(huán)境的考慮 順序表容易實現(xiàn)，任何高級語言中都有數(shù)組類型，鏈表的操作是基于指針的，相對來講前者簡單些，也是用戶考慮的一個因素。總之，兩種存儲結(jié)構(gòu)各有長短，選擇那一種由實際問題中的主要因素決定。通常“較穩(wěn)定”的線性表選擇順序存儲，而頻繁做插入刪除的即動態(tài)性較強的線性表宜選擇鏈?zhǔn)酱鎯Α＞毩?xí)題：（一）選擇題：1以下那一個術(shù)語與數(shù)據(jù)的存儲結(jié)構(gòu)無關(guān)？（ A ）A隊列 B. 哈希表 C. 線索樹 D. 雙向鏈表2、一個算法應(yīng)該是（ B ）。A程序 B問題求解步驟的描述 C要滿足五個基本

16、特性 DA和C.3、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的（ C ）A存儲結(jié)構(gòu) B物理結(jié)構(gòu) C邏輯結(jié)構(gòu) D物理結(jié)構(gòu)和存儲結(jié)構(gòu)4. 算法的計算量的大小稱為計算的（ B ）。A效率 B復(fù)雜性 C現(xiàn)實性 D難度5下列說法，不正確的是（D）。A數(shù)據(jù)元素是數(shù)據(jù)的基本單位B數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標(biāo)識單位C數(shù)據(jù)可由若干個數(shù)據(jù)元素構(gòu)成D數(shù)據(jù)項可由若干個數(shù)據(jù)元素構(gòu)成6連續(xù)存儲設(shè)計時，存儲單元的地址（ A ）。A一定連續(xù) B一定不連續(xù) C不一定連續(xù) D部分連續(xù)，部分不連續(xù)7. 線性表（ a1,a2,an）以鏈接方式存儲時，訪問第i位置元素的時間復(fù)雜性為（ C ）。AO（i） BO（1） CO（n） D

17、O（i-1）8. 對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復(fù)雜度為（ C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)9. 設(shè)單鏈表中結(jié)點的結(jié)構(gòu)為（data，link）。已知指針q所指點是指針p所指結(jié)點的直接前驅(qū)，若在*q與*p之間插入結(jié)點*s，則應(yīng)執(zhí)行下列哪一個操作？（ B ）。As>link=p>link；p>link=sBq>link=s；s>link=pCp>link=s>link；s>link=pDp>link=s；s>link=q10. 在一個長度為n的

18、順序表的表尾插入一個新元素的漸進時間復(fù)雜度為（ B ）。AO（n） BO（1） CO（n2） DO（log2n）11. 表長為n的順序存儲的線性表，當(dāng)在任何位置上插入一個元素的概率相等時，插入一個元素所需移動元素的平均個數(shù)為（ B ）An B. n/2C. (n-1)/2 D. (n+1)/212. 循環(huán)鏈表的主要優(yōu)點是（ D ）A不再需要頭指針了。B已知某個結(jié)點的位置后，能很容易找到它的直接前驅(qū)結(jié)點。C在進行刪除操作后，能保證鏈表不斷開。D從表中任一結(jié)點出發(fā)都能遍歷整個鏈表。（二）應(yīng)用題1、按增長率由小至大排列以下7個函數(shù)。答：2、數(shù)據(jù)的存儲結(jié)構(gòu)由哪四種基本的存儲方法實現(xiàn)，并做以簡要說明？答

19、：四種表示方法（1）順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯Ψ绞健Ｃ總€存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置（下標(biāo)）或存儲區(qū)間端點（下標(biāo)），兼有靜態(tài)和動態(tài)特性。（4）散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)

20、鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。3. 線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：（1）如果有 n個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？ 為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？ （1）選鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪除時間復(fù)雜

21、度為O（1）。（2）選順序存儲結(jié)構(gòu)。順序表可以隨機存取，時間復(fù)雜度為O（1）。（三）算法設(shè)計題1設(shè)計算法，求帶表頭的單循環(huán)鏈表的表長。解：int length(Linklist L) int I; listnode *p; I=0; P=L; while (p->next!=L) p=p->next; I+; return I;2.已知單鏈表L，寫一算法，刪除其重復(fù)結(jié)點。算法思路：用指針p指向第一個數(shù)據(jù)結(jié)點，從它的后繼結(jié)點開始到表的結(jié)束，找與其值相同的結(jié)點并刪除之；p指向下一個；依此類推，p指向最后結(jié)點時算法結(jié)束。算法如下：解：void pur_LinkList(LinkList

22、H) LNode *p,*q,*r; p=H->next; /*p指向第一個結(jié)點*/ if(p=NULL) return; while (p->next) q=p; while (q->next) /* 從*p的后繼開始找重復(fù)結(jié)點*/ if (q->next->data=p->data) r=q->next; /*找到重復(fù)結(jié)點，用r指向，刪除*r */ q->next=r->next; free(r); /*if*/ else q=q->next; /*while(q->next)*/ p=p->next; /*p指向下一

23、個，繼續(xù)*/ /*while(p->next)*/該算法的時間性能為O(n2)。3.已知指針la和lb分別指向兩個無頭結(jié)點的單鏈表中的首結(jié)點。請編寫函數(shù)完成從表la中刪除自第i個元素開始的共len個元素并將它們插入到表lb中第j個元素之前，若lb中只有j-1個元素，則插在表尾。函數(shù)原型如下：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,int len)；答：int DeleteAndInsertSub(LinkList &la,LinkList &lb,int i,int j,in

24、t len)int k; LinkList p,q,prev,s;if(i<0|j<0|len<0)return -1;p=la;k=1;prev=NULL;while(p&&k<i)prev=p;p=p->next;k+;if(!p)return -1;q=p;k=1;while(q&&k<len)q=q->next;k+;if(!q)return -1;if(!prev)la=q->next;elseprev->next=q->next;if(j=1)q->next=lb;lb=q;elses

25、=lb;k=1;while(s&&k<j-1)s=s->next;k+;if(!s)return -1;q->next=s->next;s->next=p;return 1;4寫一算法，將一帶有頭結(jié)點的單鏈表就地逆置，即要求逆置在原鏈表上進行，不允許重新構(gòu)造新鏈表。圖 單鏈表的倒置254525187629L297625184525L(a)(b)函數(shù)原型如下：void LinkList_reverse(LinkList &L)；答：void LinkList_reverse(LinkList &L)LinkList p,q,s;p=L

26、->next;q=p->next;s=q->next;p->next=NULL;while(s->next)q->next=p;p=q;q=s;s=s->next;q->next=p;s->next=q;L->next=s;5寫一算法，將帶有頭結(jié)點的非空單鏈表中數(shù)據(jù)域值最小的那個結(jié)點移到鏈表的最前面。要求：不得額外申請新的鏈結(jié)點。函數(shù)原型如下：void delinsert(LinkList &L)；答：void delinsert(LinkList &L)p=L->next;/p是鏈表的工作指針pre=L;/pr

27、e指向鏈表中數(shù)據(jù)域最小值結(jié)點的前驅(qū)q=p;/q指向數(shù)據(jù)域最小值結(jié)點，初始假定是第一結(jié)點while(p->next!=NULL)if(p->next->data<q->data)/找到新的最小值結(jié)點pre=p;q=p->next; p=p->next;if(q!=L->next)/若最小值是第一元素結(jié)點，則不需再操作pre->next=q->next;/將最小值結(jié)點從鏈表上摘下q->next=L->next;/將q結(jié)點插到鏈表最前面L->next=q;6編寫一個算法來交換單鏈表中指針P所指結(jié)點與其后繼結(jié)點，HEAD是該

28、鏈表的頭指針，P指向該鏈表中某一結(jié)點。答：單鏈表中查找任何結(jié)點，都必須從頭指針開始。本題要求將指針p所指結(jié)點與其后繼結(jié)點交換，這不僅要求知道p結(jié)點，還應(yīng)知道p的前驅(qū)結(jié)點。這樣才能在p與其后繼結(jié)點交換后，由原p結(jié)點的前驅(qū)來指向原p結(jié)點的后繼結(jié)點。LinkedList Exchange（LinkedList HEAD，p） HEAD是單鏈表頭結(jié)點的指針，p是鏈表中的一個結(jié)點。本算法將p所指結(jié)點與其后繼結(jié)點交換。q=head->next； q是工作指針，指向鏈表中當(dāng)前待處理結(jié)點。pre=head； pre是前驅(qū)結(jié)點指針，指向q的前驅(qū)。while（q!=null && q!=p）

29、pre=q；q=q->next； 未找到p結(jié)點，后移指針。if（p->next=null）printf（“p無后繼結(jié)點n”）; p是鏈表中最后一個結(jié)點，無后繼。Else 處理p和后繼結(jié)點交換 q=p->next； 暫存p的后繼。 pre->next=q； p前驅(qū)結(jié)點的后繼指向p的后繼。 p->next=q->next；p的后繼指向原p后繼的后繼。 q->next=p ；原p后繼的后繼指針指向p。 算法結(jié)束。7已知線性鏈表第一個鏈結(jié)點指針為list，請寫一算法，將該鏈表分解為兩個帶有頭結(jié)點的循環(huán)鏈表，并將兩個循環(huán)鏈表的長度分別存放在各自頭結(jié)點的數(shù)據(jù)域中。

30、其中,線性表中序號為偶數(shù)的元素分解到第一個循環(huán)鏈表中,序號為奇數(shù)的元素分解到第二個循環(huán)鏈表中。答：算法如下：void split(ListNode *List, ListNode *&list1, ListNode *&list2)list1=(ListNode *)malloc(sizeof(ListNode )；list2=(ListNode *)malloc(sizeof(ListNode )；p=list;；q=list1；r=list2；len1=0；len2=0；mark=1；while (p!=null)if(mark=1)q->next=p;q=q->

31、;next;len1+;mark=2;elser->next=p;r=r->next;len2+;mark=1;list1->data=len1;list2->data=len2;q->next=list1;r->next=list2;8. 設(shè)A和B是兩個單鏈表，其表中元素遞增有序。試寫一算法將A和B歸并成一個按元素值遞減有序的單鏈表C，并要求輔助空間為O(1)。答：Linklist merge(Linklist A,Linklist B)Linklist C;Listnode *p;C=null;while (A&&B) if(A->

32、data<=B->data) p=A->next;A->next=C;C=A;A=p; else p=B->next;B->next=C;C=B;B=p; if (A)while(A) p=A->next;A->next=C;C=A;A=p; else while(B) p=B->next;B->next=C;C=B;B=p;return C;二、棧、隊列和數(shù)組大綱要求：（一） 棧和隊列的基本概念 （二） 棧和隊列的順序存儲結(jié)構(gòu) （三） 棧和隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) （四） 棧和隊列的應(yīng)用 （五） 特殊矩陣的壓縮存儲 知識點：1 棧、隊列的

33、定義及其相關(guān)數(shù)據(jù)結(jié)構(gòu)的概念，包括：順序棧、鏈棧、循環(huán)隊列、鏈隊列等。棧與隊列存取數(shù)據(jù)（請注意包括：存和取兩部分）的特點。2 掌握順序棧和鏈棧上的進棧和退棧的算法，并弄清棧空和棧滿的條件。注意因棧在一端操作，故通常鏈棧不設(shè)頭結(jié)點。3 如何將中綴表達式轉(zhuǎn)換成前綴、后綴表達式，了解對兩種表達式求值的方法。4 棧與遞歸的關(guān)系。用遞歸解決的幾類問題：問題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問題的解法是遞歸的。掌握典型問題的算法以及將遞歸算法轉(zhuǎn)換為非遞歸算法，如n!階乘問題，fib數(shù)列問題，hanoi問題。了解在數(shù)值表達式的求解、括號的配對等問題中應(yīng)用棧的工作原理。5 掌握在鏈隊列上實現(xiàn)入隊和出隊的算法

34、。注意對僅剩一個元素的鏈隊列刪除元素時的處理（令隊尾指針指向隊頭）。還需特別注意僅設(shè)尾指針的循環(huán)鏈隊列的各種操作的實現(xiàn)。6 循環(huán)隊列隊空及隊滿的條件。隊空定義為隊頭指針等于隊尾指針，隊滿則可用犧牲一個單元或是設(shè)標(biāo)記的方法，這里特別注意取模運算。掌握循環(huán)隊列中入隊與出隊算法。7 在后續(xù)章節(jié)中多處有棧和隊列的應(yīng)用，如二叉樹遍歷的遞歸和非遞歸算法、圖的深度優(yōu)先遍歷等都用到棧，而樹的層次遍歷、圖的廣度優(yōu)先遍歷等則用到隊列。這些方面的應(yīng)用應(yīng)重點掌握。8 數(shù)組在機器（內(nèi)存）級上采用順序存儲結(jié)構(gòu)。掌握數(shù)組（主要是二維）在以行序為主和列序為主的存儲中的地址計算方法。9 特殊矩陣（對稱矩陣、對角矩陣、三角矩陣）

35、在壓縮存儲是的下標(biāo)變換公式。練習(xí)題：（一）選擇題：1. 一個棧的輸入序列為1 2 3 4，則（D）不可能是其出棧序列。A. 1 2 4 3B. 2 1 3 4C. 1 4 3 2D. 4 3 1 22. 一個遞歸算法必須包括（ B ）。A. 遞歸部分 B. 終止條件和遞歸部分 C. 迭代部分 D.終止條件和迭代部分3. 一個遞歸的定義可以用遞歸過程求解，也可以用非遞歸過程求解，但單從運行時間來看，通常遞歸過程比非遞歸過程（B）。 A較快 B較慢 C相同 D以上答案都不對4. 棧和隊列都是（C）A順序存儲的線性表 B鏈?zhǔn)酱鎯Φ木€性表C限制存儲的線性表 D限制存儲的非線性結(jié)構(gòu)5. 二維數(shù)組N的元素

36、是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，N按行存儲時元素N35的起始地址與N按列存儲時元素（B）的起始地址相同。A. N24 B. N34C. N35 D. N446. 設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)以列為主序存放時，元素A5,8的存儲首地址是（B）A. BA+141 B. BA+180C. BA+222 D. BA+2257. 遞歸過程或函數(shù)調(diào)用時，處理參數(shù)及返回地址，要用一種稱為（ C ）的數(shù)據(jù)結(jié)構(gòu)。A隊列 B多維數(shù)組 C棧 D. 線性表 8. 對于單

37、鏈表形式的隊列，隊空的條件是（ A ）AFRnil BFRCFnil且Rnil DRF19. 若循環(huán)隊列以數(shù)組Q0.m-1作為其存儲結(jié)構(gòu)，變量rear表示循環(huán)隊列中的隊尾元素的實際位置，其移動按 rear=(rear+1) Mod m 進行，變量length表示當(dāng)前循環(huán)隊列中的元素個數(shù)，則循環(huán)隊列的隊首元素的實際位置是（ C ）Arear-lengthB(rear-length+m) Mod mC(1+rear+m-length) Mod mDM-length（二）應(yīng)用題1、（10分）假設(shè)一個準(zhǔn)對角矩陣按以下方式存儲于一維數(shù)組B4m中：01234k4m24m1.寫出由一對下標(biāo)（i，j）表示的k

38、的轉(zhuǎn)換公式。答：i為奇數(shù)時 k=i+j-2i為偶數(shù)時 k=i+j-1合并后可寫成 k=i+j-(i%2)-1 或 k=2(i/2)+j-12、特殊矩陣和稀疏矩陣哪一種壓縮存儲后失去隨機存取的功能？為什么？答：特殊矩陣指值相同的元素或零元素在矩陣中的分布有一定規(guī)律，因此可以對非零元素分配單元（對值相同元素只分配一個單元），將非零元素存儲在向量中，元素的下標(biāo)i和j和該元素在向量中的下標(biāo)有一定規(guī)律，可以用簡單公式表示，仍具有隨機存取功能。而稀疏矩陣是指非零元素和矩陣容量相比很小（t<<m*n），且分布沒有規(guī)律。用十字鏈表作存儲結(jié)構(gòu)自然失去了隨機存取的功能。即使用三元組表的順序存儲結(jié)構(gòu)，存

39、取下標(biāo)為i和j的元素時，要掃描三元組表，下標(biāo)不同的元素，存取時間也不同，最好情況下存取時間為O(1)，最差情況下是O(n)，因此也失去了隨機存取的功能。3、有人說，采用循環(huán)鏈表作為存儲結(jié)構(gòu)的隊列就是循環(huán)隊列，你認(rèn)為這種說法對嗎？說明你的理由。答：這種說法是錯誤的。隊列（包括循環(huán)隊列）是一個邏輯概念，而鏈表是一個存儲概念，一個隊列是否是循環(huán)隊列。不取決于它將采用何種存儲結(jié)構(gòu)。根據(jù)實際的需要，循環(huán)隊列可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，包括采用循環(huán)鏈表作為存儲結(jié)構(gòu)。4、指出下列程序段的功能是什么？ (1) void demo1(seqstack *s) int I;arr64;n=0;

40、while (!stackempty(s) arrn+=pop(s); for(I=0;<n;I+) push(s,arrI); (2) void demo2(seqstack *s,int m) seqstack t; int i; initstack(t);while(! Stackempty(s) if(I=pop(s)!=m) push(t,I);while(! Stackempty(t) i=pop(t); push(s,I);（三）算法設(shè)計題1 試?yán)醚h(huán)隊列編寫求k階斐波那契序列中前n+1項（）的算法，要求滿足且，其中max為某個約定的常數(shù)。循環(huán)隊列的容量為k，因此，在算法

41、執(zhí)行結(jié)束時，留在循環(huán)隊列中的元素應(yīng)是所求k階斐波那契序列中的最后k項。答：void GetFib(int k,int n)InitQueue(Q);for(i=0;k<k-1;i+)Q.basei=0;Q.basek-1=1;for(i=0;i<k;i+)printf(“%d”,Q.basei);for(i=k;i<=n;i+)m=i%k;sum=0;for(j=0;j<k;j+)sum+=Q.base(m+j)%k;Q.basem=sum;printf(“%d”,sum);2. 已知num為無符號十進制整數(shù)，請寫一非遞歸算法，該算法輸出num對應(yīng)的r進制的各位數(shù)字。要

42、求算法中用到的棧采用線性鏈表存儲結(jié)構(gòu)（1<r<10）。 解：typedef struct nodeint data;struct node *next;link;void trans(int num,int r) link *head=NULL,*s; int n; while (num>0) n=num%r; s=(link *)malloc(sizeof(link); s->data=n; s->next=head;head=s; num=num/r; printf(“輸出r進制的各位數(shù)字：”)； s=head; while (s!=NULL) printf(

43、“%d”,s->data); s=s->next; 三、樹與二叉樹大綱要求：（一） 樹的概念 （二） 二叉樹 1. 二叉樹的定義及其主要特征 2. 二叉樹的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu) 3. 二叉樹的遍歷 4. 線索二叉樹的基本概念和構(gòu)造 5. 二叉排序樹 6. 平衡二叉樹 （三） 樹、森林 1. 樹的存儲結(jié)構(gòu) 2. 森林與二叉樹的轉(zhuǎn)換 3. 樹和森林的遍歷 （四） 樹的應(yīng)用 1. 等價類問題 2. 哈夫曼（Huffman）樹和哈夫曼編碼 知識點：1. 二叉樹的概念、性質(zhì)（1）掌握樹和二叉樹的定義。（2）理解二叉樹與普通雙分支樹的區(qū)別。二叉樹是一種特殊的樹，這種特殊不僅僅在于其分支最

44、多為2以及其它特征，一個最重要的特殊之處是在于：二叉樹是有序的。即二叉樹的左右孩子是不可交換的，如果交換了就成了另外一棵二叉樹，這樣交換之后的二叉樹與原二叉樹是不相同的兩棵二叉樹。但是，對于普通的雙分支樹而言，不具有這種性質(zhì)。（3）滿二叉樹和完全二叉樹的概念。（4）重點掌握二叉樹的五個性質(zhì)及證明方法，并把這種方法推廣到K叉樹。普通二叉樹的五個性質(zhì)：第i層的最多結(jié)點數(shù)，深度為k的二叉樹的最多結(jié)點數(shù)，n0=n2+1的性質(zhì)，n個結(jié)點的完全二叉樹的深度，順序存儲二叉樹時孩子結(jié)點與父結(jié)點之間的換算關(guān)系（序號i結(jié)點的左孩子為：2*i，右孩子為：2*i+1）。2. 掌握二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表、三叉鏈

45、表存儲結(jié)構(gòu)的各自優(yōu)缺點及適用場合，以及二叉樹的順序存儲結(jié)構(gòu)和二叉鏈表存儲結(jié)構(gòu)的相互轉(zhuǎn)換的算法。3. 熟練掌握二叉樹的先序，中序和后序遍歷算法以及按層次遍歷二叉樹的先序、中序和后序三種遍歷算法，劃分的依據(jù)是視其每個算法中對根結(jié)點數(shù)據(jù)的訪問順序而定。不僅要熟練掌握這三種遍歷的遞歸算法，理解其執(zhí)行的實際步驟，并且應(yīng)該熟練掌握三種遍歷的非遞歸算法。按層次遍歷二叉樹void LayerOrder(Bitree T)/層序遍歷二叉樹  InitQueue(Q); /建立工作隊列  EnQueue(Q,T);  while(!QueueEmpty(

46、Q)  DeQueue(Q,p);visit(p);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) EnQueue(Q,p->rchild); /LayerOrder 4. 遍歷是基礎(chǔ)，重點掌握在三種基本遍歷算法的基礎(chǔ)上實現(xiàn)二叉樹的其它算法如求二叉樹葉子結(jié)點總數(shù)，求二叉樹結(jié)點總數(shù)，求度為1或度為2的結(jié)點總數(shù)，復(fù)制二叉樹，建立二叉樹，交換左右子樹，查找值為n的某個指定結(jié)點，刪除值為n的某個指定結(jié)點等等。5. 線索二叉樹的引出，是為避免如二叉樹遍歷時的遞歸求解。遞歸雖然形式上比較好理解，但是消耗

47、了大量的內(nèi)存資源，如果遞歸層次一多，勢必帶來資源耗盡的危險。二叉樹線索化的實質(zhì)是建立結(jié)點在相應(yīng)序列中與其前驅(qū)和后繼之間的直接聯(lián)系。對于線索二叉樹，應(yīng)該掌握：線索化的實質(zhì)，三種線索化的算法，線索化后二叉樹的遍歷算法，基本線索二叉樹的其它算法問題（如：查找某一類線索二叉樹中指定結(jié)點的前驅(qū)或后繼結(jié)點）。6. 二叉排序樹的中序遍歷結(jié)果是一個遞增的有序序列。二叉排序樹的形態(tài)取決于元素的輸入順序，二叉排序樹在最差情況下形成單支樹。熟練掌握其建立、查找、插入和刪除算法，以及判斷某棵二叉樹是否二叉排序樹這一問題的遞歸與非遞歸算法。7. 平衡二叉樹是二叉排序樹的優(yōu)化，平衡二叉樹對左右子樹的深度有了限定：深度之差

48、的絕對值不得大于1。掌握平衡二叉樹的四種調(diào)整算法。8. 樹與森林的遍歷，只有兩種遍歷算法：先根與后根（對于森林而言稱作：先序與中序遍歷）。二者的先根與后根遍歷與二叉樹中的遍歷算法是有對應(yīng)關(guān)系的：先根遍歷對應(yīng)二叉樹的先序遍歷，而后根遍歷對應(yīng)二叉樹的中序遍歷。二叉樹使用二叉鏈表分別存放它的左右孩子，樹利用二叉鏈表存儲孩子及兄弟（稱孩子兄弟鏈表），而森林也是利用二叉鏈表存儲孩子及兄弟。掌握樹、森林和二叉樹間的相互轉(zhuǎn)換。9. 簡單掌握等價類的生成算法。10. 哈夫曼樹為了解決特定問題引出的特殊二叉樹結(jié)構(gòu)，它的前提是給二叉樹的每條邊賦予了權(quán)值，這樣形成的二叉樹按權(quán)相加之和是最小的，一般來說，哈夫曼樹的形

49、態(tài)不是唯一的。理解哈夫曼編碼的基本原理，掌握基于哈夫曼樹生成哈夫曼編碼的方法。練習(xí)題：（一）選擇題：1. 一棵二叉樹的前序遍歷結(jié)果為ABCDEF，中序遍歷結(jié)果為CBAEDF，則后序遍歷結(jié)果為（A）A. CBEFDA B. FEDCBAC. CBEDFA D. 不確定2. 某二叉樹的后序遍歷序列為dabec，中序遍歷序列為debac，則前序遍歷序列為（D）。Aacbed Bdecab Cdeabc Dcedba3. 具有10個葉子結(jié)點的二叉樹中有（B）個度為2的結(jié)點。A. 8 B. 9C. 10 D. 114. 樹中所有結(jié)點的度等于所有結(jié)點數(shù)加（ C ）。A0 B1 C1 D25. 設(shè)n，m為一

50、棵二叉樹的兩個結(jié)點，在中序遍歷時，n在m前的條件是（ C ）A. n在m的右方 B. n是m的祖先C. n在m的左方 D. n是m的子孫6. 利用逐點插入建立序列（50，72，43，85，75，20，35，45，65，30）對應(yīng)的二叉排序樹以后，要查找元素30要進行（ B ）次元素間的比較。A4 B. 5C6 D. 77. 在平衡二叉樹中，（ C ）。A任意結(jié)點的左、右子樹結(jié)點數(shù)目相同B任意結(jié)點的左、右子樹高度相同C任意結(jié)點的左右子樹高度之差的絕對值不大于1D不存在度為1的結(jié)點8. 由元素序列（27，16，75，38，51）構(gòu)造平衡二叉樹，則首次出現(xiàn)的最小不平衡子樹的根（即離插入結(jié)點最近且平衡

51、因子的絕對值為2的結(jié)點）為（ D ）A27 B38C51 D. 759. 在二叉樹的順序存儲中，每個結(jié)點的存儲位置與其父結(jié)點、左右子樹結(jié)點的位置都存在一個簡單的映射關(guān)系，因此可與三叉鏈表對應(yīng)。若某二叉樹共有n個結(jié)點，采用三叉鏈表存儲時，每個結(jié)點的數(shù)據(jù)域需要d個字節(jié)，每個指針域占用4個字節(jié)，若采用順序存儲，則最后一個結(jié)點下標(biāo)為k（起始下標(biāo)為1），那么（ A ）時采用順序存儲更節(jié)省空間。Ad<12n/(k-n) B. d>12n/(k-n)C. d<12n/(k+n) D. d>12n/(k+n)10. 在常用的描述二叉排序樹的存儲結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點（ B ）A左指針一定為空 B. 右指針一定為空C左右指針均為空 D. 左右指針均不為空（二）應(yīng)用題1、一棵滿k叉樹，按層次遍歷（從1開始對全部結(jié)點進行編號）存儲在一維數(shù)組中，試計算編號為u的結(jié)點的第i個孩子（若存在）的下標(biāo)以及編號為v的結(jié)點的雙親結(jié)點（若存在）的下標(biāo)。答：結(jié)點下標(biāo)為u的結(jié)點的第i個孩子的下標(biāo)：結(jié)點下標(biāo)為v的結(jié)點的父母結(jié)點的下標(biāo)：2、試求有n個