1. 引子：什么是鏈表
經過學習與練習，已經掌握了順序表的相關知識并且能夠自我實現。在這一過程中，通過對其結構的實現，發(fā)現順序表的尾部插入刪除數據效率很高，可是，在頭部與隨機插入的場景下效率低下而且存在擴容消耗等一些問題。而有這樣一種數據結構可以很好的解決順序表存在的這些問題，將瑣碎的系統(tǒng)空間充分利用，任意位置的插入刪除效率都很高。此種數據結構稱為鏈表，接下來進行對其的學習。
2. 簡單數據結構：鏈表
2.1 鏈表簡介與功能分析
簡介：
鏈表，正如其名，存儲其中的數據在物理上是離散的，各個數據間使用一條 “鏈子” 串聯而成（記錄下一元素地址的指針）。鏈表的具體結構存在數種，以是否帶頭，是否能雙向訪問，是否循環(huán)，這三個特點被簡單分為六種，下面，我們先進行其中一種，帶頭單向不循環(huán)鏈表進行學習。
單向帶頭不循環(huán)鏈表結構圖：
功能分析模塊：
數據存儲方式：
- 動態(tài)開辟malloc的一塊塊小內存塊。
- 存儲信息為數據值，與記錄下一個結點的指針
以上兩點創(chuàng)建的結點結構體數據管理方式：
- 增（頭插，尾插，隨機插入）：push_front，push_back，insert，insertafter
- 刪（頭刪，尾刪，隨機刪除）：pop_front，pop_back，erase，eraseafter
- 改（指定數據的修改）：modify
- 查（指定數據的查詢）：find
2.2 單鏈表的實現
2.2.1 單鏈表：存儲數據的結構體
鏈表結點的構建：
typedef int ListDataType;
typedef struct ListNode
{
ListDataType val;
//聲明類型的過程中不能直接使用typedef后的名字
struct ListNode* next;
}ListNode;
2.2.2 單鏈表：結點創(chuàng)建與鏈表數據清理
結點創(chuàng)建：
ListNode* BuyNewNode(ListDataType val)
{
ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
if (newnode == NULL)
{
perror("malloc failed");
exit(-1);
}
newnode->val = val;
newnode->next = NULL;
return newnode;
}
鏈表銷毀：
過程演示：
//鏈表銷毀
void ListDestroy(ListNode** PPhead)
{
assert(PPhead);
ListNode* Phead = *PPhead;
ListNode* cout = Phead;
if (Phead != NULL)
{
while (Phead->next != NULL)
{
Phead = Phead->next;
free(cout);
cout = Phead;
}
free(Phead);
*PPhead = NULL;
}
}
注：Phead為list的一份值拷貝，因此要想能夠改變list（鏈表頭）的值，傳參是我們應該采用二重指針傳址傳參。
2.2.2 單鏈表插入數據與刪除
頭插，頭刪：
頭插過程演示：
鏈表為空時頭插：
鏈表不為空時頭插：
頭刪過程演示：
//頭插
void ListPush_Front(ListNode** PPhead, ListDataType val)
{
assert(PPhead);
ListNode* Phead = *PPhead;
ListNode* newnode = BuyNewNode(val);
if (Phead == NULL)
{
*PPhead = newnode;
}
else
{
ListNode* next = Phead;
newnode->next = Phead;
*PPhead = newnode;
}
}
//頭刪
void ListPop_Front(ListNode** PPhead)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
ListNode* next = Phead->next;
free(Phead);
*PPhead = next;
}
尾插，尾刪：
//尾插
void ListPush_Back(ListNode** PPhead, ListDataType val)
{
assert(PPhead);
ListNode* Phead = *PPhead;
ListNode* end_node = Phead;
while (end_node != NULL && end_node->next != NULL)
{
end_node = end_node->next;
}
ListNode* newnode = BuyNewNode(val);
if (end_node == NULL)
{
*PPhead = newnode;
}
else//end_node->next == NULL
{
end_node->next = newnode;
}
}
//尾刪
void ListPop_Back(ListNode** PPhead)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
ListNode* end_node = Phead;
//特殊情況
if (end_node->next == NULL)
{
free(end_node);
*PPhead = NULL;
}
else//end_node->next != NULL
{
//邏輯短路
while (end_node->next->next != NULL)
{
end_node = end_node->next;
}
free(end_node->next);
end_node->next = NULL;
}
}
隨機插入與刪除：
在指定結點（pos）之前插入：
void ListInsert(ListNode** PPhead, ListNode* pos, ListDataType val)
{
//不考慮結點不存在的情況
//與ListFind模塊配合使用
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
assert(pos);
//復用頭插
if (pos == Phead)
{
ListPush_Front(PPhead, val);
}
else
{
ListNode* search = Phead;
//尋找pos結點
while (search->next != pos)
{
search = search->next;
}
//插入
ListNode* newnode = BuyNewNode(val);
ListNode* next = search->next;
search->next = newnode;
newnode->next = next;
}
}
在指定結點（pos）之后插入：
void ListInsertAfter(ListNode* pos, ListDataType val)
{
//結點不能為NULL
assert(pos);
ListNode* next = pos->next;
ListNode* newnode = BuyNewNode(val);
pos->next = newnode;
newnode->next = next;
}
刪除指定結點（pos）之后的結點：
void ListEraseAfter(ListNode* pos)
{
assert(pos);
assert(pos->next);
ListNode* next = pos->next;
pos->next = pos->next->next;
free(next);
next = NULL;
pos->next = next;
}
刪除指定結點（pos）：
void ListErase(ListNode** PPhead, ListNode* pos)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
assert(pos);
//頭刪
if (pos == Phead)
{
ListPop_Front(PPhead);
}
else
{
ListNode* search = Phead;
while (search->next != pos)
{
search = search->next;
}
ListNode* next = search->next->next;
free(search->next);
search->next = next;
}
}
2.2.3 單鏈表查詢與修改
元素查詢：
ListNode* ListFind(ListNode** PPhead, ListDataType val)
{
assert(PPhead);
ListNode* Phead = *PPhead;
assert(Phead);
ListNode* search = Phead;
while (search != NULL && search->val != val)
{
search = search->next;
}
return search;
}
數據修改：文章來源：http://www.zghlxwxcb.cn/news/detail-807525.html
void ListModify(ListNode* Node, ListDataType val)
{
assert(Node);
Node->val = val;
}
鏈表元素打?。?span toymoban-style="hidden">文章來源地址http://www.zghlxwxcb.cn/news/detail-807525.html
void ListPrint(ListNode* Phead)
{
while (Phead != NULL)
{
printf("%d->", Phead->val);
Phead = Phead->next;
}
printf("NULL\n");
}
到了這里，關于初階數據結構：鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
