數組

• 數組的時間復雜度
• 容器與數組
• 手動實現數組功能

數組是 線性表的數據結構，利用一組 連續的內存空間存儲一組具有 相同類型的數組。也正因為這種特性使得數組在內存上的存儲有一定的限制， 無法利用零碎的內存空間存儲某些數據。

數組的時間復雜度

• 數組因為支持隨機訪問，根據數組下標的隨機訪問使得其時間復雜度為O(1)

• 數據插入：假定數組的長度為N，當需求將某個數據插入到K（k<n)位置上時，前K個位置的數據位置維持原樣保持不變，但K~N位置的數據需要往后移一個位置給該數據，因此雖然讀取K位置的數據方便，但是在插入階段使得要經過一個內存拷貝的過程。當利用極限的思維去考慮，假設在第1位插入的話，那么N個數據都將往后移一位，所以最壞的時間復雜度是O(n)，最好情況下則是插入在末端，一個數據都不會后移拷貝，最好的時間復雜度為O(1)，利用數學期望計算平均的時間復雜度則為（1+2+3+4+···+n）/n = O(n)。

• 數據刪除：與數據插入類似，在刪除任意位置的數據后需要將該數據后的數據部分向前拷貝一步，維持數組內存位置連續的要求，因此最壞的時間復雜度O(n)，最好的時間復雜度O(1)，平均時間復雜度為O(n)。

容器與數組

C++的STL庫中有vector容器，將數組的很多細節封裝起來，在使用的時候可以放心使用也不用過分擔心內存泄漏相關的問題，但是不是有了vector容器就直接拋棄掉數組了呢？

傳統數組在使用過程中需要預先指定內存大小，當超出邊界后則需要重新申請內存，復制過去才能重新插入，vector則使這一操作簡單化，動態擴容使數據操作變得簡單，而且對數據的實現細節也能夠得到較好的封裝，大部分情況下業務開發，使用容器的確能夠達到一勞永逸的效果。

如果數據大小已知，并且相關的數據操作較簡單，就沒必要動用容器vector，并且在底層開發時需要優化性能，在盡量不用容器的情況下，適當使用數組也是可以的。

手動實現數組功能

#pragma once #include<iostream>class ARRAY { private:int size;int used;int* arr;public://默認構造函數ARRAY(int s = 0);//復制構造函數ARRAY(const ARRAY& AR);//析構函數~ARRAY() { delete[]arr; }//重載賦值運算符void operator=(const ARRAY& AR);//打印所有數組元素void dump();//插入元素bool insert(int elem);//搜索值元素void search(int num);//刪除某個元素bool deleteelem(int num);//顯示數組首地址void showadd(); }; #pragma once #include"array.h" #include<cstring> using namespace std;ARRAY::ARRAY(int s) {size = s;used = 0;this->arr = new int[size];if (this->arr == NULL)cout << "NEW error!\n";for (int i = 0; i < size; ++i){this->arr[i] = 0;} }ARRAY::ARRAY(const ARRAY& AR) {this->size = AR.size;this->used = AR.used;arr = new int[size];memcpy(arr, AR.arr, AR.size * sizeof(int)); }void ARRAY::operator=(const ARRAY& AR) {this->size = AR.size;this->used = AR.used;arr = new int[size];memcpy(arr, AR.arr, AR.size * sizeof(int)); }void ARRAY::dump() {for (int i = 0; i < this->used; ++i){cout << "[ " << i + 1 << " ] == ";cout << this->arr[i] << endl;} }bool ARRAY::insert(int elem) {if (this->used >= this->size){int tempsize = this->size;ARRAY temp(2 * tempsize);//模擬動態開辟內存，下面調試結果得到驗證temp.used = tempsize;memcpy(temp.arr, this->arr, this->size * sizeof(int));temp.arr[temp.used++] = elem;delete[]this->arr;*this = temp;return true;}this->arr[this->used++] = elem;return true; }void ARRAY::search(int num) {for (int i = 0; i < used; ++i){if (this->arr[i] == num){cout << "LOCATION == " << i << endl;return;}}cout << "NO SUCH " << num << " NUMBER\n"; }bool ARRAY::deleteelem(int num) {if (num < 0 || num > this->size){cout << "UNDEFINED AREA\n";return false;}else if (num > used){cout << "UNDEFINED VALUE\n";return false;}elsefor (int i = num - 1; i < used - 1; ++i)this->arr[i] = this->arr[i + 1];this->used--;return true; }void ARRAY::showadd() {cout << "Now array first address == ";cout << (void*)this->arr << endl; } #include"array.h"int main() {ARRAY myarray(3);ARRAY hisarray(3);myarray.insert(1);myarray.insert(3);myarray.insert(6);myarray.dump();myarray.showadd();myarray.search(4);myarray.search(3);hisarray = myarray;hisarray.dump();hisarray.showadd();myarray.insert(20);myarray.dump();myarray.showadd();return 0; }

輸出結果

[ 1 ] == 1 [ 2 ] == 3 [ 3 ] == 6 Now array first address == 010DCE38 NO SUCH 4 NUMBER LOCATION == 1 [ 1 ] == 1 [ 2 ] == 3 [ 3 ] == 6 Now array first address == 010DCE70 [ 1 ] == 1 [ 2 ] == 3 [ 3 ] == 6 [ 4 ] == 20 Now array first address == 010DF178

總結

以上是生活随笔為你收集整理的数据结构 数组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。