《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)匯總

《數(shù)據(jù)結(jié)構(gòu)與算法》課程設(shè)計(jì)(2013/2014學(xué)年第一學(xué)期17周)班級(jí)：12計(jì)算機(jī)科學(xué)與技術(shù)3班2.基本要求3.測(cè)試要求3字符ABCDEFGHIJKLM頻度15字符N0PQRSTUVWXYZ頻度1811某文件中的一個(gè)符號(hào))進(jìn)行編碼。這張編碼表的特殊現(xiàn)的估算概率而建立起來(lái)的(出現(xiàn)概率高的字符使用較短的編碼，反之出現(xiàn)概率低的則使目的)。赫夫曼編碼的應(yīng)用很廣泛，利用赫夫曼樹(shù)求得的用于通信表示"0”碼，指向右子樹(shù)的分支表示“1"碼，取每條路徑上的"0”或“1"的序列作為哈夫曼編\譯碼器的主要功能是先建立哈夫曼樹(shù)，然后利用建好的哈夫曼曼編碼后進(jìn)行譯碼。在數(shù)據(jù)通信中，經(jīng)常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符0、1組成的二進(jìn)制串，稱(chēng)之為編碼。構(gòu)造一棵哈夫曼樹(shù)，規(guī)定哈夫曼樹(shù)中的左分之代表0,右分支代表1,則從根節(jié)點(diǎn)到每個(gè)葉子節(jié)點(diǎn)所經(jīng)過(guò)的路徑分支組成的0和1的序列便為該節(jié)點(diǎn)對(duì)應(yīng)字符的編(1)其主要流程圖如圖1-1所示。開(kāi)始否結(jié)點(diǎn)數(shù)是否大于1是輸出根結(jié)點(diǎn)和權(quán)值否是調(diào)用SELECT函數(shù)計(jì)算根結(jié)點(diǎn)函數(shù)父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn)否是否為根結(jié)點(diǎn)?是是左子是否為空?是否是此時(shí)編碼為0右子是否為空此時(shí)編碼為0否編碼為1結(jié)束6(2)設(shè)計(jì)包含的幾個(gè)方面：①赫夫曼樹(shù)的建立赫夫曼樹(shù)的建立由赫夫曼算法的定義可知，初始森林中共有n棵只含有根結(jié)點(diǎn)的二叉樹(shù)。算法的第二步是：將當(dāng)前森林中的兩棵根結(jié)點(diǎn)權(quán)值最小的二叉樹(shù)，合并成一棵新的二叉樹(shù)；每合并一次，森林中就減少一棵樹(shù)，產(chǎn)生一個(gè)新結(jié)點(diǎn)。顯然要進(jìn)行n-1次合并，所以共產(chǎn)生n-1個(gè)新結(jié)點(diǎn)，它們都是具有兩個(gè)孩子的分支結(jié)點(diǎn)。由此可知，最終求得的赫夫曼個(gè)結(jié)點(diǎn)是初始森林的n個(gè)孤立結(jié)點(diǎn)。并且赫夫曼樹(shù)中沒(méi)有度數(shù)為1的分支結(jié)點(diǎn)。我們可以利用一個(gè)大小為2n--1的一維數(shù)組來(lái)存儲(chǔ)赫夫曼樹(shù)中的結(jié)點(diǎn)。要求電文的赫夫曼編碼，必須先定義赫夫曼編碼類(lèi)型，根據(jù)設(shè)計(jì)要求和實(shí)際需要定義的類(lèi)型如下：charch;//存放編碼的字符charbits[N+1];//存放編碼位串intlen;//編碼的長(zhǎng)度}CodeNode;//編碼結(jié)構(gòu)體類(lèi)型③代碼文件的譯碼譯碼的基本思想是：讀文件中編碼，并與原先生成的赫夫曼編碼表比較，遇到相等時(shí)，即取出其對(duì)應(yīng)的字符存入一個(gè)新串中。源程序如下：//義用N表示50葉節(jié)點(diǎn)數(shù)//用M表示節(jié)點(diǎn)總數(shù)當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1typedefstructtypedefstructif(ht[k].weight<minl)elseif(ht[kweightminmin2=ht[kweightrnode8if(ht[f].Ichild==c)9化while(flag)//菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán){調(diào)試分析五、詳細(xì)設(shè)計(jì)(1)①赫夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)描述為：if(ht[k].weight<minl)(2)哈弗曼編碼printf("%c",hcd[i].cd[k])字符的編碼break(3)哈弗曼譯碼/為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)}printf("%c",ht[i].data)(4)主函數(shù)charstr[]={A',B',C',D',E',F,G,H,T,J,K,L,M,N',O,P',Q,R'化{}//菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán)//菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán)printf("***********************本課程設(shè)計(jì)的評(píng)價(jià)由三部分組成，包括程序演示(50%),課程設(shè)計(jì)報(bào)告(30%),回答教師提問(wèn)(20%)。