數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享

1、數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享一些看法學(xué)了數(shù)據(jù)結(jié)構(gòu)的同學(xué)，不是被數(shù)據(jù)結(jié)構(gòu)傷的百孔千瘡，就是產(chǎn)生了心理陰影，太難太繞了。辛辛苦苦的學(xué)的差不多了吧，做程序的時候，好像根本用不上數(shù)據(jù)機構(gòu)一樣。此乃神物，花費那么大的力氣學(xué)，到時候用不上豈不是太虧了。很多很多的文章很多很多的過來人，都告訴你，數(shù)據(jù)結(jié)構(gòu)很重要。老師上來就跟你說，這個很重要很重要。其實沒有幾個老師能跟你講清楚數(shù)據(jù)結(jié)構(gòu)到底是什么，以至于你學(xué)完了都不知所云。都不知道學(xué)完后怎么用，如何用，有沒有用。雖然他們都說有用，非常有用，那怎么個有用法，很少提及。甚至，在工作中怎么體現(xiàn)的也不曾提及。似乎數(shù)據(jù)結(jié)構(gòu)就是什么棧、鏈表、二叉樹、圖之類的。其實這些東西不是數(shù)據(jù)結(jié)構(gòu)。

2、作為一個特別愛思考的人，沒有一個清晰的方向，學(xué)起來也是痛苦的，也是盲目的，雖然知道有用，但是還是如此?；蛘邠Q一種說法，清楚了自己學(xué)的東西，不僅學(xué)起來目標(biāo)明確，心情也爽快，同時效率還會很高。數(shù)據(jù)結(jié)構(gòu)+算法=程序其實，算法和數(shù)據(jù)結(jié)構(gòu)并非一個東西，數(shù)據(jù)結(jié)構(gòu)也不是鏈表之類的。這些都是錯誤的信號。數(shù)據(jù)結(jié)構(gòu)是一門抽象的學(xué)科。這個確實如此。而且非常抽象。然而我們的學(xué)習(xí)，最好是從具體的開始東西開始，這樣學(xué)習(xí)效果更好。很少有人一開始抽象思維就很好的，抽象思維是通過大量的培養(yǎng)才得到的。實際上在潛意識里，抽象思維好的人總會無意識的將一個抽象模型關(guān)聯(lián)到他熟知的一個東西或者現(xiàn)象中。而這些聯(lián)系在講授或?qū)W習(xí)知識的時候，又忽

3、略了。才導(dǎo)致抽象的東西，越來越抽象，或者說，我們沒有能夠?qū)⒊橄蟮臇|西足夠的具體化成一個實例。所以，你在學(xué)習(xí)的時候，盡量聯(lián)系實際中的案例來理解。數(shù)據(jù)結(jié)構(gòu)和算法，都是一種抽象的東西。其實就是人的思想。學(xué)好數(shù)據(jù)結(jié)構(gòu)和算法，就是去掌握那些別人已經(jīng)想出來的思想而已。并不是讓你去記住這些東西如何實現(xiàn)，怎么寫代碼怎么考試。而我們學(xué)到的各種數(shù)據(jù)結(jié)構(gòu)，是為了算法思路好完成邏輯而構(gòu)建的一些固定的模型，這些模型只是人為的一個規(guī)定而已。或者說，我們只是將這些比較不錯的想法思路取一個名字，然后大家交流的時候，說起這個名字就知道了這個數(shù)據(jù)結(jié)構(gòu)等。例如我們學(xué)習(xí)鏈表結(jié)構(gòu)之類的，就是人家建立的一個固定的模型，或者叫做一個約定的

4、操作方式。那么既然這些別人實現(xiàn)的都是一個典型的操作方式，那么必然有他的優(yōu)點，我們才需要學(xué)習(xí)的。然而你既然知道了天機，那么自然就可以去藐視天機，可以去創(chuàng)造，而不是一味的接受。既然是一種思想，你完全可以通過你自己的智慧去改善他的思想，這個就是思想更迭的過程。并不是后來人比前面的人聰明，而是因為他站在巨人的肩膀上起飛的。國內(nèi)的教育都是應(yīng)試教育，沒有挖掘這種創(chuàng)造力，然而，要想把這門課學(xué)好，就需要充分發(fā)揮創(chuàng)造力。你完全可以在掌握一種數(shù)據(jù)結(jié)構(gòu)模型后，改造它。可以創(chuàng)造出更好的數(shù)據(jù)結(jié)構(gòu)模型，在今后的多少年，可能教材里的結(jié)構(gòu)就出現(xiàn)了你的結(jié)構(gòu)模型了。以上是如何學(xué)習(xí)思想的看法。算法則是一套思維的流程，以何種邏輯或者

5、說是運算的先后順序?qū)⒁粋€目標(biāo)實現(xiàn)。比如說，冒泡排序，最終的目標(biāo)是將一組數(shù)據(jù)拍好順序，至于如何實現(xiàn)，其實可以有多種，并不是唯一的。冒泡代表一種思想。你只需要弄懂這個思想的關(guān)鍵，如何一步步運作到實現(xiàn)目標(biāo)的這個流程，就可以了。基于這個流程，你可以使用另外的實現(xiàn)方式來做到需要的目標(biāo)，而不必拘泥于課本上的實現(xiàn)過程。否則，你永遠都學(xué)不會算法。通常，算法都要用到數(shù)據(jù)結(jié)構(gòu)的各種模型，這些模型的建立，就是為了方便完成算法的邏輯流程的。正是這些數(shù)據(jù)結(jié)構(gòu)的存在，讓效率大大提升，或者讓操作過程更加簡便。如果你能理解我說的這些，說明你有所領(lǐng)悟，而徹底明白，只是時間的問題了，前提是要繼續(xù)思考。當(dāng)你領(lǐng)悟到數(shù)據(jù)結(jié)構(gòu)和算法不再

6、是書上那些東西，你就成功了一大半了。當(dāng)你的思維高于書上的東西，你學(xué)起來，那就簡單多了。至少你不會再迷茫，而只是熟悉那些套路而已了。你改進一個算法才成為可能，從此就不是死讀書的模式學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)了。數(shù)據(jù)結(jié)構(gòu)的研究內(nèi)容10/15/202114【數(shù)據(jù)結(jié)構(gòu)的三個方面研究內(nèi)容】具體來說，數(shù)據(jù)結(jié)構(gòu)包具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個方面的內(nèi)容，即含三個方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)和和對數(shù)據(jù)所施加的運算對數(shù)據(jù)所施加的運算（操作）。（操作）。 數(shù)據(jù)的邏輯結(jié)構(gòu)數(shù)據(jù)的邏輯結(jié)構(gòu)（面向人類）（面向人類） 數(shù)據(jù)的存儲結(jié)構(gòu)數(shù)據(jù)的存儲結(jié)構(gòu)（面向計算機）（面向計算機） 數(shù)據(jù)的運算（操作）：檢

