题目利用二进制编码模拟信息的真实传输过程.docx

1、题目利用二进制编码模拟信息的真实传输过程 题目：利用二进制编码模拟信息的真实传输过程 哈夫曼编/译码器 姓名：宋力 完成日期：11.2一 需求分析1 进行快速远距离通信的主要手段是电报，即将需传送的文字转换成二进制字符串2 本程序的目的是解决通信过程中的编码和译码问题 3 程序中传输的是二进制“字符串”（实际每个字符占8位），这只是模拟真实传输的过程 4测试数据可由用户输入 5说明： 编码和译码程序是分开进行的，因此，具有一定的实用性。比如：我用编码器输入一段字符串，然后将编码后的二进制文本（只含0与1）发送到对方，对方接收到该文本后，用译码器进行译码，可以还原出最初输入的字符串。 无须输入权

2、值，程序将会自行统计字母信息和权值信息 二 概要设计注意：传输过程中的是二进制编码而不包括任何其他的字符，因此编码时有必要先将一些有用的信息（如：字母）转换为二进制存储起来编码器和译码器分处两个程序中：A 编码器编码器程序的主要操作包括：1字符串输入和求哈夫曼编码（1） 用户输入一串字符串（2） 程序自行统计出字符串中字符的种类和各字符出现的次数（即权值）（3） 用哈夫曼树对以上出现的字符按权值大小进行编码2生成二进制的需要传输的字符串（包括字符信息和附加信息） （1） 设要传输的字符串为char *ok,分别将以下信息包含到ok中 a.出现字符种类的个数 b.字母对应ASC码转化为二进制后的

3、编码 c.字母之间的分隔标记 00000001 d.输入的字符串转化后的二进制字符串 （2） 将包含以上信息的串ok存入文件（“字符串的二进制编码.txt”）中 B 译码器译码器的主要操作包括：1接收文本中的二进制字符串2对字符串进行翻译，译码得到相应的字母3译码得到一串字符串 4将得到字符串并将其输入到文本（字符串的二进制编码.txt）中5打开文本比较文本中的字符串，发现译出的字符串与原来输入的字符串相同该程序用到的抽象数据类型 ADT hufffmantree 数据对象：D=ai|ai字母字符集，i=1,2,3，n,n=0数据关系：R1=|ai-1,aiD,i=2,3,n基本操作：void

4、 code(char *p,int *&w,char *&m,int &n) 初始条件：p为一个字符串操作结果：生成值，用w存放权值，用m存放出现的字符,用n存放字符的个数 且最后生成一文本保存得到的编码字符串以下是我程序设计的伪码：1：编码器 结构体: typedef struct 权值 char c; int weight; cell,*good; typedef struct 哈夫曼树 int weight;int parent,lchild,rchild;int minimum(HuffmanTree tree,int i)初始条件：存在哈夫曼树（可以为空）操作结果：返回权值最小的根结

5、点void find(HuffmanTree t,int i,int *s1,int *s2)初始条件：存在哈夫曼树操作结果：在i个结点中选择2个权值最小的树的根结点序号，s1为其中序号小的那个void HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *&w,int n)初始条件：HC为指向各字符哈夫曼编码的指针，哈夫曼树存在，w存放权值操作结果：w保存了权值，对哈夫曼树进行了编码，保存在HC中int search(char a,char *m,int z)初始条件：m为指向字符的指针，a为要判断的字符操作结果：查找m中是否出现过字符a,有则

6、返回它的下标，没有则返回-1void code(char *p,int *&w,char *&m,int &n)初始条件：w用来存放各字符的权值，p为指向存放字符串指针，n为字符种类树目操作结果：w 存放了各字符的权值,将指定的字符串进行了编码，并将二进制编码保存到了文件中，另一个文件存放原始字符串 void main() 输入信息和文件初始化，字母的权值将在后面进行统计将字符串信息写入文件中 打开文本，用直观的形式观察输入的字符串编码函数（包括计算权值，各输入字符的哈夫曼编码和最后将要传输的二进制编码）将编码得到的二进制串保存到另一个文件中 2：译码器int change(int x)操作结

7、果：八位以下的伪十进制数转化为真十进制数void translate(char *s)初始条件：指向二进制字符串的指针s操作结果：进行译码操作，得到字符串，并将它一文本形式输出，可将其与原始字符串进行比较void main()输入信息和文件初始化读入二进制编码文件，并用字符指针指向二进制字符串打开读入的二进制文本文档，以直观的形式观察该二进制字符串进行译码操作输出最后译码后的文本文档三 详细设计1编码程序/运行正常！#include stdlib.h#include stdio.h#include string.h#include iostream.h/typedef struct /存放权值

8、字母的结构体char c;int weight;cell,*good; /typedef struct /哈夫曼树结构体 int weight; int parent,lchild,rchild; HTNode ,*HuffmanTree;/typedef char * HuffmanCode;/存放哈夫曼编码的二级指针/ int minimum(HuffmanTree tree,int i) / 返回权值最小的树的根结点 int j,tag; int k=10000; for(j=1;j=i;j+) if(treej.weight*s2) j=*s1; *s1=*s2; *s2=j; /vo

