### 一、線性表定義
線性表：零個或多個數據元素的**有限**序列。（零個的時候是空表）
線性表的特性是：除了第一個元素（只有后繼）和最后一個元素（只有前驅），每個元素都只有一個前驅和后繼。
### 二、線性表的抽象數據類型
線性表的抽象數據類型定義如下：
### 三、線性表的順序存儲結構
線性表的順序存儲結構，指的是用一段地址連續的存儲單元依次存儲線性表的數據元素。
來看線性表順序存儲結構代碼：
發現描述順序存儲結構需要三個屬性：
1.儲存空間的起始位置：數組data，它的存儲位置就是存儲空間的存儲位置。
2.線性表的最大存儲容量：數組長度MaxSize。
3.線性表的當前長度：length。
下面再討論一下地址的計算方法：
### 四、順序存儲結構的插入與刪除
獲得元素的操作：
插入操作：
刪除操作：
線性表的順序存儲結構的優缺點：
優點：1.無需為表示表中元素之間的邏輯關系而增加額外的存儲空間2.可以快速地存取表中任一位置的元素。
缺點：1.插入和刪除操作需要移動大量元素2.當線性表長度變化較大時，難以確定存儲空間的容量3.造成存儲空間的碎片。
### 五、線性表的鏈式存儲結構
n個節點鏈結成一個鏈表，即為線性表的鏈式存儲結構，因為此鏈表的每一個節點中只包含一個指針域，所以叫做單鏈表。
把鏈表中第一個節點的存儲位置叫做頭指針，最后一個節點指針為空。
一般為了方便對鏈表進行操作，會在單鏈表的第一個結點前附設一個結點，成為頭結點。頭結點的**數據域可以不保存任何信息**。
頭指針和頭結點的異同：
**頭指針**是指向頭結點的指針；頭指針具有標識作用，所以常用頭指針冠以鏈表的名字；無論鏈表是否為空，頭指針均不為空。頭指針是鏈表的必要元素。
**頭結點**是為了操作的統一和方便而設立的，放在第一個元素的結點之前，其數據域一般無意義（也可以存放鏈表的長度）；有了頭結點，對在第一個元素結點前插入結點和刪除第一結點，其操作與其他結點的操作就統一了；頭結點不一定是鏈表的必須元素。
結點的概念：結點由存放數據元素的**數據域**存放后繼結點的**指針域**組成。
假設P是指向線性表的第i個元素的指針，則該節點aI的數據域我們可以用p->data來表示，p->data的值是一個數據元素，結點aI的指針域可以用p->next來表示，p->next的值是一個指針。如果p->data=ai,那么p->next->data=aI+1。即：
### 六、單鏈表的讀取
由上面程序看出來，獲取鏈表獲取第i個元素比較麻煩。
### 七、單鏈表的插入與刪除
插入結點：
刪除結點：
由算法可以看出，插入和刪除對于鏈表來說每次只需要簡單地通過賦值移動指針而已，時間復雜度都是O(1),顯然，對于插入和刪除數據越頻繁的操作，單鏈表的效率優勢就越是明顯。
### 八、單鏈表的整表創建
頭插法：
尾插法：
### 九、單鏈表的整表刪除
十、單鏈表結構與順序存儲結構優缺點
### 十一、循環鏈表
將單鏈表的終端結點的指針端由空指針改為指向頭結點，就使整個單鏈表形成了一個環，這種頭尾相連的單鏈表稱為單循環鏈表，簡稱循環鏈表。
下面研究一下循環鏈表的合并：
分成4步：
1.p=rearA->next;
2.rearA->next=rearB->next->next;
3.rearB->next=p;
4.free(p).
### 十二、雙向鏈表
雙向鏈表概念：雙向鏈表是在單鏈表的每個結點中，再設置一個指向其前驅結點的指針域。
雙向鏈表插入操作：
同樣也分成4步：
1.s->prior=p;
2.s->next=p->next;
3.p->next->prior=s;
4.p->next=s.
雙向鏈表的刪除操作：
分成3步：
1.p->prior->next=p->next;
2.p->next->prior=p->prior;
3.free(p).
### 十三、總結
