數(shù)據(jù)結(jié)構(gòu)第三次實驗報告

數(shù)據(jù)結(jié)構(gòu)實驗報告實驗三哈夫曼樹實驗班級：_計2-1___姓名：_依力夏提江·艾買爾__學(xué)號：_12101020129_實驗?zāi)康模菏煜し蔷€性結(jié)構(gòu)的特點,掌握非線性結(jié)構(gòu)的存儲方式及各種操作的實現(xiàn)方法，同時對自頂向下的程序設(shè)計方法、應(yīng)用程序界面的設(shè)計、非線性結(jié)構(gòu)的文件存儲方法等方面的輯程技術(shù)進行訓(xùn)練。問題描述：利用哈夫曼編碼進行信息通訊可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)，試為這樣的信息收發(fā)站寫一個哈夫曼編譯碼系統(tǒng)?；疽螅阂粋€完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化。從終端讀入字符集大小n，及n個字符和n個權(quán)值，建立哈夫曼樹，并將其存于文件hfmtree中。（2）C：編碼。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmtree中讀入），對文件tobetrans中的正文進行編碼，然后將結(jié)果存入文件codefile中。（3）D：譯碼。利用已建好的哈夫曼樹將文件codefile中的代碼進行譯碼，結(jié)果存入文件textfile中。（4）P：打印代碼文件。將文件codefi1e以緊湊格式顯示在終端上,每行50個代碼。同時將此字符形式的編碼文件寫入文件codeprint中。（5）T：打印哈夫曼樹。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹凸表形式）顯示在屏幕上，同時將此字符形式的哈夫曼樹寫入文件treeprint中。需求分析：（包括對問題的理解，解決問題的策略、方法描述）本程序?qū)崿F(xiàn)了使用赫夫曼編碼壓縮數(shù)據(jù)；輸入一串字符串sourceCode——為方便理解，暫時要求字符串只包含大寫字母和空格，如果你愿意，很容易就可以推廣到所有的字符——計算出字符串中各個字母的權(quán)重，然后對其進行赫夫曼編碼，輸出赫夫曼樹。將赫夫曼樹的葉子結(jié)點存儲到有序二叉樹中，輸出原字符串經(jīng)壓縮后得到的用’0’和’1編碼譯碼成功！最后銷毀有序二叉樹和赫夫曼樹。系統(tǒng)設(shè)計：（包括數(shù)據(jù)結(jié)構(gòu)定義、抽象出基本操作描述、主程序模塊處理過程描述）typedefcharElemType;//定

typedefstructsNode

{

doubleweight;

ElemTypedata;

}*Source;

typedefstructhNode

{

doubleweight;

ElemTypedata;

intlc,rc;

}*HuffmanTree;

typedefstructcNode

{

ElemTypedata;

stringstr;

structcNode*lc,*rc;

}*Btree;

HuffmanTreeCreateHuffmanTree(constSourcew,intn);//創(chuàng)建一棵赫夫曼樹

voidBuildHeap(HuffmanTreet,intn);//構(gòu)造一個二叉堆；小頂堆

voidPercDown(HuffmanTreet,intpos,intn);//構(gòu)造二叉堆的功能子函數(shù)

voidDeleteMin(HuffmanTreet,intlen);/*刪除二叉堆的根，并通過上移使得新得到的序列仍為二叉堆*/

voidInsertHfNode(HuffmanTreet,intlen,structhNodex);/*把x插入到原長度為len的二叉堆*/

voidPreorder(HuffmanTreet,intp);//先序遍歷赫夫曼樹

voidPostorder(Btree&t,HuffmanTreea,intn);/*后序遍歷赫夫曼樹，并記錄葉子結(jié)點編碼*/

boolInsertBtNode(Btree&t,Btrees);//向一個二叉排序樹t中插入一個結(jié)點s

voidInorder(Btreet);//中序遍歷二叉排序樹

BtreeSearch(Btreep,ElemTypedata);//查找值為data的結(jié)點的遞歸算法

stringCoding(strings,Btreet);/*利用記錄了葉子結(jié)點編碼的排序二叉樹，對sourceCode進行編碼，返回編碼后的字符串*/

stringDecode(strings,HuffmanTreehT);//利用赫夫曼樹對destCode進行解碼

voidDestroyBTree(Btree&t);//銷毀一棵二叉排序樹

voidDestroyHfmanTree(HuffmanTree&t,intn);//銷毀一棵赫夫曼樹主函數(shù)：intmain()

