數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)書06

PAGE1實(shí)驗(yàn)六樹與二叉樹6.1實(shí)驗(yàn)?zāi)康模赫莆斩鏄滏湵淼慕Y(jié)構(gòu)和二叉樹的建立過程；掌握二叉樹的基本操作，加深對(duì)二叉樹的理解，逐步培養(yǎng)解決實(shí)際問題的編程能力。6.2實(shí)驗(yàn)要求：復(fù)習(xí)課本中有關(guān)樹與二叉樹的知識(shí)；用C語言完成算法和程序設(shè)計(jì)并上機(jī)調(diào)試通過；撰寫實(shí)驗(yàn)報(bào)告，給出算法思路或流程圖和具體實(shí)現(xiàn)（源程序）、算法分析結(jié)果（包括時(shí)間復(fù)雜度、空間復(fù)雜度以及算法優(yōu)化設(shè)想）、輸入數(shù)據(jù)及程序運(yùn)行結(jié)果（必要時(shí)給出多種可能的輸入數(shù)據(jù)和運(yùn)行結(jié)果）。6.3基礎(chǔ)實(shí)驗(yàn)[實(shí)驗(yàn)1]二叉樹的構(gòu)造實(shí)驗(yàn)內(nèi)容與要求:按先序序列構(gòu)造一棵二叉鏈表表示的二叉樹T；分析:二叉樹是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹，并有左、右之分，順序不能任意顛倒的一種非線性結(jié)構(gòu)。二叉樹常用的存儲(chǔ)結(jié)構(gòu)是二叉鏈表形式，二叉鏈表由一個(gè)數(shù)據(jù)項(xiàng)data（用于存放結(jié)點(diǎn)的值）和兩個(gè)指針項(xiàng)lchild、rchild（分別指向該結(jié)點(diǎn)的左、右子樹）。結(jié)點(diǎn)及結(jié)構(gòu)如圖6-1所示：lchildlchilddata rchild圖6-1含有兩個(gè)指針的二叉樹的結(jié)點(diǎn)及結(jié)構(gòu)datalchildrchild //------二叉樹的二叉鏈表存儲(chǔ)表示模型-------typedefstructBiTNode{

TElemType

data;

StructBiTNode

*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;將此結(jié)構(gòu)定義放在一個(gè)頭文件BiTNode.h里，可避免在后面的參考程序中代碼重復(fù)書寫，另外在該頭文件里給出二叉鏈表的初始化及常量的定義。實(shí)現(xiàn)提示按先序序列建立一棵二叉樹，先構(gòu)造根結(jié)點(diǎn)，再構(gòu)造根的左、右子樹；每一棵子樹又都是一顆二叉樹，所以構(gòu)造一棵子樹的過程與構(gòu)造整棵二叉樹的過程完全相同，按照先序序列，先構(gòu)造根，再構(gòu)造左子樹，然后構(gòu)造右子樹；采用遞歸形式直到葉子結(jié)點(diǎn)為止。以下是算法描述：StatusCreateBiTree(BiTree&T)//按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），＃字符表示空樹，//構(gòu)造二叉鏈表表示的二叉樹T。scanf(&ch);if(ch=='＃')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch;

//生成根結(jié)點(diǎn)

CreateBiTree(T->lchild);

//生成左子樹

CreateBiTree(T->rchild);

