近幾次總是討論著各種各樣的表哪怔，難免有些暈灶伊。
這次的內(nèi)容依然是一個表（笑哭臉）弥鹦，為了不“暈表”亲配，我們先來理一理：這是個什么表。

我們前面已經(jīng)說過線性表了。對于線性和非線性的邏輯結(jié)構(gòu)吼虎，都對應(yīng)有順序存儲和鏈式存儲兩種方式犬钢。

先說順序表，也就是線性表的順序存儲思灰。

順序表

大家都學(xué)過C語言玷犹，那么順序表好理解一些的方式就是用C語言的數(shù)組作為例子來說。
（我好像確實比較喜歡用例子來類比洒疚。歹颓。。見諒）

C語言的數(shù)組實際上就是線性表的完全表現(xiàn)載體油湖。
我們先來回顧一下數(shù)組的種種：

• 數(shù)組有一個首地址巍扛；
• 只要知道數(shù)組的首地址，那么我們可以隨意訪問數(shù)組中的元素乏德；
• 數(shù)組的存儲（在內(nèi)存中）是連續(xù)的撤奸；

順序表的性質(zhì)和以上三個大致相同。

但是依然需要區(qū)別數(shù)組和順序表：順序表依然是一種存儲模型喊括，但是數(shù)組是實實在在的存儲容器胧瓜。我們可以對順序表執(zhí)行一系列的運算（這時候把順序表作為對象來看待），但是對于數(shù)組我們依然只能對其進行一些基礎(chǔ)操作郑什。

比如說府喳，一個順序表是用數(shù)組去表達的（即在數(shù)組中存放順序表元素，一般數(shù)組要足夠大）蘑拯，這時候順序表的長度和數(shù)組的長度是不完全一致的钝满。數(shù)組的長度指的是數(shù)組所占的空間數(shù)，而順序表的長度僅僅是指有效數(shù)據(jù)所占的空間申窘。

其實我們可以簡單總結(jié)一下：順序表=數(shù)組+各種針對數(shù)組的運算的函數(shù)

關(guān)于順序表的運算的函數(shù)這里不再贅述舱沧，相對來說比較基礎(chǔ)，有C語言學(xué)習(xí)經(jīng)歷的小伙伴們可以很容易自己去實現(xiàn)偶洋。

鏈式線性表

說完了順序表熟吏，接下來說鏈式存儲的線性表。
基于前面的順序表的概念玄窝，鏈式線性表是存儲上不連續(xù)的線性表——對應(yīng)到C語言中就是用鏈表來表達線性表牵寺。

有C語言基礎(chǔ)的小伙伴一定都很熟悉單鏈表的基礎(chǔ)操作了，這里不再贅述恩脂。
因為鏈表是用指針實現(xiàn)線性表的前驅(qū)與后繼帽氓，所以更適合利用指針的操作來使得線性表的修改操作變得更容易一些。故俩块，一些需要改動內(nèi)容的線性表更適合用鏈式線性表來表達黎休。

但是有時候用之前學(xué)過的單鏈表來表達線性表依舊是不方便浓领、不形象的。所以還有幾種不同于之前單鏈表的幾種鏈表：

1.循環(huán)鏈表：
所謂的循環(huán)鏈表就是之前的單鏈表的一個“變形”势腮。原來的單鏈表的尾指針是指向NULL的联贩，這時候只要把該單鏈表的尾指針指向該單鏈表的頭結(jié)點，即可構(gòu)成循環(huán)鏈表捎拯。此時尾結(jié)點成為了首節(jié)點的前驅(qū)泪幌。且因為循環(huán)鏈表的操作一般是對原先的單鏈表的首尾節(jié)點進行操作，為了減少從頭開始遍歷到尾結(jié)點的時間署照，所以習(xí)慣性用尾指針來指示鏈表祸泪。當然這也不是絕對的，具體情況具體對待建芙。