7、索、排序、插入、刪除、修改等數(shù)據(jù)的運算（操作）：檢索、排序、插入、刪除、修改等 線性結(jié)構(gòu)線性結(jié)構(gòu) 非線性結(jié)構(gòu)非線性結(jié)構(gòu)順序存儲順序存儲鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯?線性表線性表棧棧隊列隊列樹形結(jié)構(gòu)樹形結(jié)構(gòu)圖形結(jié)構(gòu)圖形結(jié)構(gòu)散列存儲散列存儲索引存儲索引存儲串及數(shù)組串及數(shù)組第一講 緒論p了解數(shù)據(jù)結(jié)構(gòu)有關(guān)概念的含義，特別是數(shù)據(jù)的了解數(shù)據(jù)結(jié)構(gòu)有關(guān)概念的含義，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系；（邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)之間的關(guān)系；（重點重點）p熟悉類熟悉類C C語言的書寫規(guī)范；語言的書寫規(guī)范；p了解計算算法時間復(fù)雜度的方法。（了解計算算法時間復(fù)雜度的方法。（難點難點）10/15/202115數(shù)據(jù)結(jié)構(gòu)的定義 按某種邏

8、輯關(guān)系按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機語言帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計算機語言并并按一定的存儲表示方式按一定的存儲表示方式把它們存儲在計算把它們存儲在計算機的存儲器中，并機的存儲器中，并在其上在其上定義了一個運算定義了一個運算的的集合集合。基本概念和術(shù)語p【數(shù)據(jù)】是對信息的一種符號表示。是是對信息的一種符號表示。是可以輸入可以輸入計算機中，計算機中， 能被計算機能被計算機識別處理和輸出的識別處理和輸出的一切一切符號集合。符號集合。p【數(shù)據(jù)元素】是數(shù)據(jù)的是數(shù)據(jù)的基本單位基本單位，在計算機中通常作為一個，在計算機中通常作為一個 整體

9、進行考慮和處理。也稱為整體進行考慮和處理。也稱為記錄記錄。p【數(shù)據(jù)項】一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。是數(shù)據(jù)不一個數(shù)據(jù)元素可由若干個數(shù)據(jù)項組成。是數(shù)據(jù)不可分割的可分割的最小單位最小單位。p【數(shù)據(jù)對象】是是性質(zhì)相同性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個 子集子集。10/15/202117p【數(shù)據(jù)結(jié)構(gòu)】相互之間存在一種或多種相互之間存在一種或多種特定關(guān)系特定關(guān)系的數(shù)據(jù)的數(shù)據(jù) 元素的集合元素的集合計算機如何解決問題10/15/202118問題問題機外表示機外表示處理要求處理要求邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)基本運算基本運算數(shù)學(xué)模型數(shù)學(xué)模型存儲結(jié)構(gòu)存儲結(jié)構(gòu)編程實現(xiàn)編程實現(xiàn)實現(xiàn)實現(xiàn)建模

10、建模求精求精研究數(shù)據(jù)結(jié)構(gòu)是為了幫計算機解決問題！研究數(shù)據(jù)結(jié)構(gòu)是為了幫計算機解決問題！四種基本邏輯結(jié)構(gòu)10/15/202119【集合】 數(shù)據(jù)元素間除了“同屬于一個集合”外，無其他關(guān)系?！揪€性結(jié)構(gòu)】 1對1的關(guān)系比如線性表、棧、隊列?！緲湫谓Y(jié)構(gòu)】 1對多的關(guān)系比如樹。【圖形結(jié)構(gòu)】 多對多的關(guān)系比如圖。算法與數(shù)據(jù)結(jié)構(gòu)p算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切p選擇的數(shù)據(jù)結(jié)構(gòu)是否恰當(dāng)直接影響算法的效率；選擇的數(shù)據(jù)結(jié)構(gòu)是否恰當(dāng)直接影響算法的效率；而數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由算法的執(zhí)行來體現(xiàn)。而數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由算法的執(zhí)行來體現(xiàn)。p“算法算法 + + 數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) = = 程序程序”p算法 != 程序p算法是算法是供人閱讀供人閱讀

11、的，程序是的，程序是讓機器執(zhí)行讓機器執(zhí)行的的p算法用算法用計算機語言實現(xiàn)計算機語言實現(xiàn)時就是程序時就是程序p程序不具有算法的程序不具有算法的有窮性有窮性算法的概念v算法是解決某個特定問題的求解算法是解決某個特定問題的求解步驟步驟的描述。的描述。v算法在計算機中表現(xiàn)為指令的算法在計算機中表現(xiàn)為指令的有限有限序列，每條指令表示一序列，每條指令表示一個或多個操作。個或多個操作。v計算機對數(shù)據(jù)的操作可以分為計算機對數(shù)據(jù)的操作可以分為數(shù)值性數(shù)值性和和非數(shù)值性非數(shù)值性兩種類型兩種類型。在數(shù)值性操作中主要進行的是算術(shù)運算；而在非數(shù)值性。在數(shù)值性操作中主要進行的是算術(shù)運算；而在非數(shù)值性操作中主要進行的是檢索、

12、排序、插入、刪除等等。操作中主要進行的是檢索、排序、插入、刪除等等。v程序程序不等于不等于算法：計算機程序是算法的具體實現(xiàn)。算法：計算機程序是算法的具體實現(xiàn)。10/15/202121（1）有窮性：一個算法必須在執(zhí)行有窮步之后結(jié)束。：一個算法必須在執(zhí)行有窮步之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他：算法中的每一步，必須有確切的含義，在他人理解時不會產(chǎn)生二義性。人理解時不會產(chǎn)生二義性。（3）可行性：算法中描述的每一步操作都可以通過已有的：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實現(xiàn)?；静僮鲌?zhí)行有限次實現(xiàn)。（4）輸入：一個算法應(yīng)該有零個或多個輸入。：一個算法應(yīng)

