在本文中的順序存儲結(jié)構(gòu)迄损、鏈式存儲結(jié)構(gòu)等都是對線性表而言的
線性表(Linear List)：零個或多個數(shù)據(jù)元素的有限序列省有，元素的個數(shù)定義為線性表的長度，無元素時稱為空表贯涎；每個元素的位置稱為位序(類似下標)听哭，某元素的前一個元素稱作直接先驅(qū)元素，后一個元素稱作直接后繼元素
順序存儲結(jié)構(gòu)：
用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素塘雳，在C中用一維數(shù)組來實現(xiàn)(Python中可以用列表來實現(xiàn))陆盘，描述該結(jié)構(gòu)需要三個屬性：
- 存儲空間的存儲位置：數(shù)組的存儲位置
- 線性表的最大存儲容量：即數(shù)組長度(如果不動態(tài)分配，這個長度是不變的)
- 線性表的當(dāng)前長度败明；
- 地址：存儲器中的每個存儲單元所獨有的編號隘马，若每個a(代表數(shù)據(jù)元素)所占
c個存儲單元，LOC為獲得存儲位置的函數(shù)妻顶，那么計算方法為：LOC(下標為i+1的a) = LOC(下標為i的a) + cLOC(下標為i的a) = LOC(下標為1的a) + (i-1) * c
- 順序存儲結(jié)構(gòu)的操作：
- 讀人嵩薄：若要取第i個元素，就訪問下標為i-1的元素讳嘱，注意i值的范圍(小于表長幔嗦、不小于1)，時間復(fù)雜度為O(1)
- 插入：需注意插入后線性表的長度沥潭；從最后一個元素向前遍歷到第i個位置邀泉，并分別向后移一個位置(即下標+1)，插入后表長度+1，時間復(fù)雜度每插一個為O(n)
- 刪除：與插入操作相反汇恤，不再贅述
- 線性表順序存儲結(jié)構(gòu)的優(yōu)劣：
- 優(yōu)點：不用為表中元素之間的邏輯關(guān)系添加額外的存儲空間庞钢；可以快速存取表中任一位置元素
- 缺點：插入和刪除操作時間復(fù)雜度高；長度變化大時難以確定存儲空間容量因谎；造成存儲空間的"碎片"
鏈式存儲結(jié)構(gòu)
在鏈式結(jié)構(gòu)中基括，除了要存數(shù)據(jù)元素信息外，還要存儲它的后繼元素的存儲地址财岔，其中存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域阱穗，存儲直接后繼位置的域稱為指針域；指針域中存儲的信息稱作指針或鏈使鹅。這兩部分信息組成數(shù)據(jù)元素ai(下標為i的a)的存儲映像，稱為結(jié)點(Node)
單鏈表
n個結(jié)點鏈結(jié)成一個鏈表昌抠，即為線性表的鏈式存儲結(jié)構(gòu)患朱，因為此鏈表的每個結(jié)點中只包含一個指針域，所以叫做單鏈表
- 頭指針(必須要素)：鏈表中的第一個結(jié)點的存儲位置炊苫，指向第一個結(jié)點(最后一個節(jié)點的指針為空(NULL或"^"表示))
- 頭結(jié)點(非必須)：有時為了方便操作第一結(jié)點裁厅，會在單鏈表的第一個結(jié)點前附設(shè)一個節(jié)點，其數(shù)據(jù)域可以為空
- 若p是指向線性表第i個元素的指針侨艾，ai的數(shù)據(jù)域用
p->data表示执虹，指針域用p->next表示，那么ai+1的數(shù)據(jù)域的表示可以用p->next->data - 鏈式存儲結(jié)構(gòu)的操作：
- 讀冗肜妗：若要取第i個元素袋励，從第一個結(jié)點開始遍歷鏈表讓指針不斷向后移動直至第i個結(jié)點隨后進行讀取(元素存在)或到末尾指針為空(元素不存在)
- 插入：若要在第i個元素插入數(shù)據(jù)e，聲明指針p指向頭結(jié)點当叭，遍歷鏈表使p到指定位置(即第i-1個結(jié)點)并生成一個空節(jié)點s茬故，將e賦值給
s->data，使用單鏈表的插入標準語句:s->next=p->next; p->next=s(將p的后繼結(jié)點賦值給s的后繼蚁鳖；將s賦值給p的后繼)磺芭，插入完成 - 刪除：大體與插入類似；假設(shè)在鏈表中存在結(jié)點p, d, q醉箕，d是要刪除的結(jié)點钾腺，把p的后繼結(jié)點改成q即可 (也就是p的后繼的后繼結(jié)點)，刪除標準語句：
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指針為空
- 單鏈表結(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)溉奕，表長沒準時用單結(jié)構(gòu)
靜態(tài)鏈表
不用指針褂傀，而是用數(shù)組描述的鏈表；讓數(shù)組的元素由兩個數(shù)據(jù)域組成加勤，每個下標都對應(yīng)一個data和cur(稱作游標, 相當(dāng)于next指針)仙辟，也稱作游標實現(xiàn)法
- 數(shù)組中的首尾元素作為特殊元素處理不存數(shù)據(jù)，把未使用的數(shù)組元素稱為備用鏈表鳄梅，首元素的cur存放備用鏈表的第一個結(jié)點的下標叠国，尾元素的cur存放第一個有數(shù)值的元素的下標，最后一個有值元素的cur為0
- 插入操作：先把要插入的數(shù)據(jù)賦給備用鏈表元素戴尸，再通過把插入位置前的元素的cur指向備用鏈表元素同時把原指向賦給備用鏈表元素的cur(需定義類似
malloc()的函數(shù)來分配備用下標粟焊，以實現(xiàn)動態(tài)鏈表的節(jié)點申請) - 刪除操作：把首元素的cur賦給將目標元素的cur，再把首元素的cur指向目標元素
- 靜態(tài)鏈表優(yōu)劣：
- 優(yōu)點：插入和刪除只需修改游標孙蒙，免去移動元素的操作
- 缺點：連續(xù)存儲分配使表長難以確定项棠；失去順序存儲結(jié)構(gòu)隨機存取的特性
- 總結(jié)：靜態(tài)鏈表是為了給沒有指針的高級語言設(shè)計的一種實現(xiàn)單鏈表的方法，根據(jù)實際需要使用
循環(huán)鏈表
將單鏈表中終端結(jié)點的指針端由空指針改為指向頭結(jié)點挎峦，使整個單鏈表形成一個環(huán)香追，這種頭尾相接的單鏈表稱為單鏈表循環(huán)，簡稱循環(huán)鏈表
- 與單鏈表的主要差異在于循環(huán)的判斷條件上：若
p->next不等于頭結(jié)點坦胶，則循環(huán)未結(jié)束 - 將兩個循環(huán)鏈表合并成一個表時用尾指針操作會方便很多
雙向鏈表
在單鏈表中透典，查找下一結(jié)點需要O(1)，若要查找上個結(jié)點最壞需要O(n)顿苇，為解決此問題人們設(shè)計出了雙向鏈表：在單鏈表的每個結(jié)點中再設(shè)置一個指向其前驅(qū)節(jié)點的指針域(prior)掷匠，也就是用空間換時間
- 一個節(jié)點前驅(qū)的后續(xù)等于本身：
p->next->prior= p = p->prior->next - 與單鏈表不同的是：在插入和刪除時需要更改兩個指針變量(注意順序)
