前言
上篇文章學(xué)習(xí)了線性表的順序存儲(chǔ)結(jié)構(gòu)，不過(guò)，在代碼的實(shí)現(xiàn)過(guò)程中，發(fā)現(xiàn)了順序表的一個(gè)很大的問(wèn)題：插入和刪除需要移動(dòng)大量的數(shù)據(jù)元素，那如何解決這個(gè)問(wèn)題?
鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
前篇文章有談到過(guò)線性表的存儲(chǔ)方式，一種是順序存儲(chǔ)結(jié)構(gòu)，另一種是鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。我們?cè)賮?lái)回顧一下鏈?zhǔn)酱鎯?chǔ)的定義
為了表示每個(gè)數(shù)據(jù)元素與其直接后繼元素之間的邏輯關(guān)系，每個(gè)元素除了存儲(chǔ)本身的信息外，還需要存儲(chǔ)指示其直接后繼的信息
單鏈表
上面的定義有提到邏輯關(guān)系，有一種常見(jiàn)的鏈?zhǔn)酱鎯?chǔ)邏輯結(jié)構(gòu)可以體現(xiàn)：單鏈表。
n個(gè)結(jié)點(diǎn)鏈接成一個(gè)鏈?zhǔn)骄€性表的結(jié)構(gòu)叫做鏈表，當(dāng)每個(gè)結(jié)點(diǎn)中包含一個(gè)指針域時(shí)，叫做單鏈表
鏈表的基本概念
上面的定義有提到鏈表，一個(gè)鏈表一般可以分為三個(gè)部分：
-
表頭結(jié)點(diǎn)
鏈表中的第一個(gè)結(jié)點(diǎn)，包含指向第一個(gè)數(shù)據(jù)元素的指針以及鏈表自身的一些信息
-
數(shù)據(jù)結(jié)點(diǎn)
鏈表中代表數(shù)據(jù)元素的結(jié)點(diǎn)，包含指向下一個(gè)數(shù)據(jù)元素的指針和數(shù)據(jù)元素的信息
-
尾結(jié)點(diǎn)
鏈表中的最后一個(gè)數(shù)據(jù)結(jié)點(diǎn)，其下一個(gè)元素指針為空，也就是指針域?yàn)榭?，表示無(wú)后繼
單鏈表結(jié)構(gòu)圖
實(shí)現(xiàn)單鏈表
在頭文件中聲明需要實(shí)現(xiàn)單鏈表的操作
typedef void LinkList;
typedef struct _tag_LinkListNode LinkListNode;
/**在C語(yǔ)言中可以用結(jié)構(gòu)體來(lái)定義鏈表中指針域*/
struct _tag_LinkListNode {
/**指向下個(gè)元素的指針*/
LinkListNode *next;
};
/**數(shù)據(jù)元素結(jié)點(diǎn)*/
typedef struct Value {
LinkListNode next;
int value;
} TValue;
LinkList *createLinkList();
void destroyLinkList(LinkList *list);
void clearLinkList(LinkList *list);
int getLinkListLen(LinkList *list);
int addLinkListEle(LinkList *list, LinkListNode *node, int position);
LinkListNode *getLinkListEle(LinkList *list, int position);
LinkListNode *deleteLinkListEle(LinkList *list,int position);
在實(shí)現(xiàn)的文件中定義頭節(jié)點(diǎn)
/**
* 定義表頭結(jié)點(diǎn)
*/
typedef struct _tag_LinkList {
/**指向第一個(gè)元素的頭指針*/
LinkListNode header;
/**整個(gè)單鏈表的長(zhǎng)度*/
int length;
} TLinkList;
單鏈表的添加元素操作
/**
* 添加元素到單鏈表中指定位置
* @param list
* @param node
* @param position 在鏈表中的索引值
* @return
*/
int addLinkListEle(LinkList *list, LinkListNode *node, int position) {
TLinkList *linkList = (TLinkList *) list;
/**判斷單鏈表、插入的元素以及插入的位置的合法性*/
int ret = (linkList != NULL) && (node != NULL) && (position >= 0);
int i;
if (ret) {
/** step 1 開(kāi)始位置指向表頭*/
LinkListNode *current = (LinkListNode *) linkList;
for (i = 0; i < position && current->next != NULL; i++) {
/**
* step 2 由表頭開(kāi)始通過(guò)next指針移動(dòng)position次
* 第position處的下一個(gè)元素就是要插入的位置，也就
* 是當(dāng)前元素的current->next。
*/
current = current->next;
}
/**
* step 3 交換當(dāng)前元素和插入元素的指針域
* 注：這兩步順序不能搞反，否則會(huì)導(dǎo)致單鏈
* 表斷鏈
*/
node->next = current->next;
current->next = node;
/**更新單鏈表長(zhǎng)度*/
linkList->length++;
}
return ret;
}
這里的核心算法就是step 2和step 3這兩步。我們可以通過(guò)圖來(lái)加深理解。請(qǐng)注意圖中的第2步與第1步是順序是不能搞反的，否則會(huì)導(dǎo)致斷鏈
單鏈表的刪除元素操作
/**
* 刪除鏈表中指定的元素
* @param list
* @param position 被刪除元素在鏈表中的索引值
* @return
*/
LinkListNode *deleteLinkListEle(LinkList *list, int position) {
TLinkList *linkList = (TLinkList *) list;
LinkListNode *node = NULL;
if (linkList != NULL && position >= 0 && position < linkList->length) {
LinkListNode *current = (LinkListNode *) linkList;
/**獲取第position處元素，該元素的next指針域就是需要?jiǎng)h除的元素*/
for (int i = 0; i < position; i++) {
current = current->next;
}
node = current->next;
current->next = node->next;
linkList->length--;
}
return node;
}
獲取元素
/**
* 獲取指定位置的元素
* @param list
* @param position 被獲取元素在鏈表中的索引值
* @return
*/
LinkListNode *getLinkListEle(LinkList *list, int position) {
TLinkList *linkList = (TLinkList *) list;
LinkListNode *node = NULL;
int i;
if (linkList != NULL && position >= 0 && position < linkList->length) {
/** step 1 開(kāi)始位置指向表頭*/
LinkListNode *current = (LinkListNode *) linkList;
for (i = 0; i < position; i++) {
/** step 2 由表頭開(kāi)始通過(guò)next指針移動(dòng)position次*/
current = current->next;
}
/** step 3 當(dāng)前元素的next指針即指向要獲取的元素*/
node = current->next;
}
return node;
}
總結(jié)
單鏈表的一些主要操作就都已經(jīng)實(shí)現(xiàn)完了，代碼中注釋很清楚，再加上圖一起來(lái)理解就更非常容易了(完整代碼)。那它與上篇文章學(xué)過(guò)的順序表有哪些優(yōu)缺點(diǎn)了？
-
優(yōu)點(diǎn)：
- 無(wú)需一次性定制鏈表的容量
- 插入和刪除無(wú)需移動(dòng)數(shù)據(jù)元素
-
缺點(diǎn)
- 數(shù)據(jù)元素必須保存后繼元素的位位置信息
- 獲取指定數(shù)據(jù)的元素操作需要順序訪問(wèn)之前的元素
