Question

关于数据结构的课程设计

Answer 1

．问题的描述：
要求
1.给定m〔最大为20〕个字符的出现频率，得到
这m个字符的HaffMan编码。
2. 任意一个字符序列，得到一个二进制编码序列。
对该编码序列进行译码，得到原来的字符序列。

二．算法的设计

解决该问题首先要建立haffman树，对叶子结点赋值。
文字译码过程：先检索到叶子，然后用一个数组记录从叶子到根的路径（左0右1）
然后采用“先进后出”原则输出数组元素
密码译文过程：根据左0右1做到密码对应的叶子结点，输出结点所存字符。

三．数据结构的设计

结点的设计
struct Htnode
{
int ww;
int parent,llink,rlink;
char word;

};

树结构：
struct Httree
{
struct Htnode ht[MAXNODE];
int root;
};

typedef struct Httree *PHttree;

四．程序（主要部分）

PHttree huffman(int m,int *w)
{
PHttree pht;
int i,j,x1,x2,m1,m2;
pht=(PHttree) malloc(sizeof(struct Httree));
if (pht==NULL)
{
printf("out of space!!
");
return pht;
}
for (i=0;i2*m-1;i++)
{
pht->ht[i].llink=-1;
pht->ht[i].rlink=-1;
pht->ht[i].parent=-1;
if(im)
{
pht->ht[i].ww=w[i];
pht->ht[i].word='a'+i;
}
else
{
pht->ht[i].ww=-1;
pht->ht[i].word=0;
}
}
for(i=0;im-1;i++)
{
m1=MAXINT;
m2=MAXINT;
x1=-1;x2=-1;
for(j=0;jm+i;j++)
if (pht->ht[j].wwm1&&pht->ht[j].parent==-1)
{
m2=m1;x2=x1;
m1=pht->ht[j].ww;
x1=j;
}
else if(pht->ht[j].wwm2&&pht->ht[j].parent==-1)
{
m2=pht->ht[j].ww;
......

百年天地回元气 一统山河际太平 国泰民安