數(shù)據(jù)結(jié)構(gòu)綜合實驗報告

1、實驗報告課程名稱 數(shù)據(jù)結(jié)構(gòu)B實驗學(xué)期 2018 至 2019 學(xué)年 第 一 學(xué)期學(xué)生所在系部年級 專業(yè)班級學(xué)生姓名 學(xué)號 2017任課教師實驗成績計算機學(xué)院制教育資料華北科技學(xué)院計算機學(xué)院綜合性實驗報告數(shù)據(jù)結(jié)構(gòu)課程綜合性實驗報告實驗題目用赫夫曼編碼實現(xiàn)文件壓縮開課實驗室:軟件工程實驗室2018年11月23日第3頁一、實驗?zāi)康?、了解文件的概念。2、掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲結(jié)構(gòu)及遍歷算法。5、利用Huffman樹及Huffman編碼，掌握實現(xiàn)文件壓縮的一般原理。二、設(shè)備與環(huán)境微型計算機、Windows系列操作系統(tǒng)、Visual

2、 C+6.0軟件三、實驗內(nèi)容1、實驗內(nèi)容根據(jù)ascii碼文件中各ascii字符出現(xiàn)的頻率情況創(chuàng)建 Haffman樹，再將各字符對應(yīng)的 哈夫曼編碼寫入文件中，實現(xiàn)文件壓縮。2、實驗要求a、用C語言編程實現(xiàn)上述實驗內(nèi)容中的結(jié)構(gòu)定義和算法。b、要有main()函數(shù)，并且在main()函數(shù)中使用檢測數(shù)據(jù)調(diào)用上述算法。3、最后結(jié)果輸出。要求：輸出格式要界面直觀、清晰大方、格式規(guī)范。四、實驗方法或步驟1、實驗的預(yù)備知識(1)構(gòu)造Hufffman樹的方法一Hufffman算法構(gòu)造Huffman樹步驟：I .根據(jù)給定的n個權(quán)值w1,w2, wn,構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj。II .在森林中選取

3、兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點 權(quán)值為其左右子樹根結(jié)點權(quán)值之和。III .在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。IV .重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。(2) Huffman編碼：數(shù)據(jù)通信用的二進制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“ 1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列。(3)二叉樹的存儲結(jié)構(gòu)typedef struct nodedatatype data;struct no

4、de *lchild, *rchild;BtTree2、設(shè)計思想(1)實現(xiàn)的Haffman樹的結(jié)構(gòu)及創(chuàng)建算法，有兩點說明：a) 這里的Haffman樹采用的是基于數(shù)組的帶左右兒子結(jié)點及父結(jié)點下標(biāo)作為存儲結(jié)點的二 叉樹形式，這種空間上的消耗帶來了算法實現(xiàn)上的便捷。b)由于對于最后生成的Haffman樹，其所有葉子結(jié)點均為從一個內(nèi)部樹擴充出去的，所以，當(dāng)外部葉子結(jié)點數(shù)為 m個時，內(nèi)部結(jié)點數(shù)為 m-1,整個Haffman樹的需要的結(jié)點數(shù)為 2m-1。編碼部分(2)壓縮過程的實現(xiàn)：壓縮過程的流程是清晰而簡單的：1創(chuàng)建Haffman樹 2打開需壓縮文件3將需壓縮文件中的每個ascii碼對應(yīng)的haffma

5、n編碼按bit單位輸出4文件壓縮結(jié)束。其中，步驟1和步驟3是壓縮過程的關(guān)鍵。步驟1:這里所要做工作是得到Haffman數(shù)中各葉子結(jié)點字符出現(xiàn)的頻率并進行創(chuàng)建。統(tǒng)計字符出現(xiàn)的頻率可以有很多方法：如每次創(chuàng)建前掃描被創(chuàng)建的文件，“實時”的生成各字符的出現(xiàn)頻率；或者是創(chuàng)建前即做好統(tǒng)計。本文采用后一種的方案，統(tǒng)計了十篇不同的文章中字符出現(xiàn)的頻率。當(dāng)前，也可以根據(jù)被壓縮文件的特性有針對性的進行統(tǒng)計，如要壓縮C語言的源文件，則可事先對多篇C語言源文件中出現(xiàn)的字符進行統(tǒng)計，這樣，會創(chuàng)建出高度相對較“矮”的Haffman樹，從而提高壓縮效果。步驟3:將需壓縮文件中的每個ascii碼對應(yīng)的haffman編碼按bi

