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

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

3、110010101110ACBD000111ABACCDA例：已知某系統在通訊時，只出現C，A，S，T，B五種字符，它們出現的頻率依次為2，4，2，3，3，試設計Huffman編碼。 W（權）=2，4，2，3，3，葉子結點個數n=5 148464220001113301構造的Huffman樹 T B A C SHuffman算法實現一棵有n個葉子結點的Huffman樹有2n-1個結點采用順序存儲結構一維結構數組結點類型定義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、會編程在一維數組中找到最小的一個數嗎？2、在一個一維數組里找到第二小的3、生成一個新的節點，左右孩子是？4、循環次數怎么定？第七章 圖7.1 圖的定義和術語圖(Graph)圖G是由兩個集合V(G)和E(G)組成的,記為G=(V,E)其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對或有序對有向圖有向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是有向邊（也稱弧）的有限集合，弧是頂點的有序對，記為，v,w是頂點，v為弧尾，w為弧頭無向圖無

6、向圖G是由兩個集合V(G)和E(G)組成的 其中：V(G)是頂點的非空有限集 E(G)是邊的有限集合，邊是頂點的無序對，記為（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個頂點的有向圖最大邊數是n(n-1)無向完全圖n個頂點的無向圖最大邊數是n(n-1)/2權與圖的邊或弧相關的數叫網帶權的圖叫子圖如果圖G(V

7、,E)和圖G(V,E),滿足：VVEE 則稱G為G的子圖頂點的度無向圖中，頂點的度為與每個頂點相連的邊數有向圖中，頂點的度分成入度與出度入度：以該頂點為頭的弧的數目出度：以該頂點為尾的弧的數目路徑路徑是頂點的序列V=Vi0,Vi1,Vin，滿足(Vij-1,Vij)E 或 E,(1jn)路徑長度沿路徑邊的數目或沿路徑各邊權值之和回路第一個頂點和最后一個頂點相同的路徑叫簡單路徑序列中頂點不重復出現的路徑叫簡單回路除了第一個頂點和最后一個頂點外，其余頂點不重復出現的回路叫連通從頂點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 圖的存儲結構多重鏈表例G12413例15324G2V1V2 V4 V3 V1 V2 V4 V5 V3鄰接矩陣表示頂點間相聯關系的矩陣定義：設G=(V,E)是有n1個頂點的圖，G的鄰接矩陣A是具有以下性質的n階方陣例G12413例15324G2特點：無向圖的鄰接矩陣對稱，可壓縮存儲；有n個頂點的無向圖需存儲空間為n(n+1)/2有向圖鄰接矩陣不一定對稱；有n個頂點的有向圖需存儲空間為n無向圖中頂點Vi的度TD(Vi)是鄰接矩陣A中第i行元素之和有向圖中，頂點Vi的出度是A中第i行元素之和頂點Vi的入度是A中第i列元素之和網絡的鄰接矩陣可定義為：例14523

10、75318642鄰接表實現：為圖中每個頂點建立一個單鏈表，第i個單鏈表中的結點表示依附于頂點Vi的邊（有向圖中指以Vi為尾的弧）typedef struct node int adjvex; /鄰接點域，存放與Vi鄰接的點在表頭數組中的位置 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個單鏈表中的結點數有向圖中頂點Vi的出度為第i個單鏈表中的結點個數頂點Vi的入度為整個單鏈表中鄰接點域值是i的結點個數逆鄰接表：有向圖中對每個結點建立以Vi為頭的弧的單鏈例G1bdac1234acdbvexdatafirstarc 4 1 1 3adjvexnext7.3 圖的遍歷深度優先遍歷(DFS)方法：從圖的某一頂點V0出發，訪問此頂點；然后依次從V0的未被訪問的鄰接點出發，

12、深度優先遍歷圖，直至圖中所有和V0相通的頂點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，直至圖中所有頂點都被訪問為止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廣度優先遍歷(BFS)方法：從圖的某一頂點V0出發，訪問此頂點后，依次訪問V0的各個未曾訪問過的鄰接點；然后分別從這些鄰接點出發，廣度優先遍歷圖，直至圖中所有已被訪問的頂點的鄰接點都被訪問到；若此時圖中尚有頂點未被訪問，則另選圖中一個未被訪問的頂點作起點，重復上述過程，