數(shù)據(jù)結(jié)構(gòu)教學課件：第七講1二叉樹 圖

1、例 w=5, 29, 7, 8, 14, 23, 3, 1151429782331114297823113588715142923358111135819142923871511358192923148715292914871529113581923421135819234229148715295811358192342291487152958100哈夫曼樹生成過程 在遠程通訊中，要將待傳字符轉(zhuǎn)換成由二進制的字符串： 設(shè)要傳送的字符為： ABACCDA若編碼為：A00 B01 C10 D-11 若將編碼設(shè)計為長度不等的二進制編碼，即讓待傳字符串中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則轉(zhuǎn)換的二

2、進制字符串便可能減少。00010010101100設(shè)要傳送的字符為：ABACCDA若編碼為： A0 B00 C1 D-01 關(guān)鍵：要設(shè)計長度不等的編碼，則必須使任一字符的編碼都不是另一個字符的編碼的前綴。 ABACCDA 000011010但： 0000AAAA ABA BB重碼設(shè)要傳送的字符為： ABACCDA若編碼為 ：A0 B110 C10 D-111 0110010101110ACBD000111采用二叉樹設(shè)計二進制前綴編碼規(guī)定：左分支用“0”表示；右分支用“1”表示譯碼過程：分解接收字符串：遇“0”向左，遇“1”向右；一旦到達葉子結(jié)點，則譯出一個字符，反復(fù)由根出發(fā)，直到譯碼完成。 0

3、110010101110ACBD000111ABACCDA例：已知某系統(tǒng)在通訊時，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計Huffman編碼。 W（權(quán)）=2，4，2，3，3，葉子結(jié)點個數(shù)n=5 148464220001113301構(gòu)造的Huffman樹 T B A C SHuffman算法實現(xiàn)一棵有n個葉子結(jié)點的Huffman樹有2n-1個結(jié)點采用順序存儲結(jié)構(gòu)一維結(jié)構(gòu)數(shù)組結(jié)點類型定義typedef struct int data; int pa,lc,rc;JD;為什么？lc data rc pa1 2 3 4 5 6 70 0 0 0 0 0 07 5

4、 2 4 0 0 00 0 0 0 0 0 00 0 0 0 0 0 0(1)kx1=3,x2=4m1=2,m2=4lc data rc pa1 2 3 4 5 6 70 0 0 0 3 0 07 5 2 4 6 0 00 0 0 0 4 0 00 0 5 5 0 0 0(2)klc data rc pa1 2 3 4 5 6 70 0 0 0 3 2 07 5 2 4 6 11 00 0 0 0 4 5 00 6 5 5 6 0 0 x1=2,x2=5m1=5,m2=6(3)lc data rc pax1=1,x2=6m1=7,m2=111 2 3 4 5 6 70 0 0 0 3 2 17

5、 5 2 4 6 11 180 0 0 0 4 5 67 6 5 5 6 7 0k(4)幾個？1、會編程在一維數(shù)組中找到最小的一個數(shù)嗎？2、在一個一維數(shù)組里找到第二小的3、生成一個新的節(jié)點，左右孩子是？4、循環(huán)次數(shù)怎么定？第七章 圖7.1 圖的定義和術(shù)語圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)蛴行驅(qū)τ邢驁D有向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是有向邊（也稱?。┑挠邢藜希∈琼旤c的有序?qū)?，記為，v,w是頂點，v為弧尾，w為弧頭無向圖無