{

stringsourceCode;

getline(cin,sourceCode,’\n’);

intn=sourceCode.size();

constintMAX=27;//原碼由26個大寫字母加空格組成

Sourcew=newstructsNode[MAX];

//讀取各個字母并初始化權(quán)重

w[MAX-1].data=’’;

w[MAX-1].weight=0;

for(inti=MAX-2;i>=0;i--)

{

w[i].data=’A’+i;

w[i].weight=0;

}

//讀取各個字母的權(quán)重

for(inti=0;i<n;i++)

{

if(sourceCode[i]==’’)

w[26].weight++;

else

w[sourceCode[i]-’A’].weight++;

}

//獲取出現(xiàn)了的大寫字母和空格

n=0;

for(inti=0;i<MAX;i++)

{

if(w[i].weight>0)

w[n++]=w[i];

}

////直接輸入原碼和權(quán)重

//for(inti=0;i<n;i++)

//{

//cin>>w[i].weight>>w[i].data;

//}

for(inti=0;i<n;i++)

{

cout<<w[i].weight<<""<<w[i].data<<endl;

}

HuffmanTreehT=CreateHuffmanTree(w,n);//構(gòu)造赫夫曼樹

//for(inti=1;i<2*n;i++)

//cout<<hT[i].weight<<"";

//cout<<endl;

//先序遍歷赫夫曼樹，并輸出結(jié)點權(quán)重和葉子結(jié)點的data

Preorder(hT,1);

cout<<endl;

//后序遍歷赫夫曼樹，并記錄葉子結(jié)點編碼

BtreebT=NULL;

Postorder(bT,hT,n);

//中序遍歷記錄了葉子結(jié)點編碼的排序二叉樹

Inorder(bT);

//利用記錄了葉子結(jié)點編碼的排序二叉樹，對sourceCode進行編碼

stringdestCode=Coding(sourceCode,bT);

cout<<destCode<<endl;

//利用赫夫曼樹對destCode進行解碼

stringobjCode=Decode(destCode,hT);

cout<<objCode<<endl;

DestroyBTree(bT);//銷毀二叉排序樹

//Inorder(bT);//再輸出試試看

DestroyHfmanTree(hT,n);//銷毀赫夫曼樹

//Preorder(hT,1);//再輸出試試看

system("pause");

return0;

}調(diào)試分析：（包括調(diào)試過程中對原設(shè)計的修改，以及遇到的問題和解決的方法）構(gòu)造哈夫曼非常簡單，將所有的節(jié)點放到一個隊列中，用一個節(jié)點替換兩個頻率最低的節(jié)點，新節(jié)點的頻率就是這兩個節(jié)點的頻率之和。這樣，新節(jié)點就是兩個被替換節(jié)點的父節(jié)點了。如此循環(huán)，直到隊列中只剩一個節(jié)點（樹根）。不過因為自己技術(shù)還不嫻熟所以遇到了很多麻煩，而且也參考了別人的資源，下圖輸出方式安分布方式給出了哈夫曼樹狗仔的過程！測試結(jié)果：（輸入的測試數(shù)據(jù)及運行結(jié)果、正確性、在線測試情況）基本操作的實現(xiàn)：（對各基本操作實現(xiàn)的描述）(后面可加頁)//創(chuàng)建一棵赫夫曼樹

HuffmanTreeCreateHuffmanTree(constSourcew,intn)

{

HuffmanTreehT=newstructhNode[2*n];//第一個結(jié)點不用

for(inti=0;i<n;i++)

{

hT[i+1].data=w[i].data;

hT[i+1].weight=w[i].weight;

hT[i+1].lc=hT[i+1].rc=0;

}

BuildHeap(hT,n);//構(gòu)造一個二叉堆；小頂堆

structhNodeadd;

intleft=n;

intright=n;

while(left>1)

{

hT[++right]=hT[1];

add.weight=hT[1].weight;

add.lc=right;//存儲左孩子下標(biāo)

DeleteMin(hT,left--);

hT[left+1]=hT[1];

add.weight+=hT[1].weight;

add.rc=left+1;//存儲右孩子下標(biāo)

DeleteMin(hT,left--);

InsertHfNode(hT,++left,add);

//for(inti=1;i<=right;i++)

//cout<<hT[i].weight<<"";

//cout<<endl;

//system("pause");

}

returnhT;

}

//構(gòu)造一個二叉堆；小頂堆

voidBuildHeap(HuffmanTreet,intlen)

