Question

哈夫曼编码问题，高手帮我

设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。
【基本要求】
1)将权值数据存放在数据文件(文件名为data.txt，位于执行程序的当前目录中)
2)分别采用动态和静态存储结构
3)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；
4)编码：利用建好的哈夫曼树生成哈夫曼编码；
5)输出编码；
6)设字符集及频度如下表：
字符 空格 A B C D E F G H I J K L M
频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20
字符 N O P Q R S T U V W X Y Z
频度 57 63 15 1 48 51 80 23 8 18 1 16 1
【进一步完成内容】
1)译码功能；
2)显示哈夫曼树；
3)界面设计的优化。

本人新人，分用本来就不多，还用完了，哪个高手帮忙啊，不好意思哦！~ ^-^
谢谢了！～有没有C语言写的？别的语言我不熟，看不懂．多数是C的也好．你这个好像不能用啊

Answer 1

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
int n;
struct node{
int w;
int flag;
char c;
struct node *plink,*llink,*rlink;
char code[50];

}*num[100],*root;
FILE *fp;
char tmpcode[50];
int t=0;

void main(void)
{
int i;
void settree(void); //建立树
void code(void); //对文件编码
void decode(void); // 译码
void disp(void);
root=(struct node*)malloc(sizeof(struct node));
puts("*******************哈夫曼编/译码器演示******************************");

while(1){
start:

puts("1. 初始化 2. 编码 3. 译码 4.显示编码表 5. 退出");
while(scanf("%d",&i)!=1)
{
while(getchar()!='\n')
continue;
puts("输入错误!");
puts("请重新输入！");
puts("1. 初始化 2. 编码 3. 译码 4.显示编码表 5. 退出");
}
switch (i)
{
case 1:
settree();
break;
case 2:
code();
break;
case 3:
decode();
break;
case 4:
disp();
break;
case 5:
exit(0);
default:
puts("输入错误！");
puts("请重新输入！");
goto start;
}
}
}
void settree(void)
{
int i,j,k;
struct node *p1,*p2,*tmp,*p;
void go(struct node *);
void setcode(struct node *);//建立每一个字符的编码
void printtree(struct node *);
puts("输入字符集的大小：");
scanf("%d",&n);
while(getchar()!='\n')
continue;

for(i=0;i<n;i++)
{
p=(struct node *)malloc(sizeof(struct node));
puts("请输入一个字符");
scanf("%c",&p->c);
while(getchar()!='\n')
continue;
puts("请输入该字符的权值:");
scanf("%d",&p->w);
while(getchar()!='\n')
continue;

p->plink=NULL;
p->rlink=NULL;
p->llink=NULL;
num[i]=p;
}

for(i=0;i<n-1;i++) //（递增）排序
{
for(j=i+1;j<n;j++)
{
if(num[i]->w>num[j]->w)
{
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
}
}
/*******************************开始建立树***********************/
num[n]=NULL; //结束标志
k=n;
while(num[1]!=NULL)
{
p=(struct node *)malloc(sizeof(struct node));
p1=num[0];
p2=num[1];
p->llink=p1;
p->rlink=p2;
p->plink=NULL;
p1->plink=p;
p2->plink=p;
p->w=p1->w+p2->w;

for(i=1;i<k;i++)
{
num[i]=num[i+1];
}

k--;
num[0]=p;
for(i=0;i<k-1;i++) //排序
{
for(j=i+1;j<k;j++)
{
if(num[i]->w>num[j]->w)
{
tmp=num[i];
num[i]=num[j];
num[j]=tmp;
}
}
}
}

root=num[0];
/*建立完毕*/
/*写入文件，前序*/
if((fp=fopen("c:\\hfmtree.wxl","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
setcode(root);
go(root);
fclose(fp);
}
void setcode(struct node *p)
{
if(p->llink==NULL&&p->rlink==NULL)
{
tmpcode[t]='\0';
strcpy(p->code,tmpcode);
}
else
{
tmpcode[t++]='0';
setcode(p->llink);
t--;
tmpcode[t++]='1';
setcode(p->rlink);
t--;
}
}

void go(struct node *p)
{

if(p->llink==NULL&&p->rlink==NULL)
{
fputc('(',fp);
fputc(p->c,fp);
fputs(p->code,fp);
fputc(')',fp);
}
else
{

go(p->llink);
go(p->rlink);
}
}

void code(void)
{
FILE *fp1,*fp2,*fp3;
char ch1,ch2,c;
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\tobetrans.txt","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp3=fopen("c:\\codefile.wxl","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}

while((ch1=fgetc(fp2))!=EOF)
{
t=0;

while((ch2=fgetc(fp1))!=EOF)
{
if(ch1==ch2)
{
while((c=fgetc(fp1))!=')')
{
tmpcode[t++]=c;
}
tmpcode[t]='\0';
fputs(tmpcode,fp3);
fputc('@',fp3);
rewind(fp1);
break;
}
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
}

void decode(void)
{
FILE *fp1,*fp2,*fp3;
char ch1,ch2,ch3;
char temp_3[20];
char temp_1[20];
int t1,t3;
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\textfile.txt","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp3=fopen("c:\\codefile.wxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}

while((ch3=fgetc(fp3))!=EOF)
{
t3=0;
while(ch3!='@')
{
temp_3[t3++]=ch3;
ch3=fgetc(fp3);
}
temp_3[t3]='\0';
while((ch1=fgetc(fp1))!=EOF)
{
if(isalpha(ch1))
{
ch2=ch1;
t1=0;
while((ch1=fgetc(fp1))!=')')
{
temp_1[t1++]=ch1;
}
temp_1[t1]='\0';

if(strcmp(temp_1,temp_3)==0)
{
fputc(ch2,fp2);
rewind(fp1);
break;
}
}
}
}
fclose(fp1);
fclose(fp2);
fclose(fp3);
}

void disp(void)
{
FILE *fp1,*fp2;
char ch1,ch2;
char tmp[20];
int t;
if((fp1=fopen("c:\\hfmtree.wxl","rb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
if((fp2=fopen("c:\\hfmcode.txt","wb"))==NULL)
{
puts("文件打开错误！");
getchar();
exit(0);
}
while((ch1=fgetc(fp1))!=EOF)
{
if(ch1=='(')
{
t=0;
ch1=fgetc(fp1);
ch2=ch1;
while((ch1=fgetc(fp1))!=')')
{
tmp[t++]=ch1;
}
tmp[t]='\0';
printf("%c-----%s\n",ch2,tmp);
fputc(ch2,fp2);
fputc('-',fp2);
fputc('-',fp2);
fputc('-',fp2);
fputs(tmp,fp2);
fputc('\n',fp2);
}
}
fclose(fp1);
fclose(fp2);
}

Answer 2

#include <string.h>
#include <stdio.h>

#define MAX_NODE 1024

#define MAX_WEIGHT 4096

typedef struct HaffmanTreeNode {

char ch, code[15];

int weight;

int parent, lchild, rchild;

} HTNode, *HaTree;

typedef struct {

HTNode arr[MAX_NODE];

int total;

} HTree;

/* 统计字符出现的频率 */

int statistic_char(char *text, HTree *t){

int i, j;

int text_len = strlen(text);

t->total = 0;

for (i=0; i<text_len; i++) {

for (j=0; j<t->total; j++) if (t->arr[j].ch == text[i]){

t->arr[j].weight ++;

break;

}

if (j==t->total) {

t->arr[t->total].ch = text[i];

t->arr[t->total].weight = 1;

t->total ++;

}

}

printf("char frequence\n");

for (i=0; i<t->total; i++)

printf("'%c' %d\n", t->arr[i].ch, t->arr[i].weight);

printf("\n");

return t->total;

}

int create_htree(HTree *t)

{

int i;

int total_node = t->total * 2 - 1;

int min1, min2; /* 权最小的两个结点 */

int min1_i, min2_i; /* 权最小结点对应的编号 */

int leaves = t->total;

for (i=0; i<leaves; i++) {

t->arr[i].parent = -1;

t->arr[i].rchild = -1;

t->arr[i].lchild = -1;

}

while (t->total < total_node) {

min1 = min2 = MAX_WEIGHT;

for (i=0; i<t->total; i++) { /* 对每一个结点 */

if (t->arr[i].parent == -1 /* 结点没有被合并 */

&& t->arr[i].weight < min2) { /* 结点的权比最小权小 */

if (t->arr[i].weight < min1) { /* 如果它比最小的结点还小 */

min2_i = min1_i; min2 = min1;

min1_i = i; min1 = t->arr[i].weight;

}

else

{

min2_i = i; min2 = t->arr[i].weight;

}

}

}

t->arr[t->total].weight = min1 + min2;

t->arr[t->total].parent = -1;

t->arr[t->total].lchild = min1_i;

t->arr[t->total].rchild = min2_i;

t->arr[min1_i].parent = t->total;

t->arr[min2_i].parent = t->total;

t->arr[t->total].ch = ' ';

t->total ++;

}

return 0;

}

/* 对哈夫曼树进行编码 */

void coding(HTree *t, int head_i, char *code)

{

if ( head_i == -1) return;

if (t->arr[head_i].lchild == -1 && t->arr[head_i].rchild == -1) {

strcpy(t->arr[head_i].code, code);

printf("'%c': %s\n", t->arr[head_i].ch, t->arr[head_i].code);

}

else {

int len = strlen(code);

strcat(code, "0");

coding(t, t->arr[head_i].lchild, code);

code[len] = '1';

coding(t, t->arr[head_i].rchild, code);

code[len] = '\0';

}

}

/* 中序打印树 */

void print_htree_ldr(HTree *t, int head_i, int deep, int* path)

{

int i;

if (head_i == -1) return;

path[deep] = 0;

print_htree_ldr(t, t->arr[head_i].lchild, deep + 1, path);

if (deep) printf(" ");

for (i=1; i<deep; i++) printf("%s", path[i]==path[i-1]?" ":"│ ");

int dir = path[i]==path[i-1];

if ( t->arr[head_i].lchild == -1 && t->arr[head_i].rchild == -1)

printf("%s—— %d '%c'\n", dir? "┌":"└",

t->arr[head_i].weight, t->arr[head_i].ch);

else if (head_i != t->total-1)

printf("%s—%02d┤\n", dir? "┌":"└", t->arr[head_i].weight);

else

printf(" %02d┤\n", t->arr[head_i].weight);

path[deep] = 1;

print_htree_ldr(t, t->arr[head_i].rchild, deep + 1, path);

}

/* 对字符进行编码 */

void code_string(char *text, HTree *t)

{

int i, j, text_len = strlen(text);

int n = 0;

for (i=0; i<text_len; i++) {

char ch = text[i];

for (j=0; j<t->total; j++) if (ch == t->arr[j].ch) {

printf("%s ", t->arr[j].code);

n += strlen(t->arr[j].code);

break;

}

}

printf("\n%d chars, Total len = %d\n", text_len, n);

}

int main(int argc, char* argv[])

{

HTree t;

char text[128]="ABAAAAEEEAAACCCCAAAACCDEA";

char code[128] = "";

int path[16]={0};

statistic_char(text, &t);

create_htree(&t);

print_htree_ldr(&t, t.total-1, 0, path);

coding(&t, t.total-1, code);

code_string(text, &t);

return 0;

}

Answer 3

高深