資料結構1 線性結構

資料結構是指資料元素的結合及元素間的互相關系和構造方法。元素之間的互相關系是資料的邏輯結構，元素關系的存儲形式成為存儲結構。資料結構按照邏輯關系的不同分為線性結構和非線性結構兩大類。其中線性結構是最基本的結構，元素順序排列，常見的有線性表、棧、隊列、數組、串。

一、線性表

1.線性表是最簡單也是最常用的一種線性結構。一個線性表示n(n>=0)個元素的有限序列，非空線性表的特點為：

存在唯一的一個“第一個”元素；

存在唯一的一個“最後一個”元素；

除第一個元素外，序列中的每個元素均隻有一個直接前驅；

除最後一個元素外，序列中的每個元素均隻有一個直接後驅；

2.關于線性表的存儲結構，有順序存儲和鍊式存儲兩種方式。順序存儲是用一組位址連續的存儲單元依次存儲線性表中的資料元素，進而使得邏輯上相鄰的兩個元素在實體位置上也相鄰。鍊式存儲則使用結點來存儲資料元素，結點分為資料域和指針域，資料域用于存儲元素的值，指針域則存儲元素的直接前驅或直接後驅的位址，結點之間通過指針域構成一個連結清單。若結點中隻有一個指針域，則稱為單連結清單。

順序存儲結構無須占用額外的空間來表示元素之間的邏輯關系，而且可以随機存取表中的元素，但插入、删除資料的操作比較麻煩，需要順次移動很多元素；連結清單中各資料元素的結點位址則不要求是連續的，是以必須同時存儲元素之間的邏輯關系，連結清單的插入、删除操作都比較友善，隻需修改指針域的指向即可。

3.根據結點中指針域的設定方式，還有其他幾種連結清單結構：

雙向連結清單：每個階段包含兩個指針，分别指向直接前驅和直接後驅，這樣可以從表中任意的結點出發，從兩個方向周遊連結清單。

循環連結清單，在單向連結清單或雙向連結清單的基礎上，令表尾結點的指針指向第一個元素，這樣就可以從任意結點開始周遊整個連結清單了。

二、棧和隊列

棧和隊列的邏輯結構和線性表相同，但對其的運算有所限制。

1.棧

棧隻能通過通路它的一端來實作資料的存儲和檢索，即對棧的操作時按照先進後出的原則進行的（Last In first out, LIFO），這一端稱為棧頂，則另一端為棧底。不含任何元素的棧稱為空棧。

棧的存儲結構也分順序和鍊式，順序存儲是用一組位址連續的存儲單元依次存儲自棧頂到棧底的資料元素，同時用指針top來訓示棧頂元素的位置，這種結構的棧也成為順序棧。使用這種存儲方式需要預先定義棧的存儲空間，棧的空間有限，是以元素入棧前，需要判斷棧是否已滿，否則會發生溢出。

鍊式存儲的棧（鍊棧）沒有溢出的問題，鍊棧也無須另外設定top指針

棧在表達式求值、計算機語言的實作、将遞歸過程轉變為非遞歸過程的進行中有重要作用。

2.隊列

隊列則是一種先進先出(First in first out, FIFO)的線性表，但隻能在隊列的隊尾(rear)插入元素，然後在隊頭(front)删除元素。

與順序棧類似，順序隊列采用順序存儲結構，并需要設定隊頭指針和隊尾指針。

鍊隊列則為了便于操作，會添加一個頭結點，并令頭指針指向頭結點，是以如果頭指針和尾指針的值相同，則可判定隊列為空。

隊列常用于處理需要排隊的場合，如列印隊列、消息隊列等。