13、該有零個或多個輸入。（5）輸出：一個算法應(yīng)該有一個或多個輸出。這里所說的：一個算法應(yīng)該有一個或多個輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。輸出是指與輸入有某種特定關(guān)系的量。算法的性質(zhì)算法設(shè)計的要求v正確性（四個境界）（四個境界）q沒有語法錯誤沒有語法錯誤q對于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出對于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出q對于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果對于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果q對于任何測試數(shù)據(jù)都有滿足要求的輸出結(jié)果對于任何測試數(shù)據(jù)都有滿足要求的輸出結(jié)果v可讀性：便于閱讀、理解和交流：便于閱讀、理解和交流v健壯性：不合法數(shù)據(jù)也能合理處理：

14、不合法數(shù)據(jù)也能合理處理v時間效率高和存儲量低10/15/202123算法效率的度量方法v事后統(tǒng)計方法q通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機測量其運行時間。通過設(shè)計好的測試程序和數(shù)據(jù)，利用計算機測量其運行時間。q缺陷：需要先編寫程序；和計算機軟硬件相關(guān)；和測試數(shù)據(jù)相關(guān)。缺陷：需要先編寫程序；和計算機軟硬件相關(guān)；和測試數(shù)據(jù)相關(guān)。v事前分析估算方法（我們的選擇）q依據(jù)依據(jù)統(tǒng)計方法統(tǒng)計方法對算法進行對算法進行估算估算。m = f(n)，m是語句總的執(zhí)行次數(shù)是語句總的執(zhí)行次數(shù)，n是輸入的規(guī)模。是輸入的規(guī)模。q和問題輸入規(guī)模相關(guān)和問題輸入規(guī)模相關(guān)，獨立于程序設(shè)計語言和計算機軟硬件，獨立于程序設(shè)計語言和計

15、算機軟硬件10/15/202124算法時間復(fù)雜度10/15/202125p在進行算法分析時，語句的總執(zhí)行次數(shù)在進行算法分析時，語句的總執(zhí)行次數(shù) T(n)是關(guān)于問題是關(guān)于問題規(guī)模規(guī)模 n 的函數(shù)，進而分析的函數(shù)，進而分析 T(n) 隨隨 n 的的變化情況變化情況并確定并確定 T(n) 的的數(shù)量級數(shù)量級。p算法的時間復(fù)雜度，也就是算法的時間量度，用算法的時間復(fù)雜度，也就是算法的時間量度，用“大大O記法記法”記作：記作：T(n)=O(f(n)。由此得到的。由此得到的 T(n) 的數(shù)量級叫的數(shù)量級叫“大大O階階”。它表示隨問題規(guī)模。它表示隨問題規(guī)模 n 的增大，算法執(zhí)行時間增長的增大，算法執(zhí)行時間增長

16、率和率和 f(n)的的增長率相同增長率相同，稱作算法的，稱作算法的漸進時間復(fù)雜度漸進時間復(fù)雜度，簡，簡稱時間復(fù)雜度。其中稱時間復(fù)雜度。其中 f(n) 是問題規(guī)模是問題規(guī)模 n 的的某個函數(shù)某個函數(shù)。p一般情況下，一般情況下，T(n)增長增長越慢越慢，算法，算法越優(yōu)越優(yōu)。大O階的數(shù)學(xué)定義 當(dāng)當(dāng)n時，有時，有f(n)/g(n)=常數(shù)常數(shù)0，則稱函數(shù)，則稱函數(shù)f(n)與與g(n)同階同階,或者說，或者說，f(n)與與g(n)同一個數(shù)量級，記作同一個數(shù)量級，記作 f(n)=O(g(n) 稱上式為算法的時間復(fù)雜度稱上式為算法的時間復(fù)雜度,或稱該算法的時間復(fù)雜或稱該算法的時間復(fù)雜度為度為O(g(n) 。其

17、中其中, n為問題的規(guī)模為問題的規(guī)模(大小大小)的量度。的量度。若lim(f(n)/g(n) =lim(2n3 + 3n2 + 2n + 1)/n3) =2nn則算法的時間復(fù)雜度為O(n3)算法空間復(fù)雜度10/15/202127算法的空間復(fù)雜度通過計算算法算法的空間復(fù)雜度通過計算算法所需的存儲空間所需的存儲空間實現(xiàn)，實現(xiàn)，算法空間復(fù)雜度的計算公式記作：算法空間復(fù)雜度的計算公式記作：S(n) = O(f(n)，其中，其中， n 為問題的規(guī)模，為問題的規(guī)模，f(n)為語句關(guān)于為語句關(guān)于 n 所占存所占存儲空間的函數(shù)。儲空間的函數(shù)。 我們主要討論時間復(fù)雜度問題。例題解析【例1】數(shù)據(jù)元素之間的關(guān)系在計

18、算機中有幾種表示方法？各有什么特點？答：答：四種表示方法四種表示方法（1）順序存儲方式。順序存儲方式。數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素順序存放，每個存儲結(jié)點只含一個元素。存儲位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。數(shù)據(jù)元素間的邏輯關(guān)系。存儲密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯Ψ绞?。鏈?zhǔn)酱鎯Ψ绞?。每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指每個存儲結(jié)點除包含數(shù)據(jù)元素信息外還包含一組（至少一個）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操針。指針反映數(shù)據(jù)元素間的邏輯

19、關(guān)系。這種方式不要求存儲空間連續(xù)，便于動態(tài)操作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。作（如插入、刪除等），但存儲空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲方式。索引存儲方式。除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引除數(shù)據(jù)元素存儲在一地址連續(xù)的內(nèi)存空間外，尚需建立一個索引表，索引表中索引指示存儲結(jié)點的存儲位置（下標(biāo)）或存儲區(qū)間端點（下標(biāo)），兼表，索引表中索引指示存儲結(jié)點的存儲位置（下標(biāo)）或存儲區(qū)間端點（下標(biāo)），兼有靜態(tài)和動態(tài)特性。有靜態(tài)和動態(tài)特性。（4）散列存儲方式。散列存儲方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有

20、限的通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲地址，這種存儲方式稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也稱為散列存儲。其特點是存取速度快，只能按關(guān)鍵字隨機存取，不能順序存取，也不能折半存取。不能折半存取。10/15/202128例題解析【例2】有下列運行時間函數(shù)： （1）T1(n)=1000; （2）T2(n)=n2+1000n; （3）T3(n)=3n3+100n2+n+1; 分別寫出相應(yīng)的大 O 表示的運算時間答：答：(

21、1)O(1) (2)O(n2) (3)O(n3)10/15/202129第二講 線性表v線性結(jié)構(gòu)的定義和特點q在數(shù)據(jù)元素的非空有限集中，有且僅有一個開始結(jié)點和在數(shù)據(jù)元素的非空有限集中，有且僅有一個開始結(jié)點和一個終端結(jié)點，并且所有結(jié)點只有一個直接前趨和一個一個終端結(jié)點，并且所有結(jié)點只有一個直接前趨和一個直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是直接后繼。簡言之，線性結(jié)構(gòu)反映結(jié)點間的邏輯關(guān)系是 一對一一對一。線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、。線性結(jié)構(gòu)包括線性表、堆棧、隊列、字符串、數(shù)組等等，其中，最簡單、最常用的是線性表。數(shù)組等等，其中，最簡單、最常用的是線性表。v線性表的存儲方法q

22、順序存儲：邏輯上相鄰物理上順序存儲：邏輯上相鄰物理上一定一定相鄰相鄰q鏈?zhǔn)酱鎯Γ哼壿嬌舷噜徫锢砩湘準(zhǔn)酱鎯Γ哼壿嬌舷噜徫锢砩喜灰欢ú灰欢ㄏ噜徬噜忢樞虮韛順序表線性表的順序存儲表示線性表的順序存儲表示v順序存儲用一用一組地址連續(xù)的組地址連續(xù)的存儲單元存儲單元依次依次存儲線性表存儲線性表的元素，可通過的元素，可通過數(shù)組數(shù)組來實現(xiàn)。（邏輯上相鄰物理上一定相來實現(xiàn)。（邏輯上相鄰物理上一定相鄰）鄰）q LOC(ai ) = LOC(a1) + (i - 1) len （a1為首元素，為首元素，len為單個元素占用空間長度為單個元素占用空間長度）v順序存儲的優(yōu)點q可以隨機存取表中任一元素可以隨機存取表中任一

23、元素O(1)；存儲空間使用緊湊；存儲空間使用緊湊v順序存儲的缺點q在插入元素時平均需要移動在插入元素時平均需要移動n/2個元素，刪除某一元素時，平均需個元素，刪除某一元素時，平均需要移動要移動n-1/2個元素。個元素。算法的平均時間復(fù)雜度為算法的平均時間復(fù)雜度為O(n)q預(yù)先分配空間需按最大空間分配，利用不充分預(yù)先分配空間需按最大空間分配，利用不充分;表容量難以擴充表容量難以擴充10/15/202131鏈表v鏈?zhǔn)酱鎯Y(jié)構(gòu)特點q用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素用一組任意的存儲單元存儲線性表的數(shù)據(jù)元素q利用指針實現(xiàn)了用不相鄰的存儲單元存放邏輯上相鄰的元素利用指針實現(xiàn)了用不相鄰的存儲單元存放

24、邏輯上相鄰的元素q每個數(shù)據(jù)元素每個數(shù)據(jù)元素ai，除存儲本身信息外，還需存儲其直接后繼的信息除存儲本身信息外，還需存儲其直接后繼的信息 v鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點：q結(jié)點空間可以結(jié)點空間可以動態(tài)申請和釋放動態(tài)申請和釋放；q數(shù)據(jù)元素的邏輯次序靠結(jié)點的指針來指示，數(shù)據(jù)元素的邏輯次序靠結(jié)點的指針來指示，插入和刪除時不需要移插入和刪除時不需要移動數(shù)據(jù)元素動數(shù)據(jù)元素。v鏈?zhǔn)酱鎯Y(jié)構(gòu)的缺點：q每個結(jié)點的每個結(jié)點的。當(dāng)數(shù)據(jù)域所占字節(jié)不多時。當(dāng)數(shù)據(jù)域所占字節(jié)不多時，指針域所占存儲空間的比重顯得很大。，指針域所占存儲空間的比重顯得很大。 q鏈表鏈表是是結(jié)構(gòu)結(jié)構(gòu)。對任一結(jié)點的操作都要從頭指針依鏈查找。對任一結(jié)點的操作都要

