/*在以单链表表示的正整数的有序集合上，实现集合的并、交和差运算。 基本要求： （1）用单链表存储集合中的数据； （2）对单链表中的数据进行排序。 */ #include<stdio.h> #include<stdlib.h> #include<time.h> typedef struct LNode{ int data; struct LNode *next; }LNode,*LinkList; void CreateLinkList(LinkList &L,int n){//尾插法建立单向链表,头结点不用 LinkList cur,pNew; int i; srand(time(0)); L=cur=NULL; for(i=0;i<=n;i++){ pNew=(LinkList)malloc(sizeof(LNode)); pNew->data=rand()%90+10; //产生出随机数作为集合内素 if(i==0){ L=cur=pNew; L->data=-1; } else{ cur->next=pNew; cur=pNew; } } cur->next=NULL; } int QuickSort(LinkList &L,LinkList tail){ //单链表递归快速排序 LinkList mid,p,q,m; int key; if (L->next==tail || L->next->next==tail) return -1; mid=L->next; p=L; q=mid; key=mid->data; m=mid->next; while (m!=tail){ if (m->data<key) p=p->next=m; else q=q->next=m; m=m->next; } p->next = mid; q->next = tail; QuickSort(L,mid); QuickSort(mid,tail); return 0; } void Print(LinkList L){// 输出集合 LinkList p; p=L->next;; while(p){ printf("%d\t",p->data); p=p->next; } printf("\n"); } void AddList(LinkList La,LinkList Lb){ //求并集并输出 LinkList Lc; LinkList cur,la,lb,ln; Lc=cur=(LinkList)malloc(sizeof(LNode)); la=La->next; lb=Lb->next; while(la && lb){ if(la->data<lb->data){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=la->data; cur->next=ln; cur=ln; la=la->next; } else if(la->data==lb->data){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=la->data; cur->next=ln; cur=ln; la=la->next; lb=lb->next; } else{ ln=(LinkList)malloc(sizeof(LNode)); ln->data=lb->data; cur->next=ln; cur=ln; lb=lb->next; } } while(la){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=la->data; cur->next=ln; cur=ln; la=la->next; } while(lb){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=lb->data; cur->next=ln; cur=ln; lb=lb->next; } cur->next=NULL; Print(Lc); } void JiaoList(LinkList La,LinkList Lb){ LinkList Lc,la,lb,ln,cur; Lc=cur=(LinkList)malloc(sizeof(LNode)); la=La->next; lb=Lb->next; while(la && lb){ if(la->data<lb->data) la=la->next; else if(la->data==lb->data){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=la->data; cur->next=ln; cur=ln; la=la->next; lb=lb->next; } else lb=lb->next; } cur->next=NULL; Print(Lc); } void ChaList(LinkList La,LinkList Lb){ LinkList Lc,la,lb,cur,ln; Lc=cur=(LinkList)malloc(sizeof(LNode)); la=La->next; lb=Lb->next; while(la && lb){ if(la->data<lb->data){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=la->data; cur->next=ln; cur=ln; la=la->next; } else if(la->data==lb->data){ la=la->next; lb=lb->next; } else lb=lb->next; } while(la){ ln=(LinkList)malloc(sizeof(LNode)); ln->data=la->data; cur->next=ln; cur=ln; la=la->next; } cur->next=NULL; Print(Lc); } int main(){ LinkList La,Lb; int na,nb; printf("请输入第一个集合的素数目\n"); scanf("%d",&na); CreateLinkList(La,na); printf("请输入第二个集合的素数目\n"); scanf("%d",&nb); CreateLinkList(Lb,nb); QuickSort(La,NULL); QuickSort(Lb,NULL); Print(La); Print(Lb); printf("并集为：\n"); AddList(La,Lb); printf("交集为：\n"); JiaoList(La,Lb); printf("差集为：\n"); ChaList(La,Lb); return 0; }