C++ 集合數(shù)據(jù)結(jié)構(gòu)Set

數(shù)據(jù)結(jié)構(gòu)是一個(gè)容器，用于將一些數(shù)據(jù)組織到單個(gè)對(duì)象中。我們已經(jīng)見過了幾個(gè)數(shù)據(jù)結(jié)構(gòu)，比如apstring是一些字符組成，而apvector是一組相同類型（可以是任意數(shù)據(jù)類型）的元素組成。

有序集是由一些項(xiàng)組成的集合，它有兩個(gè)決定性的屬性：

有序性：集合中的元素都有一個(gè)相應(yīng)的索引。我們可以通過這些索引確定集合中的元素。

唯一性：集合中每個(gè)元素只能出現(xiàn)一次。向集合中添加一個(gè)已經(jīng)存在的元素是沒有效果的。

此外，我們實(shí)現(xiàn)的有序集還有下面一個(gè)屬性：

大小任意：隨著我們向集合中添加元素，它會(huì)擴(kuò)充以容納新元素。apstring和apvector都是有序的；每個(gè)元素都有一個(gè)索引，我們可以通過索引來確定元素。但是我們見到的數(shù)據(jù)結(jié)構(gòu)都不具有唯一性和大小任意這兩個(gè)屬性。

要滿足唯一性，我們編寫的add函數(shù)必須先查找以確定集合中是否存在要添加的元素。集合隨著添加元素?cái)U(kuò)張這一特點(diǎn)可以利用apvector的resize函數(shù)實(shí)現(xiàn)。

下面是Set類定義的開始部分：

class Set {
private:
  apvector<apstring> elements;
  int numElements;

public:
  Set (int n);

  int getNumElements () const;
  apstring getElement (int i) const;
  int find (const apstring& s) const;
  int add (const apstring& s);
};

Set::Set (int n)
{
  apvector<apstring> temp (n);
  elements = temp;
  numElements = 0;
}

實(shí)例變量包括字符串的向量和記錄集合中有多少元素的整型數(shù)。一定要記住集合中的元素?cái)?shù)numElement與apvector的大小不是一個(gè)東西。通常前者會(huì)小一些。

Set的構(gòu)造函數(shù)接受一個(gè)參數(shù)，該參數(shù)是apvector的初始大小。元素個(gè)數(shù)初始值總是0。

getNumElements和getElement是私有實(shí)例變量的訪問函數(shù)。 numElements是只讀變量，所以我們只提供了get函數(shù)而沒有提供set函數(shù)。

int Set::getNumElements () const
{
  return numElements;
}

為什么我們必須阻止客戶程序修改getNumElements呢？ 因?yàn)檫@是該類型的不變式，客戶程序怎么能破壞不變式呢。我們看下Set其余的成員函數(shù)，看你能否說服自己它們都維護(hù)了不變式。

當(dāng)我們使用[]操作符訪問apvector時(shí)，它會(huì)檢查并確認(rèn)索引值大于等于0且小于向量的長(zhǎng)度。不過要訪問集合的元素，我們需要更強(qiáng)的條件驗(yàn)證。index必須小于元素?cái)?shù)，元素?cái)?shù)可能是個(gè)比向量長(zhǎng)度小的值。

apstring Set::getElement (int i) const
{
  if (i < numElements) {
    return elements[i];
  } else {
  cout << "Set index out of range." << endl;
  exit (1);
  }
}

如果getElement得到的索引值超出了范圍，它會(huì)打印錯(cuò)誤信息（我承認(rèn)，并不是最有用的信息）后退出。 find和add是比較有趣的函數(shù)。到目前為止，遍歷和查找的模式還是老樣子：

int Set::find (const apstring& s) const
{
  for (int i=0; i<numElements; i++) {
    if (elements[i] == s) return i;
  }
  return -1;
}

現(xiàn)在就剩下add了。像add這樣的函數(shù)的返回類型一般是void，不過在這個(gè)例子中，更有意義的可能是返回元素的索引。

int Set::add (const apstring& s)
{
  // 如果元素已經(jīng)在集合中，返回其索引
  int index = find (s);
  if (index != -1) return index;

  // 如果apvector滿了，將它的大小調(diào)整為原來的2倍
  if (numElements == elements.length()) {
  elements.resize (elements.length() * 2);
  }

  // 添加新元素并返回其索引
  index = numElements;
  elements[index] = s;
  numElements++;
  return index;
}

這里有個(gè)技巧，numElements會(huì)以兩種方式使用：其一就是表示集合中的元素?cái)?shù)目，其二是用作下一個(gè)要添加的元素的索引。

可能要花點(diǎn)時(shí)間才能相信這行得通，但是考慮一下：當(dāng)元素?cái)?shù)目為0時(shí)，下一個(gè)要加入元素的索引也是0。當(dāng)元素?cái)?shù)目等于向量的長(zhǎng)度時(shí)，這就說明向量已經(jīng)滿了，要加入新元素必須先通過resize分配更多的空間。

下面是一個(gè)Set對(duì)象的狀態(tài)圖，該對(duì)象初始包含2個(gè)元素的空間： 

現(xiàn)在我們可以使用Set類來記錄在文件中找到的城市。在main函數(shù)中我們以2為初始大小創(chuàng)建Set對(duì)象：

Set cities (2);

然后在processLine函數(shù)中我們把兩個(gè)城市添加到Set中，并保存返回的索引值。

int index1 = cities.add (city1);
int index2 = cities.add (city2);

我修改了processLine函數(shù)，使它以城市對(duì)象為第二個(gè)參數(shù)。