來(lái)自于C++程序設(shè)計(jì)的一個(gè)題目。實(shí)現(xiàn)一個(gè)集合類，要求實(shí)現(xiàn)以下4個(gè)操作。
 1.向集合中添加元素，如果集合中已存在元素則不添加
 2.從集合中移除元素，移除之前需要先判斷集合中元素是否存在
 3.重載+運(yùn)算符，用以實(shí)現(xiàn)集合的求并集運(yùn)算
 4.重載*運(yùn)算符，用以實(shí)現(xiàn)集合的求交集運(yùn)算 

1.類的整體設(shè)計(jì)
該問(wèn)題需要模擬實(shí)現(xiàn)集合類，我們可以使用數(shù)組來(lái)模擬集合，于是使用int items[100]用來(lái)存放集合中的數(shù)據(jù)。為了實(shí)現(xiàn)數(shù)組的遍歷，這就需要一個(gè)整數(shù)用來(lái)表示數(shù)組中元素的個(gè)數(shù)，于是使用int number來(lái)表示數(shù)組中元素的個(gè)數(shù)；此外，為了實(shí)現(xiàn)題目的需求，設(shè)計(jì)以下四個(gè)函數(shù)：
 1）.使用add_item(int item)成員函數(shù)向數(shù)組中添加元素
 2）.使用remove_item(int item)成員函數(shù)向數(shù)組中移除元素
 3）.重載operator+表示集合的求并集運(yùn)算
 4）.重載operator*表示集合的求交集運(yùn)算
由于向集合添加元素之前，必須確保集合中不存在該元素；在從集合中移除元素之前，必須確保集合中存在該元素，因此添加is_exist(int item)方法用以判斷集合中是否存在這個(gè)元素；此外為了顯示集合，添加display()方法, 基本設(shè)計(jì)如下:

 class Set
{
public:
  int items[100]; //定義一個(gè)數(shù)組作為容器存放100個(gè)集合元素
  int number; //定義數(shù)字i表示集合中元素的個(gè)數(shù)
  //構(gòu)造函數(shù)和析構(gòu)函數(shù)
  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();
  //判斷集合當(dāng)中是否存在item,返回元素在集合中的位置，不存在返回-1
  int is_exist(int item);
}; 

2.構(gòu)造函數(shù)

 Set() {
  this->number = 0;
  memset(this->items,0,sizeof(items));
} 

在構(gòu)造函數(shù)中，我們對(duì)數(shù)組進(jìn)行初始化，聲明完數(shù)組之后，如果不進(jìn)行初始化，數(shù)組元素是隨機(jī)值，在C語(yǔ)言中，變量不進(jìn)行初始化都會(huì)被分配隨機(jī)值。為了避免這種情況，我們使用memset函數(shù)對(duì)數(shù)組items所有元素全部賦值為0；同時(shí)，由于此時(shí)數(shù)組中沒(méi)有元素，即元素個(gè)數(shù)為0，我們的number也應(yīng)當(dāng)賦值為0. 

3.判斷數(shù)組中是否包含元素 item

 int Set::is_exist(int item)
{
  for(int i=0; i< this->number; i++) {
    if(this->items[i] == item) {
      return i;
    }
  }
  return -1;
} 

該函數(shù)用于判斷數(shù)組中是否存在item元素，如果存在就返回item元素的位置，如果不存在就返回-1. 判斷方法非常簡(jiǎn)單，寫(xiě)一個(gè)for循環(huán)從items[0]-items[number-1]一個(gè)一個(gè)進(jìn)行遍歷。如果相等，直接返回i，此時(shí)i就是數(shù)組中item元素的位置；如果遍歷完整個(gè)數(shù)組之后，都沒(méi)有發(fā)現(xiàn)與item相等的數(shù)組元素，說(shuō)明數(shù)組中不存在item這個(gè)元素，于是返回-1. 

4.向數(shù)組中添加元素

 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;
} 

首先判斷數(shù)組中是否存在該元素，如果存在則不能再向集合中添加元素，直接返回false，如果不存在，則向數(shù)組中的number所指向的那個(gè)位置添加該元素，然后number作為數(shù)組元素個(gè)數(shù)的指示器+1，這樣就完成了添加元素。 

5.保護(hù)數(shù)組元素不被修改
寫(xiě)到這里，我們發(fā)現(xiàn)，數(shù)組元素個(gè)數(shù)指示器this->number，對(duì)于該問(wèn)題的幾個(gè)算法都起到了核心的作用，首先，我們依賴于數(shù)組元素個(gè)數(shù)指示器遍歷數(shù)組，如果number值遭到修改，會(huì)導(dǎo)致無(wú)法遍歷數(shù)組。舉個(gè)例子來(lái)說(shuō)，當(dāng)我們調(diào)用下列語(yǔ)句以后:

 Set set1;
set1.add_item(1);
set1.add_item(2);
set1.add_item(3); 

集合set1中的數(shù)組items變?yōu)閇1,2,3]，數(shù)組元素個(gè)數(shù)指示器number=3，此時(shí)，如果我們還想向集合set1中添加元素20，我們需要利用number=3這個(gè)指示器，讓set1.items[number]=20,并且讓number+1以指向下一個(gè)位置,即number=4。但是如果用戶手動(dòng)修改number值，比如set1.number=50;此時(shí)，我們的number就不再能指示數(shù)組元素的正確位置，從而導(dǎo)致以上所有算法所依賴的number失效，因此，我們需要對(duì)數(shù)組本身，以及數(shù)組元素個(gè)數(shù)指示器number進(jìn)行私有化，以避免用戶隨意篡改。于是:

 class Set
{
public:
  //構(gòu)造函數(shù)和析構(gòu)函數(shù)
  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();
  //判斷集合當(dāng)中是否存在item,返回元素在集合中的位置，不存在返回-1
  int is_exist(int item);
private:
  int items[100]; //定義一個(gè)數(shù)組作為容器存放100個(gè)集合元素
  int number; //定義數(shù)字i表示集合中元素的個(gè)數(shù)
}; 

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;
} 

首先檢查要移除的元素在結(jié)合中是否存在，如果不存在，則直接返回false;其次，定位到集合中元素的位置，然后從這個(gè)位置開(kāi)始將集合中剩余的元素逐個(gè)前移，最后集合元素指示器-1，并返回true.

7. 求兩個(gè)集合的交集

 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;
} 

算法很簡(jiǎn)單，遍歷集合A中的元素，對(duì)于A中的每一個(gè)元素判斷在集合B中是否存在，如果存在就加入到集合C當(dāng)中，最后返回集合C

8. 求兩個(gè)集合的并集

 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當(dāng)中，然后遍歷集合B，對(duì)于B中的每一個(gè)元素，首先判斷是否在A中存在，如果不存在則將其加入到集合C中，最終返回集合C

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論