c语言数据结构单链表的交并差集运算实现

数据结构上机实验课后练习报告姓名：冯天明学号：班级：通信1412015年9月28日星期一实验五：实现A、B两个单链表表示的集合的交集、并集和差集实验代码：#includestdio.h#includestdlib.h#defineOK0#defineERROR-1#defineOVERFLOW-2typedefintElemType;typedefstructLNode{ElemTypedata;//定义数据域LNode*next;//定义指针域}LNode,*LinkList;voidInitList(LinkList*L)//创建链表头{*L=(LinkList)malloc(sizeof(LNode));if(!L)exit(OVERFLOW);//头结点内存申请失败(*L)-next=NULL;}voidDerstorList(LinkList&L)//清空链表{LinkListp;while(L-next){p=L-next;L-next=p-next;free(p);}}voidClearList(LinkList*L,intn)//初始化链表{LinkListp;inti;for(i=0;in;i++){p=(LinkList)malloc(sizeof(LNode));//生成新节点scanf(%d,&(p)-data);p-next=(*L)-next;//头插法(*L)-next=p;}}voidInserList(LinkList*L,ElemTypee)//头插法插入数据{LinkListp;p=(LinkList)malloc(sizeof(LNode));p-data=e;p-next=(*L)-next;//头插法(*L)-next=p;}voidDisplaList(LinkListL)//输出链表{LinkListhead;head=L-next;if(head==NULL)printf(集合为空！\n);while(head)//遍历链表{printf(%4d,head-data);//输出节点信息head=head-next;}printf(\n);}intisPresent(LinkListL,ElemTypedata)//判断链表中是否已经存在data该元素{LinkListp=L-next;while(p)//遍历链表，查找是否存在data值{if(p-data==data)return1;p=p-next;}return0;}/*************求两个链表的交集**************/intIntersection(LinkListL1,LinkListL2,LinkListL3){LinkListp,q;p=L1-next;q=L2-next;while(p){while(q){//判断两链表的元素是否相当，并且存入的链表中不存在该元素即可存入if(p-data==q-data&&!isPresent(L3,p-data)){InserList(&L3,p-data);}q=q-next;}q=L2-next;//复位p=p-next;}returnOK;}/************求链表的并集************/voidUnion(LinkListL1,LinkListL2,LinkListL3){LinkListp,q;p=L1-next;q=L2-next;DerstorList(L3);//清空链表，重新存入数据while(p){//如果p中的元素不在并集链L3中，防止L1中有重复元素if(!isPresent(L3,p-data))InserList(&L3,p-data);//插入元素p=p-next;}p=L1-next;while(q){if(!(isPresent(L3,q-data)))//q-data元素不存在并集表中，则插入{InserList(&L3,q-data);//把L2表中的元素插入}q=q-next;}}/************求链表的差集************/voidSubtraction(LinkListL1,LinkListL2,LinkListL3){LinkListp,q;p=L1-next;q=L2-next;DerstorList(L3);while(p){if(!(isPresent(L2,p-data)))//如果L2中不存在data值，即为L1-L2差集InserList(&L3,p-data);p=p-next;}}voidmain(){LinkListL1,L2,L3;intnumber;InitList(&L1);//创建空链表InitList(&L2);InitList(&L3);//存储交并差集的链表printf(请输入链表L1的元素个数:);scanf(%d,&number);printf(输入链表L1的内容:\n);ClearList(&L1,number);//初始化链表L1printf(请输入链表L2的元素个数:);scanf(%d,&number);printf(输入链表L2的内容:\n);ClearList(&L2,number);//初始化链表L2printf(L1：);DisplaList(L1);printf(L2：);DisplaList(L2);printf(L1∩L2为(交集):);Intersection(L1,L2,L3);//求链表L1与L2的交集DisplaList(L3);printf(L1∪L2为(并集):);Union(L1,L2,L3);//求链表L1L2的并集DisplaList(L3);printf(L1-L2(补集):);Subtraction(L1,L2,L3);//求链表L1L2的差集（补集）DisplaList(L3);}