信息论与编码上机实习报告
学生姓名： 班 级：
学 号： 指导老师：
实验一 字典编码与解码
一、实验题目
写一个执行Lempel Ziv 算法的程序。该程序的输入可以是英文字母。它应该将字母转化为它们的ASCII码然后进行压缩。它应该输出压缩结果。用这个程序求对输入字符串所得到的的压缩。 1、输入：
①The Lempel Ziv algorithm can compress the English text by about fifty five percent. ②The cat cannot sit on the canopy of the car. 2、输出：经过字典编码后生成的码字。
二、实验目的
1、理解和掌握字典编码和解码的原理； 2、采用VC编程实现字典编码与同步解码算法。
三、LZW字典编码算法
方法一：
1、编码算法
（1）首先建立初始字典；
（2）读入数据流，将首字符预置为P；
（3）以下步骤都在while(1)大循环中处理，若满足一定条件利用break跳出循环； <1>取数据流下一个字符C；
<2>判断C是否为结束符，若成立break；不成立继续； <3>若P+C在字典中P=P+C；
<4>若P+C不在字典中，则输出P的编码，将P+C存入字典，并且P=C。 2、解码算法
（1）首先建立与编码初始字典相同的字典；
（2）接收编码，并将译码出来的字符串存放，如果刚接收到编码还不在字典中，就按照Pre+Pre[0]提前构建新的字典元素；
（3）以下步骤都在while(Codenum[i]!=0)大循环中处理：
<1>取当前接收到的编码数据进行解码得到当前字符串Curr；当前字符串首字符构成字符串Cu;
<2>如果Pre+Cu在字典里面，不新建字典元素，Pre=Curr；
<3>如果Pre+Cu不在字典里面，就新建字典元素Pre+Cu，且Pre=Curr；
图1 编码算法流程图
方法二：
1.用结构体存储字符串及其对应的字典编码； 2.用链表存储整个字典；
3.dictionary()子函数的作用是将当前字符同链表中的字典相比较，若存在与字典中，则向结构体的数组里存放发送信息的下一位，直到当前数组中的字符串和链表字典不相等则将该字符串存储到链表中，并将标号存储到加最后一位字符之前的字符串对应的结构体的code，更新字典。
4.main()函数主要是实现初始字典的构建，即’a’-’z’和’A’-’Z’的存储。
四、实验程序
方法一程序：
1：编码程序
//程序包含的头文件以及头文件说明
#include
#include
string str; //定义一个待编码的字符串变量 string dic[200]; //这是定义字典存放空间
/*************************************************************
函数名称：int Find(string s)
函数功能：在字典中寻找字符s,并返回在字典中的序号 输入参数：所要查找的字符 返 回 值：字符在字典中对应的标号 **************************************************************/ int Find(string s) {
int i,temp=-1;
for(i=0;i<200;i++)//这个地方的i<200与上面定义的dic长度相对应 {
if(dic[i]==s) temp=i+1;//字符的查找，并输出对应的相对位置 }
return temp; }
/*********************************************************
函数名称：void Dic_init()，字典初始化
函数功能：用a~z,A~Z以及一些标点符号，初始化字典 输入参数：void 返 回 值：void **********************************************************/ void Dic_init() {
int i,j;
for(j=0,i=0;i<26;i++)//将A-Z存入初始化字典 {
dic[j]='A'+i; j++; }
for(j=26,i=0;i<26;i++)//将a-z存入初始化字典 {
dic[j]='a'+i;
j++; }
dic[52]=\存入四个符号和空格 dic[53]=\ dic[54]=\ dic[55]=\ dic[56]=\}
/*************************************************************
函数名称：void code(string str)
函数功能：对输入的字符串进行LZW字典编码 输入参数：str 待编码的字符串 返 回 值：用cout输出显示编码后的码 /************************************************************/ void code(string str) {
Dic_init(); //字典初始化
char temp[2]; //定义2个字符长的字符串 temp[0]=str[0]; //取第一个字符
temp[1]='\\0'; //将第2个设置为空格
string P=temp; //P为前缀，将temp赋给字符串P int i=1; //下面从第2个字符开始
int j=57; //目前字典存储的最后一个位置 cout<<\编码为：\ while(1) {
char t[2]; //定义2个字符长的字符串
t[0]=str[i]; //取下一字符,通过下面的i++实现后移 t[1]='\\0'; //将第2个设置为结束标志 string C=t; //C为字符流中下一个字符 if(C==\ //无码字要译，结束 {
cout<<\输出代表当前前缀的码字 break; //退出循环,编码结束 }
if(Find(P+C)>-1) //如果P+C在词典中，则P=P+C，然后后移 {
P=P+C; i++; }
else //如果P+C不在词典中，则将P+C添加到词典中，同时P=C {
cout<<\ string PC=P+C;