*实践教学*大学计算机与通信学院2015 年春季学期数据结构与算法 课程设计题 目： 集合运算问题 递归替换问题 跳马问题 长整数运算问题 专业班级：计算机科学与技术四班姓 名： * 学 号： 指导教师： 成 绩： 目 录摘 要 .3一、 集合运算问题 .41. 采用类语言定义相关的数据类型 .42. 算法设计 .43. 函数的调用关系图 .74. 调试分析 .85. 测试结果 .96. 源程序（带注释） .10二、 跳马问题 .131. 采用类语言定义相关的数据类型 .132. 算法设计 .133. 函数的调用关系图 .144. 调试分析 .155. 测试结果 .156. 源程序（带注释） .16三、 长整数运算问题 .181. 采用类语言定义相关的数据结构 .182. 算法设计 .183. 函数的调用关系图 .184. 调试分析 .195. 测试结果 .206. 源程序（带注释） .20四、 递归替换问题 .241. 采用类语言定义相关的数据类型 .242. 算法 设计 .243. 函数的调用关系图 .254. 调试分析 .255. 测试结果 .266. 源程序（带注释） .26总 结 .29参考文献 .30致 谢 .313摘 要在此次的课程设计中，我所完成的项目主要有四个。分别是：(1)集合运算问题。设计一个程序，实现两个集合的交集、并集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解；（2）递归替换问题。编写程序，扩展 C/C+源文件中的#include 指令（以递归的方式） 。请以文件名的内容替换形如括号内的代码行(#include “filename”） ；（3）跳马问题。要求在 64 个国际棋盘格子，任意位置放一个马，如何不重复地把格子走完。 （4）长整数运算问题。设计程序，实现两个任意长的整数的相加、减、乘运算问题。这些程序主要功能是加深我们对算法与数据结构中存储，线性表和栈的理解。让我们对算法与数据结构有个更深刻的认识。关键字：集合运算、递归替换、长整数、跳马4一、 集合运算问题设计一个程序，实现两个集合的交集、并集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解。1. 采用类语言定义相关的数据类型定义一个单链表作为实现该问题的数据结构。创建的链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。由于每一个结点有一个数据域和一个指针域，所以可以将结点结构体定义为 typedef struct LNode /定义结构体指针类型char data;struct LNode *next;*pointer;定义一个结构体来实现数组的动态过程，用来求幂集，只在求幂集函数内使用。typedef int Elemtype;typedef struct/定义一个结构体来实现数组的动态过程Elemtype *elem;/指针，指向一个 Elemtype 类型的指针int length;/定义数组的长度int listsize;/定义数组的初始规模SqList;/定义程序中所使用的数据结构为线性表2. 算法设计1.求并集算法。把集合 head1 的元素复制到并集集合 head3 中,然后比较 head2与 head1，将集合 head2 中在集合 head1 中没有的元素在插入到并集集合 head3中。void and(pointer head1,pointer head2,pointer head3)/定义集合并集函数 pointer p1,p2,p3;5p1=head1-next;while(p1!=NULL)/先把集合 head1 中的所有元素赋给集合 head3p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;p2=head2-next;while(p2!=NULL)/检查集合 head2 中的元素是否与集合 head1 中的元素相等p1=head1-next;while(p1!=NULL)&(p1-data!=p2-data)p1=p1-next;if(p1=NULL)/head2 中元素不与 head1 中任何元素相等，将 head2 中此元素插入到并集集合 head3 中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p2-data;p3-