好長時間沒寫新的文章, 一直都是在更新《C++ 學習筆記》, 這段時間來終於將 C++ 的樣板學完了. 之前說過, 學完樣板之後, 《資料結構》欄目的文章會重新開始發表. 但是在學習中, 我不斷地認識到以前的程式碼需要進行修改, 所以最終選擇進行重構

之前的資料結構文章中, 我們將順序表當作簡單的 int 型別的順序表, 但是這是不夠的. 從線性代數的角度來看, 一個順序表可以看作緯度為 1 的向量 vector 和一個行矩陣, 這是重構順序表的基礎. 另外, 當隨著知識儲存的提升, 我們將不再限於只用 int 型別, 而是要求這個順序表能夠容納任何的型別. 所以, 我們將運用 C++ 中的樣板進行重構

在本篇文章中, 我更傾向於將順序表當作向量 vector 來處理, 而不是順序表. 因為相對於向量來說, 它的功能太少了. 所以在之後, 我將會替換所有順序表的名稱為 向量. 也許你會不太習慣, 因為 C++ STL 中的 vector 只是一個可擴充的陣列, 而並不是向量. 但是, 數學和計算機科學的關係密不可分, 這也是我稱其為向量的其中一個原因

值得注意的是, 從這一次的《資料結構》文章開始, 我們都將會使用 C++ 泛型編程的方式來實現, 如果閣下對此不是非常了解, 可以詳細參考本人的文章《C++ 學習筆記》, 裡面對於 C++ template 有詳細的說明. 不過你需要有些許 template 基礎才可以. 所以, 每一次的資料結構, 都是可以是一次 C++ 實戰

之前的文章作為一個成長紀錄, 我將會暫時保留, 大家可以參考

我們開始介紹向量

向量在實際的程式設計當中, 其實使用陣列去實作的, 並且陣列的維度是一維的. 我們可以透過一張 SVG 圖像詳細了解向量


從圖中, 我們了解到向量中的元素是以直線型態的存儲方式儲存在陣列中, 並且支援插入和擦除. 在重構中, 我們不但支持了這個操作, 而且我們還進行了擴充, 即模仿 C++ STL 中的 emplace() 方法來豐富我們實作的向量的成員函式

所有的元素都可以用數學的表示方法表示 : (a1, a2, ..., an)

因此我們推斷出我們所需要的向量的兩個特性 :

  • 一個向量中所有資料的型別都是相同
  • 一個向量中兩兩相鄰的元素存在有序數對的關係 <ai, ai + 1>

實際的順序表還應該有一個特性 :

  • 存在最大長度, 即元素數目是有限

接下來我們開始成員函式的教學 :

1. 插入資料

我們首先還是來看一張 SVG 圖像

我們可以發現, 如果不是在最後一個位置插入元素, 會導致插入位置之後元素的位置移動

因此, 我們大致上可以分為 :

  • 在最後位置插入元素
  • 在非最後位置插入元素

第二種又可以分成在第一個位置插入和在中間插入, 不過對於向量而言, 這兩種其實並無分別. 因此, 我們可以呼叫在中間插入的函式將位置參數設定為 1 即可, 這樣避免了重複的程式碼

因為我們所需要的向量是可擴充的, 所以我們並不需要遞送具體的大小, 並且可以無限擴充. 所以我們不必擔心因為陣列容量的問題導致向量中的元素數目是固定的

2. 移除資料

與插入元素不同的是, 擦除元素之前, 我們需要判斷向量中是否真的存在元素. 如果不存在, 我們需要擲出向量中不存在元素這樣的例外情況

與插入相似的是, 除了在最後的位置擦除元素之外, 在其它位置移除元素都將會改變刪除位置之後所有元素的位置

3. 搜尋資料

在向量中查找資料可以說是向量其中一個需要操作, 但是我並不推薦直接將其設定為成員函式, 而是通過泛型演算法的形式, 通過疊代器進行搜尋

需要額外說明的是, 我們目前設計的類別並不帶疊代器和記憶體配置器這樣的操作. 通過不斷重構, 我們將會讓所有資料結構都支持這樣的操作, 並且讓它們可以被用於泛型演算法. 具體的文章最後會有介紹

我們希望演算法可以查找一個資料, 也可以搜尋一批資料

4. 運算子

除去普通的比較運算子和指派運算子之外, 向量還應該支援一元的正負運算子 ("+" 與 "-"). 即正運算子什麼也不做, 一元取反運算子將所有的資料變為相反數, 不過需要資料中的型別支援這種運算子才可以

 

除去上述操作之外, 向量還有一些基本的操作就是清空、判空、獲取等操作, 對於記憶體配置器來說, 還會有一些額外的操作, 但是這些並不建議隨意使用

關於程式碼, 從本次的《資料結構》文章開始, 我們將以 GitHub 網址的形式發布在文章中, 因為程式碼是需要不斷去修改的, 每一次修改都要編輯文章是一件挺麻煩的事情, 所以大家可以直接上本人的 GitHub 上觀看具體的實作

當然, 最好是能根據本文的思路, 自己寫過一個喇~

資料結構 Vector : GitHub 點擊直達

資料結構 Vector 使用說明 : GitHub 點擊直達