数据结构课程设计报告——汉诺塔、电文编码及译码、拓扑排序、猴子选大王.doc

上海应用技术学院课程设计报告
课程名称 《数据结构与算法课程设计》
设计题目
院系 工程创新学院 专业 软件工程 班级131042Y1
姓名 金梦 学号 1310400511 指导教师 柏海芸 日期 2015-1-20

一. 目的与要求
1. 巩固和加深对常见数据结构的理解和掌握
2. 掌握基于数据结构进行算法设计的基本方法
3. 掌握用高级语言实现算法的基本技能
4. 掌握书写程序设计说明文档的能力
5. 提高运用数据结构知识及高级语言解决非数值实际问题的能力

二. 课程设计内容说明
1. 项目一：电文的编码和译码
（1）对设计任务内容的概述
任务：从键盘接收一串电文字符，输出对应的huffman编码。同时，能翻译由huffman编码生成的代码串，输出对应的电文字符串。
要求：a)构造一棵huffman树；
b)实现huffman编码，并用huffman编码生成的代码串进行译码；
c) 程序中字符和权值是可变的，实现程序的灵活性。

（2）需求分析或功能描述
在电报通信中，电文是以二进制代码传送的。在发送时，需要将电文中的字符转换成二进制代码串，即编码；在接收时，要将收到的二进制代码串转化为对应的字符序列，即译码。我们知道，字符集中的字符被使用的频率是非均匀的。所以该程序能够自动从输入的字符串中计算各个字符的权值，以实现程序的灵活性。输入一串小写英文字符，即能够得到相应的huffman编码。

（3）概要设计或程序流程图

图1-1 建立huffman树

图1-2 huffman编码

图1-3 huffman译码

图1-4 主流程图

（4）详细设计或源代码说明
第一步：定义常量与结构体
#define MAXNUM 50
typedef char DataType;
typedef struct/* 哈夫曼树结点的结构 */
{
DataType data; /* 数据用字符表示 */
int weight; /* 权值 */
int parent; /* 双亲 */
int left; /* 左孩子 */
int right; /* 右孩子 */
}HuffNode;
typedef struct/* 哈夫曼编码的存储结构 */
{
DataType cd[MAXNUM];/* 存放编码位串 */
int start; /* 编码的起始位置 */
}HuffCode;

第二步：构造函数
建立huffman树：int HuffmanCreate(HuffNode *ht)
Huffman编码：void Encoding(HuffNode ht[],HuffCode hcd[],int n)
Huffman译码：void Decoding(HuffNode ht[],HuffCode hcd[],int n)

第三步：在主函数中调用其他函数：int main(int argc,char* argv[])

（5）程序模块及其接口描述
模块：
Huffman树的建立：int HuffmanCreate(HuffNode *ht)
Huffman编码：void Encoding(HuffNode ht[], HuffCode hcd[], int n)
Huffman译码：void Decoding(HuffNode ht[], HuffCode hcd[], int n)
主程序：int main1()

接口：n = HuffmanCreate(ht); 调用树的建立模块函数
Encoding(ht, hcd, n); 调用编码模块函数
Decoding(ht, hcd, n); 调用译码模块函数
int huffman() 用于和总程序的信息交互

（6）程序的输入与输出描述
输入：从键盘输入元素以及节点值建立哈弗曼树，输入电文
输出：电文的编码以及译码

（7）调试分析或程序测试

（8）尚未解决的问题或改进方向
输入电文的判错。

（9）对软件的使用说明
根据提示输入相关的数据，构造huffman树。再根据提示选择电文的编码，即可得出每个元素所对应的密码。再根据提示输入电文（由0或1组成），即可得到相应的译码，成功破译电文。

2. 项目二：汉诺塔
（1）对设计任务内容的概述
任务：设有三个分别命名为X、Y、Z的塔座，在塔座X上插有n个直径各不相同，从小到大依次编号1、2、…、n的圆盘，现要求将X塔座上的n个圆盘移到塔座Z上，并插在X、Y和Z中任一塔座；任何时候都不允许将较大的圆盘放在较小的圆盘之上。
要求：a) 用户输入初始圆盘数；
b) 输出所有的移动过程，有文字说明