6、t單位輸出，這是本壓縮程序中最關(guān)鍵的部分。這里涉及“轉(zhuǎn)換”和“輸出”兩個關(guān)鍵步驟：“轉(zhuǎn)換”部分大可不必去通過遍歷Haffman樹來找到每個字符對應(yīng)的哈夫曼編碼，可以將每個Haffman碼值及其對應(yīng)的ascii碼存放于如下所示的結(jié)構(gòu)體中：typedef structchar asciiCode;unsigned long haffCode;int haffCodeLen;HaffCode;創(chuàng)建由該結(jié)構(gòu)體結(jié)點所組成的，長度為128的一維數(shù)組codeList128華北科技學(xué)院計算機學(xué)院綜合性實驗報告且 codeList中的下標(biāo)和asciiCode滿足下面的順序存放關(guān)系:codeListi.ascii

7、Code=i;這樣的話，查找某個字符inChar的haffman編碼的工作便變彳#相當(dāng)輕松了，如下：sHaffCode=codeListinChar.haffCode;數(shù)組codeList128的創(chuàng)建可以采用某種遍歷方式下的按找到的字符進行置數(shù)的方式，十分的方便。/*Code2:codeList的創(chuàng)建算法，采用前序遍歷的方式進行創(chuàng)建*/void preHaffListMake(PHtTree inTree,int rootIndex,unsigned long youBiao,int sDepth,HaffCode* inList)if(inTree->htrootIndex.llink

8、Index=-1&&inTree->htrootIndex.rlinkIndex=-1)inListinTree->htrootI.haffCode=youBiao;inListinTree->htrootI.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree->htrootIndex.llinkIndex,youBiao<<1,sDepth+1,inList);preHaffListMake(inTree,inTree->htrootIndex.

9、rlinkIndex,(youBiao<<1)|0x01,sDepth+1,i nList);輸出”部分是最重要的部分，也是最易出錯的部分。這里，涉及到 C語言的位操作，要求這個算法能處理好以下幾個問題：1)每個字符所對應(yīng)的haffCode的比特位長度由523位不等長，不可少輸，多輸，輸錯任何一位， 后一個字符的haffCode要緊跟在前一個字符的 haffCode后面。2)最后一個字符要能合理的結(jié)束。這主要是為解壓縮考慮的，比如，在最后一個要輸出的haffCode的最后一位，它恰好是位于最后一個有效字符的第一位，剩下的七個比特位是要用無效的haffCode加以填充的。否則，如果填

10、充的haffCode亦為某個ascii字符的haffCode時，那么在解壓縮時，則該在原被 壓縮文件中不存在的字符便會無中生有的在解壓后的文件中出現(xiàn)，這顯然是不正確的，應(yīng)在程序中加以處理。編碼部分的流程如圖3-1所示：第4頁華北科技學(xué)院計算機學(xué)院綜合性實驗報告第14頁udufi U, *ctiunL U上八域l筆正胖仙卜rhaftBden已輸對立+curt 加仁品.li 1個字St則儆招1網(wǎng)的處理#include <stdio.h> #include <string.h> #include <stdlib.h> #include <conio.h>

