集合运算_c语言课程设计报告

YAYA_echo 贡献于2017-01-08

作者 wj  创建于2017-01-06 18:57:00   修改者何洁  修改于2017-01-06 18:57:00字数6992

文档摘要:
关键词:

东莞理工学院课程设计 东 莞 理 工 学 院 课程设计报告 课程 程序设计基础 题目 集合运算 院系名称 计算机学院 班 级 信息与计算科学2班 学 号 201441410245 学生姓名 何洁 指导教师 彭华 时 间 2015年7月3日 东莞理工学院课程设计 1 问题要求及任务描述 1.1 题目要求 设有两个用单链表表示的集合A、B,其元素类型是int且以非递减方式存储,其头结点分别为a、b。要求下面各问题中的结果集合同样以非递减方式存储,结果集合不影响原集合。 1.2 主要任务 ⑴ 编写集合元素测试函数IN_SET,如果元素已经在集合中返回0,否则返回1; ⑵ 编写集合元素输入并插入到单链表中的函数INSERT_SET,保证所输入的集合中的元素是唯一且以非递减方式存储在单链表中; ⑶ 编写集合元素输出函数,对建立的集合链表按非递增方式输出; ⑷ 编写求集合A、B的交C=A∩B的函数,并输出集合C的元素; ⑸ 编写求集合A、B的并D=A∪B的函数,并输出集合D的元素; ⑹ 求集合A与B的对称差E=(A-B)∪(B-A) 的函数,并输出集合D的元素; ⑺ 设计一个菜单,具有输入集合元素、求集合A、B的交C、求集合A、B的并D、求集合A与B的对称差E、退出等基本的功能。 测试数据:由读者自定,但集合A、B的元素个数不得少于16个。 2 解决问题的主要思路和方法 2.1 关键问题 建立两个链表来存储集合A与集合B,同时建立一个复制链表的函数以保证原始链表不被改变,通过对链表的合并,排序,比较,删除等功能来实现集合运算。 2.2 拟采用解决问题的方法 1. 建立如下结构体 struct set { int data; 东莞理工学院课程设计 struct set *next; } 2.采用动态申请内存建立链表的方法,完成链表的建立与输入 3.为完成后续功能,对链表的数据进行排序 2.3 主要算法和处理流程图 关键的数据流程图 创建链表 Create() 复制链表 Copy() 东莞理工学院课程设计 递减排序 Export() 递减输出 Output() 东莞理工学院课程设计 检查重复 IN_SET() 删除重复元素 Delete() 输出 Print() 东莞理工学院课程设计 插入元素 Insert_set() 集合交集 Mergelink() 东莞理工学院课程设计 集合并集 Union() 东莞理工学院课程设计 集合对称差 SysmmetricDifference() 东莞理工学院课程设计 主函数 东莞理工学院课程设计 3 程序实现 3.1 程序实现时应考虑的问题 1.进行集合运算前需要先将原始链表复制给一个新的链表,再用新链表代替原始链表来进行集合运算,这样原始链表才不会被改变; 2.需先创建链表来存储集合A与B的数据才可以进行集合运算; 3.选择开关结构包容所有函数 4.必须要保证该被调函数已被声明或者已出现在需调用的函数之前,才可以实现函数调用; 5.指针必须要初始化。 3.2 主要源代码及说明 #include #include struct set { int data;/*集合的元素大小*/ struct set *next;/*指向下一个节点的指针*/ }; /*函数功能:创建集合链表*/ struct set *Create(int num) { struct set *head,*h1,*h2;/*head头指针,h1指向当前节点的指针,h2指向新的节点的指针*/ int i; head=(struct set *)malloc(sizeof(struct set)); if(head==NULL) return NULL; h1=head; printf("请输入%d个元素:\n",num); for(i=0;idata); h1->next=h2; h1=h2; } h1->next=NULL;/*代表整个链表的尾部*/ return head; } /*函数功能:为不改变原始链表,在调用链表前先复制原始链表到一个新链表中*/ struct set *Copy(struct set *head) { struct set *p,*q,*temp; struct set *h=(struct set *)malloc(sizeof(struct set)); h->next=NULL; if(head->next!=NULL) { p=head; q=h; while(p->next!=NULL) { p=p->next; temp=(struct set *)malloc(sizeof(struct set)); temp->data=p->data; q->next=temp; q=temp; } q->next=NULL; } return h; } /*函数功能:对集合链表进行递减排序存储*/ 东莞理工学院课程设计 struct set *Export(struct set *head) { int temp;//临时变量 struct set *p,*q,*r=head->next;//指针p,q用来排序,指针r用来输出 if(r!=NULL) { for(p=head->next;p->next!=NULL;p=p->next)//对整个链表进行非递减的排序 for(q=p->next;q!=NULL;q=q->next) { if((p->data)>(q->data)) { temp=p->data; p->data=q->data; q->data=temp; } } } return head; } /*输出函数:以递增的形式输出集合元素*/ struct set *Output(struct set *head) { int temp;//临时变量 struct set *p,*q,*put=head->next;//指针p,q用来排序,指针put用来输出 if(put==NULL) { printf("空集!"); } if(put!=NULL) { for(p=head->next;p->next!=NULL;p=p->next)//对整个链表进行非递增的排序 东莞理工学院课程设计 for(q=p->next;q!=NULL;q=q->next) { if((p->data)<(q->data)) { temp=p->data; p->data=q->data; q->data=temp; } } } while(put!=NULL)//输出链表元素 { printf("%d ",put->data); put=put->next; } } /*测试函数:函数功能:检查元素是否重复*/ int IN_SET(struct set *q) { struct set *p1,*p2; p1=q; while(p1!=NULL) { for(p2=(p1->next);p2!=NULL;p2=(p2->next)) { if(p1->data==p2->data) { return 0; } } p1=p1->next; 东莞理工学院课程设计 } return 1; } //函数功能:删除链表中重复的节点 struct set *Delete(struct set *head) { struct set *p,*q,*r; p=head->next; while(p) { q=p; while(q->next) { if(q->next->data==p->data)//重复的则被删掉 { r=q->next; q->next=r->next; free(r); } else { q=q->next; } } p=p->next; } return head; } /*输出函数*/ void Print(struct set *head) 东莞理工学院课程设计 { struct set *p = head->next; while(p!=NULL) { printf("%d ",p->data); p = p->next; } } /*函数功能:插入新的元素到集合中*/ struct set *Insert_set(struct set **linkp,char x) { struct set *p,*pr,*h; int k,new_data; label3:printf("请输入在%c中插入的元素:",x); scanf("%d",&new_data); while((p=*linkp)!=NULL&&p->datanext; } pr=(struct set *)malloc(sizeof(struct set));//为新节点分配内存,并把新值存储到新节点中,如果内存失败,函数返回一个NULL指针 if(pr==NULL) return NULL; pr->data=new_data; pr->next=p;//在链表中插入新节点,并返回一个头指针 *linkp=pr; h=*linkp; k=IN_SET(h); if(k==0) { printf("集合元素具有唯一性,您的输入重复了!请重新输入!\n"); 东莞理工学院课程设计 goto label3; } return h; } /*函数功能:求出集合A与B的交集C*/ struct set *Mergelink(struct set *head1,struct set *head2) { struct set *head3,*p,*q,*x,*y; int i=0; head3=(struct set *)malloc(sizeof(struct set)); x=head3; for(p=head1->next;p!=NULL;p=p->next) { for(q=head2->next;q!=NULL;q=q->next) { if(p->data==q->data) { y=(struct set *)malloc(sizeof(struct set)); y->data=p->data; x->next=y; x=y; i++; } } q=head2->next; } x->next=NULL; return (head3); } /*函数功能:求出集合A、B的并集D*/ 东莞理工学院课程设计 struct set *Union(struct set *head1,struct set *head2) { int i; struct set *head3,*p,*q,*m,*n; head3=(struct set *)malloc(sizeof(struct set));//申请新节点的内存 m=head3; for(p=head2;p!=NULL;p=p->next) { for(q=head1;q!=NULL;q=q->next) { if(p->data==q->data)//若两个元素相同,则为假;若两个元素不同,则为为真 { i=0; break; } else { i=1; } } if(i==1) { n=(struct set *)malloc(sizeof(struct set));//申请新节点的内存 if(n!=NULL) //申请内存成功 { n->data=p->data; m->next=n; m=n; } } } m->next=head1->next; return (head3); 东莞理工学院课程设计 } /*函数功能:集合A与集合B的对称差*/ struct set *SysmmetricDifference(struct set *h1,struct set *h2) { struct set *head3,*head1,*head2,*p,*q,*x,*y; head1=Mergelink(h1,h2); head2=Union(h1,h2); x=(struct set *)malloc(sizeof(struct set)); head3=x; if(head1->next==NULL)//如果交集是空集则返回并集 { return(head2); } for(q=head2->next;q!=NULL;q=q->next) { for(p=head1->next;p!=NULL;p=p->next) { if(p->data==q->data)//元素相同就退出循环 break; if(p->next==NULL)//元素不同就将该节点连在新的头指针后 { y=(struct set *)malloc(sizeof(struct set)); y->data=q->data; x->next=y; x=y; } } } x->next=NULL; if(head3->next==NULL)//如果交集和并集的元素相同,则对称差是空集。 { printf("对称差是空集!\n"); 东莞理工学院课程设计 exit(0); } else return(head3); } //程序菜单 int Menu() { int i; printf("\n\n >>>>>>欢迎进入到集合运算系统<<<<<<\n"); printf("================================================\n"); printf(" 1.插入新的元素到集合中\n"); printf(" 2.输出集合A与B的交集\n"); printf(" 3.输出集合A与B的并集\n"); printf(" 4.输出集合A与B的对称差集\n"); printf(" 0.退出系统\n"); printf("================================================\n\n"); printf("请输入您的选择: "); scanf(" %d",&i); return i; } //主函数 int main(void) { struct set *a,*b,*c=NULL,*d=NULL,*e=NULL;//分别代表集合A,B,交集C,并集D,对称差E struct set *a1,*b1;//代表集合A与B的临时链表 int n,m,k1,k2,k4,k; char x; printf("***********请先输入集合A与集合B的元素!**********\n\n"); 东莞理工学院课程设计 printf("您准备输入几个元素到集合A中? "); scanf("%d",&n); label1:a=Create(n);//创建链表 k1=IN_SET(a);//检查元素是否重复 if(k1==0) { printf("集合元素具有唯一性,您的输入重复了!请重新输入!\n"); goto label1; } Export(a);//非递减排序存储 printf("集合A为: "); Print(a);//输出集合元素 printf("\n"); printf("您准备输入几个元素到集合B中? "); scanf("%d",&m); label2:b=Create(m);//创建链表 k2=IN_SET(b);//检查元素是否重复 if(k2==0) { printf("集合元素具有唯一性,您的输入重复了!请重新输入!\n"); goto label2; } Export(b);//非递减排序存储 printf("集合B为: "); Print(b);//输出集合元素 printf("\n\n*******恭喜!已成功输入集合A与集合B的元素!*******\n"); k=Menu();//输出集合运算系统目录及返回用户选项 while(k!=0) { switch (k) { case 1:a1=Copy(a);//复制原始链表 b1=Copy(b);//复制原始链表 printf("请选择将元素插入到集合A中还是集合B中?\n"); 东莞理工学院课程设计 scanf(" %c",&x); if(x=='a'||x=='A') { Insert_set(&a1,x);//插入新元素 printf("插入元素后的集合A: "); Output(a1);//非递增输出集合元素 printf("\n\n"); } else if(x=='b'||x=='B') { Insert_set(&b1,x);//插入新元素 printf("插入元素后的集合B: "); Output(b1);//非递增输出集合元素 printf("\n\n"); } break; case 2:a1=Copy(a); b1=Copy(b); printf("集合A与集合B的交集为:"); c=Mergelink(a1,b1);//计算集合的交集 Output(c); printf("\n\n"); break; case 3:a1=Copy(a); b1=Copy(b); printf("集合A与集合B的并集为:"); d=Union(a1,b1);//计算集合运算的并集 Output(d); printf("\n\n"); break; case 4:a1=Copy(a); b1=Copy(b); printf("集合A与集合B的对称差为:"); e=SysmmetricDifference(a1,b1);//计算集合的对称差 东莞理工学院课程设计 Output(e); printf("\n\n"); break; case 0: exit(0);//退出运算系统,结束程序 default: printf("错误!请重新选择!\n");//提示输入错误 } printf("请继续输入您的选择: "); scanf(" %d",&k);//继续选择 } } 4 测试 4.1 测试结果及分析 东莞理工学院课程设计 5 小结 5.1本问题解决方法及程序实现小结 1. 需做好各知识点的衔接才能做到更高效的解决问题; 2. 做这个课程设计之前需复习指针、结构体,特别是链表的知识点。具体形式可以是以程序实例来对这些知识点进行复习,尤其是难理解、易混淆和犯错误的地方; 3. 多点上机的实践经验更是有助于你发现问题解决问题,最后掌握难点知识。 5.2 尚未解决的问题及下一步工作思路 对于指针、链表等知识点,我依旧存在着很多的不懂的地方,今后将会更加努力学习,多点上机实践,争取熟练运用。 6 参考文献 《C语言 大学实用教程 (第三版)》 电子工业出版社 苏小红等主编

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 10 金币 [ 分享文档获得金币 ] 4 人已下载

下载文档