25、從頭指針依鏈查找該結(jié)點，這增加了算法的復(fù)雜度該結(jié)點，這增加了算法的復(fù)雜度 O（n）q不不便于便于在表尾在表尾插入插入元素：需遍歷整個表才能找到位置。元素：需遍歷整個表才能找到位置。10/15/202132例題解析【例例1】說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭結(jié)點之間的根本區(qū)別。結(jié)點之間的根本區(qū)別。答：答：在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標(biāo)識作表有頭結(jié)點則是鏈表的頭結(jié)點的指針，頭指針具有標(biāo)識作用，故常用頭指針冠以鏈表的名字。用，故常用頭指針冠

26、以鏈表的名字。頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素頭結(jié)點是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存結(jié)點之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長度、用做監(jiān)視哨等等），有頭結(jié)點后，對在第放鏈表的長度、用做監(jiān)視哨等等），有頭結(jié)點后，對在第一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它一元素結(jié)點前插入結(jié)點和刪除第一結(jié)點，其操作與對其它結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不結(jié)點的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。為空。10/15/202133例題解析 【例例2】設(shè)順序表設(shè)順序表va中的數(shù)據(jù)元

27、素遞增有序。試設(shè)計一個算法，將中的數(shù)據(jù)元素遞增有序。試設(shè)計一個算法，將x插入插入到順序表的適當(dāng)位置上，以保持該表的有序性。到順序表的適當(dāng)位置上，以保持該表的有序性。答：答：void Insert_SqList(SqList va, int x) /*把把x插入遞增有序表插入遞增有序表va中中*/ int i; if (va.length MAXSIZE) return; for (i=va.length-1; va.elemix & i=0; i-) va.elemi+1=va.elemi; va.elemi+1=x; va.length+;/*Insert_SqList*/ 10/15/20

28、2134#define MAXSIZE 100 typedef struct ElemType *elem; int length;SqList；例題解析【例例3】設(shè)單鏈表結(jié)點指針域為設(shè)單鏈表結(jié)點指針域為 next，試寫出刪除鏈，試寫出刪除鏈表中指針表中指針 p 所指結(jié)點的直接后繼的所指結(jié)點的直接后繼的 C 語言語句。語言語句。答：答： q = p-next; p-next = q-next; free(q);10/15/202135例題解析【例例4】設(shè)單鏈表中某指針設(shè)單鏈表中某指針 p 所指結(jié)點（即所指結(jié)點（即 p 結(jié)點）結(jié)點）的數(shù)據(jù)域為的數(shù)據(jù)域為 data，鏈指針域為，鏈指針域為 next

