算法及数据结构课程设计说明书

1、目录摘 要3一求素数问题41.1 采用类C语言定义相关的数据类型41.2算法设计41.3函数的调用关系图51.4调试分析51.5测试结果61.6 源程序（带注释）7二猴子摘桃子问题92.1采用类C语言定义相关的数据类型92.2算法设计92.3函数调用关系图102.4调试分析112.5测试结果112.5源程序（带注释）13三跳马问题163.1采用类语言定义相关的数据类型163.2算法设计163.3函数的调用关系图173.4调试分析173.5测试结果183.6.源程序（带注释）19四.可以使n个城市连接的最小生成树254.1采用类C语言定义相关的数据类型254.2算法设计254.3函数的调用关系图

2、274.4调试分析274.5测试结果284.6源程序（带注释）29总 结32参考文献33致 谢34摘 要素数问题主要是运用数据逻辑结构。采用指针数组，算法进行求解。猴子吃桃子桃子问题主要运用了数据的逻辑结构，数据的存储结构。采用数组，连式存储结构和递归调用进行。跳马问题要求在8*8的64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。给定一个8*8的棋盘，起始点在某坐标处，要求求出有多少种方法，可以不重复的遍历棋盘上所有的点规则：1.马走日字2.走过的点就不能再走。构造可以使n个城市连接的最小生成树问题给定一个地区的n个城市间的距离网,城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结

3、构定义,关键词：数据结构；邻接矩阵；类C语言；数组；普里姆算法34一求素数问题埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于N的素数的方法。从建立一个整数2N的表着手，寻找 i的整数，编程实现此算法，并讨论运算时间。1.1 采用类C语言定义相关的数据类型定义一个线性表顺序存储结构，用来求所有小于N的素数typedef int DataType;/数据类型typedef structDataType datamaxsize;定义一个一维数组int length;/线性表中实际元素的个数Seqlist;1.2算法设计 顺序存储结构是存储结构类型中的一种，该结构是把

4、逻辑上相邻的节点存储在物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体现。本程序通过建立一个指针数组为其分配一个空间，在通过埃拉托色尼筛法通过判断将其输出。 for( m1=1;m1<j1;m1+) if(numm1!=0) for(p1=m1+1;p1<n1;p1+) a1=nump1%numm1; if(a1=0) nump1 = 0; 1.3函数的调用关系图1. 如图1.1函数调用关系图Main()print()图1.1 函数调用关系图 1.4调试分析1 当m的值大于maxsize的值是发生越界问题，在输入m时要确保m的值要小于maxsize的值图1.2

5、开始界面2 算法的时间复杂度O(L.length-1)+O(m)。1.5测试结果1 图1为2200数的表 图1.3表2 图2为1m之间的素数图1.4运行结果3 图3为m大于L.length时的图图1.5大于L.lenggth1.6 源程序（带注释）#include <stdio.h>#include <math.h>#define maxsize 200#define FALSE 0typedef int DataType;typedef struct DataType datamaxsize; int length;Seqlist;/结点结构int sushu(Dat

6、aType i)/判断是否为素数 int m; if(i=1) return 0; for(m=2;m<i;m+) if(i%m=0) return 0; return 1;int main() Seqlist L; int m,j; int i,k=0; L.length=maxsize; for(j=2;j<=L.length ;j+) L.dataj-1=j; printf("%dt",L.dataj-1); printf("n"); printf("input m:n"); scanf("%d"

7、,&m); if(m>L.length ) return FALSE; printf("1至m之间的素数从小到大分别为:n"); for(i=1;i<=m ;i+) L.datai-1=i; for(i=1;i<=m;i+) if(sushu(L.datai-1) k+; printf("%dt",L.datai-1); /符号"t"的作用是横向制表。 printf("n总共%d个。n",k ); return 0; 二猴子摘桃子问题 有一群猴子摘了一堆桃子，他们每天都吃当前桃子的一半且再

8、多吃一个，到了第10天就只余下一个桃子。用多种方法实现求出原来这群猴子共摘了多少个桃子。要求：1)采用数组数据结构实现上述求解；2)采用链式数据结构实现上述求解；3)采用递归实现上述求解。2.1采用类C语言定义相关的数据类型1、采用数组数据结构在函数中定义数组peach_tal210来存储每天剩下的桃子总数利用while循环来输出每天剩下的桃子总数.2、采用链式数据结构构建创建链栈stack2，stack2 IT2(stack2 *s2)，void push2(stack2 *s2,int num2)，void peach_lianzhan2(stack2 *s2)。3、采用递归算法 利用fo

