哈弗曼壓縮軟件(數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告附源程序)

《哈弗曼壓縮軟件(數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告附源程序)》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈弗曼壓縮軟件(數(shù)據(jù)結(jié)構(gòu)試驗(yàn)報(bào)告附源程序)（15頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 題 目： 基于哈夫曼編碼的壓縮軟件 系部名稱 ： 計(jì)算機(jī) 專業(yè)名稱 ： 軟件工程 班 級(jí) ： 0802 學(xué)號(hào) ： XXXXXX 學(xué)生姓名 ： 稻草人 指導(dǎo)教師 ： XXXXX 時(shí)間 ： 2010 XX--2010 YY 一、?課程設(shè)計(jì)目的 通過運(yùn)用哈夫曼樹的知識(shí)編寫該壓縮與解壓軟件，能使學(xué)生將所學(xué) 的理論知識(shí)應(yīng)用起來，有效地運(yùn)用到解決實(shí)際問題中去，提高學(xué)生的自

2、 身的編程能力，從而達(dá)到學(xué)以致用的目的。 二、課程設(shè)計(jì)內(nèi)容 1．應(yīng)用系統(tǒng)分析，建立該系統(tǒng)的功能模塊框圖及界面的組織和設(shè)計(jì)； 2．分析系統(tǒng)中的各個(gè)函數(shù)及它們之間的關(guān)系； 3．根據(jù)問題描述，設(shè)計(jì)系統(tǒng)的結(jié)構(gòu)體及各個(gè)函數(shù)； 4．設(shè)計(jì)哈弗曼樹的構(gòu)造算法和哈弗曼編碼算法； 5．完成設(shè)計(jì)的系統(tǒng)各個(gè)應(yīng)用模塊； 6．將各個(gè)模塊整合進(jìn)行功能測(cè)試。 三、需求分析 哈弗曼壓縮軟件 1.需求分析目的 為明確軟件需求、安排項(xiàng)目規(guī)劃與進(jìn)度、組織軟件開發(fā)與測(cè)試，供設(shè)計(jì)人

3、員、開發(fā)人員參考。 2. 項(xiàng)目開發(fā)計(jì)劃 時(shí)間 開發(fā)內(nèi)容 6月22日 讀取文本文件，并統(tǒng)計(jì)文件中字母?jìng)€(gè)數(shù) 6月23日 建立huffman樹對(duì)文件，進(jìn)行huffman編碼 6月24日 壓縮 6月25日 解壓縮 3. 任務(wù)目標(biāo) 能比較完善的對(duì)txt文件進(jìn)行壓縮和解壓縮。 4. 數(shù)據(jù)字典 名稱：字符頻率 別名：weight 描述：讀取文本文件，并統(tǒng)計(jì)文件中字母?jìng)€(gè)數(shù) 定義：字符頻率 = 字符 + 數(shù)量 名稱：結(jié)點(diǎn) 別名：HTNode 描述：建立huffman樹的葉子和非葉子結(jié)點(diǎn) 定義：結(jié)點(diǎn) = 數(shù)量

4、 + 字符 + 雙親結(jié)點(diǎn) + 左孩子結(jié)點(diǎn) + 右孩子結(jié)點(diǎn) 位置：編碼文件 5. 功能劃分 n 壓縮 n 解壓縮 四、概要設(shè)計(jì) 哈弗曼壓縮軟件 1 建立哈夫曼樹。根據(jù)哈夫曼編碼技術(shù)，可以將已經(jīng)給出的字母的使用頻率建立一個(gè)哈夫曼樹，即以二叉樹的形式將英文字母和空格存儲(chǔ)。 ? 2 編碼。利用二叉樹的遍歷知識(shí)，左孩子用“0”表示，右孩子用“1”表示，將輸入的一組英文句子進(jìn)行編碼。 ?3測(cè)試和輸出。程序要求的測(cè)試的英文句子是：“knowledge is power”，輸出每一個(gè)字母然后給出相應(yīng)的哈夫曼編碼。本程序輸入字母以“#”結(jié)束。 ? 4譯碼。本程

5、序要求對(duì)已編碼的數(shù)字能夠給以反編碼。 .函數(shù)調(diào)用示意圖 Main( ) Compression( ) Decompression( ) Clock ( ) Initfromfile( ) Htcreat( ) Hccreat ( ) Convertfile( ) Decompressionfile( ) Clock ( ) Exit( ) 六、調(diào)試情況，設(shè)計(jì)技巧及體會(huì) 1．測(cè)試結(jié)論 u 能較好地進(jìn)行壓縮和解壓 u 不足的是對(duì)最后所補(bǔ)的0未處理，解壓會(huì)多出

