数据结构关于哈夫曼树的编码译码的课程设计~寻求帮助_百度知道
数据结构关于哈夫曼树的编码译码的课程设计~寻求帮助
哈夫曼编码/译码器（树的应用）1) 基本要求：系统应具有以下功能：（1） 构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符及n个对应权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存；（2） 编码：利用已构造的哈夫曼编码对“明文”文件中正文进行编码，然后将结果“密文”存入文件中；（3） 译码：将“密文”文件中的0、1代码序列进行译码；（4） 打印哈夫曼编码；（5） 打印“明文”和对应的“密文”文件。2) 提示分析采用静态链表作为哈夫曼树的存储结构（参照书中结构）。在microsoft visual c++环境下能运行无错误的源代码...不用太复杂，希望能有注解，注解OK运行OK会在追加最高财富值。高手帮帮忙，剩没几天了
我有更好的答案
一年好运随春到 四季彩云滚滚来 横批：万事如意
其他类似问题
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁哈夫曼编/译码器的问题：请求高手帮帮忙，课程设计用的，自己写的错误太多了，万分感谢，c描述。拜托了_百度知道
哈夫曼编/译码器的问题：请求高手帮帮忙，课程设计用的，自己写的错误太多了，万分感谢，c描述。拜托了
1、问题描述：利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。试写一个哈夫曼编/译码系统。2、基本要求：一个完整的系统应具有以下功能：（1）初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件中。（2）编码。利用已建好的哈夫曼树对文件中的正文进行编码，然后将结果存入文件中。（3）译码。利用已建好的哈夫曼树将文件中的代码进行译码，结果存入文件中。（4）完成数据测试，要求编码字符不低于15个，编码文件的长度不低于50个字符。 (5) 计算平均编码长度。
提问者采纳
以下程序在c-free下测试成功。算法参考 数据结构（C语言版）——清华大学出版社请根据题目具体要求进行修改！有问题找我……#include&stdio.h& #include&stdlib.h&#include&string.h&typedef char ElemTtypedef char** HuffmanC typedef int S
typedef struct{
unsigned int m_
unsigned int parent,lchild, }HTNode,*HuffmanT typedef struct weight{
unsigned int m_ }Wvoid HuffmanCoding(HuffmanTree *,HuffmanCode *,Weight *,int); void Select(HuffmanTree,int,int *,int *); void OutputHuffmanCode(HuffmanTree,HuffmanCode,int); void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,Weight *w,int n){ //w存放n个字符的权值（均&0），构造Huffman树HT，并求出n个字符的Huffman编码HC
int i,m,s1,s2,start,c,f;
(*HT)=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
//0号单元未用
for(p=HT,i=1;i&=n;++i,++p,++w)
(*HT)[i].elem=w[i-1].
(*HT)[i].m_weight=w[i-1].m_
(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
for(;i&=m;++i,++p)
(*HT)[i].elem='0';
(*HT)[i].m_weight=(*HT)[i].parent=(*HT)[i].lchild=(*HT)[i].rchild=0;
for(i=n+1;i&=m;++i)
//在HT[1...i-1]选择parent为0且weight最小的两个结点，其序号分别为s1和s2
Select(*HT,i-1,&s1,&s2);
(*HT)[s1].parent=i;(*HT)[s2].parent=i;
(*HT)[i].lchild=s1;(*HT)[i].rchild=s2;
(*HT)[i].m_weight=(*HT)[s1].m_weight+(*HT)[s2].m_
//从叶子到根逆向求每个字符的Huffman编码
(*HC)=(HuffmanCode)malloc(n*sizeof(char*));
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';
for(i=1;i&=n;++i)
//逐个字符求编码
start=n-1;
for(c=i,f=(*HT)[i].f!=0;c=f,f=(*HT)[f].parent)//从叶子到跟逆向求编码
if((*HT)[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
(*HC)[i]=(char *)malloc((n-start)*sizeof(char));
strcpy((*HC)[i],&cd[start]);
//从cd复制编码到HC
} } void Select(HuffmanTree HT,int n,int *s1,int *s2) {
(*s1)=(*s2)=0;
for(i=1;i&=n;i++)
if(HT[i].m_weight&HT[(*s2)].m_weight&&HT[i].parent==0&&(*s2)!=0)
if(HT[i].m_weight&HT[(*s1)].m_weight)
(*s2)=(*s1);
if(((*s1)==0||(*s2)==0)&&HT[i].parent==0)
if((*s1)==0) (*s1)=i;
if((*s2)==0)
if(HT[i].m_weight&HT[(*s1)].m_weight)
(*s2)=(*s1);
else (*s2)=i;
if((*s1)&(*s2))
(*s1)=(*s2);
} } void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n) {
printf(&\nnumber---element---weight---huffman code\n&);
for(i=1;i&=n;i++)
%s\n&,i,HT[i].elem,HT[i].m_weight,HC[i]); } Status main(void) {
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
printf(&input the tatol number of the Huffman Tree:& );
scanf(&%d&,&n);
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i&n;i++)
printf(&input the element & its weight:&);
scanf(&%1s%d&,&c,&wei);
w[i].elem=c;
w[i].m_weight=
HuffmanCoding(&HT,&HC,w,n);
OutputHuffmanCode(HT,HC,n);
return 1; }
不好意思哈，您能把题目做一下吗？感谢。。。。
提问者评价
虽然不对 还是谢谢了
其他类似问题
哈夫曼的相关知识
其他1条回答
#include &stdio.h&#include &stdlib.h&#include &string.h&typedef char* HuffmanC/*动态分配数组，存储哈夫曼编码*/typedef struct {
/* 用来存放各个结点的权值*/ unsigned int parent, LChild,RC /*指向双亲、孩子结点的指针*/}HTNode, * HuffmanT
/*动态分配数组，存储哈夫曼树*/void select(HuffmanTree *ht,int n, int *s1, int *s2){ for(i=1; i&=n; i++) {
if((*ht)[i].parent == 0)
} } for(i=1; i&=n; i++) {
if((*ht)[i].parent == 0)
if((*ht)[i].weight & (*ht)[min].weight)
} } *s1 = for(i=1; i&=n; i++) {
if((*ht)[i].parent == 0 && i!=(*s1))
} } for(i=1; i&=n; i++) {
if((*ht)[i].parent == 0 && i!=(*s1))
if((*ht)[i].weight & (*ht)[min].weight)
} } *s2 =}void CrtHuffmanTree(HuffmanTree *ht , int *w, int n){ /* w存放已知的n个权值，构造哈夫曼树ht */ int m,i; int s1,s2; m=2*n-1; *ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
/*0号单元未使用*/ for(i=1;i&=n;i++)
{/*1-n号放叶子结点，初始化*/
(*ht)[i].weight = w[i];
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0; }
for(i=n+1;i&=m;i++) {
(*ht)[i].weight = 0;
(*ht)[i].LChild = 0;
(*ht)[i].parent = 0;
(*ht)[i].RChild = 0; }
/*非叶子结点初始化*//* ------------初始化完毕！对应算法步骤1---------*/
for(i=n+1;i&=m;i++)
/*创建非叶子结点,建哈夫曼树*/ {
/*在(*ht)[1]~(*ht)[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、s2返回*/
select(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]. } }/*哈夫曼树建立完毕*/void outputHuffman(HuffmanTree HT, int m){ if(m!=0) {
printf(&%d
&, HT[m].weight);
outputHuffman(HT,HT[m].LChild);
outputHuffman(HT,HT[m].RChild); }}void CrtHuffmanCode(HuffmanTree *ht, HuffmanCode *hc, int n)/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/{ char * hc=(HuffmanCode *)malloc((n+1)*sizeof(char *));
/*分配n个编码的头指针*/ cd=(char * )malloc(n * sizeof(char ));
/*分配求当前编码的工作空间*/ cd[n-1]='\0';
/*从右向左逐位存放编码，首先存放编码结束符*/ for(i=1;i&=n;i++)
/*求n个叶子结点对应的哈夫曼编码*/ {
start=n-1;
/*初始化编码起始指针*/
for(c=i,p=(*ht)[i]. p!=0; c=p,p=(*ht)[p].parent) /*从叶子到根结点求编码*/
if( (*ht)[p].LChild == c)
cd[--start]='0';
/*左分支标0*/
cd[--start]='1';
/*右分支标1*/ hc[i]=(char *)malloc((n-start)*sizeof(char));
/*为第i个编码分配空间*/ strcpy(hc[i],&cd[start]); } free(cd); for(i=1;i&=n;i++)
printf(&%d编码为%s\n&,(*ht)[i].weight,hc[i]);}void main() {
HuffmanTree HT;
HuffmanCode HC;
printf(&input the total number of the Huffman Tree:& );
scanf(&%d&,&n);
w=(int *)malloc((n+1)*sizeof(int));
for(i=1;i&=n;i++) {
printf(&input the %d element's weight:&,i);
fflush(stdin);
scanf(&%d&,&wei);
CrtHuffmanTree(&HT,w,n);
m = 2*n-1; outputHuffman(HT,m);
printf(&\n&); CrtHuffmanCode(&HT,&HC,n); }
在最后有一个错误啊
您可能关注的推广回答者：
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁二叉树遍历演示_百度知道
二叉树遍历演示
课题五：二叉树遍历演示演示遍历二叉树的过程，所以首先建立二叉树，并用图形显示出树的形状。建立的过程是采用前序便利的方法来创建，设计两种生成树的方式：一种是系统随机生成，另一种是人工输入。考虑到屏幕界面的有限性，限定二叉树不超过5层，最多26个字符，输入字符小数点“.”代表NULL。初始树为某种颜色的结点，三种情况的遍历采用填充另外一种醒目的颜色，来表示当前遍历的结点，同时显示该结点的访问序号。同时在遍历的过程中在遍历图形的下方显示出遍历序列。这是我们的课程设计 对我来说有点难 所以请大家帮忙如果你们觉得麻烦 就给我一部分帮助 比喻给我 1.随即生产二叉树的函数
还有人工输入二叉数的函数2.还有就是图形显示的函数3.主函数4.三种遍历的函数
等等 谢谢啦
四、 遍历二叉树
二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施
操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就
是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比
较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按
层次访问。下面我们将分别进行讨论。
1、 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能：
TLR（根左右）, TRL（根右左）
LTR（左根右）, RTL（右根左）
LRT（左右根）, RLT（右左根）
其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。
由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT-&Lchild);
PreOrder(BT-&Rchild); }（2）中序遍历递归算法void InOrder(BTree BT) {
InOrder(BT-&Lchild);
Visit(BT);
InOrder(BT-&Rchild);
}（3）后序遍历递归算法void PostOrder(BTree BT) {
PostOrder(BT-&Lchild);
PostOrder(BT-&Rchild);
Visit(BT);
2 、按层次遍历二叉树
实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。void LevelOreder(QBTree BT) {
for (i=1;i&=BT.n;i++)
if (BT.elem[i]!='#') Visite(BT.elem[i]);}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。
在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作；
而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；void LevelOrder(BTree *BT) {
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p); //访问根结点，并将根结点入队
while (!QueueEmpty(Q)) { //当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p-&Lchild) {Visite(p-&Lchild);EnQueue(&Q,p-&Lchild); //处理左孩子&br&
if (!p-&Rchild) {Visite(p-&Rchild);EnQueue(&Q,p-&Rchild); //处理右孩子&br&
五、典型二叉树的操作算法
1、 输入一个二叉树的先序序列，构造这棵二叉树
为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉
树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判
断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结
点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针
参数在递归调用返回时完成。算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch=='#') return NULL;
//构造空树
else { BT=(BTree)malloc(sizeof(BTLinklist)); //构造新结点
BT-&lchild =Pre_Create_BT( );
//构造左子树
BT-&rchild =Pre_Create_BT( );
//构造右子树
return BT;
2、 计算一棵二叉树的叶子结点数目
这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否
为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：void Leaf(BTree BT,int *count) {
Leaf(BT-&child,&count); //计算左子树的叶子结点个数
if (BT-&lchild==NULL&&BT-&rchild==NULL) (*count)++;
Leaf(BT-&rchild,&count); //计算右子树的叶子结点个数
3、 交换二叉树的左右子树
许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一
些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：void change_left_right(BTree BT) {
change_left_right(BT-&lchild);
change_left_right(BT-&rchild);
BT-&lchild&-&BT-&
4 、求二叉树的高度
这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树 的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：int hight(BTree BT) {
//h1和h2分别是以BT为根的左右子树的高度
if (BT==NULL) return 0;
h1=hight(BT-&lchild);
h2=hight(BT-&right);
return max{h1,h2}+1;
六、树、森林与二叉树的转换
1、 树、森林转换成二叉树
将一棵树转换成二叉树的方法：
将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。
特点：一棵树转换成二叉树后，根结点没有右孩子。
将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根
结点看作兄弟关系，并对其中的每棵树依依地进行转换。
2 、二叉树还原成树或森林
这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。
第 3 节 哈夫曼树及其应用
1、哈夫曼树的定义及特点在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。
2、构造哈夫曼树的过程：（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。
例如： 假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树
在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着
程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为
这个程序很简单，并且很快就可以用下列形式编写出来：if (socre&60) printf(&bad&);else if (socre&70) printf(&pass&);else if (score&80) printf(&general&);else if (score&90) printf(&good&);esle printf(&very good&);
在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
4．前缀编码
在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两 个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。（1）等长编码
这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位 数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码
在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。最后得出每个字符的编码为：比如，发送一段编码：0010， 接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
其他类似问题
二叉树遍历的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁用C程序实现哈夫曼编码_百度知道
用C程序实现哈夫曼编码
问题描述:输入一个有n个叶结点的权植构造一棵哈夫曼树:(例如:n=8,权植为 5 29 7 8 14 23 3 11)根据哈夫曼树构造哈夫曼编码,用指向字符串的指针数组来存放,用叶子到树根逆向求每个结点的哈夫曼编码.算法提示:实现哈夫曼算法的数据类型定义为:
typedef struct pdode{/*权值域*／
int parent ,lchild,／*前件左子树右子树指针域*／
} HTnode,*
实现哈夫曼算法的大致描述为：
初始化：将2n-1个结点的三个指针域的值置为空（可用－1表
示），权值为0；
输入：读入n个叶结点的权值存入向量的前个分量中，即形成有个结点的森林（一个结点为一棵树）；
排序：按权值排序（从小到大）
大家帮帮忙啊,这是我们的课程设计题目,做完了合格才能回家过年啊!需要的是完整的程序,不是算法.拜托了!希望大家都快快回家过个好年啊!
实现哈夫曼算法的大致描述为： 初始化：将2n-1个结点的三个指针域的值置为空（可用－1表 示），权值为0； 输入：读入n个叶结点的权值存入向量的前个分量中，即形成有个结点的森林（一个结点为一棵树）； 排序：按权值排序（从小到大） 合并:把前两棵树组成一棵新树,放回森林,直至形成一棵树最后输出哈夫曼编码.
高手帮帮忙啊!救救同胞吧!万分感谢!.....好人有好运啊!
提问者采纳
去年做的课程设计，有什么不合要求的自己改改#include&string.h&#include&stdlib.h&#include&stdio.h&int m,s1,s2;typedef struct { unsigned int parent,lchild,}HTNode,*HuffmanT
//动态分配数组存储哈夫曼树typedef char *HuffmanC
//动态分配数组存储哈夫曼编码表void Select(HuffmanTree HT,int n) { int i,j; for(i = 1;i &=i++)
if(!HT[i].parent){s1 =} for(j = i+1;j &=j++)
if(!HT[j].parent){s2 =} for(i = 1;i &=i++)
if((HT[s1].weight&HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i; for(j = 1;j &=j++)
if((HT[s2].weight&HT[j].weight)&&(!HT[j].parent)&&(s1!=j))s2=j;}void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC[], int *w, int n) {
// 算法6.13
// w存放n个字符的权值(均&0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
char *if (n&=1)
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
// 0号单元未用
for (i=1; i&=n; i++) { //初始化
HT[i].weight=w[i-1];
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
for (i=n+1; i&=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
puts(&\n哈夫曼树的构造过程如下所示：&);
printf(&HT初态:\n
for (i=1; i&=m; i++)
printf(&\n%4d%8d%8d%8d%8d&,i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
按任意键，继续 ...&);
getchar();
for (i=n+1; i&=m; i++) {
// 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1);
HT[s1].parent =
HT[s2].parent =
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].
printf(&\nselect: s1=%d
s2=%d\n&, s1, s2);
for (j=1; j&=i; j++)
printf(&\n%4d%8d%8d%8d%8d&,j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
按任意键，继续 ...&);
getchar();
} //------无栈非递归遍历哈夫曼树，求哈夫曼编码
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cdlen = 0;
for (i=1; i&=m; ++i)
// 遍历哈夫曼树时用作结点状态标志
HT[i].weight = 0;
while (p) {
if (HT[p].weight==0) {
HT[p].weight = 1;
if (HT[p].lchild != 0) { p = HT[p].
cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) {
// 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0';
strcpy(HC[p], cd);
// 复制编码(串)
} else if (HT[p].weight==1) {
HT[p].weight = 2;
if (HT[p].rchild != 0) { p = HT[p].
cd[cdlen++] ='1'; }
// HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].weight = 0; p = HT[p]. --
}} // HuffmanCoding
void main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts(&输入结点数:&);
scanf(&%d&,&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf(&输入%d个结点的权值\n&,n);
for(i = 0;i &i++)
scanf(&%d&,&w[i]);
HuffmanCoding(HT,HC,w,n);
puts(&\n各结点的哈夫曼编码:&);
for(i = 1;i &=i++)
printf(&%2d(%4d):%s\n&,i,w[i-1],HC[i]);
getchar();
提问者评价
太感谢了!你的这个程序写的不错!多谢救急啊!我以后还得多多学习!祝你新年快乐!猪年行大运!!!
其他类似问题
哈夫曼编码的相关知识
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁}