數(shù)據(jù)結構學習分享

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

數(shù)據(jù)的邏輯結構（面向人類）

數(shù)據(jù)的存儲結構（面向計算機）

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

線性結構

非線性結構順序存儲鏈式存儲線性表棧隊列樹形結構圖形結構散列存儲索引存儲串及數(shù)組第一講緒論了解數(shù)據(jù)結構有關概念的含義，特別是數(shù)據(jù)的邏輯結構和存儲結構之間的關系；（重點）熟悉類C語言的書寫規(guī)范；了解計算算法時間復雜度的方法。（難點）03/02/202315數(shù)據(jù)結構的定義按某種邏輯關系組織起來的一批數(shù)據(jù)（或稱帶結構的數(shù)據(jù)元素的集合）應用計算機語言并按一定的存儲表示方式把它們存儲在計算機的存儲器中，并在其上定義了一個運算的集合?；靖拍詈托g語【數(shù)據(jù)】是對信息的一種符號表示。是可以輸入計算機中，

能被計算機識別處理和輸出的一切符號集合?！緮?shù)據(jù)元素】是數(shù)據(jù)的基本單位，在計算機中通常作為一個

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

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

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

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

1對1的關系比如線性表、棧、隊列。【樹形結構】——

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

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

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

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

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

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

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

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

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

LOC(ai

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

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

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

【例2】設順序表va中的數(shù)據(jù)元素遞增有序。試設計一個算法，將x插入到順序表的適當位置上，以保持該表的有序性。答：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】設單鏈表結點指針域為next，試寫出刪除鏈表中指針p所指結點的直接后繼的C語言語句。答： q=p->next; p->next=q->next; free(q);03/02/202335例題解析【例4】設單鏈表中某指針p所指結點（即p結點）的數(shù)據(jù)域為data，鏈指針域為next，請寫出在p結點之前插入s結點的操作。答：

設單鏈表的頭結點的頭指針為head,且pre=head；

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

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

pre=L；∥pre指向最小值結點的前驅。

q=p；∥q指向最小值結點，初始假定第一元素結點是最小值結點。

while（p->next!=null）{if（p->next->data<q->data）{pre=p；q=p->next；}∥查最小值結點

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

}pre->next=q->next；∥從鏈表上刪除最小值結點

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

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，即本項為常數(shù)項(3)q->next=pa->next∥刪常數(shù)項(4)q->next∥取下一元素(5)=pa->coef*pa->exp(6)--∥指數(shù)項減1(7)pa∥前驅后移,或q->next(8)pa->next∥取下一元素第三講棧和隊列棧限定僅在表尾進行插入和刪除的線性表，把這個表尾稱為棧頂。特點后進先出(LIFO表)棧的存儲方法棧的順序存儲——順序棧棧的鏈式存儲——鏈棧03/02/202339關于棧要求掌握的內容03/02/202340

棧的基本概念：LIFO

棧的存儲棧的應用（了解）順序棧（熟練掌握）鏈棧（熟練掌握）初始化取棧頂入棧出棧判斷棧空

棧初始化取棧頂入棧出棧判斷?？贞犃卸x03/02/202341

隊列的定義隊列：線性表

(queue)特點：先進先出(FIFO結構)。隊尾隊頭下圖是隊列的示意圖：

a1

a2

…

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

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

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

J2

J3

J4

rearfrontJ3

J4

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

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

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

J4

frontrearJ3

J4

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

J1

J4

J5frontrear

選用空閑單元法：即front和rear之一指向實元素，另一指向空閑元素。

問2：在具有n個單元的循環(huán)隊列中，隊滿時共有多少個元素？n-1個5問1：左圖中隊列長度L=？例題解析【例1】一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現(xiàn)嗎？12345的輸出呢？答： 43512不可能實現(xiàn)，主要是其中的12順序不能實現(xiàn)； 12345的輸出可以實現(xiàn)，只需壓入一個立即彈出一個即可。03/02/202344例題解析【例2】如果一個棧的輸入序列為123456，能否得到435612和135426的出棧序列？答： 435612中到了12順序不能實現(xiàn)； 135426可以實現(xiàn)。03/02/202345例題解析【例3】一個棧的輸入序列為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；

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

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

層上至多有2i-1個結點(i≥1)?！拘再|2】深度為k的二叉樹至多有2k

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

個結點的完全二叉樹的深度為

log2n+1或者log2(n+1)。【性質5】n個結點的完全二叉樹，結點按層次編號有：

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

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

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

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

的結點元素存儲在一維數(shù)組中下標為

i

的分量中（不用下標為0存儲單元）。此順序存儲結構僅適用于完全二叉樹不是完全二叉樹怎么辦？一律轉為完全二叉樹！方法很簡單，將各層空缺處統(tǒng)統(tǒng)補上“虛結點”，其內容為空。缺點：①浪費空間；②插入、刪除不便二叉樹的存儲（二）03/02/202356二叉樹鏈式存儲結構

存儲方式

一般從根結點開始存儲，用二叉鏈表來表示。（相應地，訪問樹中結點時也只能從根開始）

二叉樹結點的特點二叉樹是非線性結構，適合用鏈式存儲結構lchilddatarchild結點結構datarchildlchilddata

parentlchildrchild二叉樹結點數(shù)據(jù)類型定義：typedefstruct

BiTNode{

TElemTypedata; structBiTNode

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

前（根）序遍歷，LDR——

中（根）序遍歷，LRD——

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

設二叉樹bt的一種存儲結構如下：00237580101jhfdbacegi000940000012345678910lchilddatarchild

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

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

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