数据结构集合运算(2)

src=src->next; } return i; }//LengthOf void CreateSet(Set dest) { //创建一个新的字母集合，限定a-z ElemType ch; Set p=dest,n; for(;;) { ch=getchar(); if(ch=='\\n') break; if(ch<97||ch>122) continue; n=(Set)malloc(sizeof(ElemNode)); p->next=n; n->elem=ch; n->next=NULL; p=n; } return ; }//CreateSet void EmptySet(Set dest) { //清空一个集合，保留头结点 Set p,n; while(dest->next!=NULL) { p=dest; n=p->next; for(;n->next!=NULL;) { p=n; n=n->next; } free(n); p->next=NULL; } }//EmptySet void DestroySet(Set dest) { //销毁集合 EmptySet(dest); free(dest); }//DestroySet void SortSet(Set dest)

6

{ //对一个字母集合进行从小到大的排序 int i,j,l,flag; Set p,q,n; l=LengthOf(dest); if(l<2) return; flag=1; for(i=l-1;i>0&&flag==1;i--) { flag=0; p=dest; q=p->next; n=q->next; for(j=0;jelem>n->elem) { flag=1; p->next=n; q->next=n->next; n->next=q; q=p->next; n=q->next; } p=q; q=n; n=n->next; } } }//SortSet void DisplaySet(Set src) { //打印集合的所有元素 Set p; if(src->next==NULL) { printf(\φ\ return ; } p=src; do { p=p->next; putchar(p->elem); } while(p->next!=NULL); }//DisplaySet

7

int ExistElem(Set dest, ElemType e) { //判断元素是否存在于集合中 Set p=dest; if(LengthOf(p)==0) return 0; else{ p=p->next; while(p->elem!=e) { if(p->next==NULL) return 0; p=p->next; } return 1; } }//ExistElem void DelElem(Set dest, ElemType e) { //删除集合中的一个元素一次 Set p=dest,q; if(LengthOf(p)==0) return ; q=p->next; if(LengthOf(p)==1) { p->next=NULL; free(q); } while(q->elem!=e) { p=p->next; q=q->next; } if(q->next==NULL) { p->next=NULL; free(q); } else p->next=q->next; }//DelElem void AddElem(Set dest, ElemType e) { //在链表尾部追加一个元素 Set p=dest, n;

8

while(p->next!=NULL) p=p->next; n=(Set)malloc(sizeof(ElemNode)); p->next=n; n->elem=e; n->next=NULL; }//AddElem void ContactSet(Set dest, Set src) { //连接一个集合到另一个集合 Set p=dest; while(p->next!=NULL) p=p->next; p->next=src->next; }//ContactSet void AddSet(Set dest, Set src1, Set src2) { //集合并运算 SortSet(src1);SortSet(src2); int i=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2); src1=src1->next;src2=src2->next; while(ielem<=src2->elem) { i++; if(!ExistElem(dest, src1->elem)) { AddElem(dest, src1->elem); src1=src1->next; } else { src1=src1->next; } } else { j++; if(!ExistElem(dest, src2->elem)) { AddElem(dest, src2->elem); src2=src2->next; } else {

9

src2=src2->next; } } } while(ielem)) { AddElem(dest, src1->elem); src1=src1->next; } } while(jelem)) { AddElem(dest, src2->elem); src2=src2->next; } } }//AddSet void MulSet(Set dest, Set src1, Set src2) { //集合交运算 SortSet(src1);SortSet(src2); int i=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2); src1=src1->next;src2=src2->next; while(ielemelem) {i++;src1=src1->next;} else if(src1->elem>src2->elem) {j++;src2=src2->next;} else { i++;j++; if(!ExistElem(dest, src1->elem)) { AddElem(dest, src1->elem); src1=src1->next; src2=src2->next; } } } }//MulSet void SubSet(Set dest, Set src1, Set src2)

10