順序存儲結構（數組） 一段地址連續的存儲的單元依次存儲線性表的數據元素

數組： 數組的長度是存放線性表的存儲空間的長度，存儲分配后這個量一般不變 線性表的長度是線性表中存儲元素的個數，這個數小于等于數組長度

線性表中元素地址值： 后一個元素的地址值 = 前一個位置 + 前一個元素占據的存儲單元

存取時間復雜度： 由上面的公式可知，數組的存取時間性能為o（1）

插入與刪除： 插入： 1. 插入位置不合理，拋出異常（插入位置 < 1 個位置或大于數組長度+1） 2. 線性表長度 >= 數組長度，拋出異常或動態增加容量 3. 從最后一個位置開始遍歷到第 i 個位置，全部向后移動一個位置，將元素插到第 i 個位 置 4. 線性表長度加一

刪除： 1. 刪除位置不合理，拋出異常（刪除位置 < 1 個位置或大于數組長度+1） 2. 線性表為空，拋出異常 3. 取出要刪除的元素 4. 從刪除位置遍歷到最后一個位置，將他們向前移動一個位置 5. 線性表長度減一

數組的優缺點 優點： ● 無需為元素之間的邏輯關系增加額外的存儲空間 ● 可以快速存取表中任意位置的位置的元素 缺點： ● 插入刪除需要移動大量元素 ● 線性表長度變化較大時難以確定存儲空間 ● 造成存儲空間的碎片

鏈式存儲結構 鏈表除了存儲數據信息外，還存有后繼元素的儲存地址 每一個元素稱為結點，節點分為兩部分，前一部分存儲數據，稱為數據域，后一部分存儲后繼元素 的地址值，稱為指針域 每個節點中只包含一個指針域，叫做單鏈表 鏈表第一個節點的存儲位置較頭指針，最后一個節點指針為空

鏈表的第一個節點前可以設一個頭結點，數據域可以不存東西也可以存鏈表的長度，指針域指向第一個結點 若鏈表有頭結點，頭指針指向頭結點，無論鏈表是否為空，頭指針都不為空。此時頭結點的指針域為空

單鏈表的讀取 ● 獲取第 i 個元素 ● 聲明一個指針指向第一個結點，初始化一個 j 從 1 開始向 p 向后移動， j 累加 1 ● 若到了鏈表尾P為空，說明 i 不存在 ● 反之存在，返回 p

時間復雜度： 最壞的情況為 o（n）

單鏈表的插入和刪除 插入（在位置 i 插入 s） ● 聲明指針p , s。p指向鏈頭，初始化 j 從 1開始 ● 當 j < i 時，讓 p向后移動，不斷指向下一個結點 ● 若到鏈表尾p為空，說明第 i 個結點不存在 ● 若查找成功，在系統中用指針 s 生成一個空節點 s ● 將元素e賦值給s的數據域 ● 單鏈表插入語句 將p的指針域賦值給s的指針域，將 s 的位置賦值給p的指針域 刪除（刪除位置 i 的結點） ● 聲明指針p，q。p指向鏈頭，初始化 j 從 1開始 ● 當 j < i 時，讓 p向后移動，不斷指向下一個結點 ● 若到鏈表尾p為空，說明第 i 個結點不存在 ● 否則將欲刪除的元素的位置 p -> next 賦值給q ● 將q個位置 賦值給p ● 返回q的數據域的值，并釋放q 單鏈表查找的時間復雜度為o（n），插入和刪除的時間復雜度為o（n），但是在這個位置之后的 插入和刪除只是簡單的通過賦值移動指針，時間復雜度為o（1）。對于插入和刪除越頻繁的操作，單 鏈表的效率高

單鏈表的整表創建: 頭插法: ● 聲明一個指針 p ● 聲明一個空鏈表 L，生成一個頭結點，指針指向null ● 循環 ● 生成新結點賦值給p ● 給p的數據域賦值 ● 將頭結點的指針域賦值給p的指針域 ● 將p的位置賦值給頭結點的指針域 尾插法： ● 聲明兩個指針p , r ● 聲明一個空鏈表 L，生成一個頭結點，將r賦值為指向尾部的結點 ● 循環 ● 生成新節點p ● 給新結點的數據域賦值 ● 將p的位置賦值給r的指針域 ● 循環完畢，將r的指針域指向null 單鏈表的整表刪除 ● 聲明兩個指針 p， q ● p指向鏈表的第一個結點 ● 循環，當p不為空時 ● 將p的指針域賦值給q ● 釋放p ● 將q賦值給p ● 循環完畢，鏈表頭指針指向null

單鏈表結構和順序存儲結構（數組）的優缺點

存儲分配方式： 順序結構用一段連續存儲單元依次存儲線性表的數據元素 單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表的元素 時間性能 查找： 順序結構 ： o（1） 單鏈表 ： o（n） 插入刪除： 順序結構 ： o（n） 單鏈表 ： 查出某個位置的指針后，插入和刪除時間為o（1） 空間性能： 順序結構需要預先分配空間，分大了浪費，分小了溢出 單鏈表不需要分配存儲空間，只要有就可以分配，元素個數也不受限制

總結： 線性表需要頻繁進行插入和刪除操作時，采用鏈表；需要大量查找時，宜采用順序存儲結 構 一開始不知道元素個數時，宜采用鏈表；事先知道，采用順序存儲結構

循環鏈表 將單鏈表的尾指針指向頭結點，使整個單鏈表形成一個環

與單鏈表的差異： 單鏈表： p -> next = null ？ 到了尾部 ： 沒到尾部 循環鏈表： p -> next = 頭結點 ？ 循環結束 ： 循環未結束

循環鏈表查找第一個結點花費o（1），找最后一個花費o（n），對循環鏈表進行改造，不用頭指針，改用指向尾部的尾指針rear，這樣查找尾部結點的時間為o(1)，查找頭結點為rear -> next ->next(頭結點的存在)，時間復雜度也為o(1)

對于將兩個循環鏈表合成一個循環鏈表的處理方法（a鏈表尾結點為rearA，b鏈表尾結點為rearB） ● 聲明指針p, q ● p = rearA -> next ● q = rearB -> next ● rearA -> next = rearB -> next -> next ● rearB -> next = p ● free(q) 雙向鏈表 單鏈表查找下一個的時間復雜度為o（1），但是查找上一個的復雜度為o（n），為了解決這一問題，引入雙向鏈表 雙向鏈表是在單鏈表的每個結點中，再設置一個前驅結點指針

在雙向鏈表中插入元素： 將 s 插入 p 和 p -> next之間 ● s -> PRior = p ● s - > next= p - > next ● p - > next-> prior = s ● p - > next = s 在雙向鏈表中刪除元素： 刪除p： 將p - > next 賦值給 p -> prior 的后繼 將p - > prior賦值給 p - ＞next 的前驅 free（p）