9、id HuffmanCoding(HuffmanTree *HT,HuffmanCode *HC,int *&w,int n)/求字符的赫夫曼编码HC / w存放n个字符的权值(均0)，HT为构造的赫夫曼树 HuffmanTree hfm; char *cd; int m=2*n-1; *HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); /* 0号单元未用 */ int i; /初始化 for(hfm=*HT+1,i=1;i=n;+i,+hfm,+w) (*hfm).weight=*w; (*hfm).parent=0; (*hfm).lchild=0;

10、(*hfm).rchild=0; for(;i=m;+i,+hfm) (*hfm).parent=0; / *HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/堆首暂不使用 int s1,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; /根反向求字符的赫夫曼编码 int x,st

11、art; int k; cd=(char*)malloc(n*sizeof(char); cdn-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,&cdstart); free(cd); /释放堆空间

12、 /查找m中是否出现过字符a,有则返回它的下标，没有则返回-1 int search(char a,char *m,int z) int j=0; while(jz-1) if(mj=a) return j; /有就返回它在m或者w中的下标（w,m中一样） j+; return -1;/没有就返回-1 / /*生成将要发送的二进制字符串： 包括字符种类数，字符的ASCII码,字符的哈夫曼代码，间隔标记符，哈夫曼编码串*/ void code(char *p,int *&w,char *&m,int &n)/进行编码 /以下代码求权值 m=(char *)malloc(sizeof(char);

13、 /生成堆空间存放出现的字母 w=(int *)malloc(sizeof(int); /存放字母对应的权值，其下标与上面m下标对应 int i=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存放对应字符的权值

14、 mz-2=*(p+i); mz-1=0;/最后一个赋0 wz-2=1;/对应权值赋1 else /有就在权值上加1 wk+; i+; n=z-2;/共n+1个字符（不包括0）,序号0n，第 n+1为0 cout字符 权值endl; for(int l=0;ln+1;l+) coutml wlendl;/构建哈夫曼树 HuffmanTree HT; HuffmanCode HC; HuffmanCoding(&HT,&HC,w,n+1);/调用哈夫曼编码的函数 int zz,length,totle;/下标 char *t;/后面用来存放核心字符串编码 i=1; totle=strlen(HC

15、1)+1; t=(char *)malloc(totle*sizeof(char); t0=0; strcpy(t,HC1); while(*(p+i)!=0) zz=search(*(p+i),m,n+2); length=strlen(HCzz+1); totle+=length; t=(char *)realloc(t,totle*sizeof(char); strcat(t,HCzz+1);/将字符编码串连接到原来的后面 i+; /存放字符种类数 char * ok=(char *)malloc(16*sizeof(char); ok0=0; char *guodu=(char *)m

16、alloc(8*sizeof(char);/中间变量指针 guodu0=0;/存放字母 itoa(n+1,ok,2);/字符种类个数存入,ok后面还有几个小空间未用！ strcat(ok,00000001);/存放字母的ASC码对应二进制字符串 int n1=16;/表示ok现在存放的字符串长度 for(i=0;in+1;i+) itoa(mi,guodu,2);/字母转化为二进制然后存入guodu中 ok=(char *)realloc(ok,(n1+strlen(guodu)+8)*sizeof(char);/ n1+=strlen(guodu)+8;/ strcat(ok,guodu);

17、/输入字母代码 strcat(ok,00000001);/字母之间用00000001隔开 free(guodu);/释放堆空间/存放哈夫曼码 for(i=0;i11111111)/超过8位就退出 exit(-1); for(i=0;i8;i+)/求十进制数，用y表示 y+=k*(x/j)%10); j=j*10; k=2*k; return y; /void translate(char *s) int i=0,j=0,z; char * mark1,* mark2,*flag;/均为标记指针 char *tchar;/存放字母 int n; flag=s; char *mid=0000000

18、1; /分隔符号 mark1=strstr(s,mid);/找标记的首地址 while(flag+j)!=mark1)/累计当前地址到标记地址间的字符个数 j+; char *ctemp; / /译出字符的种类数 ctemp=(char *)malloc(j+1)*sizeof(char);/开辟堆空间 for(i=0;ij;i+) ctempi=flagi; ctempj=0; n=atoi(ctemp);/二进制整数(字符个数) n=change(n);/字符的种类数 / /译出出现的字符 tchar=(char *)malloc(n+1)*sizeof(char);/存放字符 char

19、*bm=(char *)malloc(n*sizeof(char *);/存放小编码指针 for(z=0;zn;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;ij;i+) ctempi=flagi;/求表示字母ASCII码的二进制编码串 ctempj=0; tcharz=(char)change(atoi(ctemp);/译出的字母存入数组中 /mark1此时指向00000001前了 / / char *temp; for(z=0;zn;z+)/产生小编码字符串（不是字母编码的代码） j=0; mark2=mark1+8;/让mark2指向标记后 flag=mark2; mark1=strstr(mark2,mid);/找标记的首地址 if(mark1=mark2)/当编码为分隔标记符时另外考虑 mark1+=8; mark1=st