第3章 線性表
線性表：零個或多個數(shù)據(jù)元素的有限序列妥衣。
線性表的定義
線性表(List):零個或多個數(shù)據(jù)元素的有限序列愤兵。
線性表元素的個數(shù) n (n>=0) 定義為線性表的長度络它，當 n = 0時辙培，稱為空表。
線性表的抽象數(shù)據(jù)類型
ADT 線性表(List)
Data
線性表的數(shù)據(jù)對象集合為{a1,a2,……,an},每個元素的類型均為DataType娜谊。其中属划，除第一個元素a1外恬叹，每一個元素有且只有一個直接前驅元素，除了最后一個元素an外同眯，每一個元素有且只有一個直接后繼元素绽昼。數(shù)據(jù)元素之間的關系是一對一的關系。
Operation
? InitList (*L):初始化操作须蜗，建立一個空的線性表L硅确。
? ListEmpty(L)：若線性表為空，返回true明肮，否則返回false菱农。
? ClearList(*L)：將線性表清空。
? GetElem(L,i,*e)：在線性表L中的第i個位置元素值返回給e柿估。
? LocateElem(L,e)：在線性表L中查找與給定值e相等的元素循未，如果查找成功，返回該元素在表中的序號表示成功秫舌；否則只厘，返回0表示失敗烙丛。
? ListInsert(*L,i,e)：在線性表L中的第i個位置插入新元素e。
? ListDelete(*L,i, *e)：刪除線性表L中的第i個位置元素羔味，并用e返回其值。
? ListLength(L)：返回線性表L的元素個數(shù)钠右。
endADT
線性表的順序存儲結構
順序存儲定義
線性表的順序存儲結構赋元，指的是用一段地址連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素。
順序存儲方式
一維數(shù)組來實現(xiàn)順序存儲結構飒房。
數(shù)組長度與線性表長度區(qū)別
數(shù)組的長度是存放線性表的存儲空間的長度搁凸。線性表的長度是線性表中數(shù)據(jù)元素的個數(shù)。在任意時刻狠毯，線性表的長度應該小于等于數(shù)組的長度护糖。
地址計算方法
存儲器中每個存儲單元都有自己的編號，這個編號稱為地址嚼松。
LOC(ai) = LOC(a1) + (i-1)*c
存取的時間性能為O(1)嫡良。
順序存儲結構的插入與刪除
獲得元素操作
只要i的數(shù)值在數(shù)組的下標范圍內，就是把數(shù)組的第i-1下標的值返回即可献酗。
插入操作
插入算法的思路：
- 如果插入位置不合理寝受，拋出異常；
- 如果線性表的長度大于等于數(shù)組長度罕偎，則拋出異澈艹危或動態(tài)增加容量；
- 從最后一個元素開始向前遍歷到第i個位置颜及，分別將它們都向后移動一個位置甩苛；
- 將要插入元素填入位置i處；
- 表長加1俏站。
刪除操作
刪除算法的思路：
- 如果刪除位置不合理讯蒲，拋出異常；
- 取出刪除元素乾翔；
- 從刪除元素位置開始遍歷到最后一個元素位置爱葵，分別將它們都向前移動一個位置；
- 表長減1反浓。
插入和刪除的時間復雜度萌丈，最好情況為O(1)，最壞情況為O(n)雷则，平均時間復雜度為O(n)辆雾。
線性表順序存儲結構的優(yōu)缺點
優(yōu)點：
- 無須為表示表中元素之間的邏輯關系而增加額外的存儲空間。
- 可以快速地存取表中任一位置的元素月劈。
缺點：
- 插入和刪除操作需要移動大量元素度迂。
- 當線性表長度變化較大時藤乙，難以確定存儲空間的容量。
- 造成存儲空間的"碎片"惭墓。
線性表的鏈式存儲結構
線性表鏈式存儲結構定義
? 為了表示每個數(shù)據(jù)元素ai與其直接后繼數(shù)據(jù)元素ai+1之間的邏輯關系坛梁，對數(shù)據(jù)元素ai來說，除了存儲其本身的信息之外腊凶，還需存儲一個指示其直接后繼的信息(即直接后繼的存儲位置)划咐。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲直接后繼位置的域稱為指針域钧萍。指針域中存儲的信息稱作指針或鏈褐缠。這兩部分信息組成數(shù)據(jù)元素ai的存儲映像，稱為結點(Node)风瘦。
? n個結點(ai的存儲映像)鏈結成一個鏈表队魏，即為線性表(a1,a2,...,an)的鏈式存儲結構，因為此鏈表的每個結點中只包含一個指針域万搔，所以叫做單鏈表胡桨。
? 鏈表中的第一個結點的存儲位置叫做頭指針搂鲫。在單鏈表的第一個結點前附設一個結點褒傅，稱為頭結點。頭結點的指針域存儲指向第一個結點的指針塔逃。
線性表鏈式存儲結構代碼描述
單鏈表中挖炬，我們在C語言中可用結構指針來描述揽浙。
/*線性表的單鏈表存儲結構*/
typedef struct Node
{
ElemType data;
struct Node *next;
} Node;
typedef struct Node *LinkList; /*定義LinkList*/
單鏈表的讀取
獲取鏈表第i個數(shù)據(jù)的算法思路：
- 聲明一個指針p指向鏈表的第一個結點意敛，初始化j從1開始；
- 當j<i時草姻，就遍歷鏈表，讓p的指針向后移動撩独，不斷指向下一結點敞曹，j累加1；
- 若到鏈表末尾p為空综膀，則說明第i個結點不存在；
- 否則查找成功剧劝，返回結點p的數(shù)據(jù)。
單鏈表的插入與刪除
單鏈表的插入
單鏈表第i個數(shù)據(jù)插入結點的算法思路：
- 聲明一指針p指向鏈表頭結點，初始化j從1開始拢锹；
- 當j<i時谣妻，就遍歷鏈表，讓p的指針向后移動卒稳，不斷指向下一結點蹋半，j累加1充坑；
- 若到鏈表末尾p為空，則說明第i個結點不存在匪傍；
- 否則查找成功觉痛，在系統(tǒng)中生成一個空節(jié)點s；
- 將數(shù)據(jù)元素e賦值給s->data;
- 單鏈表的插入標準語句s->next = p->next; p->next = s;
- 返回成功薪棒。
單鏈表的刪除
單鏈表第i個數(shù)據(jù)刪除結點的算法思路：
- 聲明一指針p指向鏈表頭指針，初始化j從1開始俐芯；
- 當j<i時，就遍歷鏈表吧史，讓p的指針向后移動，不斷指向下一個結點吨述，j累加1钞脂；
- 若到鏈表末尾p為空揣云，則說明第i個結點不存在冰啃；
- 否則查找成功，將欲刪除的結點p->next賦值給q阎毅；
- 單鏈表的刪除標準語句p->next = q->next;
- 將q結點中的數(shù)據(jù)賦值給e，作為返回汪榔；
- 釋放q結點。
- 返回成功痴腌。
單鏈表的整表創(chuàng)建
頭插法
尾插法
單鏈表的整表刪除
單鏈表整表刪除的算法思路如下：
- 聲明一節(jié)點p和q；
- 將第一個結點賦值給p士聪；
- 循環(huán)：
- 將下一個結點賦值給q；
- 釋放p剥悟；
- 將q賦值給p。
單鏈表結構與順序存儲結構優(yōu)缺點
存儲分配方式
- 順序存儲結構用一段連續(xù)的存儲單元依次存儲線性表的數(shù)據(jù)元素略板。
- 單鏈表采用鏈式存儲結構，用一組任意的存儲單元存放線性表中的元素叮称。
時間性能
- 查找 順序存儲結構O(1) 單鏈表O(n)
- 插入和刪除 順序存儲結構需要平均移動表長一半的元素藐鹤，時間為O(n) 單鏈表在顯出某位置的指針后瓤檐，插入和刪除時間僅為O(1)
空間性能
- 順序存儲結構需要預分配存儲空間，分大了娱节，浪費挠蛉，分小了易發(fā)生上溢。
- 單鏈表不需要分配存儲空間肄满，只要有就可以分配，元素個數(shù)也不受限制悄窃。
靜態(tài)鏈表
用數(shù)組描述的鏈表叫做靜態(tài)鏈表，這種描述方法還有起名叫做游標實現(xiàn)法轧抗。
靜態(tài)鏈表優(yōu)缺點
優(yōu)點：在插入和刪除操作時，只需要修改游標纠炮，不需要移動元素灯蝴，從而改進了順序存儲結構中的插入和刪除操作需要移動大量元素的缺點。
缺點：
- 沒有解決連續(xù)存儲分配帶來的表長難以確定的問題穷躁。
- 失去了順序存儲結構隨機性存取的特性。
循環(huán)鏈表
將單鏈表中終端節(jié)點的指針端由空指針改為指向頭結點，就使整個單鏈表形成一個環(huán)婚被，這種頭尾相接的單鏈表稱為單循環(huán)鏈表梳虽，簡稱循環(huán)鏈表(circular linked list)。
雙向鏈表
雙向鏈表(double linked list)是在單鏈表的每個結點中窜觉，再設置一個指向其前驅結點的指針域。
