【哈夫曼編/譯碼器】任務(wù)：建立最優(yōu)二叉樹函數(shù)要求：可以建立函數(shù)輸入二叉樹，并輸出其赫夫曼樹。在上交資料中請寫明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖）、輸入輸出、源程序、測試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(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中讀入），對文件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中。測試數(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。請用戶鍵入一個(gè)選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3）在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因?yàn)槲募fmTree可能早已建好。代碼如下：#include <stdio.h>#include <stdlib.h>#include <string.h>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(!HTi.parent) s1 = i; break; for(j = i+1; j <= nNode; j+) if(!HTj.parent) s2 = j; break; for(i = 1; i <= nNode; i+) if(HTi.weight < HTs1.weight) && (!HTi.parent) && (s2 != i) s1 = i; for(j = 1; j <= nNode; j+) if(HTj.weight < HTs2.weight) && (!HTj.parent) && (s1 != j) s2 = j; if(HTs1.weight > HTs2.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+) HTi.weight = wi-1; HTi.parent = 0; HTi.lchild = 0; HTi.rchild = 0; for(i = nNode+1; i <= m; i+) HTi.weight = 0; HTi.parent = 0; HTi.lchild = 0; HTi.rchild = 0; for(i = nNode+1; i <= m; i+) select(HT, i-1); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.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, HTj.weight, HTj.parent, HTj.lchild, HTj.rchild); cd = (char *) malloc (nNode * sizeof(char); cdlen = 0; cdnNode-1=0; int c,f; for(int i=1; i<=nNode; i+) cdlen=nNode-1; for(c=i,f=HTi.parent; f!=0; c=f,f=HTf.parent) if(HTf.lchild=c) cd-cdlen=0; else cd-cdlen=1; HCi=(char*)malloc(nNode-cdlen)*sizeof(char); strcpy(HCi,&cdcdlen); int main() HuffmanTree HT; / 哈夫曼樹 HuffmanCode *HC; / 哈夫曼編碼 int *w, nNode, i; / 權(quán)值 printf("輸入結(jié)點(diǎn)數(shù): n"); scanf("%d", &nNode); printf("%dnn",nNode); HC = (HuffmanCode *) malloc (nNode* sizeof(HuffmanCode); w = (int *) malloc (nNode * sizeof(int); printf("輸入 %d 個(gè)結(jié)點(diǎn)的對應(yīng)的權(quán)值n", nNode); for(i = 0; i < nNode; i+) scanf("%d", &wi); HuffmanCoding(HT, HC, w, nNode); puts("n各結(jié)點(diǎn)的哈夫曼編碼為:"); for(i = 1; i <= nNode; i+) printf("%2d -%4d : %sn", i, wi-1, HCi); getchar();使用界面如下：