9、r循环，来调用递归函数，2.2算法设计 1.一维数组解决。建立一个一维数组a10从第九天开始算起令a9=1利用for循环计算前八天猴子吃的桃子数目并同时将后一天吃的桃子数赋值到前一天。最后即可得出猴子一共吃的桃子数。void peach_shuzu2( )int i2=0, j2=0 ,peach_tal210;peach_tal2days2-1=1;i2=days2;2链式数据结构解决：链栈用链表作为存储结构，栈初始化时仅需给栈顶指针分配内存空间，而后每当有数据入栈时再为该数据分配空间，这样实现了内存空间的动态分配。通过链栈定义了栈顶*t2和栈底*l2;利用每计算一次就出栈并且计算下一天直到

10、结束。并将后一天的之赋值给前一天。最后便可得到猴子吃的总的桃子数。typedef struct 、int *t2;int *l2;stack2;stack2 IT2(stack2 *s2) s2->l2=(int *)malloc(MAX2*sizeof(int); if(s2->l2=NULL) printf(" stack2 initial fail!n"); 3.递归函数解决：递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部，直接或者间接地调用自己的算法。使用if函数控制是否调用函数本身。桃子数等与一这说明第九天吃了一个桃子函数便可以结束

11、。如果桃子数不为一则一直调用函数本身知道调用结束。void peach_digui2(int n2,int i2) if(i2=days2) peach_digui2(n2,i2); 2.3函数调用关系图1.如图2.1函数调用关系图main()menu()peach_lianzha()peach_shuzu()peach_digui()exit()图2.1 函数调用关系图2.4调试分析(1)遇到的问题刚开始时，每一个算法我都是单独的一个程序来实现，基本上没有出现问题，在将所有方法、程序做好后，再将所有程序集合在一起，利用主函数的菜单来分块调用以实现题目要求。在整合过程中，出现了一些编辑错误，但

12、是都是比较小的错误，很快就找出来了，应该说整个程序做的过程还是比较顺利的。(2)算法的时间复杂度和空间复杂度 a.时间复杂度： (1)数组解决：O(1) 2)链栈解决：O(n) (3)递归解决：O(n) b.空间复杂度： (1)数组解决：O(n) (2)链栈解决：O(n) (3)递归解决：O(n)2.5测试结果2.如图2.2测试界面操作图2.2 3. 如图2.3数组测试结果操作 图2.3 4. 图2.4链栈测试结果操作图2.4 5如图2.5递归测试结果图2.5 2.5源程序（带注释）#include<stdio.h>#include<stdlib.h>#include&

13、lt;math.h>#define MAX 50#define days 10#define ERROR 0#define TURE 1void peach_shuzu2( )int i2=0, j2=0 ,peach_tal210;peach_tal2days2-1=1;/最后一天桃子数i2=days2; while(i2>0)/判断天数是否符合要求 peach_tal2j2=2*(peach_tal2i2+1);/该天桃子数 i2=i2-1; j2=i2-1;void pop2(stack2 *s2,int &num2) if(s2->t2=NULL)/判断栈是否

