数据结构课程设计报告 题目一迷宫问题 题目二哈夫曼编码器 班级.doc

数据结构课程设计报告题目一：迷宫问题题目二：哈夫曼编码器班级：06计升班姓名： 学号：指导教师： 完成日期：2007年7月6日题目一：迷宫问题一、需求分析：1、以二维数组Mazem+2n+2表示迷宫，其中：Maze0j和Mazem+1j(0jn+1)及Mazei0和Mazein+1(0im+1)为添加的一圈障碍。数组中以元素值为0表示通路，1表示障碍。限定迷宫的大小，m,n10。2、设计一个程序，对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。迷宫的入口位置和出口位置可由用户随时设定。3、程序输入：在主程序中定义存储迷宫数据的二维数组，入口点、出口点和迷宫中任一点的方向均可由用户自行设定。4、程序输出：程序将输出迷宫中一条成功路径上的每一个点的坐标。5、本程序只求出一条成功的通路。然而，只需要对迷宫求解的函数作小量修改，便可求得全部路径。6、测试数据：当入口位置为（1，1），出口位置为（5，8），则输出的一条通路为：(1,1) ,(2,1),(2,2),(2,3)(2,4),(2,5),(3,5),(4,5),(5,5)(6,5),(6,6),(6,7),(6,8),(6,9);当输入的入口位置和出口位置之间不存在通路时，将会输出不存在通路的提示。二、设计内容：1、程序中所用到的数据及其数据类型的定义：设定栈的抽象数据类型定义为：ADT Stack 数据对象：D=ai|aiCharSet, i=1,2,n, n0 数据关系：R1=|ai-1,aiD，i=2,，n基本操作：InitStack(&S) 操作结果：构造一个空栈S。 DestroyStack(&S) 初始条件：栈S已存在。 操作结果：销毁栈S。 ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。 StackLength(S) 初始条件：栈S已存在。 操作结果：返回栈S的长度。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若S为空栈，则返回TRUE,否则返回FALSE。 GetTop(S，&e) 初始条件：栈S已存在。 操作结果：若栈S不空，则以 e返回栈顶元素。 Push(&S,e) 初始条件：栈S已存在。 操作结果：在栈S的栈顶插入新的栈顶元素e。 Pop(&S,&e) 初始条件：栈S已存在。 操作结果：删除S的栈顶元素，并以e返回其值。 StackTraverse(S,visit() 初始条件：栈S已存在。 操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。ADT Stack其中部分操作的算法： /* 在栈中压入一元素x */ void push_seq( PSeqStack pastack, DataType x ) if( pastack-t = MAXNUM - 1 ) printf( Stack Overflow! n ); else pastack-t+; pastack-spastack-t = x; /* 删除栈顶元素 */ void pop_seq( PSeqStack pastack ) if (pastack-t = -1 ) printf( Underflow!n ); else pastack-t-; 求迷宫路径的伪码算法：void mazePath(int mazeN, int direction2, int x1, int y1, int x2, int y2) int i, j, k, g, h; PSeqStack st; DataType element; st = createEmptyStack_seq( ); mazex1y1 = 2; /* 从入口开始进入,作标记 */ pushtostack(st, x1, y1, -1); /* 入口点进栈 */ while ( !isEmptyStack_seq(st) /* 走不通时,一步步回退 */ element = top_seq(st); pop_seq(st); i = element.x; j = element.y; for (k = element.d + 1; k = 3; k+) /* 依次试探每个方向 */ g = i + directionk0;h = j + directionk1; if (g = x2 & h = y2 & mazegh = 0) /* 走到出口点 */ printpath(st); /* 打印路径 */ return; if (mazegh = 0) /* 走到没走过的点 */ mazegh = 2; /* 作标记 */ pushtostack(st, i, j, k); /* 进栈 */ i = g; j = h; k = -1; /* 下一点转换成当前点 */ printf(The path has not been found.n);/* 栈退完未找到路径 */ 2、函数之间的调用关系： mainMazePath Push_seqPop_seqPrintPathisEmptyStack_seqtop_seq3、主程序及其主要模块的流程图：主程序： void main() int direction2=0,1,1,0,0,-1,-1,0; int mazeN = 1,1,1,1,1,1,1,1,1,1,1, 1,0,1,0,0,1,1,1,0,0,1, 1,0,0,0,0,0,1,0,0,1,1, 1,0,1,1,1,0,0,0,1,1,1, 1,0,0,0,1,0,1,1,0,1,1, 1,1,0,0,1,0,1,1,0,0,1, 1,1,1,0,0,0,0,0,0,0,1, 1,1,1,1,1,1,1,1,1,1,1 ; mazePath(maze,direction,1,1,5,8); getchar(); return ; 各模块之间的调用关系： 主程序模块迷宫模块栈模块三、调试分析：1、 本次作业比较简单，只有一个核心算法，即求迷宫的路径，所以总的调试比较顺利。2、 本程序只包括三个主要模块，即主程序模块、迷宫模块和栈模块，三模块之间的调用关系比较简单合理。3、 本程序还存在一个缺陷，就是当指定了入口和出口以后，其只能输出一条符合此条件的成功路径，然而，只需对迷宫求解的函数做小量修改，便可求得全部路径。4、 程序中的主要算法MazePath和PrintPath的时间复杂度均为：O(mn),其空间复杂度亦为：O(mn).5、 经验体会：通过本次作业，我基本掌握了栈的一些基本应用及其算法实现过程，以及迷宫求解问题的具体实现过程。四、用户手册：1、本程序的运行环境为C+操作系统，执行文件为：TestMaze.exe。2、在主程序中输入一组迷宫数据，由用户自行设定好入口位置和出口位置，然后运行程序，如果入口到出口存在路径，结果显示界面将会打印路径上的每一个点的坐标，例如：本题中输入的迷宫数据，设定其入口位置为（1，1），出口位置为（5，8），运行程序后，将显示一下结果界面：然后，点回车即出现提示：Press any key to continue，再点任意键即可回到编译界面；如果入口到出口不存在路径，运行程序以后将会出现以下结果界面：然后，点回车即出现提示：Press any key to continue,再点任意键即可回到编译界面。五、测试结果：对于主程序中给定的迷宫，任意给定以下四组数据，已将得到以下测试结果：1、入口位置：（1，1） 出口位置：（6，9） 得出的一条通路为：（1，1），（2，1），（2，2），（2，3），（2，4），（2，5），（3，5），（4，5），（5，5），（6，5），（6，6），（6，7）2、入口位置：（1，1） 出口位置：（3，8） 从该入口到出口没有通路。 3、入口位置：（2，3） 出口位置：（5，9） 得出的一条通路为：（2，3），（2，4），（2，5），（3，5），（4，5），（5，5），（6，5），（6，6），（6，7），（6，8）4、入口位置：（2，3） 出口位置：（4，9） 从该入口到出口没有通路。 六、附录：源程序文件名清单：base.H /公用的常量和类型stkpas.H /栈类型maze.H /迷宫类型testmaze.C /主程序题目二：哈夫曼编码器 一、需求分析1、利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是要求要在发送端通过一个编码系统对传输数据预先编码。2、程序输入：输入的结点数目及权值均为整型。利用建好的哈夫曼树对正文进行编码，然后存入文件中。3、程序输出：将显示哈夫曼哈夫曼树的构造过程。将已在内存中的哈夫曼树以直观的方式显示在终端上，同时将此字符形式的哈夫曼中写入文件中4、测试数据：输入结点数目n=8，其权值分别为5，29，7，8，14，23，3，11，则m=15。二、设计内容1、数据类型的定义：typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树 typedef char *HuffmanCode; /动态分配数组存储哈夫曼编码表 基本操作及其伪码算法： void Select(HuffmanTree HT,int n) / 在HT1.i-1中选择weight最小的两个结点， / 其序号分别为s1和s2int i,j; for(i = 1;i = n;i+) if(!HTi.parent)s1 = i;break; for(j = i+1;j = n;j+) if(!HTj.parent)s2 = j;break; for(i = 1;i HTi.weight)&(!HTi.parent)&(s2!=i)s1=i; for(j = 1;j HTj.weight)&(!HTj.parent)&(s1!=j)s2=j; void HuffmanCoding(HuffmanTree HT, HuffmanCode HC, int *w, int n) / 算法6.13 / w存放n个字符的权值(均0)，构造哈夫曼树HT， / 并求出n个字符的哈夫曼编码HC int i, j; char *cd; int p; int cdlen; if (n=1) return; m = 2 * n - 1; HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 0号单元未用 for (i=1; i=n; i+) /初始化 HTi.weight=wi-1; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; for (i=n+1; i=m; i+) /初始化 HTi.weight=0; HTi.parent=0; HTi.lchild=0; HTi.rchild=0; puts(n哈夫曼树的构造过程如下所示：); printf(HT初态:n 结点 weight parent lchild rchild); for (i=1; i=m; i+) printf(n%4d%8d%8d%8d%8d,i,HTi.weight, HTi.parent,HTi.lchild, HTi.rchild); printf( 按任意键，继续 .); getchar(); for (i=n+1; i=m; i+) / 建哈夫曼树 / 在HT1.i-1中选择parent为0且weight最小的两个结点， / 其序号分别为s1和s2。 Select(HT, i-1); HTs1.parent = i; HTs2.parent = i; HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; printf(nselect: s1=%d s2=%dn, s1, s2); printf( 结点 weight parent lchild rchild); for (j=1; j=i; j+) printf(n%4d%8d%8d%8d%8d,j,HTj.weight, HTj.parent,HTj.lchild, HTj.rchild); printf( 按任意键，继续 .); getchar(); /-无栈非递归遍历哈夫曼树，求哈夫曼编码 cd = (char *)malloc(n*sizeof(char); / 分配求编码的工作空间 p = m; cdlen = 0; for (i=1; i=m; +i) / 遍历哈夫曼树时用作结点状态标志 HTi.weight = 0; while (p) if (HTp.weight=0) / 向左 HTp.weight = 1; if (HTp.lchild != 0) p = HTp.lchild; cdcdlen+ =0; else if (HTp.rchild = 0) / 登记叶子结点的字符的编码 HCp = (char *)malloc(cdlen+1) * sizeof(char); cdcdlen =0; strcpy(HCp, cd); / 复制编码(串) else if (HTp.weight=1) / 向右 HTp.weight = 2; if (HTp.rchild != 0) p = HTp.rchild; cdcdlen+ =1; else / HTp.weight=2，退回退到父结点，编码长度减1 HTp.weight = 0; p = HTp.parent; -cdlen; / HuffmanCoding2、函数之间的调用关系图： 3、主程序及其主要模块的流程图： 主程序： void main() HuffmanTree HT;HuffmanCode *HC;int *w,n,i; puts(输入结点数:); scanf(%d,&n); HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode); w = (int *)malloc(n*sizeof(int); printf(输入%d个结点的权值n,n); for(i = 0;i n;i+) scanf(%d,&wi); HuffmanCoding(HT,HC,w,n); puts(n各结点的哈夫曼编码:); for(i = 1;i = n;i+) printf(%2d(%4d):%sn,i,wi-1,HCi); getchar(); 模块流程图： 主程序模块建哈夫曼树模块求哈法曼编码模块三、调试分析1、刚开始曾忽略了一些变量参数的标识“&”，使程序起初出现了一些较低级的错误，导致调试程序时费时不少。今后应重视确定参数的变量和赋值的区分和标识。2、在程序中，一些局部变量的定义还不够全面，变量的引用过程还不够熟练，曾出现过多处引用上的错误，至今还仍然存在一处引用警告，但此处警告不影响程