2.雙向鏈表：
在使用之前學(xué)過的單鏈表或者循環(huán)鏈表時會發(fā)現(xiàn)没隘，無論如何我們只能從某個節(jié)點開始定向遍歷，所以當我們需要找到該節(jié)點的前驅(qū)的時候就需要從頭開始重新遍歷單鏈表或者循環(huán)遍歷一遍鏈表禁荸，在時間開銷上來說十分不劃算右蒲。所以這時候用雙向鏈表就會好一些。
雙向鏈表就是在之前單鏈表的節(jié)點基礎(chǔ)上屡限，對節(jié)點的結(jié)構(gòu)再添加一個指針，該指針指向該節(jié)點的前驅(qū)節(jié)點炕倘。這時候每個節(jié)點都可以直接訪問該節(jié)點的前驅(qū)和后綴钧大，就能大大減少時間的開銷。
同時要注意的一點是罩旋，在雙向鏈表的操作中啊央，修改鏈表（增、刪等）都需要同時操作前驅(qū)節(jié)點的指針和后繼結(jié)點的指針涨醋，并且需要使當前節(jié)點的兩個指針的指向都正確瓜饥。

3.靜態(tài)鏈表：
在這之前我們說到的都是動態(tài)鏈表，因為節(jié)點都是在用的時候申請浴骂、不用時銷毀的乓土。但是靜態(tài)鏈表就有些特殊了。
靜態(tài)鏈表是用數(shù)組實現(xiàn)的溯警。
先不要慌趣苏。靜態(tài)鏈表之所以依然取名為鏈表，就是因為它還是具有鏈表的特點：以節(jié)點為單位梯轻、相鄰元素間的邏輯由指針的指向來確定食磕。
但是為什么叫靜態(tài)鏈表并且強調(diào)它是用數(shù)組來實現(xiàn)的呢？
想象一下喳挑，把一條貪吃蛇揉吧揉吧塞到一個盒子里彬伦，蛇寶寶的頭可能和尾巴都是相鄰存放的滔悉，但是邏輯結(jié)構(gòu)依然是蛇的身子表達出來的。靜態(tài)鏈表就是這樣单绑，將一個鏈表“存到“數(shù)組中回官，兼顧了鏈表和數(shù)組的特點：鏈式邏輯，數(shù)組存儲询张。下面盜一張圖來說明一下：

圖片.jpg

順序表和鏈式線性表的比較

上面說完了順序窥妇、舷胜；鏈式兩種方式以及各自的載體去實現(xiàn)線性表的表達。下面分析一下二者各自的優(yōu)缺點:

對于順序表而言活翩，就是一系列的數(shù)組特性：存取數(shù)據(jù)操作簡單烹骨、存儲密度高、連續(xù)讀取的效率高材泄。但是執(zhí)行插入沮焕、刪除等操作時，會有大量數(shù)據(jù)被連同操作拉宗，資源開銷大峦树；而且總占用空間有一個固定的大小，容易產(chǎn)生資源閑置或溢出的現(xiàn)象旦事。

對于鏈式存儲來說則是鏈表的特性：存儲密度較锌杖搿（因為節(jié)點中往往需要分配指針域，而且數(shù)據(jù)在內(nèi)存中的存儲并不是連續(xù)的地址族檬，連續(xù)讀取的過程中需要不斷進行指針運算）歪赢。但是執(zhí)行插入、刪除等操作時十分方便单料，不用操作其他無關(guān)數(shù)據(jù)埋凯。

總結(jié)起來說就是：如果線性表不需要執(zhí)行插入点楼、刪除等改動元素的操作的話用順序表比較合適，否則則采用鏈式線性表白对。
還有就是掠廓，幾乎所有的編程語言都支持數(shù)組，但不一定支持指針甩恼。
這就意味著蟀瞧，順序表無論如何是可以實現(xiàn)的，但是鏈式線性表就不一定能實現(xiàn)了条摸！

以上就是線性表的兩種存儲形式的表達的討論和總結(jié)悦污。

說點題外話：
為什么要把這個并不復(fù)雜的東西的概念說這么多呢？
私以為,概念神馬的還是蠻重要的钉蒲，從根本出發(fā)弄清楚概念切端，對后面的應(yīng)用或者更復(fù)雜的操作會有比較大的幫助。另外一方面顷啼，很多東西我們會用踏枣，但不知道為什么這么用。作為計算機專業(yè)的學(xué)生钙蒙，在專業(yè)知識方面茵瀑，我還是想達到“知其然，知其所以然”的程度躬厌。

新手上路马昨，才疏學(xué)淺。如有錯漏烤咧，懇請指教偏陪。