数据结构c语言版的 课程设计
发布网友
发布时间：2022-05-04 20:59
共3个回答
热心网友
时间：2022-06-25 20:43
利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编／译码系统。试为这样的信息收发站写一个哈夫曼码的编／译码系统。
二、基本要求：
1、I：初始化（Initialization），从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
2、E：编码（Encoding），利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读人），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
3、D：译码（Decoding），利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
4、P：输出代码文件（Print），将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。
5、T：输出哈夫曼树（TreePrinting），将已在内存中的哈夫曼树以直观的方式（树或凹人表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
三、测试数据：]
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“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 1 5 32 20 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、用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出运行Quit。请用户键入一个选择功能符。此功能执行完毕后再显示此菜单，直至某次用户选择了“Q”为止。
3、在程序的一次执行过程中，第一次执行I、D或C命令之后，哈夫曼树已经在内存了，不必再读入。每次执行中不一定执行I命令，因为文件hfmTree可能早已建好。
#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);
}
热心网友
时间：2022-06-25 20:44
热心网友
时间：2022-06-25 20:44
