線性表

含義

零個或多個數(shù)據(jù)元素的有限序列。

在一個較復雜的線性表中常摧，一個數(shù)據(jù)表可以由若干個數(shù)據(jù)項組成钳垮，比如：

學號	姓名	性別	出生年月	家庭住址
1
2
…

抽象數(shù)據(jù)類型定義

ADT 線性表(List)

Data
  線性表的數(shù)據(jù)對象元素集合為{a1,a2,...,an}，每個元素的類型均為DataType口渔。數(shù)據(jù)元素之間的關(guān)系都是一對一關(guān)系。

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ù)

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

#define MAXSIZE 20
typedef int ElemType
typedef struct {
  ElemType data[MAXSIZE]
  int length
}SqList

需要三個屬性：

存儲空間的起始位置
最大存儲容量，數(shù)組長度MAXSIZE
當前長度——length

操作	步驟	時間復雜度
GetElem	a[i] = e	O(1)
ListInsert	1. i不合法咧党，拋錯;	O(n)
	2. length >= MaxSize秘蛔，拋錯;
	3. a[i + 1] = a[i];
	4. a[i] = e;
	5. L.length ++
ListDelete	1. i不合法，拋錯;	O(n)
	2. e = a[i];
	3. a[i] = a[i+1];
	4. L.length --

優(yōu)點	缺點
1. 無須為表示表中元素之間邏輯而增加額外的存儲空間	1. 插入刪除O(n)
2, 可快速存取表中任一位置元素	2. 線性表長度變化較大傍衡，無法確定MaxSize
	3. 造成存儲空間碎片

鏈式存儲結(jié)構(gòu)

1 -> 2 -> 3

為了表示每個數(shù)據(jù)元素ai與其后繼數(shù)據(jù)元素ai+1之間的邏輯關(guān)系深员，對數(shù)據(jù)元素ai來說，不僅要存儲本身數(shù)據(jù)信息蛙埂，還要存儲指示其直接后繼的指針倦畅。

頭指針 —— 鏈表中第一個結(jié)點的存儲位置
頭結(jié)點 —— 為了方便對鏈表進行操作，會在單鏈表第一個結(jié)點前附設(shè)一個結(jié)點绣的，數(shù)據(jù)域可以不存儲任何信息

| | 0100| -> |a1|0700| ->...->|an|Null|
頭結(jié)點尾結(jié)點

頭指針	頭結(jié)點
指向鏈表第一個結(jié)點的指針叠赐，若有頭結(jié)點，就指向頭結(jié)點	為了操作方便和統(tǒng)一而設(shè)立屡江，放在第一元素結(jié)點之前芭概，一般無意義數(shù)據(jù)
頭指針具有標識作用，常冠以鏈表名字	有了頭結(jié)點惩嘉，對第一元素的操作和其他結(jié)點一致
無論鏈表是否為空罢洲，頭指針均不為空	不一定是鏈表必要元素

typedef struct Node {
  ElemType data;
  struct Node *next;
}Node
typedef struct Node *LinkList

image.png

操作	步驟	時間復雜度
GetElem	1. p = L->next j = 1	O(n)
	2. p = p -> next j ++ while(j < i)
	3. 若p = Null 說明第i個元素不存在
	4. *e = p -> next
ListInsert	1. GetElem(L, i , *e)	查找O(n)
	2. 查找成功，s->data = e	插入O(1)
	3. s->next = p->next p->next = s
	4. a[i] = e;
	5. L.length ++
ListDelete	1. GetElem(L, i , *e)	查找O(n)
	2. 查找成功文黎，q = p -> next	刪除O(1)
	3. p -> next = q -> next
	4. e = q -> data
	5. free(q)
整表創(chuàng)建——頭插法	1. InitList(* L) *L -> next = Null	O(n)
	2. 循環(huán)將結(jié)點p插入頭結(jié)點與前一個新結(jié)點之間
整表創(chuàng)建——尾插法	1. InitList(* L) *L -> next = Null
	2. 循環(huán)將結(jié)點p插入尾部
	3. 循環(huán)結(jié)束惹苗，p -> next = Null
ClearList	1. LinkList p, q	O(n)
	2. p = (*L) -> next
	3. 循環(huán)： q = p -> next free(p) q = p
	4. 循環(huán)結(jié)束 (L*) -> next = Null

單鏈表 VS 循環(huán)鏈表

	單鏈表結(jié)構(gòu)	順序存儲結(jié)構(gòu)
存儲分配方式	任意存儲單元存放元素	連續(xù)存儲單元依次存放元素
時間性能：查找、插入耸峭、刪除	查找O(n) 插入刪除：找到位置后操作O(1)	查找O(1) 插入刪除O(n)
空間性能	不需要分配存儲空間桩蓉，元素個數(shù)不受限制	需要預(yù)分配空間，會造成浪費式上溢

靜態(tài)鏈表

用來滿足沒有指針的一些語言可以創(chuàng)建單鏈表

數(shù)組的元素都是由兩個數(shù)據(jù)域組成：

data：存放數(shù)據(jù)
curr：相當于單鏈表中的next指針

#define MAXSIZE 1000
typedef struct {
  ElemType data;
  int curr;
} Component, StackLinkList[MAXSIZE]

約定：

數(shù)組的一個元素curr指向備用鏈表的第一個結(jié)點的下標劳闹；
數(shù)組的最后一個元素curr指向第一個有數(shù)據(jù)的元素的下標触机；
數(shù)組的第一個元素和最后一個元素不存儲任何數(shù)據(jù)

image.png

如上圖所示帚戳，這個是1000個元素的靜態(tài)鏈表，第0個和第999個元素都不存儲任何數(shù)據(jù)儡首，其中第0個元素curr指向第一個沒有數(shù)據(jù)的元素——坐標為4片任，第999個元素指向第一個有數(shù)據(jù)的元素——坐標為1，最后一個有數(shù)據(jù)的元素3指向頭結(jié)點——坐標為0蔬胯。

操作	步驟
ListInsert	1. 將元素插入到備用鏈表的首位p
	2. arr[0].curr = arr[p].curr
	3. 找到p前的元素q
	4. arr[q].curr = p
ListDelete	1. 找到要刪除的元素前一個元素的位置p
	2. arr[p].curr = arr[q].curr
	3. arr[q].curr = arr[0].curr
	4. arr[0].curr = q

優(yōu)點	缺點
插入刪除時对供，不需要移動元素	沒有解決需要提前分配存儲空間的問題；失去了順序存儲結(jié)構(gòu)隨機存取的特性

循環(huán)鏈表

空表.png

循環(huán)判斷：p -> next == 頭結(jié)點氛濒，則循環(huán)結(jié)束

雙向鏈表