在本文中的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)等都是對線性表而言的

線性表(Linear List)：零個或多個數(shù)據(jù)元素的有限序列，元素的個數(shù)定義為線性表的長度，無元素時稱為空表；每個元素的位置稱為位序(類似下標(biāo))，某元素的前一個元素稱作直接先驅(qū)元素，后一個元素稱作直接后繼元素

順序存儲結(jié)構(gòu)：

用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素，在C中用一維數(shù)組來實現(xiàn)(Python中可以用列表來實現(xiàn))，描述該結(jié)構(gòu)需要三個屬性：

• 存儲空間的存儲位置：數(shù)組的存儲位置
• 線性表的最大存儲容量：即數(shù)組長度(如果不動態(tài)分配，這個長度是不變的)
• 線性表的當(dāng)前長度；

1. 地址：存儲器中的每個存儲單元所獨有的編號，若每個a(代表數(shù)據(jù)元素)所占c個存儲單元，LOC為獲得存儲位置的函數(shù)，那么計算方法為：
   • LOC(下標(biāo)為i+1的a) = LOC(下標(biāo)為i的a) + c
   • LOC(下標(biāo)為i的a) = LOC(下標(biāo)為1的a) + (i-1) * c
2. 順序存儲結(jié)構(gòu)的操作：
   • 讀?。喝粢〉趇個元素，就訪問下標(biāo)為i-1的元素，注意i值的范圍(小于表長、不小于1)，時間復(fù)雜度為O(1)
   • 插入：需注意插入后線性表的長度；從最后一個元素向前遍歷到第i個位置，并分別向后移一個位置(即下標(biāo)+1)，插入后表長度+1，時間復(fù)雜度每插一個為O(n)
   • 刪除：與插入操作相反，不再贅述
3. 線性表順序存儲結(jié)構(gòu)的優(yōu)劣：
   • 優(yōu)點：不用為表中元素之間的邏輯關(guān)系添加額外的存儲空間；可以快速存取表中任一位置元素
   • 缺點：插入和刪除操作時間復(fù)雜度高；長度變化大時難以確定存儲空間容量；造成存儲空間的"碎片"

鏈?zhǔn)酱鎯Y(jié)構(gòu)

在鏈?zhǔn)浇Y(jié)構(gòu)中，除了要存數(shù)據(jù)元素信息外，還要存儲它的后繼元素的存儲地址，其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，存儲直接后繼位置的域稱為指針域；指針域中存儲的信息稱作指針或鏈。這兩部分信息組成數(shù)據(jù)元素ai(下標(biāo)為i的a)的存儲映像，稱為結(jié)點(Node)

單鏈表

n個結(jié)點鏈結(jié)成一個鏈表，即為線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，因為此鏈表的每個結(jié)點中只包含一個指針域，所以叫做單鏈表

1. 頭指針(必須要素)：鏈表中的第一個結(jié)點的存儲位置，指向第一個結(jié)點(最后一個節(jié)點的指針為空(NULL或"^"表示))
2. 頭結(jié)點(非必須)：有時為了方便操作第一結(jié)點，會在單鏈表的第一個結(jié)點前附設(shè)一個節(jié)點，其數(shù)據(jù)域可以為空
3. 若p是指向線性表第i個元素的指針，ai的數(shù)據(jù)域用p->data表示，指針域用p->next表示，那么ai+1的數(shù)據(jù)域的表示可以用p->next->data
4. 鏈?zhǔn)酱鎯Y(jié)構(gòu)的操作：
   • 讀?。喝粢〉趇個元素，從第一個結(jié)點開始遍歷鏈表讓指針不斷向后移動直至第i個結(jié)點隨后進行讀取(元素存在)或到末尾指針為空(元素不存在)
   • 插入：若要在第i個元素插入數(shù)據(jù)e，聲明指針p指向頭結(jié)點，遍歷鏈表使p到指定位置(即第i-1個結(jié)點)并生成一個空節(jié)點s，將e賦值給s->data，使用單鏈表的插入標(biāo)準(zhǔn)語句:s->next=p->next; p->next=s(將p的后繼結(jié)點賦值給s的后繼；將s賦值給p的后繼)，插入完成
   • 刪除：大體與插入類似；假設(shè)在鏈表中存在結(jié)點p, d, q，d是要刪除的結(jié)點，把p的后繼結(jié)點改成q即可 (也就是p的后繼的后繼結(jié)點)，刪除標(biāo)準(zhǔn)語句：q=p->next; p->next=q->next
   • 整表創(chuàng)建：頭插法(把新結(jié)點插在頭結(jié)點后)、尾插法(比頭插法多需要一個指向尾結(jié)點的變量)
   • 整表刪除：先聲明p和q：第一個結(jié)點賦給p；循環(huán)：p->next賦給q，釋放p，q賦給p；直至p指針為空
