数据结构课程设计报告(集合的交并差运算).doc

《数据结构课程设计报告(集合的交并差运算).doc》由会员分享，可在线阅读，更多相关《数据结构课程设计报告(集合的交并差运算).doc（27页珍藏版）》请在三一办公上搜索。

1、 淮 阴 工 学 院数据结构课程设计报告作 者:学 号：班 级:学 院:专 业:题 目:指导教师： 2016年1月目 录1 课题描述12 系统设计12.1功能模块设计12.1.1基于单链表设计12.1.2基于顺序表设计22.2数据结构设计22.2.1基于单链表设计22.1.2基于顺序表设计32.3算法设计32.3.1基于单链表，顺序表设计33.1菜单设计（基于单链表）53.2源代码设计（基于单链表）53.3菜单设计（基于顺序表）10 3.4源代码设计（基于顺序表）104.1最终结果（基于单链表）204.2最终结果（基于顺序表）20结 论21致 谢22参 考 文 献231 课题描述编制一个能演示

2、执行集合的交、并和差运算的程序。集合元素用小写英文字母，执行各种操作应以对话方式执行。利用单链表表示集合；理解好三种运算的含义2 系统设计2.1功能模块设计2.1.1基于单链表设计（1）节点结构单元模块定义有序表的节点结构；typedef struct LNode/定义结构体类型指针 char data;struct LNode*next;*pointer;（2）有序表单元模块实现有序表的抽象数据类型；readdata(pointer head)初始条件：head是以head为头节点的空链表。操作结果：生成以head为头节点的非空链表。pop(pointer head)初始条件：head是以h

