数据结构实验指导书06

PAGE1实验六树与二叉树6.1实验目的：掌握二叉树链表的结构和二叉树的建立过程；掌握二叉树的基本操作，加深对二叉树的理解，逐步培养解决实际问题的编程能力。6.2实验要求：复习课本中有关树与二叉树的知识；用C语言完成算法和程序设计并上机调试通过；撰写实验报告，给出算法思路或流程图和具体实现（源程序）、算法分析结果（包括时间复杂度、空间复杂度以及算法优化设想）、输入数据及程序运行结果（必要时给出多种可能的输入数据和运行结果）。6.3基础实验[实验1]二叉树的构造实验内容与要求:按先序序列构造一棵二叉链表表示的二叉树T；分析:二叉树是每个结点至多只有两棵子树，并有左、右之分，顺序不能任意颠倒的一种非线性结构。二叉树常用的存储结构是二叉链表形式，二叉链表由一个数据项data（用于存放结点的值）和两个指针项lchild、rchild（分别指向该结点的左、右子树）。结点及结构如图6-1所示：lchildlchilddata rchild图6-1含有两个指针的二叉树的结点及结构datalchildrchild //------二叉树的二叉链表存储表示模型-------typedefstructBiTNode{

TElemType

data;

StructBiTNode

*lchild,*rchild;

//左右孩子指针}BiTNode,*BiTree;将此结构定义放在一个头文件BiTNode.h里，可避免在后面的参考程序中代码重复书写，另外在该头文件里给出二叉链表的初始化及常量的定义。实现提示按先序序列建立一棵二叉树，先构造根结点，再构造根的左、右子树；每一棵子树又都是一颗二叉树，所以构造一棵子树的过程与构造整棵二叉树的过程完全相同，按照先序序列，先构造根，再构造左子树，然后构造右子树；采用递归形式直到叶子结点为止。以下是算法描述：StatusCreateBiTree(BiTree&T)//按先序次序输入二叉树中结点的值（一个字符），＃字符表示空树，//构造二叉链表表示的二叉树T。scanf(&ch);if(ch=='＃')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);

T->data=ch;

//生成根结点

CreateBiTree(T->lchild);

//生成左子树

CreateBiTree(T->rchild);

//生成右子树}returnOK;}//CreateBiTree参考程序：//头文件BiTNode.h的内容如下： #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);/*申请结点*/T->data=ch;/*生成根结点*/T->lchild=CreateBiTree(T->lchild);/*构造左子树*/T->rchild=CreateBiTree(T->rchild);/*构造右子树*/}//以下是主程序shiyan6_1_1.c#include"BiTNode.h"main(){BiTreeT=NULL;printf("\n请读入构造二叉树的字符序列：");CreateBiTree(T);/*建立一棵二叉树T*/} [实验2]二叉树的遍历实验内容与要求:对一棵二叉链表表示的二叉树进行先序遍历、中序遍历、后序遍历和层序遍历并分别输出遍历的结点顺序。分析：二叉树的先序遍历是：若二叉树为空，则空操作；否则，访问根结点，先序遍历左子树，先序遍历右子树。二叉树的中序遍历是：若二叉树为空，则空操作；否则，中序遍历左子树，访问根结点，中序遍历右子树。二叉树的后序遍历是：若二叉树为空，则空操作；否则，后序遍历左子树，后序遍历右子树；访问个结点。二叉树的层序遍历是：在访问二叉树的结点时按照自上而下，从左至右的顺序。根作为第一层，根的孩子作为第二层，以此类推。先序遍历二叉树递归算法StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//采用二叉链表存储结构，Visit是对数据元素操作的应用函数，//先序遍历二叉树T，对每个结点调用函数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为队列

InitQueue(Q);

