题目利用二进制编码模拟信息的真实传输过程.docx
《题目利用二进制编码模拟信息的真实传输过程.docx》由会员分享，可在线阅读，更多相关《题目利用二进制编码模拟信息的真实传输过程.docx（21页珍藏版）》请在冰点文库上搜索。
题目利用二进制编码模拟信息的真实传输过程
题目：
利用二进制编码模拟信息的真实传输过程
哈夫曼编/译码器
姓名：
宋力完成日期：
11.2
一．需求分析
1．进行快速远距离通信的主要手段是电报，即将需传送的文字转换成二进制字符串
2．本程序的目的是解决通信过程中的编码和译码问题
3．程序中传输的是二进制“字符串”（实际每个字符占8位），这只是模拟真实传输的过程
4．测试数据可由用户输入
5．说明：
编码和译码程序是分开进行的，因此，具有一定的实用性。
比如：
我用编码器输入一段字符串，然后将编码后的二进制文本（只含0与1）发送到对方，对方接收到该文本后，用译码器进行译码，可以还原出最初输入的字符串。
无须输入权值，程序将会自行统计字母信息和权值信息
二．概要设计
注意：
传输过程中的是二进制编码而不包括任何其他的字符，因此编码时有必要先将一些有用的信息（如：
字母）转换为二进制存储起来
编码器和译码器分处两个程序中：
A．编码器
编码器程序的主要操作包括：
1．字符串输入和求哈夫曼编码
（1）用户输入一串字符串
（2）程序自行统计出字符串中字符的种类和各字符出现的次数（即权值）
（3）用哈夫曼树对以上出现的字符按权值大小进行编码
2．生成二进制的需要传输的字符串（包括字符信息和附加信息）
（1）设要传输的字符串为char*ok,分别将以下信息包含到ok中
a.出现字符种类的个数
b.字母对应ASC码转化为二进制后的编码
c.字母之间的分隔标记00000001
d.输入的字符串转化后的二进制字符串
（2）将包含以上信息的串ok存入文件（“字符串的二进制编码.txt”）中
B．译码器
译码器的主要操作包括：
1．接收文本中的二进制字符串
2．对字符串进行翻译，译码得到相应的字母
3．译码得到一串字符串
4．将得到字符串并将其输入到文本（"字符串的二进制编码.txt"）中
5．打开文本比较文本中的字符串，发现译出的字符串与原来输入的字符串相同
该程序用到的抽象数据类型
ADThufffmantree
{
数据对象：
D={ai|ai∈字母字符集，i=1,2,3……，n,n>=0}
数据关系：
R1={|ai-1,ai∈D,i=2,3,……,n}
基本操作：
voidcode（char*p,int*&w,char*&m,int&n）
初始条件：
p为一个字符串
操作结果：
生成值，用w存放权值，用m存放出现的字符,用n存放字符的个数
且最后生成一文本保存得到的编码字符串
}
以下是我程序设计的伪码：
1：
编码器
结构体:
typedefstruct权值
{charc;
intweight;
}cell,*good;
typedefstruct哈夫曼树
{
intweight;
intparent,lchild,rchild;
};
intminimum（HuffmanTreetree,inti）
初始条件：
存在哈夫曼树（可以为空）
操作结果：
返回权值最小的根结点
voidfind（HuffmanTreet,inti,int*s1,int*s2）
初始条件：
存在哈夫曼树
操作结果：
在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个
voidHuffmanCoding（HuffmanTree*HT,HuffmanCode*HC,int*&w,intn）
初始条件：
HC为指向各字符哈夫曼编码的指针，哈夫曼树存在，w存放权值
操作结果：
w保存了权值，对哈夫曼树进行了编码，保存在HC中
intsearch（chara,char*m,intz）
初始条件：
m为指向字符的指针，a为要判断的字符
操作结果：
查找m中是否出现过字符a,有则返回它的下标，没有则返回-1
voidcode（char*p,int*&w,char*&m,int&n）
初始条件：
w用来存放各字符的权值，p为指向存放字符串指针，n为字符种类树目
操作结果：
w存放了各字符的权值,将指定的字符串进行了编码，并将二进制编码保存到了文件中，另一个文件存放原始字符串
voidmain（）
{
输入信息和文件初始化，字母的权值将在后面进行统计
将字符串信息写入文件中
打开文本，用直观的形式观察输入的字符串
编码函数（包括计算权值，各输入字符的哈夫曼编码和最后将要传输的二进制编码）
将编码得到的二进制串保存到另一个文件中
}
2：
译码器
intchange（intx）
操作结果：
八位以下的伪十进制数转化为真十进制数
voidtranslate（char*s）
初始条件：
指向二进制字符串的指针s
操作结果：
进行译码操作，得到字符串，并将它一文本形式输出，可将其与原始字符串进行比较
voidmain（）
{
输入信息和文件初始化
读入二进制编码文件，并用字符指针指向二进制字符串
打开读入的二进制文本文档，以直观的形式观察该二进制字符串
进行译码操作
输出最后译码后的文本文档
}
三．详细设计
1．编码程序
//运行正常！
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#include"iostream.h"
////////////////////////////////
typedefstruct//存放权值字母的结构体
{
charc;
intweight;
}cell,*good;
///////////////////////////////
////////////////////////////////
typedefstruct//哈夫曼树结构体
{
intweight;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;
////////////////////////////////////
typedefchar**HuffmanCode;//存放哈夫曼编码的二级指针
///////////////////////////////////
intminimum（HuffmanTreetree,inti）
{//返回权值最小的树的根结点
intj,tag;
intk=10000;
for（j=1;j<=i;j++）
if（tree[j].weightk=tree[j].weight,tag=j;
tree[tag].parent=1;//根结点的双亲赋1
returntag;
}
////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////
voidfind（HuffmanTreet,inti,int*s1,int*s2）
{//在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个
intj;
*s1=minimum（t,i）;
*s2=minimum（t,i）;
if（*s1>*s2）
{
j=*s1;
*s1=*s2;
*s2=j;
}
}
//////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////
voidHuffmanCoding（HuffmanTree*HT,HuffmanCode*HC,int*&w,intn）//求字符的赫夫曼编码HC
{//w存放n个字符的权值（均>0），HT为构造的赫夫曼树
HuffmanTreehfm;
char*cd;
intm=2*n-1;
*HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;/*0号单元未用*/
inti;
/////////////////////////////////////////初始化
for（hfm=*HT+1,i=1;i<=n;++i,++hfm,++w）
{
（*hfm）.weight=*w;
（*hfm）.parent=0;
（*hfm）.lchild=0;
（*hfm）.rchild=0;
}
for（;i<=m;++i,++hfm）
（*hfm）.parent=0;
//////////////////////////////////////////
*HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;//堆首暂不使用
ints1,s2;
for（i=n+1;i<=m;++i）//建哈夫曼树
{
find（*HT,i-1,&s1,&s2）;
（*HT）[s1].parent=（*HT）[s2].parent=i;
（*HT）[i].lchild=s1;
（*HT）[i].rchild=s2;
（*HT）[i].weight=（*HT）[s2].weight+（*HT）[s1].weight;
}
//////////////////////////////////////////////////根反向求字符的赫夫曼编码
intx,start;
intk;
cd=（char*）malloc（n*sizeof（char））;
cd[n-1]='\0';//串尾结束符号
for（i=1;i<=n;i++）
{//求每个字符的赫夫曼编码
start=n-1;//存放编码终止的位置
for（x=i,k=（*HT）[i].parent;k!
=0;x=k,k=（*HT）[k].parent）
if（（*HT）[k].lchild==x）
cd[--start]='0';
else
cd[--start]='1';
（*HC）[i]=（char*）malloc（（n-start）*sizeof（char））;//分配堆空间
strcpy（（*HC）[i],&cd[start]）;
}
free（cd）;//释放堆空间
}
//查找m中是否出现过字符a,有则返回它的下标，没有则返回-1
intsearch（chara,char*m,intz）
{
intj=0;
while（j{
if（m[j]==a）
returnj;//有就返回它在m或者w中的下标（w,m中一样）
j++;
}
return-1;//没有就返回-1
}
//////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////
/*生成将要发送的二进制字符串：
包括字符种类数，字符的ASCII码,字符的哈夫曼代码，间隔标记符，哈夫曼编码串*/
voidcode（char*p,int*&w,char*&m,int&n）//进行编码
{
///////////////////////////////////////////////////////////以下代码求权值
m=（char*）malloc（sizeof（char））;//生成堆空间存放出现的字母
w=（int*）malloc（sizeof（int））;//存放字母对应的权值，其下标与上面m下标对应
inti=0,k,z=1;
while（*（p+i）!
='\0'）
{
if（z==1）//k==-1用于后面if语句的条件判断，表示没有出现
k=-1;
else
k=search（*（p+i）,m,z）;//查找，若出现字符m则返回其下标，否则返回-1（表示没有）
if（k==-1）//如果没有就加入该字符
{z++;
m=（char*）realloc（m,z*sizeof（char））;
w=（int*）realloc（w,z*sizeof（int））;//w存放对应字符的权值
m[z-2]=*（p+i）;
m[z-1]='\0';//最后一个赋'\0'
w[z-2]=1;//对应权值赋1
}
else//有就在权值上加1
w[k]++;
i++;
}
n=z-2;//共n+1个字符（不包括\0）,序号0—n，第n+1为\0
cout<<"字符"<<""<<"权值"<for（intl=0;lcout<//////////////////////////////////////////////////////////构建哈夫曼树
HuffmanTreeHT;
HuffmanCodeHC;
HuffmanCoding（&HT,&HC,w,n+1）;//调用哈夫曼编码的函数
intzz,length,totle;//下标
char*t;//后面用来存放核心字符串编码
i=1;
totle=strlen（HC[1]）+1;
t=（char*）malloc（totle*sizeof（char））;
t[0]='\0';
strcpy（t,HC[1]）;
while（*（p+i）!
='\0'）
{
zz=search（*（p+i）,m,n+2）;
length=strlen（HC[zz+1]）;
totle+=length;
t=（char*）realloc（t,totle*sizeof（char））;
strcat（t,HC[zz+1]）;//将字符编码串连接到原来的后面
i++;
}
//////////////////////////////////////////////////////存放字符种类数
char*ok=（char*）malloc（16*sizeof（char））;
ok[0]='\0';
char*guodu=（char*）malloc（8*sizeof（char））;//中间变量指针
guodu[0]='\0';//存放字母
itoa（n+1,ok,2）;//字符种类个数存入,ok后面还有几个小空间未用！
strcat（ok,"00000001"）;
////////////////////////////////////////////////存放字母的ASC码对应二进制字符串
intn1=16;//表示ok现在存放的字符串长度
for（i=0;i{
itoa（m[i],guodu,2）;//字母转化为二进制然后存入guodu中
ok=（char*）realloc（ok,（n1+strlen（guodu）+8）*sizeof（char））;//////////
n1+=strlen（guodu）+8;//////////
strcat（ok,guodu）;//输入字母代码
strcat（ok,"00000001"）;//字母之间用00000001隔开
}
free（guodu）;//释放堆空间
/////////////////////////////////////////////////存放哈夫曼码
for（i=0;i{
ok=（char*）realloc（ok,（n1+strlen（HC[i+1]）+8）*sizeof（char））;/////////////
n1+=strlen（HC[i+1]）+8;
strcat（ok,HC[i+1]）;//输入单字符对应的编码（编码出错了）
strcat（ok,"00000001"）;//要改进，用第一个编码来间隔，前面对应加入该码长度
}
/////////////////////////////////////////////////存放字符串哈夫曼编码
ok=（char*）realloc（ok,n1+strlen（t）*sizeof（char））;
strcat（ok,t）;//输入字符串编码
////////////////////////////////////////////////写入文件
FILE*fp;
if（（fp=fopen（"字符串的二进制编码.txt","wt+"））==NULL）
{
printf（"error!
"）;
exit（-1）;
}
fwrite（ok,strlen（ok）+1,1,fp）;
fclose（fp）;
free（ok）;//释放堆空间
}
/////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////
voidmain（）
{
int*w,n;
char*m;//存放出现字符的字符串
charp[256];//存入输入的字符串（若为文件则可指向它）
printf（"请输入一串字符串:
"）;
gets（p）;//输入要传输的字符串，字母的权值将在后面进行统计
FILE*fp3;//新建文本文件，并对其操作
if（（fp3=fopen（"输入的（要进行传输的）字符串.txt","wt+"））==NULL）
{
printf（"error!
"）;
exit（-1）;
}
fwrite（p,sizeof（char）,strlen（p）+1,fp3）;
fclose（fp3）;
system（"输入的（要进行传输的）字符串.txt"）;//打开该文本文件
code（p,w,m,n）;//编码函数
2．//译码程序
//接受文档中二进制的字符串，并将其译码，得到一串字符串
//运行正常
#include"stdlib.h"
#include"stdio.h"
#include"string.h"
#include"iostream.h"
//////////////////////////////////
intchange（intx）//八位以下的伪十进制数转化为真十进制数
{
inti,y=0,j=1,k=1;
if（x>11111111）//超过8位就退出
exit（-1）;
for（i=0;i<8;i++）//求十进制数，用y表示
{
y+=k*（（x/j）%10）;
j=j*10;
k=2*k;
}
returny;
}
////////////////////////////////////
////////////////////////////////////
voidtranslate（char*s）
{
inti=0,j=0,z;
char*mark1,*mark2,*flag;//均为标记指针
char*tchar;//存放字母
intn;
flag=s;
char*mid="00000001";//分隔符号
mark1=strstr（s,mid）;//找标记的首地址
while（（flag+j）!
=mark1）//累计当前地址到标记地址间的字符个数
j++;
char*ctemp;
////////////////////////////////////////////////////////
//////////////////////////////////////译出字符的种类数
ctemp=（char*）malloc（（j+1）*sizeof（char））;//开辟堆空间
for（i=0;ictemp[i]=flag[i];
ctemp[j]='\0';
n=atoi（ctemp）;//二进制整数（字符个数）
n=change（n）;//字符的种类数
//////////////////////////////////////////////////////
////////////////////////////////////////译出出现的字符
tchar=（char*）malloc（（n+1）*sizeof（char））;//存放字符
char**bm=（char**）malloc（n*sizeof（char*））;//存放小编码指针
for（z=0;z{j=0;
mark2=mark1+8;//00000001后标记
flag=mark2;
mark1=strstr（mark2,mid）;//找标记的首地址
while（（mark2+j）!
=mark1）
j++;
free（ctemp）;//释放堆空间
ctemp=（char*）malloc（（j+1）*sizeof（char））;//再次开辟空间
for（i=0;ictemp[i]=flag[i];//求表示字母ASCII码的二进制编码串
ctemp[j]='\0';
tchar[z]=（char）change（atoi（ctemp））;//译出的字母存入数组中
}
//mark1此时指向00000001前了
///////////////////////////////////////////////////////
//////////////////////////////////
char*temp;
for（z=0;z{
j=0;
mark2=mark1+8;//让mark2指向标记后
flag=mark2;
mark1=strstr（mark2,mid）;//找标记的首地址
if（mark1==mark2）//当编码为分隔标记符时另外考虑
{mark1+=8;
mark1=st
升级会员 