接上篇線性表 (一)
四优妙、線性表的物理結(jié)構(gòu)--鏈式存儲結(jié)構(gòu)
4.1 定義
順序存儲結(jié)構(gòu)的最大缺點就是插入和刪除的時候需要移動大量元素，十分耗時憎账。
鏈式存儲結(jié)構(gòu)中套硼，不考慮所有元素的位置，只是讓每個元素知道它下一個元素的位置在哪里胞皱，所有元素像一條繩子串起來的珠子邪意，只是這些珠子的位置是散亂的九妈。
這種結(jié)構(gòu)下，我們可以在知道第一個元素時就知道第二個元素的內(nèi)存地址雾鬼，知道第二個元素時能找到第三個元素的地址......
以前在順序存儲中萌朱，每個數(shù)據(jù)元素只需要存儲本身的元素信息就行了，而在鏈式存儲結(jié)構(gòu)中策菜，除了存儲本身的元素外還需要存儲下一個元素的地址信息晶疼。我們把存儲數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域，把存儲后續(xù)位置的域稱為指針域又憨。這兩部分信息組成數(shù)據(jù)元素a的存儲映象翠霍，稱為結(jié)點（Node）。
n個結(jié)點鏈接成的一個鏈表即為線性表的鏈式存儲結(jié)構(gòu)蠢莺，簡稱鏈表寒匙。因為這個鏈表的每個結(jié)點都只有一個指針域，所以稱為單鏈表躏将。
單鏈表正是通過每個結(jié)點的指針域?qū)⒕€性表的數(shù)據(jù)元素按其邏輯次序鏈接在一起的
鏈表中的第一個結(jié)點的存儲位置稱為頭指針锄弱，整個鏈表的存取必須從頭指針開始進行，最后一個指針指向空祸憋，用Null或者^表示,如果圖:
為了方便会宪。我們會在單鏈表的第一個結(jié)點前設置一個結(jié)點，成為頭結(jié)點夺衍。頭結(jié)點的數(shù)據(jù)域可以不存儲任何信息狈谊，也可以存儲如線性表長度等附加信息，頭結(jié)點的指針域存儲指向第一個結(jié)點的指針：
4.2 頭指針與頭結(jié)點的異同
頭指針：
1沟沙、頭指針是指向鏈表第一個節(jié)點的指針河劝，若鏈表有頭節(jié)點，則是指向頭結(jié)點的指針矛紫。
2赎瞎、頭指針具有標識作用，所以常用頭指針冠以鏈表的名字颊咬。
3务甥、無論鏈表是否為空，頭指針均不為空喳篇，頭指針是鏈表的必要元素敞临。頭結(jié)點：
1、頭結(jié)點是為了方便操作的統(tǒng)一而設立的麸澜，放在第一個元素的節(jié)點之前挺尿，其數(shù)據(jù)域無意義，也可以存儲一些公共信息。
2编矾、有了頭結(jié)點熟史，對在于第一個元素結(jié)點前插入結(jié)點和刪除結(jié)點，其操作就與其他結(jié)點的操作統(tǒng)一了窄俏。
3蹂匹、頭結(jié)點不一定是鏈表必須要素。
4.3 代碼描述
使用結(jié)構(gòu)指針來描述單鏈表：
typedef stuck Node {
ElemType data;
stuck Node *next;
} Node;
//定義一個鏈表
typedef struct Node *LinkList;
五凹蜈、單鏈表的常見操作
5.1 讀取
算法思路：
- 聲明一個p指針指向鏈表第一個結(jié)點限寞，初始化j從1開始
- 當j<i時遍歷鏈表，讓p向后移動踪区，j累加
- 若鏈表末尾p為空則說明第i個結(jié)點不存在
- 否則查找成功昆烁，返回p結(jié)點的數(shù)據(jù)
代碼實現(xiàn)：
status GetElem(LinkList L, int i, ElemType *e) {
int j = 1;
LinkList p;
p = L->next;
while (j<i && p) {
p = p -> next;
j++;
}
if (!p || j>i) {
return ERROR;
}
*e = p->data;
return OK;
}
尋找鏈表中點
算法思想
- 聲明一個快指針，一個慢指針缎岗。
- 塊指針一次走一步静尼，慢指針一次走兩步。
- 當快指針到達終點時传泊，慢指針剛好在單鏈表的中點
- 返回慢指針所指向的結(jié)點元素
status FindMidElem (LinkList L) {
LinkList fastP = L->next->next;
LinkList slowP = L->next;
int j=1;
while (j < L->length) {
fastP = fastP->next->next;
slowP = slowP->next;
}
return slowP->data;
}
查找元素的時間復雜度取決于i的位置鼠渺，所以時間復雜度為O(n)。
5.2 單鏈表的插入
算法思路：
- 先找到需要插入的位置：聲明一個指向鏈表頭的結(jié)點眷细，初始化j為1拦盹；當j<i時，遍歷鏈表溪椎，讓p的指針向后移動普舆，j累加1；若最后p指針為空則插入位置不存在校读，否則p就是所尋找的位置沼侣。
- 在系統(tǒng)中生成一個空結(jié)點s；
- 將元素e的數(shù)據(jù)賦值給s
- 將p->next賦值給s->next,p->next為s
代碼實現(xiàn)：
status insetElem(LinkList *L, int i, ElemType e) {
LikList *p;
LikList *p = GetElem(L, i, e);
if (!e) { return ERROR; }
s = (LinkList)malloc(sizeof(Node));
s->data = e;
s->next = p->next;
p->next = s;
return OK;
}
5.2 單鏈表的刪除
算法思想：
- 先找到需要插入的位置：聲明一個指向鏈表頭的結(jié)點歉秫，初始化j為1蛾洛；當j<i時，遍歷鏈表雁芙，讓p的指針向后移動轧膘，j累加1；若最后p指針為空則插入位置不存在兔甘，否則p就是所尋找的位置谎碍。
- 將欲刪除的結(jié)點p->next賦值給q；
- 將要刪除的結(jié)點q中的元素賦值給e洞焙，作為返回值蟆淀；
- 釋放q結(jié)點
- 返回成功
代碼實現(xiàn)：
status deleteElem(LinkList *L, int i, ElemType *e) {
LinkList *p = GetElem(L,i,e);
if (!e) { return ERROR; }
LinkList *q = p->next;
p->next = q->next;
e = q->data;
free(q);
return OK;
}
