《数据结构设计说明书1》由会员分享，可在线阅读，更多相关《数据结构设计说明书1（32页珍藏版）》请在金锄头文库上搜索。
1、*实践教学*大学计算机与通信学院2015年春季学期数据结构与算法 课程设计题 目： 集合运算问题 递归替换问题 跳马问题 长整数运算问题 专业班级：计算机科学与技术四班姓 名： * 学 号： 指导教师： 成 绩： 目 录摘 要3一、集合运算问题41.采用类语言定义相关的数据类型42.算法设计43.函数的调用关系图74.调试分析85.测试结果96.源程序（带注释）10二、跳马问题131.采用类语言定义相关的数据类型132.算法设计133.函数的调用关系图144.调试分析155.测试结果156.源程序（带注释）16三、长整数运算问题181.采用类语言定义相关的数据结构182.算法设计183.函数的
2、调用关系图184.调试分析195.测试结果206.源程序（带注释）20四、递归替换问题241.采用类语言定义相关的数据类型242.算法设计243.函数的调用关系图254.调试分析255.测试结果266.源程序（带注释）26总 结29参考文献30致 谢31摘 要在此次的课程设计中，我所完成的项目主要有四个。分别是：(1)集合运算问题。设计一个程序，实现两个集合的交集、并集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解；（2）递归替换问题。编写程序，扩展C/C+源文件中的#include指令（以递归的方式）。请以文件名的内容替换形如括号内的代码行(#include“fil
3、ename”）；（3）跳马问题。要求在64个国际棋盘格子，任意位置放一个马，如何不重复地把格子走完。（4）长整数运算问题。设计程序，实现两个任意长的整数的相加、减、乘运算问题。这些程序主要功能是加深我们对算法与数据结构中存储，线性表和栈的理解。让我们对算法与数据结构有个更深刻的认识。关键字：集合运算、递归替换、长整数、跳马一、 集合运算问题设计一个程序，实现两个集合的交集、并集、差集、显示输出等，要求结果集合中的元素不重复；实现一个集合的幂集的求解。1. 采用类语言定义相关的数据类型定义一个单链表作为实现该问题的数据结构。创建的链表都是由一个个结点组成，由于结点的不同，组成的链表也不同。由于每
4、一个结点有一个数据域和一个指针域，所以可以将结点结构体定义为typedef struct LNode /定义结构体指针类型char data;struct LNode *next;*pointer;定义一个结构体来实现数组的动态过程，用来求幂集，只在求幂集函数内使用。typedef int Elemtype;typedef struct/定义一个结构体来实现数组的动态过程Elemtype *elem;/指针，指向一个Elemtype类型的指针int length;/定义数组的长度int listsize;/定义数组的初始规模SqList;/定义程序中所使用的数据结构为线性表2. 算法设计1.求
5、并集算法。把集合head1的元素复制到并集集合head3中,然后比较head2与head1，将集合head2中在集合head1中没有的元素在插入到并集集合head3中。void and(pointer head1,pointer head2,pointer head3)/定义集合并集函数 pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)/先把集合head1中的所有元素赋给集合head3p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-nex
6、t=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-next=head3-next;head3-next=p3;p2=p2-next;/下一个元素2.
7、求交集算法。循环使集合head1中一个元素与集合head2中所有元素比较，将集合head1与集合head2中相等的元素插入到交集集合head3中。void or(pointer head1,pointer head2,pointer head3)/定义集合交集函数 pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)/循环使集合head1中一个元素与集合head2中所有元素比较p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;if(p2!=NULL)&(p2-data=p1-data)/
8、若集合head1与集合head2存在相等的元素，则将该元素插入到交集集合head3中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;/下一个元素3.求差集算法。循环使集合head1中一个元素与集合head2中所有元素比较, 将集合head1中不与head2中任何元素相等元素插入到差集集合head3中。void differ(pointer head1,pointer head2,pointer head3) /定义集合差集函数 pointer
9、p1,p2,p3;p1=head1-next;while(p1!=NULL)/循环使集合head1中一个元素与集合head2中所有元素比较p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;if(p2=NULL)/head2中元素不与head1中任何元素相等，将head2中此元素插入到并集集合head3中p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;/下一个元素4.求幂集算法。
10、i的初始化值为1，先判断i是否大于A的长度，若大于则输出B，否则取A中的第i个位置的值，取B的长度k，将A中第i个位置的值插入到B中k后面，把i加1在次执行本程序当ilenth(A)时递归结束。void GetPowerSet(int i,SqList A,SqList &B)/得到幂集的函数int x,k;if(iA.length)/即是所有的值都被走完了一遍，生成了集合的一个子集，因此递归结束Output(B);/输出一个子集elsex=GetElem(A,i);/从A表中第i位置返回元素值并赋给xk=B.length;/B表的长度赋给kListInsert(B,k+1,x);/在B表第k
11、+1位置插入xGetPowerSet(i+1,A,B);/递归调用函数ListDelete(B,k+1,x);/在B表第k+1位置删除xGetPowerSet(i+1,A,B);/递归调用函数3. 函数的调用关系图程序主要使用四个函数：1. or(head1,head2,head3) 求交集函数；2. add(head1,head2,head3) 求并集函数；3. differ(head1,head2,head3) 求差集函数；4. GetPowerSet(1,A,B) 求幂集函数。主函数分别调用已写好的交集、并集、差集及幂集函数，通过输出函数输出相应的结果（幂集函数除外），如下图所示： 图1
12、.函数调用关系图4. 调试分析a. 调试中遇到的问题及问题的解决方法（1）由于对集合的两种运算的算法推敲不足，在链表类型及其尾指针的设置时出现错误，导致程序低效。 刚开始时曾忽略了一些变量参数的标识”&”，使调试程序浪费时间不少。今后应重视确定参数的变量和赋值属性的区分和标识。（2）开始时输入集合后，程序只能进行一次运算，后来加入switch语句,成功解决了这一难题。 （3）起初在调用求求并集函数时，并未新建一链表，在原链表上进行修改，导致原链表的data改变，随之调用的求差集函数输不出正确结果，通过在每个函数中新建一链表并返回输出，很好地解决了问题。（4）对链表中为NULL的结点要特别注意不
13、能对其进行删除等操作。b. 算法的时间复杂度和空间复杂度设集合A的长度为n,集合B的长度为m。1.求交集算法：时间复杂度是O(n*n*m)(n=m)，空间大小是链表的长度n+m；2.求并集算法：时间复杂度是O(n*m)，空间大小是链表的长度n+n+m；3.求差集算法：时间复杂度是O(n*m)，空间大小是链表的长度n+n+m；4.求幂集算法：时间复杂度是O（n2），空间大小是链表的长度n。5. 测试结果设输入集合A=1,3,4,5,7,9，集合B=1,2,4,6,8,9，幂集运算集合A=1，2,3，运行结果如下所示：1.根据提示输入两个集合，分别以回车键结束，如下图所示： 图2.输入集合测试图2.输入相应的运算对应的数字分别进行相应的运算，输入0退出，如下图所示：图3.集合运算测试图6. 源程序（带注释）#include#include#include#define LIST_INIT_SI
