資料結構第二課 | 順序表（詳解）

前言：Hello！大家好，我是@每天都要敲代碼，上次我們講了資料結構第一課時間複雜度和空間複雜度；不明白的小夥伴可以學習一遍時間複雜度和空間複雜度傳送門；今天讓我們開始一起學習資料結構第二課啦-----線性表；在學習線性表之前，我們要先弄清楚它的概念，下面讓我們一起來看看吧！

概念：

線性表：線性表是n個具有相同特性的資料元素的有限序列。線性表是一種在實際中廣泛

使用的資料結構，常見的線性表：順序表、連結清單、棧、隊列、字元串....

解釋：線性表在邏輯上是線性結構，也就是連續的一條直線。但是在實體結構上并不一定是

連續的，線性表在實體上存儲時，通常以【數組】和【鍊式結構】(連結清單)的形式存儲

 數組空間是連續的，連結清單空間是不連續的。

順序表實作：順序表是用一段【實體位址連續】的存儲單元【依次存儲資料元素】的線性結構，一般情況下采用數組存儲。在數組上完成資料的增删改查。

順序表一般可以分為：

                   1.靜态順序表：适應定長數組存儲。

                   2.動态順序表：使用動态開辟的數組存儲

目錄

靜态順序表：

動态順序表：

1.先建立順序表：struct SqList

2.進行初始化：SqListInit

3.列印函數：SqListPrint

4.尾插函數：SqListPushBack

擴容函數：SqListExpasion

5.頭插函數：SqListPushFront

6.尾删函數 SqListPopBack

7.頭删函數 SqListPopFront

8.修改：SqListModify 

 查找：SqListFind

9.任意位置插入：SqListInsert

10.任意位置删除：SqListDelete

11.銷毀：SqListDestory

所有具體代碼：

補充題目1： 原地移除元素

補充題目2：合并兩個有序數組

總結： 

    靜态連結清單的形式很簡單，但是容量的大小其實是寫死了，不太實用；我們先寫出靜态連結清單感受一下吧：

靜态順序表：

     我們先對順序表進行初始化，那麼傳參怎麼辦呢？傳值還是傳址？它要改變原來的資料，當然是傳址啦；初始化有兩種方法，自己選擇一種适合自己使用就可以；

    第二步我們就把相對簡單的列印函數寫出來了；

    第三步我們就進行尾插，在插入的時候我們就發現了靜态順序表的弊端，我們首先要進行判滿，滿了就不能插了，隻能手動進行擴容，擴小了造成來回擴容，很麻煩；擴大了又會造成浪費，那麼該怎麼辦？我們不妨寫成動态順序表的形式；是以下面的函數接口我就不在寫了；直接寫成動态順序表的形式吧！！！

動态順序表：

      對于動态順序表我們就把常用的接口函數都寫出來吧，雖然稍微有點複雜，不要怕，我們一個一個接口函數來解決：

1.先建立順序表：struct SqList

   包括存儲資料的數組arr，用malloc建立出來、有效資料的個數sz、容量capacity；下面一起來實作吧:

2.進行初始化：SqListInit

    我們同樣也需要傳址！！！在寫初始化接口函數之前，我們首先要思考，要初始化什麼？怎麼初始化？

第一種初始化方式：首先我們要肯定要用malloc先動态申請空間，申請空間的大小就是上面定義的宏常量INIT_MAX的大小；值得注意的是malloc開辟空間是以位元組為機關開辟的；之後還是把sz的大小初始化為0，容量capacity的大小初始化為INIT_MAX的大小。

第二種初始化方式：當然你也可以像航哥一樣，才開始把ps->arr=NULL，ps->sz=0，  ps->capacity = 0；我們插入的時候直接realloc進行擴容；這裡就需要老鐵對malloc和realloc有一定的了解了，我們思考一下，當realloc初始傳一個空指針，是不是相當于malloc的作用呢？不妨自己去嘗試一下吧！并且寫成這種形式，我們在直接用reallo直接擴容之前，要把capacity初始化一個值，不然（倍數*capacity=0）就永遠為0了；我們一般擴容為原來的兩倍。

下面兩種方式的擴容都給出來，選擇自己習慣的就好；我是比較偏向第一種方式，是以讀這篇部落格還是按照第一種初始化方式去了解：

