哈夫曼編、譯碼器2

韶關(guān)學(xué)院學(xué)生實(shí)驗(yàn)報(bào)告冊實(shí)驗(yàn)課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)項(xiàng)目名稱：實(shí)驗(yàn)六樹及其應(yīng)用哈夫曼編/譯碼器實(shí)驗(yàn)類型（打√）：（基礎(chǔ)、綜合、設(shè)計(jì)√）院系：信息工程學(xué)院計(jì)算機(jī)系專業(yè)：*****姓名：***學(xué)號(hào)：*****指導(dǎo)老師：陳正銘韶關(guān)學(xué)院教務(wù)處編制一、實(shí)驗(yàn)預(yù)習(xí)報(bào)告內(nèi)容預(yù)習(xí)日期：2007年實(shí)驗(yàn)預(yù)習(xí)報(bào)告內(nèi)容原則上應(yīng)包括實(shí)驗(yàn)?zāi)康?、?shí)驗(yàn)所用的主要儀器藥品、實(shí)驗(yàn)原理與公式、實(shí)驗(yàn)預(yù)習(xí)疑問等項(xiàng)目。【實(shí)驗(yàn)?zāi)康摹渴炀氄莆辗蔷€性數(shù)據(jù)結(jié)構(gòu)二叉樹樹的操作，熟悉樹的各種存儲(chǔ)結(jié)構(gòu)特性，以及如何應(yīng)用樹解決具體問題?！拘枰治觥坷霉蚵幋a進(jìn)行通信可以大大提高信道利用率，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼。試為這樣的信息收發(fā)寫一個(gè)哈夫曼編/譯碼系統(tǒng)，要求具備以下功能：初始化、編碼、譯碼、印代碼文件、印哈夫曼樹。一個(gè)完整的哈夫曼碼的編譯碼系統(tǒng)系統(tǒng)應(yīng)具有以下功能：（1）I:初始化(Initialization)。從終端讀入字符集大小n，幾個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmtree中。（2）C:編碼(Coding)。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree中讀入），對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中。（3）D:譯碼(Decoding)。利用已建好的哈夫曼樹將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中。（4）P:打印代碼文件(Print)。將文件codefile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件codeprint中。（5）T:打印哈夫曼樹(Treeprinting)。將已在內(nèi)存中的哈夫曼樹以直觀的方式（數(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件treeprint中。【軟件平臺(tái)】Windows2000，VisualC＋＋6.0或WINTC【概要設(shè)計(jì)】ADTArray{數(shù)據(jù)對(duì)象:D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系:若D為空集，則稱為空樹；否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root,(2)當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹?；静僮鳎篠tatusinitHTree(HuffmanTree&T,intn)//初始化一個(gè)n個(gè)字符集的哈夫曼樹StatusDestroyHTree(HuffmanTree&T)//銷毀哈夫曼樹StatusSelect(int&s1,int&s2,intn,PHTNodeH)//從二叉樹位置從0~n集合中找到2個(gè)根結(jié)點(diǎn)的權(quán)值最小的位置StatusHEncoding(charstring[SIZE])//哈夫曼編碼,并把結(jié)果保存在string文件中StatusHDecoding(charstring[SIZE])//哈夫曼譯碼,并把結(jié)果保存在string文件中}ADTArray【疑問】（這部分內(nèi)容因人而異，也可不寫）實(shí)驗(yàn)預(yù)習(xí)評(píng)分：二、實(shí)驗(yàn)原始（數(shù)據(jù)）記錄實(shí)驗(yàn)時(shí)間：2007年6月13日（星期三第7，8節(jié)）實(shí)驗(yàn)同組人：如有實(shí)驗(yàn)實(shí)驗(yàn)數(shù)據(jù)表格，學(xué)生在實(shí)驗(yàn)預(yù)習(xí)時(shí)應(yīng)畫好實(shí)驗(yàn)數(shù)據(jù)表格，供實(shí)驗(yàn)填寫數(shù)據(jù)。*******************************************************************************本程序的命令:(1)創(chuàng)建哈夫曼樹C;(2)對(duì)指定的文件現(xiàn)行編碼E;(3)對(duì)指定的代碼進(jìn)行譯碼D;(4)退出程序Q.*******************************************************************************請(qǐng)輸入命令(C,E,D,Q):C請(qǐng)輸入字符集的大小(n):27請(qǐng)輸入字集的保存路徑\名稱:c:\charset.txt請(qǐng)輸入字符集對(duì)應(yīng)的權(quán)值::186A:64D:32E:103F:H:47I:57J:1K:5L:32M:20P:15Q:1R:48S:51T:80U:23V:8W:18X:1Y:16Z:1請(qǐng)輸入哈夫曼樹的保存路徑\名稱:c:\hfmtree.txt請(qǐng)輸入任意鍵繼續(xù)運(yùn)行程序請(qǐng)輸入命令(C,E,D,Q):E請(qǐng)輸入保存哈夫曼樹的保存路徑\名稱:c:\hfmtree.txt請(qǐng)輸入要編碼文件的保存路徑\名稱:c:\textfile.txt請(qǐng)輸入代碼文件的保存路徑\名稱:codefile.txt哈夫曼編碼的結(jié)果:1101000101100011111100010001010011000010010101011001011101100011111110010100011111110011101011000001001001001101101010請(qǐng)輸入任意鍵繼續(xù)運(yùn)行程序請(qǐng)輸入命令(C,E,D,Q):D請(qǐng)輸入保存哈夫曼樹的保存路徑\名稱:c:\hfmtree.txt請(qǐng)輸入代碼文件的保存路徑\名稱:c:\codefile.txt請(qǐng)輸入譯碼文件的保存路徑\名稱:c:\decode.txt哈夫曼譯碼的結(jié)果:THISPROGRAMISMYFAVORITE指導(dǎo)教師批閱及簽名三、實(shí)驗(yàn)報(bào)告內(nèi)容

2007年6實(shí)驗(yàn)報(bào)告內(nèi)容原則上應(yīng)包括主要實(shí)驗(yàn)步驟、實(shí)驗(yàn)數(shù)據(jù)計(jì)算（實(shí)驗(yàn)操作）結(jié)果、實(shí)驗(yàn)結(jié)果（疑問）分析等項(xiàng)目?！局鞒绦蚰K】：voidmain(){初始化;do{接受命令;處理命令;}while(命令!=“退出”)；}【功能模塊調(diào)用關(guān)系圖】主程序模塊主程序模塊創(chuàng)建哈夫曼樹創(chuàng)建哈夫曼樹模塊哈夫曼編碼哈夫曼編碼模塊哈夫曼譯碼哈夫曼譯碼模塊【詳細(xì)設(shè)計(jì)】typedefstructHTNode//哈夫曼樹結(jié)點(diǎn)類型{intweight;//結(jié)點(diǎn)的權(quán)值intparent,lchild,rchild;//結(jié)點(diǎn)的雙親parent,結(jié)點(diǎn)的左子樹lchild,結(jié)點(diǎn)的右子樹rchild}*PHTNode;structHuffmanTree//哈夫曼樹類型{HTNode*HT;//哈夫曼樹ElemTypech;//哈夫曼樹的字符集intn;//哈夫曼樹的字符集個(gè)數(shù)};StatusinitHTree(HuffmanTree&T,intn)//初始化一個(gè)n個(gè)字符集的哈夫曼樹StatusDestroyHTree(HuffmanTree&T)//銷毀哈夫曼樹StatusSelect(int&s1,int&s2,intn,PHTNodeH)//從二叉樹位置從0~n集合中找到2個(gè)根結(jié)點(diǎn)的權(quán)值最小的位置StatusHEncoding(charstring[SIZE])//哈夫曼編碼,并把結(jié)果保存在string文件中StatusHDecoding(charstring[SIZE])//哈夫曼譯碼,并把結(jié)果保存在string文件中StatusOpenWriteFile(PFILE&fp,charstring[SIZE])//打開寫的文件StatusOpenReadFile(PFILE&fp,charstring[SIZE])//打開讀的文件StatusPrintFile(charstring[SIZE])//輸出文件名為string的字符【調(diào)試分析】（這部分內(nèi)容因人而異）這里最大的問題就是文件的運(yùn)用了，一開始，我用的是freopen()函數(shù)，這個(gè)函數(shù)能完成在文件里面的輸入輸出操作，但是無法完成在屏幕上顯示出來。后來，查了課本，發(fā)現(xiàn)fopen(),fclose()更好用?！居脩羰謨浴勘境绦蜻\(yùn)行環(huán)境為ＤＯＳ，執(zhí)行文件為：haffman.exe.進(jìn)入演示程序后，出現(xiàn)提示信息：——進(jìn)行相應(yīng)輸入后程序執(zhí)行相應(yīng)操作，顯示相應(yīng)結(jié)果。實(shí)驗(yàn)報(bào)告評(píng)分：注：1、如有個(gè)別實(shí)驗(yàn)的實(shí)驗(yàn)報(bào)告內(nèi)容多，實(shí)驗(yàn)報(bào)告冊頁面不夠?qū)?，或有識(shí)圖，畫圖要求的，學(xué)生應(yīng)根據(jù)實(shí)驗(yàn)指導(dǎo)老師要求另附相同規(guī)格的紙張并粘貼在相應(yīng)的“實(shí)驗(yàn)報(bào)告冊”中。2、實(shí)驗(yàn)報(bào)告冊屬教學(xué)運(yùn)行材料，院系（中心）應(yīng)按有關(guān)規(guī)定歸檔保管?！驹闯绦颉?include<iostream.h>#include<stdlib.h>#include<process.h>#include<conio.h>#include<stdio.h>#defineERROR0#defineOK1typedefboolStatus;#defineSIZE20typedefFILE*PFILE;typedefchar*ElemType;typedefstructHTNode//哈夫曼樹結(jié)點(diǎn)類型{intweight;//結(jié)點(diǎn)的權(quán)值intparent,lchild,rchild;//結(jié)點(diǎn)的雙親parent,結(jié)點(diǎn)的左子樹lchild,結(jié)點(diǎn)的右子樹rchild}*PHTNode;structHuffmanTree//哈夫曼樹類型{HTNode*HT;//哈夫曼樹ElemTypech;//哈夫曼樹的字符集intn;//哈夫曼樹的字符集個(gè)數(shù)};StatusOpenWriteFile(PFILE&fp,charstring[SIZE])//打開寫的文件{if(!(fp=fopen(string,"wb"))){cout<<"文件打開失敗"<<endl;exit(ERROR);cout<<"Pressanykeytoexit"<<endl;getch(); }returnOK;}StatusOpenReadFile(PFILE&fp,charstring[SIZE])//打開讀的文件{if(!(fp=fopen(string,"rb"))){cout<<"文件打開失敗"<<endl;cout<<"Pressanykeytoexit"<<endl;getch();exit(ERROR);}returnOK;}StatusPrintFile(charstring[SIZE])//輸出文件名為string的字符{FILE*fp;charc;OpenReadFile(fp,string);while(!feof(fp)){for(inti=1;i<=50&&!feof(fp);i++){c=getc(fp);cout<<c;}cout<<endl;}fclose(fp);returnOK;}StatusinitHTree(HuffmanTree&T,intn)//初始化一個(gè)n個(gè)字符集的哈夫曼樹{T.n=n;if(!(T.HT=newHTNode[2*T.n])){cout<<"分配哈夫曼樹的存儲(chǔ)空間失敗"<<endl;exit(ERROR);}if(!(T.ch=newchar[T.n+1])){cout<<"分配字符集的存儲(chǔ)空間失敗"<<endl;exit(ERROR);}returnOK;}StatusDestroyHTree(HuffmanTree&T)//銷毀哈夫曼樹{delete(T.HT);delete(T.ch);returnOK;}StatusSelect(int&s1,int&s2,intn,PHTNodeH)//從二叉樹位置從0~n集合中找到2個(gè)根結(jié)點(diǎn)的權(quán)值最小的位置{inti,leap=0;for(i=1;i<=n;i++)if(!H[i].parent)if(leap){if(H[i].weight<H[s1].weight) s1=i;}else{s1=i;leap=1;}leap=0;H[s1].parent=1;for(i=1;i<=n;i++)if(!H[i].parent)if(leap){if(H[i].weight<H[s2].weight) s2=i;}else{s2=i;leap=1;}returnOK; }StatusCreateHTree()//創(chuàng)建哈夫曼樹并把結(jié)果保存在string為文件名的文件里{inti,s1,s2;FILE*fp,*cfp;charc,string[SIZE];HuffmanTreeT;intn;cout<<"請(qǐng)輸入字符集的大小(n):";cin>>n;initHTree(T,n);cout<<"請(qǐng)輸入字集的保存路徑\\名稱:";cin>>string;OpenReadFile(cfp,string);cout<<"請(qǐng)輸入字符集對(duì)應(yīng)的權(quán)值:"<<endl;for(i=1;i<=T.n;i++){c=getc(cfp);cout<<c<<":";T.ch[i]=c;cin>>T.HT[i].weight;T.HT[i].parent=0;T.HT[i].rchild=0;T.HT[i].lchild=0;}for(;i<2*T.n;i++){T.HT[i].weight=0;T.HT[i].parent=0;T.HT[i].rchild=0;T.HT[i].lchild=0;}for(i=T.n+1;i<2*T.n;i++){Select(s1,s2,i-1,T.HT);T.HT[i].lchild=s1;T.HT[i].rchild=s2;T.HT[s1].parent=i;T.HT[s2].parent=i;T.HT[i].weight=T.HT[s1].weight+T.HT[s2].weight;}cout<<"請(qǐng)輸入哈夫曼樹的保存路徑\\名稱:";cin>>string;OpenWriteFile(fp,string);fwrite(&T.n,sizeof(int),1,fp);fwrite(T.HT,sizeof(HTNode),2*T.n,fp);fwrite(T.ch,sizeof(char),T.n+1,fp);fclose(fp);fclose(cfp);DestroyHTree(T);returnOK;}StatusHEncoding(charstring[SIZE])//哈夫曼編碼,并把結(jié)果保存在string文件中{HuffmanTreeT;FILE*fp,*hfp,*cfp;inti,j,k;charch[SIZE],c,*cd;cout<<"請(qǐng)輸入保存哈夫曼樹的保存路徑\\名稱:";cin>>ch;OpenReadFile(hfp,ch);cout<<"請(qǐng)輸入要編碼文件的保存路徑\\名稱:";cin>>ch;OpenReadFile(fp,ch);cout<<"請(qǐng)輸入代碼文件的保存路徑\\名稱:";cin>>string;OpenWriteFile(cfp,string);fread(&T.n,sizeof(int),1,hfp);if(!(cd=newchar[T.n])){cout<<"編碼工作空間分配失敗"<<endl;exit(ERROR);}initHTree(T,T.n);fread(T.HT,sizeof(HTNode),2*T.n,hfp);fread(T.ch,sizeof(char),T.n+1,hfp);c=getc(fp);while(!feof(fp)){for(i=1;i<=T.n&&c!=T.ch[i];i++);j=T.n;k=i; while(T.HT[k].parent)if(T.HT[T.HT[k].parent].lchild==k){cd[--j]='0'; k=T.HT[k].parent;}else{cd[--j]='1'; k=T.HT[k].parent;}for(j;j<T.n;j++)putc(cd[j],cfp);c=getc(fp);}DestroyHTree(T);delete(cd);fclose(cfp);fclose(hfp);fclose(fp);returnOK;}StatusHDecoding(charstring[SIZE])//哈夫曼譯碼,并把結(jié)果保存在string文件中{HuffmanTreeT;charch[SIZE],c;FILE*fp,*hfp,*cfp;cout<<"請(qǐng)輸入保存哈夫曼樹的保存路徑\\名稱:";cin>>ch;OpenReadFile(hfp,ch);fread(&T.n,sizeof(int),1,hfp);initHTree(T,T.n);fread(T.HT,sizeof(HTNode),2*T.n,hfp);fread(T.ch,sizeof(char),T.n+1,hfp);voidPrintHTree(HuffmanTreeT);cout<<"請(qǐng)輸入代碼文件的保存路徑\\名稱:";cin>>ch;OpenReadFile(cfp,ch);cout<<"請(qǐng)輸入譯碼文件的保存路徑\\名稱:";cin>>string;OpenWriteFile(fp,string);c=ge