哈夫曼编码译码系统实验报告数据结构课程设计样本.doc

安徽大学
哈夫曼编码译码系统实验报告数据结构课程设计
哈夫曼编码译码系统实验报告数据结构课程设计
姓名：鉏飞祥
学号：E21414018
专业：软件工程
完成日期
2016/7/4

计算机科学与技术学院

1 .需求分析
 1.1问题描述
• 问题描述：运用哈夫曼编码进行通信可以大大提高信道运用率，缩短信息传播时间，减少传播成本。但是，这规定在发送端通过一种编码系统对待传数据预先编码，在接受端将传来数据进行译码（解码）。对于双工信道（即可以双向传播信息信道），每端都需要一种完整编/译码系统。试为这样信息收发站设计一种哈夫曼编译码系统。

 1.2基本规定
(1) 输入形式和输入值范畴；
(2) 输出形式；
(3) 程序所能达到功能。
1.基本规定
（1）初始化（Initialzation）。从数据文献DataFile.data中读入字符及每个字符权值，建立哈夫曼树HuffTree；
（2）编码（EnCoding）。用已建好哈夫曼树，对文献ToBeTran.data中文本进行编码形成报文，将报文写在文献Code.txt中；
（3）译码（Decoding）。运用已建好哈夫曼树，对文献CodeFile.data中代码进行解码形成原文，成果存入文献Textfile.txt中；
（4）输出（Output）。输出DataFile.data中浮现字符以及各字符浮现频度（或概率）；输出ToBeTran.data及其报文Code.txt；输出CodeFile.data及其原文Textfile.txt；

2. 概要设计
阐明本程序中用到所有抽象数据类型定义。主程序流程以及各程序模块之间层次(调用)关系。 
(1) 数据构造 
哈夫曼树节点
struct huff
{
int weight;
int parent;
int l;
int r;
};
哈夫曼编码存储
struct huff *hufftree;

(2) 程序模块
选取1到i-1中parent为0且权值最小两个下标
void Select(struct huff *HT，int n，int &s1，int &s2)
构建哈夫曼树：
void huffmancoding(struct huff *ht,int *w,int n)
对原文进行编码：
void code(char *c)
依照报文找到原文：
void decoding(char *zifu)
3. 详细设计
核心技术分析：
1：构建哈夫曼树及生成哈夫曼编码：
 依照每个字符权值不同，依照最优二叉树构建办法，递归生成哈夫曼树，并且用数组存储哈夫曼树。
再从每一叶子节点向树根遍历，求得编码
例如：
如图所示四个节点v1，v2，v3，v4，她们权值分别为7，11,4,5
V2
V1
7 11 4 5
V3
V4

第一步：选取两个权值最小节点作为左右子孩子，建立一种二叉树，双亲权值为两个自孩子之和，如图
7 11 9
V
V2
V1

V3
V4

重复第一步：
11 16
V2

V1

V3
V4

27
重复第一步：
16

V2

V1

V3
V4

则此时建立是优有二叉树，商定定左子树边编码为1，右子树编码为0，则可以对次二叉树进行编码，如图：

1 0
V2

1 0
V1

1 0
V3
V4

则各顶点编码为：
V1 01
V2 1
V3 001
V4 000
2：将原文编码：
逐个从文献读入字符，依照已经建立好哈夫曼树，找到每一字符相应编码
3：将报文译码：
环节一：
先读入一种字符，存入匹配字符串
环节二：
依照匹配串找所有哈夫曼编码，如果找到相应编码，则输入该编码所相应字符，如果找不到，则读入两个字符存入匹配串，重复环节二，找到为止。
环节三：
把剩余字符重复环节一二

4. 测试与分析
调试过程，不也许错分派空间语句却莫名让整个程序崩溃，关于编译原理和内存分派各种问题太欠缺。学了计算机构成原理与体系构造也不懂得
例如在自定义函数中：
Char **c;
C=(char **)malloc(4*sizoef(char *));
C[2]=(char *)malloc(4*sizeof(char));
这样居然会让程序这执行到这一句时崩溃，本来不也许有错误。
而这句如果写在主函数中，就不会有问题。
分派空间不大，不也许是内存不够用。
解决办法是分开，把
C=(char **)malloc(4*sizoef(char *));
放在主函数中，此外一句不变依然在自定义函数中。
malloc和free尽量配对使用，注意：malloc后普通要对返回值进行判断，避免发生不必要错误。
注意，最佳再p 被free掉后，加上p=NULL这句

“野指针”不是NULL指针，是指向“垃圾”内存（不可用内存）指针。人们普通不会错用NULL指针，由于用if语句很容易判断。但是“野指针”是很危险，if无法判断一种指针是正常指针还是“野指针”。有个良好编程习惯是避免“野指针”唯一办法。

指针p被free或者delete之后，没有置为NULL，让人误觉得p是个合法指针。别看free和delete名字（特别是delete），它们只是把指针所指内存给释放掉，但并没有把指针自身干掉。此时指针指向就是“垃圾”内存。释放后指针应及时将指针置为NULL，防止产生“野指针”
malloc函数动态申请内存空间是在堆里(而普通局部变量存于栈里)，并且该段内存不会被初始化，与全局变量不同样，如果不采用手动free()加以释放，则该段内存始终存在，直到程序退出才被系统，所觉得了合理使用内存，在不合用该段内存时，应当调用free()。此外，如果在一种函数里面使用过malloc，最佳要配对使用free，否则容易导致内存泄露（没有将内存还给自由存储区）。
但是，往往会在free时候发生段错误.

