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

數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)分享一些看法學(xué)了數(shù)據(jù)結(jié)構(gòu)的同學(xué)，不是被數(shù)據(jù)結(jié)構(gòu)傷的百孔千瘡，就是產(chǎn)生了心理陰影，太難太繞了。辛辛苦苦的學(xué)的差不多了吧，做程序的時(shí)候，好像根本用不上數(shù)據(jù)機(jī)構(gòu)一樣。此乃神物，花費(fèi)那么大的力氣學(xué)，到時(shí)候用不上豈不是太虧了。很多很多的文章很多很多的過來人，都告訴你，數(shù)據(jù)結(jié)構(gòu)很重要。老師上來就跟你說，這個(gè)很重要很重要。其實(shí)沒有幾個(gè)老師能跟你講清楚數(shù)據(jù)結(jié)構(gòu)到底是什么，以至于你學(xué)完了都不知所云。都不知道學(xué)完后怎么用，如何用，有沒有用。雖然他們都說有用，非常有用，那怎么個(gè)有用法，很少提及。甚至，在工作中怎么體現(xiàn)的也不曾提及。似乎數(shù)據(jù)結(jié)構(gòu)就是什么棧、鏈表、二叉樹、圖之類的。其實(shí)這些東西不是數(shù)據(jù)結(jié)構(gòu)。作為一個(gè)特別愛思考的人，沒有一個(gè)清晰的方向，學(xué)起來也是痛苦的，也是盲目的，雖然知道有用，但是還是如此?；蛘邠Q一種說法，清楚了自己學(xué)的東西，不僅學(xué)起來目標(biāo)明確，心情也爽快，同時(shí)效率還會(huì)很高。數(shù)據(jù)結(jié)構(gòu)+算法=程序其實(shí)，算法和數(shù)據(jù)結(jié)構(gòu)并非一個(gè)東西，數(shù)據(jù)結(jié)構(gòu)也不是鏈表之類的。這些都是錯(cuò)誤的信號(hào)。數(shù)據(jù)結(jié)構(gòu)是一門抽象的學(xué)科。這個(gè)確實(shí)如此。而且非常抽象。然而我們的學(xué)習(xí)，最好是從具體的開始東西開始，這樣學(xué)習(xí)效果更好。很少有人一開始抽象思維就很好的，抽象思維是通過大量的培養(yǎng)才得到的。實(shí)際上在潛意識(shí)里，抽象思維好的人總會(huì)無意識(shí)的將一個(gè)抽象模型關(guān)聯(lián)到他熟知的一個(gè)東西或者現(xiàn)象中。而這些聯(lián)系在講授或?qū)W習(xí)知識(shí)的時(shí)候，又忽略了。才導(dǎo)致抽象的東西，越來越抽象，或者說，我們沒有能夠?qū)⒊橄蟮臇|西足夠的具體化成一個(gè)實(shí)例。所以，你在學(xué)習(xí)的時(shí)候，盡量聯(lián)系實(shí)際中的案例來理解。數(shù)據(jù)結(jié)構(gòu)和算法，都是一種抽象的東西。其實(shí)就是人的思想。學(xué)好數(shù)據(jù)結(jié)構(gòu)和算法，就是去掌握那些別人已經(jīng)想出來的思想而已。并不是讓你去記住這些東西如何實(shí)現(xiàn)，怎么寫代碼怎么考試。而我們學(xué)到的各種數(shù)據(jù)結(jié)構(gòu)，是為了算法思路好完成邏輯而構(gòu)建的一些固定的模型，這些模型只是人為的一個(gè)規(guī)定而已。或者說，我們只是將這些比較不錯(cuò)的想法思路取一個(gè)名字，然后大家交流的時(shí)候，說起這個(gè)名字就知道了這個(gè)數(shù)據(jù)結(jié)構(gòu)等。例如我們學(xué)習(xí)鏈表結(jié)構(gòu)之類的，就是人家建立的一個(gè)固定的模型，或者叫做一個(gè)約定的操作方式。那么既然這些別人實(shí)現(xiàn)的都是一個(gè)典型的操作方式，那么必然有他的優(yōu)點(diǎn)，我們才需要學(xué)習(xí)的。然而你既然知道了天機(jī)，那么自然就可以去藐視天機(jī)，可以去創(chuàng)造，而不是一味的接受。既然是一種思想，你完全可以通過你自己的智慧去改善他的思想，這個(gè)就是思想更迭的過程。并不是后來人比前面的人聰明，而是因?yàn)樗驹诰奕说募绨蛏掀痫w的。國(guó)內(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í)思想的看法。算法則是一套思維的流程，以何種邏輯或者說是運(yùn)算的先后順序?qū)⒁粋€(gè)目標(biāo)實(shí)現(xiàn)。比如說，冒泡排序，最終的目標(biāo)是將一組數(shù)據(jù)拍好順序，至于如何實(shí)現(xiàn)，其實(shí)可以有多種，并不是唯一的。冒泡代表一種思想。你只需要弄懂這個(gè)思想的關(guān)鍵，如何一步步運(yùn)作到實(shí)現(xiàn)目標(biāo)的這個(gè)流程，就可以了?；谶@個(gè)流程，你可以使用另外的實(shí)現(xiàn)方式來做到需要的目標(biāo)，而不必拘泥于課本上的實(shí)現(xiàn)過程。否則，你永遠(yuǎn)都學(xué)不會(huì)算法。通常，算法都要用到數(shù)據(jù)結(jié)構(gòu)的各種模型，這些模型的建立，就是為了方便完成算法的邏輯流程的。正是這些數(shù)據(jù)結(jié)構(gòu)的存在，讓效率大大提升，或者讓操作過程更加簡(jiǎn)便。如果你能理解我說的這些，說明你有所領(lǐng)悟，而徹底明白，只是時(shí)間的問題了，前提是要繼續(xù)思考。當(dāng)你領(lǐng)悟到數(shù)據(jù)結(jié)構(gòu)和算法不再是書上那些東西，你就成功了一大半了。當(dāng)你的思維高于書上的東西，你學(xué)起來，那就簡(jiǎn)單多了。至少你不會(huì)再迷茫，而只是熟悉那些套路而已了。你改進(jìn)一個(gè)算法才成為可能，從此就不是死讀書的模式學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)了。數(shù)據(jù)結(jié)構(gòu)的研究?jī)?nèi)容03/02/202314【數(shù)據(jù)結(jié)構(gòu)的三個(gè)方面研究?jī)?nèi)容】具體來說，數(shù)據(jù)結(jié)構(gòu)包含三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)，數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的運(yùn)算（操作）。

