集合的并、交和差运算

1、数据结构课程设计报告设计题目： 专 业 计算机科学与技术 班 级 计091 学 生 张楠 学 号 3090911020 指导教师 起止时间 2011.7.42011.7.9 22011 年 夏季 学期 目录1.实验内容实验题目：编制一个演示集合的并、交运算的程序。题目： 集合运算功能： 使用链表来表示集合，完成集合的合并，求交集等操作。分步实施：1 初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2 完成最低要求： 3 进一步要求： 要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4）要提供程序测试方案1） 程序一定要经得起测试，宁可功能少一些，

2、也要能运行起来，不能运行的程序是没有价值的。需求分析：1、  本演示程序中，集合的元素限定为整形数据。集合输入的形式为一个以“0“为结束标志。2、  演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息“之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。3、  程序执行的命令包括：1）  构造集合1；2）构造在集合2；3）求并集；4）求交集；5）求差集；6）返回；7）结束。“构造集合1”和“构造集合2”时，需以整形的形式键入集合元素。二、数据结构设计及流程图为了实现上述程序的功能，应以有序链表表示集合。

3、为此，需要两个抽象数据类型：有序表和集合。1、有序表的抽象数据类型定义为：input(linklist l)初始条件：l是以l为头节点的空链表。操作结果：生成以l为头节点的非空链表。output(linklist l)初始条件：l是以l为头节点的非空链表。操作结果：将以l为头节点的链表中数据逐个输出。2、集合的抽象数据类型定义为：heji(linklist A,linklist B,linklist C)初始条件：链表A、B、C已存在操作结果：生成一个由A和B的并集构成的集合C。jiaoji(linklist A,linklist B ,linklist ,C)初始条件：链表A、B、C已存在操

4、作结果：生成一个由A和B的交集构成的集合C。3、本程序抱含四个模块：1）  节点结构单元模块定义有序表的节点结构；2）  有序表单元模块实现有序表的抽象数据类型；3）  集合单元模块实现集合获得抽象数据类型；4）主程序模块：Void main（）初始化；do接受命令；处理命令；while（“命令”!=“退出”）；流程图三、源程序# include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>typedef struct nodeint da

5、ta;struct node* next;lnode,*linklist;lnode *init_lnode();void input(linklist l);void jiaoji(linklist A,linklist B,linklist C);void heji(linklist A,linklist B,linklist C);void chaji(linklist A,linklist B, linklist C)；void output(linklist l);void main() lnode *a,*b,*c;a=init_lnode();b=init_lnode();c=i

6、nit_lnode();printf("求AB集合的交集和并集n");printf("请输入A集合的元素:");input(a);printf("n请输入B集合的元素:");input(b);printf("n输入完成n");printf("n按任意键进入主菜单:");getch();dochar menu="nnn- 1.交集运算 -nn" "- 2和集运算-nn" "-3.差集运算 -nn" "- 0. 退出 -nn&qu

7、ot;printf("%s",menu);printf("n请在0-3中选择:");scanf("%d",&sel);switch(sel)case 1: printf("AB集合的交集是:"); jiaoji(A,B,C); output(C); C->next=NULL; break; case 2: printf("AB的合集是:");heji(A,B,C);output(C); C->next=NULL;break; case 3:chaji(A,B,C); brea

8、k; case 0:break;while(sel!=0); /*主函数结束*/ /*初始化函数*/lnode * init_lnode() lnode *l; l=(lnode *)malloc(sizeof(lnode); l->next=NULL; return l;/*录入函数*/void input(linklist l)lnode *s;int x;scanf("%d",&x);while(x!=0)s=(lnode *)malloc(sizeof(lnode);s->data=x;s->next=l->next;l->ne

9、xt=s;scanf("%d",&x);/*交集函数*/void jiaoji(linklist A,linklist B,linklist C)lnode *p,*q,*t;p=A->next;while(p!=NULL)q=B->next;while(q!=NULL)&&(q->data!=p->data)q=q->next;if(q!=NULL)&&(q->data=p->data)t=(lnode*)malloc(sizeof(lnode);t->data=p->data;

10、t->next=C->next;C->next=t;p=p->next;/*输出函数*/void output(linklist l)lnode *s;s=l->next;while(s!=NULL) printf("%5d",s->data);s=s->next;printf("n");/*并集函数*/void heji(linklist A,linklist B,linklist C)lnode *p,*q,*t;p=A->next;while(p!=NULL) t=(lnode*)malloc(siz

11、eof(lnode);t->data=p->data;t->next=C->next;C->next=t;p=p->next;q=B->next;while(q!=NULL)p=A->next;while(p!=NULL)&&(p->data!=q->data) p=p->next;if (p=NULL)t=(lnode*)malloc(sizeof (lnode);t->data=q->data;t->next=C->next;C->next=t;q=q->next;/*差集

12、函数*/void chaji(linklist A,linklist B, linklist C)lnode *p,*q,*s,*t; p=A->next;printf("A与B的差集是:n");while(p!=NULL)q=B->next;while(q!=NULL)&&(p->data!=q->data)q=q->next;if(q=NULL)s=(lnode*)malloc(sizeof(lnode);s->data=p->data;s->next=C->next;C->next=s;p=p

13、->next;output(C);C->next=NULL; q=B->next;printf("B与A的差集是:n");while(q!=NULL)p=A->next;while(p!=NULL)&&(p->data!=q->data)p=p->next;if(p=NULL)t=(lnode*)malloc(sizeof(lnode);t->data=q->data;t->next=C->next;C->next=t;q=q->next;output(C);四、测试数据及程序运行情况 下面是运行时的界面(附图):五、心得体会1、由于对集合的三种运算的算法推敲不足，在链表类型及其尾指针的设置时出现错误，导致程序低效。2、刚开始时曾忽略了一些变量参数的标识”&”，使调试程序浪费时间不少。今后应重视确定参数的变量和赋值属性的区分和标识。3、开始时输入集合后，程序只能进行一次运算，