哈夫曼樹C++實(shí)現(xiàn).doc

《哈夫曼樹C++實(shí)現(xiàn).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈夫曼樹C++實(shí)現(xiàn).doc（5頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

【哈夫曼編/譯碼器】 任務(wù)：建立最優(yōu)二叉樹函數(shù) 要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。 在上交資料中請(qǐng)寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法； 利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。 [基本要求] 一個(gè)完整的系統(tǒng)應(yīng)具有以下功能： （1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。 （2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。 （3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。 （4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。 （5）T：印哈夫曼樹（Tree printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。 [測(cè)試數(shù)據(jù)] （1）利用下面這道題中的數(shù)據(jù)調(diào)試程序。 某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)八種字符，其概率分別為0.25，0.29，0.07，0.08，0.14，0.23，0.03，0.11，試設(shè)計(jì)哈夫曼編碼。 （2）用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。 字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 [實(shí)現(xiàn)提示] （1）編碼結(jié)果以文本方式存儲(chǔ)在文件CodeFile中。 （2）用戶界面可以設(shè)計(jì)為“菜單”方式：顯示上述功能符號(hào)，再加上“Q”，表示退出運(yùn)行Quit。請(qǐng)用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。 （3）在程序的一次執(zhí)行過(guò)程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。 代碼如下： #include #include #include int m, s1, s2; typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } HTNode, *HuffmanTree; typedef char* HuffmanCode; void select(HuffmanTree HT, int nNode) // { int i, j; for(i = 1; i <= nNode; i++) if(!HT[i].parent) { s1 = i; break; } for(j = i+1; j <= nNode; j++) if(!HT[j].parent) { s2 = j; break; } for(i = 1; i <= nNode; i++) if((HT[i].weight < HT[s1].weight) && (!HT[i].parent) && (s2 != i)) s1 = i; for(j = 1; j <= nNode; j++) if((HT[j].weight < HT[s2].weight) && (!HT[j].parent) && (s1 != j)) s2 = j; if(HT[s1].weight > HT[s2].weight) { int tmp = s1; s1 = s2; s2 = tmp; } } void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int nNode) { int i, j; char *cd; int cdlen; if(nNode < 1) return; m = 2*nNode-1; HT = (HTNode*) malloc ((m+1) *sizeof(HTNode)); for(i = 1; i <= nNode; i++) { HT[i].weight = w[i-1]; HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } for(i = nNode+1; i <= m; i++) { HT[i].weight = 0; HT[i].parent = 0; HT[i].lchild = 0; HT[i].rchild = 0; } for(i = nNode+1; i <= m; i++) { select(HT, i-1); HT[s1].parent = i; HT[s2].parent = i; HT[i].lchild = s1; HT[i].rchild = s2; HT[i].weight = HT[s1].weight + HT[s2].weight; if(i==m) { printf("結(jié)點(diǎn) weight parent lchild rchild"); for(j = 1; j <= i; j++) printf("\n%4d%8d%8d%8d%8d", j, HT[j].weight, HT[j].parent, HT[j].lchild, HT[j].rchild); } } cd = (char *) malloc (nNode * sizeof(char)); cdlen = 0; cd[nNode-1]=\0; int c,f; for(int i=1; i<=nNode; i++) { cdlen=nNode-1; for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--cdlen]=0; else cd[--cdlen]=1; } HC[i]=(char*)malloc((nNode-cdlen)*sizeof(char)); strcpy(HC[i],&cd[cdlen]); } } int main() { HuffmanTree HT; // 哈夫曼樹 HuffmanCode *HC; // 哈夫曼編碼 int *w, nNode, i; // 權(quán)值 printf("輸入結(jié)點(diǎn)數(shù): \n"); scanf("%d", &nNode); printf("%d\n\n",nNode); HC = (HuffmanCode *) malloc (nNode* sizeof(HuffmanCode)); w = (int *) malloc (nNode * sizeof(int)); printf("輸入 %d 個(gè)結(jié)點(diǎn)的對(duì)應(yīng)的權(quán)值\n", nNode); for(i = 0; i < nNode; i++) scanf("%d", &w[i]); HuffmanCoding(HT, HC, w, nNode); puts("\n各結(jié)點(diǎn)的哈夫曼編碼為:"); for(i = 1; i <= nNode; i++) printf("%2d ---%4d : %s\n", i, w[i-1], HC[i]); getchar(); } 使用界面如下：