实验 集合运算

1 问题描述与分析

1.1 问题陈述

实现集合交、并、差

1.2 问题分析

• 研究对象

对象为集合，集合包含一定的元素。

• 功能需求分析

本程序要实现集合的交、并、差，功能结构图如图A.1

1.  创建集合;
2.  求两个集合的交集;
3.  求两个集合的并集;
4.  求两个集合的交集。

2 数据结构设计

  本实验包括两个集合的多个运算，集合运算不能改变原有集合。集合创建好后不发生改变，因此采用顺序存储。结点定义如下:

template <class DT>
struct SqList									// 顺序表
{
	DT* elem;									// 表首址
	int length;									// 表长
	int size;									// 表容量
};

3 算法设计

  3.1 创建集合

      集合的创建与顺序表相似，但要注意集合中不能有相同的元素，所以每次输入都要判定该元素是否已经存在，如果存在则不能放入表中。

      使用变量count对不重复元素计数，表长等于count。

      算法描述如下。

template <class DT>
void CreatList(SqList<DT>& L, int n)    //创建集合
{
    int count = 0, i, j;
    DT elem;
    bool exist = false;
    cout << "请依次输入" << n << "个元素值：" << endl;
    for (i = 1; i <= n; i++)
    {
        cin >> elem;
        for (j = 0; j <= count; j++)
             if (L.elem[j] == elem)      //判断是否存在相同元素
                 exist = true;
        if (!exist)                     //如果不存在则加入L中
        {

             L.elem[i - 1] = elem;
             count++;
        }
        exist = false;
    }
    L.length = count;                   //表长为创建的元素个数
}

  3.2  两个集合的交集

       两个集合的交为两个集合中都有的元素，所以，求集合La和Lb交，可以遍历La，对其中的每一个元素e，再Lb中查找，如果找到该元素，将其添加到Lc中。用先信标的基本操作，算法描述如下。

template<class DT>
void InterSet(SqList<DT> La, SqList<DT> Lb, SqList<DT>& Lc) // 求交集
{
    DT e;
    int j = 1; // 设置Lc中首个元素的存储位置
    for (int i = 1; i <= La.length; i++) // 遍历La
    {
        GetElem_i(La, i, e); // 依位序获取La中的每个元素e
        if (LocateElem_e(Lb, e)) // 如果Lb中有元素e
             InsertElem_i(Lc, j++, e); // 将e添加在Lc表尾，j先自增表示新的位置
    }
    Lc.length = j - 1; // Lc表长为Lc中元素个数
}

  3.3 两个集合的并

      两个集合的并集为两集合La,Lb元素的和且不能有重复元素，并且不能改变原集合，所以可以先将La插入到Lc中，然后遍历Lb，对其每个元素e，在La中查找，如果没有找到，将其添加到Lc中。

算法描述如下。

template<class DT>
void unionLists(SqList<DT>& La, SqList<DT> Lb, SqList<DT>& Lc) //求并集
{
    DT e;
    int i;
    for (i = 1; i <= La.length; i++)//将La中的元素添加到Lc中
    {
        GetElem_i(La, i, e); //从La中获取元素e
        InsertElem_i(Lc, i, e); //将e插入到Lc中
    }
    Lc.length = i - 1; //更新Lc.length
    //从Lb中获取元素e，如果e不在Lc中，则将e插入到Lc中
    for (i = 1; i <= Lb.length; i++)
    {
        GetElem_i(Lb, i, e); //从Lb中获取元素e
        if (!LocateElem_e(Lc, e)) //如果e不在Lc中
        {
             int k = Lc.length + 1; //在Lc的表尾插入e
             InsertElem_i(Lc, k, e);
             Lc.length = k; //更新Lc.length
        }
    }
}

  3.5 两个集合的差

     差集Lc = La – Lb = La – La ∩ LB,即Lc中为属于La而不属于Lb的元素集合。遍历La，对其每个元素e，在Lb中查找，如果没有找到，将其添加到Lc中。

算法描述如下。

template<class DT>
void SubSet(SqList<DT> La, SqList<DT> Lb, SqList<DT>& Lc) { // 求差集 
    int j = 0; // 设置Lc中首个元素的存储位置
    DT e;      // 用于存储La中的元素
    for (int i = 1; i <= La.length; i++) { // 遍历La
        if (GetElem_i(La, i, e)) { // 依位序获取La中的每个元素e
             if (!LocateElem_e(Lb, e)) { // 如果Lb中没有元素e
                 InsertElem_i(Lc, ++j, e); // 将e添加在Lc表尾，j先自增表示新的位置
             }
        }
    }
    Lc.length = j; // Lc表长为Lc中元素个数
}

  3.4 两个集合的差

      程序包含多个功能，系统采用菜单形式提供功能选择。菜单定义如下。

void dispmenu()                             //显示菜单
{
    cout << "-----请选择操作------" << endl;
    cout << "1.求交集" << endl;
    cout << "2.求并集" << endl;
    cout << "3.求差集" << endl;
    cout << "0.退出" << endl;
}

4 运行与测试

• 程序启动成功，先创建集合，如图A.2

• 创建完成后，显示菜单如图A.3

• 按1，输出集合La，Lb的交集如图A.4

• 按2，输出集合La，Lb的并集如图A.5

• 按3，输出集合La，Lb的差集如图A.6

• 按0，退出程序，并摧毁集合La，Lb，Lc

5 小结

5.1 实验所得

• 我学习到了如何使用类模板，以及头文件的创建和调用；
• 学到了如何创建显示菜单，对switch的运用更加熟练；
• 根据具体任务选择合适的数据类型，如本实验研究对象为集合，且创建过后无需改变，适合采用顺序表；
• 要根据程序功能，设计不同的算法。

5.2 注意事项

(1) 集合有别于顺序表，集合具有互异性，创建集合时不能出现重复元素；

(2) 完成一个操作后要及时清空Lc，如求完并集后，要清空Lc，以防影响下一步操作；

(3) 程序运行完成后要摧毁三个表，防止内存泄露。

——

完整代码：https://codecopy.cn/post/46m927?pw=candle