算法与数据结构

1、数据结构与算法 课程设计题 目：求素数问题；方程求解问题；最短字符串问题；扫雷问题专业班级： 软件工程三班 目 录摘 要4一 求素数问题51.采用类语言定义相关的数据类型52.算法设计53.调试分析64.测试结果65.源程序（带注释）6二方程求解问题81.采用类语言定义相关的数据类型82.算法设计83.函数的调用关系图94.调试分析95.测试结果96.源程序（带注释）9三最短字符串问题111.采用类语言定义相关的数据类型112.算法设计113.函数的调用关系图124.调试分析125.测试结果136.源程序（带注释）15四扫雷问题191.采用类语言定义相关的数据类型192.算法设计203.函数的

2、调用关系图214.调试分析215.测试结果226.源程序（带注释）23总 结27参考文献28致 谢29摘 要处理了四个问题：求素数问题，用埃拉托色尼筛法（Sieve of Eratosthenes）结合顺序表求出所有小于N的素数；方程求解问题，方程A5+B5+C5+D5+E5=F5刚好有满足0ABCDEF75的整数解，利用穷举循环求解；最短字符串问题，编写一个程序，从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干，字符串具有相同的长度，就按字母顺序输出它们；扫雷问题，编写一个程序读取文件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为O的方块，这些

3、就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成O，而那些不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。关键词： 埃拉托色尼筛法；方程求解；最短字符串； 扫雷一 求素数问题埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2N的表着手，寻找i#的整数，编程实现此算法，并讨论运算时间。1.采用类语言定义相关的数据类型利用顺序表存储结构：typedef structint *elem;int length;int listsize;Sqlist;2.算法设计算法描述：先把1删除（

4、现今数学界1既不是质数也不是合数）；读取队列中当前最小的数2，然后把2的倍数删去；读取队列中当前最小的数3，然后把3的倍数删去；读取队列中当前最小的数5，然后把5的倍数删去；如上所述直到需求的范围内所有的数均删除或读取。算法实现：Sqlist l;for(int i=1;i=number;i+)l.elemi=i;l.elem1=0;for(int p=2;psqrt(number);p+)for(int j=p+1;j=number;j+)if(l.elemj!=0)&(l.elemj%p=0)l.elemj=0;3.调试分析由于说明书中字符显示问题，上网搜索埃拉托色尼筛法，了解如何求素数，