//生成右子樹}returnOK;}//CreateBiTree參考程序：//頭文件BiTNode.h的內(nèi)容如下： #include<stdio.h>#include<stdlib.h>#include<malloc.h>#defineMAX20#defineOK1#defineERROR0#defineNULL0#defineOVERFLOW0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;BiTreeCreateBiTree(BiTreeT){charch;scanf("%c",&ch);if(ch=='#')T=NULL;/*#代表空指針*/else{T=(BiTNode*)malloc(sizeof(BiTNode));if(!T)exit(OVERFLOW);/*申請(qǐng)結(jié)點(diǎn)*/T->data=ch;/*生成根結(jié)點(diǎn)*/T->lchild=CreateBiTree(T->lchild);/*構(gòu)造左子樹*/T->rchild=CreateBiTree(T->rchild);/*構(gòu)造右子樹*/}//以下是主程序shiyan6_1_1.c#include"BiTNode.h"main(){BiTreeT=NULL;printf("\n請(qǐng)讀入構(gòu)造二叉樹的字符序列：");CreateBiTree(T);/*建立一棵二叉樹T*/} [實(shí)驗(yàn)2]二叉樹的遍歷實(shí)驗(yàn)內(nèi)容與要求:對(duì)一棵二叉鏈表表示的二叉樹進(jìn)行先序遍歷、中序遍歷、后序遍歷和層序遍歷并分別輸出遍歷的結(jié)點(diǎn)順序。分析：二叉樹的先序遍歷是：若二叉樹為空，則空操作；否則，訪問根結(jié)點(diǎn)，先序遍歷左子樹，先序遍歷右子樹。二叉樹的中序遍歷是：若二叉樹為空，則空操作；否則，中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹。二叉樹的后序遍歷是：若二叉樹為空，則空操作；否則，后序遍歷左子樹，后序遍歷右子樹；訪問個(gè)結(jié)點(diǎn)。二叉樹的層序遍歷是：在訪問二叉樹的結(jié)點(diǎn)時(shí)按照自上而下，從左至右的順序。根作為第一層，根的孩子作為第二層，以此類推。先序遍歷二叉樹遞歸算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)，//先序遍歷二叉樹T，對(duì)每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次。//一旦visit()失敗，則操作失敗。if(T){

if(Visit(T->data))if(PreOrderTraverse(T->lchild,Visit))if(PreOrderTraverse(T->rchild，Visit))

returnOK;returnERROR;}else

returnOK;}//PreOrderTraverse中序遍歷的遞歸算法StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(InOrderTraverse(T->rchild，Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild，Visit))returnOK;returnERROR;}else

returnOK;}//InOrderTraverse后序遍歷遞歸算法StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){if(T){if(PostOrderTraverse(T->lchild,Visst))if(PostOrderTraverse(T->rchild，Visit))

if(Visit(T->data))returnOK;returnERROR;}else

returnOK;}//PreOrderTraverse層次遍歷二叉樹的非遞歸算法StatusLevelOrder(BiTreeT){

//按層次遍歷二叉樹T，Q為隊(duì)列

InitQueue(Q);

