数据结构与算法说明书.pdfVIP

数据结构与算法课程设计 题 目： 求素数问题 猴子吃桃问题 跳马问题 排序重构问题 。 1 目 录 目 录 2 摘 要 4 一．求素数问题 5 1.数据结构设计 5 2.算法设计 5 3.调试分析 6 4.测试结果 6 5.源程序（带注释） 6 二．构造可以使N 个城市连接的最小生成树 8 1.数据结构设计 9 2.算法设计 9 3.调试分析 10 4.测试结果11 5.源程序（带注释） 12 三．猴子吃桃问题 19 .数据结构设计 19 2.算法设计 19 3.调试分析 21 4.测试结果 21 5.源程序（带注释） 22 4 ．排序重构问题 24 1.数据结构设计 24 2.算法设计 24 2 3、流程图如下： 25 4 、调试分析 25 5、测试结果 25 6、源程序（带注释） 26 总 结 30 参考文献 31 致 谢 31 3 摘 要 此报告是关于四个问题的设计：求素数问题、猴子吃桃子问题、跳马问题、 哈夫曼的编/译码系统。 1. 求素数问题。埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有 小于N 的素数的方法。从建立一个整数2~N 的表着手，寻找i˂ 的整数，编 程实现此算法，并讨论运算时间。（1） 2. 猴子吃桃子问题。有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且 再多吃一个，到了第 10 天就只余下一个桃子。用多种方法实现求出原来这群 猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解；2)采用链 式数据结构实现上述求解；3)采用递归实现上述求解。（2） 3. 跳马问题。要求在 64 个国际象棋格子,任意位置放一个马,如何不重复地把格 子走完。（3） 4.排序重构问题。令A 为一个由N 个已特殊排序数组成的数列：A ，A ，…，A ， 1 2 N 其中A =0。令B 为N （N-1）/2 个数（定义为D =A -A (ij)）组成的数列。例如， 1 ij i j A=0，1，5，8，那么D=1，3，4，5，7，8。请完成： a） 编写程序，根据A 构造D； 编写程序，构造与D 相对应的某一个数列A ，注意A 不是唯一的。。 1）编译的语言：C 语言 2）编译环境：Visual C++ 6.0 关键词：递归，链表，栈和队列，猴子吃桃，跳马，排序重构 C 语言 数据结构 顺序表 链表 数组 4 一．求素数问题 埃拉托色尼筛法（Sieve of Eratosthenes ）是一种用来求所有小于N 的素数的方法。 从建立一个整数2~N 的表着手，寻找i˂ 的整数，编程实现此算法，并讨论运算 时间。(1) 1.数据结构设计 定义一个线性表顺序存储结构，用来求所有小于N 的素数 typedef int DataType;//数据类型 typedef struct{ DataType data[maxsize]; 定义一个一维数组 int length;//线性表中实际元素的个数 }Seqlist; 2.算法设计 用一个循环结构判断是否为素数，如果是素数则返回1，负责返回0 。 int sushu(DataType i) { int