Question

急求数据结构实习题哈夫曼编码程序（要求c语言，没学过c++）

需求：1、打开一篇英文文本。2、根据字符出现的次数以他们为权值输出哈夫曼编码方式。3、对英文文章进行编码。4、对编码进行译码核对正确性。 程序美观的我会再追加的。

Answer 1

　　哈夫曼编码

一、源程序

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
/* Huffman
树的存储结构
*/
#define n

8

/*
叶子数目根据需要设定
*/
#define m

2*n-1
/* Huffman
树中结点总数

*/
typedef struct

{int weight;

/*
结点的权值
*/
int lchild,rchild,parent;
/*
左、右孩子及双亲的下标
*/
}htnode;
typedef htnode huffmantree[m+1];/* huffmantree
是结构数组类型
,
其
0
号单元不用，存储哈夫
曼树

*/

typedef struct
{char ch;

/*
存储字符
*/

char code[n+1];

/*
存放编码位串
*/
}codenode;
typedef codenode huffmancode[n+1];/*huffmancode
是结构数组类型
,
其
0
号单元不用
,
存储哈夫
曼编码
*/

void inithuffmantree(huffmantree ht)

/*
初始化哈夫曼树函数
inithuffmantree()*/
{int i;

for(i=0;i<=m;i++)

{ht[i].weight=0;

ht[i].lchild=ht[i].rchild=ht[i].parent=0;

}
}

void inputweight(huffmantree ht)

