來自于C++程式設計的一個題目。實作一個集合類,要求實作以下4個操作。
(1)向集合中添加元素,如果集合中已存在元素則不添加
(2)從集合中移除元素,移除之前需要先判斷集合中元素是否存在
(3)重載+運算符,用以實作集合的求并集運算
(4)重載*運算符,用以實作集合的求交集運算
1.類的整體設計
該問題需要模拟實作集合類,我們可以使用數組來模拟集合,于是使用int items[100]用來存放集合中的資料。為了實作數組的周遊,這就需要一個整數用來表示數組中元素的個數,于是使用int number來表示數組中元素的個數;此外,為了實作題目的需求,設計以下四個函數:
1.使用add_item(int item)成員函數向數組中添加元素
2.使用remove_item(int item)成員函數向數組中移除元素
3.重載operator+表示集合的求并集運算
4.重載operator*表示集合的求交集運算
另外,本人從事線上教育多年,将自己的資料整合建了一個QQ群,有興趣一起交流學習c/c++的小夥伴可以加群:941636044,裡面有大神會給予解答,也會有許多的資源可以供大家學習分享,歡迎大家前來一起學習進步!
由于向集合添加元素之前,必須確定集合中不存在該元素;在從集合中移除元素之前,必須確定集合中存在該元素,是以添加is_exist(int item)方法用以判斷集合中是否存在這個元素;此外為了顯示集合,添加display()方法, 基本設計如下:
class Set
{
public:
int items[100]; //定義一個數組作為容器存放100個集合元素
int number; //定義數字i表示集合中元素的個數
//構造函數和析構函數
Set() {
this->number = 0;
memset(this->items,0,sizeof(items));
}
//初始化方法
int init(int items[], int num);
//添加元素
bool add_item(int item);
//删除元素
bool remove_item(int item);
//求集合的并集
Set operator+ (Set set2);
//求集合的交集
Set operator* (Set set2);
//顯示集合元素
int display();
//判斷集合當中是否存在item,傳回元素在集合中的位置,不存在傳回-1
int is_exist(int item);
};
2.構造函數
Set() {
this->number = 0;
memset(this->items,0,sizeof(items));
}
在構造函數中,我們對數組進行初始化,聲明完數組之後,如果不進行初始化,數組元素是随機值,在C語言中,變量不進行初始化都會被配置設定随機值。為了避免這種情況,我們使用memset函數對數組items所有元素全部指派為0;同時,由于此時數組中沒有元素,即元素個數為0,我們的number也應當指派為0.
3.判斷數組中是否包含元素 item
int Set::is_exist(int item)
{
for(int i=0; i< this->number; i++) {
if(this->items[i] == item) {
return i;
}
}
return -1;
}
該函數用于判斷數組中是否存在item元素,如果存在就傳回item元素的位置,如果不存在就傳回-1. 判斷方法非常簡單,寫一個for循環從items[0]-items[number-1]一個一個進行周遊。如果相等,直接傳回i,此時i就是數組中item元素的位置;如果周遊完整個數組之後,都沒有發現與item相等的數組元素,說明數組中不存在item這個元素,于是傳回-1.
4.向數組中添加元素
bool Set::add_item(int item)
{
if(is_exist(item) >= 0 || this->number >= 100) {
return false;
}
this->items[this->number] = item;
this->number++;
return true;
}
首先判斷數組中是否存在該元素,如果存在則不能再向集合中添加元素,直接傳回false,如果不存在,則向數組中的number所指向的那個位置添加該元素,然後number作為數組元素個數的訓示器+1,這樣就完成了添加元素。
5.保護數組元素不被修改
寫到這裡,我們發現,數組元素個數訓示器this->number,對于該問題的幾個算法都起到了核心的作用,首先,我們依賴于數組元素個數訓示器周遊數組,如果number值遭到修改,會導緻無法周遊數組。舉個例子來說,當我們調用下列語句以後:
Set set1;
set1.add_item(1);
set1.add_item(2);
set1.add_item(3);
集合set1中的數組items變為[1,2,3],數組元素個數訓示器number=3,此時,如果我們還想向集合set1中添加元素20,我們需要利用number=3這個訓示器,讓set1.items[number]=20,并且讓number+1以指向下一個位置,即number=4。但是如果使用者手動修改number值,比如set1.number=50;此時,我們的number就不再能訓示數組元素的正确位置,進而導緻以上所有算法所依賴的number失效,是以,我們需要對數組本身,以及數組元素個數訓示器number進行私有化,以避免使用者随意篡改。于是:
class Set
{
public:
//構造函數和析構函數
Set() {
this->number = 0;
memset(this->items,0,sizeof(items));
}
//初始化方法
int init(int items[], int num);
//添加元素
bool add_item(int item);
//删除元素
int remove_item(int item);
//求集合的并集
Set operator+ (Set set2);
//求集合的交集
Set operator* (Set set2);
//顯示集合元素
int display();
//判斷集合當中是否存在item,傳回元素在集合中的位置,不存在傳回-1
int is_exist(int item);
private:
int items[100]; //定義一個數組作為容器存放100個集合元素
int number; //定義數字i表示集合中元素的個數
};
6. 從集合中移除元素
bool Set::remove_item(int item)
{
int pos = is_exist(item);
if(pos == -1) return false;
for(int i=pos; i< this->number-1; i++) {
this->items[i] = this->items[i+1];
}
this->number--;
return true;
}
首先檢查要移除的元素在結合中是否存在,如果不存在,則直接傳回false;其次,定位到集合中元素的位置,然後從這個位置開始将集合中剩餘的元素逐個前移,最後集合元素訓示器-1,并傳回true.
7. 求兩個集合的交集
Set Set::operator* (Set set2)
{
Set result;
for(int i=0; i< this->number; i++) {
if(set2.is_exist(this->items[i]) >= 0) {
result.items[result.number] = this->items[i];
result.number++;
}
}
return result;
}
算法很簡單,周遊集合A中的元素,對于A中的每一個元素判斷在集合B中是否存在,如果存在就加入到集合C當中,最後傳回集合C
8. 求兩個集合的并集
Set Set::operator+ (Set set2)
{
Set result;
for(int i=0; i<this->number; i++) {
result.items[result.number] = this->items[i];
result.number++;
}
for(int j=0; j<set2.number; j++) {
if(result.is_exist(set2.items[j]) == -1) {
result.items[result.number] = set2.items[j];
result.number++;
}
}
return result;
}
首先周遊集合A,将集合A中的元素全部加到集合C當中,然後周遊集合B,對于B中的每一個元素,首先判斷是否在A中存在,如果不存在則将其加入到集合C中,最終傳回集合C。
最後說一下,本人從事線上教育多年,将自己的資料整合建了一個QQ群,對于有興趣一起交流學習c/c++的初學者可以加群:941636044,裡面有大神會給予解答,也會有許多的資源可以供大家學習分享,歡迎大家前來一起學習進步!