算法与数据结构讲解.doc

2014年秋季学期 数据结构与算法 课程设计 题 目：集合运算问题、计算1的个数问题、 方程求解问题、图的基本操作与实现  目 录 摘 要 3 一．集合运算问题 4 1.采用类语言定义相关的数据类型 4 2.算法设计 4 3.函数的调用关系图 4.调试分析 5.测试结果 6.源程序（带注释） 二．计算1的个数问题 3 1.数据结构 3 2.算法设计 4 3.调试分析 4 4.测试结果 4 5.源程序（带注释） 4 三．方程求解问题 5 1.采用类语言定义相关的数据类型 5 2.算法设计 5 3．函数的调用关系图 5 4.调试分析 5 5.测试结果 6 6.源程序（带注释） 6 四.图的基本操作与实现．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．7 1.数据结构．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．.8 2.算法设计．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．1 3.运行结果．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．0 4.源程序（带注释）．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．0 总 结 5 参考文献 6 致 谢 6 摘 要 第一个程序是编写算法实现集合的相关操作包括集合的输入、输出、删除集合中重复的元素、删除、修改，求两个集合的交、并、差。采用单链表对集合进行操作、运行等。需要用到二叉树思想、便利线性表和双重循环结构等完成问题。 第二个程序是递归结构计算1的个数问题，共分为两种情况，奇数情况和偶数情况。 第三个程序为方程求解问题，用c语言实现方程A5+B5+C5+D5+E5=F5刚好有一个满足0≤A≤B≤C≤D≤E≤F≤75的整数解的问题。也可以将生活中的实际问题转换成此类方程的求解，这样进行程序的迭代和功能的更新，就可以实现更多未知数、更高次、更多解的方程求解问题，和涉及此类方程求解的实际问题。 第四个程序为图的一些基本操作，内容包括图的存储结构、图的深度优先遍历，广度优先遍历，图节点的度数等等。 关键词： 集合，单链表，递归，替换，连通图 定义一个结构体存储结构，用来生成求幂集的二叉树只在求幂集函数内使用 typedef struct //根节点结构体（幂集使用） { int data[MAX]; int length; }root; 定义一个二维数组，用来存储节点选择情况，其第一个下标表示是左孩子还是右孩子，第二个表示节点当前所处的层数 int c[2][MAX]; //c构造数据池 1.并集：用两个循环结构为并集赋值，最后进行重复元素检查（check（））。 for(i=0;in;i++) //A集合赋值 { c[i]=a[i]; } for(i=0;i=m;i++) //B集合赋值 { c[n+i]=b[i]; } k=n+m; //集合大小 k=check(c,k); //集合重复元素检查 2.利用双重循环判断元素是否在A、B里面均存在，存在则赋值在C里面 for(i=0;i=n;i++) //在A里面检查 for(j=0;j=m;j++) //在B里面检查 { if(a[i]==b[j]) //元素在A和B里面均出现 { c[k]=a[i]; //赋值 k++; //C集合容量加1