哈夫曼編碼譯碼課程設(shè)計報告樣本

計算機與信息工程系《實踐環(huán)節(jié)名稱》報告專業(yè)：計算機科學(xué)與技術(shù)班級：********學(xué)號：*********姓名：楊明英報告完畢日期：/6/10指引教師：***評語：成績：批閱教師簽名：批閱時間：目錄1．問題描述……………12．基本規(guī)定……………13．數(shù)據(jù)構(gòu)造……………14．總體設(shè)計……………15．詳細設(shè)計……………25.1主函數(shù)voidmain()………25.2建立文獻voidjianliwenjian()…………35.3輸入原文voidluruyuanwen()…………45.4創(chuàng)立哈夫曼樹voidchuangjian()………55.5編碼voidbianma()……………………65.6對哈夫曼碼譯碼voidyiwen()…………75.7保存譯文voidbaocunyiwen()……………85.8輸出原文voidduquyuanwen()…………95.9輸出原文編碼voidduqubianma()…………105.10輸出譯文voidduquyiwen()……………116．測試與調(diào)試…………117．源程序清單…………88．實驗心得……………28問題描述打開一篇英文文章，記錄該文章中每個字符浮現(xiàn)次數(shù)，然后以它們作為權(quán)值，設(shè)計一種哈夫曼編/譯碼系統(tǒng)。基本規(guī)定以每個字符浮現(xiàn)次數(shù)為權(quán)值，建立哈夫曼樹，求出哈夫曼編碼，對文獻yuanwen中正文進行編碼，將成果存到文獻yiwen中，再對文獻yiwen中代碼進行譯碼，成果存到textfile中。數(shù)據(jù)構(gòu)造charCH[N]；//記錄原文字符數(shù)組charYW[N]；//記錄譯文字符數(shù)組typedefchar*Hcode[m+1]；//存儲哈夫曼字符編碼串頭指針數(shù)組typedefstruct{chara;intnum;}dangenode；//記錄單個字符類別和浮現(xiàn)次數(shù)typedefstruct{dangenodeb[m]；inttag;}jilunode；//記錄原文浮現(xiàn)字符種類和數(shù)量typedefstructnode//靜態(tài)三叉哈夫曼樹定義{intweight；//結(jié)點權(quán)值intparent；//雙親下標intLchild；//左孩子結(jié)點下標intRchild；//右孩子結(jié)點下標}htnode,hn[M+1]；//hn是構(gòu)造數(shù)組類型，0號單元不用總體設(shè)計功能函數(shù)模塊劃分voidmain()//主函數(shù)voidjianliwenjian()//建立存儲原文文獻yuanwenvoidluruyuanwen()//通過程序錄入原文到文獻yuanwen中voidmin_2(hnht,intn,int*tag1,int*tag2)//選取權(quán)值較小兩個結(jié)點voidchuangjian(jilunode*jilu,hnht)//建立哈夫曼樹voidbianma(jilunode*jilu,hnht,Hcodehc,intn)//對原文進行編碼voidbianmabaocun(Hcodehc,jilunode*jilu)//保存編碼在文獻yiwen中voidyiwen(Hcodehc,jilunode*jilu)//讀取yiwen中編碼，并將其翻譯為原文voidbaocunyiwen()//將翻譯譯文保存到文獻textfile中voidduqubianma()//在編碼文獻yiwen中讀取編碼voidduquyiwen()//從文獻textfile中讀取譯文詳細設(shè)計主函數(shù)voidmain()開始開始IntInttep=1;Ntep=1Ntep=1YYa=1Na=1NYYNa=2YNa=2Yjianliwenjian();jianliwenjian();NYa=3NYa=3luruyuanwen();Nluruyuanwen();NYc=1Yc=1chuangjian(jilu,humtree);Nchuangjian(jilu,humtree);Na=4Nc=1Ya=4Nc=1YYtep=0;Ytep=0;Nbianma(jilu,humtree,hc,jilu->tag);hc,jilu);Nbianma(jilu,humtree,hc,jilu->tag);hc,jilu);Yyiwen(hc,jilu);tep=0;a=yiwen(hc,jilu);tep=0;a=5system("cls");YYNa=6Na=6duquyuanwen();Bianmabaocun(hc,jiolu);system("cls");duquyuanwen();Bianmabaocun(hc,jiolu);system("cls");break;Ybaocunyiwen();Ybaocunyiwen();Na=7break;Na=7break;NNc=1c=1Nc=1duqubianma();NNc=1c=1Nc=1duqubianma();YYNYYduquyiwen();c=1tep=0;tep=0;NYYduquyiwen();c=1tep=0;tep=0;NYNYa=8tep=0;system("cls");a=8tep=0;system("cls");NYc=1tep=0;system("cls");NYc=1tep=0;system("cls");YYYbreak;system("cls");Ybreak;system("cls");tep=0;system("cls");break;IFYEStep=0;system("cls");break;IFYESbreak;break;system("cls");break;system("cls");break;結(jié)束結(jié)束5.2建立文獻voidjianliwenjian()一方面，要建立一種文獻來存儲原文，在這里文獻名稱按規(guī)定默以為yuanwen，文獻建立時有也許成功，有也許失敗，建立失敗時輸出“Cannotopenfile”，成功后會提示：“文獻已建立，名稱為yuanwen”。NYNY5.3輸入原文voidluruyuanwen()輸入原文時一方面要打開原文獻，成功打開文獻后逐個讀取輸入字符存儲到文獻中，直到遇到結(jié)束標志‘^’，然后關(guān)閉文獻。YNNYYNNY5.4創(chuàng)立哈夫曼樹voidchuangjian()打開存儲原文文獻yuanwen，將字符逐個讀出，然后記錄字符種類，類別和數(shù)量，最后建立靜態(tài)三叉鏈表來建立哈夫曼樹，樹中葉子結(jié)點相應(yīng)浮現(xiàn)個字符。YNYNYNYN5.5編碼voidbianma()該函數(shù)實現(xiàn)對哈夫曼樹編碼，先申請一種能存儲字符編碼暫時空間cd，編碼從哈夫曼樹葉子結(jié)點開始，尋找其父母結(jié)點，然后依照父母結(jié)點判斷孩子結(jié)點左右位置，左邊置1，右邊置0，并將1,0這樣字符從后往前逆序存儲在cd中，每求得一種葉子結(jié)點編碼，就將其復(fù)制到存儲哈夫曼編碼頭指正數(shù)組中，找完葉子結(jié)點編碼后就釋放暫時空間cd。NYNY5.6對哈夫曼碼譯碼voidyiwen()打開文獻yiwen，打開成功后，逐個讀取存儲在里邊編碼字符，并與先前編碼相匹配，直到找到編碼相應(yīng)原字符，當找完編碼后就關(guān)閉文獻。NYYNYNNYYNYN5.7保存譯文voidbaocunyiwen()打開文獻textfile，打開成功后，將譯文保存到文獻中，然后關(guān)閉文獻。YNYN5.8輸出原文voidduquyuanwen()打開文獻yuanwen，將里邊原文輸出，以便查看。YNYN5.9輸出原文編碼voidduqubianma()打開文獻yiwen，打開成功后，將文獻中存儲編碼輸出，然后關(guān)閉文獻。YNYN5.10輸出譯文voidduquyiwen()打開文獻textfile，打開成功后，輸出里邊譯文，然后關(guān)閉文獻。NYNY測試與調(diào)試程序調(diào)試采用MicrosoftVisualStudio，程序在調(diào)試過程中遇到了各種問題，一方面在建立哈夫曼樹時我是用靜態(tài)三叉鏈表實現(xiàn)，但里邊參數(shù)parent，Lchild，Rchild定義為指針類型，在原理上是可行，但調(diào)試時總得不到對的成果，日后改為書中用基本類型整型后就較好得到了滿意成果，其他某些小錯誤在不斷地調(diào)試，不斷地改進后，基本達到可滿意效果。各模塊調(diào)試成果截屏如下：6.1主函數(shù)菜單6.2建立文獻6.3通過程序輸入原文6.4直接將原文存儲到文獻yuawen中6.5對原文編碼6.6對編碼譯碼6.7輸出原文6.8輸出編碼6.9輸出譯文7.源程序清單#include<stdio.h>#include<stdlib.h>#include<string.h>#defineN5000#definem128//葉子結(jié)點個數(shù)，即字符總類數(shù)#defineM2*m-1//哈夫曼樹節(jié)點數(shù)charCH[N]；//記錄原文字符數(shù)組charYW[N]；//記錄譯文字符數(shù)組typedefchar*Hcode[m+1]；//存儲哈夫曼字符編碼串頭指針數(shù)組typedefstruct{chara;intnum;}dangenode；//記錄單個字符類別和浮現(xiàn)次數(shù)typedefstruct{dangenodeb[129];inttag;}jilunode；//記錄原文浮現(xiàn)字符種類數(shù)typedefstructnode{intweight；//結(jié)點權(quán)值intparent；//雙親下標 intLchild；//左孩子結(jié)點下標intRchild；//右孩子下標}htnode,hn[M];//靜態(tài)三叉哈夫曼樹定義voidjianliwenjian(){ printf("當前建立文獻，以存儲原文（文獻名稱默以為“yuanwen”）\n"); printf("文獻建立中......\n"); FILE*fp; if((fp=fopen("yuanwen","wb"))==NULL)//建立文獻 { printf("Cannotopenfile\n"); exit(0); } printf("文獻已建立,名稱為：yuanwen");fclose(fp)；//關(guān)閉文獻}voidluruyuanwen()//原文輸入完后，將其保存到文獻yuanwen中{ charch; FILE*fp; if((fp=fopen("yuanwen","wb"))==NULL)//打開文獻 { printf("Cannotopenfile\n"); exit(0); }printf("請輸入原文（結(jié)束標志為：“^”）\n");do{ ch=getchar();fputc(ch,fp)；//將字符保存到文獻中}while(ch!='^')；//判斷結(jié)束getchar()；//接受回車命令符fclose(fp)；//關(guān)閉文獻}voidmin_2(hnht,intn,int*tag1,int*tag2)//在建哈夫曼樹過程中，選取權(quán)值小兩{個結(jié)點 inti,min,s；min=N;for(i=1;i<=n;i++) if(ht[i].weight<min&&ht[i].parent==0){min=ht[i].weight；*tag1=i；//記錄權(quán)值最小結(jié)點下標}min=N; for(i=1;i<=n;i++)if(ht[i].weight<min&&ht[i].parent==0&&i!=*tag1){min=ht[i].weight；*tag2=i；} if(ht[*tag1].weight==ht[*tag2].weight&&ht[*tag2].Lchild!=0) { s=(*tag1)；//如果結(jié)點權(quán)值相似，先浮現(xiàn)放在哈夫曼樹左邊 (*tag1)=(*tag2); (*tag2)=s; }}voidchuangjian(jilunode*jilu,hnht)//建立哈夫曼樹、以及對原{文字符類別和數(shù)量記錄inti,j,s,tag1,tag2;s=0;i=-1;charch;FILE*fp; if((fp=fopen("yuanwen","rb"))==NULL)//以只讀方式打開文獻 { printf("Cannotopenfile\n"); exit(0); }while(!feof(fp))//判斷文獻批示標志與否移動到了文獻尾處 { ch=fgetc(fp); if(ch!='^')//判斷字符與否是結(jié)束標志 { ++i; CH[i]=ch;for(j=1;j<=jilu->tag;j++) { if(CH[i]==jilu->b[j].a) { jilu->b[j].num++; break; }}if(j-1==jilu->tag&&CH[i]!=jilu->b[j-1].a){jilu->tag++;jilu->b[jilu->tag].a=CH[i];jilu->b[jilu->tag].num=1;} } }jilu->tag--; fclose(fp)；//關(guān)閉文獻printf("原文中各字符記錄狀況如下：\n");printf("*^*^*^*^*^*^*^*^**^*^*^**^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n");for(i=1;i<=jilu->tag;i++){ s++; printf("‘%c’個數(shù)為:%d",jilu->b[i].a,jilu->b[i].num); if(s%4==0)//每行放四個數(shù)據(jù) printf("\n");}printf("\n")；for(i=1;i<=2*(jilu->tag)-1;i++){if(i<=jilu->tag){ ht[i].weight=jilu->b[i].num；//初始化葉子結(jié)點權(quán)值 ht[i].Lchild=0；//初始化葉子結(jié)點左孩子 ht[i].parent=0；//初始化葉子結(jié)點父母 ht[i].Rchild=0；//初始化葉子結(jié)點右孩子}else{ ht[i].Lchild=0；//初始化非葉子結(jié)點左孩子 ht[i].parent=0；//初始化非葉子結(jié)點父母 ht[i].Rchild=0；//初始化非葉子結(jié)點右孩子 ht[i].weight=0；//初始化非葉子結(jié)點權(quán)值}}for(i=jilu->tag+1;i<=2*(jilu->tag)-1;i++){min_2(ht,i-1,&tag1,&tag2)；需找權(quán)值小兩個父母為0結(jié)點 ht[tag1].parent=i; ht[tag2].parent=i;ht[i].Lchild=tag1; ht[i].Rchild=tag2; ht[i].weight=ht[tag1].weight+ht[tag2].weight;}}voidbianma(jilunode*jilu,hnht,Hcodehc,intn)//哈夫曼樹建完后，對葉{子結(jié)點逐個編碼 char*cd; intstart,i,p,c; cd=(char*)malloc((n+1)*sizeof(char))；//申請存儲字符暫時空間 cd[n-1]='\0'；//加結(jié)束標志 for(i=1;i<=n;i++) { start=n-1; c=i; p=ht[i].parent; while(p!=0) { --start; if(ht[p].Lchild==c) cd[start]='1'；//結(jié)點在左邊置1 if(ht[p].Rchild==c) cd[start]='0'；//結(jié)點在右邊置0 c=p; p=ht[p].parent; } printf("%c編碼為：%s\n",jilu->b[i].a,&cd[start]); hc[i]=(char*)malloc((n-start)*sizeof(char))；//為字符數(shù)組分派空間 strcpy(hc[i],&cd[start]);//將暫時空間中編碼復(fù)制到字符數(shù)組中 } free(cd)；//釋放暫時空間}voidbianmabaocun(Hcodehc,jilunode*jilu)//將原文以編碼形式保存到{文獻yiwen中 inti,j; FILE*fp; if((fp=fopen("yiwen","wb"))==NULL)//以寫方式打開文獻 { printf("Cannotopenfile\n"); exit(0)；//文獻打開失敗退出 } for(i=0;i<=N&&CH[i]!='^';i++) { for(j=1;j<=jilu->tag;j++) if(CH[i]==jilu->b[j].a) { fputs(hc[j],fp)；//將文獻中字符輸出到字符數(shù)組中 printf("%s",hc[j]); } } fclose(fp)；//關(guān)閉文獻}voidyiwen(Hcodehc,jilunode*jilu)//讀取yiwen中編碼，并將其翻譯{為原文存儲到字符數(shù)組YW[N]中 inttag1,tag2,i,j,s=0; FILE*fp；//文獻指針 char*c; if((fp=fopen("yiwen","rb"))==NULL)//以只讀方式打開文獻 { printf("cannotopenfile\n"); exit(0); } while(!feof(fp)) { tag1=1；//結(jié)束for循環(huán)輔助標志 tag2=1；//結(jié)束for循環(huán)輔助標志 c=(char*)malloc(200*sizeof(char)); for(i=0;i<200&&tag1;i++) { c[i]=fgetc(fp)；//將文獻中字符輸出到數(shù)組中 c[i+1]='\0'；//加結(jié)束標志 for(j=1;(j<=jilu->tag)&&tag2;j++) { if(strcmp(hc[j],c)==0)//將編碼與原文字符匹配 { YW[s]=jilu->b[j].a；//匹配成功后將字符保存到數(shù)組YW中 tag1=0; s++; free(c)；//釋放暫時字符存儲空間 tag2=0; } } } } YW[s]='\0';}voidbaocunyiwen()//將翻譯譯文保存到文獻textfile中{ inti; FILE*fp; if((fp=fopen("textfile","wb"))==NULL) { printf("Cannotopenfile\n"); exit(0); } for(i=0;YW[i]!='\0';i++) { fputc(YW[i],fp)；//將數(shù)組中字符保存到文獻中 putchar(YW[i]); } fclose(fp)；//關(guān)閉文獻}voidduquyiwen()//從文獻textfile中讀取譯文{ charch;FILE*fp; if((fp=fopen("textfile","rb"))==NULL)//以只讀方式打開文獻 { printf("cannotopenfile\n"); exit(0); } while(!feof(fp)) { ch=fgetc(fp)；//將文獻中字符賦給字符變量ch printf("%c",ch)；//輸出字符 }fclose(fp)；//關(guān)閉文獻}voidduquyuanwen()//從文獻yuanwen中讀取原文{ charch;FILE*fp; if((fp=fopen("yuanwen","rb"))==NULL)//以只讀方式打開文獻 { printf("cannotopenfile\n"); exit(0); } while(!feof(fp)) { ch=fgetc(fp)；//將文獻中字符賦給字符變量ch printf("%c",ch)；//輸出字符 }fclose(fp)；//關(guān)閉文獻}voidduqubianma()//從文獻yiwen中讀取原文{ charch;FILE*fp; if((fp=fopen("yiwen","rb"))==NULL) { printf("cannotopenfile\n"); exit(0); } while(!feof(fp)) { ch=fgetc(fp)；//將文獻中字符賦給字符變量ch printf("%c",ch)；//輸出字符 }fclose(fp)；//關(guān)閉文獻}voidmain(){ inta,c,tep=1;hnhumtree；//定義用三叉鏈表方式實現(xiàn)哈夫曼樹 Hcodehc；//定義存儲哈夫曼字符編碼串頭指針數(shù)組jilunodeji；//定義存儲字符種類數(shù)量棧jilunode*jilu;jilu=&ji；//取指針jilu->tag=0；//字符種類數(shù)標志初始化 while(tep) { printf("(*^__^*)哈夫曼編碼系統(tǒng)歡迎您(*^__^*)\n");printf("*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n");printf("1——創(chuàng)立存貯原文獻文獻\n"); printf("2——輸入原文\n");printf("3——對原文編碼\n"); printf("4——對編碼譯碼\n");printf("5——輸出原文\n"); printf("6——輸出譯碼\n");printf("7——輸出譯文\n"); printf("8——退出\n"); printf("注意：如果您未創(chuàng)立原文獻原文操作，請不要進行后續(xù)項操作！\n"); printf("*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n"); printf("請輸入服務(wù)選項（-8）:"); scanf("%d",&a); getchar(); switch(a) { case1: jianliwenjian()；//建立存儲字符文獻 printf("與否繼續(xù)？（.YES2，NO）："); scanf("%d",&c); getchar(); if(c==1)tep=1; else tep=0;system("cls"); break; case2: system("cls");luruyuanwen()；//將原文錄入到文獻中 printf("\n注意：原文獻將保存在名稱為“yuanwen”文獻中！\n"); printf("與否繼續(xù)？（.YES2，NO）："); scanf("%d",&c); getchar(); if(c==1)tep=1; else tep=0;system("cls"); break; case3:chuangjian(jilu,humtree)；//創(chuàng)立哈夫曼樹 printf("\n各字符編碼成果為：\n");bianma(jilu,humtree,hc,jilu->tag)；//對哈夫曼樹葉子結(jié)點編碼 printf("原文編碼為：\n");printf("*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n"); bianmabaocun(hc,jilu)；//保存編碼 printf("\n*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*^*\n"); printf("\n注意：原文編碼將保存在以名稱為“yiwen”文獻中！\n");printf("與否繼續(xù)？（.YES2，NO）："); scanf("%d",&c); getchar(); if(c==1)tep=1; else tep=0;system("cls"); break; case4: system("cls"); printf("編碼相應(yīng)譯文為：\n");