算法及数据结构

1、数据结构与算法数据结构与算法 课程设计课程设计题 目：求素数问题;计算 1 的个数问题;递归替换问题;图的基本操作和实现 11目目 录录摘摘 要要 .3 3一求素数问题一求素数问题 .4 41. 采用类语言定义相关的数据类型 .42. 算法设计 .43. 函数的调用关系图 .54.调试分析 .55. 测试结果 .56.源程序（带注释） .7二计算二计算 1 1 的个数问题的个数问题 .9 91.采用类语言定义相关的数据类型.92.算法设计.93.函数的调用关系图.104.调试分析.105.测试结果.116.源程序（带注释）.11三三 递归替换问题递归替换问题.12121.采用类语言定义相关的数

2、据类型 .122. 算法设计 .133. 函数的调用关系图 .144.调试分析 .155. 测试结果 .156.源程序（带注释） .15四图的基本操作与实现四图的基本操作与实现 .18181. 采用类语言定义相关的数据类型 .182. 算法设计 .193函数的调用关系图 .19224.调试分析 .205.测试结果 .206.源程序（带注释） .21总总 结结 .3232参考文献参考文献 .3333致致 谢谢 .333333摘摘 要要 素数问题的求解是查找小于 N 的素数的求解方法，它能够实现对数据N 的输入，判断 N 是否越界，查找小于 N 的素数，判断是否继续输入 N 等操作。计算 1 的个

3、数问题是递归程序，通过分析输入十进制值，返回十进制数 N的二进制表示中 1 的个数。递归替换是用相应文件的内容来替换上面的代码“预编译” 的命令，即在最后的结果查看文件中没有“# include”字样。图的基本操作与实现。自选存储结构,输入含 n 个顶点（用字符表示顶点）和 e 条边的图 G；求每个顶点的度,输出结果；指定任意顶点 x 为初始顶点,对图 G 作 DFS 遍历,输出 DFS 顶点序列；指定任意顶点 x 为初始顶点,对图 G 作 BFS 遍历,输出 BFS顶点序列；输入顶点 x,查找图 G:若存在含 x 的顶点,则删除该结点及与之相关连的边,并作 DFS 遍历；判断图 G 是否是连

4、通图，输出信息“YES”/“NO” ；如果选用的存储结构是邻接矩阵,则用邻接矩阵的信息生成图 G 的邻接表,即复制图 G。关键词：关键词： 数据结构；递归；文件；图44一求素数问题一求素数问题埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于 N 的素数的方法。从建立一个整数 2N 的表着手，寻找 i的整数，编程实现此算法，并讨论运算时间。1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型定义一个线性表顺序存储结构，用来求所有小于 N 的素数typedef int DataType;/数据类型typedef structDataType datama

5、xsize;/定义一个一维数组int length;/线性表中实际元素的个数Seqlist;2.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;553.3.函数的调用关系图函数的调用关系图4.4.调试分析调试分析a 当 m 的值大于 maxsize 的值是发生越界问题，在输入 m 时要确保 m 的值要小于 maxsize 的值图 1.1b算法的时间复杂度 O(L.length-1)

6、+O(m)。5.5.测试结果测试结果主函数sushu661. 图 1.2 2200 数的表2. 图 1.3 1m 之间的素数773.图 1.4 m 大于 L.length 时的图6.6.源程序（带注释）源程序（带注释）#include #include #define maxsize 200#define FALSE 0typedef int DataType;typedef structDataType datamaxsize; /定义一个一维数组int length; /线性表中实际元素的个数Seqlist;/结点结构88int sushu(DataType i)/判断是否为素数 int

