《算法与数据结构课程设计说明书》由会员分享，可在线阅读，更多相关《算法与数据结构课程设计说明书（34页珍藏版）》请在金锄头文库上搜索。
1、 目录目录 摘 要.3 一求素数问题.4 1.1 采用类 C 语言定义相关的数据类型.4 1.2 算法设计4 1.3 函数的调用关系图5 1.4 调试分析5 1.5 测试结果6 1.6 源程序（带注释）.7 二猴子摘桃子问题.9 2.1 采用类 C 语言定义相关的数据类型9 2.2 算法设计9 2.3 函数调用关系图10 2.4 调试分析11 2.5 测试结果11 2.5 源程序（带注释）13 三跳马问题.16 3.1 采用类语言定义相关的数据类型16 3.2 算法设计16 3.3 函数的调用关系图17 3.4 调试分析17 3.5 测试结果18 3.6.源程序（带注释）.19 四.可以使 n
2、 个城市连接的最小生成树.25 4.1 采用类 C 语言定义相关的数据类型25 4.2 算法设计25 4.3 函数的调用关系图27 4.4 调试分析27 4.5 测试结果28 4.6 源程序（带注释）29 总 结.32 参考文献.33 致 谢.34 3 摘摘 要要 素数问题主要是运用数据逻辑结构。采用指针数组，算法进行求解。猴子吃 桃子桃子问题主要运用了数据的逻辑结构，数据的存储结构。采用数组，连式存 储结构和递归调用进行。跳马问题要求在 8*8 的 64 个国际象棋格子,任意位置放 一个马,如何不重复地把格子走完。给定一个 8*8 的棋盘，起始点在某坐标处， 要求求出有多少种方法，可以不重复
3、的遍历棋盘上所有的点规则：1.马走日字 2. 走过的点就不能再走。构造可以使 n 个城市连接的最小生成树问题给定一个地区 的 n 个城市间的距离网,城市间的距离网采用邻接矩阵表示,邻接矩阵的存储结构 定义, 关键词：数据结构；关键词：数据结构；邻接矩阵；类邻接矩阵；类 C C 语言；数组；普里姆算法语言；数组；普里姆算法 4 一求素数问题一求素数问题 埃拉托色尼筛法（Sieve of Eratosthenes）是一种用来求所有小于 N 的素数的 方法。从建立一个整数 2N 的表着手，寻找 i的整数，编程实现此算法，并 讨论运算时间。 1.11.1 采用类采用类 C C 语言定义相关的数据类型语
4、言定义相关的数据类型 定义一个线性表顺序存储结构，用来求所有小于 N 的素数 typedef int DataType;/数据类型 typedef struct DataType datamaxsize;定义一个一维数组 int length;/线性表中实际元素的个数 Seqlist; 1.21.2 算法设计算法设计 顺序存储结构是存储结构类型中的一种，该结构是把逻辑上相邻的节点存储在 物理位置上相邻的存储单元中，结点之间的逻辑关系由存储单元的邻接关系来体 现。本程序通过建立一个指针数组为其分配一个空间，在通过埃拉托色尼筛法通 过判断将其输出。 for( m1=1;m1 #include #d
5、efine maxsize 200 #define FALSE 0 typedef int DataType; typedef struct DataType datamaxsize; int length; Seqlist;/结点结构 int sushu(DataType i)/判断是否为素数 int m; if(i=1) return 0; for(m=2;mL.length ) return FALSE; printf(“1 至 m 之间的素数从小到大分别为:n“); for(i=1;il2=(int *)malloc(MAX2*sizeof(int); if(s2-l2=NULL) p
6、rintf(“ stack2 initial fail!n“); 3.递归函数解决： 递归过程一般通过函数或子过程来实现。递归方法：在函数或子过程的内部， 直接或者间接地调用自己的算法。使用 if 函数控制是否调用函数本身。桃子数等 与一这说明第九天吃了一个桃子函数便可以结束。如果桃子数不为一则一直调用 函数本身知道调用结束。 void peach_digui2(int n2,int i2) if(i2=days2) peach_digui2(n2,i2); 2.32.3 函数调用关系图函数调用关系图 1.如图 2.1 函数调用关系图 11 main() menu() peach_lianzh
7、a()peach_shuzu()peach_digui()exit() 图 2.1 函数调用关系图 2.42.4 调试分析调试分析 (1)遇到的问题 刚开始时，每一个算法我都是单独的一个程序来实现，基本上没有出现问 题，在将所有方法、程序做好后，再将所有程序集合在一起，利用主函数的菜单 来分块调用以实现题目要求。在整合过程中，出现了一些编辑错误，但是都是比 较小的错误，很快就找出来了，应该说整个程序做的过程还是比较顺利的。 (2)算法的时间复杂度和空间复杂度 a.时间复杂度： (1)数组解决：O(1) 2)链栈解决：O(n) (3)递归解决：O(n) b.空间复杂度： (1)数组解决：O(n)
8、 (2)链栈解决：O(n) (3)递归解决：O(n) 2.52.5 测试结果测试结果 2.如图 2.2 测试界面操作 12 图 2.2 3.如图 2.3 数组测试结果操作 图 2.3 4.图 2.4 链栈测试结果操作 图 2.4 5 如图 2.5 递归测试结果 13 图 2.5 2.52.5 源程序（带注释）源程序（带注释） #include #include #include #define MAX 50 #define days 10 #define ERROR 0 #define TURE 1 void peach_shuzu2( ) int i2=0, j2=0 ,peach_tal2
9、10; peach_tal2days2-1=1;/最后一天桃子数 i2=days2; while(i20)/判断天数是否符合要求 peach_tal2j2=2*(peach_tal2i2+1);/该天桃子数 i2=i2-1; j2=i2-1; 14 void pop2(stack2 *s2,int else s2-t2-; num2=*s2-t2; void peach_lianzhan2(stack2 *s2) int i2=0,num2=0; push2(s2,1);/进行第一天运算 i2+; for(i2;i2 #include #define MAXNUM 8 /横纵格数最大值 #de
10、fine INVALIDDIR - 1 /无路可走的情况 #define MAXLEN 64 /棋盘总格数 #define MAXDIR 8 /下一步可走的方向 typedef struct int x; /表示横坐标 int y; /表示纵坐标 int direction; /表示移动方向 HorsePoint; HorsePoint ChessPathMAXLEN; /模拟路径栈 int count; /入栈结点个数 图 3.3 测试结果 20 int ChessBoardMAXNUMMAXNUM; /标志棋盘数组 void Initial() /棋盘初始化的数组 int i,j; for
11、(i=0;i=MAXNUM|positon.y=MAXNUM|positon.xdirection=parent-direction+; /上一结点能走的方向 for(i=parent-direction;ix+tryxi; /试探新结点的可走方向 newpoint.y=parent-y+tryyi; if(newpoint.x=0 /上一结点可走的方向 22 ChessBoardnewpoint.xnewpoint.y=1; /标记已走过 return newpoint; parent-direction=INVALIDDIR; return newpoint; void CalcPoint
12、(HorsePoint hh ) /计算路径函数 HorsePoint npositon; HorsePoint *ppositon; Initial(); /调用初始化函数 ppositon= /调用输入初始点函数 PushStack(*ppositon); while(!(count=0|count=MAXLEN) /当路径栈不满或不空时 ppositon= /指针指向栈 npositon=GetNewPoint(ppositon); /产生新的结点 if(ppositon-direction!=INVALIDDIR) /可以往下走 ChessPathcount-1.direction=p
13、positon-direction; PushStack(npositon); else PopStack(); void PrintChess() /以 8*8 矩阵的形式输出运行结 果 23 int i,j; int stateMAXNUMMAXNUM; /stateij为棋盘上（i,j）点 被踏过的次序 int step=0; /行走初始化 HorsePoint positon; count=MAXLEN; if(count=MAXLEN) /当棋盘全部走过时 for(i=0;i #include #define MAX_VERTEX_NUM 20 #define MAX_NAME 3
14、#define MAX_INFO 20 #define INFINITY INT_MAX typedef int VRType; typedef char InfoType; typedef char VertexTypeMAX_NAME; typedef struct VertexType adjvex; VRType lowcost; minsideMAX_VERTEX_NUM; void PRIM(MGraph G,VertexType u)/普里姆算法 30 int i,j,k,s=0; minside closedge;/最小权值 k=LocateVex(G,u);/k 为顶点 u
15、在 G 中的序号 for(j=0;jG.vexnum;j+) /辅助数组初始化 if(j!=k) strcpy(closedgej.adjvex,u); closedgej.lowcost=G.arcskj.adj; closedgek.lowcost=0; /将顶点 u 并入最小生成树集合 printf(“最小代价生成树的各条边为:n“); for(i=1;iG.vexnum;i+) k=minimum(closedge,G); printf(“(%s- %s)t%dn“,closedgek.adjvex,G.vexsk,closedgei.lowcost); s+=closedgek.lowcost;/最小边求和 closedgek.lowcost=0; for(j=0;jG.vexnum;j+) if(G.arcs
