從零開始實現數據結構(二) 有序數組
- 2019 年 10 月 3 日
- 筆記
有序數組顧名思義就是數組內所有元素的排列都是按照一定的順序的。不管插入元素是多少，有序數組都會自動將該元素插入合適的位置。這裡要實現的是一個定長的有序數組。
一.有序數組COrderArray類
要實現一個有序數組，首先應該考慮這個數組應該要實現什麼樣的功能：
1.構造函數，初始化數組，給定指定的數組長度。
2.插入數據，最重要的功能，插入的數據自動按照順序排好。
3.按照指定值查找，有序數組有一個很重要的特點就是很方便查找某一個特定值。
4.按照指定的位置查找，這個功能也相當於為重載 [] 下標運算符，這樣就可以像普通的數組一樣通過下標訪問有序數組的元素。
5.刪除指定位置的元素。
6.刪除指定值的元素。
7.清空所有元素。
8.合併兩個有序數組，這個功能也是刷算法題可能會遇到的一種類型的題目。
理清楚大概要實現什麼樣的功能，就可以開始寫頭文件的函數聲明。
#pragma once #include "CArray.h" class COrderArray ://依然是繼承數組基類 public CArray { public: COrderArray(int size);//構造函數 void PushBack(int value);//插入數據 void RemoveForValue(int value);//根據指定值刪除數組元素 void RemoveForPos(int pos);//根據指定位置刪除數組元素 int FindForValue(int value);//根據指定值查找數組元素 int &operator[](int pos); //重載下標運算符，達到按位置操作數組元素的目的 //重載下標運算符的時候，這裡的返回值必須是引用類型 void Clear();//清空所有元素 void Merge(COrderArray& array);//合併兩個有序數組 private: void _InsertElement(int value, int start); //因為在數組中插入值的時候會將該位置後的所有的元素都向後移一個位置，參數為插入值和後移的初始位 //所以單獨寫一個私有函數來完成插入並後移的功能，防止函數體內容太多，該函數也是不能在外部去調用 void _RemoveElement(int pos); //和上面同理，這個函數是用來刪除數組中某個位置的元素，刪除完成後把該位置後面的元素前移 //注意：這兩個函數和上面的的插入、刪除函數的不同之處在於上面兩個公有函數負責給用戶調用 //並且實現用什麼樣的策略去刪除或者插入，它們是內部調用下面的兩個私有函數 //而這兩個私有函數只是是完成插入和刪除的功能 };其他的成員函數以及成員變量在CArray數組基類中已經定義了，這裡就不用再寫。
二.COrderArray類的具體實現
1.構造函數
因為這是一個定長的有序數組，所以構造函數需要給定一個n，然後把數組的容量設置為n
COrderArray::COrderArray(int size) { m_Capacity = size; mp_Array = new int[m_Capacity]; }2.插入元素
有序數組每插入一個元素都要考慮插入的位置，確保插入以後整個數組依然是有序的。所以插入元素以前要把當前要插入的元素和數組已經有的元素大小進行比較。可以採用順序比較的方法，即從最小的元素開始比較。
但是因為這是一個有序數組，順序比較的方式會顯得很笨重，在這裡使用二分法是最好的。即首先確定一個初始位和末尾位，然後兩個位置中間的元素。如果要插入的元素比中間的元素大，則把起始位重新設置為現在的中間位置、，然後重新計算新的中間位，再比較中間位。這樣的好處是很快就能找到合適的插入位置。
//插入元素，判斷元素大小來決定其應該在數組中位置 void COrderArray::PushBack(int value) { //數組元素個數已經達到數組最大容量，直接返回 if (m_Size == m_Capacity) { return; } //二分查找 int start = 0; int end = m_Size; int mid = (start + end) / 2; while (1) { //數組還沒有元素的時候，直接插入 if (m_Size == 0) { mp_Array[m_Size] = value; break; } //循環跳出的條件，即mid與首尾之一相等 if (mid==start||mid==end) { if (mp_Array[mid] > value)//如果最後一次循環時，mid位置的元素大於插入位置的元素 { _InsertElement(value, mid);//對當前mid位置，調用插入元素的函數 break; } //若最後一次循環時，mid位置元素小於插入位置的元素 //對mid位置後面的一個位置，調用插入元素的函數 _InsertElementvalue, mid + 1); break; } //二分法，比較插入元素和中間元素的大小，然後改變mid的值 if (mp_Array[mid] > value)//插入元素比中間元素小，end改為mid，mid根據新的end更新一下 { end = mid; mid = (start + end) / 2; } else//插入元素比中間元素大，start改為mid，mid根據新的start更新一下 { start = mid; mid = (start + end) / 2; } } m_Size++; }二分法的過程比較適合在紙上一步一步畫出來，就很容易理解這個過程。
在剛剛的函數中只是實現了去搜索插入元素應該插入的位置，實際上還並沒有完成插入，所以在循環結束的時候還調用了_InsertElement(value, mid)，來完成插入，並把插入位置後面的所有元素都後移一位。
**_InsertElement函數如下：**
//在數組中要插入的元素位置之後的所有元素進行後移 void COrderArray::_InsertElement(int value, int pos) { for (int i = m_Size; i > pos; i--) { mp_Array[i] = mp_Array[i - 1]; } mp_Array[pos] = value; }這裡只需要根據插入的位置，一個for循環把後面所有的元素移動一位，再插入新的元素即可。
3.根據指定值查找元素
根據值查找元素和上面的方法類似，使用二分查找。
//根據值查找，二分查找，和上面的插入類似 int COrderArray::FindForValue (int value) { int start = 0; int end = m_Size; int mid = (start + end) / 2; while (mid != start && mid != end) { if (mp_Array[mid] == value) { return mid; } if (mp_Array[mid] > value) { end = mid; mid = (start + end) / 2; } else { start = mid; mid = (start + end) / 2; } } if (mp_Array[mid] == value) { return mid; } }4.根據指定位置查找元素
這一個功能實際上和數組的下標索引是相同的，所以這個地方可以不寫函數，而是重載下標運算符。之前寫的動態數組也可以加入這一個功能。
int &COrderArray::operator[](int pos) { if (pos > m_Size || pos < 0) { return mp_Array[0]; } return mp_Array[pos]; }重載下標運算符的時候返回值是一個引用類型，而且最好是做一個越界的檢查，如果下標索引越界，就返回數組的第一個元素。
5.清空所有元素
和動態數組清空元素類似，只需要把當前元素個數置零即可。
//清空所有元素 void COrderArray::Clear() { m_Size = 0; }6.根據指定位置刪除元素
根據指定位置刪除數組元素只需要把要刪除的位置後面的所有元素都向前移動一個位置，這樣就自動覆蓋了要刪除的元素。而前面寫的_RemoveElement(int pos)函數功能就是將刪除元素，並指定位置後的元素向前移動，所有這裡可以直接考慮調用這個函數。
**_RemoveElement(int pos)如下：**
//刪除操作，把刪除的數後面每一個元素向前移動一個位置 void COrderArray::_RemoveElement(int pos) { if (pos >= 0 && pos < m_Size) { for (int i = pos; i < m_Size; i++) { mp_Array[i] = mp_Array[i + 1]; } m_Size--; } }根據指定位置刪除元素的函數：
//根據指定位置刪除元素 void COrderArray::RemoveForPos(int pos) { _RemoveElement(pos); }7.根據指定值刪除元素
要根據指定值刪除數組中的元素，首先其實還是要查找到數組中指定值，所以可以直接用前面寫的查找指定值的函數，用一個變量來接收返回的位置，找到以後再調用前面的的_RemoveElement(int pos)函數即可。
//根據指定值刪除元素 void COrderArray::RemoveForValue(int value) { int pos = FindForValue(value); _RemoveElement(pos); }8.合併兩個有序數組
要實現兩個有序數組的合併，有幾種思考方式，一種是使用一個新的對象來裝合併後的有序數組，這種開銷相對比較大。所以這裡選擇將第一個有序數組和第二個有序數組都合併到第一個裏面，並且不改變第二個數組。所以函數的參數就應該是第二個有序數組。
即 Merge(COrderArray& tempArray)
注意這裡使用的是COrderArray&，這是一個引用。當類對象做函數形參的時候通常都會使用引用的方式，因為使用引用不會調用拷貝構造函數，而是直接操作原來的對象，這樣可以減輕程序的開銷。
同時，如果在對象中包含有new出來的指針，一定得要使用引用的方式傳參。因為值傳遞會生成一個對象的副本，在結束的時候還會自動執行析構函數，會把原來對象new出來的指針delete掉。而在整個程序結束時，又會調用一次析構函數，這樣重複delete同一個指針，會運行出錯。而引用作參數則不會生成對象的副本，也不會調用析構函數。當然，如果對象本身沒有動態創建的變量，值傳遞也不會出太大的問題。
合併的思想主要是兩個數組依次比大小，小的就先放進新的數組中，然後繼續比下去。
因為這裡創建的是一個定長數組，所以得先開一個新的更大的內存空間，大小就為兩個數組容量之和，所以這裡的合併從後往前合併應該是更好的。
//合併兩個有序數組 void COrderArray::Merge(COrderArray& tempArray) { //開一個新的內存來存儲合併後的數組，首先需要計算新的內存需要多大 int tempArrayCapacity = tempArray.getCapacity(); int newCapacity = tempArrayCapacity + m_Capacity; int* newSpace = new int[newCapacity]; //因為原來數組的元素有可能沒有滿 //所以要從兩個數組當前size的位置開始合併 //tempsize即兩個數組的size之和 //pos是合併的時候的一個索引，每取出來一個元素，就放到newSpace[pos]，並-1，到0的時候就合併完 int tempArraySize = tempArray.getSize(); int tempSize = tempArraySize + m_Size; int pos = tempSize - 1;//索引要-1 //開始合併 while (pos >= 0) { //如果第一個數組元素個數不為0才進行比較 if (m_Size != 0) { //第一個數組元素大於傳參進來的數組元素 //或者第二個數組元素索引已經比較到0 //第一個數組的元素放進新開的內存空間，然後size-1 if (mp_Array[m_Size - 1] >= tempArray[tempArraySize - 1]) { newSpace[pos] = mp_Array[m_Size - 1]; m_Size--; } else { newSpace[pos] = tempArray[tempArraySize - 1]; tempArraySize--; } }else//如果第一個數組元素個數已經為0，直接把另一個數組的元素按順序放進來，不需要再進行比較 { newSpace[pos] = tempArray[tempArraySize - 1]; tempArraySize--; } pos--; } //清理掉要合併數組的原來的內存 //把size設置為新的合併後的size //數組容量設置為新的容量 //指針要指向新的存放數據的內存空間 delete[] mp_Array; m_Size = tempSize; m_Capacity = newCapacity; mp_Array = newSpace; }到這裡，所有的有序數組的功能就實現完畢，接下來是主函數來調用這個有序數組。
三.主函數Array.cpp
主函數主要是創建兩個有序數組對象，然後插入數據，可以看到插入的數據都是有序的，然後再合併兩個有序數組。
#include<iostream> using namespace std; #include "COrderArray.h" using namespace std; int main() { int n; cin >> n; //COrderArray* oArray = new COrderArray(n); COrderArray oArray(n); COrderArray oArray2(n); //插入第一個數組的數據 for (int i = 0; i < n; i++) { int temp; cin >> temp; oArray.PushBack(temp); } //插入第二個數組的數據 for (int i = 0; i < n; i++) { int temp; cin >> temp; oArray2.PushBack(temp); } oArray.Print();//打印數組 oArray.Merge(oArray2);//合併兩個數組 oArray.Print();//重新打印 return 0; }輸入數據： 6 9 4 6 11 5 8 7 10 6 18 2 4 輸出數據： print all date : 4 5 6 8 9 11 合併數組後的輸出數據： print all date : 2 4 4 5 6 6 7 8 9 10 11 18這樣就實現了一個有序數組就，這個地方和前面一樣也只是int作為數組的類型，並沒有使用模板，所以還可以擴展開來，實現更多的功能。最後給出所有文件的代碼。
所有文件源代碼
COrderArray.h文件的全部代碼如下：
#pragma once #include "CArray.h" class COrderArray ://依然是繼承數組基類 public CArray { public: COrderArray(int size);//構造函數 void PushBack(int value);//插入數據 void RemoveForValue(int value);//根據指定值刪除數組元素 void RemoveForPos(int pos);//根據指定位置刪除數組元素 int FindForValue(int value);//根據指定值查找數組元素 int &operator[](int pos); //重載下標運算符，達到按位置操作數組元素的目的 //重載下標運算符的時候，這裡的返回值必須是引用類型 void Clear();//清空所有元素 void Merge(COrderArray& array);//合併兩個有序數組 private: void _InsertElement(int value, int start); //因為在數組中插入值的時候會將該位置後的所有的元素都向後移一個位置，參數為插入值和後移的初始位 //所以單獨寫一個私有函數來完成插入並後移的功能，防止函數體內容太多，該函數也是不能在外部去調用 void _RemoveElement(int pos); //和上面同理，這個函數是用來刪除數組中某個位置的元素，刪除完成後把該位置後面的元素前移 //注意：這兩個函數和上面的的插入、刪除函數的不同之處在於上面兩個公有函數負責給用戶調用 //並且實現用什麼樣的策略去刪除或者插入，它們是內部調用下面的兩個私有函數 //而這兩個私有函數只是是完成插入和刪除的功能 };COrderArray.cpp文件的全部代碼如下：
#include<iostream> #include "COrderArray.h" COrderArray::COrderArray(int size) { m_Capacity = size; mp_Array = new int[m_Capacity]; } //在數組中要插入的元素位置之後的所有元素進行後移 void COrderArray::_InsertElement(int value, int pos) { for (int i = m_Size; i > pos; i--) { mp_Array[i] = mp_Array[i - 1]; } mp_Array[pos] = value; } //插入元素，判斷元素大小來決定其應該在數組中位置 void COrderArray::PushBack(int value) { if (m_Size == m_Capacity) { return; } //二分查找 int start = 0; int end = m_Size; int mid = (start + end) / 2; while (1) { //數組還沒有元素的時候，直接插入 if (m_Size == 0) { mp_Array[m_Size] = value; break; } //循環跳出的條件，即mid與首尾之一相等 if (mid==start||mid==end) { if (mp_Array[mid] > value) { _InsertElement(value, mid); break; } _InsertElement(value, mid + 1); break; } //大小判別，然後改變mid的值進行二分 if (mp_Array[mid] > value) { end = mid; mid = (start + end) / 2; } else { start = mid; mid = (start + end) / 2; } } m_Size++; } //根據值查找，二分查找，和上面的插入類似 int COrderArray::FindForValue (int value) { int start = 0; int end = m_Size; int mid = (start + end) / 2; while (mid != start && mid != end) { if (mp_Array[mid] == value) { return mid; } if (mp_Array[mid] > value) { end = mid; mid = (start + end) / 2; } else { start = mid; mid = (start + end) / 2; } } if (mp_Array[mid] == value) { return mid; } } //刪除操作，把刪除的數後面每一個元素向前移動一個位置 void COrderArray::_RemoveElement(int pos) { if (pos >= 0 && pos < m_Size) { for (int i = pos; i < m_Size; i++) { mp_Array[i] = mp_Array[i + 1]; } m_Size--; } } //根據指定位置刪除元素 void COrderArray::RemoveForPos(int pos) { _RemoveElement(pos); } //根據指定值刪除元素 void COrderArray::RemoveForValue(int value) { int pos = FindForValue(value); _RemoveElement(pos); } //重載下標運算符 int &COrderArray::operator[](int pos) { if (pos > m_Size || pos < 0) { return mp_Array[0]; } return mp_Array[pos]; } //清空所有元素 void COrderArray::Clear() { m_Size = 0; } //合併兩個有序數組 void COrderArray::Merge(COrderArray& tempArray) { //開一個新的內存來存儲合併後的數組，首先需要計算新的內存需要多大 int tempArrayCapacity = tempArray.getCapacity(); int newCapacity = tempArrayCapacity + m_Capacity; int* newSpace = new int[newCapacity]; //從兩個數組當前size的位置開始合併 int tempArraySize = tempArray.getSize(); int tempSize = tempArraySize + m_Size; int pos = tempSize - 1; while (pos >= 0) { if (m_Size != 0) { if (mp_Array[m_Size - 1] >= tempArray[tempArraySize - 1]|| tempArraySize==0) { newSpace[pos] = mp_Array[m_Size - 1]; m_Size--; } else { newSpace[pos] = tempArray[tempArraySize - 1]; tempArraySize--; } }else { newSpace[pos] = tempArray[tempArraySize - 1]; tempArraySize--; } pos--; } delete[] mp_Array; m_Size = tempSize; m_Capacity = newCapacity; mp_Array = newSpace; }Array.cpp文件的全部代碼如下：
#include<iostream> using namespace std; #include "COrderArray.h" using namespace std; int main() { int n; cin >> n; //COrderArray* oArray = new COrderArray(n); COrderArray oArray(n); COrderArray oArray2(n); //插入第一個數組的數據 for (int i = 0; i < n; i++) { int temp; cin >> temp; oArray.PushBack(temp); } //插入第二個數組的數據 for (int i = 0; i < n; i++) { int temp; cin >> temp; oArray2.PushBack(temp); } oArray.Print();//打印數組 oArray.Merge(oArray2);//合併兩個數組 oArray.Print();//重新打印 return 0; }