使用散列表实现整型集合的交并差等运算

基于以下代码，补充完善代码，实现集合的交、并、差、对称差的运算。并在test()函数编写相应的测试代码进行测试。

#include
using namespace std;

struct Node{
int data;
struct Node *next;
};

const int MaxSize = 100;
class HashTable
{
public:
HashTable( )
{
//将散列表的同义词子表头指针全部设置为空
for (int i = 0; i < MaxSize; i++)
{
ht[i] = NULL;
}
}

HashTable(int arr[], int n)
{
    //先将散列表的同义词子表头指针全部设置为空 
    for (int i = 0; i < MaxSize; i++)
    {
        ht[i] =  NULL;
    }    
    
    //将arr数组的每个元素插入本散列表 
    for (int i = 0; i < n ; i++)
    {
        Insert(arr[i]);
    }
}

~HashTable( )
{
    //析构，遍历散列表，对每个同义词字表，删除节点释放内存 
    Node *p = NULL, *q = NULL;
    for (int i = 0; i < MaxSize; i++)
    {
        p = q = ht[i];
        while (p != NULL)
        {
            p = p->next;
            delete q;
            q = p;
        }
    }
}


//插入k，如果k已在散列表返回1，成功插入返回0 
//算法步骤如下： 
//1.计算k的散列值j 
//2.获得同义词子表j的链表头指针
//3.遍历此同义词子表，查找k是否已经在子表内
//4.根据3的结果执行以下操作 
//4.1如果已在子表，则不进行插入
//4.2如果不在，则在同义词子表j的头部插入新的节点     
int Insert(int k)
{
    
    int j = H(k);
    Node *p = ht[j];
    while (p != NULL)
    {
        if (p->data == k) break;
        else p = p->next;
        
    }
    if (p == NULL) {
        Node *q = new Node;
        q->data = k;
        q->next = ht[j];
        ht[j] = q;
        return 0;
    }
    else {
        return 1;
    }
}

//删除k，成功删除返回1，k不在散列表返回0 
//删除的算法步骤如下：
//1.计算k的散列值j 
//2.获得同义词子表j的链表头指针
//3.遍历此同义词子表，查找k数据的节点p以及前驱节点pre
//4.根据3的结果如下操作
//4.1如果找到k数据（即p指针不为空）,删除p节点。
//    删除时需要注意，可能p节点没有前驱（即p节点是第一个元素，pre为空），此时设置散列表表头指向p->next即可。 
//4.2如果未找到，不做任何操作 
int Delete(int k)
{

    int j = H(k);
    Node *p = ht[j], *pre = NULL;
    while ((p != NULL) && (p->data != k))
    {
        pre = p;
        p = p->next;
    }
    if (p != NULL) {
        if (pre == NULL) ht[j] = p->next;
        else pre->next = p->next;
        delete p;
        return 1;
    }
    else
        return 0;
}


//查找k，成功找到返回节点指针，否则返回空指针 
Node * Search(int k)
{
    int j = H(k);
    Node *p = ht[j];
    while (p != NULL)
    {
        if (p->data == k) return p;
        else p = p->next;
    }
    return NULL;
}

public:

//与散列表B计算交集，结果保存在本散列表 
void Intersection_Update(HashTable *B)
{
    //遍历本散列表的所有同义词子表 
    for (int j = 0; j < MaxSize; j++)
    {
        
        Node *p = ht[j];
        Node *pre = NULL;//p节点的前驱 
        
        while (p != NULL)
        {
            if (B->Search(p->data) != NULL) 
            {    
                //如果在散列表B中找到p节点数据，则保留 
                pre = p;
                p = p->next;
            }
            else{
                //如果在散列表B中未找到p节点数据，在此同义词子表中删除p节点 
                Node *q = p->next;
                if (pre == NULL) //前驱pre为空时，当前p节点是同义词子表j的第一个节点 
                {
                    ht[j] = q;
                } 
                else{
                    pre->next = q;
                }
                delete p;
                p = q;
            }
        }
    }
}

//并集，结果保存于本散列表 
void Union_Update(HashTable *B)
{
    //思路是遍历B散列表的所有同义词子表 
    // 可通过 B->GetSubList(j)获得B散列表的同义词子表j，
    // 然后再遍历此同义词子表j与本散列表进行并集的运算 
    // TODO
}

//差集，结果保存于本散列表 
void Difference_Update(HashTable *B)
{
    // TODO 思路与并集相似 
}

//对称差集 
void Symmetric_Difference_Update(HashTable *B)
{
    // TO DO，思路与并集相似 
}

public:

//打印本散列表所有数据 
void PrintHashtable()
{
    //遍历本散列表的所有同义词此表 
    for (int j = 0; j < MaxSize; j++)
    {
        
        //获得同义词子表j的头指针 
        Node *p = ht[j];
        
        //遍历此同义词子表 
        while (p != NULL)
        {
            cout << p->data << " ";
            p = p->next;
        }
    }
    cout << endl;
} 


//返回同义词子表j的链表头指针 
Node *GetSubList(int j)
{
    return ht[j];
}

private:

int H( int k )
{
    return k % MaxSize;
}
Node * ht[MaxSize];

};

void test()
{
int a[] = {47, 7, 29, 11, 16, 92, 22, 8, 3};
HashTable ht_a(a, 9);
ht_a.PrintHashtable();

int b[] = {47, 29, 8, 10, 20};
HashTable ht_b(b, 5);
ht_b.PrintHashtable();


//交集运算测试 
ht_a.Intersection_Update(&ht_b);

 //并集运算测试 


//差集运算测试 


//对称差集测试 


ht_a.PrintHashtable();

}

int main(int argc, const char * argv[]) {

test();


return 0;

}