数据结构课程设计说明书.pdf

******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 2014 年秋季学期 数据结构与算法 课程设计 题 目：求素数问题、计算1的个数问题、 递归替换问题、图的基本操作与实现 专业班级： 软件工程13级1班 姓 名： 学 号： 指导教师： 成 绩： 目 录 摘 要3 一．求素数问题4 1.问题描述4 2.算法设计4 3.源程序4 4.运行结果7 5.总结8 二．计算1 的个数问题9 1.问题描述9 2.算法设计9 3.源程序9 4.运行结果11 5.总结11 三.递归替换的问题11 1.问题描述11 2.算法设计11 3.源程序12 4.运行结果15 5.总结15 四.图的基本操作与实现16 1.问题描述16 2.算法设计16 3.源程序17 4.运行结果45 5.总结46 参考文献48 致 谢49 摘 要 本设计主要是用C语言设计开发，所用IDE工具为codeblocks，四个问题 均应用了不同的数据结构，有图的存储，有递归的操作等等，再设计过程中也应 用了不同的算法如埃拉托色尼筛法，图的深度优先搜索和广度优先搜索。 第一个程序是用埃拉托色尼筛法求解素数问题。用一个循环结构判断是否为 素数，如果是素数则返回1，负责返回0。 第二个程序是递归结构计算1的个数问题，共分为两种情况，奇数情况和偶 数情况。 第三个程序为递归替换仿编译问题，具体要求是递归替换问题。编写程序， 扩展C/C++源文件中的#include指令 （以递归的方式）。以文件名的内容替换形 预编译命令“include”。具体是用相应文件的内容来替换上面的代码“预编译” 的命令，即在最后的结果查看文件中没有 “# include”字样，其位置为相应文 件的内容，考虑到有可能在我们要替换的文件中也可能会有预编译命令，所以要 用递归的算法。通过这个代码的编写可以帮我们更深层次的理解c语言编译的过 程，同时也能够练习递归的运用。 第四个程序为图的一些基本操作，内容包括图的存储结构、图的深度优先遍 历，广度优先遍历，图节点的度数等等。 关键词： 埃拉托色尼筛法 素数问题 递归 替换 连通图 克鲁斯卡尔算法 数据结构 图的遍历 一．求素数问题 1.问题描述 埃拉托色尼筛法 （Sieve of Eratosthenes）是一种用来求所有小于N 的素 数的方法。从建立一个整数2~N 的表着手，寻找i˂ 的整数，编程实现此算法， 并讨论运算时间。(1) 2.算法设计 用一个循环结构判断是否为素数，如果是素数则返回1，负责返回0。 int sushu(DataType i) { int m; if(i 1) return 0; for(m 2;mi;m++) { if(i%m 0) return 0; } return 1; } 3.源程序 #includestdio.h #includemath.h 4 #definemaxsize200 #defineFALSE 0 typedefint Dat