If(T!=NULL){//若树非空EnQueue(Q,T);//根结点入队列

While(!QueueEmpty(Q)){

DeQueue(Q,b);

//队首元素出队列

Visit(b->data);

//访问结点

If(b->lchild!=NULL)EnQueue(Q,b->lchild);//左子树非空，则入队列

If(b->rchold!=Null)EnQueue(Q,b->rchild);//右子树非空，则入队列

}//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;/*用一维数组表示队列，front和rear分别表示队首和队尾指针*/intfront,rear;front=rear=0;if(T)/*若树非空*/{Queue[rear++]=T;/*根结点入队列*/while(front!=rear){/*当队列非空*/b=Queue[front++];/*队首元素出队列，并访问这个结点*/printf("%2c",b->data);if(b->lchild!=NULL)Queue[rear++]=b->lchild;/*左子树非空，则入队列*/if(b->rchild!=NULL)Queue[rear++]=b->rchild;/*右子树非空，则入队列*/}}}/*LevelOrder*/voidmain(){BiTreeT=NULL,B;printf("\n请读入构造二叉树的字符序列:");B=CreateBiTree(T);/*建立一棵二叉树T*/printf("\n该二叉树的先序遍历是:");PreOrderTraverse(B,PrintElement);/*先序遍历二叉树*/printf("\n该二叉树的中序遍历");InOrderTraverse(B,PrintElement);/*中序遍历二叉树*/printf("\n该二叉树的后序遍历");PostOrderTraverse(B,PrintElement);/*后序遍历二叉树*/printf("\n该二叉树的层次遍历是:");LevleOrder(B);/*层次遍历二叉树*/getchar();}}[实验3]叶子结点统计实验内容与要求：统计一棵二叉树的叶子结点的个数分析： 叶子结点是二叉树中既没有左孩子又没有有孩子的结点。采用递归方式。求一棵二叉树的叶子结点数的递归模型如下。f(bt)=0; 若为空树时f(bt)=1; 若只有根结点时,该根结点是叶结点f(bt)=f(btree->lchild)+f(btree->rchild); 其它参考程序：#include<stdio.h>#include"BiTNode.h"intleafcount(BiTreebt){/*统计二叉树bt中叶子结点数*/intn;if(bt==NULL)n=0;elseif(bt->lchild==NULL&&bt->rchild==NULL)n=1;elsen=leafcount(bt->lchild)+leafcount(bt->rchild);/*二叉树叶子结点数等于左、右子树的叶子结点数之和*/returnn;}voidmain(){BiTreeT=NULL;intm;printf("\n请输入要构造二叉树的结点序列:");T=CreateBiTree(T);/*建立一棵二叉树T*/m=leafcount(T);printf("叶子结点数是:%d",m);getchar();getchar();}[实验４]二叉树的深度统计实验内容与要求：统计一棵二叉树的深度。分析若一棵二叉树是空树，则它的深度为０，否则它的深度取值为它的左、右子树中深度最大的深度加１。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请输入所构造二叉树的结点序列：");T=CreateBiTree(T);/*建立一棵二叉树T*/printf("\n二叉树的深度是:%d",depth(T));getchar();}[实验5]子树交换实验内容与要求：试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。分析：子树交换就是将原来的二叉树中每个结点的左、右子树分别交换生成一棵新的二叉树，该二叉树与原来二叉树成对称形状。先将二叉树根结点的左、右子树交换，然后在将左（右）子树的左、右子树交换直到子树为空树。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请输入要构造二叉树的节点序列:");T=CreateBiTree(T);/*建立一棵二叉树T*/Exchange(T);}[实验6]线索二叉树实验内容与要求：构造一棵二叉链表表示的二叉树，并将其中序遍历线索化。分析：在一棵有N个结点的二叉树中，有N+1个指针域为空。把这些空的指针项加以利用，将空的左指针指向其前驱，空的右指针指向后继，这样的指针九百能了线索。线索化就是通过将空的左指针指向其前驱，空的右指针指向其后继，使非线性的二叉树线性化的过程。线索二叉树采用线索链表表示，链表结构为图6-2（b）所示，在二叉链表结构(图6-2(a)所示)的基础上增加了两个标志域LTag和RTag。这两个标志域当其值为1时，指向其前驱和后继。值为0时保持其指针指向不变。lchildLTaglchildLTagdataRTagrchildlchilddatarchild图6-2链表结构和线索链表结构 0lchild域指示结点的左孩子0lchild域指示结点的左孩子LTag=1lchild域指示结点的前驱 0rchild域指示结点的右孩子RTag=1rchild域指示结点的后继中序遍历线索化二叉树就是在对线索树中序遍历的过程中为左标志域为1的结点寻找前驱，为由标志域为1的结点寻找后继。结点的后继是中序遍历其右子树时访问的第一个结点，结点的前驱是中序遍历其左子树时最后访问的一个结点。先构造一棵用线索链表表示的二叉树T，辅设一个全局变量pre用于记录离当前结点p最后“访问”的结点。对该二叉树T进行中序遍历，生成线索化后二叉树的头结点Thrt，如果p的左标志域为空，则将其变为线索，并让其左指针指向pre，pre就是中序遍历二叉树Thrt时p结点的前驱；如果pre的右标志域为空，则p就是pre的后继，将pre的右标志域变为线索。参考程序：//以下代码保存在文件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;

/*结点类型*/typedefBiThrNode*BiThrTree;/*二叉树类型*//*构造二叉树*/void

CreatBinTree(BiThrTree*T){

/*构造二叉链表,注意:输入序列是先序序列*/charch;

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

*T=NULL;

else{

/*读入非空格*/

T=(BiThrNode*)malloc(sizeof(BiThrNode));/*生成结点*/

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

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

/*构造左子树

*/

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

/*构造右子树*/

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

if(p)

{InThreading(p->lchild);/*左子树线索化*/

if(!p->lchild){p->LTag=Thread;p->lchild=pre;}/*前驱线索*/

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

InThreading(p->rchild);/*右子树线索化*/

}}intInOrderThreading(BiThrTree*Thrt,BiThrTreeT)

{/*中序遍厉二叉树T，并将其中序线索化，Thrt指向头结点*/if(!(*Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(0);

(*Thrt)->LTag=Link;(*Thrt)->RTag=Thread;/*建头结点*/

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

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

else

{(*Thrt)->lchild=T;pre=*Thrt;InThreading(T);/*中序遍历进行中序线索化*/

pre->rchild=*Thrt;pre->RTag=Thread;/*最后一个结点线索化*/

(*Thrt)->rchild=pre;

}return1;}//输出结点intprint(BiThrTreee){printf("%d

%c

%d\n",e->LTag,e->data,e->RTag);return1;}//中序遍历线索化二叉树intInOrderTraverse(BiThrTreeT,int(*visit)(BiThrTreee)){/*T指向头结点，头结点的左链lchild指向根结点，中序遍厉二叉树BiThrTreep;

p=T->lchild;/*p指向根结点*/

while(p!=T)/*空树或遍厉结束时，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);}/*访问后继结点*/

p=p->rchild;

}return1;}voidmain(){

/*测试程序*/BiThrTreeT,Thrt;

CreatBinTree(&T);InOrderThreading(&Thrt,T);InOrderTraverse(Thrt,print);}6.4提高实验[实验1]哈夫曼树与哈夫曼编码实验内容与要求:从终端读入一段电文（允许出现标点和空格），统计其中出现的字符的个数，以及每个每个字符出现的频率，然后根据统计数据建立以字符作为叶子结点，以其出现的次数为权值的哈夫曼树，求出各字符的编码并输出。根据上述编码对输入的信息进行译码。分析:哈夫曼树是最优二叉树，利用哈夫曼树求得的用于通信的二进制编码成为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支进行约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，去每条路径上的“0”和“1”的序列作为和各个叶子结点对应的字符的编码，就是哈夫曼编码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n中字符，则电文编码总长为ΣWiLi。若将此对应到二叉树上，Wi为叶子结点的权，Li为根结点到叶子结点的路径长度，ΣWiLi恰好为二叉树上带权路径长度。实现提示根据题目要求，要实现本设计，必须实现以下几方面的功能：①哈夫曼树的建立；②哈夫曼编码的生成；③编码文件的译码。⑴哈夫曼树的建立由哈夫曼算法可知，初始森林中含有n棵只含有根结点的二叉树，每合并一次，森林中减少一个二叉树，产生一个新结点，最终求得的哈夫曼树中共有2n-1个结点。其中n个叶结点是初始森林中的n个孤立结点。可用一个大小为2n-1的一维数组来存储哈夫曼树中的结点。因此哈夫曼树的存储结构描述为：#definen100//树中叶结点的个数#definem2*n-1//哈夫曼树中结点总数typedefstruct{intweight;//权值intlchild,rchild,parent;//左右还自己双亲指针}HTNode;//树中结点类型typedefHTNodeHuffmanTree[m+1];//0号单元不用要实现哈夫曼树算法，首先要实现HT[1..k]中选择parent为0且权值最小的两个根结点的选择算法；另外，还需要有一个记录电文中出现的各个字母以及统计它们出现的频率的算法。假设电文中仅含有大写字母。1)选择parent为0且权值最小的两个根结点的算法：voidselect(HuffmanTreeHT,intk,int&s1,int&s2){//在HT[1..k]中选择parent为0且权值最小的两个根结点//其序号分别为s1和s2，通过引用参数带回主调函数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)统计电文中的字符及其出现的次数假设电文中全是大写字母，该算法的思想为：定义一个含有26个元素的整形数组，用来存储各字母出现的次数。因为大写字母的ASCII码与整数1-26之间相差64，因此在算法中使用字母减去64（或采用字母作为下标）作为统计数组的下标对号入座，可以免去循环判断。另外要求出电文中包含多少种字符，并保存这些字符以供编码时使用。可以用一个循环判断先前统计好的各类字符个数的数组是否为0，若不为0，表示该字符在电文中出现过，将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组的元素中。具体实现如下：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’//统计各字符的个数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;//存入对应的字母到数组中cnt[j]=temp[i]//存入对应字母的权值}returnj;}3)构造哈夫曼树voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//构造哈夫曼树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个结点的权值HT[i].weight=cnt[i];for(i=num+1;i<=2*num;i++);//生成其余n-1个结点{//在HT[1..k]中选择parent=0且权值最小的两个根结点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,次数为:%d\n”,HC[i].ch,cnt[i]);i++;} }⑵哈夫曼编码 要求电文的哈夫曼编码，必须先定义哈夫曼编码类型，根据设计需要类型定义如下： typedefstruct{charch;charbits[n-1];//存放编码位串intlen;//编码长度}CodeNode;typedefCodeNodeHuffmanCode[n];1)哈夫曼编码算法：voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根据哈夫曼树HT求哈夫曼编码intc,p,i;//c和p分别指示HT中孩子和双亲的位置charcd[n];//临时存放编码串intstart;//指示编码在cd中的起始位置cd[num]=’\0’for(i=1;i<=num;i++){start=num;c=i;//从叶结点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)建立正文的编码文件将要编码的字符串中的字符逐一与预先生成哈夫曼树时保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完为止。具体算法如下：voidcoding(HuffmanCodeHC,char*str){//对str所代表的字符串进行编码并写入磁盘文件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);}⑶代码文件的译码 读文件中编码，并与原生成的哈夫曼编码表比较，遇到相等时，即取出起相应的字符存入一个新串中。 char*decode(HuffmanCodeHC){//代码文件codefile.txt译码FILE*fp;charstr[254];//假设元文本文件不超过254char*p;staticcharcd[n+1];inti,j,k=0,cjs;fp=fopen(“codefile.txt”,”r”);while(!fopen(fp)){cjs=0;//一个字符的编码是否读结束 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;}参考程序类型及相关变量定义存放在（shiyan6_2_1.h）#definen100#definem2*n-1typedefstruct{charch;charbits[n-1];intlen;}CodeNode;typedefCodeNodeHuffmanCode[n+1]；typedefstruct{intweight;intlchild,rchild,parent;}HTNode;//树中结点类型typedefHTNodeHuffmanTree[m+1]//0号单元不用intnum;以下程序存放在（shiyan6_2_2.h）voidselect(HuffmanTreeHT,intk,int&s1,int&s2){//在HT[1..k]中选择parent为0且权值最小的两个根结点//其序号分别为s1和s2，通过引用参数带回主调函数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’//统计各字符的个数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;//存入对应的字母到数组中cnt[j]=temp[i]//存入对应字母的权值}returnj;}voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//构造哈夫曼树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个结点的权值HT[i].weight=cnt[i];for(i=num+1;i<=2*num;i++);//生成其余n-1个结点{//在HT[1..k]中选择parent=0且权值最小的两个根结点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,次数为:%d\n”,HC[i].ch,cnt[i]);i++;}}voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根据哈夫曼树HT求哈夫曼编码intc,p,i;//c和p分别指示HT中孩子和双亲的位置charcd[n];//临时存放编码串intstart;//指示编码在cd中的起始位置cd[num]=’\0’for(i=1;i<=num;i++){start=num;c=i;//从叶结点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){//对str所代表的字符串进行编码并写入磁盘文件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);