对的做法是这样：
// 在分派之前加一句判断指针与否为空，防止产生内存泄露
程序运营成果：

完美解决所提出问题。

5. 附录
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct huff
{
int weight;
int parent;
int l;
int r;
};
int mm;/*记录哈夫曼字码个数*/
struct huff *hufftree;
char **huffmancode;
void Select(struct huff *HT，int n，int &s1，int &s2)//选取函数，选出parent为零，且权值最小两个节点
{
int min1=100;
int min2=100;
int i;
for(i=1;i<=n;i++)
if((min1>HT[i].weight)&&(HT[i].parent==0))
min1=HT[i].weight;
for(i=1;i<=n;i++)
if((min1==HT[i].weight)&&(HT[i].parent==0))
{
s1=i;
break;
}
for(i=1;i<=n;i++)
if((min2>HT[i].weight)&&(HT[i].parent==0)&&(i!=s1))
min2=HT[i].weight;
for(i=1;i<=n;i++)
if((min2==HT[i].weight)&&(HT[i].parent==0)&&(i!=s1))
{
s2=i;
break;
}
}
int pipei(char *c)/*在huffmancode寻找匹配编码*/
{
int i;
for(i=1;i<mm;i++)
{
if(strcmp(c,huffmancode[i])==0)
{
return i;
break;
}
}

return 0;

}
void decoding(char *zifu)/*对哈夫曼编码进行译码*/
{
FILE *fp,*fp1;
int i,j,p,ii;
int n;
char c[11];
for(i=0;i<10;i++)
c[i]='\0';
printf("codefile.txt报文为：\n");
if((fp=fopen("codefile.txt","r"))==NULL)
{
printf("error\n");
}

char a[100];
for(i=1;;i++)
{
fscanf(fp,"%c",&a[i]);
if(a[i]=='#')
break;
printf("%c",a[i]);
}
printf("\n");
fclose(fp);
if((fp1=fopen("testfile.txt","w"))==NULL)
{
printf("error\n");
}
i=1;
j=1;
int m=1;
printf("相应原文为\n");
while(true)
{

if(a[m]=='#')
break;
for(j=0;j<i;j++)
{
c[j]=a[m+j];
}

n=pipei(c);
if(n!=0)
{

fprintf(fp1,"%c",zifu[n]);
printf("%c",zifu[n]);
m=m+i;
i=1;
}
else
i++;
for(ii=0;ii<10;ii++)
c[ii]='\0';

}
printf("\n");
fclose(fp1);

}
int main()
{
system("color e0")；//可以写成 red 调出颜色组

system("title huffman系统")；//设立cmd窗口标题

system("date /T");
system("TIME /T");

void huffmancoding(struct huff *ht,int *w,int n);
void code(char *c);
int i;
FILE *fp,*fp1,*fp2;
if((fp=fopen("DataFile.txt","r"))==NULL)
{
printf("error\n");
}
int w[28];

char c[28];
printf("从文献DataFile.txt读入字符和权值分别为：\n");
for(i=1;;i++)
{
fscanf(fp,"%c",&c[i]);
if(c[i]=='#')
break;
fscanf(fp,"%d",&w[i]);
printf("%c：",c[i]);
printf("%d\n",w[i]);
}
fclose(fp);
int m=i-1;
mm=i;
huffmancode=(char **)malloc(i*sizeof(char *));
huffmancoding(hufftree,w,m);
printf("各字符编码为\n");
for(i=1;i<=m;i++)
{
printf("%c：",c[i]);
printf("%s\n",huffmancode[i]);
}
code(c);
decoding(c);
return 0;
}
void code(char *c)/*依照原文进行编码*/
{

FILE *fp,*fp1;
int i,j;
char a[100];
printf("tobetran.txt原文为：\n");
if((fp=fopen("tobetran.txt","r"))==NULL)
{
printf("error\n");
}
for(i=1;;i++)
{

fscanf(fp,"%c",&a[i]);

if(a[i]=='#')
{

printf("\n");
break;
}
printf("%c ",a[i]);

}
fclose(fp);

if((fp1=fopen("code.txt","w"))==NULL)
{
printf("error\n");
}
printf("相应报文为：\n");
for(i=1;;i++)
{
if(a[i]=='#')
break;
for(j=1;j<=26;j++)
{
if(a[i]==c[j])
{
fprintf(fp1,"%s",huffmancode[j]);
printf("%s",huffmancode[j]);
break;
}
}
}
printf("\n");

fclose(fp1);

}
void huffmancoding(struct huff *ht,int *w,int n)/*构建哈夫曼树和哈夫曼编码*/
{

if(n<=1)
return;
int m,i;
m=2*n-1;
ht=(struct huff *)malloc((m+1)*sizeof(struct huff));
struct huff *p;
for(p=ht,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->l=0;
p->r=0;
}
for(;i<=m;i++,p++)
{
p->l=0;
p->weight=0;
p->parent=0;
p->r=0;
}
for(i=1;i<=4;i++)
for(i=n+1;i<=m;i++)
{
int s1,s2;
Select(ht,i-1,s1,s2);
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].l=s1;
ht[i].r=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}

char *cd;
cd=(char *)malloc(n*sizeof(char));
cd[n-1]='\0';

int start,c,f;
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].l==c)
cd[--start]='0';
else
cd[--start]='1';
huffmancode[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(huffmancode[i],&cd[start]);

}
free(cd);

}
6. 顾客使用手册
运营程序即可。
如果变化，可以变化文献datafile.txt，codefile.txt中值