#include<stdio.h> #include<malloc.h> typedef char ElemType typedef struct LNode { ElemType data; struct LNode *next; } LinkNode; void CreateListF(LinkNode *&L,ElemType a[],int a) //头插法建立单链表 { LinkNode *s; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; for(int i=0;i<n;i++) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data=a[i]; s->next = L->next; L->next = s; } } void CreateListR(ListNode *&L,ElemType a[],int n) { LinkNode *s,r; L=(LinkNode *)malloc(sizeof(LinkNode)); L->next=NULL; r=L; //r始终指向尾结点 for(int i=0;i<n;i++) { s=(LinkNode * )malloc(sizeof(LinkNode)); s->data=a[i]; r->next =s; r=s; } r->next =NULL; //尾结点next设置为NULL } void InitList(LinkNode *&L) { L=(LinkNode *)malloc(sizeof(LinkNode)); L->next = NULL; } void DestroyList(LinkNode *&L) { LinkNode *pre = L,P = pre->next; while(p!=NULL) { free(pre); pre=p; p = pre->next; } free(pre); } bool ListEmpty(LinkNode *L) { return (L->next==NULL); } int ListLength(LinkNode *L) { int i=0; LinkNode *p=L; while(p->next!=NULL) { i++; p=p->next; } return (i); } void DispList(LinkNode *L) { LinkNode *p = L->next; while(p!=NULL) { printf("%c",p->data); p =p->next; } printf("\n"); } bool GetElem(LinkNode *L,int i,ElemType &e) { int j=0; LinkNode *p = L; if(i<=0) return false; while(j<i&&p!=NULL) { j++; p = p->next; } if(p==NULL) return false; else { e = p->data; return true; } } int LocateElem(LinkNode *L,ElemType e) { int i =1; LinkNode *p = L->next; while(p!=NULL&&p->data!=e) { p=p->next; i++; } if(p==NULL) return (0); else return (1); } bool ListInsert(LinkNode *&L,int i, ElemType e) { int j =0; LinkNode *p =L,*s; if(i<=0) return false; while(j<i-1&&p!=NULL) { j++; p =p->next; } if(p==NULL) return false; else { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = e; s->next = p->next; p->next =s; return true; } } bool ListDelete(LinkNode *&L,int i,ElemType &e) { int j =0; LinkNode *p=L,*q; if(i<=0) return false; while(j<i-1&&p!=NULL) { j++; p = p->next; } if(p==NULL) return false; else { q = p->next; if(q==NULL) return false; e = q->data; p->next = q->next; free(q); return true; } } #include"linklist.cpp" void Sort(LinkNode *&L) { LinkNode *p ,*pre,*q; p = L->next->next; p->next->next = NULL; while(p!=NULL) { q = p->next; pre = L; while(pre->next!=NULL&&pre->next->data<p->data) pre = pre->next; pre->next =p; p =q; } } void Union(LinkNode *ha,LinkNode *hb,LinkNode *&hc) { LinkNode *pa=ha->next,pb=hb->next,*s,*tc; hc = (LinkNode *)malloc(sizeof(LinkNode)); tc = hc; while(pa!=NULL&&pb!=) { if(pa->data<pb->data) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = pa->data; tc->next =s; tc =s; pa = pa->next; } else if(pa->pata>pb-data) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = pb->data; tc->next =s;tc =s; pb= pb->next; } else { s = (LinkNode * )malloc(sizeof(LinkNode)); s->data = pa->data; tc->next =s;tc =s; pa= pa->next; pb= pb->next; } } if(pb!=NULL) pa=pb; while(pa!=NULL) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = pa->data; tc->next = s;tc =s; pa= pa->next; } tc->next =NULL; } void InterSect(LinkNode *ha,LinkNode *hb,LinkNode *&hc) { LinkNode *pa = ha->next,*pb,*s,*tc; hc = (LinkNode *)malloc(sizeof(LinkNode)); tc =hc; while(pa!=NULL) { pb =hb->next; while(pb!=NULL && pb->data<pa->data) pb= pb->next; if(pb!=NULL && pb->data ==pa->data) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = pa->data; tc->next = s; tc =s; } pa = pa->next; } tc->next =NULL; } void Subs(LinkNode *ha,LinkNode *hb,LinkNode *&hc) { LinkNode *pa = ha->next,*pb,*s,*tc; hc= (LinkNode *)malloc(sizeof(LinkNode)); tc =hc; while(pa!=NULL) { pb= hb->next; while(pb!=NULL && pb->data<pa->data) pb = pb->next; if(!(pb!=NULL&&pb->data<pa->data)) { s = (LinkNode *)malloc(sizeof(LinkNode)); s->data = pa->data; tc->next =s; tc =s; } pa =pa->next; } tc->next =NULL; } int main() { LinkNode *ha,*hb,*hc; ElemType a[]={'c','a','e','h'}; ElemType b[]={'f','h','b','g','d','a'}; printf("集合的运算如下：\n"); CreateListR(ha,a,4); CreateListF(hb,b,6); printf("原集合A:");DispList(ha); printf("原集合B:");DispList(hb); Sort(ha);Sort(hb); printf("有序集合A为："); DispList(ha); printf("有序集合B为："); DispList(hb); Union(ha,hb,hc); printf("集合的并集为C：");DispList(hc); InterSect(ha,hb,hc); printf("集合的交集为C: ");DispList(hc); Subs(ha,hb,hc); printf("集合的差C为： ")DispList(hc); DestroyList(ha);DestroyList(hb);DestroyList(hc); return 1; }