29、，請寫出在，請寫出在 p 結(jié)點之前插入結(jié)點之前插入 s 結(jié)點的操作。結(jié)點的操作。答：答：設(shè)單鏈表的頭結(jié)點的頭指針為設(shè)單鏈表的頭結(jié)點的頭指針為head,且且pre=head； while (pre-next != p) pre=pre-next; s-next = p; pre-next=s;10/15/202136例題解析【例例5】試編寫在帶頭結(jié)點的單鏈表中刪除（一個）最小值結(jié)點的算法。試編寫在帶頭結(jié)點的單鏈表中刪除（一個）最小值結(jié)點的算法。void delete（Linklist &L）答：答：題目分析題目分析 本題要求在單鏈表中刪除最小值結(jié)點。單鏈表中刪除結(jié)點，為使結(jié)點刪除后不出本題要求在

30、單鏈表中刪除最小值結(jié)點。單鏈表中刪除結(jié)點，為使結(jié)點刪除后不出現(xiàn)現(xiàn)“斷鏈斷鏈”，應(yīng)知道被刪結(jié)點的前驅(qū)。而，應(yīng)知道被刪結(jié)點的前驅(qū)。而“最小值結(jié)點最小值結(jié)點”是在遍歷整個鏈表后才能知道。所是在遍歷整個鏈表后才能知道。所以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點及其前驅(qū)。遍歷結(jié)束后再執(zhí)行刪除操作。以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點及其前驅(qū)。遍歷結(jié)束后再執(zhí)行刪除操作。 void delete（LinkedList &L） L是帶頭結(jié)點的單鏈表是帶頭結(jié)點的單鏈表 p = L-next； p為工作指針。指向待處理的結(jié)點。假定鏈表非空。為工作指針。指向待處理的結(jié)點。假定鏈表非空。 pre = L； pre指向最小

31、值結(jié)點的前驅(qū)。指向最小值結(jié)點的前驅(qū)。 q = p； q指向最小值結(jié)點，初始假定第一元素結(jié)點是最小值結(jié)點。指向最小值結(jié)點，初始假定第一元素結(jié)點是最小值結(jié)點。 while（p-next!=null） if（p-next-datadata）pre=p；q=p-next；查最小值結(jié)點查最小值結(jié)點 p = p-next； 指針后移。指針后移。 pre-next=q-next；從鏈表上刪除最小值結(jié)點從鏈表上刪除最小值結(jié)點 free（q）；）； 釋放最小值結(jié)點空間釋放最小值結(jié)點空間 結(jié)束算法結(jié)束算法delete。10/15/202137例題解析【例例6】一元稀疏多項式以循環(huán)單鏈表按降冪排列，結(jié)點有三個域，系

32、數(shù)域一元稀疏多項式以循環(huán)單鏈表按降冪排列，結(jié)點有三個域，系數(shù)域 coef，指數(shù)域，指數(shù)域 exp 和指針域和指針域 next；現(xiàn)對鏈表求一階導(dǎo)數(shù)；現(xiàn)對鏈表求一階導(dǎo)數(shù) ，鏈表的，鏈表的頭指針為頭指針為 ha，頭結(jié)點的，頭結(jié)點的 exp 域為域為 1。 void derivative(ha) q=ha ; pa=ha-next; while( (1)_) if ( (2)_) ( (3)_); free(pa); pa= ( (4) _); else pa-coef ( (5) _); pa-exp( (6)_); q=( (7) _); pa=( (8)_); 10/15/202138(1) p

33、a!=ha 或或pa-exp!=-1(2) pa-exp=0 若指數(shù)為若指數(shù)為0，即本項為常數(shù)項，即本項為常數(shù)項(3) q-next=pa-next 刪常數(shù)項刪常數(shù)項(4) q-next 取下一元素取下一元素(5) =pa-coef*pa-exp(6) - 指數(shù)項減指數(shù)項減1(7) pa 前驅(qū)后移前驅(qū)后移,或或q-next(8) pa-next 取下一元素取下一元素 第三講 棧和隊列v棧q限定僅在表尾進行插入和刪除的線性表，把這限定僅在表尾進行插入和刪除的線性表，把這個表尾稱為個表尾稱為棧頂棧頂。v特點q后進先出后進先出(LIFO表表)v棧的存儲方法q棧的順序存儲棧的順序存儲順序棧順序棧q棧的

34、鏈?zhǔn)酱鎯５逆準(zhǔn)酱鎯︽湕ｆ湕?0/15/202139關(guān)于棧要求掌握的內(nèi)容10/15/202140 棧的基本概念：棧的基本概念：LIFOLIFO 棧的存儲棧的存儲棧的應(yīng)用（了解）棧的應(yīng)用（了解）順序棧順序棧（熟練掌握）（熟練掌握）鏈棧鏈棧（熟練掌握）（熟練掌握）初始化初始化取棧頂取棧頂入棧出棧入棧出棧判斷?？张袛鄺？?棧棧初始化初始化取棧頂取棧頂入棧出棧入棧出棧判斷?？张袛鄺？贞犃卸x10/15/202141 隊列的定義隊列的定義 線性表線性表 特點：先進先出特點：先進先出 (FIFO結(jié)構(gòu)結(jié)構(gòu))。 隊頭隊頭 下圖是隊列的示意圖：下圖是隊列的示意圖： a1a2an 出隊出隊 入隊入隊 隊頭隊頭 隊

35、尾隊尾 當(dāng)隊列中沒有元素時稱為當(dāng)隊列中沒有元素時稱為空隊列空隊列。 表尾稱為隊尾表尾稱為隊尾(rear)表頭稱為隊頭表頭稱為隊頭(front)插入元素稱為入隊插入元素稱為入隊刪除元素稱為出隊刪除元素稱為出隊限定在表的一端插入、另一端刪除。限定在表的一端插入、另一端刪除。 順序隊列的假溢出問題10/15/202142 在順序隊列中，當(dāng)尾指針已經(jīng)指向了隊列的最后一個在順序隊列中，當(dāng)尾指針已經(jīng)指向了隊列的最后一個 位置即數(shù)組上界時，若再有元素入隊，就會發(fā)生位置即數(shù)組上界時，若再有元素入隊，就會發(fā)生“”。 “”隊列的存儲空間未滿，卻發(fā)生了溢出。隊列的存儲空間未滿，卻發(fā)生了溢出。 rear front