數(shù)據(jù)的邏輯結(jié)構(gòu)（面向人類）

數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)（面向計(jì)算機(jī)）

數(shù)據(jù)的運(yùn)算（操作）：檢索、排序、插入、刪除、修改等

線性結(jié)構(gòu)

非線性結(jié)構(gòu)順序存儲(chǔ)鏈?zhǔn)酱鎯?chǔ)線性表?xiàng)ｊ?duì)列樹形結(jié)構(gòu)圖形結(jié)構(gòu)散列存儲(chǔ)索引存儲(chǔ)串及數(shù)組第一講緒論了解數(shù)據(jù)結(jié)構(gòu)有關(guān)概念的含義，特別是數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系；（重點(diǎn)）熟悉類C語言的書寫規(guī)范；了解計(jì)算算法時(shí)間復(fù)雜度的方法。（難點(diǎn)）03/02/202315數(shù)據(jù)結(jié)構(gòu)的定義按某種邏輯關(guān)系組織起來的一批數(shù)據(jù)（或稱帶結(jié)構(gòu)的數(shù)據(jù)元素的集合）應(yīng)用計(jì)算機(jī)語言并按一定的存儲(chǔ)表示方式把它們存儲(chǔ)在計(jì)算機(jī)的存儲(chǔ)器中，并在其上定義了一個(gè)運(yùn)算的集合。基本概念和術(shù)語【數(shù)據(jù)】是對(duì)信息的一種符號(hào)表示。是可以輸入計(jì)算機(jī)中，

能被計(jì)算機(jī)識(shí)別處理和輸出的一切符號(hào)集合。【數(shù)據(jù)元素】是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)

整體進(jìn)行考慮和處理。也稱為記錄?！緮?shù)據(jù)項(xiàng)】一個(gè)數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)組成。是數(shù)據(jù)不

可分割的最小單位?！緮?shù)據(jù)對(duì)象】是性質(zhì)相同的數(shù)據(jù)元素的集合。是數(shù)據(jù)的一個(gè)

子集。03/02/202317【數(shù)據(jù)結(jié)構(gòu)】相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)

元素的集合計(jì)算機(jī)如何解決問題03/02/202318問題機(jī)外表示處理要求邏輯結(jié)構(gòu)基本運(yùn)算數(shù)學(xué)模型存儲(chǔ)結(jié)構(gòu)編程實(shí)現(xiàn)實(shí)現(xiàn)建模求精研究數(shù)據(jù)結(jié)構(gòu)是為了幫計(jì)算機(jī)解決問題！四種基本邏輯結(jié)構(gòu)03/02/202319【集合】——數(shù)據(jù)元素間除了“同屬于一個(gè)集合”外，無其他關(guān)系。【線性結(jié)構(gòu)】——

1對(duì)1的關(guān)系比如線性表、棧、隊(duì)列。【樹形結(jié)構(gòu)】——

