数据结构课程设计说明书

*******************实践教学*******************兰州理工大学计算机与通信学院2014年秋季学期数据结构与算法课程设计题目：求素数问题、计算1的个数问题、递归替换问题、图的基本操作与实现专业班级：软件工程13级1班姓名：学号：指导教师：成绩：目录摘要...................................................................................................................3一．求素数问题...................................................................................................41.问题描述.........................................................................................................42.算法设计.........................................................................................................43.源程序.............................................................................................................44.运行结果.........................................................................................................75.总结.................................................................................................................8二．计算1的个数问题.......................................................................................91.问题描述.........................................................................................................92.算法设计.........................................................................................................93.源程序.............................................................................................................94.运行结果.......................................................................................................115.总结...............................................................................................................11三.递归替换的问题............................................................................................111.问题描述.......................................................................................................112.算法设计.......................................................................................................113.源程序...........................................................................................................124.运行结果.......................................................................................................155.总结...............................................................................................................15四.图的基本操作与实现....................................................................................161.问题描述.......................................................................................................162.算法设计.......................................................................................................163.源程序...........................................................................................................174.运行结果.......................................................................................................455.总结...............................................................................................................46参考文献.............................................................................................................48致谢.................................................................................................................49摘要本设计主要是用C语言设计开发，所用IDE工具为codeblocks，四个问题均应用了不同的数据结构，有图的存储，有递归的操作等等，再设计过程中也应用了不同的算法如埃拉托色尼筛法，图的深度优先搜索和广度优先搜索。第一个程序是用埃拉托色尼筛法求解素数问题。用一个循环结构判断是否为素数，如果是素数则返回1，负责返回0。第二个程序是递归结构计算1的个数问题，共分为两种情况，奇数情况和偶数情况。第三个程序为递归替换仿编译问题，具体要求是递归替换问题。编写程序，扩展C/C++源文件中的#include指令（以递归的方式）。以文件名的内容替换形预编译命令“include”。具体是用相应文件的内容来替换上面的代码“预编译”的命令，即在最后的结果查看文件中没有“#include”字样，其位置为相应文件的内容，考虑到有可能在我们要替换的文件中也可能会有预编译命令，所以要用递归的算法。通过这个代码的编写可以帮我们更深层次的理解c语言编译的过程，同时也能够练习递归的运用。第四个程序为图的一些基本操作，内容包括图的存储结构、图的深度优先遍历，广度优先遍历，图节点的度数等等。关键词：埃拉托色尼筛法素数问题递归替换连通图克鲁斯卡尔算法数据结构图的遍历4一．求素数问题1.问题描述埃拉托色尼筛法（SieveofEratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2~N的表着手，寻找i˂错误!未找到引用源。的整数，编程实现此算法，并讨论运算时间。(1)2.算法设计用一个循环结构判断是否为素数，如果是素数则返回1，负责返回0。intsushu(DataType&i){intm;if(i==1)return0;for(m=2;mi;m++){if(i%m==0)return0;}return1;}3.源程序#includestdio.h#includemath.h5#definemaxsize200#defineFALSE0typedefintDataType;typedefstruct{DataTypedata[maxsize];intlength;}Seqlist;//结点结构intsushu(DataTypei)//判断是否为素数{intm;if(i==1)return0;for(m=2;mi;m++){if(i%m==0)return0;}return1;}intmain(){SeqlistL;L.length=maxsize;intm;intj;for(j=2;j=L.length;j++){L.data[j-1]=j;6printf(%d\t,L.data[j-1]);}printf(\n);printf(inputm:\n);scanf(%d,&m);if(mL.length)returnFALSE;printf(1至m之间的素数从小到大分别为:\n);inti,k=0;for(i=1;i=m;i++)L.data[i-1]=i;for(i=1;i=m;i++)if(sushu(L.data[i-1])){k++;printf(%d\t,L.data[i-1]);//符号“\t”的作用是横向制表。}printf(\n总共%d个。\n,k);return0;}74.运行结果图1.图2为1~m之间的素数图23图3为m大于L.length时的图8图35.总结1当m的值大于maxsize的值是发生越界问题，在输入m时要确保m的值要小于maxsize的值2、算法的时间复杂度O(L.length-1)+O(m)。9二．计算1的个数问题1.问题描述编写递归程序，返回十进制数N的二进制表示中1的个数。2.算法设计采用递归结构采用以下已知情况设计程序若N是奇数，那么它的二进制中1的个数等于N/2的二进制中1的个数加1，N-1是偶数，比N少一个最低位的1，1的个数就是N/2的二进制中1的个数-1。3.源程序#includestdio.h10intcount(intN){intn;if(N==1)n=1;elseif((N+1)%2==0)n=count(N/2)+1;//奇数情况若N是奇数，那么它的二进制中1的个数等于N/2的二进制中1的个数加1，elseif(N%2==0)n=count(N+1)-1;//偶数情况若N是奇数,N-1是偶数，比N少一个最低位的1，1的个数就是N/2的二进制中1的个数-1ret