（2）需求分析或功能描述
汉诺塔是源自印度神话里的玩具。上帝创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上安大小顺序摞着64片黄金圆盘。上帝命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。有预言说这件事完成时宇宙会在一瞬间闪电式毁灭。而实际上，利用递归的思维，我们可以得出，移动完n个圆盘，所需要做的最少步骤是2^n-1，按照他们说的，离宇宙毁灭还有很长很长的时间。直至今日，汉诺塔仍然是一款比较受欢迎的游戏，也有较高的数学研究价值。本

（3）概要设计或程序流程图
如果盘子为1，则将这个盘子从塔座X移动到塔座Z；
如果不为1，则采用递归思想。
将塔座X的前n-1个盘子借助Z盘（即目的盘）移到塔座Y，移后，此时Z为空座，那我们就可以将塔座X的第n个盘子移到塔座Z了。接下来就将塔座Y的n-1个盘子借助X移到塔座Z，从而完成盘子的移动。
开始
输入盘数（初始化三个）
判断盘数是否为1
盘子数大于1，继续进行递归过程
输出移动步骤
执行移位操作
执行移位操作
输出移动步骤

结束
是

图 2-1 汉诺塔的递归算法

（4）详细设计或源代码说明
void move(int n, char x, char y, char z) //利用递归的算法控制盘子的移动
printf("\t%d:%c->%c\n", n, x, z); //当n只有1个的时候直接从x移动到z
move(n - 1, x, z, y); //第n-1个要从x通过z移动到y
printf("\t%d:%c->%c\n", n, x, z);
move(n - 1, y, x, z); //n-1个移动过来之后y变开始盘，y通过x移动到z

（5）程序模块及其接口描述
模块：
移动模块：void move(int n, char x, char y, char z)，用于汉诺塔盘子的递归移动
主程序模块：int main2()，用于输入相关数据及调用移动模块函数。
接口：move(n, 'x', 'y', 'z');用于调用移动模块函数 int hanoic()用于和总程序的信息交互

（6）程序的输入与输出描述
输入：从键盘输入所需移动的汉诺塔的盘子个数n
输出：从控制台显示各个编号的盘子移动的步骤

（7）调试分析或程序测试

（8）尚未解决的问题或改进方向
对输入的数字的大小的限定以及判错。

（9）对软件的使用说明
根据提示进行菜单选择，进入汉诺塔程序后，根据提示输入相应的盘子个数即可得到对应的编号的盘子的移动步骤。
3. 项目三：猴子选大王
（1）对设计任务内容的概述
任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1-m的顺序围坐一圈，从第1开始数，每数到第N个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王。

（2）需求分析或功能描述
输入数据m,n，计算出最终猴子大王的序号，模拟出整个过程。 找到合适的数据结构处理这个问题， 找到正确的方法解决这个问题。

（3）概要设计或程序流程图

图 3-1 猴子选大王流程图

（4）详细设计或源代码说明
typedef struct _RingNode
{
int pos;
struct _RingNode *next;
}RingNode, *RingNodePtr; //建立线性链表以存储相应的数据
void CreateRing(RingNodePtr pHead, int count)
void PrintRing(RingNodePtr pHead) //建立相应的循环链表
RingNodePtr KickFromRing(RingNodePtr pHead, int n) //淘汰猴子

（5）程序模块及其接口描述
模块：
循环链表的建立及输入模块：void CreateRing(RingNodePtr pHead, int count)
void PrintRing(RingNodePtr pHead)
淘汰猴子模块：RingNodePtr KickFromRing(RingNodePtr pHead, int n)
主程序模块：void main3()

接口：CreateRing(pHead, m);
PrintRing(pHead);
pRing = KickFromRing(pHead, n);