/*
输入权值函数

*/
{int i;

for(i=1;i<=n;i++)

{printf("
请输入第
%d
个权值
:

",i);

scanf("%d",&ht[i].weight);

}

}

void selectmin(huffmantree

ht, int

i, int

*p1, int

*p2)
/*
在
ht[1..i]
中选两个权值最小的根结点，其序号为
*p1
和
*p2
，
*p1
中放权值最小的根结点
的序号，
*p2
中放权值次小的根结点的序号
*/
{int j,min1,min2;

/* min1,min2
分别是最小权值和次小权值
*/

min1=min2=32767;
*p1=*p2=0;
for(j=1;j<=i;j++)

{if(ht[j].parent==0)

/* j
为根结点
*/

if(ht[j].weight<min1||min1==32767)

{
if(min1!=32767)
{min2=min1;

*p2=*p1;}

min1=ht[j].weight;

*p1=j;

}

else

if(ht[j].weight<min2||min2==32767)

{min2=ht[j].weight;

*p2=j;}

}
}

void createhuffmantree(huffmantree

ht)
/*
构造
huffman
树，
ht[m]
为其根结点
*/

{

int i,p1,p2;

inithuffmantree(ht);

/*
将
ht
初始化
*/

inputweight(ht);

/*
输入叶子权值至
ht [1..n]
的
weight
域
*/

for(i=n+1;i<=m;i++)

/*
共进行
n-1
次合并，新结点依次存于
ht[i]
中
*/

{selectmin(ht,i-1,&p1,&p2); /*
在
ht [1.. i-1]
中选择两个权值最小的根结点，
其序号分
别为
p1
和
p2*/

ht[p1].parent=ht[p2].parent=i;

ht[i].lchild=p1;

/*
最小权值的根结点是新结点的左孩子
*/

ht[i].rchild=p2;

/*
次小权值的根结点是新结点的右孩子
*/

ht[i].weight=ht[p1].weight+ht[p2].weight;

}
}

void huffmancodes(huffmantree ht,huffmancode

hcd) /*
根据
huffman
树
ht
求
huffman
编码
*/
{
int c,p,i;

/* c
和
p
分别指示

ht
中孩子和双亲的位置

*/
char cd[n+1];

/*
临时存放编码
*/
int start;

/*
指示编码在
cd
中的起始位置
*/
cd[n]='\0';

getchar();

/*
编码结束符
*/
printf("
请输入字符
");

for(i=1;i<=n;i++)

/*
依次求叶子
ht [i]
的编码
*/

{
hcd[i].ch=getchar();
/*
读入叶子
ht [i]
对应的字符
*/

start=n;

/*
编码起始位置的初值
*/

c=i;

/*
从叶子
ht [i]
开始上溯
*/

while((p=ht[c].parent)!=0)

/*
直至上溯到
ht [ c]
是树根为止
*/

{ cd[--start]=(ht[p].lchild==c)?'0':'1';

/*
若
ht [ c]
是
ht[p]
的左孩子，则生成代码
0
，否
则生成代码
1*/

c=p;

/*
继续上溯
*/

}

strcpy(hcd[i].code,&cd[start]);

/*
复制编码位串
*/

}
printf("\n");
for(i=1;i<=n;i++)
printf("
第
%d
个字符
%c
的编码为
%s\n",i,hcd[i].ch,hcd[i].code);
}

void main()
{huffmantree t;

huffmancode h;
printf("\n
请输入
%d
个权值
\n",n);
createhuffmantree(t);

/*
构造
huffman
树
*/
huffmancodes(t,h);

/*
构造
huffman
编码
*/
}

追问

请看一下补充的提问

Answer 2

#include <stdio.h>

#define MAXBIT      100
#define MAXVALUE  10000
#define MAXLEAF     30
#define MAXNODE    MAXLEAF*2 -1

typedef struct 
{
    int bit[MAXBIT];
    int start;
} HCodeType;        /* 编码结构体 */
typedef struct
{
    int weight;
    int parent;
    int lchild;
    int rchild;
} HNodeType;        /* 结点结构体 */

/* 构造一颗哈夫曼树 */
void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
{ 
    /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值，
        x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
    int i, j, m1, m2, x1, x2;
    /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
    for (i=0; i<2*n-1; i++)
    {
        HuffNode[i].weight = 0;
        HuffNode[i].parent =-1;
        HuffNode[i].lchild =-1;
        HuffNode[i].lchild =-1;
    } /* end for */

    /* 输入 n 个叶子结点的权值 */
    for (i=0; i<n; i++)
    {
        printf ("Please input weight of leaf node %d: \n", i);
        scanf ("%d", &HuffNode[i].weight);
    } /* end for */

    /* 循环构造 Huffman 树 */
    for (i=0; i<n-1; i++)
    {
        m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
        x1=x2=0;
        /* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */
        for (j=0; j<n+i; j++)
        {
            if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
            {
                m2=m1; 
                x2=x1; 
                m1=HuffNode[j].weight;
                x1=j;
            }
            else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
            {
                m2=HuffNode[j].weight;
                x2=j;
            }
        } /* end for */
            /* 设置找到的两个子结点 x1、x2 的父结点信息 */
        HuffNode[x1].parent  = n+i;
        HuffNode[x2].parent  = n+i;
        HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
        HuffNode[n+i].lchild = x1;
        HuffNode[n+i].rchild = x2;

        printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
        printf ("\n");
    } /* end for */
} /* end HuffmanTree */

int main(void)
{
    HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
    HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */
    int i, j, c, p, n;
    printf ("Please input n:\n");
    scanf ("%d", &n);
    HuffmanTree (HuffNode, n);
    
    for (i=0; i < n; i++)
    {
        cd.start = n-1;
        c = i;
        p = HuffNode[c].parent;
        while (p != -1)   /* 父结点存在 */
        {
            if (HuffNode[p].lchild == c)
                cd.bit[cd.start] = 0;
            else
                cd.bit[cd.start] = 1;
            cd.start--;        /* 求编码的低一位 */
            c=p;                    
            p=HuffNode[c].parent;    /* 设置下一循环条件 */
        } /* end while */
        
        /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
        for (j=cd.start+1; j<n; j++)
        { HuffCode[i].bit[j] = cd.bit[j];}
        HuffCode[i].start = cd.start;
    } /* end for */
    
    /* 输出已保存好的所有存在编码的哈夫曼编码 */
    for (i=0; i<n; i++)
    {
        printf ("%d 's Huffman code is: ", i);
        for (j=HuffCode[i].start+1; j < n; j++)
        {
            printf ("%d", HuffCode[i].bit[j]);
        }
        printf ("\n");
    }
    getch();
    return 0;
}

追问

请看一下补充的提问