C语言集合交并差运算(数据结构)

数据结构课程设计1姓名:邵晓航集合的交运算问题辽宁工程技术大学数据结构课程设计指导教师：吴德成班级：理科实验11-22012年12月15日集合的交集运算问题2集合交运算问题1、问题描述用链表表示两个简单集合，求两个集合的交，并做相关推广。2、基本要求1)集合元素限定为单字符型。2)另外申请存储空间存放集合中相同的元素。3)输入：在程序中定义，随机生成或键盘输入。4)输出：两个集合及两个集合的交。3、设计思路设有集合A、B，A与B的交集为A∩B。A∩B指既属于集合A又属于集合B的元素。因为要求另外申请存储空间，可另找一个新的集合C，C中存储A和B共同的元素。问题即变为求：C=A∩B。于是算法思想为：以A为标准，对B进行遍历，把B中和A相同的元素存储到C中。为方便操作，链表需要设置头结点。具体过程如下：1.扫描A，对A中每个元素执行22.在B中查找该元素2.1如果B中有，则保留到C中2.1否则，继续查找3.显示C=A∩B从以上过程可见，可以借助于链表的基本操作实现上述算法。4、测试与运行（程序见附录）数据结构课程设计3从运行过程可以看出以下几点：A、B集合可以为数字、字母、字符，因为定义A、B集合为字符型A、B集合中的元素都是简单的单字符A、B集合遍历时，是反序输出的在“请选择序号”如果选择“2”则跳出输入循环，结束5、问题扩展（附录2）上述程序设计可以解决两个简单单字符集合的交集问题，由此可发散求解两个集合的并集和差集。求集合的并就是求A和B中所有的元素求集合的差就是求A集合中减去同B集合相同元素的部分（假设A大于B）我们先定义两个集合的并，设计思路如下：1.把A中的元素全部放到一个集合C中2.以A每一个元素为基准，对B进行循环2.1B中存在元素与该元素不同，则把该元素放到C中2.2B中存在元素与该元素相同，继续循环3.显示C=A+B我们定义两个集合的差，设计思路如下：1.假定A大于B，计算C=A-B2.以A每一个元素为基准，对B进行循环2.1B中元素都与该元素不同，则把该元素放到C中2.2B中存在元素与该元素相同，继续循环3.显示C=A-B6、反思与改进从以上运行结果来看，该程序仅能处理单字符的简单集合。因为在链表遍历时，程序是由后向前推移的。又因为集合中元素是字符型，所以元素“abc”会记录成“cba”，且元素的连贯性也会遭到破坏，如上图交集中出现两个“a”。此时需要调整程序中的“输入集合函数”函数集合的交集运算问题47、附录1#includestdio.h#includestdlib.htypedefstructLNode//定义结构体类型指针{chardata;structLNode*next;}*pointer;voidreaddata(pointerhead)//定义输入集合函数{pointerp;chartmp;scanf(%c,&tmp);while(tmp!='\n'){p=(pointer)malloc(sizeof(structLNode));p-data=tmp;p-next=head-next;head-next=p;scanf(%c,&tmp);}}voidpop(pointerhead)//定义输出集合函数{pointerp;p=head-next;while(p!=NULL){printf(%c,p-data);p=p-next;}printf(\n);}voidor(pointerhead1,pointerhead2,pointerhead3)//定义集合的交集函数{pointerp1,p2,p3;p1=head1-next;while(p1!=NULL){p2=head2-next;while((p2!=NULL)&&(p2-data!=p1-data))p2=p2-next;数据结构课程设计5if((p2!=NULL)&&(p2-data==p1-data)){p3=(pointer)malloc(sizeof(structLNode));p3-data=p1-data;p3-next=head3-next;head3-next=p3;}p1=p1-next;}}voidmain()//主函数{intx;printf((输入数据,按回车键结束\n);pointerhead1,head2,head3;head1=(pointer)malloc(sizeof(structLNode));head1-next=NULL;head2=(pointer)malloc(sizeof(structLNode));head2-next=NULL;head3=(pointer)malloc(sizeof(structLNode));head3-next=NULL;printf(请输入集合A：\n);readdata(head1);//调用输入集合函数printf(请输入集合B：\n);readdata(head2);//调用输入集合函数A:printf(1.交集2.结束\n);do{printf(请选择序号\n);scanf(%d,&x);switch(x){case1:or(head1,head2,head3);//调用交集函数printf(集合A为：);pop(head1);printf(集合B为：);pop(head2);printf(两集合的交集C=A∩B：);pop(head3);head3-next=NULL;break;case2:break;default:gotoA;}集合的交集运算问题6}while(x!=2);}8、附录2voidand(pointerhead1,pointerhead2,pointerhead3)//定义集合的并集函数{pointerp1,p2,p3;p1=head1-next;while(p1!=NULL){p3=(pointer)malloc(sizeof(structLNode));p3-data=p1-data;p3-next=head3-next;head3-next=p3;p1=p1-next;}p2=head2-next;while(p2!=NULL){p1=head1-next;while((p1!=NULL)&&(p1-data!=p2-data))p1=p1-next;if(p1==NULL){p3=(pointer)malloc(sizeof(structLNode));p3-data=p2-data;p3-next=head3-next;head3-next=p3;}p2=p2-next;}}voiddiffer(pointerhead1,pointerhead2,pointerhead3)//定义集合的差集函数{pointerp1,p2,p3;p1=head1-next;while(p1!=NULL){p2=head2-next;while((p2!=NULL)&&(p2-data!=p1-data))p2=p2-next;if(p2==NULL){数据结构课程设计7p3=(pointer)malloc(sizeof(structLNode));p3-data=p1-data;p3-next=head3-next;head3-next=p3;}p1=p1-next;}}