線性結構是一種基本的數據結構，主要用于對客觀世界中具有單一前驅和后繼的數據關系進行描述。
特點是數據元素間呈現一種線性關系，即元素“一個接一個排列”。
（一）線性表
常采用順序存儲和鏈式存儲。
1.線性表的定義
一個線性表是n(n>=0)個元素的有限序列，通常表示為(a1,a2,...,an)。
特點：
- 存在唯一的一個稱作是“第一個”的元素；
- 存在唯一的一個稱作“最后一個”的元素；
- 除第一個元素外，序列中的每個元素均只有一個直接前驅；
- 除最后一個元素外，序列中的每個元素均只有一個直接后繼。
2.線性表的存儲結構
線性表的存儲結構分為順序存儲和鏈式存儲。
（1）順序存儲
順序存儲：指用一組地址連續(xù)的存儲單元依次存儲線性表中的數據元素，從而使得邏輯上相鄰的兩個元素在物理位置上也相鄰。
使用這種存儲方式，元素間的邏輯關系無須占用額外的空間來存儲。
存儲位置計算，第i個元素ai的存儲位置：
LOC(ai)=LOC(a1)+(i-1)*L
其中，L是表中每個元素所占空間的字節(jié)數。
優(yōu)缺點：
- 優(yōu)點
可以隨機存取表中的元素 - 缺點
插入和刪除操作需要移動元素
（2）鏈式存儲
鏈式存儲：是用通過指針鏈接起來的結點來存儲數據元素。
基本的節(jié)點結構如下所示：
| 數據域 | 指針域 |
|---|
其中數據域用于存儲數據元素的值，指針域存儲當前元素的直接前驅或直接后繼的位置信息，指針域中的信息稱為指針（鏈）。
存儲各數據元素的結點的地址不要求連續(xù)，因此在存儲數據元素的同時必須存儲元素之間的邏輯關系。
在鏈式存儲結構下進行插入和刪除，其實質是對相關指針的修改。
根據結點中指針域的設置方式，鏈表分為：
- 單向鏈表，結點中只有一個指針域；
- 雙向鏈表，每個結點包含兩個指針，分別指出當前元素的直接前驅和直接后繼；
- 循環(huán)列表，在單向鏈表（或雙向鏈表）的基礎上令表尾結點的指針指向鏈表的第一個結點，構成循環(huán)鏈表，特點是可以從表中任意結點開始遍歷整個鏈表；
- 靜態(tài)鏈表，借助數組來描述線性表的鏈式存儲結構，用數組元素的下標表示元素所在結點的指針。
（二）棧和隊列
棧和隊列是程序中常用的兩種數據結構，它們的邏輯結構和線性表相同，特點是運算有所限制。
棧是“后進先出（Last In First Out，LIFO）”，隊列是“先進先出（First In First Out，FIFO）”。
1.棧
（1）棧的定義及基本運算
1）棧的定義
棧是只能通過訪問它的一端來實現數據存儲和檢索的一種線性數據結構。
在棧中進行插入和刪除操作的一端稱為棧頂（Top），相應地，另一端稱為棧底（Bottom）。不含數據元素的棧稱為空棧。
2）棧的基本運算
- 初始化棧：創(chuàng)建一個空棧
S； - 判斷空：當棧
S為空時返回“真”，否在返回“假”； - 入棧（push）：將元素
x加入棧頂，并更新棧頂指針； - 出棧（pop）：將棧頂元素從棧中刪除，并更新棧頂指針；
- 讀棧頂元素（top）：返回棧頂元素的值，但不修改棧頂指針。
（2）棧的存儲結構
1）順序存儲
棧的順序存儲是指用一組地址連續(xù)的存儲單元依次存儲自棧頂到棧底的數據元素，同時附設指針top指示棧頂元素的位置。
采用順序存儲結構的棧也成為順序棧。
需要預先定義棧的存儲空間，棧的空間容量有限。
2）棧的鏈式存儲
用鏈表做為存儲結構的棧也稱為鏈棧。
不必另外設置頭指針，鏈表的頭指針就是棧頂指針。
3）棧的應用
棧的應用包括表達式求值，括號匹配等。
在計算機語言的實現以及將遞歸過程轉變?yōu)榉沁f歸過程的處理中，棧有重要的作用。
2.隊列
（1）隊列的定義及基本運算
1）隊列的定義
隊列是一種先進先出的線性表，它只允許在表的一端插入數據元素，而在表的另一端刪除元素。
在隊列中，允許插入元素的一端稱為隊尾（rear），允許刪除元素的一端稱為隊頭（front）。
2）隊列的基本運算
- 初始化隊列：創(chuàng)建一個空的隊列
Q； - 判讀空：當隊列為空時返回“真”，否則返回“假”；
- 入隊（EnQueue）：將元素
x加入到隊列Q的隊尾，并更新隊尾指針； - 出隊（DelQueue）：將隊頭元素從隊列
Q中刪除，并更新隊頭指針； - 讀隊頭元素：返回隊頭元素的值，但不更新隊頭指針。
（2）隊列的存儲結構
1）隊列的順序存儲
隊列的順序存儲結構又稱為順序隊列，它是利用一組地址連續(xù)的存儲單元存放隊列中的元素。
由于隊列中元素的插入和刪除限定在表的兩端進行，因此設置隊頭指針和隊尾指針，分別指出當前的隊頭和隊尾。
元素出隊時只修改隊頭指針；存儲空間提前設定，所以隊尾指針會有一個上限值。
2）隊列的鏈式存儲
隊列的鏈式存儲也稱為鏈隊列。
為了便于操作，給鏈隊列添加一個頭結點，并令頭指針指向頭結點。
因此，隊列為空的判斷條件時頭指針和尾指針的值相同，并且均指向頭結點。
（3）隊列的應用
隊列機構常用于處理需要排隊的場合，例如操作系統中處理打印任務的打印隊列、離散事件的計算機模擬等。
（三）串
串（字符串）是一種特殊的線性表，其數據元素為字符。
在計算機運算時，常把一個串作為一個整體來處理。
1.串的定義及基本運算
（1）串的定義
串是僅由字符構成的有限序列，是一種線性表。
（2）串的幾個基本概念
- 空串：長度為零的串，不包含任何字符；
- 空格串：由一個或多個空格組成的串；
- 子串：由串中任意長度的連續(xù)字符構成的序列；
（3）串的基本操作
- 賦值操作：將串
s的值賦給串t； - 連接操作：將串
t接續(xù)在串s的尾部，形成一個新串； - 求串長：返回串
s的長度； - 串比較：比較兩個串的大小；
- 求子串：返回串
s中從start開始的，長度為len的字符序列。
2.串的存儲結構
- 順序存儲結構
用一組地址連續(xù)的存儲單元來存儲串值的字符序列 - 鏈式存儲結構
每個結點中可以存儲一個字符，也可以存儲多個字符，要考慮存儲密度的問題
3.串的模式匹配
子串的定位操作通常稱為串的模式匹配，它是各種串處理系統中最重要的運算之一。
子串也稱為模式串。
（1）樸素的模式匹配算法
也稱為布魯特-福斯算法。
基本思想是從主串的第一個字符起與模式串的第一個字符比較，若相等，則繼續(xù)逐一對字符進行后續(xù)的比較，否則從主串第二個字符起與模式串的第一個字符重新比較，直到模式串中每個字符依次和主串中一個連續(xù)的字符序列相等時為止，此時稱為匹配成功，若不能在主串中找到與模式串相同的子串，則匹配失敗。
（2）改進的模式匹配算法
又稱為KMP算法。
當匹配過程中出現相比較的字符不相等時，不需要回退主串的字符位置指針，而是利用已經得到的“部分匹配”結果將模式串向右“滑動”盡可能遠的距離，再繼續(xù)進行比較。
