Question

数据结构课程设计题，求救高手～～帮个忙，还有悬赏分哦～

题目：编制一个可进行传数据编码及接收数据译码的编/译系统

要求：（1）用Huffman树给出Huffman编码；
（2）可单独或小组的形式完成，但至多3人；
（3）写出实验报告，并提交电子文档及源程序。

一、 需求分析：
1、根据用户指定的字符表和频度的实际统计数据建立Huffman树；
2、其中其叶子结点表示字符的权值及父母、左、右孩子等结点的信息；
3、其左右分支分别用代码0、1表示；
4、本系统的目的是为用户提供编/译码系统，根据用户输入的字符依字符集的权值进行编码保存；
5、根据接收到的编码进行译码；
6、输出其内容。
二、测试数据：
（1）、利用教科书(P148)例6-2中的数据调试程序。
（2）、用下表给出的字符集和频度的实际统计数据建立Huffman树，并实现以下报文的编码和译码：“THIS # PROGRAM # IS # MY # FAVORITE”。
字符 # 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
三、 详细设计：
抽象数据类型HuffmanTree的定义如下：
typedef struct
{
char data; //结点字符
int weight; //结点权值
int parent,lchild,rchild; //父子结点
}HTNode,HuffmanTree;
typedef char HuffmanCode;
基本操作P：
CreateHuffmanTree（&HT,）;
初始条件：给出HuffmanTree的定义。
操作结果：构造HuffmanTree。
HuffmanCoding(HuffmanTree HT,HuffmanCode &HC)
初始条件：HT存在。
操作结果：得出编码HC。
PrintHuffmanCode(HuffmanTree HT,HuffmanCode HC)
初始条件：HT，HC存在。
操作结果：显示字符与其对应的编码。
g(int)
初始条件：HT，HC存在。
操作结果：从根到叶子遍历树，得出译码。

Answer 1

我这里有个程序是编码用的:(C++)
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<math.h>

struct htnode
{
char ch;
int weight,parent,lchild,rchild;
};
struct hc
{
char *code;
char word;
int size;
};

void select(struct htnode * ht,int n,int& s1, int& s2)
{
int small1=9999, small2=9999,i;
for(i=1;i<=n-1;i++)
{
if(ht[i].weight<small1&&ht[i].parent==0)
{
small1=ht[i].weight;
s1=i;
}
++i;
if(ht[i].weight<small2&&ht[i].parent==0)
{
small2=ht[i].weight;
s2=i;
}
}
}

void reduce()
{
FILE *fpin,*fpout;
int cut[256];
int i,k;
char flag;
double j=0;
for(i=0;i<=255;i++)
cut[i]=0;
fpin=fopen("code.txt","r");
fpout=fopen("reduce.txt","wb");
i=0;
while(fread(&flag,sizeof(char),1,fpin))
{

if(flag=='1')
{
cut[i]=(cut[i])|(int)(pow(2,(7-j)));
}
j=j+1;
if(j==8)
{
j=0;
i++;
}
}
for(k=0;k<=i;k++)
{
fwrite(&cut[k],sizeof(int),1,fpout);
}
printf("\n");
fclose(fpin);
fclose(fpout);
}

void unreduce()
{
FILE *fpin;
fpin=fopen("reduce.txt","r");
double j=0;
int flag,uncut[256],k=0,i;
while(fread(&flag,sizeof(int),1,fpin))
{

for(j=0;j<=7;j=j+1)
if(flag&(int)(pow(2,(7-j))))
uncut[k++]=1;
else
uncut[k++]=0;
}
for(i=0;i<k-8;i++)
printf("%d",uncut[i]);
fclose(fpin);
}

void translate(struct hc *hcc,int n)
{
int i,j,k;
FILE *fpin,*fpout;
char text[255];
for(k=0;k<255;k++)
text[k]='\0';
k=0;
fpin=fopen("code.txt","r");
fpout=fopen("translate.txt","w");
while(!feof(fpin))
{
text[k++]=fgetc(fpin);
for(i=1;i<=n;i++)
if(strcmp(text,hcc[i].code)==0)
{
fprintf(fpout,"%c",hcc[i].word);
for(j=0;j<k;j++)
text[j]='\0';
k=0;
}
}
fclose(fpin);
fclose(fpout);
}

