實驗題目：驗證集合的并與交程序
一钉鸯、實驗?zāi)康?/h2>
- 驗證集合的并與交程序现诀。
二夷磕、實驗內(nèi)容
- 有兩個順序表LA和LB，把它們當(dāng)成集合來使用仔沿，考慮它們的并運算和交運算〕咂澹可以把順序表當(dāng)作一個抽象數(shù)據(jù)類型封锉，直接利用它的定義來實現(xiàn)要求的運算。
三膘螟、設(shè)計和編碼
1. 本實驗用到的理論知識
線性表（順序存儲結(jié)構(gòu)）
2. 算法設(shè)計
主要展示Union和Intersection兩個函數(shù)的設(shè)計成福，其余的均是線性表（順序存儲結(jié)構(gòu)）的常見算法。
偽代碼如下
void Union(SeqList<T> &LA, SeqList<T> &LB) {
int n1 = LA.Length(), n2 = LB.Length();
for (i = 0; i < n2; i++) {
x = LB.getData(i + 1); //在LB中取一元素
k = LA.Search(x); //在LA中搜索它
if (k == 0) //若在LA中未找到插入它
{
LA.Insert(n1, x);
n1++;
} //插入到第n個表項位置}
}
}
void Intersection(SeqList<T> &LA, SeqList<T> &LB) {
int n1 = LA.Length();
for (i = 0; i < n1; i++) {
x = LA.getData(i + 1); //在LA中取一元素
k = LB.Search(x); //在LB中搜索它
if (k == 0) //若在LB中未找到
{
LA.Remove(i + 1);
n1--;
} //在LA中刪除它
else i++;
}
}
| 時間復(fù)雜度 | 空間復(fù)雜度 |
|---|---|
3. 編碼
程序清單如下（部分有修改）
// SeqList_main.cpp
// Encoding: UTF-8
#include <iostream> //引入輸入輸出流
using namespace std;
#include "SeqList.cpp" //引入類SeqList的聲明
int main()
{
int p[5] = {1, 2, 3, 4, 5};
int q[4] = {0, 4, 5, 6};
SeqList<int> a(p, 5), b(q, 4);
cout << "a: ";
a.PrintList();
cout << "b: ";
b.PrintList();
cout << "Union(a, b): ";
Union(a, b);
a.PrintList();
SeqList<int> c(p, 5), d(q, 4);
cout << "c: ";
c.PrintList();
cout << "d: ";
d.PrintList();
cout << "Intersection(c, d): ";
Intersection(c, d);
c.PrintList();
}
// SeqList.h
// Encoding: UTF-8
#ifndef SeqList_H //避免重復(fù)包含SeqList.h頭文件
#define SeqList_H
const int MaxSize = 10; //10只是示例性的數(shù)據(jù)荆残，可以根據(jù)實際問題具體定義
template <typename DataType>
class SeqList
{
public:
SeqList() { length = 0; } //無參構(gòu)造函數(shù)奴艾，創(chuàng)建一個空表
SeqList(DataType a[], int n); //有參構(gòu)造函數(shù)
~SeqList() {} //析構(gòu)函數(shù)
void Insert(int i, DataType x); //在線性表第i個位置插入值為x的元素
DataType Remove(int i); //刪除線性表的第i個元素
int Search(DataType x); //求線性表中值為x的元素序號
void PrintList(); //按序號依次輸出各元素
int Length(); //求性線表的長度
int getData(int i); //按位查找，在線性表中查找第i個元素
template <typename T>
friend void Union(SeqList<T> &LA, SeqList<T> &LB); //集合的并
template <typename T>
friend void Intersection(SeqList<T> &LA, SeqList<T> &LB); //集合的交
private:
DataType data[MaxSize]; //存放數(shù)據(jù)元素的數(shù)組
int length; //線性表的長度
};
#endif
// SeqList.cpp
// Encoding: UTF-8
#include <iostream> //引入輸入輸出流
using namespace std;
#include "SeqList.h" //引入類SeqList的聲明
//以下是類SeqList的成員函數(shù)定義
template <typename DataType>
SeqList<DataType>::SeqList(DataType a[], int n)
{
if (n > MaxSize)
throw "參數(shù)非法";
for (int i = 0; i < n; i++)
data[i] = a[i];
length = n;
}
template <typename DataType>
void SeqList<DataType>::Insert(int i, DataType x)
{
if (length >= MaxSize)
throw "上溢";
if (i < 1 || i > length + 1)
throw "位置非法";
for (int j = length; j >= i; j--)
data[j] = data[j - 1]; //第j個元素存在數(shù)組下標(biāo)為j-1處
data[i - 1] = x;
length++;
}
template <typename DataType>
DataType SeqList<DataType>::Remove(int i)
{
if (length == 0)
throw "下溢";
if (i < 1 || i > length)
throw "位置非法";
DataType x = data[i - 1];
for (int j = i; j < length; j++)
data[j - 1] = data[j]; //此處j已經(jīng)是元素所在的數(shù)組下標(biāo)
length--;
return x;
}
template <typename DataType>
int SeqList<DataType>::Search(DataType x)
{
for (int i = 0; i < length; i++)
if (data[i] == x)
return i + 1; //下標(biāo)為i的元素其序號為i+1
return 0; //退出循環(huán)内斯，說明查找失敗
}
template <typename DataType>
void SeqList<DataType>::PrintList()
{
for (int i = 0; i < length; i++)
cout << data[i] << " ";
cout << endl;
}
template <typename DataType>
int SeqList<DataType>::Length() { return length; }
template <typename DataType>
int SeqList<DataType>::getData(int i)
{
if (length == 0)
throw "下溢";
if (i < 1 || i > length)
throw "位置非法";
return data[i - 1];
}
template <typename T>
void Union(SeqList<T> &LA, SeqList<T> &LB)
{
int n1 = LA.Length(), n2 = LB.Length();
int i, k;
T x;
for (i = 0; i < n2; i++)
{
x = LB.getData(i + 1); //在LB中取一元素
k = LA.Search(x); //在LA中搜索它
if (k == 0) //若在LA中未找到插入它
{
LA.Insert(n1, x);
n1++;
} //插入到第n個表項位置}
}
}
template <typename T>
void Intersection(SeqList<T> &LA, SeqList<T> &LB)
{
int n1 = LA.Length();
T x;
int k, i = 0;
while (i < n1)
{
x = LA.getData(i + 1); //在LA中取一元素
k = LB.Search(x); //在LB中搜索它
if (k == 0) //若在LB中未找到
{
LA.Remove(i + 1);
n1--;
} //在LA中刪除它
else
i++;
}
}
四蕴潦、運行與測試
1. 測試環(huán)境
運行環(huán)境：Windows 20H2, i7-9750H @ 2.60GHz, 16GB RAM
編譯器：gcc version 8.1.0 (x86_64-posix-seh-rev0, Built by MinGW-W64 project)
編譯命令：-g
運行終端：cmd
2. 在調(diào)試程序的過程中遇到的問題與解決方案
暫未發(fā)現(xiàn)異常。
3. 程序的運行結(jié)果
運行結(jié)果（符合預(yù)期）
D:\OneDrive - mail2.sysu.edu.cn\MyDocuments\code\DSA\week04\集合的并與交>SeqList_main.exe
a: 1 2 3 4 5
b: 0 4 5 6
Union(a, b): 1 2 3 4 0 6 5
c: 1 2 3 4 5
d: 0 4 5 6
Intersection(c, d): 4 5
六俘闯、總結(jié)與心得
- 鏈表是實現(xiàn)集合的并與交的一種可行的數(shù)據(jù)結(jié)構(gòu)潭苞。但如果想獲得更好的性能，可以考慮紅黑樹真朗，C++ STL 中的 set 就是這么實現(xiàn)的此疹。