If(T!=NULL){//若樹非空EnQueue(Q,T);//根結(jié)點(diǎn)入隊(duì)列

While(!QueueEmpty(Q)){

DeQueue(Q,b);

//隊(duì)首元素出隊(duì)列

Visit(b->data);

//訪問結(jié)點(diǎn)

If(b->lchild!=NULL)EnQueue(Q,b->lchild);//左子樹非空，則入隊(duì)列

If(b->rchold!=Null)EnQueue(Q,b->rchild);//右子樹非空，則入隊(duì)列

}//while

}//if}LevelOrder參考程序：//以下代碼保存在文件shiyan6_1_2.c#include<stdio.h>#include"BiTNode.h"StatusPrintElement(TElemTypee){printf("%2c",e);returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){inti,j,k;if(T==NULL)returnOK;else{i=Visit(T->data);if(i){j=PreOrderTraverse(T->lchild,Visit);/*先序遍歷左子樹*/if(j){k=PreOrderTraverse(T->rchild,Visit);/*先序遍歷右子樹*/if(k)returnOK;}}elsereturnERROR;}}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*中序遍歷*/if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Visit))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){/*后序遍歷*/if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data))returnOK;returnERROR;}elsereturnOK;}voidLevleOrder(BiTreeT){/*層次遍歷二叉樹T，從第一層開始，每層從左到右*/BiTreeQueue[MAX],b;/*用一維數(shù)組表示隊(duì)列，front和rear分別表示隊(duì)首和隊(duì)尾指針*/intfront,rear;front=rear=0;if(T)/*若樹非空*/{Queue[rear++]=T;/*根結(jié)點(diǎn)入隊(duì)列*/while(front!=rear){/*當(dāng)隊(duì)列非空*/b=Queue[front++];/*隊(duì)首元素出隊(duì)列，并訪問這個(gè)結(jié)點(diǎn)*/printf("%2c",b->data);if(b->lchild!=NULL)Queue[rear++]=b->lchild;/*左子樹非空，則入隊(duì)列*/if(b->rchild!=NULL)Queue[rear++]=b->rchild;/*右子樹非空，則入隊(duì)列*/}}}/*LevelOrder*/voidmain(){BiTreeT=NULL,B;printf("\n請(qǐng)讀入構(gòu)造二叉樹的字符序列:");B=CreateBiTree(T);/*建立一棵二叉樹T*/printf("\n該二叉樹的先序遍歷是:");PreOrderTraverse(B,PrintElement);/*先序遍歷二叉樹*/printf("\n該二叉樹的中序遍歷");InOrderTraverse(B,PrintElement);/*中序遍歷二叉樹*/printf("\n該二叉樹的后序遍歷");PostOrderTraverse(B,PrintElement);/*后序遍歷二叉樹*/printf("\n該二叉樹的層次遍歷是:");LevleOrder(B);/*層次遍歷二叉樹*/getchar();}}[實(shí)驗(yàn)3]葉子結(jié)點(diǎn)統(tǒng)計(jì)實(shí)驗(yàn)內(nèi)容與要求：統(tǒng)計(jì)一棵二叉樹的葉子結(jié)點(diǎn)的個(gè)數(shù)分析： 葉子結(jié)點(diǎn)是二叉樹中既沒有左孩子又沒有有孩子的結(jié)點(diǎn)。采用遞歸方式。求一棵二叉樹的葉子結(jié)點(diǎn)數(shù)的遞歸模型如下。f(bt)=0; 若為空樹時(shí)f(bt)=1; 若只有根結(jié)點(diǎn)時(shí),該根結(jié)點(diǎn)是葉結(jié)點(diǎn)f(bt)=f(btree->lchild)+f(btree->rchild); 其它參考程序：#include<stdio.h>#include"BiTNode.h"intleafcount(BiTreebt){/*統(tǒng)計(jì)二叉樹bt中葉子結(jié)點(diǎn)數(shù)*/intn;if(bt==NULL)n=0;elseif(bt->lchild==NULL&&bt->rchild==NULL)n=1;elsen=leafcount(bt->lchild)+leafcount(bt->rchild);/*二叉樹葉子結(jié)點(diǎn)數(shù)等于左、右子樹的葉子結(jié)點(diǎn)數(shù)之和*/returnn;}voidmain(){BiTreeT=NULL;intm;printf("\n請(qǐng)輸入要構(gòu)造二叉樹的結(jié)點(diǎn)序列:");T=CreateBiTree(T);/*建立一棵二叉樹T*/m=leafcount(T);printf("葉子結(jié)點(diǎn)數(shù)是:%d",m);getchar();getchar();}[實(shí)驗(yàn)４]二叉樹的深度統(tǒng)計(jì)實(shí)驗(yàn)內(nèi)容與要求：統(tǒng)計(jì)一棵二叉樹的深度。分析若一棵二叉樹是空樹，則它的深度為０，否則它的深度取值為它的左、右子樹中深度最大的深度加１。intdepth(BiTreeT){

/*求二叉樹的深度*/intdep1,dep2;if(T==NULL)return0;