5. 單鏈表結(jié)構(gòu)(單)與順序存儲結(jié)構(gòu)(順)優(yōu)劣：
   • 存儲上：順用是的一段連續(xù)的存儲單元依次存儲；單不受固定的存儲空間限制
   • 時間性能：查找：順為O(1), 單為O(n)；插入和刪除：順為O(n), 單(找出位置后)為O(1)
   • 空間性能：順需要預(yù)分配；單可以動態(tài)生成
   • 總結(jié)：查找多時用順結(jié)構(gòu)，頻繁增改時用單結(jié)構(gòu)；表長可確定用順結(jié)構(gòu)，表長沒準(zhǔn)時用單結(jié)構(gòu)

靜態(tài)鏈表

不用指針，而是用數(shù)組描述的鏈表；讓數(shù)組的元素由兩個數(shù)據(jù)域組成，每個下標(biāo)都對應(yīng)一個data和cur(稱作游標(biāo), 相當(dāng)于next指針)，也稱作游標(biāo)實現(xiàn)法

6. 數(shù)組中的首尾元素作為特殊元素處理不存數(shù)據(jù)，把未使用的數(shù)組元素稱為備用鏈表，首元素的cur存放備用鏈表的第一個結(jié)點的下標(biāo)，尾元素的cur存放第一個有數(shù)值的元素的下標(biāo)，最后一個有值元素的cur為0
7. 插入操作：先把要插入的數(shù)據(jù)賦給備用鏈表元素，再通過把插入位置前的元素的cur指向備用鏈表元素同時把原指向賦給備用鏈表元素的cur(需定義類似malloc()的函數(shù)來分配備用下標(biāo)，以實現(xiàn)動態(tài)鏈表的節(jié)點申請)
8. 刪除操作：把首元素的cur賦給將目標(biāo)元素的cur，再把首元素的cur指向目標(biāo)元素
9. 靜態(tài)鏈表優(yōu)劣：
   • 優(yōu)點：插入和刪除只需修改游標(biāo)，免去移動元素的操作
   • 缺點：連續(xù)存儲分配使表長難以確定；失去順序存儲結(jié)構(gòu)隨機存取的特性
   • 總結(jié)：靜態(tài)鏈表是為了給沒有指針的高級語言設(shè)計的一種實現(xiàn)單鏈表的方法，根據(jù)實際需要使用

循環(huán)鏈表

將單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點，使整個單鏈表形成一個環(huán)，這種頭尾相接的單鏈表稱為單鏈表循環(huán)，簡稱循環(huán)鏈表

10. 與單鏈表的主要差異在于循環(huán)的判斷條件上：若p->next不等于頭結(jié)點，則循環(huán)未結(jié)束
11. 將兩個循環(huán)鏈表合并成一個表時用尾指針操作會方便很多

雙向鏈表

在單鏈表中，查找下一結(jié)點需要O(1)，若要查找上個結(jié)點最壞需要O(n)，為解決此問題人們設(shè)計出了雙向鏈表：在單鏈表的每個結(jié)點中再設(shè)置一個指向其前驅(qū)節(jié)點的指針域(prior)，也就是用空間換時間

12. 一個節(jié)點前驅(qū)的后續(xù)等于本身： p->next->prior= p = p->prior->next
13. 與單鏈表不同的是：在插入和刪除時需要更改兩個指針變量(注意順序)