線性表的順序存儲結構 - 順序表

1. 順序表的定義

? 用一組地址連續的存儲單元依次存儲線性表的數據元素，從而使邏輯上相鄰的兩個元素在物理位置上也相鄰

2. 順序表的特點

• 隨機訪問： 即通過首地址和元素序號可以在O(1) 時間內找到指定元素！
• 存儲密度高： 每個節點只存儲數據節點！（鏈表還要存儲指針）
• 不宜與插入刪除與擴容： 進行這些操作需要進行大量的元素移動操作！

3. 順序表的相關代碼（Dev-C++）

? 本代碼使用萬能頭文件，如果運行失敗，請自行修改頭文件！

• 順序表創建 - 靜態分配

#include<bits/stdc++.h>
#define MAXSIZE 10 //最大長度
using namespace std;typedef struct{int data[MAXSIZE]; //靜態數組存放數據元素int length;
}SeqList;//初始化順序表
void InitSeqList(SeqList &L){for(int i = 0 ; i < MAXSIZE ; i++ ){L.data[i] = 0;}L.length = 0;
}int main(){SeqList L;InitSeqList(L); return 0;
}

• 順序表創建 - 動態分配

#include<bits/stdc++.h>
#define INITSIZE 10 //初始長度
using namespace std;typedef struct{int *data; //動態分配數組的指針int length;int MAXSIZE; //最大長度
}SeqList;//初始化順序表
void InitList(SeqList &L){L.data = (int*)malloc(INITSIZE*sizeof(int));L.length = 0;L.MAXSIZE = INITSIZE;cout << "初始化鏈表最大長度為：" << L.MAXSIZE << endl; 
}void IncreaseSize(SeqList &L, int len){int *p = L.data;L.data = (int *)malloc((L.MAXSIZE + len)*sizeof(int));for(int i = 0 ; i < L.length ; i ++){ //復制數據到新申請的區域L.data[i] = p[i];}L.MAXSIZE = L.MAXSIZE + len; //增加長度free(p);  //釋放內存空間cout << "增加后鏈表最大長度為：" << L.MAXSIZE; 
}int main() {SeqList L;InitList(L);int len;cout << "現在進行動態鏈表長度擴充：(請輸入增加長度)："; cin >> len;IncreaseSize(L,len);return 0;
}

• 順序表的插入

? 順序表插入可以分解為兩個步驟：

? · 從后向前遍歷，將順序表中第 i 個元素及以后的元素都向后移動一個位置。

? · 將需要插入的元素 e 放入 L.data[i - 1] 的位置即可。

#include<bits/stdc++.h>
#define MAXSIZE 20
using namespace std;typedef struct{int data[MAXSIZE];int length;
}SeqList;void InitList(SeqList &L){for(int i = 0 ; i < MAXSIZE ; i++){L.data[i] = 0;}L.length = 5; //Test: L.length = 0; 這里初始化為長度為5，是為了下面輸出順序表可以看到 要不然測試的時候不會打印順序表！cout << "初始化后的順序表" << endl;for(int i = 0 ; i < L.length ; ++ i){cout << L.data[i] << " "; } cout << '\n'; 
}bool ListInsert(SeqList &L, int i, int e){if(i < 1 || i > L.length + 1) return false; //檢查要插入的位置是否合理if(L.length > MAXSIZE) return false; //檢查長度是否允許繼續插入for(int j = L.length ; j >= i ; -- j ){ //從后向前遍歷，一次向后挪動一個位置L.data[j] = L.data[j - 1];}L.length ++; //記得增加表長L.data[i - 1] = e;cout << "插入元素后的順序表" << endl;for(int i = 0 ; i < L.length ; ++ i){cout << L.data[i] << " "; } cout << '\n'; 
}int main(){SeqList L;int i, e;InitList(L);cout << "請輸入要插入的位置及元素：" << endl;cin >> i >> e; ListInsert(L, i, e);return 0;	
}

? 時間復雜度分析：

? 最好情況：要在最后一個位置插入元素，那么不需要移動元素，時間復雜度為O(1)。

? 最壞情況：要在表頭插入一個元素，那么所有元素都需要向后移動一個位置，時間復雜度為O(n)。其中 n 為表長度。

? 平均情況：要插入的元素插入到任何一個位置的概率相同，平均時間復雜度為O(n)。

• 順序表的刪除

? 順序表的刪除（這里指刪除第 i 個位置的元素）可以分為兩個步驟：

? · 將第 i 個位置的元素賦值給 e。這個目的是傳回，如果沒必要的話其實可以不用這個步驟。

? · 從 i 位置開始向后遍歷，讓后面的元素都向前移動，填補刪除元素的位置。

#include<bits/stdc++.h>
#define MAXSIZE 10
using namespace std;typedef struct{int data[MAXSIZE];int length;
}SeqList;void InitList(SeqList &L){for(int i = 0 ; i < MAXSIZE ; ++ i){L.data[i] = 0;} L.length = 5; //Test: L.length = 5;cout << "初始化后的順序表" << endl;for(int i = 0 ; i < L.length ; ++ i){cout << L.data[i] << " "; } cout << '\n'; 
}bool ListDel(SeqList &L, int i, int &e){ //這里的e只是為了把刪除的元素帶回if(i < 1 || i > L.length) return false; //檢查合理性if(L.length == 0) return false;e = L.data[i - 1];for(int j = i ; j < L.length ; ++ j){L.data[j - 1] = L.data[j];}L.length --; //記得減少長度cout << "刪除后的順序表" << endl;for(int i = 0 ; i < L.length ; ++ i){cout << L.data[i] << " "; } cout << '\n'; return true;
}int main(){SeqList L;int i, e;InitList(L);cout << "請輸入要刪除第幾個元素" << endl;cin >> i;if(ListDel(L, i, e)){cout << "刪除成功！刪除的元素為：" << e << endl; }else{cout << "刪除失敗！" << endl;}return 0;
}

? 時間復雜度分析：

? 最好情況：刪除表尾元素，那么不需要移動元素，時間復雜度為O(1)。

? 最壞情況：刪除表頭元素，那么n - 1元素都需要向前移動一個位置，時間復雜度為O(n)。其中 n 為表長度。

? 平均情況：刪除任何一個位置的元素概率都相同，那么平均時間復雜度為O(n)。

• 順序表按位查找

? GetElem(L, i, e) 函數，傳入要查找的位號，即要查找第幾個元素，e是為了帶回該元素的值！

#include<bits/stdc++.h>
#define MAXSIZE 10
using namespace std;typedef struct{int data[MAXSIZE];int length;
}SeqList;void InitList(SeqList &L){for(int i = 0 ; i < MAXSIZE ; ++ i){L.data[i] = i;}L.length = 5; //Test: L.length = 5;cout << "初始化后的順序表" << endl;for(int i = 0 ; i < L.length ; ++ i){cout << L.data[i] << " "; } cout << '\n'; 
}int GetElem(SeqList &L, int i, int &e){if(i < 1 || i > L.length) return false;if(L.length == 0) return false;e = L.data[i - 1];return e;
}int main(){SeqList L;int i;int e;InitList(L);cout << "請輸入查找第幾個元素：" << endl; cin >> i;if(GetElem(L, i, e)){cout << "查找成功，該元素為：" << e << endl;}else{cout << "查找失敗！" << endl; }return 0;
}

? 時間復雜度分析： O(1)，因為可以直接通過索引訪問元素。

• 順序表按值查找

? LocateElem(L, e, loc) 函數，傳入要查找的元素值，loc 是為了帶回該元素的位序！

#include<bits/stdc++.h>
#define MAXSIZE 10
using namespace std;typedef struct{int data[MAXSIZE];int length;
}SeqList;void InitList(SeqList &L){for(int i = 0 ; i < L.length ; ++ i){L.data[i] = i;}L.length = 5; //Test: L.length = 0;cout << "初始化后的順序表" << endl;for(int i = 0 ; i < L.length ; ++ i){cout << L.data[i] << " "; } cout << '\n'; 
}int LocateElem(SeqList &L, int e, int &loc){for(int i = 0 ; i < L.length ; ++ i){if(L.data[i] == e){loc = i + 1;return loc;}}return false;
}int main(){SeqList L;int e;int loc;InitList(L);cout << "請輸入要查找的數值" << endl;cin >> e;if(LocateElem(L, e, loc)){cout << "查找成功，該元素位于第" << loc << "個位置！" << endl;}else{cout << "查找失敗！" << endl; }return 0;
}