7、m; if(i=1) return 0; for(m=2;mi;m+) if(i%m=0) return 0; return 1;int main() Seqlist L;L.length=maxsize; int m; int j; for(j=2;jL.length ) return FALSE; printf(1 至 m 之间的素数从小到大分别为:n); int i,k=0; for(i=1;i=m ;i+)99 L.datai-1=i; for(i=1;i=m;i+) if(sushu(L.datai-1) k+; printf(%dt,L.datai-1); /符号“t”的作用是横向

8、制表 printf(n 总共%d 个。n,k ); return 0; 二计算二计算 1 1 的个数问题的个数问题 编写递归程序，返回十进制数 N 的二进制表示中 1 的个数。 1.1. 采用类语言定义相关的数据类型采用类语言定义相关的数据类型 采用递归。 根据以下已知情况设计程序： 若 N 是奇数，那么它的二进制中 1 的个数等于 N/2 的二进制中 1 的个数加 1，N-1是偶数，比 N 少一个最低位的 1，1 的个数就是 N/2 的二进制中 1 的个数-1。 2.2. 算法设计算法设计 if(N=1) n=1; else if(N+1)%2=0) n=count(N/2)+1;/奇数情况

9、 若 N 是奇数，那么它的二进制中 1 的个数等于 N/2 的二进制中 1 的个数加 1， else if(N%2=0) n=count(N+1)-1;/偶数情况 若 N 是奇数,N-1 是偶数，比N 少一个最低位的 1，1 的个数就是 N/2 的二进制中 1 的个数-1 return n; 10103.3. 函数的调用关系图函数的调用关系图4.4. 调试分析调试分析a.调试中遇到的问题及问题的解决方法：遇到的问题：在调试时发现，写入程序是产生的数据不当、函数定义不当、函数调用不当等方面的问题。还有一些在输入数据时产生的输入值、输入范围不相匹配的错误。解决方法：对于前一问题，在程序调试中根据系

10、统提示找到相应出错行， 。细心分析、多方求证，最终得到顺利解决。对于后一问题，可根据事先程序中写入的相关提示就可以解决，如无提示就返回相关实现的算法程序中查找。b.算法的时间复杂度和空间复杂度：时间复杂度为：O(1),空间复杂度为：O(n)。主函数递归11115.5. 测试结果测试结果图 2.1 二进制中 1 的个数结果6.6. 源程序（带注释）源程序（带注释）#includeint count(int N)int n;if(N=1)n=1;else if(N+1)%2=0)n=count(N/2)+1;/奇数情况，若 N 是奇数，那么它的二进制中 1 的个数等于 N/2 的二进制中 1 的个

11、数加 1；else if(N%2=0)1212n=count(N+1)-1;/偶数情况，若 N 是奇数，,N-1 是偶数，比 N 少一个最低位的 1，1 的个数就是 N/2 的二进制中 1 的个数-1 return n;void main()int N;printf(请输入数字：);scanf(%d,&N);printf(二进制中 1 的个数：%dn,count(N);三三 递归替换问题递归替换问题编写程序，扩展 C/C+源文件中的#include 指令（以递归的方式） 。请以文件名的内容替换形如下面的代码行。1.1.采用类语言定义相关的数据类型采用类语言定义相关的数据类型typede

12、f struct /创建结构体，让文件的读写方便 char dataMAX; /数据项char1;intprint(char chMAX,int n) /递归函数13132.2.算法设计算法设计 FILE *fp,*fp1; char sMAX; /s，存储#后面的include char1 bMAX; /b,文件中内容在内存中的存储位置 int i=0,k,d=0,j,flag; /switch 参数，用于确认调用函数的参数 if(fp=fopen(ch,rb+)=NULL) printf(文件打开失败！n); exit(0); while(!feof(fp) fread(&bi,1

13、,sizeof(char1),fp); i+; if(bi-1.data0=) /结构体数组计数器 break; k=i-1; /记录 b 大小，可以认为是对应文件的行数 fclose(fp);14143.3.函数的调用关系图函数的调用关系图 创建三个文件用来存储预编译命令创建要编译的文件通过递归算法实现文件预编译保存结果，输出结果15154.4.调试分调试分析析调试中遇到的问题及对问题的解决方法:如何产生不同的递归调用。解决方法是：通过一个递归函数，产生不同的递归调用。5.5.测试结果测试结果图 3.16.6.源程序（带注释）源程序（带注释）# include # include # inc

