知道一個算法的好壞怎么去判斷以后，就該正式的去學習一些常見的數據結構，當然，這里的數據結構僅僅是初階，不會挨個一個一個學完，后期慢慢來。

一、數據結構總論

一般按照邏輯結構和存儲結構來分類，在初階的學習時，雖不能全部學完，但基本每個類別都能見到例子。

1.按邏輯結構分類

按照邏輯結構分類，可以分為集合結構（數據元素同屬于一個集合，但是并沒有任何的關系）、線性結構（數據元素一對一，好像一條線一樣連在了一起）、樹形結構（數據元素一對多的關系，就好像一個樹的主干的根只有一個，但是他身上每一個節點都可能有好幾個樹枝）、圖狀/網狀結構（這種結構就類似于在天上俯瞰一個城市的公路一樣，每條路的十字看做一個數據元素的話，那就是多對多的關系）

2.按存儲結構分類

按照存儲結構有順序存儲（如數組，數組元素就是在內存中連續的存儲）、鏈式存儲（其實在C語言學習結構體的時候我們就已經見過怎樣建立一個鏈表節點，即一個數據域，一個地址，這個地址是指向鏈式存儲的下一個數據元素）、索引存儲、哈希存儲（根據散列函數的計算而定位數據元素）。

二、線性表

線性表是一類數據結構的總稱，這一類數據結構最明顯的特點就是邏輯上是線性的，但是物理上不一定是線性的。

也就是說，線性表在使用的時候，在我們的大腦中思考就是連續的、線性的，但實際上在內存中的存儲可不一定是順序存儲。

三、順序表

1.概述

這次學習的順序表就是屬于線性表，符合線性表的特征，即邏輯結構是線性結構，且數據順序存儲（底層實現類似于數組，或者說借助于數組）。

2.順序表和數組的區別

這個時候就有人要問了，既然你跟我說順序表借助于數組實現，那為啥不就當成數組呢。它們兩個的關系就類似于什么呢：
我相信基本上能跟編程打交道的，你說你自己一點也不玩游戲，我是不信的，甭管玩手機游戲還是電腦游戲，你要玩游戲最基本得有個設備吧，就說手機游戲，你弄個平板玩，正常就摟著玩就行了唄，但是有的人嫌舉著累，買個支架，又嫌自己打游戲的時候發熱會導致掉幀，卡的不行，又買了一個散熱器，手老出汗買個指套，更有甚者玩個手機游戲開加速器。

順序表和數組基本就是這樣的，數組只能存一系列數據，你存著只能取出來用，對里面的數據進行增刪改是很麻煩的，順序表在創建好以后，相當于數組+增加/刪除/修改/查找……一系列的輔助工具，幫助你對數據進行維護，數組就沒有這個條件。

3.順序表的聲明

①靜態順序表

靜態數據表就是用定長數組來存儲數據的，當然，并不等同于數組，一般都是這樣定義的：

#define定義是為了方便修改靜態順序表的大小，即底層的數組的大小，為什么要將數組的類型由typedef定義一下呢，直接寫個int不行嗎？

給順序表的數據的類型取別名也是為了方便修改順序表所存儲的數據類型。

這樣看來順序表也沒比數組好到哪去，只不過可以確定有效數據個數而已。

這么看當然看不出來順序表相對于數組的優點，因為正常情況下，比如用順序表來存儲雙11某用戶的訂單個數，這種玩意肯定是動態的，不能說你就給他7個大小的內存，假如就說成7個訂單，那萬一雙十一買的多了咋辦，難道還能讓用戶少買一點嗎？肯定是用戶創建的訂單決定數據存儲的大小，也就是經常用的就是動態順序表。

②動態順序表

動態和靜態的區別在哪里那，其實舉的小例子已經給出了，靜態的順序表存儲的數據個數是固定的，你給少了吧就不夠用，給多了吧，又給內存浪費了（不要小看內存浪費，一個人浪費1000個字節，人多起來再多的內存都不夠用）。

千萬不要說，那你說要多大，比如存7個int，我就給你#define N 7，你要幾我就定義幾，這真就是對程序的內存申請不了解啊，在C語言學習的時候不說別的，編譯的時候就給這個順序表的內存大小固定死了，你把N定義的值改了有什么用，你程序已經寫好了，軟件里就是這么大，你說改成9，那么軟件就不能用了，就得重新把你改好的應用到軟件里，你敢想象雙十一，特別是雙十一的晚上購物平臺提交不了訂單會造成多大的損失嗎，等你改好再上架，黃花菜都涼了。

