(完整word版)建立赫夫曼树课程设计-数据结构(完整word版)建立赫夫曼树课程设计-数据结构(完整word版)建立赫夫曼树课程设计-数据结构建立赫夫曼树一．需求设计：建立建立最优二叉树函数，要求可以建立函数输入二叉树，并输出其赫夫曼树。二．概要设计：存储结构:采用了数组和结构体结合的存储方式。以下是树中结点的存储结构形式,其中包括了权值，左孩子,右孩子，父亲这几个结点.typedefstruct//huffman树存储结构{unsignedintweight;//权值intlchild,rchild,parent；}huftree;基本算法:这个算法的主要流程为：通过控制台输入的形式得到建立赫夫曼树需要的参数—-〉调用生成赫夫曼树的算法来生成赫夫曼树，这个过程中还不断的调用select
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
来寻找当前结点中权值最小的结点来生成树的新结点，然后添加到树中去-->通过用户的选择来输出赫夫曼树，其输出的形式为“元素--—--元素权值-——--父结点-----左孩子————-右孩子”的形式。在程序中以下代码是用来控制控制台的提示信息的：while（in！=’3’)｛printf（”1建立初始化赫夫曼树\n2输出赫夫曼树\n3退出\n请输入（1--3):\n”）；scanf(”％c”，&in）;switch（in）{case'1’：printf("请输入待编码字符个数:");printf（”请输入字符和对应权值:”）；for（i=1;i〈=n;i++）｛printf(">〉>"）;scanf（”％c％d”，cha+i，weight+i）；}huffman（tree,w，n）;break;//生成huffman树case'2’:huffmancode（tree,n）；break;｝}下面的代码是用来生成赫夫曼树的，其中这个过程汇总调用了select方法来不断寻找当前所有结点中权值最小的结点，然后生成新的结点，再生成相应的树。voidhuffman（huftreetree［］,int*w,intn）//生成huffman树{intm,i;if（n〈=1）return;m=2＊n—1;for（i=1；i<=n；i++）//给tree中每个结点权值赋值,且分别给左右孩子及双亲初始化{tree［i]。weight=w[i];tree[i]。parent=0;tree[i］。lchild=0；tree[i］.rchild=0;｝for(i=n+1；i<=m；i++)//给除了叶子结点下的其它结点初始化{tree[i].weight=0；tree[i］。parent=0；tree[i］。lchild=0;tree［i]。rchild=0；}for（i=n+1;i<=m；i++)//最终结果｛select（tree，i-1)；tree［s1］。parent=i；tree[s2]。parent=i;tree［i]。lchild=s1；tree［i］.rchild=s2;tree［i]。weight=tree［s1].weight+tree[s2］。weight;}}三．详细设计:源程序：#include〈iomanip〉#include
#defineMAX99charcha［MAX];charhc［MAX—1］［MAX]；ints1,s2;//设置全局变量，以便在方法（函数）select中返回两个变量typedefstruct//huffman树存储结构{unsignedintweight；//权值intlchild，rchild,parent；}huftree;voidselect（huftreetree[］,intk）//找寻parent为,权最小的两个节点｛inti;for(i=1;i〈=k&&tree［i]。parent!=0；i++);s1=i；//初始化s1for(i=1；i〈=k;i++)if（tree［i］。parent==0＆＆tree［i]。weight〈tree［s1］.weight）s1=i；//把最小值赋给s1for（i=1；i〈=k；i++）if（tree［i］.parent==0＆&i！=s1)break；s2=i;//初始化s2for（i=1；i<=k;i++）if（tree［i］。parent==0＆&i!=s1＆&tree［i]。weight〈tree［s2]。weight）s2=i;//把最小值赋给s2｝voidhuffman（huftreetree[］,int＊w，intn)//生成huffman树{intm,i；if（n<=1)return;m=2＊n-1；for(i=1;i<=n;i++)//给tree中每个结点权值赋值，且分别给左右孩子及双亲初始化｛tree［i］。weight=w［i］;tree[i].parent=0;tree[i］.lchild=0;tree[i］。rchild=0；}for(i=n+1;i〈=m;i++）//给除了叶子结点下的其它结点初始化{tree[i］。weight=0；tree［i］.parent=0;tree［i].lchild=0;tree[i].rchild=0;}for(i=n+1;i〈=m；i++）//最终结果｛select（tree，i-1）;tree[s1］.parent=i;tree[s2］。parent=i；tree[i]。lchild=s1;tree［i]。rchild=s2；tree[i］。weight=tree[s1］.weight+tree［s2]。weight;}}voidhuffmancode（huftreetree［],intn)//输出huffman编码｛intstart,c，i,f;printf("哈夫曼树为：\n”)；printf(”元素—--——元素权值—-——-父结点-—-——左孩子---—-右孩子\n”)；for（i=1；i<=2*n—1；i++)｛printf(”％d-————％d-—---%d————-%d-——--%d\n",i,tree[i］。weight，tree[i]。parent,tree[i］。lchild,tree［i］。rchild）；｝}voidmain(）｛inti=0,n=0；int＊w，weight[MAX］；huftreetree［MAX]；w=weight;charin='6';while（in！='3'）｛printf(”1建立初始化赫夫曼树\n2输出赫夫曼树\n3退出\n请输入(1-—3）：\n”）;scanf("％c"，＆in）；switch（in){case'1’:printf(”请输入待编码字符个数：”)；printf（"请输入字符和对应权值：”）；for（i=1；i〈=n；i++)｛printf("〉〉〉");scanf(”%c%d",cha+i,weight+i)；｝huffman(tree,w,n）;break；//生成huffman树case'2'：huffmancode(tree,n）;break；}｝}四．调试分析：测试数据和结果：调试得到输出结果如图：当建立一个含有5个初始结点，权值分别为2，4，6，8，10的赫夫曼树的测试结果：算法时间复杂度：O（n2)对相关问
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
的思考：此处只是赫夫曼树的建立和输出算法的实现，一个完整的赫夫曼编/译码系统其实可以进一步完善，并且可以实现相关编码解码的功能。这也是赫夫曼树在生活中用到最多的地方。
浙公网安备 33021202002483