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

*******************

实践教学

*******************

兰州理工大学

计算机与通信学院

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.问题描述

埃拉托色尼筛法（SieveofEratosthenes）是一种用来求所有小于N的素

数的方法。从建立一个整数2~N的表着手，寻找i˂的整数，编程实现此算法，

并讨论运算时间。(1)

2.算法设计

用一个循环结构判断是否为素数，如果是素数则返回1，负责返回0。

intsushu(DataTypei)

{

intm;

if(i1)

return0;

for(m2;mi;m++)

{

if(i%m0)

return0;

}

return1;

}

3.源程序

#includestdio.h

#includemath.h

4

#definemaxsize200

#defineFALSE0

typedefintDat