（6）程序的输入与输出描述
输入：从键盘输入猴子个数与报数的最大数
输出：控制台显示被删除的猴子编码以及猴王编码

（7）调试分析或程序测试

（8）尚未解决的问题或改进方向
对输入非数字字符的判错

（9）对软件的使用说明
根据提示进入猴子选大王程序，输入相应的猴子数m以及报数的最大数n，即可得到相应的淘汰次序以及选出的猴王的编号。

4. 项目四：拓扑排序
（1）对设计任务内容的概述
任务：编写函数实现图的拓扑排序。

（2）需求分析或功能描述
拓扑排序的基本思想为：
1) 从有向图中选一个无前驱的顶点输出；
2) 将此顶点和以它为起点的弧删除；
3) 重复1),2)直到不存在无前驱的顶点；
4) 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。

（3）概要设计或程序流程图
对于给定的有向图，采用邻接表作为存储结构，为每个顶点设计一个链表，每个链表有一个表头节点，这些表头节点构成一个数组，表头节点中增加一个存放顶点入度的域count。即将邻接表定义中的VNode类型修改如下：
typedef struct //表头节点类型
{ Vertex data; //顶点信息
intcount; //存放顶点入度
ArcNode *firstarc; //指向第一条边
}VNode;
在执行拓扑排序的过程中，当某个顶点的入度为0（没有前驱顶点）时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测入度为0的顶点，设立一个栈ST，以存放入度为0的顶点。

（4）详细设计或源代码说明
void MatTolist(MGraph g,ALGraph * &G)，按照输入的内容创建邻接矩阵拓扑排序：
void TopSort(ALGraph * G)，进行拓扑排序并显示。

（5）程序模块及其接口描述
模块：
创建邻接矩阵模块：void MatTolist(MGraph g, ALGraph * &G)
拓扑排序模块：void TopSort(ALGraph * G)
主程序模块：int main4()
接口：MatTolist(g, G);
TopSort(G);

（6）程序的输入与输出描述
输入：用键盘输入邻接矩阵
输出：若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为一个拓扑序列。
（7）调试分析或程序测试
对如下有向无环图进行排序：

结果：

若输入以下有向回路图的邻接矩阵：

（8）尚未解决的问题或改进方向
能够直接输入顶点和路径来得出相应的邻接矩阵。

（9）对软件的使用说明
事先得出所求的有向图的邻接矩阵，并输入，即可得出相应的拓扑排序。

一. 结论及体会
通过“电文的编码与译码”这个题目，我认识到了哈弗曼树的构建，以及编码和译码的实现；对于汉诺塔的编程，我了解到了递归算法的思想；在猴子选大王中，我则更多了了解了循环链表的应用；在进行拓扑排序的课程设计中，我遇到了程序正确，却对某些无向图无法进行拓扑排序的问题。多次对程序进行修改后，才可以进行拓扑排序。问题出在调用函数的错误理解，模块之间的联系模糊不清,在同学的帮助和自己的努力思考下， 我最终把这些问题一一解决，并把教训牢记在心，努力使自己得到更大的收获和提高。因为在理论学习中没有好好的掌握，现在要独立完成一个较复杂的程序编写，确实有困难。今后我必需扎实基础理论、认真思考，而且要践行我的承诺，一步一个脚印的走下去，才可以达到我们预期的彼岸！

附录1：参考文献
[1] 《数据结构教程（第4版）》，李春葆，清华大学出版社，2013
[2]《数据结构》，杨剑，清华大学出版社，2011
[3]《数据结构(C语言版)》，严蔚敏 吴伟民，清华大学出版社，1997
[4]《Data Structures Using C数据结构（C语言版）》，R Krishnamoorthy、G Indirani Kumaravel，清华大学出版社，2009-9
[5]《C++数据结构与程序设计 （美）Robert L.Kruse/Alexander J.Ryba著/钱丽萍译》，
清华大学出版社，2004
[6]《计算机算法设计与分析（第2版）》，王晓东， 电子工业出版社， 2004
附录2：部分源代码清单

第 16 页