因此，來看我們動態順序表的聲明（動態就是可以根據你給的數據，去調整申請的內存大小）。

因為要動態申請，所以提前準備一個指針，去接收不管是malloc還是calloc等去申請的那塊內存空間的地址，有效數據個數不用多說，而靜態順序表的大小是確定的，動態順序表只能動態計算去確定，因此多加一個capacity變量。

4.動態順序表的初始化

聲明好一個變量做的第一件事就是初始化，創建一個順序表也是如此：

信心滿滿的寫完了，然后：

？？？

你這破計算機犯什么毛病，我已經第六行就是給你初始化去的，你告訴我未初始化干嘛。

其實還是我們之前提過的一個問題，傳值調用和傳址調用。

傳值調用只是對實參的一個臨時拷貝，如果僅僅用于計算，無可厚非，但是如果想傳值用形參來實現修改實參的話，那還是想想算了。

形參的值不影響實參的值，出了函數還直接沒了。

如果相對實參進行修改，那還是傳地址過來吧，讓我順著地址給你修改：

又再次復習了一下，這次可就是傳值傳址調用的實例了，不再是空泛的硬憋出來的例子。

5.順序表的插入

尾插

比如這樣的數據：

想在尾部插入的話得有size吧，知道了size才能知道該插入的位置（即我們想象出來的下標），這塊內存空間的起始地址也得有吧，因此，干脆直接像初始化一樣，傳過來這個順序表的地址，你想去用這個順序表哪個成員就用哪個成員，最后另外寫出來一個參數，這個參數接收需要插入的元素：

當然，這么寫就是錯的，順序表只初始化是沒有對應的內存空間的，并沒有給這個順序表申請空間，是不能去賦值的，所以在此之前先懟一個內存開辟，由于考慮到內存可能溢出的問題，所以malloc calloc realloc用realloc，這樣如果第一次開辟的內存不夠用，可以自主開辟：

realloc第一個參數如果是NULL的話，效果和malloc是一樣的，因為需要修改的位置為空，那么就不需要修改，直接開辟即可，返回值仍需檢查。

調試結果就是這樣的，其實挺簡單的。

頭插

這個有兩個要注意的點，一個是頭插必須把已有的數據后移，空出來順序表最前面的位置；后移必后面的先移，不然就會導致數據的覆蓋：

最后空出來的賦值就簡單了，下面是代碼表達：

調試沒問題：

指定位置插入

其實如果空想的話，你給我的下標是幾，那我就把這個下標開始加上后面的全部都后移，最后在這個位置插入你想插的元素：

真是服了，寫出來一大堆亂碼，檢查了半天是因為自己在擴容的時候寫錯了：

我算出來的newcapacity是元素個數，人家realloc要的是字節數，還得乘一下，調試半天。

其它沒什么疑問：

6.順序表的刪除

尾刪

直接給出

刪除操作，下意識的我們就可能想到，必須把尾部的數據給刪除了，但是實際上刪除以后難道計算機對于這塊位置就不再管了嗎？顯然不是的，只是變成亂碼了而已，假設給上亂碼，你不還是得size--嘛，反正也就是為了不再訪問順序表尾部的值，直接size--即可

頭刪

從前往后覆蓋即可：

比如這個，就是從2->1，3->2等等即可。

代碼表達：

測試：

一樣道理，即使最后的不刪，size為3，不管你做遍歷還是插入等一系列操作，都不會被這個值影響。

指定位置刪除

類似于頭插的前移，只不過與所給位置有關而已：

調試：

7.順序表的查找

參數肯定是一個順序表，一個需要查找的元素，不過這次僅僅是查找，可以傳值調用了，畢竟不要求對數據源進行修改，僅僅是對比。

調試：

8.順序表遍歷打印

當然，這里只寫int類型的遍歷：

調試：

毋庸置疑。

9.順序表的銷毀

如果你寫的是局部變量，那就等出了函數系統自動回收空間就算了，但是我們用的最多的是動態順序表，也就意味著有一塊動態開辟的內存空間，碰見這樣的事的話，用完了手動給它回收吧，不過我們要給它封裝成一個函數：

不用多解釋，其實就是調用了個free，最后置指針為空。