6、向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序?qū)?，記為（v,w）或（w,v)，并且（v,w)=(w,v)例245136G1圖G1中：V(G1)=1,2,3,4,5,6 E(G1)=, , , , , , 例157324G26圖G2中：V(G2)=1,2,3,4,5,6,7 E(G1)=(1,2), (1,3), (2,3), (2,4),(2,5), (5,6), (5,7)有向完全圖n個頂點的有向圖最大邊數(shù)是n(n-1)無向完全圖n個頂點的無向圖最大邊數(shù)是n(n-1)/2權(quán)與圖的邊或弧相關(guān)的數(shù)叫網(wǎng)帶權(quán)的圖叫子圖如果圖G(V

7、,E)和圖G(V,E),滿足：VVEE 則稱G為G的子圖頂點的度無向圖中，頂點的度為與每個頂點相連的邊數(shù)有向圖中，頂點的度分成入度與出度入度：以該頂點為頭的弧的數(shù)目出度：以該頂點為尾的弧的數(shù)目路徑路徑是頂點的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn)路徑長度沿路徑邊的數(shù)目或沿路徑各邊權(quán)值之和回路第一個頂點和最后一個頂點相同的路徑叫簡單路徑序列中頂點不重復(fù)出現(xiàn)的路徑叫簡單回路除了第一個頂點和最后一個頂點外，其余頂點不重復(fù)出現(xiàn)的回路叫連通從頂點V到頂點W有一條路徑，則說V和W是連通的連通圖圖中任意兩個頂點都是連通的叫連通分量非連通圖的每一個連通部分叫強連通圖有

8、向圖中，如果對每一對Vi,VjV, ViVj,從Vi到Vj 和從Vj到 Vi都存在路徑，則稱G是例213213有向完全圖無向完全圖356例245136圖與子圖例245136G1頂點2入度：1 出度：3頂點4入度：1 出度：0例157324G26頂點5的度：3頂點2的度：4例157324G26例245136G1路徑：1，2，3，5，6，3路徑長度：5簡單路徑：1，2，3，5回路：1，2，3，5，6，3，1簡單回路：3，5，6，3路徑：1，2，5，7，6，5，2，3路徑長度：7簡單路徑：1，2，5，7，6回路：1，2，5，7，6，5，2，1簡單回路：1，2，3，1連通圖例245136強連通圖356

9、例非連通圖連通分量例2451367.2 圖的存儲結(jié)構(gòu)多重鏈表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3鄰接矩陣表示頂點間相聯(lián)關(guān)系的矩陣定義：設(shè)G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質(zhì)的n階方陣例G12413例15324G2特點：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點Vi的出度是A中第i行元素之和頂點Vi的入度是A中第i列元素之和網(wǎng)絡(luò)的鄰接矩陣可定義為：例14523

10、75318642鄰接表實現(xiàn)：為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的?。﹖ypedef struct node int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數(shù)組中的位置 struct node *next; /鏈域，指示下一條邊或弧JD;adjvex next表頭接點：typedef struct tnode int vexdata; /存放頂點信息 struct node *firstarc; /指示第一個鄰接點TD;TD gaM; /ga0不用vexdata firstarc例G1bdac例aecbdG21234acd

11、bvexdatafirstarc 3 2 4 1adjvexnext1234acdbvexdatafirstarc 4 2 1 2adjvexnext5e 4 3 5 1 5 3 2 3特點無向圖中頂點Vi的度為第i個單鏈表中的結(jié)點數(shù)有向圖中頂點Vi的出度為第i個單鏈表中的結(jié)點個數(shù)頂點Vi的入度為整個單鏈表中鄰接點域值是i的結(jié)點個數(shù)逆鄰接表：有向圖中對每個結(jié)點建立以Vi為頭的弧的單鏈例G1bdac1234acdbvexdatafirstarc 4 1 1 3adjvexnext7.3 圖的遍歷深度優(yōu)先遍歷(DFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發(fā)，

12、深度優(yōu)先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，直至圖中所有頂點都被訪問為止V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V5 V3 V6 V7V1V2V4V5V3V7V6V8例例V1V2V4V5V3V7V6V8深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7深度遍歷：V1 V2 V4 V8 V5 V6 V3 V7V1V2V4V5V3V7V6V8例深度遍歷：V1 V2 V4 V8 V3 V6 V7 V5廣度優(yōu)先遍歷(BFS)方法：從圖的某一頂點V0出發(fā)，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發(fā)，廣度優(yōu)先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復(fù)上述過程，