第一種方式初始化：

 第二種方式初始化和擴容：

3.列印函數：SqListPrint

 同樣我們先把相對簡單的列印函數寫出來，以後需要直接調用這個函數就行：

4.尾插函數：SqListPushBack

擴容函數：SqListExpasion

    在尾插之前我們需要先判斷是否需要擴容，看ps->sz == ps->capacity；滿足我們就需要擴容，而且在哪裡插入都需要先判斷是否需要擴容；我們不妨封裝成一個函數，下面在使用直接調用就行，避免代碼備援；尾插我們在直接插入就行了，不需要資料的移動，很簡單：

 是否擴容成功呢？我們定義的初始capacity=4，我們不如來多輸入幾個數來測試一下：

 能正常列印出來，說明我們已經擴容成功了！！！

5.頭插函數：SqListPushFront

     同樣在頭插之前我們需要先判斷是否需要擴容；頭插就不像尾插那麼簡單直接在後面插入資料；頭插需要往後移元素，把下标為0的位置留給新插入的資料；那麼怎麼移動呢？當然是從後面開始移動啦！從前面資料會被覆寫！！！

 頭插兩個資料11、12看運作結果：

 正常列印，說明頭插成功。

6.尾删函數 SqListPopBack

對于尾删也很簡單，直接讓ps->sz--通路不到最後一個元素就可以了：

 下面我們尾删兩個數試試：

發現9、10已經列印不出來了，尾删成功。

7.頭删函數 SqListPopFront

   對于頭删，也要先判斷是否為空表；我們同樣也要移動元素，從最前面開始，把資料一個個往前移；然後在把ps->sz--就可以啦：這裡可以再回過頭來去看一下頭插函數裡面的移動元素和這裡頭删函數移動元素的差別，對比着學習！！！

 下面頭删兩個元素，列印試試看：

正常删除頭兩個元素12和11，頭删除成功。

8.修改：SqListModify 

 查找：SqListFind

    在修改資料之前，我們肯定要先進行查找，根據資料的下标進行修改操作，是以不妨先封裝一個查找的函數SqListFind；根據這個查找函數找下标，然後在傳參進行修改：

 我們不妨修改一個元素試試，比如：把3改為300：

從這裡可以看出，完全是沒問題的。 

9.任意位置插入：SqListInsert

在任意位置插入；你可以有兩種了解，

一種直接給你下标pos，就把資料插入到pos裡；比如：我們直接給出下标pos=1的位置插入，這時我們插入之前就要判斷pos下标是不是越界；直接用assert(pos<ps->sz)斷言就可以。

另外一種了解你可以根據給出的具體資料，調用SqListFind查找函數傳回的下标pos，來進行插入；這時傳回的下标除了找不到是-1，其它的肯定傳回的是合法的值，是以不用越界判斷也是可以的。

這裡我們隻實作第一種了解：

 我們不妨在下标為0的元素前面插入100；看運作結果：

從這裡可以看出，完全是沒問題的。 

10.任意位置删除：SqListDelete

   同樣删除也是和任意位置插入一樣，有兩種了解；我們還是隻實作第一種了解，我們随意給定一個下标就可以删除這個下标的元素：

 我們不妨删除下标為1的資料；看運作結果：

 從這裡可以看出，完全是沒問題的，1被删除了。 

11.銷毀：SqListDestory

所有具體代碼：

補充題目1： 原地移除元素

補充題目2：合并兩個有序數組

    這兩道題目是航哥資料結構補充的兩道題目；我們在以前的部落格裡已經做過這兩道題目，這裡就不在說了，感興趣的小夥伴，不妨看看我的另外兩篇部落格，專門詳解了這兩道題目：傳送門1<原地移除元素>     傳送門2<合并兩個有序數組>

總結： 

       當然你可以模仿通訊錄那樣寫一個詳細的菜單，這裡就留給老鐵們自己動手寫一寫！今天的資料結構之順序表就學完了，希望對您有所收獲；等你完全一口氣能寫出這個順序表，不妨就嘗試把這個當成小項目來寫；建立SqList.h：用來存放函數的聲明、頭檔案的引用、結構體的定義、常量的定義等放在這裡面；建立SqList.c來寫具體函數的實作；建立tect.c來寫主函數、以及各個函數的調用等。