集合的运算（C++单链表实现）
·
1.需求分析
（1）建立两个含有若干个元素的单链表 A、B , 要求从文件读入数据，显示、保存函数公用。 集合的元素不限定，可以是大小写字母。演示程序以用户和计算机的对话方式执行。
（2）集合中（A与B的交集）包含所有既属于集合 A 又属于集合 B 的元素，显示计算后的结果并保存。
（3）集合中（A与B的并集）包含所有或属于集合 A 或属于集合 B 的元素， 显示计算后的结果并保存。
（4）集合中（A-B）包含所有属于集合 A 而不属于集合 B 的元素，显示计算后的结果并保存。
（5）判断集合 A 与 B 相等，输出结果。
（6）集合 A、B 的所有子集，显示计算后的结果并保存。
2.数据结构与模块化设计
2.1 数据结构设计
本程序采用单链表为存储结构，创建一个集合即初始化一个空链表，程序如下所示：
//定义单链表的结点
struct Node
{
char data;
struct Node *next;
};
//初始化空集合
Gather::Gather()
{
first=new Node;
first=NULL;
}
2.2 模块化设计
本系统有 5 大模块及 7 小模块，与 main 函数之间的主要调用关系如图所示。
图中，3大模块**JiaoJi（），BingJi（），ChaJi（），Equal（），Subset（）**分别用来实现两集合之间的交集、并集、差集、判相等及子集，5大模块的实现主要由7小模块之间的调用实现；
- **Length（）**函数，返回集合的长度；
- **PrintList（）**为遍历函数，用来实现集合的输出显示；
- **Locate（char ch）**为按值查找函数，用来判断集合中是否存在元素ch；
- **Insert（char ch）**为插入函数，用来实现集合的初始化；
- **Get（int i）**为按位查找，用查找位置为i的值；
- **Save（ofstream &fp）**为保存函数，将集合保存至指定的txt文件；
- **Read（ifstream &fp）**为读取函数，从txt文件读取元素到集合中。
2.3 总体功能流程图
3.程序设计
（1）头文件 Gather.h
//Gather.h
#ifndef GATHER_H
#define GATHER_H
#include<fstream>
using namespace std;
//定义单链表的结点
struct Node
{
char data;
struct Node *next;
};
//定义集合类Gather的声明
class Gather
{
public:
Gather();//初始化集合
int Length(); //求单链表的长度
void PrintList();//遍历
bool Locate(char ch);//按值查找
bool Insert(char ch);//插入操作
char Get(int i);//按位查找
void JiaoJi(Gather B);//求交集
void BingJi(Gather B);//求并集
void ChaJi(Gather B);//求差集
void Save(ofstream &fp);//保存
void Read(ifstream &fp);//读取
void Equal(Gather B);//判断是否相等
void Subset(ofstream &fp);//求子集
private:
Node *first;
};
#endif
(2) Gather.cpp
//Gather.cpp
#include<iostream>
#include <fstream>
#include"Gather.h"
#include<math.h>
using namespace std;
//初始化空集合
Gather::Gather()
{
first=new Node;
first=NULL;
}
//求单链表的长度
int Gather::Length()
{
struct Node *p=first;
int count=0;
while(p!=NULL)
{
p=p->next;
count++;
}
return count;
}
//遍历
void Gather::PrintList()
{
struct Node *p=first;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
cout<<endl;
}
//按值查找
bool Gather:: Locate(char ch)
{
struct Node *p=first;
while(p!=NULL)
{
if(p->data==ch) return true;
p=p->next;
}
return false;
}
//插入操作
bool Gather::Insert(char ch)
{
Node *p=first,*s=NULL;
if(first==NULL)
{
first=new Node;
first->data=ch;
first->next=NULL;
return true;
}else{
while(p->next!=NULL)
{
p=p->next;
}
s=new Node;s->data=ch;
s->next=p->next;p->next=s;
return true;
}
}
//按位查找
char Gather::Get(int i)
{
Node *p=this->first;
int count=0;
while(p!=NULL&&count<i)
{
p=p->next;
count++;
}
if(p==NULL) throw"查找位置错误";
else return p->data;
}
//求交集
void Gather::JiaoJi(Gather B)
{
Gather C;
Node *p=this->first;
while(p!=NULL)
{
char ch=p->data;
if(B.Locate(ch)&&!C.Locate(ch)) C.Insert(ch);
p=p->next;
}
C.PrintList();
//将结果保存到文件JiaoJi
ofstream fc("JiaoJi.txt");
C.Save(fc);
fc.close();
cout<<endl;
}
//求并集
void Gather::BingJi(Gather B)
{
Gather C;
Node *p=this->first;
while(p!=NULL)
{
char ch=p->data;
if(!C.Locate(ch)) C.Insert(ch);
p=p->next;
}
Node *q=B.first;
while(q!=NULL)
{
char ch=q->data;
if(!C.Locate(ch)) C.Insert(ch);
q=q->next;
}
C.PrintList();
//将结果保存到文件BingJi
ofstream fc("BingJi.txt");
C.Save(fc);
fc.close();
cout<<endl;
}
//求差集
void Gather::ChaJi(Gather B)
{
Gather C;
Node *p=this->first;
while(p!=NULL)
{
char ch=p->data;
if(!B.Locate(ch)&&!C.Locate(ch)) C.Insert(ch);
p=p->next;
}
C.PrintList();
//将结果保存到文件ChaJi
ofstream fc("ChaJi.txt");
C.Save(fc);
fc.close();
cout<<endl;
}
//保存
void Gather::Save(ofstream &fp)
{
Node *p=this->first;
while(p!=NULL)
{
fp<<p->data<<" ";
p=p->next;
}
fp.close();
}
//读取
void Gather::Read(ifstream &fp)
{
char name[100];
int i=0;
while(fp.peek()!=EOF)
{
fp>>name[i];
this->Insert(name[i]);
cout<<name[i]<<" ";
i++;
}
}
//判相等
void Gather::Equal(Gather B)
{
Node *p=this->first;
if(this->Length()==B.Length()){
while(p!=NULL)
{
char ch=p->data;
if(B.Locate(ch)) p=p->next;
else{
cout<<"集合A与集合B不相等!"<<endl;
return;
}
}
cout<<"集合A与集合B相等!"<<endl;
}else{
cout<<"集合A与集合B不相等!"<<endl;
}
}
//求子集并保存
void Gather::Subset(ofstream &fp)
{
Node *p=this->first;
int i,j;
int len=this->Length();
for(i=(int)pow(2,len)-1;i>=1;i--)
{
int sum=i;
for(j=len-1;j>=0;j--)
{
if(sum>=pow(2,j))
{
cout<<this->Get(len-1-j);
fp<<this->Get(len-1-j);
sum-=(int)pow(2,j);
}
}
cout<<" ";
fp<<" ";
}
fp.close();
cout<<endl;
return;
}
（3）主函数文件（运行文件）Gather_main.cpp
//Gather_main.cpp
#include <iostream>
#include <fstream>
#include "Gather.cpp"
using namespace std;
int main()
{
Gather A;
Gather B;
char nameA[100];
char nameB[100];
char word1;
cout<<"****************************集合的初始化******************************"<<endl;
cout<<"* *"<<endl;
cout<<"* 1 从文件读入 *"<<endl;
cout<<"* 2 从键盘输入 *"<<endl;
cout<<"* *"<<endl;
cout<<"**********************************************************************"<<endl;
cout<<" 请输入1或2进行选择： ";
cin>>word1;
cout<<endl;
switch(word1)
{
case '1':{cout<<"集合A：";ifstream fp1("A.txt");
A.Read(fp1);
fp1.close();
cout<<"\n集合B："; ifstream fp2("B.txt");
B.Read(fp2);
fp2.close();
cout<<endl;}
break;
case '2':{cout<<"请输入集合A：";
for(int i=0;i<100;i++)
{
cin>>nameA[i];
A.Insert(nameA[i]);
if(cin.get()=='\n')
{
break;
}
}
ofstream f1("A.txt");
A.Save(f1);
f1.close();
cout<<"请输入集合B：";
for(int j=0;j<100;j++)
{
cin>>nameB[j];
B.Insert(nameB[j]);
if(cin.get()=='\n')
{
break;
}
}
ofstream f2("B.txt");
B.Save(f2);
f2.close();}
break;
}
char word2;
while(1)
{
cout<<"****************************集合的运算设计******************************"<<endl;
cout<<"* *"<<endl;
cout<<"* 1 求交集 *"<<endl;
cout<<"* 2 求并集 *"<<endl;
cout<<"* 3 求差集 *"<<endl;
cout<<"* 4 判相等 *"<<endl;
cout<<"* 5 求集合A子集 *"<<endl;
cout<<"* 6 求集合B子集 *"<<endl;
cout<<"* 7 退出 *"<<endl;
cout<<"* *"<<endl;
cout<<"************************************************************************"<<endl;
cout<<" 请输入1~7进行选择： ";
cin>>word2;
cout<<endl;
switch(word2)
{
case '1':cout<<"A和B的交集：";A.JiaoJi(B);
break;
case '2':cout<<"A和B的并集：";A.BingJi(B);
break;
case '3':cout<<"A和B的差集：";A.ChaJi(B);
break;
case '4':A.Equal(B);cout<<endl;
break;
case '5':{ofstream fa("Aziji.txt");A.Subset(fa);fa.close();cout<<endl;}
break;
case '6':{ofstream fb("Bziji.txt");B.Subset(fb);fb.close();cout<<endl;}
break;
case '7':cout<<"*******************************结束!!!**********************************"<<endl;
return 1;
default:
cout<<" 出错，重新选择！"<<endl;
}
}
return 0;
}
4.运行展示
运行环境：Dev-C++ 5.11
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
4
0- 0
已为社区贡献2条内容
所有评论(0)