集合的并,交和差运算
2018年11月6日
【问题描述】
编制一个能演示执行集合的并，交和差运算的程序
【基本要求】
（1）集合的元素限定为小写字母字符
（2）演示程序以用户和计算机的对话方式执行
【测试数据】
（1） Set1 = “magazine” , Set2 = “paper”,
Set1∪Set2 = “aegimnprz” , Set1∩Set2 = “ae” , Set1-Set2 = “gimnz”,
（2）Set1 = “012oper4a6tion89” , Set2 = “error data”,
Set1∪Set2 = “adeinoprt” , Set1∩Set2 = “aeort” , Set1-Set2 = “inp”,
【实现提示】
以有序链表表示集合
【问题分析】
首先，根据提示要用链表储存我们的数据，这个没啥说的
这是顺序创建链表的函数，返回头节点，数据用string的形式传递进来（如果想用递归法创建链表，查看博主另一篇《递归法实现约瑟夫环》的博客）。 接下来就是各个求集合的函数。struct node{
char i;
struct node *next = NULL;
node(char x){i=x;}
};
struct node* createList(string m){//m是字符串的列表
node *head = new node(m[0]);
node *tmp = head;
for(int i=1;i<m.size();i++){
tmp->next = new node(m[i]);
tmp = tmp->next;
}
return head;
}
实现方法没啥好说的，就是两个比一下，将结果给第三个字符串就行了。不过这里注意一下，题目中的结果是按照从小到大实现的，而且每个字符串只输出一次，但是仅仅只比较是无法完成想要的结果的，于是，我们将得到的字符串传入我们自己的比较函数中去。string jiao(node* node1,node* node2){//求交集
string node3;
node* head1 = node1;
node* head2 = node2;
while(node1 != NULL){
while(node2 != NULL){
if(node2->i == node1->i)
node3.push_back(node2->i);
node2 = node2->next;
}
node1 = node1->next;
node2 = head2;
}
node1 = head1;
return mycompare(node3);
}
string he(node* node1,node* node2){//求并集
string node3;
node* head1 = node1;
node* head2 = node2;
while(node1 != NULL){
node3.push_back(node1->i);
while(node2 != NULL){
if(node1->i != node2->i)
node3.push_back(node2->i);
node2 = node2->next;
}
node1 = node1->next;
node2 = head2;
}
node1 = head1;
return mycompare(node3);
}
string jian(node* node1,node* node2){//求两字符串相减
string node3;
node* head1 = node1;
node* head2 = node2;
while(node1 != NULL){
node3.push_back(node1->i);
while(node2 != NULL){
if(node2->i == node1->i)
node3.pop_back();
node2 = node2->next;
}
node1 = node1->next;
node2 = head2;
}
node1 = head1;
return mycompare(node3);
}
这儿就是比较函数，让我们想得到的结果从小到大排序，但是注意一下，我们这任然不能避免重复输出，主要是因为，删除重复的数值有点麻烦，博主于是就在输出的时候耍了点小滑头，增加个判断函数，判断是否和前面的值相等，相等的话就不输出，仅仅输出不相等的值。这是我们的输出函数。string mycompare(string a){//用来排序使输出的字符串由小到大
for(int x=0;x<a.size();x++){
for(int y=x;y<a.size();y++){
if(a[x]>a[y]){
char m = a.at(x);
char n = a.at(y);
a[x] = n;
a[y] = m;
}
}
}
return a;
}
下面是我们的全部代码void shuchu(string a){//用来排除重复的输出
char x = a[0];
cout<<x;
for(int i=1;i<a.size();i++){
if(a[i] != x)
cout<<a[i];
x = a[i];
}
}
#include <iostream>
#include <stdlib.h>
#include <string>
using namespace std;
struct node{
char i;
struct node *next = NULL;
node(char x){i=x;}
};
struct node* createList(string m){//m是字符串的列表
node *head = new node(m[0]);
node *tmp = head;
for(int i=1;i<m.size();i++){
tmp->next = new node(m[i]);
tmp = tmp->next;
}
return head;
}
string mycompare(string a){//用来排序使输出的字符串由小到大
for(int x=0;x<a.size();x++){
for(int y=x;y<a.size();y++){
if(a[x]>a[y]){
char m = a.at(x);
char n = a.at(y);
a[x] = n;
a[y] = m;
}
}
}
return a;
}
void shuchu(string a){//用来排除重复的输出
char x = a[0];
cout<<x;
for(int i=1;i<a.size();i++){
if(a[i] != x)
cout<<a[i];
x = a[i];
}
}
string jiao(node* node1,node* node2){//求交集
string node3;
node* head1 = node1;
node* head2 = node2;
while(node1 != NULL){
while(node2 != NULL){
if(node2->i == node1->i)
node3.push_back(node2->i);
node2 = node2->next;
}
node1 = node1->next;
node2 = head2;
}
node1 = head1;
return mycompare(node3);
}
string he(node* node1,node* node2){//求并集
string node3;
node* head1 = node1;
node* head2 = node2;
while(node1 != NULL){
node3.push_back(node1->i);
while(node2 != NULL){
if(node1->i != node2->i)
node3.push_back(node2->i);
node2 = node2->next;
}
node1 = node1->next;
node2 = head2;
}
node1 = head1;
return mycompare(node3);
}
string jian(node* node1,node* node2){//求两字符串相减
string node3;
node* head1 = node1;
node* head2 = node2;
while(node1 != NULL){
node3.push_back(node1->i);
while(node2 != NULL){
if(node2->i == node1->i)
node3.pop_back();
node2 = node2->next;
}
node1 = node1->next;
node2 = head2;
}
node1 = head1;
return mycompare(node3);
}
int main(){
string S1,S2;
cout<<"请输入字符串S1:";
cin>>S1;
cout<<"请输入字符串S2:";
cin>>S2;
struct node* s1 = createList(S1);
struct node* s2 = createList(S2);
char x;
cout<<"请输入你的选择 A.求并集合 B.求交集 C.求集合相减:";
cin>>x;
switch(x){
case 'A':
shuchu(he(s1,s2));
break;
case 'B':
shuchu(jiao(s1,s2));
break;
case 'C':
shuchu(jian(s1,s2));
break;
}
return 0;
}
Previous
分布式系统中的命令执行的一致性（paxos算法）
Newer