一、概要设计
用户可以自行输入数据创建集合(这里设置为整型),并可以选择不同的功能进行不同的集合运算(交集,并集,差集,相对补)。
二、详细设计
1.大致版图
#define type int struct List{ List *next; type data; };
3.函数
void swap(List *&m1,List *&m2){ //使m1的内容换成m2的内容 //应该先吧m1清空 List *r1 = m1->next; while(r1!=NULL){ List *temp = r1; r1=r1->next; delete temp; } //接下来把m2的内容换到m1中去 r1 = m1; r1->next = NULL; List *temp; List *r2 = m2->next; while(r2!=NULL){ temp = new List; temp->data = r2->data; r1->next = temp; temp->next = NULL; r1 = temp; r2 = r2->next; } }
这是交换两个链表的函数。因为在求并交集的时候,我设计的函数会对原链表的值进行改动,会影响后序操作的结果。所以,在用户输入集合之后,就立即新建一个链表存储输入的链表,在每次运算前,都调用此函数交换链表的值。
void createList(List *&m){ cout<<"您正在创建一个集合!"<<endl<<"请先输入元素,以空格分开各元素(如果您输入相同的数字,则该数字会默认只出现一次):"<<endl; int n; vector<int>v; while(cin>>n){ bool has=false; for (vector<int>::iterator it = v.begin(); it != v.end(); it++){ if(n==*it){ has = true; break; } } if(!has){ v.push_back(n); } if(cin.get()=='\n'){ break; } } List *p; List *r = m; for (vector<int>::iterator it = v.begin(); it != v.end(); it++) { p = new List; p->data = *it; r->next = p; p->next = NULL; r=p; } cout<<"创建成功!"<<endl; }
用户输入值的函数。集合中的元素都是不一样的,所以每次当用户输入一个值,我们都遍历存储值的向量,查找有没有这个数。如果有,则跳过,如果没有,则插入。输入数字以空格分开,以回车表示输入完毕。
List * add(List *&m1,List *&m2){ //求并集 List *p1; List *p2 = m2; while(p2->next!=NULL){ p2=p2->next; } List *r2 = m2->next; List *r1 = m1->next; //对于r1的元素,都遍历r2一遍,如果没有,则加到后面。如果有则不处理 while(r1!=NULL){ bool has = false; r2 = m2->next; while(r2!=NULL){ if(r2->data==r1->data){ has = true; break; } r2=r2->next; } if(r2==NULL){ //说明没有这个元素 p1 = new List; p1->data = r1->data; p2->next = p1; p1->next = NULL; p2=p1; } r1=r1->next; } return m2; }
求并集。思路:对于r1的元素,都遍历r2一遍,如果没有,则加到后面。如果有则不处理
List * sub(List *&m1,List *&m2){ //求交集 //求出2个链表中的相同的元素,m1/\m2即m1-相同; m2/\m1即m2-相同 List *p1,*p2,*r1,*r2,*p3,*r3; List *m3 = new List; m3->next = NULL; r3 = m3; r1 = m1->next; while(r1!=NULL){ r2 = m2->next; bool has = false; while(r2!=NULL){ if(r2->data==r1->data){ has = true; break; } r2=r2->next; } if(has){ //说明有这个元素 ,则加到临时链表中去 //在加入之前应该先判断一下是不是有这个元素 p1 = m3->next; //p1做临时指针 has = false; while(p1!=NULL){ if(p1->data==r1->data){ //说明有这个元素,说明不需要加进去 has = true; break; } p1=p1->next; } //判断完毕 if(!has){ p3 = new List; p3->data = r2->data; r3->next = p3; p3->next = NULL; r3 = p3; } } r1=r1->next; } return m3; }
这个函数是求并集。思路:新建一个临时链表m3。对于m1中每个元素,都遍历m2中的每个元素,并判断是否相同,如果相同,则说明属于交集中的一部分,用m3来存储,使用尾插法插到链表末尾。这样,两个链表中的相同的元素都存储在m3中。最后返回m3(即交集)
List * mul(List *&m1,List *&m2){ //求对称差 //求出2个链表中的相同的元素,m1/\m2即m1-相同; m2/\m1即m2-相同 List *p1,*p2,*r1,*r2,*p3,*r3; List *m3 = new List; m3->next = NULL; r3 = m3; r1 = m1->next; while(r1!=NULL){ r2 = m2->next; bool has = false; while(r2!=NULL){ if(r2->data==r1->data){ has = true; break; } r2=r2->next; } if(has){ //说明有这个元素 ,则加到临时链表中去 //在加入之前应该先判断一下是不是有这个元素 p1 = m3->next; //p1做临时指针 has = false; while(p1!=NULL){ if(p1->data==r1->data){ //说明有这个元素,说明不需要加进去 has = true; break; } p1=p1->next; } //判断完毕 if(!has){ p3 = new List; p3->data = r2->data; r3->next = p3; p3->next = NULL; r3 = p3; } } r1=r1->next; } //交集已经求出来了,即m3 //对于m3中的每个元素,都遍历m1,如果有,则删除这个元素;如果没有,则无需处理 //应该加入一个前指针和一个后指针 r3 = m3->next; while(r3!=NULL){ List *pre = m1; r1 = m1->next; bool has = false; while(r1!=NULL){ if(r1->data==r3->data){ has = true; break; } pre=pre->next; r1=pre->next; } if(has){ //如果有,就删除 List *temp = r1; r1 = r1->next; pre->next = r1; delete temp; } else{ //如果没有,则不处理 } r3=r3->next; } return m1; }
函数前半部分是求链表m1、m2的交集(参照前面sub()函数),这样,求得两个链表(即集合)的交集后,将集合中的和交集元素相同的元素除去。为了达到这个目的,对于m3中的每个元素,都遍历m1,查看是否相同。如果相同,则删除后此元素。注意:因为此处用到了删除,所以在开始遍历时,应该准备两个指针,pre和r,pre始终指向r的前一个元素。
List * div(List *&m1,List *&m2,List *&m11,List *&m21){ swap(m1,m11); swap(m2,m21); List *m3 = new List; m3->next = NULL; m3 = mul(m1,m2); List *m31 = new List; m31->next = NULL; swap(m31,m3); swap(m1,m11); swap(m2,m21); List *m4 = new List; m4->next = NULL; List *m41 = new List; m41->next=NULL; m4 = mul(m2,m1); swap(m41,m4); List *m5 = add(m31,m41); return m5; }
求对称差在求出了交集后就很容易求出。我们先求出两个集合的交集(用sub()函数,之后再求集合m1(即链表m1)与交集的差集m4(用mul()函数);之后再求出集合m2(即链表m2)与交集的差集m5(用mul()函数)。最后再求出m4与m5的并集(用add()函数)即可。
void sort(List *&m){ List *r = m->next; //相当于保存数据链表结点 m->next=NULL; //m结点重新开始 List *r2 = m; //方便尾插的哨兵指针 List *p1 = r; //p1作为 bool moveP1 = false; while(p1!=NULL){ int min = p1->data; List *pre; List *p2=p1->next; while(p2!=NULL){ if(min>p2->data){ min = p2->data; } p2=p2->next; } if(p1->data==min){ List *temp = p1; p1=p1->next; delete temp; moveP1 = true; } else{ pre = p1; p2 = pre->next; bool is = false; while(p2!=NULL){ if(p2->data==min){ is = true; break; } pre=pre->next; p2 = pre->next; } if(is){ List *temp = p2; p2=p2->next; pre->next = p2; delete temp; } } List *p3 = new List; p3->data=min; r2->next = p3; p3->next = NULL; r2=p3; } }
排序函数。不另外创建头结点进行排序。原理:代码写的不是很清楚。遍历整个数据链表,找到最小值,删除此结点,另外创建结点存储最小值,插入到原头节点之后。涉及到删除操作,所以需要一个pre指针和一个p指针(一前一后)。
void disp(List *&m){ sort(m); List *r = m->next; if(r==NULL){ cout<<"为空!"<<endl; return ; } while(r!=NULL){ cout<<r->data<<" "; r=r->next; } cout<<endl; }
简单的输出函数,只不过在开头加入了排序函数。
int main(){ List *m1 = new List; List *m2 = new List; m1->next = NULL; m2->next = NULL; List *m11 = new List; List *m21 = new List; m11->next = NULL; m21->next = NULL; List *Add = new List; //并集 List *Sub = new List; //交集 List *Mul = new List; //对称差 List *Div = new List; //相对补 cout<<"目前是求集合各运算界面,您需要输入两个集合:"<<endl; createList(m1); createList(m2); swap(m11,m1); swap(m21,m2); int select; do{ cout<<"您可以选择以下操作:1.求并集 2.求交集 3.求差集(a-b) 4.求差集(b-1) 5.求相对差集 6.查看输入1集合 0.退出"<<endl<<"选择相应操作的序号来进行:"<<endl; while (!(cin >>select)){ cin.clear(); while (cin.get() != '\n'){ continue; }//跳过错误输入 cout << "请输入一个数字:"<<endl; } switch(select){ case 1:{ swap(m1,m11); swap(m2,m21); Add = add(m1,m2); cout<<"并集如下:"<<endl; disp(Add); break; } case 2:{ swap(m1,m11); swap(m2,m21); Sub = sub(m1,m2); cout<<"交集如下:"<<endl; disp(Sub); break; } case 3:{ swap(m1,m11); swap(m2,m21); Mul = mul(m1,m2); cout<<"差集如下:"<<endl; disp(Mul); break; } case 4:{ swap(m1,m11); swap(m2,m21); Mul = mul(m2,m1); cout<<"差集如下:"<<endl; disp(Mul); break; } case 5:{ swap(m1,m11); swap(m2,m21); Div = div(m1,m2,m11,m21); cout<<"相对差集如下:"<<endl; disp(Div); break; } case 6:{ cout<<"您输入的集合如下:"<<endl; disp(m1); disp(m2); break; } case 0:{ cout<<"退出成功!"<<endl; return 0; } default:{ break; } } } while(select!=0); return 0; }
主函数。提供人机交互界面。
三、总结
整体简单,如果是第一次写,个人感觉很锻炼逻辑能力。
.cpp文件下载:
链接: https://pan.baidu.com/s/1bXTwtepmZ1TpLweyE989Ow 提取码: k3bg 复制这段内容后打开百度网盘手机App,操作更方便哦