計蒜客課程數據結構（順序表），數據結構

計蒜客課程數據結構（順序表），數據結構

1.線性表是由相同數據類型的 n 個數據元素a₀,a₁,......,a_n-1 組成的有限序列。一個數據元素可以由若干個數據項組成。若用 L 命名線性表，則其一般表示如下：

     L=(a₀,a₁,......,a_n-1)

其中， a₀​​ 是唯一的“第一個”數據元素，又稱為表頭元素；a_n-1​​ 是唯一的“最後一個”數據元素，又稱為表尾元素。

線性表按照存儲結構，可以分為順序表和鏈表兩種類型。

2.順序表是在計算機內存中以數組形式保存的線性表，是指用一組地址連續的存儲單元依次存儲數據元素的線性結構。

線性表中元素具有邏輯上的順序性。

線性表中所有元素的數據類型都是相同的。

線性表中的元素個數是有限的。

3.順序表最主要的特點是可以進行 隨機訪問，即可以通過表頭元素的地址和元素的編號（下標），在 O(1)O(1) 的時間復雜度內找到指定的元素。

順序表的不足之處是插入和刪除操作需要移動大量的元素，從而保持邏輯上和物理上的連續性。

4.順序表的構造，插入，擴容，刪除，遍歷

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 class Vector {
 5 private:
 6     int size, length;                //順序表當前的最大容量和當前順序表中的元素個數
 7     int *data;                       //動態分配，指向存儲元素的數組的指針
 8 public:
 9     Vector(int input_size) {         //構造函數，構造一個容量為input_size的順序表
10         size = input_size;
11         length = 0;
12         data = new int[size];        //讓data指向一段連續size個int空間
13     }
14     ~Vector() {                     //析構函數
15         delete[] data;              //將data指向的空間回收
16     }
17     bool insert(int loc, int value) {//順序表的插入
18         if (loc < 0 || loc > length) {//判斷插入的位置是否合法
19             return false;
20         }
21         if (length >= size) {           //判斷容量是否已經達到上限
22             return false;               //這句可注釋掉並調用擴容操作
23         }
24         for (int i = length; i > loc; --i) { //loc位置後元素後移
25             data[i] = data[i - 1];
26         }
27         data[loc] = value;
28         length++;
29         return true;
30     }
31     void expand(){                      //順序表的擴容
32         int *old_data=data;
33         size=size*2;
34         data=new int[size];
35         for(int i=0;i<length;i++){
36             data[i]=old_data[i];
37         }
38         delete[]old_data;
39     }  
40     int search(int value) {                 //順序表的查找
41         for (int i = 0; i < length; ++i) {
42             if (data[i] == value) {
43                 return i;
44             }
45         }
46         return -1;
47     }
48     bool remove(int index) {               //順序表的刪除
49         if (index < 0 || index >= length) {
50             return false;
51         }
52         for (int i = index + 1; i < length; ++i) {
53             data[i - 1] = data[i];
54         }
55         length = length - 1;
56         return true;
57     }
58     void print() {                            //順序表的遍歷
59         for(int i=0;i<length;i++){
60             if(i>0){
61                 cout<<" ";
62             }
63             cout<<data[i];
64         }
65         cout<<endl;
66     }
67 };
68 int main() {
69     Vector a(2);
70     cout << a.insert(0, 1) << endl;
71     cout << a.insert(0, 2) << endl;
72     a.print();
73     cout << a.remove(1) << endl;
74     a.print();
75     cout << a.search(0) << endl;
76     cout << a.search(1) << endl;
77     return 0;
78 }