void huffmancodeing(int w[256],char word[255],int n,char text[255])
{
FILE *fp,*fpp;
fp=fopen("huffmancode.txt","w");
struct hc *hcc;
char *cd;
int i,c,f,start,k=0,s1,s2;
struct htnode *ht;
int m=2*n-1;
if(n<=1) return;
ht=(struct htnode *)malloc(sizeof(struct htnode)*(m+1));
for(i=1;i<=n;i++)
{
ht[i].ch=word[i-1];
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].weight=w[ht[i].ch];
}
for(i=1;i<=n;i++)
printf("%c,%d",ht[i].ch,ht[i].weight);
printf("\n");
for(i=n+1;i<=m;i++)
{
ht[i].ch=word[i-n];
ht[i].parent=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].weight=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;
}
hcc=(struct hc *)malloc((n+1)*sizeof(struct hc));
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';
hcc[i].code=(char *)malloc((n-start)*sizeof(char));
strcpy(hcc[i].code,&cd[start]);
hcc[i].word=ht[i].ch;
hcc[i].size=n-start-1;
}
free(cd);
for(i=1;i<=n;i++)
fprintf(fp,"%c:%s",hcc[i].word,hcc[i].code);
fclose(fp);
fpp=fopen("code.txt","wb");
while(text[k]!='\0')
{
for(i=1;i<=n;i++)
if(text[k]==hcc[i].word)
{
fwrite(hcc[i].code,sizeof(char)*hcc[i].size,1,fpp);
//fprintf(fpp,"%s",hcc[i].code);
}
k++;
}
fclose(fpp);
for(i=1;i<=n;i++)
printf("%c:%s\n",hcc[i].word,hcc[i].code);
translate(hcc,n);
reduce();
unreduce();
}

void main()
{
FILE *fpin;
char file[20];
printf("请输入要压缩的文件名\n");
gets(file);
fpin=fopen(file,"r");
int w[256],i,j,k,m=0,flag,n=0;
for(i=0;i<=255;i++) w[i]=0;
i=k=0;
char ch,word[256],text[256],code[256];
while(!feof(fpin))
code[m++]=fgetc(fpin);
fclose(fpin);
code[--m]='\0';
m=0;
while(code[m])
{
ch=code[m];
m++;
text[k++]=ch;
flag=0;
w[ch]++;
for(j=0;j<=255;j++)
if(word[j]==ch)
flag=1;
if(flag==0)
{
word[i]=ch;
n++;
i++;
}

}
word[i]='\0';
text[k]='\0';
huffmancodeing(w,word,n,text);
}

详细建树过程:
#include<string.h>
#include<stdlib.h>
#include<stdio.h>

int m,s1,s2;

typedef struct {
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char *HuffmanCode;

void Select(HuffmanTree HT,int n) {
int i,j;
for(i = 1;i <= n;i++)
if(!HT[i].parent){s1 = i;break;}
for(j = i+1;j <= n;j++)
if(!HT[j].parent){s2 = j;break;}
for(i = 1;i <= n;i++)
if((HT[s1].weight>HT[i].weight)&&(!HT[i].parent)&&(s2!=i))s1=i;
for(j = 1;j <= n;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) {

int i, j;
char *cd;
int p;
int cdlen;

if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
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;
}

printf("HT start:\n node weight parent lchild rchild");
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++) {

Select(HT, i-1);
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;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf("node weight parent lchild rchild");
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));
p = m; 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].lchild; 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].rchild; cd[cdlen++] ='1'; }
} else {
HT[p].weight = 0; p = HT[p].parent; --cdlen;
}
}
}
main() {
HuffmanTree HT;HuffmanCode *HC;int *w,n,i;
puts("input the number of node:");
scanf("%d",&n);
HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode));
w = (int *)malloc(n*sizeof(int));
printf("input the percent of %d node:\n",n);
for(i = 0;i < n;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,n);
puts("\n the huffman code of the nodes :");
for(i = 1;i <= n;i++)
printf("%2d(%4d):%s\n",i,w[i-1],HC[i]);
getchar();
}