實現(xiàn)典型數(shù)據結構的查找、添加和刪除數(shù)據 并分析其時間和空間復雜度

• 線性結構：

數(shù)組：是一種線性表數(shù)據結構，它用一組連續(xù)的內存空間，來存儲一組具有相同類型的數(shù)據。

1. 查找數(shù)據 ：隨機訪問

• 流程圖

/** ?查詢元素下標* ?參數(shù)1：Array_t數(shù)組結構體指針* ?參數(shù)2：元素值* ?返回：成功返回元素下標，失敗返回-1*/
int search(struct Array_t *array, int elem){int idx = 0;// 遍歷數(shù)組for (idx = 0; idx < array->used; idx++){// 找到與查詢的元素值相同的數(shù)組元素，則返回元素下標if (array->arr[idx] == elem){return idx;}// 如果數(shù)組元素大于新元素，說明未找到此數(shù)組下標, 則提前報錯退出// 因為本例子的數(shù)組是有序從小到大的if (array->arr[idx] > elem){break;}}// 遍歷完，說明未找到此數(shù)組下標，則報錯退出std::cout << "ERROR: No search to this" << elem << " elem." << std::endl;return -1;
}

• 復雜度分析（時間和空間）

時間復雜度：已知索引 O(1)；未知索引 O(n)；

空間復雜度：O(n)。

---

2.添加數(shù)據

• 流程圖

/** ?插入新元素* ?參數(shù)1：Array_t數(shù)組結構體指針* ?參數(shù)2：新元素的值* ?返回：成功返回插入的數(shù)組下標，失敗返回-1*/
int insertElem(struct Array_t *array, int elem){// 當數(shù)組被占用數(shù)大于等于數(shù)組長度時，說明數(shù)組所有下標都已存放數(shù)據了，無法在進行插入if (array->used >= array->length){std::cout << "ERROR: array size is full, can't insert " << elem << " elem." << std::endl;return -1;}int idx = 0;// 遍歷數(shù)組，找到大于新元素elem的下標idxfor (idx = 0; idx < array->used; idx++){// 如果找到數(shù)組元素的值大于新元素elem的值，則退出if (array->arr[idx] > elem){break;}}// 如果插入的下標的位置不是在末尾，則需要把idx之后的// 數(shù)據依次往后搬移一位，空出下標為idx的元素待后續(xù)插入if (idx < array->used){// 將idx之后的數(shù)據依次往后搬移一位memmove(&array->arr[idx + 1], &array->arr[idx], (array->used - idx) * sizeof(int));}// 插入元素array->arr[idx] = elem;// 被占用數(shù)自增array->used++;// 成功返回插入的數(shù)組下標return idx;
}

• 復雜度分析）

時間復雜度：未知索引 O(n)；

空間復雜度：O(n)。

• 可以改進

我們的數(shù)組是無序的，插入一個元素也不在乎順序，也沒有指定插入元素的位置，那么這時候就可以選擇直接插入尾部；如果插入元素時指定了一個插入位置，如果不關心順序的話也可以采用一種巧妙的辦法來實現(xiàn)：

public static void addByElement(int[] arr, int size, int index,int element) {if (null == arr || arr.length == 0){//數(shù)組是否為空return;}if (size >= arr.length){//確認數(shù)組至少有一個空位return;}arr[size] = arr[index];//將 index 和有效數(shù)組位數(shù)的最后一位交換arr[index] = element;

這里其實就是直接將需要插入元素的位置上的原有元素放到最后，然后再直接插入，避免了數(shù)組的移動，實現(xiàn)了?O(1)?時間復雜度的插入。

---

3.刪除數(shù)據

• 流程圖

/** ?刪除新元素* ?參數(shù)1：Array_t數(shù)組結構體指針* ?參數(shù)2：刪除元素的數(shù)組下標位置* ?返回：成功返回0，失敗返回-1*/
int deleteElem(struct Array_t *array, int idx){// 判斷下標位置是否合法if (idx < 0 || idx >= array->used){std::cout << "ERROR:idx[" << idx << "] not in the range of arrays." << std::endl;return -1;}// 將idx下標之后的數(shù)據往前搬移一位memmove(&array->arr[idx], &array->arr[idx + 1], (array->used - idx - 1) * sizeof(int));// 數(shù)組占用個數(shù)減1array->used--;return 0;
}

• 復雜度分析

時間復雜度：O(n)；

空間復雜度：O(n)。