算法与数据结构.docx

数据结构与算法课程设计 题 目：集合运算问题；计算1 的个数问题；八皇后问 题；构造可以使II个城市 连接的最小生成树问题 TOC \o 1-5 \h \z 摘要 4 \o Current Document 一?集合运算问题 5 \o Current Document 采用类语言定义相关的数据类型 5 算法设计 5 \o Current Document 函数的调用关系图 6 调试分析 6 测试结果： 6 \o Current Document 源程序（带注释） 8 \o Current Document 二计算1的个数问题 13 \o Current Document 采用类语言定义相关的数据类型 13 算法设计 13 \o Current Document 函数的调用关系图 13 调试分析 14 测试结果 14 \o Current Document 源程序（带注释） 15 \o Current Document 三.八皇后问题 17 \o Current Document 采用类语言定义相关的数据类型 17 算法设计 17 \o Current Document 函数的调用关系图 19 调试分析 20 测试结果 21 源程序（带注释） 22 \o Current Document 四?构造可以使N个城市连接的最小生成树问题 25 \o Current Document 1 ?采用类语言定义相关的数据类型 25 算法设计 26 函数的调用关系图 27 调试分析 28 测试结果 29 源程序（带注释） 32 \o Current Document 参考文献 38 致谢 39 木程序主要解决集合运算问题，计算1的个数问题，八皇后问题，n个城市最小生成树问题，设计一 个程序，实现两个集合的并集、交集、差集、显示输出等，要求结果集合中的元索不重复； 实现一个集合的幕集的求解。编写递归程序，返回十进制数N的二进制表示中1的个数编写 计算机可以直接识别的语言是机器语言，而机器语言在计算机中的主要表现形式 是二进制数，为了能够方便这两者之间的转换，为十进制数和二进制树之间搭建 一个桥梁，我们编写了这样一个程序。将十进制数转换为二进制数并返冋十进制 数N的二进制表示中1的个数。程序实现将八个皇后放宜在国际象棋棋盘的无冲突的位 置上的算法，并给出所有的解。给定一个地区的n个城市间的距离网，用Prim算法或Kruskal 算法建立最小生成树，并计算得到的最小生成树的代价 关键词：集合的运算 计算1的个数八皇示最小生成树 ?集合运算问题 设计一个程序，实现两个集合的并集、交集、茅集、显示输出等，要求结果集合屮的元素不 垂复；实现一个集合的幕集的求解。 1 ?采用类语言定义相关的数据类型 typedef int ElemType; typedef struct { //线性表的结构体 ElemType data[MAXSIZE]; int length; }SqList; 算法设计 初始化三个线性表，第一个和第二个线性表分别为两个集合，第三个线性 表为计算后的集合 void InitList(SqList *L){ 〃初始化线性表 L-data=NULL; L-length=0; } 求并集，把集合1和集合2中的元素不重复的放入集合2中 void operate4(SqList *L1,SqList *L2,SqList *L3){ //求并集 int i,j; ElemType res_date; InitList(L3); 〃初始化 L3 for(i=0;iLl-length;i++){ 〃将属于LI同时也屈于L2的元素赋值给L3 res_date=L 1 -data[i]; for(j=0 ;j L2-length;j+4-){ if(res_date==L2-datafj ]) { L3-data[L3-length]=res_date; L3-length++; break; 求交集，把即存在于集合1 乂存在于集合2的元索放入集合3屮 求差集，把存在于集1合1但不存在于集合2的元素放入集合3中 求该集合的任意个元索的组合，所有的组合加上空集即是该集合的冥集 3.函数的调用关系图 4 ?调试分析 a、 输入的数据类型不统一。解决办法：对输入的数据进行筛选和检验 b、 算法的时间复杂度为o(n2) c、 算法的空间复朵度为o(r)2) 5.测试结果: 例:集合］为{1,3, 6, 9,11} 集合 2 为{2, 4, 5, 9, 12} 求并集结果： 求差集结果: F:\CYuYan\bin\v/wtemp,exe i 回 S2 r MENU 1 - 给集合L1和集合L 2添加