36、J1 J2 J3 J4 rear front J3 J4 (1)、平移元素：把元素平移到隊列的首部。、平移元素：把元素平移到隊列的首部。 解決解決“假溢出假溢出”的問題有兩種可行的方法：的問題有兩種可行的方法： (2)、將新元素插入到第一個位置上，構(gòu)成、將新元素插入到第一個位置上，構(gòu)成循環(huán)隊列循環(huán)隊列， 入隊和出隊仍按入隊和出隊仍按“先進先出先進先出”的原則進行。的原則進行。 。 rear front J3 J4 front rear J3 J4 循環(huán)隊列10/15/202143隊空條件隊空條件 : front = rear (初始化時：初始化時：front = rear )隊滿條件隊滿條件：

37、 front = (rear+1) % N (N=maxsize)隊列長度：隊列長度：L=（Nrearfront）% N J2 J3J1 J4 J5frontrear 選用選用空閑單元法：空閑單元法：即即front和和rear之一指向?qū)嵲?，另一指向空閑元素。之一指向?qū)嵲?，另一指向空閑元素。 問問2： 在具有在具有n個單元的循個單元的循環(huán)隊列中，隊滿時共有多少環(huán)隊列中，隊滿時共有多少個元素？個元素？ n-1個個5 問問1：左圖中隊列長度左圖中隊列長度L=？例題解析【例例1】一個棧的輸入序列是一個棧的輸入序列是12345，若在入棧，若在入棧的過程中允許出棧，則棧的輸出序列的過程中允許出棧，則棧

38、的輸出序列43512可能可能實現(xiàn)嗎？實現(xiàn)嗎？12345的輸出呢？的輸出呢？答：答：4351243512不可能實現(xiàn)，主要是其中的不可能實現(xiàn)，主要是其中的1212順序不能實順序不能實現(xiàn)；現(xiàn)；1234512345的輸出可以實現(xiàn)，只需壓入一個立即彈出的輸出可以實現(xiàn)，只需壓入一個立即彈出一個即可。一個即可。 10/15/202144例題解析【例例2】如果一個棧的輸入序列為如果一個棧的輸入序列為123456，能，能否得到否得到435612和和135426的出棧序列？的出棧序列？答：答：435612中到了中到了12順序不能實現(xiàn)；順序不能實現(xiàn)；135426可以實現(xiàn)?？梢詫崿F(xiàn)。10/15/202145例題解析【

39、例例3 3】一個棧的輸入序列為一個棧的輸入序列為123123，若在入棧的過程中允許出，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？棧，則可能得到的出棧序列是什么？答：答：可以通過窮舉所有可能性來求解：可以通過窮舉所有可能性來求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入入3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出， 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213；

40、1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合計有合計有5 5種可能性。種可能性。10/15/202146例題解析【例例4】簡述順序存儲隊列的假溢出的避免方法及隊列滿和簡述順序存儲隊列的假溢出的避免方法及隊列滿和空的條件?？盏臈l件。答：設(shè)順序存儲隊列用一維數(shù)組答：設(shè)順序存儲隊列用一維數(shù)組qm表示，其中表示，其中m為隊列中元素個數(shù)，為隊列中元素個數(shù)，隊列中元素在向量中的下標(biāo)從隊列中元素在向量中的下標(biāo)從0到到m-1。設(shè)隊頭指針為。設(shè)隊頭指針為front，隊尾指，隊尾指針是針是rear，約定，約定front指向隊頭元素的前一位置，指向隊頭元素的前一位置，rear指

41、向隊尾元指向隊尾元素。當(dāng)素。當(dāng)front等于等于-1時隊空，時隊空，rear等于等于m-1時為隊滿。由于隊列的性時為隊滿。由于隊列的性質(zhì)（質(zhì)（“刪除刪除”在隊頭而在隊頭而“插入插入”在隊尾），所以當(dāng)隊尾指針在隊尾），所以當(dāng)隊尾指針rear等于等于m-1時，若時，若front不等于不等于-1，則隊列中仍有空閑單元，所以隊列并不，則隊列中仍有空閑單元，所以隊列并不是真滿。這時若再有入隊操作，會造成假是真滿。這時若再有入隊操作，會造成假“溢出溢出”。其解決辦法有二。其解決辦法有二，一是將隊列元素向前，一是將隊列元素向前“平移平移”（占用（占用0至至rear-front-1）；二是）；二是將隊列看成首

42、尾相連，即循環(huán)隊列（將隊列看成首尾相連，即循環(huán)隊列（0.m-1）。在循環(huán)隊列下，仍）。在循環(huán)隊列下，仍定義定義front=rear時為隊空，而判斷隊滿則用兩種辦法，一是用時為隊空，而判斷隊滿則用兩種辦法，一是用“犧犧牲一個單元牲一個單元”，即，即rear+1=front（準(zhǔn)確記是（準(zhǔn)確記是（rear+1）%m=front，m是隊列容量）時為隊滿。另一種解法是是隊列容量）時為隊滿。另一種解法是“設(shè)標(biāo)記設(shè)標(biāo)記”方法方法，如設(shè)標(biāo)記，如設(shè)標(biāo)記tag，tag等于等于0情況下，若刪除時導(dǎo)致情況下，若刪除時導(dǎo)致front=rear為隊為隊空；空；tag=1情況下，若因插入導(dǎo)致情況下，若因插入導(dǎo)致front=

43、rear則為隊滿。則為隊滿。10/15/202147第四講 串和數(shù)組【例例1】填空題：填空題：1. 空格串是指空格串是指_，其長度等于，其長度等于_?！敬鸢复鸢浮浚?）由空格字符（）由空格字符（ASCII值值32）所組成的字符串）所組成的字符串 （2）空）空格個數(shù)格個數(shù)2組成串的數(shù)據(jù)元素只能是組成串的數(shù)據(jù)元素只能是_?！敬鸢复鸢浮孔址址窘馕鼋馕觥看且环N特殊的線性表，其特殊性在于串中的元素只能是字符串是一種特殊的線性表，其特殊性在于串中的元素只能是字符型數(shù)據(jù)。型數(shù)據(jù)。3兩個字符串相等的充分必要條件是兩個字符串相等的充分必要條件是_?！敬鸢复鸢浮績纱拈L度相等且兩串中對應(yīng)位置上的字符也相等。