6、幾個(gè)字符。 2. 設(shè)計(jì)技巧 本軟件可對(duì)字母、漢字可以實(shí)現(xiàn)共同壓縮，壓縮率在50%以上，壓縮后對(duì)哈夫曼樹進(jìn)行保存，以便后面解壓，對(duì)葉子結(jié)點(diǎn)只保存其字符、左孩子、右孩子，對(duì)非葉子結(jié)點(diǎn)保存左孩子和右孩子。解壓時(shí)從根結(jié)點(diǎn)開始，利用哈夫曼樹進(jìn)行解壓，遇到0，找左孩子，遇到1找右孩子，到葉子結(jié)點(diǎn)時(shí)，輸出字符。 3．心得體會(huì)： 通過這次課題實(shí)驗(yàn)的程序?qū)嵺`，我實(shí)在獲益匪淺！數(shù)據(jù)結(jié)構(gòu)是上個(gè)學(xué)期開展的一門學(xué)科，學(xué)習(xí)好這門學(xué)科是非常重要的，在以后的程序設(shè)計(jì)方面這門學(xué)科能給我們很大的幫助。同時(shí)，學(xué)習(xí)這門學(xué)科也是艱辛的，因?yàn)樗容^難懂，這不僅需要我們要發(fā)揮我們的聰明才志，還需要我們?cè)诓粩?/p>

7、的實(shí)踐中領(lǐng)悟。 這次的程序設(shè)計(jì)對(duì)我來說無疑是一個(gè)具大的考驗(yàn)，從接起課題后，我就一直為實(shí)現(xiàn)程序而努力，翻閱相關(guān)書籍、在網(wǎng)上查找資料。因?yàn)殚_始時(shí)基礎(chǔ)不是很好，過程中遇到了不少的阻礙，編寫程序的進(jìn)度也比較慢。雖然如此，但是通過自己的努力與老師的指導(dǎo)，我對(duì)這次實(shí)驗(yàn)的原理有了一定的理解，通過參照從網(wǎng)上找到的源程序，終于在其它源程序的基礎(chǔ)下寫出了本次實(shí)驗(yàn)的核心算法，并使其能夠正常的運(yùn)行。 這一個(gè)多月的設(shè)計(jì)工作，讓我體會(huì)到了作為一個(gè)編程人員的艱難，一個(gè)算法到具體實(shí)現(xiàn)，再到應(yīng)用層面的開發(fā)是需要有一段較長(zhǎng)的路要走的，不是一朝一夕就可以實(shí)現(xiàn)的，而且在編好程序后，編程人員還要花很多的時(shí)間去完善它，其中包含的心酸

8、，外人是不會(huì)明白的。 非常感謝在背后一直給我指導(dǎo)的老師和同學(xué)，他們的支持和鼓勵(lì)讓我在遇到挫折時(shí)能夠站起來戰(zhàn)勝它，也讓我走到了今天這一步，完成了實(shí)驗(yàn)的設(shè)計(jì)。今后，我會(huì)更加努力的學(xué)習(xí)專業(yè)知識(shí)，提高自我的能力。 七、參考文獻(xiàn) 《c語言程序設(shè)計(jì)》譚浩強(qiáng)主編 八、附錄：源代碼 #include #include #include #include #include typedef struct word { char word[3]; unsigned long tim

9、es; struct word *next; }word,*word_list; typedef struct Tnode { unsigned long weight; char word[3]; long parent,lchild,rchild; }Tnode,HuffTree; HuffTree ht[5000]; char *hc[5000]; int n=0; void stat(word_list head,char *filename) { FILE *fp; char ch[3]; int fla

10、g=0; word *p,*q,*s; fp=fopen(filename,"rt"); if(fp==NULL) printf("\n無法打開要壓縮的文件,或該文件不存在!"); p=head; while((ch[0]=fgetc(fp))!=EOF) { if(ch[0]<0||ch[0]>254) { ch[1]=fgetc(fp); ch[2]='\0'; } else ch[1]='\0'; if(ch[0]==10) strcpy(ch

11、,"-n"); if(ch[0]==32) strcpy(ch,"-t"); for(q=head->next;q!=NULL;q=q->next) { if(!strcmp(q->word,ch)) { (q->times)++; flag=1; break; } } if(flag==0) { s=(word *)malloc(sizeof(word)); strcpy(s-

12、>word,ch); s->times=1; p->next=s; p=s; p->next=NULL; ++n; } flag=0; } p->next=NULL; fclose(fp); return; } void protect1(char *filename) { FILE *fp2; char ch[26]="編碼："; int i; strcat(ch,filename); fp2=fopen(ch,"wt"); if(fp2==NULL)

13、 { printf("\n編碼文件無法創(chuàng)建!"); exit(1); } for(i=1;i<=2*n-1;i++) { fprintf(fp2,"%s %ld %ld %ld\n",ht[i].word,ht[i].parent,ht[i].lchild,ht[i].rchild); } fclose(fp2); return; } void out(char *filename) { FILE *fp2; char ch[26]="編碼："; int i; strcat(ch,filename);

14、 fp2=fopen(ch,"rt"); if(fp2==NULL) { printf("\n編碼文件無法打開!"); exit(1); } for(i=1;!feof(fp2);i++) { fscanf(fp2,"%s %ld %ld %ld\n",ht[i].word,&ht[i].parent,&ht[i].lchild,&ht[i].rchild); n=i; } fclose(fp2); return; } void sort() { int i,j; unsigned

15、long min; char ch[3]; for(i=1;iht[j].weight) { min=ht[j].weight; ht[j].weight=ht[i].weight; ht[i].weight=min; strcpy(ch,ht[i].word); strcpy(ht[i].word,ht[j].word); strcpy(ht[j].word,ch)

16、; } } return; } void select(int t,int *s1,int *s2) { int i; unsigned long min1,min2; min1=min2=4294967295; *s1=*s2=0; for(i=1;i<=n;i++) { if(ht[i].parent==0) { if((ht[i].parent==0)&&(ht[i+1].parent==0)&&i+1<=n) { min1=ht[i].weight; *s1=i; m

17、in2=ht[i+1].weight; *s2=i+1; break; } else { min1=ht[i].weight; *s1=i; break; } } } for(i=n+1;i<=t;i++) { if(ht[i].weight

18、next;i<=n&&p!=NULL;i++,p=p->next) { ht[i].weight=p->times; strcpy(ht[i].word,p->word); ht[i].parent=ht[i].rchild=ht

19、[i].lchild=0; } m=2*n-1; for(i=n+1;i<=m;i++) { ht[i].parent=ht[i].rchild=ht[i].lchild=ht[i].weight=0; } sort(); for(i=n+1;i<=m;i++) { select(i-1,&s1,&s2); strcpy(ht[i].word,"無"); ht[i].weight=ht[s1].weight+ht[s2].weight; ht[s2].parent=ht[s1].p

20、arent=i; ht[i].lchild=s2; ht[i].rchild=s1; } return; } void ctrHuffmancode() { char *cd; int c,p,start,i; cd=(char *)malloc((n+1)*sizeof(char)); cd[n]='\0'; for(i=1;i<=n;i++) { start=n; c=i; p=ht[i].parent; while(p!=0) { --start; if(ht[p].lc

21、hild==c) cd[start]='0'; else if(ht[p].rchild==c) cd[start]='1'; c=p; p=ht[p].parent; } hc[i]=(char *)malloc((n-start)*(sizeof(char))); strcpy(hc[i],&cd[start]); } free(cd); return; } void compress(char *filename,char *filename1) { FILE *fp1,*fp2; int t,i=0,j

22、=0,sum=0; char ch[3], tr[8]; unsigned char c; fp1=fopen(filename,"rt"); if(fp1==NULL) { printf("\n無法打開 %s 文件,或該文件不存在!",filename); exit(0); } fp2=fopen(filename1,"wb"); if(fp2==NULL) { printf("\n無法創(chuàng)建 %s 文件!",filename1); exit(0); } system("cls"); printf("

23、\n\n\n\n\n\n\n\n 壓縮中，請(qǐng)稍候..."); while((ch[0]=fgetc(fp1))!=EOF) { if(ch[0]<0||ch[0]>254) { ch[1]=fgetc(fp1); ch[2]='\0'; } else ch[1]='\0'; for(t=1;t<=n;t++) { if(ch[0]==10&&ch[1]=='\0') strcpy(ch,"-n");

24、if(ch[0]==32&&ch[1]=='\0') strcpy(ch,"-t"); if(!strcmp(ht[t].word,ch)) { while(j<=7) { for(;*(hc[t]+i)!='\0';i++,j++) { tr[j]=*(hc[t]+i); if(j==7) { sum=(tr[7]-48)*1+(tr[6]-48)*2+(tr[5]-48)*4+(tr[4]-48)*

25、8+(tr[3]-48)*16+(tr[2]-48)*32+(tr[1]-48)*64+(tr[0]-48)*128; c=(unsigned char)sum; fputc(c,fp2); j=0; i++; break; } } if(*(hc[t]+i)=='\0') { i=0; t=n+1; break; } }

26、 } } } if(j<=7&&j!=0) { for(;j<=7;j++) { tr[j]=48; if(j==7) { sum=(tr[7]-48)*1+(tr[6]-48)*2+(tr[5]-48)*4+(tr[4]-48)*8+(tr[3]-48)*16+(tr[2]-48)*32+(tr[1]-48)*64+(tr[0]-48)*128; c=(unsigned char)sum; fputc(c,fp2); break; } } } fc

27、lose(fp1); fclose(fp2); system("cls"); printf("\n\n\n\n\n\n\n\n 壓縮完成!(按任意鍵返回)\n"); getch(); return; } void re_compress(char *filename1,char *filename2) { int m[8],i=0,j=0,flag=1; HuffTree p; char ch,cha='\t'; unsigned char c; FILE *fp1,*fp2; p=ht[

28、n]; fp1=fopen(filename1,"rb"); if(fp1==NULL) { printf("\n無法打開壓縮文件 %s,或該文件不存在!",filename1); exit(0); } fp2=fopen(filename2,"wt"); if(fp2==NULL) { printf("\n無法創(chuàng)建 %s 文件!",filename2); exit(0); } system("cls"); printf("\n\n\n\n\n\n\n\n 解壓中，

29、請(qǐng)稍候..."); ch=fgetc(fp1); c=(unsigned char)ch; while(!feof(fp1)) { while(flag!=0) { for(i=7;i>=0;i--) { m[i]=c%2; flag=c=c/2; if(i==0||c==0) { break; } } if((unsigned char)ch<128&&(c==0)&&(i!=0)) { for(i=--i;i>=0;i--) { m

30、[i]=0; if(i==0) break; } } for(j=i;j<=7;j++) { if(m[j]==0) p=ht[p.lchild]; else if(m[j]==1) p=ht[p.rchild]; if(p.lchild==0&&p.rchild==0) { if(strcmp(p.word,"-n")==0) { fputc('\n',fp2); } else if(strc

31、mp(p.word,"-t")==0) { fputc(' ',fp2); } else if(strcmp(p.word,"-n")!=0&&strcmp(p.word,"-t")!=0) { fprintf(fp2,"%s",p.word); } p=ht[n]; } } } ch=fgetc(fp1); c=(unsigned char)ch; flag=1; }

32、 fclose(fp1); fclose(fp2); system("cls"); printf("\n\n\n\n\n\n\n\n 解壓完成!(按任意鍵返回)\n"); getch(); return; } main() { char filename[20],filename1[20],filename2[20]; word_list head; char choise; head=(word *)malloc(sizeof(word)); head->next=NULL

33、; while(1) { system("cls"); printf("\n\n\n\n\n ************************************"); printf("\n\n 請(qǐng)選擇您要執(zhí)行的操作:\n\n 1.壓縮文件\n\n 2.解壓文件\n\n

34、 3.退出\n"); printf("\n\n ************************************"); flushall(); choise=getch(); switch(choise) { case '1':{ system("cls"); printf("\n\n\n\n\n\n\n\n 請(qǐng)輸入要壓縮的文件名:"); flushall(); scanf("%s",f

35、ilename); printf("\n\n 請(qǐng)輸入壓縮后的文件名:"); flushall(); scanf("%s",filename1); stat(head,filename); ctrHuffTree(head); ctrHuffmancode(); protect1(filename1); compress(filename,filename1); break; } case '2':{ s

36、ystem("cls"); printf("\n\n\n\n\n 請(qǐng)輸入要解壓的文件名:"); flushall(); scanf("%s",filename1); printf("\n 請(qǐng)輸入解壓后的文件名:"); flushall(); scanf("%s",filename2); out(filename1); re_compress(filename1,filename2); break; } case '3':{ exit(1); printf("\n\n "); } default:{ system("cls"); printf("\n您的選擇有誤!"); break; } } } printf("\nmain over!\n"); return; }