1對(duì)多的關(guān)系比如樹?！緢D形結(jié)構(gòu)】——多對(duì)多的關(guān)系比如圖。算法與數(shù)據(jù)結(jié)構(gòu)算法與數(shù)據(jù)結(jié)構(gòu)關(guān)系密切選擇的數(shù)據(jù)結(jié)構(gòu)是否恰當(dāng)直接影響算法的效率；而數(shù)據(jù)結(jié)構(gòu)的優(yōu)劣由算法的執(zhí)行來體現(xiàn)。“算法+數(shù)據(jù)結(jié)構(gòu)=程序”算法!=程序算法是供人閱讀的，程序是讓機(jī)器執(zhí)行的算法用計(jì)算機(jī)語言實(shí)現(xiàn)時(shí)就是程序程序不具有算法的有窮性算法的概念算法是解決某個(gè)特定問題的求解步驟的描述。算法在計(jì)算機(jī)中表現(xiàn)為指令的有限序列，每條指令表示一個(gè)或多個(gè)操作。計(jì)算機(jī)對(duì)數(shù)據(jù)的操作可以分為數(shù)值性和非數(shù)值性兩種類型。在數(shù)值性操作中主要進(jìn)行的是算術(shù)運(yùn)算；而在非數(shù)值性操作中主要進(jìn)行的是檢索、排序、插入、刪除等等。程序不等于算法：計(jì)算機(jī)程序是算法的具體實(shí)現(xiàn)。03/02/202321（1）有窮性：一個(gè)算法必須在執(zhí)行有窮步之后結(jié)束。（2）確定性：算法中的每一步，必須有確切的含義，在他人理解時(shí)不會(huì)產(chǎn)生二義性。（3）可行性：算法中描述的每一步操作都可以通過已有的基本操作執(zhí)行有限次實(shí)現(xiàn)。（4）輸入：一個(gè)算法應(yīng)該有零個(gè)或多個(gè)輸入。（5）輸出：一個(gè)算法應(yīng)該有一個(gè)或多個(gè)輸出。這里所說的輸出是指與輸入有某種特定關(guān)系的量。算法的性質(zhì)算法設(shè)計(jì)的要求正確性（四個(gè)境界）沒有語法錯(cuò)誤對(duì)于合法的輸入數(shù)據(jù)能夠產(chǎn)生滿足要求的輸出對(duì)于非法的輸入數(shù)據(jù)能夠得出滿足規(guī)格說明的結(jié)果對(duì)于任何測(cè)試數(shù)據(jù)都有滿足要求的輸出結(jié)果可讀性：便于閱讀、理解和交流健壯性：不合法數(shù)據(jù)也能合理處理時(shí)間效率高和存儲(chǔ)量低03/02/202323算法效率的度量方法事后統(tǒng)計(jì)方法通過設(shè)計(jì)好的測(cè)試程序和數(shù)據(jù)，利用計(jì)算機(jī)測(cè)量其運(yùn)行時(shí)間。缺陷：需要先編寫程序；和計(jì)算機(jī)軟硬件相關(guān)；和測(cè)試數(shù)據(jù)相關(guān)。事前分析估算方法（我們的選擇）依據(jù)統(tǒng)計(jì)方法對(duì)算法進(jìn)行估算。m=f(n)，m是語句總的執(zhí)行次數(shù)，n是輸入的規(guī)模。和問題輸入規(guī)模相關(guān)，獨(dú)立于程序設(shè)計(jì)語言和計(jì)算機(jī)軟硬件

03/02/202324算法時(shí)間復(fù)雜度03/02/202325在進(jìn)行算法分析時(shí)，語句的總執(zhí)行次數(shù)T(n)是關(guān)于問題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，用“大O記法”記作：T(n)=O(f(n))。由此得到的T(n)的數(shù)量級(jí)叫“大O階”。它表示隨問題規(guī)模n的增大，算法執(zhí)行時(shí)間增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱作算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。其中f(n)是問題規(guī)模n的某個(gè)函數(shù)。一般情況下，T(n)增長(zhǎng)越慢，算法越優(yōu)。大O階的數(shù)學(xué)定義

當(dāng)n→∞時(shí)，有f(n)/g(n)=常數(shù)≠0，則稱函數(shù)f(n)與g(n)同階,或者說，f(n)與g(n)同一個(gè)數(shù)量級(jí)，記作

f(n)=O(g(n))

稱上式為算法的時(shí)間復(fù)雜度,或稱該算法的時(shí)間復(fù)雜度為O(g(n))。其中,n為問題的規(guī)模(大小)的量度。若lim(f(n)/g(n))=lim((2n3+3n2+2n+1)/n3)

=2n→∞n→∞則算法的時(shí)間復(fù)雜度為O(n3)算法空間復(fù)雜度03/02/202327

算法的空間復(fù)雜度通過計(jì)算算法所需的存儲(chǔ)空間實(shí)現(xiàn)，算法空間復(fù)雜度的計(jì)算公式記作：S(n)=O(f(n))，其中，n為問題的規(guī)模，f(n)為語句關(guān)于n所占存儲(chǔ)空間的函數(shù)。

我們主要討論時(shí)間復(fù)雜度問題。例題解析【例1】數(shù)據(jù)元素之間的關(guān)系在計(jì)算機(jī)中有幾種表示方法？各有什么特點(diǎn)？答：四種表示方法（1）順序存儲(chǔ)方式。數(shù)據(jù)元素順序存放，每個(gè)存儲(chǔ)結(jié)點(diǎn)只含一個(gè)元素。存儲(chǔ)位置反映數(shù)據(jù)元素間的邏輯關(guān)系。存儲(chǔ)密度大，但有些操作（如插入、刪除）效率較差。（2）鏈?zhǔn)酱鎯?chǔ)方式。每個(gè)存儲(chǔ)結(jié)點(diǎn)除包含數(shù)據(jù)元素信息外還包含一組（至少一個(gè)）指針。指針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求存儲(chǔ)空間連續(xù)，便于動(dòng)態(tài)操作（如插入、刪除等），但存儲(chǔ)空間開銷大（用于指針），另外不能折半查找等。（3）索引存儲(chǔ)方式。除數(shù)據(jù)元素存儲(chǔ)在一地址連續(xù)的內(nèi)存空間外，尚需建立一個(gè)索引表，索引表中索引指示存儲(chǔ)結(jié)點(diǎn)的存儲(chǔ)位置（下標(biāo)）或存儲(chǔ)區(qū)間端點(diǎn)（下標(biāo)），兼有靜態(tài)和動(dòng)態(tài)特性。（4）散列存儲(chǔ)方式。通過散列函數(shù)和解決沖突的方法，將關(guān)鍵字散列在連續(xù)的有限的地址空間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的存儲(chǔ)地址，這種存儲(chǔ)方式稱為散列存儲(chǔ)。其特點(diǎn)是存取速度快，只能按關(guān)鍵字隨機(jī)存取，不能順序存取，也不能折半存取。03/02/202328例題解析【例2】有下列運(yùn)行時(shí)間函數(shù)：（1）T1(n)=1000;（2）T2(n)=n2+1000n;（3）T3(n)=3n3+100n2+n+1;分別寫出相應(yīng)的大O表示的運(yùn)算時(shí)間答：(1)O(1)(2)O(n2)(3)O(n3)03/02/202329第二講線性表線性結(jié)構(gòu)的定義和特點(diǎn)在數(shù)據(jù)元素的非空有限集中，有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，并且所有結(jié)點(diǎn)只有一個(gè)直接前趨和一個(gè)直接后繼。簡(jiǎn)言之，線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是