else{dep1=depth(T->lchild);

dep2=depth(T->rchild);

returndep1>dep2?dep1+1:dep2+1;｝}//depth參考程序：//以下代碼存放在文件shiyan6_1_4.c文件中#include<stdio.h>#include"BiTNode.h"intdepth(BiTreeT){/*求二叉樹的深度*/intdep1,dep2;if(T==NULL)returnERROR;else{dep1=depth(T->lchild);dep2=depth(T->rchild);returndep1>dep2?dep1+1:dep2+1;}}/*depth*/voidmain(){BiTreeT=NULL;printf("\n請(qǐng)輸入所構(gòu)造二叉樹的結(jié)點(diǎn)序列：");T=CreateBiTree(T);/*建立一棵二叉樹T*/printf("\n二叉樹的深度是:%d",depth(T));getchar();}[實(shí)驗(yàn)5]子樹交換實(shí)驗(yàn)內(nèi)容與要求：試編寫算法，對(duì)一棵二叉樹根結(jié)點(diǎn)不變，將左、右子樹進(jìn)行交換，樹中每個(gè)結(jié)點(diǎn)的左、右子樹進(jìn)行交換。分析：子樹交換就是將原來的二叉樹中每個(gè)結(jié)點(diǎn)的左、右子樹分別交換生成一棵新的二叉樹，該二叉樹與原來二叉樹成對(duì)稱形狀。先將二叉樹根結(jié)點(diǎn)的左、右子樹交換，然后在將左（右）子樹的左、右子樹交換直到子樹為空樹。voidExchange(BiTreeT){BiTNodep;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;Exchange(T->lchild);Exchange(T->rchild);}}參考程序：//以下代碼存放在文件shiyan6_1_5.c#include<stdio.h>#include"BiTNode.h" voidExchange(BiTreeT){BiTNode*p;if(T){p=T->lchild;T->lchild=T->rchild;T->rchild=p;Exchange(T->lchild);Exchange(T->rchild);}}voidmain(){BiTreeT=NULL;printf("\n請(qǐng)輸入要構(gòu)造二叉樹的節(jié)點(diǎn)序列:");T=CreateBiTree(T);/*建立一棵二叉樹T*/Exchange(T);}[實(shí)驗(yàn)6]線索二叉樹實(shí)驗(yàn)內(nèi)容與要求：構(gòu)造一棵二叉鏈表表示的二叉樹，并將其中序遍歷線索化。分析：在一棵有N個(gè)結(jié)點(diǎn)的二叉樹中，有N+1個(gè)指針域?yàn)榭铡０堰@些空的指針項(xiàng)加以利用，將空的左指針指向其前驅(qū)，空的右指針指向后繼，這樣的指針九百能了線索。線索化就是通過將空的左指針指向其前驅(qū)，空的右指針指向其后繼，使非線性的二叉樹線性化的過程。線索二叉樹采用線索鏈表表示，鏈表結(jié)構(gòu)為圖6-2（b）所示，在二叉鏈表結(jié)構(gòu)(圖6-2(a)所示)的基礎(chǔ)上增加了兩個(gè)標(biāo)志域LTag和RTag。這兩個(gè)標(biāo)志域當(dāng)其值為1時(shí)，指向其前驅(qū)和后繼。值為0時(shí)保持其指針指向不變。lchildLTaglchildLTagdataRTagrchildlchilddatarchild圖6-2鏈表結(jié)構(gòu)和線索鏈表結(jié)構(gòu) 0lchild域指示結(jié)點(diǎn)的左孩子0lchild域指示結(jié)點(diǎn)的左孩子LTag=1lchild域指示結(jié)點(diǎn)的前驅(qū) 0rchild域指示結(jié)點(diǎn)的右孩子RTag=1rchild域指示結(jié)點(diǎn)的后繼中序遍歷線索化二叉樹就是在對(duì)線索樹中序遍歷的過程中為左標(biāo)志域?yàn)?的結(jié)點(diǎn)尋找前驅(qū)，為由標(biāo)志域?yàn)?的結(jié)點(diǎn)尋找后繼。結(jié)點(diǎn)的后繼是中序遍歷其右子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)的前驅(qū)是中序遍歷其左子樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)。先構(gòu)造一棵用線索鏈表表示的二叉樹T，輔設(shè)一個(gè)全局變量pre用于記錄離當(dāng)前結(jié)點(diǎn)p最后“訪問”的結(jié)點(diǎn)。對(duì)該二叉樹T進(jìn)行中序遍歷，生成線索化后二叉樹的頭結(jié)點(diǎn)Thrt，如果p的左標(biāo)志域?yàn)榭?，則將其變?yōu)榫€索，并讓其左指針指向pre，pre就是中序遍歷二叉樹Thrt時(shí)p結(jié)點(diǎn)的前驅(qū)；如果pre的右標(biāo)志域?yàn)榭眨瑒tp就是pre的后繼，將pre的右標(biāo)志域變?yōu)榫€索。參考程序：//以下代碼保存在文件shiyan6_1_6.c中#include<stdio.h>#include<malloc.h>#include<stdlib.h>typedefcharDataType;/*定義DataType類型*/typedefenum{Link,Thread}PointerTag;typedefstructnode{DataTypedata;structnode*lchild,*rchild;/*左右孩子子樹*/PointerTagLTag,RTag;}BiThrNode;

