兰州理工大学算法课设论文.pdfVIP

******************* 实践教学 ******************* 兰州理工大学 计算机与通信学院 2015 年秋季学期 算法与数据结构课程设计 题 目：计算 1 的个数问题;方程求解 问题; 图的基本操作与实现 专业班级：13 级信息与计算科学1 班 姓 名： 李 伟 学 号： 指导教师： 李 睿 成 绩： 目 录 摘 要 3 一．计算1 的个数问题 4 1.采用类语言定义相关的数据类型4 2.算法设计4 3.函数调用关系图5 4.调试分析5 5.测试结果6 6.源程序（带注释）7 二．解方程问题 9 1.采用类语言定义相关的数据类型9 2.算法设计9 3.函数的调用关系图10 4.调试分析10 5.测试结果 11 6.源程序（带注释） 11 三．图的基本操作与实现 12 1.采用类语言定义相关的数据类型12 2.算法设计14 3.函数的调用关系图15 4.调试分析15 5.测试结果16 6.源程序（带注释）17 总 结 24 参考文献 25 致 谢 26 摘 要 这次算法与数据结构课设的三个题目分别是：1、计算1 的个数问题2、解方 程问题3、图的基本操作与实现。 对于问题一，它主要采用直接递归的方法实现了统计十进制转换为二进制后 所含 “1”的个数的统计，在这个问题的基础上改程序还可以统计负整数转换为二 进制后所含“1”的个数。分析了它的空间复杂度和最坏时间复杂度。 对于问题二，主要采用六重循环求解，这里计算了非零解为 （F=76,E=67,D=47,C=46,B=43,A=19 ）。通过分析它的最坏时间复杂度和空间复 杂度，与实际计算相符合。 对于问题三，首先，建立了以邻接表为存储结构的无向图图，并设计了统计 每个节点度的算法；然后，通过查阅相关资料，建立了 BFS 和 DFS 遍历算法， 并建立了两个实例进行检验，遍历结果与理论结果相符；最后，采用DFS 遍历算 法实现了判断无向图是否连通的算法，该算法通过了测试。并分析了相应算法的 时间复杂度和空间复杂度。 关键词：直接递归；BFS ；DFS ；算法效率 3 一．计算1 的个数问题 编写递归程序，返回十进制数N 的二进制表示中1 的个数。 1.采用类语言定义相关的数据类型 (1)抽象数据结构 这里定义的抽象数据结构为顺序栈如下： Typedef struct { Int Data[Stack_Size]; Int top; } 为了记录十进制N 转化成二进制后中所含“1”的个数，定义了静态变量如下： static int count=0; (2)相应操作函数 十进制转换函数为void Tranfrom （int n）。 2.算法设计 第一步：输入十进制整数N,并将它传递给Tranfrom()函数； 第二步：判断N 是否为0，若为零，返回记录“1”个数的静态变量count 停止 计算；否则进入第三步； 第三步：计算m=N%2 并判断是否等于“1”，若等于，则执行cou