一對(duì)一。線性結(jié)構(gòu)包括線性表、堆棧、隊(duì)列、字符串、數(shù)組等等，其中，最簡(jiǎn)單、最常用的是線性表。線性表的存儲(chǔ)方法順序存儲(chǔ)：邏輯上相鄰物理上一定相鄰鏈?zhǔn)酱鎯?chǔ)：邏輯上相鄰物理上不一定相鄰順序表順序表——線性表的順序存儲(chǔ)表示順序存儲(chǔ)——用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組來實(shí)現(xiàn)。（邏輯上相鄰物理上一定相鄰）

LOC(ai

)=LOC(a1)+(i-1)len

（a1為首元素，len為單個(gè)元素占用空間長(zhǎng)度）順序存儲(chǔ)的優(yōu)點(diǎn)可以隨機(jī)存取表中任一元素O(1)；存儲(chǔ)空間使用緊湊順序存儲(chǔ)的缺點(diǎn)在插入元素時(shí)平均需要移動(dòng)n/2個(gè)元素，刪除某一元素時(shí)，平均需要移動(dòng)n-1/2個(gè)元素。算法的平均時(shí)間復(fù)雜度為O(n)預(yù)先分配空間需按最大空間分配，利用不充分;表容量難以擴(kuò)充03/02/202331鏈表鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)特點(diǎn)用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息

鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)：結(jié)點(diǎn)空間可以動(dòng)態(tài)申請(qǐng)和釋放；數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)元素。鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的缺點(diǎn)：每個(gè)結(jié)點(diǎn)的指針域需額外占用存儲(chǔ)空間。當(dāng)數(shù)據(jù)域所占字節(jié)不多時(shí)，指針域所占存儲(chǔ)空間的比重顯得很大。鏈表是非隨機(jī)存取結(jié)構(gòu)。對(duì)任一結(jié)點(diǎn)的操作都要從頭指針依鏈查找該結(jié)點(diǎn)，這增加了算法的復(fù)雜度O（n）不便于在表尾插入元素：需遍歷整個(gè)表才能找到位置。03/02/202332例題解析【例1】說明在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針與頭結(jié)點(diǎn)之間的根本區(qū)別。答：在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，頭指針指鏈表的指針，若鏈表有頭結(jié)點(diǎn)則是鏈表的頭結(jié)點(diǎn)的指針，頭指針具有標(biāo)識(shí)作用，故常用頭指針冠以鏈表的名字。頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義（當(dāng)然有些情況下也可存放鏈表的長(zhǎng)度、用做監(jiān)視哨等等），有頭結(jié)點(diǎn)后，對(duì)在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一結(jié)點(diǎn)，其操作與對(duì)其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。03/02/202333例題解析

【例2】設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試設(shè)計(jì)一個(gè)算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。答：voidInsert_SqList(SqListva,intx)/*把x插入遞增有序表va中*/{inti;if(va.length>MAXSIZE)return;for(i=va.length-1;va.elem[i]>x&&i>=0;i--)va.elem[i+1]=va.elem[i];va.elem[i+1]=x;va.length++;}/*Insert_SqList*/03/02/202334#defineMAXSIZE100typedef

struct{

ElemType*elem;

intlength;}SqList；例題解析【例3】設(shè)單鏈表結(jié)點(diǎn)指針域?yàn)閚ext，試寫出刪除鏈表中指針p所指結(jié)點(diǎn)的直接后繼的C語言語句。答： q=p->next; p->next=q->next; free(q);03/02/202335例題解析【例4】設(shè)單鏈表中某指針p所指結(jié)點(diǎn)（即p結(jié)點(diǎn)）的數(shù)據(jù)域?yàn)閐ata，鏈指針域?yàn)閚ext，請(qǐng)寫出在p結(jié)點(diǎn)之前插入s結(jié)點(diǎn)的操作。答：

設(shè)單鏈表的頭結(jié)點(diǎn)的頭指針為head,且pre=head；