5、用数组解决了这个问题。时间复杂度是O（n3/2）空间复杂度是O（n）。4.测试结果图1.1以100为例测试结果5.源程序（带注释）int InitList_sq(Sqlist &L)L.elem=(int *)malloc(LIST_INIT_SIZE *sizeof(int);if(!L.elem)printf(存储分配失败！);L.length=0;L.listsize=LIST_INIT_SIZE;return 0;Sqlist l；for(int i=1;i=number;i+)l.elemi=i;l.elem1=0;for(int p=2;psqrt(number);p+)for(i

6、nt j=p+1;j=number;j+)if(l.elemj!=0)&(l.elemj%p=0)l.elemj=0;二方程求解问题方程A5+B5+C5+D5+E5=F5刚好有一个满足0ABCDEF75的整数解。请编写一个求出该解的程序。（3）1. 采用类语言定义相关的数据类型数据声明和头文件声明：#include#include int key();long p76;long A,B,C,D,E,F,i,flag=0;2.算法设计算法描述：首先建立数组，用来存储整型ABCDEF五次方的值，然后利用fo嵌套循环，一次求ABCDEF五次方的值，接下来用if判断语句，若ABCDE次方之和与F五次方

7、的差为零，输出ABCDEF的整数解。算法实现：for(i=0;i=75;i+) pi=int(pow(i,5); /把的次方放在数组中，以便调用 for(A=0;A=60;A+)/循环穷举找到方程的解 for(B=A;B=75;B+)for(C=B;C=75;C+) for(D=C;D=75;D+) for(E=D;E=75;E+) for(F=E;F=75;F+) if(pA+pB+pC+pD+pE-pF=0) printf(ttt%d %d %d %d %d %dnn,A,B,C,D,E,F);3.函数的调用关系图 4.调试分析这个算法说明比较容易理解，思路简单，就是不容易使用算法与数据结

8、构的知识。时间复杂度O(n6),空间复杂度O(n)。5.测试结果图2.1运行后部分结果截图6.源程序（带注释）#include#include int key() /求方程的解 找到解返回否则返回 long p76; long A,B,C,D,E,F,i,flag=0; for(i=0;i=75;i+) pi=int(pow(i,5); /把的次方放在数组中，以便调用 for(A=0;A=60;A+)/循环穷举找到方程的解 for(B=A;B=75;B+) for(C=B;C=75;C+) for(D=C;D=75;D+) for(E=D;E=75;E+) for(F=E;F=75;F+) i

9、f(pA+pB+pC+pD+pE-pF=0) printf(ttt%d %d %d %d %d %dnn,A,B,C,D,E,F); flag=1; if(flag=1) return 1; else return 0; int main() if(key()=0) printf(方程A5+B5+C5+D5+E5=F5(0=A=BC=D=E=F=75)无解); return 1;三最短字符串问题编写一个程序，从输入中读取字符串，并按长度顺序，最短字符串优先的原则输出它们。如果有若干字符串具有相同的长度，就按字母顺序输出它们。1.采用类语言定义相关的数据类型首先，将字符串输入 tempMaxSi

10、ze，然后将数据存入str1中，在比较时引入str2,比较字符串长度或者字母，将最短的字符串存入str2中，之后调用输出函数输出。数据声明，预编译，头文件声明：#include#include#include#define Max 100/预设最大字符串个数#define MaxSize 256int num;/全局变量num表示输入字符串个数int input(char *str1)int count=0;char tempMaxSize;2.算法设计字符串的输入代码通过建立数组str1,当字符串的格数小于宏定义中num 时，可以输入一些字符串。字符串的排序代码当输入字符串时，调用函数 so

11、rt() 进行排序，更具字符串的长短进行排序。如果字符串长度相同时，可以更具字母优先进行排序。算法实现：int i,j;char tempMaxSize;for(i=0;inum-1;i+)for(j=i+1;jnum;j+)if(strlen(str2j)strlen(str2i)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(str2i,temp);if(strlen(str2j)=strlen(str2i)if(strcmp(str2j,str2i)0)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(

12、str2i,temp);puts(排序完毕！);3.函数的调用关系图最短字符串采用数组的形式进行输入和排序的，通过子函数4.调试分析调试中遇到的问题及对问题的解决方法输入数据看是否满足需求,采用顺序表进行存储。时间复杂度：T(n)=O(n)，空间复杂度：S(n)=O(2n)。5.测试结果图3.1菜单图3.2输入字符串图3.3排序图3.4输出排序结果6.源程序（带注释）#include#include#include#define Max 100/预设最大字符串个数#define MaxSize 256int num; /全局变量num表示输入字符串个数/字符串输入函数int input(cha

13、r *str1)int count=0;char tempMaxSize;printf(输入字符串个数);scanf(%d,&num);while(countnum)printf(输入第%d个,count+1);if(scanf(%s,temp)&temp0!=0)str1count=(char *)malloc(sizeof(temp);strcpy(str1count,temp);count+;puts(输入完毕！);return 1;/字符串排序函数int sort(char *str2)int i,j;char tempMaxSize;for(i=0;inum-1;i+)for(j=i

14、+1;jnum;j+)if(strlen(str2j)strlen(str2i)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(str2i,temp);if(strlen(str2j)=strlen(str2i)if(strcmp(str2j,str2i)0)strcpy(temp,str2j);strcpy(str2j,str2i);strcpy(str2i,temp);puts(排序完毕！);return 1;/字符串显示函数void show(char *str)int i;for(i=0;inum;i+)puts(stri);/菜单函数voi

15、d menu()puts(=);puts(= 最短字符串问题 =);puts( 1、输入字符串 );puts( 2、排序字符串 );puts( 3、输出字符串 );puts( 4、退出 );puts(=);/主函数int main()int key,flag1=0,flag2=0;char *str1Max;while(1)system(cls);/清屏fflush(stdin);menu();printf(请选择(1/2/3):n);scanf(%d,&key);if(key=1)flag1=input(str1);else if(key=2)if(flag1)flag2=sort(str1

16、);elseputs(没有字符串！请选择1、输入字符串！);else if(key=3)if(flag1=1&flag2=0)puts(输入的字符串为：);show(str1);else if(flag1=1&flag2=1)puts(排序后的字符串为：);show(str1);elseputs(没有字符串！请选择1、输入字符串！);else if(key=4)return 0;elseprintf(对不起，没有这个选项!n);system(pause);/暂停 四扫雷问题有些个人计算机会带有一个名为Minesweeper的游戏。该游戏界面是一个网格，网格中的有些方块是雷。编写一个程序以读取文

17、件，该文件中存放着网格中的行数、列数以及网格本身。网格会含有一些标记为o的方块，这些就是雷。其他方块不是雷，将会标记上问号（？）。程序的输出就是输出这个网格。雷依然会标记成o，而那些不含雷的方块会替换成一个数字，以表明邻近雷的个数。最大数字将是8。（4）1.采用类语言定义相关的数据类型数据结构和头文件声明：#include windows.h#include iostream#include fstreamtypedef struct _MINERint IsMiner;int MinerNum;MINER,*LPMINER;/结构体及其位置指针 LPMINER m_Array;long m_

18、N;std:ifstream m_ifs;CMiner();/构造函数CMiner();/析构函数int Init(int n);/初始化int Display();int Sweep(int i, int j);int Probe(int i, int j);2.算法设计计算每个位置周围雷的算法：每个雷周围有八个位置，其布雷情况可以有循环算法来实现，在循环中计算每个雷周围的雷数，我用了静态数据存储实现。算法实现：int CMiner:Sweep(int i,int j)/扫雷int sum = 0;sum+=Probe(i - 1, j - 1);sum+=Probe(i - 1, j );

19、 sum+=Probe(i - 1, j + 1);sum+=Probe(i , j - 1);sum+=Probe(i , j + 1);sum+=Probe(i +1, j - 1);sum+=Probe(i + 1, j );sum+=Probe(i + 1, j +1);return sum; int CMiner:Probe(int i, int j)/试探if (i 0)return 0;if (j = m_N)return 0;if (j = m_N)return 0;if (m_Arrayi*m_N + j.IsMiner)return 1;return 0;3.函数的调用关系

20、图开始判定条件进行计算雷数条件变化语句结束输出计结果4.调试分析这个问题比较复杂，听过同学帮助和网上搜索，了解算法和程序设计，没有编写随机布雷的算法，只写了扫雷的算法。时间复杂度O(n2),空间复杂度O(n)。5.测试结果图4.1文件中的8*8雷阵图4.2扫雷结果6.源程序（带注释）/miner.h#include windows.h#include iostream#include fstreamtypedef struct _MINERint IsMiner;int MinerNum;MINER,*LPMINER;class CMinerpublic:LPMINER m_Array;lon

21、g m_N;std:ifstream m_ifs;CMiner();/构造函数CMiner();/析构函数int Init(int n);/初始化int Display();int Sweep(int i, int j);int Probe(int i, int j);#include Miner.hCMiner:CMiner()CMiner:CMiner()int CMiner:Init(int n)char temp128;m_ifs.open(miner.txt, std:ios_base:app);/ m_Array初始化m_Array = (LPMINER)malloc(sizeof

22、(MINER)*n*n);memset(m_Array, 0, sizeof(MINER)*n*n);m_N = n;int i,j;for ( i = 0; i m_N; i+)m_ifs.getline(temp, 128);for (j = 0; j m_N; j+)if (tempj = O)m_Arrayi*m_N + j.IsMiner = 1;return 0;int CMiner:Display()/展示int i, j;for (i = 0; i m_N; i+)for (j = 0; j m_N; j+)if (m_Arrayi*m_N + j.IsMiner = 0)m_

23、Arrayi*m_N + j.MinerNum=Sweep(i, j);printf(%2d, m_Arrayi*m_N + j.MinerNum);elseprintf( %O);printf(n);return 0;int CMiner:Sweep(int i,int j)/扫雷int sum = 0;sum+=Probe(i - 1, j - 1);sum+=Probe(i - 1, j ); sum+=Probe(i - 1, j + 1);sum+=Probe(i , j - 1);sum+=Probe(i , j + 1);sum+=Probe(i +1, j - 1);sum+=

24、Probe(i + 1, j );sum+=Probe(i + 1, j +1);return sum;int CMiner:Probe(int i, int j)/试探if (i 0)return 0;if (j = m_N)return 0;if (j = m_N)return 0;if (m_Arrayi*m_N + j.IsMiner)return 1;return 0;/SweepMiner.cpp #include stdafx.h#include Miner.hint _tmain(int argc, _TCHAR* argv)CMiner miner1;miner1.Init(

25、8);miner1.Display();system(pause);return 0;总 结课程设计是培养学生综合运用所学知识,发现,提出,分析和解决实际问题,锻炼实践能力的重要环节,是对学生实际工作能力的具体训练和考察过程.随着科学技术发展的日新日异，当今计算机应用在是生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术十分重要的。回顾起此次课程设计，至今我仍感慨颇多，的确，从从拿到题目到完成整个编程，从理论到实践，在整整半个月的日子里，可以学到很多很多的的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，通过这次课程设计之后，一定把以前所学过的知识重新温故。在课程设计过程中，我学到了很多人生的哲理，懂得怎么样去制定计划，怎么样去实现这个计划，并掌握了在执行过程中怎么样去克服心理