数据结构课程设计-赫夫曼编码的应用.docx

西南大学计算机与信息科学学院课程设计报告课程：数据结构课程设计题目：赫夫曼编码的应用级、专业：2014级计算机专业2 班学生姓名：提交日期： 2016年 06月 23日内容提要：这次的数据结构课程设计分为两个部分：基础部分和综合部分。基础的部分只是为了巩固基础知识，综合设计是主要部分。基础部分：基础部分是为了巩固加强基础知识，为综合的实验报告奠定基础。其中的内容包括一元多项式的相加，图的基本操作，树的基本操作。从基础部分着手，简单的两个多项式的相加的实现，图的基本操作的实现，树的基本操作的实现。综合部分：综合部分针对综合的设计能力的锻炼，在基础的部分上增强。综合部分就是做赫夫曼编码译码系统。输入一些字符串或者是英文句子，根据字符出现的比重进行权值的计算，从而建立赫夫曼树，赫夫曼树是赫夫曼编码的基础，在赫夫曼树建立之上对其进行编码和译码。首先实现的是编码，其次是译码。根据每个字符的编码，译码的时候，输入密文，会自动的去编码表中寻找匹配的字符，从而进行译码，并打印出译码的明文。关键词：赫夫曼树编码电文译码链表图数据结构指针参考书目：数据结构（c语言版）清华大学出版社严蔚敏吴伟民编著数据结构课程设计第2版机械工业出版社苏仕华魏韦巍王敬生刘燕君编著成绩评定：指导教师（签字）：年月日目录一、 基础设计部分011. 问题描述012. 功能需求分析013. 总体设计014. 详细设计025. 源代码036. 测试177. 总结18二、 综合设计部分201. 问题描述202. 功能需求分析203. 总体设计214. 详细设计225. 源代码256. 测试307. 总结31三、 参考文献3131一、基础部分课程设计1 问题描述基础部分有三个基础的简单的程序。在这三个简单的课程设计之中要实现一元多项式的相加、图的基本操作以及树的基本操作。针对一元多项式相加的问题，如何实现在屏幕上把输入的两个要相加的一元多项式分别的显示出来以及相加以后的结果以多项式的形式显示出来？针对图的基本操作，如何实现用领接矩阵建立一个图？如何在建立好一个图的基础上实现广度优先和深度优先遍历等等问题？针对树的综合，如何运用二叉链表建立树？以及二叉链表的遍历（包括先序、中序、后序、递归、非递归等）的实现等问题的解决？2 功能需求分析 一元多项式的相加：一元多项式的相加运算主要完成的是分别输入两个多项式，实现两个多项式指数对应的项的系数相加，并把相加的结果在屏幕上打印出来。在开始的时候输入每个多项式的项数之后再以成对的形式输入系数和指数，然后对应指数相等的项系数相加合并。 图的综合：图的综合实现了以邻接矩阵的方式构造一个图，而且在此基础上面广度优先和深度优先实现图的遍历。输入一个图的节点个数，再输入每个节点的符号，依次输入两个节点之间的路径长度构造邻接矩阵，并以广度优先和深度优先实现图的遍历过程。 树的基本操作：树的基本操作实现的功能包括输入字符建立二叉链表构造树，先序、中序以及后序遍历用递归算法实现，求二叉树的叶子个数以及借助队列实现二叉树的层次遍历。3 总体设计基础部分的总体结构：基础部分一元多项式的相加树的综合图的综合二叉树的叶子结数以及层次遍历遍历二叉树建立二叉链表实现两个多项式的相加邻接矩阵构造图在屏幕上打印出计算结果分别输入两个多项式图的遍历：广度优先和深度优先4 详细设计1. 一元多项式的相加结构体：typedef int elemtype; typedef struct polynnode /*单项链表的声明*/ int coef; / 系数 int expn; / 指数struct polynnode *next; polynnode,*polynlist; /*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/ /*指数系数一对一对输入*/2. 图的基本操作的结构体：struct stuchar name3;struct sttstruct stu ding10;int jz1010;int dd;struct shustruct stu * p;struct shu * l;struct shu * r;3. 树的基本操作的结构体：int dep, count= 0;typedef int status;typedef char telemtype;typedef struct bitnode telemtype data; struct bitnode *lchild, *rchild; /*右孩子，左孩子*/bitnode, *bitree;5 源代码 一元多项式的相加的源程序代码：#include#include#includetypedef int elemtype; typedef struct polynnode /*单项链表的声明*/ int coef; / 系数 int expn; / 指数struct polynnode *next; polynnode,*polynlist; /*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/ /*指数系数一对一对输入*/ void createpolyn(polynlist &l,int n) int i; polynlist p,q; l=(polynlist)malloc(sizeof(polynnode); / 生成头结点 l-next=null; q=l; printf(n 成对输入多项式ha的%d个数据:,n); for(i=1;icoef,&p-expn); /指数和系数成对输入 q-next=p; q=q-next; p-next=null; / 初始条件：单链表l已存在/ 操作结果: 依次对l的每个数据元素调用函数vi()。一旦vi()失败,则操作失败void polyntraverse(polynlist l,void(*vi)(elemtype, elemtype) polynlist p=l-next; while(p) vi(p-coef, p-expn); if(p-next) printf( + ); /+号的输出，最后一项后面没有+ p=p-next; printf(n); /*listtraverse()调用的函数(类型要一致)*/ void visit(elemtype c, elemtype e) if(c != 0) printf(%dx%d,c,e); /格式化输出多项式每一项 /* 多项式相加，原理：归并 */ /* 参数：两个已经存在的多项式 */ /* 返回值：归并后新的多项式的头结点 */ polynlist mergelist(polynlist la, polynlist lb) polynlist pa, pb, pc, lc; pa = la-next; pb = lb-next; lc = pc = la; / 用la的头结点作为lc的头结点while(pa&pb) if(pa-expn expn) pc-next = pa; /如果指数不相等，pc指针连上指数小的结点，pc = pa; pa = pa-next; /指向该结点的指针后移 else if (pa -expn pb-expn ) pc-next = pb; /pc指针连上指数小的结点，pc = pb; pb = pb-next; /指向该结点的指针后移 else /(pa -expn = pb-expn ) pa-coef = pa-coef + pb-coef; /指数相等时，系数相加pc-next = pa; pc = pa; pa = pa-next; /两指针都往后移pb = pb-next; pc-next = pa ? pa:pb; / 插入剩余段return lc; int main() int m,n; polynlist ha,hb,hc;printf(1.输入第一个多项式的项数:);scanf(%d,&m); printf( 非递减输入多项式ha ); createpolyn(ha,m); / 正位序输入n个元素的值printf(n); printf(2.输入第二个多项式的项数:);scanf(%d,&n); printf( 非递减输入多项式hb ); createpolyn(hb,n); / 正位序输入n个元素的值printf(n); printf(3.多项式ha :); polyntraverse(ha, visit); printf(n); printf(4.多项式hb :); polyntraverse(hb, visit); printf(n); printf(5.一元多项式的相加结果为：); hc = mergelist(ha,hb); polyntraverse(hc, visit); 图的基本操作的源程序代码：#include #include#includestruct stuchar name3;struct sttstruct stu ding10;int jz1010;int dd;struct shustruct stu * p;struct shu * l;struct shu * r;struct stt * jltu()int i=0,j=0;struct stt * p;p=(struct stt *)malloc(sizeof(struct stt);p-dd=0;for(;i10;i+)for(j=0;jjzij=100;return p;void txtu(struct stt * p)void scjd(struct stt * p);int i,j=0;printf(输入节点数:（dd=i;while(i-)printf(输入第%d个结点名字:n,p-dd-i);gets(p-dingj+.name);printf(构造邻接矩阵:（各节点间的距离，无联系为:100）n);for(i=0;idd;i+)for(j=i+1;jdd;j+)printf(输入点%s与点%s的距离:n,,);scanf(%d,&p-jzij);p-jzji=p-jzij;scjd(p);void scjd(struct stt * p)int i=p-dd,j=0;printf(顶点数:%dn,i);while(i-)printf(姓名:%sn,);j+;printf(邻接矩阵为:n);for(i=0;i10;i+)for(j=0;jjzij);printf(n);void bianli(struct stt * p)void gdbl(struct stt * p,int i,int b10);void sdbl(struct stt * p,int i,int b10);int i,j,b10=1,1,1,1,1,1,1,1,1,1;i=p-dd;while(i-)bi=0;printf(从第几个结点开始遍历？n);scanf(%d,&i);j=i;printf( 深度遍历:n);sdbl(p,i,b);i=p-dd;while(i-)bi=0;printf(n);printf( 广度遍历:n);gdbl(p,j,b);void gdbl(struct stt * p,int i,int b10)int pd(int b10);int j=0,m,k=0,a10=11,11,11,11,11,11,11,11,11,11;aj+=i;bi=1;while(!pd(b)i=ak;m=0;while(mjzim!=100&!bm) aj+=m;bm=1;m+;k+;k=0;while(ak!=11)printf(-%s-,p-dingak+.name);int pd(int b10)int i=0;while();bi=1;while(jdd)if(pd(b) break;if(p-jzij!=100&!bj) sdbl(p,j,b);j+;void scs(struct stt * p)int i,j,k=0,m,n;int a10,b10;struct shu * gen,* p1;printf(选择根结点:n);scanf(%d,&j);n=j;for(i=0;i10;i+)ai=j;for(i=0;ijzji;while(k+dd)for(i=1,j=0;ibi) j=i;bj=bj+100;for(m=0;mjzjmbm&bmjzjm;am=j;i=0;while(i10)printf( %d ,ai+);printf(这个数组每个位置是其值的孩子，不一定是二叉树所以出现下一个相同值时其位置为该值左孩子的右孩子,依次类推。n);int main()struct stt * p;p=jltu();txtu(p);bianli(p);printf(n);scs(p);return 0; 树的基本操作的源程序代码：#include #include#include#define ok 1#define error 0#define overflow -1#define list_int_size 100#define listincrement 10int dep, count= 0;typedef int status;typedef char telemtype;typedef struct bitnode telemtype data;struct bitnode *lchild, *rchild;bitnode, *bitree;/建立二叉树status createbitree(bitree &t)char ch;getchar();scanf(%c, &ch);if(ch = | ch = n) t = null;return error; else t = (bitree)malloc(sizeof(bitnode); t-data = ch;printf(请输入%c的左孩子：, t-data);createbitree(t-lchild); printf(请输入%c的右孩子：, t-data);createbitree(t-rchild);return ok; /主菜单void print()printf(n菜单：n);printf(1 . 输入字符序列，建立二叉链表n);printf(2 . 先序、中序、后序遍历二叉树:递归算法n);printf(3 . 中序遍历二叉树:非递归算法n);printf(4 . 求二叉树的叶子个数n);printf(5 . 借助队列实现二叉树的层次遍历n);printf(0 . exitn请选择操作序号：);/先序、中序、后序遍历二叉树:递归算法void print2() printf(n递归算法遍历二叉树，菜单如下：n);printf(1.先根遍历n); printf(2.中序遍历n);printf(3.后续遍历n); printf(0.退出n); printf(请输入二级菜单选择:);status visit(bitree t)if(t) printf(%c , t-data);return ok; status printelement(telemtype e)printf( %c , e);return ok;/先序status preordertraverse(bitree t, status (*visit)(telemtype e)if(t) if(visit(t-data)if(preordertraverse(t-lchild, visit)if(preordertraverse(t-rchild, visit)return ok;return error; elsereturn ok; /中序status midordertraverse(bitree t, status (*visit)(telemtype e)if(t) if(midordertraverse(t-lchild, visit)if(visit(t-data)if(midordertraverse(t-rchild, visit)return ok;return error;elsereturn ok;/后序status lastordertraverse(bitree t, status (*visit)(telemtype e)if(t) if(lastordertraverse(t-lchild, visit)if(lastordertraverse(t-rchild, visit)if(visit(t-data)return ok;return error; elsereturn ok;/求树的叶子的个数,和打印出叶子status leafnumtree(bitree t)int lnum,rnum;if(t!=null) if(t-lchild=null & t-rchild=null)return 1;else lnum=leafnumtree(t-lchild);rnum=leafnumtree(t-rchild);return lnum+rnum; return 0;/求二叉树的高度status bitreedepth(bitree t)int l,r;if(t) l=bitreedepth(t-lchild); r=bitreedepth(t-rchild);if(l=r)dep += l;else dep += r; elsereturn 1;/先序、中序、后序遍历二叉树:非递归算法void print3() printf(n非递归算法遍历二叉树，菜单如下：n); printf(1.中根遍历n); printf(0.退出n); printf(请输入二级菜单选择:);typedef struct queuenode bitree e;struct queuenode *next;queuenode,*queueptr; /定义队列结点结构typedef struct queueptr front; queueptr rear;linkqueue; /栈的顺序存储表示typedef struct bitnode *base; /栈底指针 bitnode *top; /栈顶指针 int stacksize; /当前已分配的存储空间sqstack;/初始化一个带头结点的队列void initqueue(linkqueue &q)q.front=q.rear=(queueptr)malloc(sizeof(queuenode);q.front-next=null;/入队列void enqueue(linkqueue &q,bitree p) queueptr s;int first=1; s=(queueptr)malloc(sizeof(queuenode);s-e =p;s-next=null; q.rear-next=s; q.rear=s;/出队列void dequeue(linkqueue &q,bitree &p)char data; queueptr s;s=q.front-next; p=s-e ;data=p-data;q.front-next=s-next;if(q.rear=s)q.rear=q.front;free(s);printf(%ct,data);/判断队列是否为空status queueempty(linkqueue q)if(q.front-next=null)return 1;return 0;/按层次遍历树中结点void traverse(bitree t)linkqueue q;bitree p;initqueue(q); p=t;enqueue(q,p);while(queueempty(q)!=1) dequeue(q,p);if(p-lchild!=null)enqueue(q,p-lchild);if(p-rchild!=null)enqueue(q,p-rchild); printf(n); /建立一个空栈void initstack(sqstack &s) s.base=(bitree)malloc(list_int_size * sizeof(bitnode);if(!s.base)exit(overflow );/存储分配失败 s.top=s.base; s.stacksize=list_int_size; /压入栈void push(sqstack & s,bitree p) if(s.top-s.base=s.stacksize)/满栈，追加存储结构s.base=(bitree)realloc(s.base,(s.stacksize+listincrement)*sizeof(bitnode);if(!s.base) exit(overflow );/存储分配失败 s.top=s.base+s.stacksize; s.stacksize+=listincrement; *(+s.top)=*p; /退出栈bool pop(sqstack &s,bitree &p)if( s.top=s.base) printf(空栈n);return false; p=(bitree)malloc( sizeof(bitnode); *p=*s.top; -s.top;return true; /判断是否是空栈bool stackempty(sqstack &s) if( s.top=s.base) return true;elsereturn false ; status inordertraverandcountleaf(bitree &t,status(* vist)(telemtype e)int j=0,count=0;bitree p;p=(bitnode *)malloc( sizeof(bitnode);/关键一步p=t; sqstack s;initstack(s);while(p|!stackempty(s)if(p) push(s,p);/如果p为非空，将p压入栈if(!(p-lchild)&!(p-rchild) +count;/记录叶子节点数 p=p-lchild; /ifelse pop(s,p);/如果p为空，则p退栈vist(p-data); p=p-rchild; /else /whilereturn count;int main()int n, ncase;int count;bool f, f1, f2, f3; bitree t; telemtype e;print();while(scanf(%d, &n)!=eof) f = true;switch(n)case 1: printf(输入空格或回车表示此结点为空结束n请输入头结点：);if(createbitree(t) printf(二叉树建立成功!n);else printf(二叉树建立失败!n);break;case 2:print2();while(scanf(%d, &ncase)!= eof) f1 = true;switch(ncase) case 1: printf(先序遍历顺序为：);if(preordertraverse(t, printelement)printf(先序遍历成功!n);else printf(先序遍历失败!n);break;case 2:printf(中序遍历顺序为：);if(midordertraverse(t, printelement) printf(中序遍历成功!n);elseprintf(中序遍历失败!n);break;case 3: printf(后序遍历顺序为：);if(lastordertraverse(t, printelement) printf(后序遍历成功!n);elseprintf(后序遍历失败!n);break;case 0: f1 = false;break;default :printf(输入错误，请重新输入!n);if(!f1)break;print2(); break;case 3:print3();while(scanf(%d, &ncase)!= eof) f2 = true;switch(ncase) case 1:inordertraverandcountleaf(t,printelement);break;case 0: f2 = false;break;default :printf(输入错误，请重新输入!n); if(!f2)break;print3();break;case 4:dep = 0;bitreedepth(t); printf(二叉树的高度为：%dn, dep-1);break;case 5:count = leafnumtree(t);printf(二叉树的叶子个数为：%dn, count);break;case 6: printf(按层次遍历的顺序为:n);traverse(t);printf(n);break;case 0: f = false;break;default: printf(输入错误，请重新输入!n);break; if(!f)printf(退出程序.n);break;print(); return 0;6 测试图1如图1所示为一元多项式的相加的测试图，多项式ha：2x2+34x3+56x4与多项式hb：12x1+23x2+334+2x5相加，结果为12x1+25x2+34x2+343+89x4+2x5。图2图3图4如图所示，图2、3、4则为图的综合的试验测试。图5图6如上所示，图5、6为树的综合的试验测试截图。7 总结以上是综合设计基础部分的所有内容，做基础部分只是为了给后面的综合设计打下基础，巩固和扎实基础部分的知识，重点还是综合设计的部分。在基础部分，做了三个基本的实验程序，包括一元多项式的相加、图的基本操作和树的基本操作。应用到了指针、链表等基础知识，进一步对基础知识进行了了解和掌握。其中在树的基本操作之中。因为我选的综合应用设计题也是赫夫曼编码，所以在基础部分就没有实现赫夫曼编码的操作，只是简单把树的基本操作实现了。在一元多项式的相加中，实现了两个多项式的相加，项数相同的系数合并，然后打印出相加的结果；在图的综合之中，以邻接矩阵的方式建立图，并实现了图的广度优先和深度优先的遍历，在树的综合之中建立二叉链表，递归实现先序、中序、后序遍历二叉树等的功能。虽然基础的实验也许做的不够完美，但是经过这几个基础的实验，最后的收获也不少，不仅温习了旧的知识，也学到了新的知识，给综合课程设计打下了坚实的基础。二、综合部分课程设计1 问题描述在当今的信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。赫夫曼编码正是一种应用广泛非常有效的数据压缩技术。赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个对应的字符的编码，这就是哈夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。我们需要解决的就是对电文的编码和译码问题。2 功能需求分析建立赫夫曼树：根据输入的字符串建立赫夫曼树。从键盘输入字符串，根据输入的字符串中每个字符出现的频率计算比重，实现赫夫曼树的建立。赫夫曼编码：根据所建立的赫夫曼树进行赫夫曼编码。指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，对每个字符进行编码，并在屏幕上打印出每个字母所对应的编码结果。赫夫曼译码：根据给出的每个数值的编码进行相应的译码。从键盘输入密文（只能由“1”和“0”组成），根据输入的密文，对应的去扫描编码表，找出与之对应的字母，进行译码，并将译码的结果在屏幕上面打印出来。3 总体设计1. 总体结构赫夫曼编码译码系统译码编码建立赫夫曼树将译码结果打印出来从键盘上输入密文进行译码根据建立的赫夫曼树进行编码将编码结果打印出来从键盘上输入字符串根据输入的字符串算出每个字母出现的频率算出比重2. 设计流程程序总体执行的流程图如下：开始输入需要编码的字符串对输入的字符串根据出现的频率算出其比重根据每个字符所占的比重建立huffmantree编码输入密文进行译码输入的字符是否只含0和1？否是打印译码明文是否继续译码？是否结束程序4 详细设计1. 赫夫曼编码的结构体typedef struct haha int weight;/*权值*/ int parent,lchild,rchild,flag;/*父结点、左孩子结点、右孩子结点，flag表示状态，用来记录是否被选中，初始为0*/ char data;/*存放字符*/ haha,*huffmantree;/*树中结点类型*/ typedef struct hehechar m;int n;struct hehe *next;hehe,*zhouwu;typedef char * *huffmancode;/*动态分配数组存储赫夫曼编码表*/2. 函数功能的描述以及结构begin()：函数原型为void begin(zhouwu &l)；函数实现的功能是对输入的字符串中的字母进行比重统计，算出其的比重权值。开始begin()函数结构：为l动态分配内存输入字符串计算比重结束返回lselect()：函数原型为void select(huffmantree &ht,int k,int &x,int &y)；/*选择权值最小的两个根节点的算法 */函数实现的功能是在所有的值中选择两个权值最小的数的结点。huffmancoding()：函数原型为void huffmancoding(huffmantree &ht,zhouwu &l)；/*编码*/ 函数实现的功能是对字符进行编码。huffmancoding()函数结构：结束循环结构打印出编码，释放指针是是否in是否成立？生成编码1生成编码0否否是选择的两个节点的权值是否为最小？是否为左孩子？赫夫曼树建立完毕，开始编码是select（）函数全部设置为0初始化数组的每个分量为h