/*結(jié)點(diǎn)類型*/typedefBiThrNode*BiThrTree;/*二叉樹類型*//*構(gòu)造二叉樹*/void

CreatBinTree(BiThrTree*T){

/*構(gòu)造二叉鏈表,注意:輸入序列是先序序列*/charch;

if((ch=getchar())=='')

*T=NULL;

else{

/*讀入非空格*/

T=(BiThrNode*)malloc(sizeof(BiThrNode));/*生成結(jié)點(diǎn)*/

(*T)->data=ch;(*T)->LTag=Link;(*T)->RTag=Link;

CreatBinTree(&(*T)->lchild);

/*構(gòu)造左子樹

*/

CreatBinTree(&(*T)->rchild);

/*構(gòu)造右子樹*/

}}BiThrTreepre;/*全局變量*/voidInThreading(BiThrTreep){

if(p)

{InThreading(p->lchild);/*左子樹線索化*/

if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驅(qū)線索*/

if(!pre->rchild){pre->RTag=Thread;pre->rchild=p;}/*后繼線索*/pre=p;/*保持pre指向p*/

InThreading(p->rchild);/*右子樹線索化*/

}}intInOrderThreading(BiThrTree*Thrt,BiThrTreeT)

{/*中序遍厲二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)*/if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(0);

(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建頭結(jié)點(diǎn)*/

(*Thrt)->rchild=*Thrt;/*右指針回指*/

if(!T)(*Thrt)->lchild=*Thrt;

else

{(*Thrt)->lchild=T;pre=*Thrt;InThreading(T);/*中序遍歷進(jìn)行中序線索化*/

pre->rchild=*Thrt;pre->RTag=Thread;/*最后一個(gè)結(jié)點(diǎn)線索化*/

(*Thrt)->rchild=pre;

}return1;}//輸出結(jié)點(diǎn)intprint(BiThrTreee){printf("%d

%c

%d\n",e->LTag,e->data,e->RTag);return1;}//中序遍歷線索化二叉樹intInOrderTraverse(BiThrTreeT,int(*visit)(BiThrTreee)){/*T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的左鏈lchild指向根結(jié)點(diǎn)，中序遍厲二叉樹BiThrTreep;

p=T->lchild;/*p指向根結(jié)點(diǎn)*/

while(p!=T)/*空樹或遍厲結(jié)束時(shí)，p==T*/

{while(p->LTag==Link)p=p->lchild;

if(!visit(p))return0;/*打印*/while(p->RTag==Thread&&p->rchild!=T)

{p=p->rchild;visit(p);}/*訪問后繼結(jié)點(diǎn)*/

p=p->rchild;

}return1;}voidmain(){

/*測試程序*/BiThrTreeT,Thrt;

CreatBinTree(&T);InOrderThreading(&Thrt,T);InOrderTraverse(Thrt,print);}6.4提高實(shí)驗(yàn)[實(shí)驗(yàn)1]哈夫曼樹與哈夫曼編碼實(shí)驗(yàn)內(nèi)容與要求:從終端讀入一段電文（允許出現(xiàn)標(biāo)點(diǎn)和空格），統(tǒng)計(jì)其中出現(xiàn)的字符的個(gè)數(shù)，以及每個(gè)每個(gè)字符出現(xiàn)的頻率，然后根據(jù)統(tǒng)計(jì)數(shù)據(jù)建立以字符作為葉子結(jié)點(diǎn)，以其出現(xiàn)的次數(shù)為權(quán)值的哈夫曼樹，求出各字符的編碼并輸出。根據(jù)上述編碼對(duì)輸入的信息進(jìn)行譯碼。分析:哈夫曼樹是最優(yōu)二叉樹，利用哈夫曼樹求得的用于通信的二進(jìn)制編碼成為哈夫曼編碼。樹中從根到每個(gè)葉子都有一條路徑，對(duì)路徑上的各分支進(jìn)行約定：指向左子樹的分支表示“0”碼，指向右子樹的分支表示“1”碼，去每條路徑上的“0”和“1”的序列作為和各個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的字符的編碼，就是哈夫曼編碼。假設(shè)每種字符在電文中出現(xiàn)的次數(shù)為Wi，編碼長度為Li，電文中有n中字符，則電文編碼總長為ΣWiLi。若將此對(duì)應(yīng)到二叉樹上，Wi為葉子結(jié)點(diǎn)的權(quán)，Li為根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑長度，ΣWiLi恰好為二叉樹上帶權(quán)路徑長度。實(shí)現(xiàn)提示根據(jù)題目要求，要實(shí)現(xiàn)本設(shè)計(jì)，必須實(shí)現(xiàn)以下幾方面的功能：①哈夫曼樹的建立；②哈夫曼編碼的生成；③編碼文件的譯碼。⑴哈夫曼樹的建立由哈夫曼算法可知，初始森林中含有n棵只含有根結(jié)點(diǎn)的二叉樹，每合并一次，森林中減少一個(gè)二叉樹，產(chǎn)生一個(gè)新結(jié)點(diǎn)，最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn)。其中n個(gè)葉結(jié)點(diǎn)是初始森林中的n個(gè)孤立結(jié)點(diǎn)?？捎靡粋€(gè)大小為2n-1的一維數(shù)組來存儲(chǔ)哈夫曼樹中的結(jié)點(diǎn)。因此哈夫曼樹的存儲(chǔ)結(jié)構(gòu)描述為：#definen100//樹中葉結(jié)點(diǎn)的個(gè)數(shù)#definem2*n-1//哈夫曼樹中結(jié)點(diǎn)總數(shù)typedefstruct{intweight;//權(quán)值intlchild,rchild,parent;//左右還自己雙親指針}HTNode;//樹中結(jié)點(diǎn)類型typedefHTNodeHuffmanTree[m+1];//0號(hào)單元不用要實(shí)現(xiàn)哈夫曼樹算法，首先要實(shí)現(xiàn)HT[1..k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的選擇算法；另外，還需要有一個(gè)記錄電文中出現(xiàn)的各個(gè)字母以及統(tǒng)計(jì)它們出現(xiàn)的頻率的算法。假設(shè)電文中僅含有大寫字母。1)選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)的算法：voidselect(HuffmanTreeHT,intk,int&s1,int&s2){//在HT[1..k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)//其序號(hào)分別為s1和s2，通過引用參數(shù)帶回主調(diào)函數(shù)inti,j;intmin1=32767;for(i=1;i<=k;i++)//找s1if(HT[i].weight<min1&&HT[i].parent==0){j=i;min1=HT[i].weight;}s1=j;min1=32767;for(i=1;i<=k;i++)//找s1if(HT[i].weight<min1&&HT[i].parent==0&&i!=s1){j=i;min1=HT[i].weight;}s2=j;}2)統(tǒng)計(jì)電文中的字符及其出現(xiàn)的次數(shù)假設(shè)電文中全是大寫字母，該算法的思想為：定義一個(gè)含有26個(gè)元素的整形數(shù)組，用來存儲(chǔ)各字母出現(xiàn)的次數(shù)。因?yàn)榇髮懽帜傅腁SCII碼與整數(shù)1-26之間相差64，因此在算法中使用字母減去64（或采用字母作為下標(biāo)）作為統(tǒng)計(jì)數(shù)組的下標(biāo)對(duì)號(hào)入座，可以免去循環(huán)判斷。另外要求出電文中包含多少種字符，并保存這些字符以供編碼時(shí)使用?？梢杂靡粋€(gè)循環(huán)判斷先前統(tǒng)計(jì)好的各類字符個(gè)數(shù)的數(shù)組是否為0，若不為0，表示該字符在電文中出現(xiàn)過，將其值存入一個(gè)數(shù)組對(duì)應(yīng)的元素中，同時(shí)將其對(duì)應(yīng)的字符也存入另一個(gè)數(shù)組的元素中。具體實(shí)現(xiàn)如下：intjsq(char*s,intcnt[],charstr[]){char*p;inti,j,k;inttemp[27];for(i=1;i<=26;i++)temp[i]=0;for(p=s;*p!=’\0’//統(tǒng)計(jì)各字符的個(gè)數(shù)if(*p>=’A’&&*P<=’Z’){k=*p-64;tepm[k]++;}j=0;for(i=1,j=0;i<=26;i++)if(temp[i]!=0){j++;str[j]=i+64;//存入對(duì)應(yīng)的字母到數(shù)組中cnt[j]=temp[i]//存入對(duì)應(yīng)字母的權(quán)值}returnj;}3)構(gòu)造哈夫曼樹voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//構(gòu)造哈夫曼樹HTinti,s1,s2;for(i=1;i<=2*num-1;i++)//初始化HT{HT[i].lchild=0;HT[i].rchild=0; HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++)//輸入n個(gè)結(jié)點(diǎn)的權(quán)值HT[i].weight=cnt[i];for(i=num+1;i<=2*num;i++);//生成其余n-1個(gè)結(jié)點(diǎn){//在HT[1..k]中選擇parent=0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)s1和s2select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}for(i=0;i<=num;i++)HC[i].ch=str[i];i=1;while(i<=num){printf(“字符%c,次數(shù)為:%d\n”,HC[i].ch,cnt[i]);i++;} }⑵哈夫曼編碼 要求電文的哈夫曼編碼，必須先定義哈夫曼編碼類型，根據(jù)設(shè)計(jì)需要類型定義如下： typedefstruct{charch;charbits[n-1];//存放編碼位串intlen;//編碼長度}CodeNode;typedefCodeNodeHuffmanCode[n];1)哈夫曼編碼算法：voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根據(jù)哈夫曼樹HT求哈夫曼編碼intc,p,i;//c和p分別指示HT中孩子和雙親的位置charcd[n];//臨時(shí)存放編碼串intstart;//指示編碼在cd中的起始位置cd[num]=’\0’for(i=1;i<=num;i++){start=num;c=i;//從葉結(jié)點(diǎn)HT[i]開始上朔 while((p=HT[c].parent)>0)//直至回朔到HT[c]的根為止{//若HT[c]是HT[p]的左孩子,則生成0,否則生成代碼1cd[--start]=(HT[p].lchild==c)?’0’:’1c=p;}strcpy(HC[i].bits,&cd[start]);HC[i].len=num-start;}}2)建立正文的編碼文件將要編碼的字符串中的字符逐一與預(yù)先生成哈夫曼樹時(shí)保存的字符編碼對(duì)照表進(jìn)行比較，找到之后，對(duì)該字符的編碼寫入代碼文件，直至所有字符處理完為止。具體算法如下：voidcoding(HuffmanCodeHC,char*str){//對(duì)str所代表的字符串進(jìn)行編碼并寫入磁盤文件inti,j;FILE*fp;fp=fopen(“codefile.txt”,”w”);while(*str){for(i=1;i<=num;i++)if(HC[i].ch==*str){for(j=0;j<HC[i].len,j++)fputc(HC[i].bits[j],fp);break;}str++;}fclose(fp);}⑶代碼文件的譯碼 讀文件中編碼，并與原生成的哈夫曼編碼表比較，遇到相等時(shí)，即取出起相應(yīng)的字符存入一個(gè)新串中。 char*decode(HuffmanCodeHC){//代碼文件codefile.txt譯碼FILE*fp;charstr[254];//假設(shè)元文本文件不超過254char*p;staticcharcd[n+1];inti,j,k=0,cjs;fp=fopen(“codefile.txt”,”r”);while(!fopen(fp)){cjs=0;//一個(gè)字符的編碼是否讀結(jié)束 for(i=0;i<num&&cjs==0&&!feof(fp);i++){cd[i]=’’;cd[i+1]=’\0’;//初始化cd串cd[i]=fgetc(fp);for(j=1;j<=num;j++)if(strcmp(HC[j].bits,cd)==0){str[k]=HC[j].ch;k++;cjs=1;break;}}}str[k]=’\0’;p=str;returnp;}參考程序類型及相關(guān)變量定義存放在（shiyan6_2_1.h）#definen100#definem2*n-1typedefstruct{charch;charbits[n-1];intlen;}CodeNode;typedefCodeNodeHuffmanCode[n+1]；typedefstruct{intweight;intlchild,rchild,parent;}HTNode;//樹中結(jié)點(diǎn)類型typedefHTNodeHuffmanTree[m+1]//0號(hào)單元不用intnum;以下程序存放在（shiyan6_2_2.h）voidselect(HuffmanTreeHT,intk,int&s1,int&s2){//在HT[1..k]中選擇parent為0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)//其序號(hào)分別為s1和s2，通過引用參數(shù)帶回主調(diào)函數(shù)inti,j;intmin1=32767;for(i=1;i<=k;i++)//找s1if(HT[i].weight<min1&&HT[i].parent==0){j=i;min1=HT[i].weight;}s1=j;min1=32767;for(i=1;i<=k;i++)//找s1if(HT[i].weight<min1&&HT[i].parent==0&&i!=s1){j=i;min1=HT[i].weight;}s2=j;}jsq(char*s,intcnt[],charstr[]){char*p;inti,j,k;inttemp[27];for(i=1;i<=26;i++)temp[i]=0;for(p=s;*p!=’\0’//統(tǒng)計(jì)各字符的個(gè)數(shù)if(*p>=’A’&&*P<=’Z’){k=*p-64;tepm[k]++;}j=0;for(i=1,j=0;i<=26;i++)if(temp[i]!=0){j++;str[j]=i+64;//存入對(duì)應(yīng)的字母到數(shù)組中cnt[j]=temp[i]//存入對(duì)應(yīng)字母的權(quán)值}returnj;}voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//構(gòu)造哈夫曼樹HTinti,s1,s2;for(i=1;i<=2*num-1;i++)//初始化HT{HT[i].lchild=0;HT[i].rchild=0; HT[i].parent=0;HT[i].weight=0;}for(i=1;i<=num;i++)//輸入n個(gè)結(jié)點(diǎn)的權(quán)值HT[i].weight=cnt[i];for(i=num+1;i<=2*num;i++);//生成其余n-1個(gè)結(jié)點(diǎn){//在HT[1..k]中選擇parent=0且權(quán)值最小的兩個(gè)根結(jié)點(diǎn)s1和s2select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}for(i=0;i<=num;i++)HC[i].ch=str[i];i=1;while(i<=num){printf(“字符%c,次數(shù)為:%d\n”,HC[i].ch,cnt[i]);i++;}}voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根據(jù)哈夫曼樹HT求哈夫曼編碼intc,p,i;//c和p分別指示HT中孩子和雙親的位置charcd[n];//臨時(shí)存放編碼串intstart;//指示編碼在cd中的起始位置cd[num]=’\0’for(i=1;i<=num;i++){start=num;c=i;//從葉結(jié)點(diǎn)HT[i]開始上朔while((p=HT[c].parent)>0)//直至回朔到HT[c]的根為止{//若HT[c]是HT[p]的左孩子,則生成0,否則生成代碼1cd[--start]=(HT[p].lchild==c)?’0’:’1c=p;}strcpy(HC[i].bits,&cd[start]);HC[i].len=num-start;}}voidcoding(HuffmanCodeHC,char*str){//對(duì)str所代表的字符串進(jìn)行編碼并寫入磁盤文件inti,j;FILE*fp;fp=fopen(“codefile.txt”,”w”);while(*str){for(i=1;i<=num;i++)if(HC[i].ch==*str){for(j=0;j<HC[i].len,j++)fputc(HC[i].bits[j],fp);