11、; struct headunsigned char b;/記錄字符在數(shù)組中的位置long count;/字符出現(xiàn)頻率（權(quán)值）long parent,lch,rch;/定義哈夫曼樹指針變量char bits256;/定義存儲哈夫曼編碼的數(shù)組header512,tmp;/*壓縮*/void compress()char filename255,outputfile255,buf512;unsigned char c;long i,j,m,n,f;long min1,pt1,flength,length1,length2;double div;FILE *ifp,*ofp;/printf(&quo

12、t;t請您輸入需要壓縮的文件：");/gets(filename);strcpy(filename,"yuan.txt");ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打開失敗！nn");return;/printf("t請您輸入壓縮后的文件名：");/gets(outputfile);strcpy(outputfile,"yuanys.txt");/ofp=fopen(strcat(outpufile,".hub&quo

13、t;),"wb");ofp=fopen(outputfile,"wb");if(ofp=NULL)printf("nt壓縮文彳失??！nn");return;flength=0;while(!feof(ifp)字符重復(fù)出現(xiàn)頻率+1字符出現(xiàn)原文件長度+1原文件長度用作求壓縮率的分母fread(&c,1,1,ifp);headerc.count+; /flength+; /flength-;length1=flength; /headerc.count-;for(i=0;i<512;i+)if(headeri.count!=0

14、)headeri.b=(unsigned char)i;/*將每個哈夫曼碼值及其對應(yīng)的ASCII碼存放在一維數(shù)組headeri中，且編碼表中的下標(biāo)和ASCII碼滿足順序存放關(guān)系*/elseheaderi.b=0;headeri.parent=-1;headeri.lch=headeri.rch=-1; /對結(jié)點進行初始化for(i=0;i<256;i+) /根據(jù)頻率(權(quán)值)大小，對結(jié)點進行排序，選擇較小的結(jié)點進樹for(j=i+1;j<256;j+)if(headeri.count<headerj.count)tmp=headeri;headeri=headerj;heade

15、rj=tmp;for(i=0;i<256;i+)if(headeri.count=0)break;n=i; /外部葉子結(jié)點數(shù)為n個時，內(nèi)部結(jié)點數(shù)為 n-1 ,整個哈夫曼樹的需要的結(jié)點數(shù)為 2*n-1.m=2*n-1;for(i=n;i<m;i+) /構(gòu)建哈夫曼樹min1=999999999; 預(yù)設(shè)的最大權(quán)值，即結(jié)點出現(xiàn)的最大次數(shù)for(j=0;j<i;j+)if(headerj.parent!=-1)/parent!=-1說明該結(jié)點已存在哈夫曼樹中,M出循環(huán)重新選擇新結(jié)點*/continue;if(min1>headerj.count) pt1=j;min1=heade

16、rj.count;continue;headeri.count=headerpt1.count;headerpt1.parent=i; /依據(jù)parent域值(結(jié)點層數(shù))確定樹中結(jié)點之間的關(guān)系headeri.lch=pt1; /計算左分支權(quán)值大小min1=999999999;for(j=0;j<i;j+)if(headerj.parent!=-1)continue;if(min1>headerj.count) pt1=j；min1=headerj.count;continue;headeri.count+=headerpt1.count;headeri.rch=pt1; /計算右分

17、支權(quán)值大小headerpt1.parent=i;for(i=0;i<n;i+) /哈夫曼無重復(fù)前綴編碼f=i;headeri.bits0=0; /根結(jié)點編碼 0while(headerf.parent!=-1)j=f;f=headerf.parent;if(headerf.lch=j) /置左分支編碼 0j=strlen(headeri.bits);memmove(headeri.bits+1,headeri.bits,j+1);/依次存儲連接“ 0” “1”編碼headeri.bits0='0'else /置右分支編碼1j=strlen(headeri.bits);me

18、mmove(headeri.bits+1,headeri.bits,j+1);headeri.bits0='1'fseek(ifp,0,SEEK_SET); /從文件開始位置向前移動0字節(jié)，即定位到文件開始位置fwrite(&flength,sizeof(int),1,ofp);/*用來將數(shù)據(jù)寫入文件流中，參數(shù) flength 指向欲寫入的數(shù)據(jù)地址，總共寫入的字符數(shù)以參數(shù)size*int來決定，返回實際寫入的int數(shù)目1*/fseek(ofp,8,SEEK_SET);buf0=0; /定義緩沖區(qū)，它的二進制表示00000000f=0;pt1=8;/*假設(shè)原文件第一個字符

19、是"A" , 8位2進制為01000001 ,編碼后為0110識別編碼第一個'0',那么我們就可以將其左移一位，看起來沒什么變化。下一個是1',應(yīng)該|1 ,結(jié)果00000001同理4位都做完，應(yīng)該是 00000110,由于字節(jié)中的8位并沒有全部用完，我們應(yīng)該繼續(xù)讀下 一個字符，根據(jù)編碼表繼續(xù)拼完剩下的4位，如果字符的編碼不足4位，還要繼續(xù)讀一個字符，如果字符編碼超過4位，那么我們將把剩下的位信息拼接到一個新的字節(jié)里*/while(!feof(ifp)c=fgetc(ifp);f+；for(i=0;i<n;i+)if(c=headeri.b)br

20、eak;strcat(buf,headeri.bits);j=strlen(buf);c=0;while(j>=8) /對哈夫曼編碼位操作進行壓縮存儲for(i=0;i<8;i+)if(bufi='1')c=(c<<1)|1;elsec=c<<1;fwrite(&c,1,1,ofp);pt1+; 統(tǒng)計壓縮后文件的長度strcpy(buf,buf+8); /一個字節(jié)一個字節(jié)拼接j=strlen(buf);if(f=flength) break;if(j>0) /對哈夫曼編碼位操作進行壓縮存儲strcat(buf,"000

21、00000");for(i=0;i<8;i+)if(bufi='1')c=(c<<1)|1;elsec=c<<1;fwrite(&c,1,1,ofp);pt1+;fseek(ofp,4,SEEK_SET);fwrite(&pt1,sizeof(long),1,ofp);fseek(ofp,pt1,SEEK_SET);fwrite(&n,sizeof(long),1,ofp);for(i=0;i<n;i+)fwrite(&(headeri.b),1,1,ofp);c=strlen(headeri.bit

22、s);fwrite(&c,1,1,ofp);j=strlen(headeri.bits);if(j%8!=0) /若存儲的位數(shù)不是8的倍數(shù)，則補for(f=j%8;f<8;f+)strcat(headeri.bits,"0");while(headeri.bits0!=0)8位，則對有效位數(shù)左移實現(xiàn)兩字符0” “1” 值把字符的編碼按原先存儲順序c=0;for(j=0;j<8;j+) /字符的有效存儲不超過編碼的連接if(headeri.bitsj='1')c=(c<<1)|1; /|1不改變原位置上的“elsec=c<

23、<1;strcpy(headeri.bits,headeri.bits+8); /連接fWrite(&c,1,1,ofp);length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /計算文件的壓縮率fclose(ifp);fclose(ofp);printf("nt壓縮文彳成功！n");printf("t 壓縮率為 f%n'n",div*100);/*解壓縮*/void uncompress。char filename255,outputfile255,b

24、uf255,bx255;unsigned char c;long i,j,m,n,f,p,l;long flength;FILE *ifp,*ofp;/printf("t請您輸入需要解壓縮的文件：")；/gets(filename);strcpy(filename,"yuanys.txt");ifp=fopen(strcat(filename,".hub"),"rb");ifp=fopen(filename,"rb");if(ifp=NULL)printf("nt文件打開失敗！n&qu

25、ot;);return;/printf("t請您輸入解壓縮后的文件名：");/gets(outputfile);strcpy(outputfile,"yuanjy.txt");ofp=fopen(outputfile,"wb");if(ofp=NULL)printf("nt解壓縮文件失?。");return;fread(&flength,sizeof(long),1,ifp); /讀取原文件長度，對文件進行定位fread(&f,sizeof(long),1,ifp);fseek(ifp,f,SEE

26、K_SET);fread(&n,sizeof(long),1,ifp);for(i=0;i<n;i+)fread(&headeri.b,1,1,ifp);fread(&c,1,1,ifp);p=(long)c; 讀取原文件字符的權(quán)值headeri.count=p;headeri.bits0=0;if(p%8>0)m=p/8+1;elsem=p/8;for(j=0；j<m；j+)fread(&c,1,1,ifp);f=c;itoa(f,buf,2); 將f轉(zhuǎn)換為二進制表示的字符串f=strlen(buf);for(l=8;l>f;l-)st

27、rcat(headeri.bits,"0");strcat(headeri.bits,buf);headeri.bitsp=0;華北科技學(xué)院計算機學(xué)院綜合性實驗報告for(i=0;i<n;i+) /根據(jù)哈夫曼編碼的長短，對結(jié)點進行排序for(j=i+1;j<n；j+)if(strlen(headeri.bits)>strlen(headerj.bits)tmp=headeri;headeri=headerj;headerj=tmp;p=strlen(headern-1.bits);fseek(ifp,8,SEEK_SET);m=0;bx0=0;while(

28、1) /通過哈夫曼編碼的長短，依次解碼，從原來的位存儲還原到字節(jié)存儲while(strlen(bx)<(unsigned int)p)fread(&c,1,1,ifp);f=c;itoa(f,buf,2);f=strlen(buf);for(l=8;l>f;l-) 在單字節(jié)內(nèi)對相應(yīng)位置補0strcat(bx,"0");strcat(bx,buf);for(i=0;i<n;i+)if(memcmp(headeri.bits,bx,headeri.count)=0) break;第15頁華北科技學(xué)院計算機學(xué)院綜合性實驗報告strcpy(bx,bx+he

29、aderi.count); /*從壓縮文件中的按位存儲還原到按字節(jié)存儲字符，字符位置不改變*/c=headeri.b;fwrite(&c,1,1,ofp);m+; 統(tǒng)計解壓縮后文件的長度if(m=flength)break; /flength是原文件長度fclose(ifp);fclose(ofp);printf("nt解壓縮文件成功！n");if(m=flength) /對解壓縮后文件和原文件相同性比較進行判斷(根據(jù)文件大小)printf("t解壓縮文件與原文件相同！nn");elseprintf("t解壓縮文件與原文件不同！nn");/*主函數(shù)*/void main()int c;w