算法與數(shù)據(jù)結(jié)構(gòu)

1、數(shù)據(jù)結(jié)構(gòu)與算法數(shù)據(jù)結(jié)構(gòu)與算法第一章第一章緒論緒論1數(shù)據(jù)結(jié)構(gòu)的分類：⑴線性結(jié)構(gòu)。其中每個結(jié)點最多只有一個前驅(qū)和后繼的結(jié)構(gòu)。線性表（單鏈表、循環(huán)鏈表、雙向鏈表）、棧、隊列等都是線性表的結(jié)構(gòu)。“一對一”⑵樹形結(jié)構(gòu)。其中每個結(jié)點最多只有一個前驅(qū)，但可以有多個后繼的結(jié)構(gòu)。二叉樹、樹、森林都是樹形結(jié)構(gòu)?！耙粚Χ唷雹菑碗s結(jié)構(gòu)。其中結(jié)點的前驅(qū)和后繼點個數(shù)都不做限制的結(jié)構(gòu)。有向圖、無向圖都是復雜結(jié)構(gòu)?！岸鄬Χ唷?存儲的各種表示：順序表示、連接表示、散列旗

2、袍、索引表示3文件的處理，在文件上的操作的種類：⑴檢索⑵插入⑶刪除⑷修改⑸排序4算法的性質(zhì)：有窮性、確定性、可行性練習題：練習題：1計算下列程序片段的時間代價inti=1while(in1q=pq)palistelement[q1]=palistelement[q]⑵刪除f(q=pqn1n1q)Palistelement[q]=palistelement[q1]2單鏈表：⑴插入intPost_link(LinkListllistPNod

3、epDataTypex)⑵刪除intV_link(LinkListllistDataTypex)3循環(huán)雙鏈表⑴插入pllinkrlimk=prlinkprlinkllink=pllink⑵刪除q=(PDoubleNode)malloc(sizeof(structDoubleNode))4采用順序存儲方式表示矩陣一般有行優(yōu)先順序行優(yōu)先順序和列優(yōu)先順序。列優(yōu)先順序。第五章第五章二叉樹與樹二叉樹與樹1結(jié)點的層數(shù)：規(guī)定根的層數(shù)為0，其余結(jié)點的層

4、數(shù)結(jié)點的層數(shù)等于其父結(jié)點的層數(shù)加12結(jié)點的度數(shù)：結(jié)點的非空子樹（即后綴）個數(shù)叫做結(jié)點的度數(shù)結(jié)點的度數(shù)3一般二叉樹的性質(zhì)：性質(zhì)一：在非空二叉樹的i層上，至多有2i個結(jié)點（i≥0）性質(zhì)二：高度為k的二叉樹中最多有2k11個結(jié)點（k≥0）性質(zhì)五：對于具有n個結(jié)點的完全二叉樹，如果按照從上（根結(jié)點）到下（葉結(jié)點）和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點從0開始到n1進行編號，對于任意的下標為i的結(jié)點，有：⑴如果i=0，則它是根結(jié)點，他沒有父結(jié)點，如

5、果i0，則它的父結(jié)點的下標為（i1）2⑵如果2i1≤n1，則下標為i的結(jié)點的左子結(jié)點的下標為2i1，否則下標為i的結(jié)點沒有左子結(jié)點⑶如果2i2≤n1，則下標為i的結(jié)點的右子結(jié)點的下標為2i2，否則下標為i的結(jié)點沒有右子結(jié)點4二叉樹的周游（要求會做題）先根次周游（DLR）：若二叉樹不空，則先訪問根；然后按先根次序周游左子樹；最后按先根次序周游右子樹后根次序（LRD）：若二叉樹不空，則先按后根次序周游左子樹；然后按后根次序周游右子樹；最后訪

6、問根。對稱（中根）次序：若二叉樹不空，則先按對稱序周游左子樹；然后訪問根；最后按對稱序周游右子樹5二叉樹的表示對于完全二叉樹，如果按照（根結(jié)點）到下（葉結(jié)點）和從左到右的順序，對二叉樹中的所有結(jié)點從0到n1編號，這樣存放到一繼數(shù)組中，只要通過數(shù)組元素的下標關(guān)系，就可以確定二叉樹中結(jié)點之間的邏輯關(guān)系。（會做題）看p132圖5.10及該數(shù)組的度p133圖5.116看p136線索二叉樹7哈夫曼樹的權(quán)值WPL=∑wili假設有一組（無序）實數(shù)w

7、1w2w3…wm現(xiàn)要構(gòu)造一棵以wi（i=12，…m）為權(quán)的m個外部結(jié)點的擴充的二叉樹，使得帶權(quán)的外部路徑長度WPL最小。滿足這一要求的擴充二叉樹就稱為哈夫曼樹哈夫曼樹或最優(yōu)二叉樹最優(yōu)二叉樹（會構(gòu)建哈夫曼樹，會求權(quán)值）8在樹中，結(jié)點的度數(shù)：在樹中一個結(jié)點的子結(jié)點個數(shù)叫做這個結(jié)點的度數(shù)結(jié)點的度數(shù)9樹的周游：主要分先根次序先根次序和后根次序后根次序兩種先根次序：首先訪問根結(jié)點，然后從左到右按先根次序周游根結(jié)點的每顆子樹后根次序：首先從左到右按

8、后根次序周游根結(jié)點的每科子樹，最后訪問根結(jié)點10p161長子兄弟表示法11樹林的周游：樹林的周游方法有兩種：先根次序和后根次序先根次序：首先訪問樹林中第一棵樹的根結(jié)點，然后先根次序周游第一棵樹除去根結(jié)點剩下的所有子樹構(gòu)成的樹林，最后先根次序周游除去第一棵樹之后剩下的樹林。后根次序：首先后根次序周游第一棵樹的根結(jié)點的所有子樹構(gòu)成的樹林，然后訪問樹林中第一棵樹的根結(jié)點，最后后根次序周游除去第一棵樹之后剩下的樹林12p164樹林與二叉樹的轉(zhuǎn)換