{

for(inti=len/2+len%2;i>0;i--)

{

PercDown(t,i,len);

}

}

//構(gòu)造二叉堆的功能子函數(shù)

voidPercDown(HuffmanTreet,intpos,intlen)

{

intchild;

structhNodemin=t[pos];

while(pos*2<=len)

{

child=pos*2;

if(child!=len&&t[child+1].weight<t[child].weight)

child++;

if(min.weight>t[child].weight)

t[pos]=t[child];

else

break;

pos=child;

}

t[pos]=min;

}

//刪除二叉堆的根，并通過上移使得新得到的序列仍為二叉堆

voidDeleteMin(HuffmanTreet,intlen)

{

structhNodelast=t[len--];//二叉堆的最后一個元素

intchild,pos=1;

while(pos*2<=len)//把二叉堆的某些元素往前移，使得新得到的序列仍為二叉堆

{

child=pos*2;

if(child!=len&&t[child+1].weight<t[child].weight)//若i有右兒子，且右兒子小于左兒子，c指向右兒子

child++;

if(last.weight>t[child].weight)//若i的小兒子小于二叉堆的最后一個元素，把其移到i的位置

t[pos]=t[child];

else

break;

pos=child;

}

t[pos]=last;//把二叉堆的最后一個元素放到適當(dāng)?shù)目瘴唬藭r得到的序列仍為二叉堆

}

//把x插入到原長度為len的二叉堆

voidInsertHfNode(HuffmanTreet,intlen,structhNodex)

{

inti;

for(i=len;i/2>0&&t[i/2].weight>x.weight;i/=2)

t[i]=t[i/2];

t[i]=x;

}

//后序遍歷赫夫曼樹，并記錄葉子結(jié)點編碼

voidPostorder(Btree&t,HuffmanTreea,intn)

{

int*stack=newint[n];

int*tag=newint[n];

char*buf=newchar[n];

boolflag=true;

inttop=-1;

intp=1;

while(a[p].lc>0||top>=0)

{

while(a[p].lc>0)//先一直尋找左孩子

{

flag=true;//此時p指向的是新葉子（未輸出過的葉子）

stack[++top]=p;//結(jié)點入棧

p=a[p].lc;

tag[top]=0;//表示右孩子沒有被訪問

buf[top]=’0’;//左孩子標(biāo)記’0’

}

if(flag)//如果p指向的是新葉子

{

//cout<<a[p].data<<":";//輸出葉子結(jié)點

//for(inti=0;i<=top;i++)

//cout<<buf[i];

//cout<<endl;

Btrees=newstructcNode;

s->data=a[p].data;

for(inti=0;i<=top;i++)

s->str+=buf[i];

s->lc=s->rc=NULL;

if(!(InsertBtNode(t,s)))//插入一個結(jié)點s

deletes;

}

if(top>=0)//所有左孩子處理完畢后

{

if(tag[top]==0)//如果右孩子沒有被訪問

{

flag=true;//此時p指向的是新葉子（未輸出過的葉子）

p=stack[top];//讀取棧頂元素，但不退棧，因為要先輸出其右孩子結(jié)點

p=a[p].rc;

tag[top]=1;//表示右孩子被訪問，下次直接退棧

buf[top]=’1’;//右孩子標(biāo)記’1’

}

else//棧頂元素出棧

{

flag=false;//此時p指向的是舊葉子（已輸出過的葉子），不再輸出

top--;

}

}

}

}

//先序遍歷赫夫曼樹

voidPreorder(HuffmanTreet,intp)

{

if(t==NULL)

return;

if(t[p].lc>0)

{

cout<<t[p].weight<<endl;

Preorder(t,t[p].lc);//遍歷左子樹

Preorder(t,t[p].rc);//遍歷右子樹

}

else

cout<<t[p].weight<<""<<t[p].data<<endl;

}

//向一個二叉排序樹t中插入一個結(jié)點s

boolInsertBtNode(Btree&t,Btrees)

{

if(t==NULL)

{

t=s;

returntrue;

}

elseif(t->data>s->data)//把s所指結(jié)點插入到左子樹中

returnInsertBtNode(t->lc,s);

elseif(t->data<s->data)//把s所指結(jié)點插入到右子樹中

returnInsertBtNode(t->rc,s);

else//若s->data等于b的根結(jié)點的數(shù)據(jù)域之值，則什么也不做

returnfalse;

}

//中序遍歷二叉排序樹

voidInorder(Btreet)

{

i