3、ead为头节点的非空链表。操作结果：将以head为头节点的链表中数据逐个输出。（3）集合单元模块实现集合获得抽象数据类型；and(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的并集构成的集合head3。or(pointer head1,pointer head2,pointer head3)初始条件：链表head1、head2、head3已存在操作结果：生成一个由head1和head2的交集构成的集合head3。（4）主程序模块Void main（）初始化；d

4、o接受命令；处理命令；while（“命令”!=“退出”）；2.1.2基于顺序表设计（1）顺序表结构单元模块定义顺序表的结构体；typedef struct /定义SeqList的结构体 DataType listMaxSize; int size ; SeqList;（2）函数单元模块定义各种所需函数；int ListDel( SeqList *L , int i , DataType *x)/顺序表的删除函数int ListGet(SeqList L , int i , DataType *x)/获取顺序表的元素函数void ListFind(SeqList L , DataType x)/

5、顺序表查找元素函数void SelcetSort(SeqList *L ) /顺序表选择排序函数void UnionSet(SeqList mylist1 , SeqList mylist2)/求并集函数void MixedSet(SeqList mylist1 , SeqList mylist2)/求交集元素函数void DiffentSet(SeqList mylist1 , SeqList mylist2) /求差集元素函数（3）主函数单元模块定义主函数；void main() SeqList mylist1 , mylist2;/定义顺序表mylist int i;DataType t

6、emp;ListInitiate( &mylist1);ListInitiate( &mylist2);/初始化两个顺序表2.2数据结构设计2.2.1基于单链表设计定义结构体类型指针，集合采用单链表存储。typedef struct LNode/定义结构体类型指针head1=(pointer)malloc(sizeof(struct LNode); head1-next=NULL; head2=(pointer)malloc(sizeof(struct LNode); head2-next=NULL; head3=(pointer)malloc(sizeof(struct LNode);2.1

7、.2基于顺序表设计typedef struct /定义SeqList的结构体 DataType listMaxSize;int size ;void UnionSet(SeqList mylist1 , SeqList mylist2) /求并集int m, i,j ;DataType x;SeqList Test;ListInitiate( &Test); /定义并初始化2.3算法设计2.3.1基于单链表，顺序表设计 数据输入界面 主菜单界面 结束 集合的差集运算 集合的交集运算 集合的并集运算图2.1系统模块流程图调用输入函数，输入集合信息 显示主菜单 接受用户选择是否合法否 是是否为4否

8、 是 退出系统调用对应选项函数图2.2主菜单流程图 主菜单 用户选择序号是否合法 否 是是否为1 否 是调用并集函数和输出函数 图2.3并集模块流程图求交集与差集的流程图与并集类似。3 详细设计3.1菜单设计（基于单链表）图3.1主界面3.2源代码设计（基于单链表）#include#includetypedef struct LNode/定义结构体类型指针char data;struct LNode*next;*pointer;void readdata(pointer head)/定义输入集合函数pointer p;char tmp;scanf(%c,&tmp);while(tmp!=n)p

9、=(pointer)malloc(sizeof(struct LNode);/为指针P申请存空间p-data=tmp;p-next=head-next;head-next=p;scanf(%c,&tmp);void pop(pointer head)/定义输出集合函数 pop()出栈函数pointer p;p=head-next;while(p!=NULL)printf(%c,p-data);p=p-next;printf(n);void and(pointer head1,pointer head2,pointer head3)/定义集合的并集函数pointer p1,p2,p3;p1=he

10、ad1-next;while(p1!=NULL)/遍历链表head1 p3=(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)/遍历链表head2p1=head1-next;while(p1!=NULL)&(p1-data!=p2-data) p1=p1-next;if (p1=NULL)p3=(pointer)malloc(sizeof(struct LNode);p3-data=p2-dat

11、a;p3-next=head3-next;head3-next=p3;p2=p2-next;void or(pointer head1,pointer head2,pointer head3)/定义集合的交集函数pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;if(p2!=NULL)&(p2-data=p1-data)p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-

12、next=head3-next;head3-next=p3;p1=p1-next;void differ(pointer head1,pointer head2,pointer head3)/定义集合的差集函数pointer p1,p2,p3;p1=head1-next;while(p1!=NULL)p2=head2-next;while(p2!=NULL)&(p2-data!=p1-data)p2=p2-next;if(p2=NULL)p3=(pointer)malloc(sizeof(struct LNode);p3-data=p1-data;p3-next=head3-next;head

13、3-next=p3;p1=p1-next;void main()/主函数int x; printf(输入数据,按回车键结束,第一个集合大于第二个集合)n);pointer head1,head2,head3;head1=(pointer)malloc(sizeof(struct LNode);head1-next=NULL;head2=(pointer)malloc(sizeof(struct LNode);head2-next=NULL;head3=(pointer)malloc(sizeof(struct LNode);head3-next=NULL;printf(请输入集合1：n);re

14、addata(head1);/调用输入集合函数printf(请输入集合2：n);readdata(head2);/调用输入集合函数A:printf(1.并集 2.交集 3.差集 4.结束 x.重新运算n); doprintf(请选择序号n);scanf(%d,&x);switch(x)case 1:printf(两集合的并是n);and(head1,head2,head3);/调用并集函数pop(head3);head3-next=NULL;break;case 2:printf(两集合的交是n);or(head1,head2,head3);/调用交集函数pop(head3);head3-ne

15、xt=NULL;break;case 3: printf(两集合的差是n);differ(head1,head2,head3);/调用差集函数pop(head3);head3-next=NULL;break; case 4:break;default:goto A;while(x!=4);3.3菜单设计（基于顺序表）图3.2主界面3.4源代码设计（基于顺序表）#include #include #include #define MaxSize 100# define EQUAL =typedef char DataType;typedef struct /定义SeqList的结构体DataTy

16、pe listMaxSize; int size ; SeqList; void ListInitiate( SeqList *L) /初始化操作L-size = 0;int ListLength( SeqList L) /获取长度return L.size;int ListInsert( SeqList *L , int i , DataType x) /插入函数的参数分别是SeqList类型的变量，插入位置I，和插入的元素Xint j; if( L-size = MaxSize)printf(顺序表已满，无法插入其他元素！n);return 0;system(pause); else if

17、( iL-size ) printf(参数i不合法！n); return 0; system(pause); else for( j=L-size ; ji ; j-) L-listj = L-listj-1; /将i至size中间的元素依次后移一个单位 L-listi = x; /将x插入指定的位置i L-size +; /L的size，及长度加一 return 1; int ListDel( SeqList *L , int i , DataType *x) /顺序表的删除函数int j;if( L-size = 0)printf(顺序表已无数据可删！n);return 0;system(

18、pause); else if( iL-size-1 ) printf(参数i不合法！n); return 0; system(pause); else *x = L-listi; /保存删除的元素到x中 for( j=i+1 ; jsize-1 ; j+) L-listj-1 = L-listj; /将i+1至size中间的元素依次前移一个单位 L-size -; /L的size，及长度加一 return 1; int ListGet(SeqList L , int i , DataType *x) /获取顺序表的元素函数if( iL.size-1 ) printf(参数i不合法！n); r

19、eturn 0; else *x = L.listi; return 1; void ListFind(SeqList L , DataType x) /顺序表查找元素函数int i; for(i=0 ; iL.size; i+) if(L.listi = x) printf(与查找元素相同的位置为：%d n , i+1 ); continue; if( i = L.size-1 ) printf(没有找到与所查询相同的元素！n);void SelcetSort(SeqList *L ) /顺序表选择排序函数int i,j;DataType temp;int length = ListLeng

20、th( *L);for(i=0; ilisti+1;j=i;while(j -1 & temp listj)L-listj+1 = L-listj;j-;L-listj+1 = temp;void UnionSet(SeqList mylist1 , SeqList mylist2) /求并集int m, i,j ;DataType x;SeqList Test;ListInitiate( &Test); /定义并初始化for(m=0 ; m ListLength(mylist1) ; m+) ListGet(mylist1 , m , &x);ListInsert( &Test , m ,

21、x ); /先将顺序表一中的元素放入顺序表中 for(i=0 ; i ListLength(mylist2) ; i+) ListGet(mylist2 , i , &x);ListInsert( &Test , m , x ); /再将顺序表二中的元素放入顺序表中m+; for(i=0 ; i ListLength(Test) ; i+) /求并集for(j = i+1 ; jListLength(Test); j+) /将顺序表中的相同的元素删除if(Test.listi = Test.listj )ListDel( &Test , j , &x);SelcetSort(&Test);pr

22、intf( The elements of the Union Set are : );for(i=0 ; i ListLength(Test) ; i+) ListGet(Test , i , &x); printf(%c , x); printf(n);void MixedSet(SeqList mylist1 , SeqList mylist2) /求交集元素函数int m, i,j ;DataType x;SeqList mylist;ListInitiate( &mylist); /定义并初始化SeqList Test;ListInitiate( &Test); m=0;for(i=

23、0 ; i ListLength(mylist1) ; i+) /求交集for(j = 0 ; jListLength(mylist2); j+)if(mylist1.listi = mylist2.listj )ListInsert( &Test , m , mylist1.listi ); /将相同的元素放在Test顺序表中m+;continue;for(i=0 ; i ListLength(Test) ; i+) /求并集for(j = i+1 ; jListLength(Test); j+) /将顺序表中的相同的元素删除if(Test.listi = Test.listj )ListD

24、el( &Test , j , &x);SelcetSort(&Test); /对顺序表进行有序化printf( The elements of the Mixed Set are : );for(i=0 ; i Test.size ; i+) ListGet(Test , i , &x); printf(%c , x); printf(n);void DiffentSet(SeqList mylist1 , SeqList mylist2) /求差集元素函数int m=0,n, i,j ;DataType x;SeqList Test;ListInitiate( &Test); for(i=

25、0 ; i ListLength(mylist1) ; i+) n=0;for(j = 0 ; jListLength(mylist2); j+)if(mylist1.listi = mylist2.listj )n+;if(n = 0)ListInsert( &Test , m , mylist1.listi ); /将相同的元素放在Test顺序表中m+;for(i=0 ; i ListLength(Test) ; i+) /求并集for(j = i+1 ; jListLength(Test); j+) /将顺序表中的相同的元素除if(Test.listi = Test.listj )Lis

26、tDel( &Test , j , &x);SelcetSort(&Test); printf( The elements of the Diffrent Set are : );for(i=0 ; i ListLength(Test) ; i+) ListGet(Test , i , &x); printf(%c , x); printf(n);void main()SeqList mylist1 , mylist2; /定义顺序表mylist int i;DataType temp;ListInitiate( &mylist1);ListInitiate( &mylist2); /初始化两

27、个顺序表printf(n%s%sn, EQUAL , EQUAL);printf(n Welcome to the Program of Collection ! n );printf(n%s%sn, EQUAL , EQUAL);printf(n 请输入两个集合 ! n);printf(n 请输入集合1！: );i = 0; while( (temp=getchar() ) != n)if(96temp & temp123)ListInsert( &mylist1 , i , temp); /顺序表一赋值temp;i+;printf(n 输入集合2！: );i = 0; while( (te

28、mp=getchar() ) != n)if(96temp & temp123)ListInsert( &mylist2 , i , temp); /顺序表一赋值temp;i+;printf(n collection one: );for(i=0; imylist1.size; i+)printf(%c , mylist1.listi);printf(nn);printf( collection two: );for(i=0; imylist2.size; i+)printf(%c , mylist2.listi);printf(nn);/调用各个函数printf(n请选择功能:!n);pri

29、ntf(n%s%sn, EQUAL , EQUAL);printf( The number 1 is : 并集.n);printf( The number 2 is : 交集.n);printf( The number 3 is : 差集.n);printf(%s%sn, EQUAL , EQUAL);while(1)int choice;printf(n 请输入您的选择！： n (others exit the programe!): );scanf(%d , &choice);switch(choice)case 1 : UnionSet( mylist1 , mylist2); brea

30、k;case 2 : MixedSet(mylist1 , mylist2); break;case 3 : DiffentSet(mylist1 , mylist2); break;default : exit(0);4 测试4.1最终结果（基于单链表）图4.1结果展示4.2最终结果（基于顺序表）图4.2结果展示结 论通过本次数据结构课程设计，课题实现集合的交并差运算用单链表和顺序表都可以实现，在整个程序方面设计两种方法思路大体相同，唯一不同的在于用单链表比较结果时候得到一个符合结果元素的就放入结果链表中。而顺序表实现结果时候是对结果顺序表按照三种运算法则对表进行删除操作得到最终结果。致 谢

31、在这一次的课程设计中，首先要感谢的是老师，谢谢老师的悉心指导与不厌其烦的为我们修改程序，在做课程设计时老师总能陪在我们身旁，为我们提前开空调，并帮我们调试程序。还告诉我们如何撰写实验报告。更要感谢我们学校-工学院我们系-计算机工程系给了我这个实践机会，让我对自己编写程序的能力有了进一步的认识，为我以后的发展奠定了良好的基础，即锻炼了我的能力，又让我认识到世上无难事，只怕有心人！ 还要谢谢我的同学，谢谢和我做一样题目的同学，还有隔壁的舍友，他们总能随时帮我，随叫随到，帮我查找错误，还给我提供程序运行环境，谢谢他们容忍我的不足。使我对数据结构的出错地方有了更深刻的认识， 当然还要感谢那些参考文献的

32、原作者们，他们给我提供了很大的帮助，让我编程序时顺利了好多，为我省了好多麻烦！谢谢他们，没他们就没这么顺利的代码，感谢他们。此外还有我的父母，还有那些提供过帮助的所有人和，谢谢他们为我做的，最主要的是我的父母，他们为我提供了一个良好的成长环境，一路上有他们的陪伴才幸福快乐，谢谢的他们对我的关心与支持，当然还要谢谢他们在我成功时提醒我：不要骄傲，要继续努力。正因为有了他们的提醒，我才能取得成功谢谢他们，感谢他们！参 考 文 献1 吉根林. 数据结构（C+语言描述）.高等教育，20142 谭浩强. C程序设计学习辅导.北京：清华大学，20103 建洋，于长辉等. C+程序设计工程化。大学，20104 根强. 数据结构（C+版）.2版.北京：中国水利水电，20095 春葆. 数据结构教程.北京：清华大学，2006院 系专 业班 级学 号姓 名课题名称集合的交并差运算所完成的工作在本次数据结构课程设计中，我所做的题目是集合的交并差运算，在存储条件集合和结果集合既用了单链表实现，也用了顺序表实现。在设计过程中由于对集合的三种算法推敲不足，在链表类型以及其指针的设置时出现错误，导致程序低效。所幸最后问题经努力得以解决。顺序表方面对函数方面的设计花的时间较多。总之，最后使得两种设计方法都得到了最终题目要求的结果。成绩评定（五级分制）： 指导教师（签名） 年月日