while(pre->next!=p)pre=pre->next;s->next=p;pre->next=s;03/02/202336例題解析【例5】試編寫在帶頭結(jié)點(diǎn)的單鏈表中刪除（一個(gè)）最小值結(jié)點(diǎn)的算法。voiddelete（Linklist&L）答：[題目分析]本題要求在單鏈表中刪除最小值結(jié)點(diǎn)。單鏈表中刪除結(jié)點(diǎn)，為使結(jié)點(diǎn)刪除后不出現(xiàn)“斷鏈”，應(yīng)知道被刪結(jié)點(diǎn)的前驅(qū)。而“最小值結(jié)點(diǎn)”是在遍歷整個(gè)鏈表后才能知道。所以算法應(yīng)首先遍歷鏈表，求得最小值結(jié)點(diǎn)及其前驅(qū)。遍歷結(jié)束后再執(zhí)行刪除操作。

voiddelete（LinkedList&L）{∥L是帶頭結(jié)點(diǎn)的單鏈表p=L->next；∥p為工作指針。指向待處理的結(jié)點(diǎn)。假定鏈表非空。

pre=L；∥pre指向最小值結(jié)點(diǎn)的前驅(qū)。

q=p；∥q指向最小值結(jié)點(diǎn)，初始假定第一元素結(jié)點(diǎn)是最小值結(jié)點(diǎn)。

while（p->next!=null）{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值結(jié)點(diǎn)

p=p->next；∥指針后移。

}pre->next=q->next；∥從鏈表上刪除最小值結(jié)點(diǎn)

free（q）；∥釋放最小值結(jié)點(diǎn)空間}∥結(jié)束算法delete。03/02/202337例題解析【例6】一元稀疏多項(xiàng)式以循環(huán)單鏈表按降冪排列，結(jié)點(diǎn)有三個(gè)域，系數(shù)域coef，指數(shù)域exp和指針域next；現(xiàn)對(duì)鏈表求一階導(dǎo)數(shù)，鏈表的頭指針為ha，頭結(jié)點(diǎn)的exp域?yàn)楱C1。

voidderivative(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)________);}}03/02/202338(1)pa!=ha∥或pa->exp!=-1(2)pa->exp==0∥若指數(shù)為0，即本項(xiàng)為常數(shù)項(xiàng)(3)q->next=pa->next∥刪常數(shù)項(xiàng)(4)q->next∥取下一元素(5)=pa->coef*pa->exp(6)--∥指數(shù)項(xiàng)減1(7)pa∥前驅(qū)后移,或q->next(8)pa->next∥取下一元素第三講棧和隊(duì)列棧限定僅在表尾進(jìn)行插入和刪除的線性表，把這個(gè)表尾稱為棧頂。特點(diǎn)后進(jìn)先出(LIFO表)棧的存儲(chǔ)方法棧的順序存儲(chǔ)——順序棧棧的鏈?zhǔn)酱鎯?chǔ)——鏈棧03/02/202339關(guān)于棧要求掌握的內(nèi)容03/02/202340

棧的基本概念：LIFO

棧的存儲(chǔ)棧的應(yīng)用（了解）順序棧（熟練掌握）鏈棧（熟練掌握）初始化取棧頂入棧出棧判斷?？?/p>

棧初始化取棧頂入棧出棧判斷?？贞?duì)列定義03/02/202341

隊(duì)列的定義隊(duì)列：線性表

(queue)特點(diǎn)：先進(jìn)先出(FIFO結(jié)構(gòu))。隊(duì)尾隊(duì)頭下圖是隊(duì)列的示意圖：

a1

a2

…

an出隊(duì)入隊(duì)隊(duì)頭隊(duì)尾當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。表尾稱為隊(duì)尾(rear)表頭稱為隊(duì)頭(front)插入元素稱為入隊(duì)刪除元素稱為出隊(duì)限定在表的一端插入、另一端刪除。順序隊(duì)列的假溢出問題03/02/202342

在順序隊(duì)列中，當(dāng)尾指針已經(jīng)指向了隊(duì)列的最后一個(gè)位置即數(shù)組上界時(shí)，若再有元素入隊(duì)，就會(huì)發(fā)生“溢出”。

“假溢出”——隊(duì)列的存儲(chǔ)空間未滿，卻發(fā)生了溢出。rearfrontJ1

J2

J3

J4

rearfrontJ3

J4

(1)、平移元素：把元素平移到隊(duì)列的首部。效率低。

解決“假溢出”的問題有兩種可行的方法：(2)、將新元素插入到第一個(gè)位置上，構(gòu)成循環(huán)隊(duì)列，入隊(duì)和出隊(duì)仍按“先進(jìn)先出”的原則進(jìn)行。

操作效率、空間利用率高。rearfrontJ3

J4

frontrearJ3

J4

循環(huán)隊(duì)列03/02/202343隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=maxsize)隊(duì)列長(zhǎng)度：L=（N＋rear－front）%NJ2J3

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向?qū)嵲兀硪恢赶蚩臻e元素。

問2：在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？n-1個(gè)5問1：左圖中隊(duì)列長(zhǎng)度L=？例題解析【例1】一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？答： 43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)； 12345的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。03/02/202344例題解析【例2】如果一個(gè)棧的輸入序列為123456，能否得到435612和135426的出棧序列？答： 435612中到了12順序不能實(shí)現(xiàn)； 135426可以實(shí)現(xiàn)。03/02/202345例題解析【例3】一個(gè)棧的輸入序列為123，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？答：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；

