本科生毕业设计论文内芯格式.docVIP

长 春 大 学 课 程 设 计 说 明 书 题目名称 八皇后问题 哈夫曼编码 院 （系） 计算机科学技术040540230 学生姓名 赵 刚 指导教师 张 力 起止日期 2007.12.24~2008.1.4 目录 一．设计题目 (2) 1.1八皇后问题 (2) 1.2哈夫曼编码 (2) 二．设计目的 (3) 三．算法思想分析 (3) 3.1八皇后问题 (3) 3.2哈夫曼编码 (4) 3.2.1哈夫曼树 (4) 3.2.2哈夫曼编码的基本原理和方法 (4) 3.2.3代码的译码 (5) 3.2.4统计频度 (5) 3.2.5打印哈夫曼树 (5) 四．算法思想描述与实现 (5) 4.1八皇后问题 (5) 4.1.1描述 (5) 4.1.2实现 (6) 4.2哈夫曼编码 (7) 4.2.1定义模块功能函数 (7) 4.2.2运行程序时产生的文本 (8) 4.2.3函数一览表 (8) 五．程序流程图 (9) 5.1八皇后执行图示 (9) 5.2哈夫曼编码 (10) 5.2.1 执行图示 (10) 5.2.2 流程图 六．总结 (15) 6.1八皇后问题 (15) 6.1.1 关于递归 (15) 6.1.2 关于非递归 (15) 6.2 哈夫曼编码 (16) 七．参考文献 (16) 八．附录 (17) 8.1八皇后源程序 (17) 8.2哈夫曼源程序 (19-38) （一）设计题目 1.1.【八皇后问题】 【问题描述】求出在一个n×n的棋盘上，放置n个不能互相捕捉的国际象棋“皇后”的所有布局。这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线个方向相互捕捉。如图所示，一个皇后放在棋盘的第4行第3列位置上，则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉，也就是下一个皇后不能放的位置。 1 2 3 45 6 7 8 × × × × × × × × × × Q × × × × × × × × × × × × × × × 从图中可以得到以下启示：一个合适的解应是在每列、每行上只有一个皇后，且一条斜线上也只有一个皇后。初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码；设字符集及频度如下表： A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 【进一步完成内容】 1)对任意输入的一段字符，统计字符出现的频度，完成哈夫曼编码； 2)译码功能；显示哈夫曼树；面设计的优化。20％至90％，其压缩效率取决于被压缩文件的特征。试设计一个哈夫曼编码系统，满足编码、译码和哈夫曼树的打印。通过本课程设计，应使学生掌握哈夫曼编码的特点、存储方法和基本原理，培养学生正确编程及调试的能力，掌握文件的基本操作。运用数据结构解决简单的实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。 （三）算法思想分析 3.1【八皇后问题】 求解过程从空配置开始。在第1列至第m列为合理配置的基础上，再配置第m+1列，直至第n列配置也是合理时，就找到了一个解。接着改变第n列配置，希望获得下一个解。另外，在任一列上，可能有n种配置。开始时配置在第1行，以后改变时，顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时，就要回溯，去改变前一列的配置。n皇后问题，无非就是就解决树的结构： 初始状态构成（主）树的根节点； 除根结点以外，每个结点都具有一个、且只有一个父结点。对应n皇后问题来说，置放i行皇后的子结点，只有在置放列前i-1行皇后父结点基础上产生； 每个非根结点都有一条路径通往根结点，其路径长度（代价）定义为这条路径的边数。对应于n皇后来说，当前行序号即为路径代价。当路径代价为n+1时，说明n个皇后已置放完毕，一种成功的摆法产生。 3.2【哈夫曼编码】 3.2.1.【哈夫曼树】 原理： 一般而言，给定n个实数w1，w2，．．．．．．，wn（n≥２），求一个具有n个结点的二叉数，使其带权路径长度最小。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点