Question

创建一个哈夫曼树并且进行编码权重如下w={5，29，7 8，14，13 ，3 ，11}写出c语言代码

写出完整的代码，包含主函数，可以运行的

Answer 1

#include "stdafx.h"
#include "hfm.h"
#include<string.h>
#include<malloc.h>  //malloc()等
#include<stdio.h>
#include<stdlib.h>
#include<ctype.h>
#include<limits.h>
#include<iostream>
#define TRUE 1
#define FALSE 1
#define OK 1
#define ERROR 1
#define INFEASIBLE -1

typedef int Status;
typedef int Boolean；
/************************************************************************/
/* 最优二叉树简称：哈夫曼树                                                                     */
/************************************************************************/
//哈夫曼树结构
; typedef struct{
unsigned int weight;          //权重
unsigned int parent, lchild, rchild;  //树的双亲节点，和左右孩子

}HTNode, *HuffmanTree;

typedef char**  HuffmanCode;


//返回i个节点中权值最小的树的根节点的序号，供select()调用
int Min(HuffmanTree T, int i){
int j, flag;
unsigned int k = UINT_MAX;  //%d-->UINT_MAX = -1,%u--->非常大的数
for (j = 1; j <= i; j++)
if (T[j].weight < k && T[j].parent == 0)
k = T[j].weight, flag = j;                  //
T[flag].parent = 1;    //将parent标志为1避免二次查找

return flag;   //返回
}

void Select(HuffmanTree T, int i,int& s1,int& s2){
//在i个节点中选取2个权值最小的树的根节点序号，s1为序号较小的那个
int j;
s1 = Min(T,i);
s2 = Min(T,i);
if (s1 > s2){
j = s1;
s1 = s2;
s2 = j;
}
}

//HuffmanCode代表的树解码二进制值
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n){
//w存放n个字符的权值(均>0),构造哈夫曼树HT,并求出n个字符的哈夫曼编码HC
int m, i, s1, s2, start;
unsigned c, f;
char* cd;   
//分配存储空间
HuffmanTree p;
if (n <=1)
return;
//n个字符(叶子节点)有2n-1个树节点，所以树节点m
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m + 1)*sizeof(HTNode));  //0号元素未用
//这一步是给哈夫曼树的叶子节点初始化
for (p = HT + 1, i = 1; i <= n; ++i, ++p,++w)
{
(*p).weight = *w;
(*p).lchild = 0;
(*p).rchild = 0;
(*p).parent = 0;
}
//这一步是给哈夫曼树的非叶子节点初始化
for (; i <= m; ++i, ++p){
(*p).parent = 0;
}
/************************************************************************/
/* 做完准备工作后 ，开始建立哈夫曼树                                                               
/************************************************************************/
for (i = n + 1; i <= m; i++)
{
//在HT[1~i-1]中选择parent=0且weigh最小的节点，其序号分别为s1,s2
Select(HT, i - 1, s1, s2);  //传引用
HT[s1].parent = HT[s2].parent= i;
HT[i].lchild = s1;
HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
}
/************************************************************************/
/* 从叶子到根逆求每个叶子节点的哈夫曼编码                                          */
/************************************************************************/
//分配n个字符编码的头指针向量，（[0]不用）
HC = (HuffmanCode)malloc((n + 1)*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].parent; 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));  //生成一个块内存存储字符
//为第i个字符编码分配空间
strcpy(HC[i], &cd[start]);  //从cd赋值字符串到cd
}
free(cd);  //释放资源
}

//函数声明
int Min(HuffmanTree T, int i); //求i个节点中的最小权重的序列号，并返回
void Select(HuffmanTree T, int i, int& s1, int& s2); //从两个最小权重中选取最小的(左边)给s1，右边的给s2
void HuffmanCoding(HuffmanTree &HT, HuffmanCode&HC, int* w, int n);//哈夫曼编码与解码

int main(){

HuffmanTree HT;
HuffmanCode HC;

int *w, n, i;
printf("请输入权值的个数(>1):");
scanf_s("%d",&n);

w = (int*)malloc(n*sizeof(int));
printf("请依次输入%d个权值(整形):\n",n);

for (i = 0; i <= n - 1;i++)
{
scanf_s("%d",w+i);
}
HuffmanCoding(HT, HC, w, n);

for (i = 1; i <= n;i++)
{
puts(HC[i]);
}
return 0;
}

Answer 2

下面这个可以输入权重的
#include <stdio.h>
#define N 10 /*待编码字符的个数，即树中叶结点的最大个数*/
#define M 2*N-1 /*树中总的结点数目*/
typedef struct
{
unsigned int weight;/* 用来存放各个结点的权值*/
unsigned int parent,lchild,rchild;/*指向双亲、孩子结点的指针*/
}HTNode; /*树中结点的结构*/
typedef struct
{
char data; /*待编码的字符*/
int weight; /*字符的权值 */
char code[N]; /*字符的编码 */
} HTCode;
void Init(HTCode hc[],int *n)
{
/*初始化，读入待编码字符的个数n，从键盘输入n个字符和n个权值*/
int i,a;
printf("\n请输入字符个数 n=");
scanf("%d",&(*n));
printf("\n请输入 %d 个字符\n",*n);
while(isspace(a=getchar()));
for (i=1;i<=*n;i++)
{hc[i].data=a;
a=getchar();}
printf("\n请输入 %d 个字符的权重\n",*n);
for (i=1;i<=*n;i++)
scanf("%d",&(hc[i].weight));
}
void Select(HTNode ht[],int k,int *s1,int *s2)
{
/*ht[1…k]中选择parent为0，并且weight最小的两个结点 其序号由指针变量s1,s2指向*/
int i;
for (i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for (i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight)
*s1=i;
for (i=1; i<=k ; i++)
if (ht[i].parent==0 && i!=*s1)
break;
*s2=i;
for (i=1;i<=k;i++)
if ( ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight)
*s2=i;
}
void HuffmanCoding(HTNode ht[],HTCode hc[],int n)
{
/*构造Huffman树ht，并求出n个字符的编码*/
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1;
for (i=1;i<=m;i++)
{
if (i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].rchild=0;
}
for (i=n+1;i<=m;i++)
{
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].weight;
}
cd[n-1]='\0';
for (i=1;i<=n;i++)
{
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent)
if (ht[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
strcpy(hc[i].code,&cd[start]);
}
}
void main()
{
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n); /*初始化*/
HuffmanCoding(ht,hc,n);/*构造Huffman树，并形成字符的编码*/

for (i=1;i<=n;i++)
printf("\n%c --- %s",hc[i].data,hc[i].code);/*输出字符的编码*/

}

Answer 3

......

追问

你的代码，在哪里啊加qq1294360375
虽然不能运行，又是少了头文件#include
#include，改了后无错误不能运行