合計(jì)有5種可能性。03/02/202346例題解析【例4】簡(jiǎn)述順序存儲(chǔ)隊(duì)列的假溢出的避免方法及隊(duì)列滿和空的條件。答：設(shè)順序存儲(chǔ)隊(duì)列用一維數(shù)組q[m]表示，其中m為隊(duì)列中元素個(gè)數(shù)，隊(duì)列中元素在向量中的下標(biāo)從0到m-1。設(shè)隊(duì)頭指針為front，隊(duì)尾指針是rear，約定front指向隊(duì)頭元素的前一位置，rear指向隊(duì)尾元素。當(dāng)front等于-1時(shí)隊(duì)空，rear等于m-1時(shí)為隊(duì)滿。由于隊(duì)列的性質(zhì)（“刪除”在隊(duì)頭而“插入”在隊(duì)尾），所以當(dāng)隊(duì)尾指針rear等于m-1時(shí)，若front不等于-1，則隊(duì)列中仍有空閑單元，所以隊(duì)列并不是真滿。這時(shí)若再有入隊(duì)操作，會(huì)造成假“溢出”。其解決辦法有二，一是將隊(duì)列元素向前“平移”（占用0至rear-front-1）；二是將隊(duì)列看成首尾相連，即循環(huán)隊(duì)列（0..m-1）。在循環(huán)隊(duì)列下，仍定義front=rear時(shí)為隊(duì)空，而判斷隊(duì)滿則用兩種辦法，一是用“犧牲一個(gè)單元”，即rear+1=front（準(zhǔn)確記是（rear+1）%m=front，m是隊(duì)列容量）時(shí)為隊(duì)滿。另一種解法是“設(shè)標(biāo)記”方法，如設(shè)標(biāo)記tag，tag等于0情況下，若刪除時(shí)導(dǎo)致front=rear為隊(duì)空；tag=1情況下，若因插入導(dǎo)致front=rear則為隊(duì)滿。03/02/202347第四講串和數(shù)組【例1】填空題：1.空格串是指_____________，其長(zhǎng)度等于_____________?！敬鸢浮浚?）由空格字符（ASCII值32）所組成的字符串（2）空格個(gè)數(shù)2．組成串的數(shù)據(jù)元素只能是_____________。【答案】字符【解析】串是一種特殊的線性表，其特殊性在于串中的元素只能是字符型數(shù)據(jù)。3．兩個(gè)字符串相等的充分必要條件是_____________?！敬鸢浮?jī)纱拈L(zhǎng)度相等且兩串中對(duì)應(yīng)位置上的字符也相等。4．一個(gè)字符串中_____________稱為該串的子串?！敬鸢浮咳我鈧€(gè)連續(xù)的字符組成的子序列03/02/202348例題解析【例2】設(shè)計(jì)一個(gè)算法，將字符串s的全部字符復(fù)制到字符串t中，不能利用strcpy函數(shù)。答：【算法分析】要實(shí)現(xiàn)兩個(gè)字符串的復(fù)制，實(shí)質(zhì)為兩個(gè)字符數(shù)組之間的復(fù)制，在復(fù)制時(shí)，一個(gè)字符一個(gè)字符的復(fù)制，直到遇到'\0'，'\0'一同復(fù)制過去，'\0'之后的字符不復(fù)制?！舅惴ㄔ创a】voidcopy(chars[],chart[]){inti;for(i=0;s[i]!='\0';i++)t[i]=s[i];t[i]=s[i];}03/02/202349例題解析【例3】設(shè)有一個(gè)二維數(shù)組A[m][n]，假設(shè)A[0][0]存放位置在644，A[2][2]存放位置在676，每個(gè)元素占一個(gè)空間，問A[3][3]存放在什么位置？答：設(shè)數(shù)組元素A[i][j]存放在起始地址為L(zhǎng)oc（i,j）的存儲(chǔ)單元中?！週oc（2,2）=Loc（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.03/02/202350例題解析【例4】設(shè)有一個(gè)nn的對(duì)稱矩陣A，為了節(jié)約存儲(chǔ)，可以只存對(duì)角線及對(duì)角線以上的元素，或者只存對(duì)角線或?qū)蔷€以下的元素。前者稱為上三角矩陣，后者稱為下三角矩陣。我們把它們按行存放于一個(gè)一維數(shù)組B中，稱之為對(duì)稱矩陣A的壓縮存儲(chǔ)方式。試問：（1）存放對(duì)稱矩陣A上三角部分或下三角部分的一維數(shù)組B有多少元素？（2）若在一維數(shù)組B中從0號(hào)位置開始存放，則對(duì)稱矩陣中的任一元素aij在只存下三角部分的情形下應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。答：（1）數(shù)組B共有1＋2+3++n=（n+1）*n/2個(gè)元素。（2）只存下三角部分時(shí)，若ij，則數(shù)組元素A[i][j]前面有i-1行（1i-1，第0行第0列不算），第1行有1個(gè)元素，第2行有2個(gè)元素，，第i-1行有i-1個(gè)元素。在第i行中，第j號(hào)元素排在第j個(gè)元素位置，因此，數(shù)組元素A[i][j]在數(shù)組B中的存放位置為：1+2++（i-1）+j=（i-1）*i/2+j若i<j，數(shù)組元素A[i][j]在數(shù)組B中沒有存放，可以找它的對(duì)稱元素A[j][i]。在數(shù)組B的第（j-1）*j/2+i位置中找到。如果第0行第0列也計(jì)入，數(shù)組B從0號(hào)位置開始存放，則數(shù)組元素A[i][j]在數(shù)組B中的存放位置可以改為：當(dāng)ij時(shí)，=i*（i+1）/2+j；當(dāng)i<j時(shí)，=j*（j+1）/2+i。03/02/202351第五講樹03/02/202352二叉樹的定義定義：是n（n≥0）個(gè)結(jié)點(diǎn)的有限集合，由一個(gè)根結(jié)點(diǎn)以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。邏輯結(jié)構(gòu)：一對(duì)二（1：2）

