學(xué)長劉林英 數(shù)據(jù)結(jié)構(gòu)實驗報告

華北科技學(xué)院《用哈夫曼編碼實現(xiàn)文件壓縮》實驗報告《用哈夫曼編碼實現(xiàn)文件壓縮》實驗報告課程名稱數(shù)據(jù)結(jié)構(gòu)B實驗學(xué)期2012至2013學(xué)年第二學(xué)期學(xué)生所在系部管理學(xué)院年級B11專業(yè)班級B112學(xué)生姓名劉林英學(xué)號201104064212任課教師蘭蕓實驗成績

一、實驗題目：用哈夫曼編碼實現(xiàn)文件壓縮二、實驗?zāi)康模毫私馕募母拍?。掌握線性鏈表的插入、刪除等算法。3、掌握Huffman樹的概念及構(gòu)造方法。4、掌握二叉樹的存儲結(jié)構(gòu)及遍歷算法。5、利用Huffman樹及Huffman編碼，掌握實現(xiàn)文件壓縮的一般原理。三、實驗設(shè)備與環(huán)境：微型計算機、Windows系列操作系統(tǒng)、VisualC++6.0軟件四、實驗內(nèi)容：根據(jù)ascii碼文件中各ascii字符出現(xiàn)的頻率情況創(chuàng)建Haffman樹，再將各字符對應(yīng)的哈夫曼編碼寫入文件中，實現(xiàn)文件壓縮。五、概要設(shè)計：1、用C語言編程實現(xiàn)上述實驗內(nèi)容中的結(jié)構(gòu)定義和算法。2、要有main()函數(shù)，并且在main()函數(shù)中使用檢測數(shù)據(jù)調(diào)用上述算法。3、實驗完成后撰寫實驗報告，實驗報告的具體格式參見《實驗報告樣例》。4、實驗完成后把打印好的實驗報告以及電子版的實驗報告和源程序一并上交。六、詳細(xì)設(shè)計：實驗的預(yù)備知識（1）構(gòu)造Hufffman樹的方法—Hufffman算法構(gòu)造Huffman樹步驟：根據(jù)給定的n個權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點的二叉樹，令起權(quán)值為wj。在森林中選取兩棵根結(jié)點權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點權(quán)值為其左右子樹根結(jié)點權(quán)值之和。在森林中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。（2）Huffman編碼：數(shù)據(jù)通信用的二進(jìn)制編碼思想：根據(jù)字符出現(xiàn)頻率編碼，使電文總長最短編碼：根據(jù)字符出現(xiàn)頻率構(gòu)造Huffman樹，然后將樹中結(jié)點引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列。（3）二叉樹的存儲結(jié)構(gòu)typedefstructnode{datatypedata;structnode*lchild,*rchild;}BinTree;實驗步驟啟動Visualc++6.0，如下圖所示。(2)鼠標(biāo)單擊“文件”菜單，出現(xiàn)的“New”對話框中，選擇“Projects”標(biāo)簽下的“Win32ConsoleApplication”選項。在“Projectname”中輸入工程名稱，單擊“OK”按鈕，如下圖所示。、單擊“Finish”按鈕，如下圖所示。（4）鼠標(biāo)單擊“OK”按鈕，完成工程的創(chuàng)建，如下圖所示（5）選擇“工程”—〉“添加工程”—〉“New”菜單，在出現(xiàn)的“New”對話框中，選擇“Files”標(biāo)簽，選擇“c++SourceFile”選項，在“File”框中輸入文件名：“hefuman.c”,單擊“OK”按鈕，如下圖所示。（6）輸入代碼，如下圖所示。程序代碼如下：#include<stdio.h>#include<stdlib.h>#include<string.h>#defineMAXLEN10000//MAXLEN最大長度可以設(shè)置，當(dāng)前設(shè)定為10000typedefstruct{intweight,lchild,rchild,parent;//定義權(quán)值、左孩子、右孩子和雙親的結(jié)構(gòu)體charkey;//獲取從鍵盤輸入的字符}htnode;typedefhtnodehfmt[10000];//上限為10000intn;voidchushihuahfmt(hfmttree)//初始化哈弗曼樹{inti;printf("\n請輸入所有的字符總數(shù)n=");scanf("%d",&n);getchar();for(i=0;i<2*n-1;i++)//對結(jié)構(gòu)體進(jìn)行初始化，總的節(jié)點個數(shù)為2*n-1，其中的n為葉子節(jié)點數(shù)目。{tree[i].weight=0;tree[i].lchild=-1;tree[i].rchild=-1;tree[i].parent=-1;}printf("\n");}voidinputweight(hfmttree)//輸入函數(shù)，用于輸入相關(guān)節(jié)點的權(quán)值。{intw;//w表示權(quán)值inti;//控制器chark;//k表示獲取的字符for(i=0;i<n;i++){printf("請輸入第%d個字符:",i+1);//從零開始的，所以為i+1scanf("%c",&k);getchar();tree[i].key=k;printf("請輸入第%d個字符的權(quán)值:",i+1);scanf("%d",&w);getchar();tree[i].weight=w;printf("\n");//換行符}}voidselectmin(hfmttree,inti,int*p1,int*p2)//選中兩個權(quán)值最小的樹{longmin1=999999;longmin2=999999;intj;for(j=0;j<=i;j++)if(tree[j].parent==-1)//確保為無左右子樹的根節(jié)點if(min1>tree[j].weight){min1=tree[j].weight;*p1=j;//選擇最小權(quán)值字符的下標(biāo)返回} for(j=0;j<=i;j++)if(tree[j].parent==-1)if(min2>tree[j].weight&&j!=(*p1))//注意j!=(*p1),這是為了防止重復(fù)訪問同一個根節(jié)點{min2=tree[j].weight;*p2=j;//選擇次小權(quán)值字符的下標(biāo)返回}}voidcreathfmt(hfmttree)//創(chuàng)建哈夫曼樹的函數(shù){inti,p1,p2;chushihuahfmt(tree);inputweight(tree);for(i=n;i<2*n-1;i++)//利用循環(huán)控制構(gòu)造哈弗曼樹{selectmin(tree,i-1,&p1,&p2);//接收傳來的最小和次小的根節(jié)點tree[p1].parent=i;tree[p2].parent=i;//設(shè)置為相同的雙親節(jié)點tree[i].lchild=p1;//分別賦值左右孩子的權(quán)值和結(jié)構(gòu)體的其他組成要素tree[i].rchild=p2;tree[i].weight=tree[p1].weight+tree[p2].weight;//由次小和最小根節(jié)點構(gòu)成新的節(jié)點，權(quán)值相加}}voidprinthfmt(hfmttree)//打印哈夫曼樹{ inti;printf("------------------------------------------------------------------\n");printf("**********************哈夫曼編數(shù)結(jié)構(gòu):*****************************\n");printf("\t\t權(quán)重\t父母\t左孩子\t右孩子\t字符\t");for(i=0;i<2*n-1;i++){printf("\n");printf("\t\t%d\t%d\t%d\t%d\t%c",tree[i].weight,tree[i].parent,tree[i].lchild,tree[i].rchild,tree[i].key);}printf("\n------------------------------------------------------------------\n");printf("\n\n");}voidhfmtpath(hfmtt,inti,intj)//編碼的重要哈夫曼樹路徑遞歸算法{inta,b;a=i;b=j=t[i].parent;if(t[j].parent!=-1)//逆向遞歸{i=j;hfmtpath(t,i,j);}if(t[b].lchild==a)printf("0");//編碼elseprintf("1");}voidphfmnode(hfmtt)//對字符進(jìn)行初始編碼{inti,j;printf("\n------------------------------------------------------------------\n");printf("**************************哈夫曼編碼******************************");for(i=0;i<n;i++){j=0;printf("\n");printf("\t\t%c\t",t[i].key,t[i].weight);hfmtpath(t,i,j);}printf("\n------------------------------------------------------------------\n");}voidencoding(hfmtt)//對用戶輸入的電文進(jìn)行編碼{charr[1000];//用來存儲輸入的字符串inti,j;printf("\n\n請輸入需要編碼的字符:");gets(r);printf("編碼結(jié)果為:");for(j=0;r[j]!='\0';j++)//判斷輸入的字符for(i=0;i<n;i++)if(r[j]==t[i].key)hfmtpath(t,i,j);printf("\n");}intmain()//主函數(shù){hfmtht;charflag;printf("http://哈夫曼編碼程序//\n");printf("|********************************************|\n");creathfmt(ht);//建立一個哈弗曼樹printhfmt(ht);//打印建立的哈弗曼樹phfmnode(ht);printf("\n------------------------------------------------------------------\n");printf("***************************編碼&&退出***********************");printf("\n【1】編碼\t【0】退出");printf("\n您的選擇：");flag=getchar();getchar();while(flag!='0'){if(flag=='1')