44、兩串的長度相等且兩串中對應(yīng)位置上的字符也相等。4一個字符串中一個字符串中_稱為該串的子串稱為該串的子串 。【答案答案】任意個連續(xù)的字符組成的子序列任意個連續(xù)的字符組成的子序列10/15/202148例題解析【例例2】設(shè)計一個算法，將字符串設(shè)計一個算法，將字符串s的全部字符復(fù)制到字的全部字符復(fù)制到字符串符串t中，不能利用中，不能利用strcpy函數(shù)。函數(shù)。答：答：【算法分析算法分析】要實現(xiàn)兩個字符串的復(fù)制，實質(zhì)為兩個字符數(shù)組之間要實現(xiàn)兩個字符串的復(fù)制，實質(zhì)為兩個字符數(shù)組之間的復(fù)制，在復(fù)制時，一個字符一個字符的復(fù)制，直到遇到的復(fù)制，在復(fù)制時，一個字符一個字符的復(fù)制，直到遇到0，0一同復(fù)制過去，一同

45、復(fù)制過去，0之后的字符不復(fù)制。之后的字符不復(fù)制。【算法源代碼算法源代碼】void copy(char s,char t) int i; for(i=0;si!=0;i+) ti=si; ti=si;10/15/202149例題解析【例例3】設(shè)有一個二維數(shù)組設(shè)有一個二維數(shù)組Amn，假設(shè)，假設(shè)A00存放存放位置在位置在644，A22存放位置在存放位置在676，每個元素占一，每個元素占一個空間，問個空間，問A33存放在什么位置？存放在什么位置？答：設(shè)數(shù)組元素答：設(shè)數(shù)組元素Aij存放在起始地址為存放在起始地址為Loc（i, j）的存儲單元中。）的存儲單元中。 Loc （ 2, 2 ） = Loc （

46、0, 0 ） + 2 * n + 2 = 644 + 2 * n + 2 = 676. n = （ 676 - 2 - 644 ） / 2 = 15 Loc （ 3, 3 ） = Loc （ 0, 0 ） + 3 * 15 + 3 = 644 + 45 + 3 = 692.10/15/202150例題解析【例例4】設(shè)有一個設(shè)有一個n n的對稱矩陣的對稱矩陣A，為了節(jié)約存儲，可以只存對角線及對角線以，為了節(jié)約存儲，可以只存對角線及對角線以上的元素，或者只存對角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后上的元素，或者只存對角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們

47、按行存放于一個一維數(shù)組者稱為下三角矩陣。我們把它們按行存放于一個一維數(shù)組B中，稱之為對稱矩中，稱之為對稱矩陣陣A的壓縮存儲方式。試問：的壓縮存儲方式。試問：（1） 存放對稱矩陣存放對稱矩陣A上三角部分或下三角部分的一維數(shù)組上三角部分或下三角部分的一維數(shù)組B有多少元素？有多少元素？（2） 若在一維數(shù)組若在一維數(shù)組B中從中從0號位置開始存放，則對稱矩陣中的任一元素號位置開始存放，則對稱矩陣中的任一元素aij在只在只存下三角部分的情形下應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。存下三角部分的情形下應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計算公式。答：答：（1） 數(shù)組數(shù)組B共有共有12 + 3 + + n

48、= （ n+1 ）*n / 2個元素。個元素。 （2） 只存下三角部分時，若只存下三角部分時，若i j，則數(shù)組元素，則數(shù)組元素Aij前面有前面有i-1行（行（1 i-1，第，第0行第行第0列不算），第列不算），第1行有行有1個元素，第個元素，第2行有行有2個元素，個元素，第，第i-1行有行有i-1個元素。個元素。在第在第i行中，第行中，第j號元素排在第號元素排在第j個元素位置，因此，數(shù)組元素個元素位置，因此，數(shù)組元素Aij在數(shù)組在數(shù)組B中的存中的存放位置為：放位置為：1 + 2 + + （i-1） + j = （i-1）*i / 2 + j若若i j，數(shù)組元素，數(shù)組元素Aij在數(shù)組在數(shù)組B中沒

49、有存放，可以找它的對稱元素中沒有存放，可以找它的對稱元素Aji。在數(shù)。在數(shù)組組B的第的第 （j-1）*j / 2 + i位置中找到。如果第位置中找到。如果第0行第行第0列也計入，數(shù)組列也計入，數(shù)組B從從0號位號位置開始存放，則數(shù)組元素置開始存放，則數(shù)組元素Aij在數(shù)組在數(shù)組B中的存放位置可以改為：當(dāng)中的存放位置可以改為：當(dāng)i j時，時，= i*（i+1） / 2 + j；當(dāng)；當(dāng)i n，則無左孩子；，則無左孩子； 3)i的右孩子是的右孩子是2i + 1，如果，如果2i + 1n則無右孩子。則無右孩子。例題解析1深度為深度為H 的完全二叉樹至少有的完全二叉樹至少有_個結(jié)點；至多有個結(jié)點；至多有_個