基本特征:每個(gè)結(jié)點(diǎn)最多只有兩棵子樹（不存在度大于2的結(jié)點(diǎn)）；左子樹和右子樹次序不能顛倒（有序樹）。滿二叉樹完全二叉樹二叉樹的性質(zhì)（能證明嗎）03/02/202353【性質(zhì)1】在二叉樹的第i

層上至多有2i-1個(gè)結(jié)點(diǎn)(i≥1)?！拘再|(zhì)2】深度為k的二叉樹至多有2k

-1個(gè)結(jié)點(diǎn)（k≥1）?！拘再|(zhì)3】對(duì)任何一棵二叉樹T，如果其葉子數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。（葉子數(shù)＝結(jié)點(diǎn)的度為2的結(jié)點(diǎn)數(shù)＋1）【性質(zhì)4】具有n

個(gè)結(jié)點(diǎn)的完全二叉樹的深度為

log2n+1或者log2(n+1)?！拘再|(zhì)5】n個(gè)結(jié)點(diǎn)的完全二叉樹，結(jié)點(diǎn)按層次編號(hào)有：

1)i的雙親是，如果i=1時(shí)為根（無雙親）；

2)i的左孩子是2i，如果2i>n，則無左孩子；

3)i的右孩子是2i+1，如果2i+1>n則無右孩子。例題解析1．深度為H的完全二叉樹至少有_____________個(gè)結(jié)點(diǎn)；至多有_____________個(gè)結(jié)點(diǎn)；H和結(jié)點(diǎn)總數(shù)N之間的關(guān)系是_____________?！敬鸢浮浚?）2H-1 （2）2H-1 （3）H=log2N+12．一棵有n個(gè)結(jié)點(diǎn)的滿二叉樹有_____________個(gè)度為1的結(jié)點(diǎn)，有_____________個(gè)分支（非終端）結(jié)點(diǎn)和_____________個(gè)葉子，該滿二叉樹的深度為_____________?！敬鸢浮浚?）0 （2）(n-1）/2 （3）(n+1）/2 （4）log2n

+13．對(duì)于一個(gè)具有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)它為一棵_____________時(shí)，具有最小高度，當(dāng)它為一棵_____________時(shí)，具有最大高度。【答案】（1）完全二叉樹 （2）單支樹，樹中任一結(jié)點(diǎn)（除最后一個(gè)結(jié)點(diǎn)是葉子外），只有左子女或只有右子女。4．已知二叉樹有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹的總結(jié)點(diǎn)數(shù)至少是_____________?！敬鸢浮?9【解析】在二叉樹中，N0=N2+1，所以，有50個(gè)葉子結(jié)點(diǎn)的二叉樹，有49個(gè)度為2的結(jié)點(diǎn)。若要使該二叉樹的結(jié)點(diǎn)數(shù)最少，度為1的結(jié)點(diǎn)應(yīng)為0個(gè)，即總結(jié)點(diǎn)數(shù)N=N0+N1+N2=99。03/02/202354二叉樹的存儲(chǔ)（一）03/02/202355二叉樹存儲(chǔ)方法有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)二叉樹順序存儲(chǔ)結(jié)構(gòu)完全二叉樹：用一組地址連續(xù)的存儲(chǔ)單元依次自上而下、自左至右存儲(chǔ)結(jié)點(diǎn)元素，即將編號(hào)為i

的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組中下標(biāo)為

i

的分量中（不用下標(biāo)為0存儲(chǔ)單元）。此順序存儲(chǔ)結(jié)構(gòu)僅適用于完全二叉樹不是完全二叉樹怎么辦？一律轉(zhuǎn)為完全二叉樹！方法很簡(jiǎn)單，將各層空缺處統(tǒng)統(tǒng)補(bǔ)上“虛結(jié)點(diǎn)”，其內(nèi)容為空。缺點(diǎn)：①浪費(fèi)空間；②插入、刪除不便二叉樹的存儲(chǔ)（二）03/02/202356二叉樹鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

存儲(chǔ)方式

一般從根結(jié)點(diǎn)開始存儲(chǔ)，用二叉鏈表來表示。（相應(yīng)地，訪問樹中結(jié)點(diǎn)時(shí)也只能從根開始）

二叉樹結(jié)點(diǎn)的特點(diǎn)二叉樹是非線性結(jié)構(gòu)，適合用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)lchilddatarchild結(jié)點(diǎn)結(jié)構(gòu)datarchildlchilddata

parentlchildrchild二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義：typedefstruct