14、为空 printf("error"); else s2->t2-; num2=*s2->t2;void peach_lianzhan2(stack2 *s2)int i2=0,num2=0; push2(s2,1);/进行第一天运算 i2+; for(i2;i2<days2;i2+)/判断天数是否符合 pop2(s2,num2); push2(s2,num2); void peach_digui2(int n2,int i2) if(i2=days2)/判断天数 else n2=2*(n2+1); /计算桃子数 i2+; peach_digui2(n2,i

15、2)；/返回函数继续计算int menu(int m) printf("ttt-n");printf("ttt-1.数组-n");printf("ttt-2.链栈-n");printf("ttt-3.递归-n");printf("ttt-4.退出-n"); printf("please input number:"); scanf("%d",&m); return m;int main() int i=1,n=1,m;stack s; s=IT(&

16、amp;s);while(1) switch(menu(m) case 1: peach_shuzu();break; case 2: peach_lianzhan(&s);break; case 3: peach_digui(n,i);break; case 4: exit(0);break; return 0 ;三跳马问题 要求在64个国际象棋格子,任意位置放一个马,如何不重复地把格子走完。3.1采用类语言定义相关的数据类型#define MAXNUM 8 /横纵格数最大值 #define INVALIDDIR - 1 /无路可走的情况 #define MAXLEN 64 /棋盘总

17、格数 #define MAXDIR 8 /下一步可走的方向 typedef struct int x; /表示横坐标 int y; /表示纵坐标 int direction; /表示移动方向 HorsePoint; HorsePoint ChessPathMAXLEN; /模拟路径栈 int count; /入栈结点个数int ChessBoardMAXNUMMAXNUM; /标志棋盘数组3.2算法设计棋盘初始化的数组,通过建立Initiai()函数。将马没有在棋盘上走过的位置初始化为0，用ChessBoardij=0;表示。其代码如下：void Initial() /棋盘初始化的数组int

18、i,j;for(i=0;i<MAXNUM;i+)for(j=0;j<MAXNUM;j+)ChessBoardij=0; /棋盘格均初始化为0，表示没有走过for(i=0;i<MAXLEN;i+)ChessPathi.x=0;ChessPathj.y=0;ChessPathi.direction=INVALIDDIR;count=0; / 栈中最初没有元素3.3函数的调用关系图函数的调用关系图如图3.1所示图3.1 函数调用关系图开始数组初始化数组为1时,表示已走过数组为0表未走走下一个结点判断是否小于NUM,大于返回上一结点小于则继续往下走图3.1 函数的调用关系图3.4调试

19、分析关于时间复杂度的计算是按照运算次数来进行的, 关于空间复杂度的计算是在程序运行过程所要借助的内容空间大小。即：空间复杂是储存空间的大小和变换等等决定的时间复杂是逻辑比较、赋值等基本运算的次数决定的3.5测试结果 （1）输入初始值 2，4 0，0（2）测试结果如图3.2 图3.3所示图3.2 测试结果图3.3 测试结果3.6.源程序（带注释） #include<stdio.h>#include<stdlib.h>#define MAXNUM 8 /横纵格数最大值#define INVALIDDIR - 1 /无路可走的情况#define MAXLEN 64 /棋盘总格

20、数#define MAXDIR 8 /下一步可走的方向typedef struct int x; /表示横坐标int y; /表示纵坐标int direction; /表示移动方向HorsePoint;HorsePoint ChessPathMAXLEN; /模拟路径栈int count; /入栈结点个数int ChessBoardMAXNUMMAXNUM; /标志棋盘数组void Initial() /棋盘初始化的数组int i,j;for(i=0;i<MAXNUM;i+)for(j=0;j<MAXNUM;j+)ChessBoardij=0; /棋盘格均初始化为0，表示没有走过f

21、or(i=0;i<MAXLEN;i+)ChessPathi.x=0;ChessPathj.y=0;ChessPathi.direction=INVALIDDIR;count=0; / 栈中最初没有元素void PushStack(HorsePoint positon) /入栈函数ChessBoardpositon.xpositon.y=1; /把标志设为1，证明已走过ChessPathcount=positon;count+;HorsePoint PopStack() /出栈函数 HorsePoint positon;count-;positon=ChessPathcount;Chess

22、Boardpositon.xpositon.y=0;ChessPathcount.direction=INVALIDDIR;return positon;HorsePoint GetInitPoint() /输入horse的起始坐标HorsePoint positon;doprintf("n请输入起始点(x,y):");scanf("%d,%d",&positon.x,&positon.y);printf("nn");while(positon.x>=MAXNUM|positon.y>=MAXNUM|pos

23、iton.x<0|positon.y<0); /不超过各个边缘positon.direction=INVALIDDIR; /是初值，没走过return positon;HorsePoint GetNewPoint(HorsePoint *parent) /产生新结点函数int i;HorsePoint newpoint;int tryxMAXDIR=1,2,2,1,-1,-2,-2,-1; /能走的8个方向坐标增量int tryyMAXDIR=-2,-1,1,2,2,1,-1,-2;newpoint.direction=INVALIDDIR; /新结点可走方向初始化parent-&

24、gt;direction=parent->direction+; /上一结点能走的方向for(i=parent->direction;i<MAXDIR;i+)newpoint.x=parent->x+tryxi; /试探新结点的可走方向newpoint.y=parent->y+tryyi;if(newpoint.x<MAXNUM&&newpoint.x>=0&&newpoint.y<MAXNUM&&newpoint.y>=0&&ChessBoardnewpoint.xnewpo

25、int.y=0)parent->direction=i; /上一结点可走的方向ChessBoardnewpoint.xnewpoint.y=1; /标记已走过return newpoint;parent->direction=INVALIDDIR;return newpoint;void CalcPoint(HorsePoint hh ) /计算路径函数HorsePoint npositon;HorsePoint *ppositon;Initial(); /调用初始化函数ppositon=&hh; /调用输入初始点函数PushStack(*ppositon);while(!

26、(count=0|count=MAXLEN) /当路径栈不满或不空时ppositon=&ChessPathcount-1; /指针指向栈npositon=GetNewPoint(ppositon); /产生新的结点if(ppositon->direction!=INVALIDDIR) /可以往下走ChessPathcount-1.direction=ppositon->direction;PushStack(npositon);else PopStack();void PrintChess() /以8*8矩阵的形式输出运行结果int i,j;int stateMAXNUMM

27、AXNUM; /stateij为棋盘上（i,j）点被踏过的次序int step=0; /行走初始化HorsePoint positon;count=MAXLEN;if(count=MAXLEN) /当棋盘全部走过时for(i=0;i<MAXLEN;i+)step+;positon=ChessPathi;statepositon.xpositon.y=step;for(i=0;i<MAXNUM;i+)printf("tt");for(j=0;j<MAXNUM;j+)if(stateij<10)printf(" ");printf(&

28、quot;%6d",stateij); /按顺序输出马踏过的点printf("n");printf("n");elseprintf("tt此时不能踏遍棋盘上所有点!n");int main(int argc,char *argv)HorsePoint h;h=GetInitPoint();CalcPoint(h);PrintChess();return 0;四.可以使n个城市连接的最小生成树4.1采用类C语言定义相关的数据类型邻接矩阵,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;邻接矩阵的存储

29、结构定义, MGraph最小值判断minsideMAX_VERTEX_NUM;普利姆算法PRIM(MGraph G,VertexType u)4.2算法设计 假设 WN=(V,E) 是一个含有 n 个顶点的连通网，TV 是 WN 上最小生成树中顶点的集合，TE 是最小生成树中边的集合。显然，在算法执行结束时，TV=V，而 TE 是 E 的一个子集。在算法开始执行时，TE 为空集，TV 中只有一个顶点，因此，按普里姆算法构造最小生成树的过程为：在所有“其一个顶点已经落在生成树上，而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边，逐条加在生成树上，直至生成树中含有 n-1条边为止。通过教材

30、给出的结构再加自己的想法，通过定义邻接矩阵，领用普利姆算法选着选着最小值在判断。typedef structVRType adj; ArcCell, AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;int vexnum;intarcnum; MGraph;typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;void PRIM(MGraph G,VertexType

31、u)int i,j,k,s=0;minside closedge;k=LocateVex(G,u);for(j=0;j<G.vexnum;+j) if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; for(i=1;i<G.vexnum;i+) k=minimum(closedge,G); printf("(%s-%s)t%dn",closedgek.adjvex,G.vexsk,closedgei.lowcost); s+=closedgek

32、.lowcost;closedgek.lowcost=0; for(j=0;j<G.vexnum;j+)if(G.arcskj.adj<closedgej.lowcost)strcpy(closedgej.adjvex,G.vexsk);closedgej.lowcost=G.arcskj.adj; printf("%dn",s);4.3函数的调用关系图如图4.1函数调用关系图main()GreatAN()LocateVex()display()minimum()PRIM()图4.1 函数调用关系图 4.4调试分析 (1)遇到的问题 a.依据书上给的定义敲入代码

33、时，无法执行。 解决方法：通过查阅资料，查找相似的例子，通过分析，再看课本不断理解，不断试运行才得以解决。 (2)算法的时间复杂度和空间复杂度 通过对PRIM算法的分析具体方法是假定在进行第k次前已经保留着从T中到T外的每一顶点（共n-k个顶点）的各一条最短边，进行第k次时，首先从这n-k条最短边中，找出一条最最短的边，它就是从T中到T外的所有边中的最短边，假设为（i,j），此步需进行n-k次比较；然后把边（i,j）和顶点j分别并入T中的边集TE和顶点集U中，此时T外只有n-(k+1)个顶点，对于其中的每个顶点t，若（j,t）边上的权值小于已保留的从原T中到顶点t的最短边的权值，则用（j,t）

34、修改之，使从T中到T外顶点t的最短边为（j,t），否则原有最短边保持不变，这样，就把第k次后从T中到T外每一顶点t的各一条最短边都保留下来了，为进行第k+1次运算做好了准备，此步需进行n-k-1次比较。所以，利用此方法求第k次的最短边共需比较2(n-k)-1次，即时间复杂度为O(n-k)。4.5测试结果1.如图4.2测试界面图4.2 2.如图4.3测试结果图4.3 4.6源程序（带注释）#include"stdio.h"#include <limits.h>#include<string.h>#define MAX_VERTEX_NUM 20#def

35、ine MAX_NAME 3#define MAX_INFO 20 #define INFINITY INT_MAXtypedef int VRType;typedef char InfoType;typedef char VertexTypeMAX_NAME;typedef structVertexType adjvex;VRType lowcost;minsideMAX_VERTEX_NUM;void PRIM(MGraph G,VertexType u)/普里姆算法int i,j,k,s=0;minside closedge;/最小权值k=LocateVex(G,u);/k为顶点u在G中的序号for(j=0;j<G.vexnum;j+) /辅助数组初始化if(j!=k)strcpy(closedgej.adjvex,u);closedgej.lowcost=G.arcskj.adj;closedgek.lowcost=0; /将顶点u并入最小生成树集合 printf("最小代价生成树的各条边为:n");for(i=1;i<G.vexnum;i+) k=minimum(closedge,G); printf("