50、結(jié)個結(jié)點；點；H和結(jié)點總數(shù)和結(jié)點總數(shù)N之間的關(guān)系是之間的關(guān)系是_。【答案答案】（1）2H-1 （2）2H-1 （3）H= log2N +1 2一棵有一棵有n個結(jié)點的滿二叉樹有個結(jié)點的滿二叉樹有_個度為個度為1的結(jié)點，有的結(jié)點，有_個個分支（非終端）結(jié)點和分支（非終端）結(jié)點和_個葉子，該滿二叉樹的深度為個葉子，該滿二叉樹的深度為_?！敬鸢复鸢浮浚?）0 （2）(n-1）/2 （3）(n+1）/2 （4） log2n +13對于一個具有對于一個具有n個結(jié)點的二叉樹，當(dāng)它為一棵個結(jié)點的二叉樹，當(dāng)它為一棵_時，具有最小高度，當(dāng)時，具有最小高度，當(dāng)它為一棵它為一棵_時，具有最大高度。時，具有最大高度?！?/p>

51、答案答案】（1）完全二叉樹）完全二叉樹（2）單支樹，樹中任一結(jié)點（除最后一個結(jié)點是葉子外）單支樹，樹中任一結(jié)點（除最后一個結(jié)點是葉子外），只有左子女或只有右子女。，只有左子女或只有右子女。4已知二叉樹有已知二叉樹有50個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是個葉子結(jié)點，則該二叉樹的總結(jié)點數(shù)至少是_?！敬鸢复鸢浮?9【解析解析】在二叉樹中，在二叉樹中，N0 = N2+1，所以，有，所以，有50個葉子結(jié)點的二叉樹，有個葉子結(jié)點的二叉樹，有49個度為個度為2的結(jié)的結(jié)點。若要使該二叉樹的結(jié)點數(shù)最少，度為點。若要使該二叉樹的結(jié)點數(shù)最少，度為1的結(jié)點應(yīng)為的結(jié)點應(yīng)為0個，即總結(jié)點數(shù)個，即總結(jié)點數(shù)N= N0 +

52、N1+ N2 =99。10/15/202154二叉樹的存儲（一）10/15/202155v二叉樹存儲方法有二叉樹存儲方法有順序存儲順序存儲和和鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯二叉樹二叉樹順序存儲順序存儲結(jié)構(gòu)結(jié)構(gòu)q完全二叉樹完全二叉樹：用一組地址連續(xù)的存儲單元依次：用一組地址連續(xù)的存儲單元依次自上而下自上而下、自左至右、自左至右存儲結(jié)點元素，即將編號為存儲結(jié)點元素，即將編號為 i 的結(jié)點元素的結(jié)點元素存儲在一維數(shù)組中下標(biāo)為存儲在一維數(shù)組中下標(biāo)為 i 的分量中（不用下標(biāo)為的分量中（不用下標(biāo)為0存存儲單元）。儲單元）。此此順序存儲結(jié)構(gòu)僅適用于完全二叉樹順序存儲結(jié)構(gòu)僅適用于完全二叉樹 q不是完全二叉樹怎么辦？不是完

53、全二叉樹怎么辦？o一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上一律轉(zhuǎn)為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛虛結(jié)點結(jié)點”，其內(nèi)容為空。，其內(nèi)容為空。q缺點：缺點：浪費空間；插入、刪除不便浪費空間；插入、刪除不便二叉樹的存儲（二）10/15/202156二叉樹鏈?zhǔn)酱鎯Y(jié)構(gòu) 存儲方式 一般從根結(jié)點開始存儲，用二叉鏈表來表示。一般從根結(jié)點開始存儲，用二叉鏈表來表示。（相應(yīng)地，訪問樹中結(jié)點時也只能從根開始）（相應(yīng)地，訪問樹中結(jié)點時也只能從根開始） 二叉樹結(jié)點的特點二叉樹是非線性結(jié)構(gòu)，適合用鏈?zhǔn)酱鎯Y(jié)構(gòu)lchild data rchild結(jié)點結(jié)構(gòu)結(jié)點結(jié)構(gòu) data rchild lch

54、ild data parentlchildrchild二叉樹結(jié)點數(shù)據(jù)類型定義：二叉樹結(jié)點數(shù)據(jù)類型定義：typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;二叉樹遍歷10/15/202157v若規(guī)定先左后右，則只有前三種情況： 前（根）序遍歷，前（根）序遍歷， 中（根）序遍歷，中（根）序遍歷， 后（根）序遍歷后（根）序遍歷v根據(jù)遍歷順序確定一棵二叉樹q已知二叉樹的已知二叉樹的前序前序序列和序列和中序中序序列，序列，可以可以唯一確定一棵二叉樹。唯一確定一棵二叉樹。q已知二叉樹的已

55、知二叉樹的后序后序序列和序列和中序中序序列，序列，可以可以唯一確定一棵二叉樹。唯一確定一棵二叉樹。q已知二叉樹的已知二叉樹的前序前序序列和序列和后序后序序列，序列，不能不能唯一確定一棵二叉樹。唯一確定一棵二叉樹。例題解析10/15/202158設(shè)二叉樹設(shè)二叉樹bt的一種存儲結(jié)構(gòu)如下：的一種存儲結(jié)構(gòu)如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild 其中其中bt為樹根結(jié)點指針為樹根結(jié)點指針,lchild、rchild分別為結(jié)點的左、右孩分別為結(jié)點的左、右孩子指針域子指針域,在這里使用結(jié)點編號作為指針域值在這里使用結(jié)點編號作為

56、指針域值,0表示指針域為表示指針域為空空;data為結(jié)點的數(shù)據(jù)域。請完成下列各題：為結(jié)點的數(shù)據(jù)域。請完成下列各題：(1)畫出二叉樹的樹形表示；畫出二叉樹的樹形表示； (2)寫出按先序、中序和后序遍歷二叉樹寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點序列；所得到的結(jié)點序列；例題解析（續(xù)）10/15/20215900237580101jhfdbacegi000940000012345678910lchilddatarchild(1)畫出二叉樹的樹形表示；因畫出二叉樹的樹形表示；因為第為第6號結(jié)點不是任何結(jié)點的孩號結(jié)點不是任何結(jié)點的孩子結(jié)點，該結(jié)點必定是根結(jié)點，子結(jié)點，該結(jié)點必定是根結(jié)點，再根據(jù)

57、和結(jié)點左、右指針域的值再根據(jù)和結(jié)點左、右指針域的值很容易得到該二叉樹的樹形表示很容易得到該二叉樹的樹形表示為為 abgfdcehij例題解析（續(xù)）10/15/20216000237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij (2)寫出按先序、中序和后寫出按先序、中序和后序遍歷二叉樹序遍歷二叉樹bt所得到的結(jié)點所得到的結(jié)點序列；序列；a.先序序列先序序列ab c e df h g i j例題解析（續(xù)）10/15/20216100237580101jhfdbacegi000940000012345678910lch

58、ilddatarchildabgfdcehij (2)寫出按先序、中序和后寫出按先序、中序和后序遍歷二叉樹序遍歷二叉樹bt所得到的結(jié)點所得到的結(jié)點序列；序列；a.先序序列先序序列ab c e df h g i jb.中序序列中序序列ec bhf dj i ga例題解析（續(xù)）10/15/20216200237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij (2)寫出按先序、中序和后序遍寫出按先序、中序和后序遍歷二叉樹歷二叉樹bt所得到的結(jié)點序列；所得到的結(jié)點序列；a.先序序列先序序列ab c e df h g i j

59、b.中序序列中序序列ec bhf dj i gab.后序序列后序序列ec hf j i g dba樹與森林【例題例題】從概念上講，樹，森林和二叉樹是三種不同的從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。么，并指出樹和二叉樹的主要區(qū)別。答：答：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵

60、樹的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。決樹和森林中的問題。樹和二叉樹的區(qū)別有樹和二叉樹的區(qū)別有3：一是二叉樹的度至多為：一是二叉樹的度至多為2，樹無此限制；二是，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分支的情況下，二叉樹有左右子樹之分，即使在只有一個分支的情況下， 也必須指也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個別書上允許為空）。不允許為空（個別書上允許為空）。10/15/20