算法與數(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)。其中每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和后繼的結(jié)構(gòu)。線性表（單鏈表、循環(huán)鏈表、雙向鏈表）、棧、隊(duì)列等都是線性表的結(jié)構(gòu)?！耙粚?duì)一”⑵樹(shù)形結(jié)構(gòu)。其中每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)，但可以有多個(gè)后繼的結(jié)構(gòu)。二叉樹(shù)、樹(shù)、森林都是樹(shù)形結(jié)構(gòu)。“一對(duì)多”⑶復(fù)雜結(jié)構(gòu)。其中結(jié)點(diǎn)的前驅(qū)和后繼點(diǎn)個(gè)數(shù)都不做限制的結(jié)構(gòu)。有向圖、無(wú)向圖都是復(fù)雜結(jié)構(gòu)?！岸鄬?duì)多”2存儲(chǔ)的各種表示：順序表示、連接表示、散列旗

2、袍、索引表示3文件的處理，在文件上的操作的種類：⑴檢索⑵插入⑶刪除⑷修改⑸排序4算法的性質(zhì)：有窮性、確定性、可行性練習(xí)題：練習(xí)題：1計(jì)算下列程序片段的時(shí)間代價(jià)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采用順序存儲(chǔ)方式表示矩陣一般有行優(yōu)先順序行優(yōu)先順序和列優(yōu)先順序。列優(yōu)先順序。第五章第五章二叉樹(shù)與樹(shù)二叉樹(shù)與樹(shù)1結(jié)點(diǎn)的層數(shù)：規(guī)定根的層數(shù)為0，其余結(jié)點(diǎn)的層

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

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

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

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

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