数据结构课程设计

1、西南大学计算机与信息科学学院 课程设计报告课 程： 数据结构课程设计 题 目： 赫夫曼编码的应用 级、专业： 2014 级 计算机 专业 2 班学生姓名： 杨爱婵 提交日期： 2016 年 06 月 23 日内容提要：这次的数据结构课程设计分为两个部分：基础部分和综合部分。基础的部分只是为了巩固基础知识，综合设计是主要部分。基础部分：基础部分是为了巩固加强基础知识，为综合的实验报告奠定基础。其中的内容包括一元多项式的相加，图的基本操作，树的基本操作。从基础部分着手，简单的两个多项式的相加的实现，图的基本操作的实现，树的基本操作的实现。综合部分：综合部分针对综合的设计能力的锻炼，在基础的部分上增

2、强。综合部分就是做赫夫曼编码译码系统。输入一些字符串或者是英文句子，根据字符出现的比重进行权值的计算，从而建立赫夫曼树，赫夫曼树是赫夫曼编码的基础，在赫夫曼树建立之上对其进行编码和译码。首先实现的是编码，其次是译码。根据每个字符的编码，译码的时候，输入密文，会自动的去编码表中寻找匹配的字符，从而进行译码，并打印出译码的明文。关键词： 赫夫曼树 编码 电文译码 链表 图 数据结构 指针参考书目：数据结构（C语言版） 清华大学出版社 严蔚敏 吴伟民 编著数据结构课程设计 第2版 机械工业出版社 苏仕华 魏韦巍 王敬生 刘燕君 编著成绩评定：指导教师（签字）： 年 月 日目录一、 基础设计部分011

3、. 问题描述012. 功能需求分析013. 总体设计014. 详细设计025. 源代码036. 测试177. 总结18二、 综合设计部分201. 问题描述202. 功能需求分析203. 总体设计214. 详细设计225. 源代码256. 测试307. 总结31三、 参考文献3131一、基础部分课程设计1 问题描述基础部分有三个基础的简单的程序。在这三个简单的课程设计之中要实现一元多项式的相加、图的基本操作以及树的基本操作。针对一元多项式相加的问题，如何实现在屏幕上把输入的两个要相加的一元多项式分别的显示出来以及相加以后的结果以多项式的形式显示出来？针对图的基本操作，如何实现用领接矩阵建立一个图

4、？如何在建立好一个图的基础上实现广度优先和深度优先遍历等等问题？针对树的综合，如何运用二叉链表建立树？以及二叉链表的遍历（包括先序、中序、后序、递归、非递归等）的实现等问题的解决？2 功能需求分析 一元多项式的相加：一元多项式的相加运算主要完成的是分别输入两个多项式，实现两个多项式指数对应的项的系数相加，并把相加的结果在屏幕上打印出来。在开始的时候输入每个多项式的项数之后再以成对的形式输入系数和指数，然后对应指数相等的项系数相加合并。 图的综合：图的综合实现了以邻接矩阵的方式构造一个图，而且在此基础上面广度优先和深度优先实现图的遍历。输入一个图的节点个数，再输入每个节点的符号，依次输入两个节点

5、之间的路径长度构造邻接矩阵，并以广度优先和深度优先实现图的遍历过程。 树的基本操作：树的基本操作实现的功能包括输入字符建立二叉链表构造树，先序、中序以及后序遍历用递归算法实现，求二叉树的叶子个数以及借助队列实现二叉树的层次遍历。3 总体设计基础部分的总体结构：基础部分一元多项式的相加树的综合图的综合二叉树的叶子结数以及层次遍历遍历二叉树建立二叉链表实现两个多项式的相加邻接矩阵构造图在屏幕上打印出计算结果分别输入两个多项式图的遍历：广度优先和深度优先4 详细设计1. 一元多项式的相加结构体：typedef int ElemType; typedef struct PolynNode /*单项链表

6、的声明*/ int coef; / 系数 int expn; / 指数 struct PolynNode *next; PolynNode,*PolynList; /*正位序(插在表尾)输入n个元素的值，建立带表头结构的单链线性表*/ /*指数系数一对一对输入*/2. 图的基本操作的结构体： struct stu char name3;struct stt struct stu ding10;int jz1010;int dd;struct shustruct stu * p;struct shu * l;struct shu * r;3. 树的基本操作的结构体： int dep, count

7、= 0;typedef int Status;typedef char TElemType;typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; /*右孩子，左孩子*/BiTNode, *BiTree;5 源代码 一元多项式的相加的源程序代码：#include #include #include typedef int ElemType; typedef struct PolynNode /*单项链表的声明*/ int coef; / 系数 int expn; / 指数 struct PolynNode

8、*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

9、; / 初始条件：单链表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

10、(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指针连上指数小的结

11、点， 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;

12、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);

13、 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

14、 * 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

15、(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)

16、 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) i

17、nt 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(

18、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

19、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 TElemTyp

20、e 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-

21、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)

22、; 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(

23、PreOrderTraverse(T-lchild, Visit) if(PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return 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;

24、else return 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; else return OK;/求树的叶子的个数,和打印出叶子Status LeafNumTree(BiTree T) int lnum,rnum; if(T!=NULL) if(T-lc

25、hild=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; else return 1; /先序、中序、后序遍历二叉树:非递归算法void

26、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; /栈顶指针 in

27、t 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

28、 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; BiT

29、ree 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

30、=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

31、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; else return false ; Status InOrderTraverAndCountLeaf(BiTree &T,Status(* Vist)(TElemType e) int

32、 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; /if else Pop(s,p);/如果p为空，则p退栈 Vist(p-data); p=p-rchild; /else /while return count;int main() in

33、t 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(n

34、case) case 1: printf(先序遍历顺序为：); if(PreOrderTraverse(T, PrintElement) printf(先序遍历成功!n); else printf(先序遍历失败!n); break; case 2: printf(中序遍历顺序为：); if(MidOrderTraverse(T, PrintElement) printf(中序遍历成功!n); else printf(中序遍历失败!n); break; case 3: printf(后序遍历顺序为：); if(LastOrderTraverse(T, PrintElement) printf(后

35、序遍历成功!n); else printf(后序遍历失败!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 :

36、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(输入错误，请重

37、新输入!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 总结以上是综合设计基础部分的所有内容，做基础部分只是为了给后面的综合设计打下基础，巩固和扎实基础部分的知识，重点还是综合设计的部分。在基础部分，做了三个基本的实验程序，包括一元多项式的相加、图的基本操作和树的基本操作。应用到了指针、链表等基础知识，进一步对基础知识进行了了解和掌握。其中在树的基本操作之中。因为我选的综合应用设计题也是