14、lude #define MAX 100typedef struct /创建结构体，让文件的读写方便 char dataMAX; /数据项char1;intprint(char chMAX,int n) /递归函数1616 FILE *fp,*fp1; char sMAX; /s，存储#后面的include char1 bMAX; /b,文件中内容在内存中的存储位置 int i=0,k,d=0,j,flag; /switch 参数，用于确认调用函数的参数 if(fp=fopen(ch,rb+)=NULL) printf(文件打开失败！n); exit(0); while(!feof(fp) f

15、read(&bi,1,sizeof(char1),fp); i+; if(bi-1.data0=) /结构体数组计数器 break; k=i-1; /记录 b 大小，可以认为是对应文件的行数 fclose(fp); if(fp1=fopen(辅助.c,ab+)=NULL) printf(文件打开失败！n); exit(0); d=0; /s 数组存取计数1717器 for(i=0;ik;i+) if(bi.data0=#) /发现include，递归调用 print for(j=2;j9;j+) sd=bi.dataj; d+; if(strcmp(s,include)=0) flag

16、=bi.data19-0; switch(flag) /带选择的递归调用 case 1:fp=print(filename1.c,1);break; case 2:fp=print(filename2.c,2);break; case 3:fp=print(filename3.c,3);break; default:break; else /否则的话讲代码存入辅助文件 printf(%sn,bi.data); fwrite(&bi,1,sizeof(char1),fp); fputc(r, fp); fputc(n, fp);1818 else /否则的话讲代码存入辅助文件 print

17、f(%sn,bi.data); fwrite(&bi,1,sizeof(char1),fp1); fputc(r, fp); fputc(n, fp); close(fp1); return 0;四图的基本操作与实现四图的基本操作与实现1.1. 采用类语言定义相关的数据类型采用类语言定义相关的数据类型 typedef struct EdgeNode int nextToVertex; /相邻顶点 struct EdgeNode * nextEdge; /下一条边 EdgeNode,*PEdgeNode; /图的顶点的定义 typedef struct VertexType vertex

18、; /顶点信息 PEdgeNode firstEdge; /第一条边（出度） VertexNode,*PVertexNode; /图的定义 1919 typedef struct int vertexNum; /顶点个数 int edgeNum; /边的个数 VertexNode vertexNodeMAX_VERTEX; /顶点信息数组 GraphList,*PGraphList;2.2.算法设计算法设计采用邻接表来存储无向图，无向图中有 n 个顶点 e 条边，所以邻接表需要 n个头结点和 2e 个表结点，顶点 vi的度恰好为第 i 个链表中的表结点数。深度优先的非递归算法需要借助栈实现，对

19、所有节点做未访问标记后起始节点入栈，使用 while 循环栈不为空时，栈顶顶点 v 出栈，如果顶点 v 未标记为已访问标记 v为已访问，遍历顶点 v 的邻接点，如果邻接点 u 未被标记为已访问，则 u 入栈，如此循环完成深度优先遍历。同理借助借助队列完成图的广度遍历。通过遍历邻接表中的表结点，确定邻接矩阵中的相应元素。对图深度优先遍历后，如果存在未被标记的顶点，说明图不是连通图，否则是连通。3 3函数的调用关系图函数的调用关系图 Y N开始Main（）操作选择结束建立图求深度遍历生成邻接表20204.4.调试分析调试分析深度优先遍历的非递归算法在最好的情况下（每个顶点仅有两条边相连）每个顶点仅

20、被访问一次，时间复杂度为 O（n） ；而在最坏的情况下（图为完全图时） ，搜索第 i 层结点时将会有 n-i 个结点入栈，最多在栈中存储（n-2）*（n-1）/2个结点，此时的时间复杂度与递归算法类似，为 O（n） 。5.测试结果测试结果1.图 4.1 第一个顶点第一个边21212.图 4.2 6 顶点 6 边6.6.源程序（带注释）源程序（带注释）#include#include#define maxsize 10#define Stack_size 50typedef int QueueDataType;typedef int StackDataType;typedef struct no

21、de int data; struct node *next;dnode;typedef struct2222int vex; dnode *first;Node;typedef struct Node arrymaxsize; int num;graph;typedef struct StackDataType DataStack_size;int top;SeqStack;/初始化 void initStack(SeqStack *S)S-top=-1;/判断是否为空int isEmpty(SeqStack *S)return(S-top=-1 ); /入栈 void Push(SeqSt

22、ack *S,StackDataType x) if(S-top=Stack_size-1) printf(栈满n); S-top+;S-DataS-top=x;2323 /出栈 int Pop(SeqStack *S) StackDataType x; if(S-top=-1) printf(栈空n); x=S-DataS-top;S-top-;return x; typedef structQueueDataType datamaxsize;int front;int rear;SeqQueue;SeqQueue *S;void InitQueue(SeqQueue *S)S=(SeqQu

23、eue *)malloc(sizeof(SeqQueue);S-front=S-rear=0;void EnQueue(SeqQueue *S,int v)S-dataS-rear=v;S-rear+;int DeQueue(SeqQueue *S,int v)v=S-dataS-front;S-front=S-front+;return v;2424int visitmaxsize;graph creat()/创建邻接表 graph a; dnode *p; int i,x,y,e; printf(输入顶点数和边数（以空格分割） ：); scanf(%d%d,&a.num,&

24、e); for(i=1;i=a.num;i+) a.arryi.first=NULL; a.arryi.vex=i; printf(顶点下标从 1 开始n); for(i=1;idata=y; p-next=a.arryx.first; a.arryx.first=p; p=(dnode*)malloc(sizeof(dnode); p-data=x; p-next=a.arryy.first ; a.arryy.first=p;2525 return a;/转换为 邻 接矩阵 void copy(graph b,int adjmaxsize) int i,j; dnode *p; for(i

25、=1;i=b.num;i+) for(j=1;j=b.num;j+) adjij=0; for(i=1;idata=1; p=p-next ; for(i=1;i=b.num;i+) for(j=1;j=b.num;j+) printf(%d ,adjij); printf(n); void vexdu(graph a)/求度数2626 dnode *p; int i,count; for(i=1;inext ; printf(%d 的度数:%dn,a.arryi.vex,count); void clr() int i; for(i=1;idata=0) Push(S,p-data);/ 下

26、一个未访问的所有顶点 入栈 p=p-next; /广度优先遍历 void bfs(graph a,int v)SeqQueue *Q;InitQueue(Q);clr();EnQueue(Q,v);while(Q-front!=Q-rear) v=DeQueue(Q,v);dnode *p;2828p=a.arryv.first;if(visitv=0)visitv=1;printf( %d,v);while(p)/ 访问下一个未访问的所有顶点 并入队 if(visitp-data=0) visitp-data=1;printf( %d,p-data);EnQueue(Q,p-data);p=

27、p-next; void find1(graph a) int v; clr(); printf(输入 DFS 开始顶点: ); scanf(%d,&v); printf(DFS 结果：); dfs(a,v);void find2(graph a)int x;printf(n 输入 BFS 开始顶点: );scanf(%d,&x);2929printf(BFS 结果：n); bfs(a,x); void find3(graph a) int i; clr(); printf(n 是连通图？：); dfs(a,1); for(i=1;ia.num;i+) if(visiti=0)

28、 printf( NOn);/ 此图不是连通的。 return ; printf( YESn);/ 此图是连通的? return;void find4(graph a) int x,i; dnode *p,*q; clr(); printf(输入要查找删除的点：); scanf(%d,&x); for(i=1;ia.num) printf(没找到！无 xn);3030 return; else printf(找到！n); q=p=a.arryi.first ; a.arryi.vex=0; if(p-data=x)p=p-next; else while(p) if(p-data=x)

29、 q-next=p-next; break; q=p; p=p-next; printf(DFS 结果：n); dfs(a,x); printf(n); void find5(graph a) int vmaxsizemaxsize; printf(邻接矩阵：n); copy(a,v);3131 int main() graph h; h=creat(); vexdu(h); find1(h); find2(h); find3(h); find4(h); find5(h);3232总总 结结通过本次课程设计使我提升了如何从实际问题中抽象出合适的数学模型，采取合适的数据处理方式和设计算法解决实际问题的能力，加深了对数据表达及存储形式的理解。递归替换程序，使我进一步理解了队列的链式存储方式，学会了利用队列的链式存储设计相关函数以解决此类数学模型问题