BiTNode{

TElemTypedata; structBiTNode

*lchild,*rchild;}BiTNode,*BiTree;二叉樹遍歷03/02/202357若規(guī)定先左后右，則只有前三種情況：DLR——

前（根）序遍歷，LDR——

中（根）序遍歷，LRD——

后（根）序遍歷根據(jù)遍歷順序確定一棵二叉樹已知二叉樹的前序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的后序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的前序序列和后序序列，不能唯一確定一棵二叉樹。例題解析03/02/202358

設(shè)二叉樹bt的一種存儲(chǔ)結(jié)構(gòu)如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild

其中bt為樹根結(jié)點(diǎn)指針,lchild、rchild分別為結(jié)點(diǎn)的左、右孩子指針域,在這里使用結(jié)點(diǎn)編號(hào)作為指針域值,0表示指針域?yàn)榭?data為結(jié)點(diǎn)的數(shù)據(jù)域。請(qǐng)完成下列各題：(1)畫出二叉樹的樹形表示；(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；例題解析（續(xù)）03/02/20235900237580101jhfdbacegi000940000012345678910lchilddatarchild(1)畫出二叉樹的樹形表示；因?yàn)榈?號(hào)結(jié)點(diǎn)不是任何結(jié)點(diǎn)的孩子結(jié)點(diǎn)，該結(jié)點(diǎn)必定是根結(jié)點(diǎn)，再根據(jù)和結(jié)點(diǎn)左、右指針域的值很容易得到該二叉樹的樹形表示為

abgfdcehij例題解析（續(xù)）03/02/20236000237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；a.先序序列abcedfhgij例題解析（續(xù)）03/02/20236100237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；a.先序序列abcedfhgijb.中序序列ecbhfdjiga例題解析（續(xù)）03/02/20236200237580101jhfdbacegi000940000012345678910lchilddatarchildabgfdcehij(2)寫出按先序、中序和后序遍歷二叉樹bt所得到的結(jié)點(diǎn)序列；a.先序序列abcedfhgijb.中序序列ecbhfdjigab.后序序列echfjigdba樹與森林【例題】從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構(gòu)，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。答：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（樹是森林的特例，即森林中只有一棵樹的特殊情況）可用二叉樹惟一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有3：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個(gè)分支的情況下，也必須指出是左子樹還是右子樹，樹無此限制；三是二叉樹允許為空，樹一般不允許為空（個(gè)別書上允許為空）。03/02/202363例題解析【例題】已知一棵二叉樹的中序序列和后序序列分別為GLDHBEIACJFK和LGHDIEBJKFCA（1）給出這棵二叉樹；（2）轉(zhuǎn)換為對(duì)應(yīng)的森林。答：03/02/202364ACBHJDFGKLEIEABLDGHIJFCK例題解析【例題】假設(shè)一棵二叉樹的層次次序（按層次遞增順序排列，同一層次自左向右）為ABECFGDHI,中序序列為BCDAFEHIG。請(qǐng)畫出該二叉樹，并將其轉(zhuǎn)換為對(duì)應(yīng)的森林。答：按層次遍歷，第一個(gè)結(jié)點(diǎn)（若樹不空）為根，該結(jié)點(diǎn)在中序序列中把序列分成左右兩部分：左子樹和右子樹。若左子樹不空，層次序列中第二個(gè)結(jié)點(diǎn)為左子樹的根；若右子樹為空，則層次序列中第三個(gè)結(jié)點(diǎn)為右子樹的根。對(duì)右子樹也作類似的分析。層次序列的特點(diǎn)是，從左到右每個(gè)結(jié)點(diǎn)或是當(dāng)前情況下子樹的根或是葉子。03/02/202365IADEBFCGHECABDIGHF二叉樹的應(yīng)用：Huffman樹03/02/202366Huffman樹的應(yīng)用帶權(quán)路徑計(jì)算WPL帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱作赫夫曼樹具有相同帶權(quán)結(jié)點(diǎn)的哈夫曼樹不惟一滿二叉樹不一定是哈夫曼樹哈夫曼樹的結(jié)點(diǎn)的度數(shù)為0或2，沒有度為1的結(jié)點(diǎn)。包含

n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中共有2n–1個(gè)結(jié)點(diǎn)。Huffman樹的構(gòu)造過程給定權(quán)值集w={2,3,4,7,8,9},試構(gòu)造關(guān)于w的的一顆哈夫曼樹，并求其帶權(quán)路徑長(zhǎng)度WPL。03/02/2023672347894789235789235499235497815Huffman樹的構(gòu)造過程03/02/202368給定權(quán)值集w={2,3,4,7,8,9},試構(gòu)造關(guān)于w的的一顆哈夫曼樹，并求其帶權(quán)路徑長(zhǎng)度WPL。78159235491878159235491833WPL=(2+3)×4+4×3+9×2+(7+8)×2=80【例題】T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479Huffman編碼過程T={(a,2),(b,3),(c,4),(d,7),(e,9)}為帶權(quán)字符集，試構(gòu)造關(guān)于該字符集的一顆哈夫曼樹，求其加權(quán)路徑長(zhǎng)度WPL、T中每個(gè)字符的哈曼夫編碼和哈夫曼編碼的平均長(zhǎng)度。23479235T={(a,2),(b,3),(c,4),(d,7),(e,9)}