本文共 6701 字,大约阅读时间需要 22 分钟。
//* 选作内容 (1)集合元素的判定和子集判定运算 (2)求集合的补集 (3)集合的混合式运算表达求值 (4)集合的元素类型推广到其他类型,甚至任意类型 */ /* 测试数据: (1)Set1 = "magazine",Set2 = "paper", Set1∪Set2 = "aegimnpra",Set1∩Set2 = "ae",Set1 - Set2 = "gimnz" (2)Set1 = 012oper4a6tion89",Set2 = "error date", Set1∪Set2 = "adeinoprt",Set1∩Set2 = "aeort",Set1 - Set2 = "inp" */ #include<iostream> #include<cstdlib> #include<cstdio> using namespace std; #define ElemType char typedef struct ElemNode { ElemType elem; struct ElemNode *next; }ElemNode, *Set; //-------------FunctionList------------------------------ //---------------函数原型-------------------------------- int LengthOf(Set src);//返回一个集合的长度 void CreateSet(Set dest);//创建一个新的字母集合,限定a-z void EmptySet(Set dest);//清空一个集合,保留头结点 void DestroySet(Set dest);//销毁集合 void SortSet(Set dest);//对一个集合进行从小到大的排序 void DisplaySet(Set src);//打印集合的所有元素 int ExistElem(Set dest, ElemType e);//判断元素是否存在于集合中 void DelElem(Set dest, ElemType e);//删除集合中的一个元素一次 void AddElem(Set dest, ElemType e);//在链表尾部追加一个元素 void ContactSet(Set dest, Set src);//连接一个集合到另一个集合 void AddSet(Set dest, Set src1, Set src2);//集合并运算 void MulSet(Set dest, Set src1, Set src2);//集合交运算 void SubSet(Set dest, Set src1, Set src2);//集合差运算 int ExistSubset(Set dest, Set src);//子集判断 void NegSet(Set dest, Set src);//求补集 int main() { Set dest=(Set)malloc(sizeof(ElemNode)); Set src1=(Set)malloc(sizeof(ElemNode)); Set src2=(Set)malloc(sizeof(ElemNode)); dest->next=NULL; cout<<"输入两个集合:"<<endl; CreateSet(src1);CreateSet(src2); cout<<endl; cout<<"Set1 = ";DisplaySet(src1); cout<<"\t"; cout<<"Set2 = ";DisplaySet(src2); cout<<endl<<endl; int item; cout<<"1->集合并"<<" "<<"2->集合交"<<" "<<"3->集合差"<<" "<<"非零整数->错误!重输"<<" "<<"0->进入下一步演示"<<endl; while(cin>>item) { if(item) switch(item) { case 1: cout<<"集合并运算:Set1∪Set2 = "; AddSet(dest, src1, src2); DisplaySet(dest); EmptySet(dest); cout<<endl;break; case 2: cout<<"集合交运算:Set1∩Set2 = "; MulSet(dest, src1, src2); DisplaySet(dest); EmptySet(dest); cout<<endl;break; case 3: cout<<"集合差运算:Set1-Set2 = "; SubSet(dest, src1, src2); DisplaySet(dest); EmptySet(dest); cout<<endl;break; default: cout<<"输入错误!重输!!!"<<endl;break; } else {cout<<"进入下一步演示..."<<endl;break;} // 此处在VC++ 6.0 运行与CFree中有点不同(在CFree中要按下回车~~~) } getchar(); cout<<"输入一个集合:"<<endl; CreateSet(dest); cout<<"原集合为:"; DisplaySet(dest); cout<<endl<<endl; char ch; cout<<"在链表尾部添加一个元素ch = "; cin>>ch; AddElem(dest, ch); DisplaySet(dest); cout<<endl<<endl; cout<<"删除集合中的存在的某个元素ch = "; cin>>ch; DelElem(dest, ch); DisplaySet(dest);cout<<endl<<endl; cout<<"再创建一个集合src = "; Set src=(Set)malloc(sizeof(ElemNode)); getchar(); CreateSet(src); cout<<"将src集合链接到集合dest中..."<<endl; ContactSet(dest, src); cout<<"此时dest为:"; DisplaySet(dest); cout<<endl; if(ExistSubset(dest, src)) cout<<"此时src是dest的子集..."<<endl; else cout<<"此时src不是dest的子集..."<<endl; cout<<endl<<"dest = "; DisplaySet(dest); cout<<endl; cout<<"dest的补集是:"; Set p=(Set)malloc(sizeof(ElemNode)); p->next=NULL; NegSet(p, dest); DisplaySet(p); cout<<endl<<"演示结束!!!"<<endl; DestroySet(dest); return 0; } //---------------BasicFunctions----------------------- //------------------函数实现-------------------------- int LengthOf(Set src) { //返回一个集合的长度 int i=0; while(src->next!=NULL) { i++; 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) { //对一个字母集合进行从小到大的排序 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;j<i;j++) { if(q->elem>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 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; 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(i<len1&&j<len2) { if(src1->elem<=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 { src2=src2->next; } } } while(i<len1) { i++; if(!ExistElem(dest, src1->elem)) { AddElem(dest, src1->elem); src1=src1->next; } } while(j<len2) { j++; if(!ExistElem(dest, src2->elem)) { 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(i<len1&&j<len2) { if(src1->elem<src2->elem) {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) { //集合差运算 SortSet(src1);SortSet(src2); int i=0,len=LengthOf(src1); src1=src1->next; while(i<len) { i++; if(!ExistElem(src2, src1->elem)) { if(!ExistElem(dest, src1->elem)) { AddElem(dest, src1->elem); src1=src1->next; } } else { src1=src1->next; } } }//SubSet int ExistSubset(Set dest, Set src) { //子集判断 int i=0,len=LengthOf(src); src=src->next; while(i<len) { if(!ExistElem(dest, src->elem)) return 0; i++; src=src->next; } return 1; }//ExistSubset void NegSet(Set dest, Set src) { //求补集 SortSet(src); int i=0; while(i<26) { if(!ExistElem(src, i+97)) AddElem(dest, i+97); i++; } }//NegSet转载地址:http://onows.baihongyu.com/