数据结构课程设计--哈夫曼编码问题的设计和实现.doc

成绩课程设计说明书(论文)题 目 哈夫曼编码问题的设计和实现 课 程 名 称 数据结构课程设计 院（系、部、中心） 专 业 班 级 学 生 姓 名 学 号 设 计 地 点 指 导 教 师 设计起止时间：2008 年6月 2日至 2008 年 6月 6 日 目录1问题描述21.1题目内容21.2基本要求21.3测试数据22需求分析22.1程序的基本功能22.2输入值、输出值以及输入输出形式22.3各个模块的功能要求33概要设计43.1所需的ADT，每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）43.2主程序流程以及模块调用关系43.3各个模块的算法设计说明44详细设计74.1数据类型74.2函数调用85各个算法实现的源程序86调试分析117使用说明128测试结果129源程序121 问题描述1.1 题目内容 哈夫曼编码问题的设计和实现 输入一个英文字符串，对该字符串中各字符个数进行统计取得各字符的出现次数；以其出现次数作为关键字建立哈夫曼树并进行编码，最后输出各个字符对应的码值。1.2 基本要求要求：设计存储结构、基本算法（主要采用程序流程图体现）；完成基本算法的实现代码；设计测试输入数据对程序进行测试，分析输出结果数据、算法的时间复杂度分析，如有改进算法则提出算法的改进方法。1.3 测试数据 测试数据三组： AAAABBBCCD(判断连续的字符串是否可行) AABBAABCDC(判断间段的字符串是否可行) AAAA BBBCCD(判断含空格的字符串是否可行)2 需求分析2.1 程序的基本功能该程序大体上有两个功能：1 输入任何一个字符串后，该程序能统计不同字符串的个数，并以不同字符串的个数作为权值。2 已知不同字母的权值，以该权值作为叶结点，构造一棵带权路径最小的树，对该树从叶结点到根结点路径分支遍历，经过一个分支就得到一位夫曼编码值。（规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码）2.2 输入值、输出值以及输入输出形式输入值 ：AAAABBBCCD输出值 ：W =4 C=0 W=3 C=10 W=2 C=111 W=1 C=110输入值 ：AABBAABCDC输出值 ：W=4 C=0 W=3 C=10 W=2 C=111 W=1 C=110输入值 ：AAAA BBBCCD输出值 ：W=4 C=11 W=1 C=010 W=3 C=10 W=2 C=00 W=1 C=0112.3 各个模块的功能要求1 统计模块任意输入一个字符串，不论字母是否相联，字符串中是否含空格都能统计出不同字母的个数。2 建立哈夫曼树模块 以统计的字符串个数作为权值，利用仿真存储结构，建立带权路径最小的树。其中对结点的存储需要六个域，分别是 weight 域，flag域， parent域，leftChild 域，rightChild域。weight 域是对权值的存放，flag 域是一个标志域，flag=0时表示该结点尚未加入到哈夫曼树中，flag=1时表示该结点已加入到哈夫曼树中。3 哈夫曼编码模块从哈夫曼树的叶结点到根结点路径分支逐步遍历，每经过一个分支就得到一位哈夫曼编码。哈夫曼编码也利用仿真存储结构。4 主函数模块从屏幕上输入字符串，调用函数，输出每个字母的权值与编码。3 概要设计3.1 所需的ADT，每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义）抽象数据类型集合：在该程序中未用到抽象数据类型，主要用到的数据类型为 ：int ,char 。在哈夫曼树的建立与哈夫曼树的编码中用到仿真存储3.2 主程序流程以及模块调用关系输入字符串调用count 函数申请内存空间调用 Haffman调用 HaffmanCode输出权值与编码。3.3 各个模块的算法设计说明1 主函数模块开始 定义初始化变量nMaxN n y打印n越界HaffmanHaffmanCode输入i=0inj=myHaffCodei.start+1 yJn n n输出n结束 y输出权值i+j+ 主函数中利用gets输入一个字符串，调用count 函数统计不同字母的个数，在调用Haffman 函数建立哈夫曼树，然后调用HaffmanCode函数进行编码，如果成功，输出权值与编码，否则退出。开始2 统计函数 i=0,k=0n in&si!=0 ytemp=1 jn N y j=si&i!=jweightk+=temp i+ ytemp+ Pn Nj+sp=sp+1n+;j- Yp+结束统计函数在统计不同字符个数时先利用一个for循环遍历所有的字母，每遍历一个不同字母前令temp=1,然后用一个for循环将其后的字母与之比较，若相等则temp+,且将该字母从字符串中删除，否则从下一个字母遍历。如此循环直到字符串结束。3 Haffman 函数开始 int i,j,m1,m2,x1,x2i=0i2*n-1 n i=0haffTreej.weightm2&haffTreej.flag=0haffTreei.weight=weightihaffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1haffTreei.rightChild=-1;inin-1ynhaffTreei.weight=0n结束 赋值 y Jn+i ni+haffTreej.weightm1&haffTreej.flag=0yni+ym2=m1;x2=x1;m1=haffTreej.weight; x1=j;x1=j;j+y赋值Haffman函数主要以仿真结构存储信息，开始对每个域开始赋值，再根据不同的情况对每个域的值进行修改，如此循环下去，直到每个域的值修改完全。4 HffmanCode 函数开始 初始化inn结束parent！=0ynjbitcd-start=1haffCodei.bitj=cd-bitj;i+haffCodei.start=cd-start haffCodei.weight=cd-weight;ycd-bitcd-start=0cd-start-;child=parent;parent=haffTreechild.parent;HaffmanCode 函数主要以仿真结构存储信息 ，由叶结点向根结点遍历，从数据域start域开始编码，bit数组存放编码，其编码为0，1序列.。4 详细设计4.1 数据类型 typedef structint weight; /*权值*/int flag; /*标记*/int parent; /*双亲结点下标*/int leftChild; /*左孩子下标*/int rightChild; /*右孩子下标*/HaffNode; /*哈夫曼树的结点结构*/typedef structint bitMaxN; /*数组*/int start; /*编码的起始下标*/int weight; /*字符的权值*/Code; /*哈夫曼编码结构*/ int weight16; /*用于存放权值*/char s30; /* 存放字符串*/主函数模块4.2 函数调用哈夫曼树建立函数 统计函数模块哈夫曼树编码函数5 各个算法实现的源程序1.字符串统计源程序:int count(char * s,int * weight,int n)int i,j,temp,k=0,p;for(i=0;in&si!=0;i+)temp=1;for(j=0;jn;j+) /*遍历相同的字母*/if(sj=si&i!=j)temp+;for(p=j;pn;p+) /*删除相同的字母*/sp=sp+1;n-;j-; weightk+=temp; /*temp 作为权值赋给weight数组*/return i; /*返回权值个数*/2哈夫曼树建立源程序void Haffman( int weight,int n,HaffNode haffTree)/*建立叶结点个数为n，权值数组为weight的哈夫曼树haffTree*/int i,j,m1,m2,x1,x2;for(i=0;i2*n-1;i+)if(in)haffTreei.weight=weighti;elsehaffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/*构造哈夫曼树haffTree的n-1个非叶结点*/for(i=0;in-1;i+)m1=m2=MaxValue;x1=x2=0;for(j=0;jn+i;j+)if(haffTreej.weightm1&haffTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;elseif(haffTreej.weightm2&haffTreej.flag=0)m2=haffTreej.weight;x2=j;/*将找出的两颗权值最小的子树合并为一棵子树*/haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1;haffTreen+i.weight=haffTreex1.weight+haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.rightChild=x2; 3哈夫曼树编码函数void HaffmanCode(HaffNode haffTree,int n,Code haffCode)/*由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode*/ Code *cd=(Code *)malloc(sizeof(Code);int i,j,child,parent;/*求n个结点的哈夫曼编码*/for(i=0;istart=n-1;cd-weight=haffTreei.weight;child=i;parent=haffTreechild.parent;/*由叶结点向上直到根结点*/while(parent!=0)if(haffTreeparent.leftChild=child)cd-bitcd-start=0; /*左孩子分支编码0*/elsecd-bitcd-start=1; /*左孩子分支编码1*/cd-start-;child=parent;parent=haffTreechild.parent;for(j=cd-start+1;jbitj; /*保存每个叶结点的编码*/haffCodei.start=cd-start; /*保存不等长编码的起始位置*/haffCodei.weight=cd-weight; /*保存相应字符的权值*/6 调试分析 测试数据与输出结果与2.2结果相同。对过函数的分析：1count 函数:最坏情况下时间复杂度为O(n*n*n),调试时必须给定字符串的长度，否则会输出乱码，这很不方便。只要在条件语句中加上”si!=0” ,就能解决。同时对入含空格的字符串不能正确统计，因为输入字符串是以scanf 的形式输入，scanf 遇到空格自动结束，将scanf 改为gets 即可，出现gets(s);2Haffman函数在最坏情况下计算的次数为2*n-1+(3*n-3)*n/2时间复杂度最坏情况下为O(n*n); Haffman函数在书写时要注意定义变量的位置。3HaffmanCode函数在最坏情况下计算的次数为n*(3*n-1),时间复杂度为O(n*n); HaffmanCode函数在书写时要注意定义变量的位置。4主函数的时间复杂度又输入的字符串决定。曾在主函数中将printf(输入:n); get(s),n=count(s,weight,30)放在Haffman(weight,n,myHaffTree);HaffmanCode(myHaffTree,n,myHaffCode)前面，出现很多问题，像“HaffNode undefine”,”see undeclear HaffNode”等， 调整后没有问题。主函数的时间复杂度由输入的字符串决定。 算法改进设想：由于统计函数时间复杂度较高，是否降低其时间复杂度?统计函数中用到三个循环，一个用于遍历所有字符，一个用于寻找相同字符，一个用于删除相同字符。而且三个循环嵌套，如果能减少循环的次数或者是由较少的循环嵌套，就能降低时间复杂度了。7 使用说明在写源程序前先将所要用到的函数都写好，以“haffman.h”保存起来。再书写主函数，保存到相同的位置。在vc环境下，用“Build”里面的“complie”，进行编译 ，运行。利用Debug中的F5,F10,F9,F11设置断点等进行调试。8 测试结果 9 源程序 包含哈夫曼树和图，以哈夫曼树为主要。图在压缩文件中 哈夫曼树#include#include#define MaxValue 10000#define MaxBit 4#define MaxN 10 typedef structint weight; /*权值*/int flag; /*标记*/int parent; /*双亲结点下标*/int leftChild; /*左孩子下标*/int rightChild; /*右孩子下标*/HaffNode; /*哈夫曼树的结点结构*/typedef structint bitMaxN; /*数组*/int start; /*编码的起始下标*/int weight; /*字符的权值*/Code; /*哈夫曼编码结构*/void Haffman( int weight,int n,HaffNode haffTree)/*建立叶结点个数为n，权值数组为weight的哈夫曼树haffTree*/int i,j,m1,m2,x1,x2;for(i=0;i2*n-1;i+)if(in)haffTreei.weight=weighti;elsehaffTreei.weight=0;haffTreei.parent=0;haffTreei.flag=0;haffTreei.leftChild=-1;haffTreei.rightChild=-1;/*构造哈夫曼树haffTree的n-1个非叶结点*/for(i=0;in-1;i+)m1=m2=MaxValue;x1=x2=0;for(j=0;jn+i;j+)if(haffTreej.weightm1&haffTreej.flag=0)m2=m1;x2=x1;m1=haffTreej.weight;x1=j;elseif(haffTreej.weightm2&haffTreej.flag=0)m2=haffTreej.weight;x2=j;/*将找出的两颗权值最小的子树合并为一棵子树*/haffTreex1.parent=n+i;haffTreex2.parent=n+i;haffTreex1.flag=1;haffTreex2.flag=1;haffTreen+i.weight=haffTreex1.weight+haffTreex2.weight;haffTreen+i.leftChild=x1;haffTreen+i.rightChild=x2;void HaffmanCode(HaffNode haffTree,int n,Code haffCode)/*由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode*/ Code *cd=(Code *)malloc(sizeof(Code);int i,j,child,parent;/*求n个结点的哈夫曼编码*/for(i=0;istart=n-1;c