本文借鑒點選跳轉
文章目錄
- 連結清單的介紹
- 連結清單是什麼
- 結點
- 頭結點、頭指針和首元結點
- 連結清單的基本操作
- 插入
- 删除
連結清單的介紹
連結清單是什麼
連結清單又稱單連結清單、鍊式存儲結構，用于存儲邏輯關系為“一對一”的資料。
和順序表不同，使用連結清單存儲資料，不強制要求資料在記憶體中集中存儲，各個元素可以分散存儲在記憶體中。例如，使用連結清單存儲 {1,2,3}，各個元素在記憶體中的存儲狀态可能是：
可以看到，資料不僅沒有集中存放，在記憶體中的存儲次序也是混亂的。那麼，連結清單是如何存儲資料間邏輯關系的呢？
連結清單存儲資料間邏輯關系的實作方案是：為每一個元素配置一個指針，每個元素的指針都指向自己的直接後繼元素，如下圖所示：
顯然，我們隻需要記住元素 1 的存儲位置，通過它的指針就可以找到元素 2，通過元素 2 的指針就可以找到元素 3，以此類推，各個元素的先後次序一目了然。
像圖 2 這樣，資料元素随機存儲在記憶體中，通過指針維系資料之間“一對一”的邏輯關系，這樣的存儲結構就是連結清單。
結點
很多教材中，也将“結點”寫成“節點”，它們是一個意思。
在連結清單中，每個資料元素都配有一個指針，這意味着，連結清單上的每個“元素”都長下圖這個樣子：
資料域用來存儲元素的值，指針域用來存放指針。資料結構中，通常将圖 3 這樣的整體稱為結點。
也就是說，連結清單中實際存放的是一個一個的結點，資料元素存放在各個結點的資料域中。舉個簡單的例子，圖 2 中 {1,2,3} 的存儲狀态用連結清單表示，如下圖所示：
在 C 語言中，可以用結構體表示連結清單中的結點，例如：
typedef char ElemType;
typedef struct node {
ElemType data;
struct Node *link;
} Node; 我們習慣将結點中的指針命名為 next，是以指針域又常稱為“Next 域”。
頭結點、頭指針和首元結點
圖 4 所示的連結清單并不完整，一個完整的連結清單應該由以下幾部分構成：
- 頭指針：一個和結點類型相同的指針，它的特點是：永遠指向連結清單中的第一個結點。上文提到過，我們需要記錄連結清單中第一個元素的存儲位置，就是用頭指針實作。
- 結點：連結清單中的節點又細分為頭結點、首元結點和其它結點：
- 頭結點：某些場景中，為了友善解決問題，會故意在連結清單的開頭放置一個空結點，這樣的結點就稱為頭結點。也就是說，頭結點是位于連結清單開頭、資料域為空（不利用）的結點。
- 首元結點：指的是連結清單開頭第一個存有資料的結點。
- 其他節點：連結清單中其他的節點。
也就是說，一個完整的連結清單是由頭指針和諸多個結點構成的。每個連結清單都必須有頭指針，但頭結點不是必須的。
例如，建立一個包含頭結點的連結清單存儲 {1,2,3}，如下圖所示：
再次強調，頭指針永遠指向連結清單中的第一個結點。換句話說，如果連結清單中包含頭結點，那麼頭指針指向的是頭結點，反之頭指針指向首元結點。
連結清單的基本操作
插入
同順序表一樣，向連結清單中增添元素，根據添加位置不同，可分為以下 3 種情況：
- 插入到連結清單的頭部，作為首元節點；
- 插入到連結清單中間的某個位置；
- 插入到連結清單的最末端，作為連結清單中最後一個結點；
對于有頭結點的連結清單，3 種插入元素的實作思想是相同的，具體步驟是：
- 将新結點的 next 指針指向插入位置後的結點；
- 将插入位置前結點的 next 指針指向插入結點；
例如，在連結清單
{1,2,3,4}
的基礎上分别實作在頭部、中間、尾部插入新元素 5，其實作過程如圖1 所示：
代碼實作
// TODO 添加節點,在最後的位置插入
void appendTail(Node *list, ElemType data) {
// Node* head=list;
Node *node = (Node *) malloc(sizeof(Node));
node->data = data;
node->link = NULL;
while (list->link) {
list = list->link;
}
list->link = node;
} 删除
從連結清單中删除指定資料元素時，實則就是将存有該資料元素的節點從連結清單中摘除。
對于有頭結點的連結清單來說，無論删除頭部（首元結點）、中部、尾部的結點，實作方式都一樣，執行以下三步操作：
- 找到目标元素所在結點的直接前驅結點；
- 将目标結點從連結清單中摘下來;
- 手動釋放結點占用的記憶體空間；
從連結清單上摘除目标節點，隻需找到該節點的直接前驅節點 temp，執行如下操作：
temp->next=temp->next->next; 例如，從存有
{1,2,3,4}
的連結清單中删除存儲元素 3 的結點，則此代碼的執行效果如圖 3 所示：
代碼實作
//TODO 删除指定位置的節點
void delLink(Node *list, int loc) {
if(loc<1){//判斷和删除位置是否有誤
printf("删除位置錯誤！！！");
}else{
for (int i = 0; i < loc - 1; ++i) {
list = list->link;//找到删除位置的前一個節點
}
Node *node = list->link;
node = node->link;//删除位置的後一個節點
free(list->link);//釋放删除的節點
list->link = node;//指向新的位址
}
} 完整代碼如下所示
//
// Created by HR on 2022/9/27.
//
#include "stdio.h"
#include "windows.h"
#include "stdlib.h"
typedef char ElemType;
typedef struct node {
ElemType data;
struct Node *link;
} Node;
// TODO 初始化連結清單
Node *creatHead() {
Node *head;
head = (Node *) malloc(sizeof(Node));
head->link = NULL;
return head;
}
// TODO 添加節點,在最後的位置插入
void appendTail(Node *list, ElemType data) {
// Node* head=list;
Node *node = (Node *) malloc(sizeof(Node));
node->data = data;
node->link = NULL;
while (list->link) {
list = list->link;
}
list->link = node;
}
// TODO 列印輸出
void printList(Node *list)//周遊操作
{
list = list->link;//指向頭節點
while (list)//周遊列印
{
printf("%c", list->data);
list = list->link;
}
printf("\n");
}
// TODO 删除指定值的節點
void deleteTail(Node *list, ElemType data)//删除
{
Node *pre = list;
Node *current = list->link;
while (current) {
if (current->data == data) {
pre->link = current->link;
free(current);
break;//退出循環
}
pre = current;
current = current->link;
}
}
// TODO 在指定位置插入指定的值
void insertLink(Node *list, int loc, ElemType data) {
if(loc<1){//判斷插入位置是否有誤
printf("插入位置錯誤！！！");
}else{
Node *node = (Node *) malloc(sizeof(Node));// 需要插入的節點
node->data = data;//修改資料域
for (int i = 0; i < loc - 1; ++i) {
list = list->link;//找到插入位置前一個節點
}
node->link = list->link;//為建立節點的指針域指派
list->link = node;//修改插入節點前一位的指針域位址
}
}
//TODO 删除指定位置的節點
void delLink(Node *list, int loc) {
if(loc<1){//判斷和删除位置是否有誤
printf("删除位置錯誤！！！");
}else{
for (int i = 0; i < loc - 1; ++i) {
list = list->link;//找到删除位置的前一個節點
}
Node *node = list->link;
node = node->link;//删除位置的後一個節點
free(list->link);//釋放删除的節點
list->link = node;//指向新的位址
}
}
// TODO 有序連結清單合并
void MergeList(Node *a, Node *b, Node *c) {
Node *aNext = a->link;
Node *bNext = b->link;
while (aNext && bNext) {
Node *tmp = (Node *) malloc(sizeof(Node));
if (aNext->data > bNext->data) {
tmp->data = bNext->data;
tmp->link = c->link;
c->link = tmp;
bNext = bNext->link;
} else {
tmp->data = aNext->data;
tmp->link = c->link;
c->link = tmp;
aNext = aNext->link;
}
}
while (aNext) {
Node *tmp = (Node *) malloc(sizeof(Node));
tmp->data = aNext->data;
tmp->link = c->link;
c->link = tmp;
aNext = aNext->link;
}
while (bNext) {
Node *tmp = (Node *) malloc(sizeof(Node));
tmp->data = bNext->data;
tmp->link = c->link;
c->link = tmp;
bNext = bNext->link;
}
}
int main() {
Node *head = creatHead();
char arr[] = "asdfghjkl";
for (int i = 0; i < strlen("asdfghjkl"); i++) {
appendTail(head, arr[i]);
}
printList(head);
deleteTail(head, 'b');
printf("連結清單資料展示:");
printList(head);
insertLink(head, 4, 'z');
printf("在第四個位置插入z:");
printList(head);
delLink(head, 4);
printf("删除第四個位置的元素:");
printList(head);
// 合并
Node *a = creatHead();
char arr1[] = "3789";
for (int i = 0; i < strlen("3789"); i++) {
appendTail(a, arr1[i]);
}
Node *b = creatHead();
char arr2[] = "257";
for (int i = 0; i < strlen("257"); i++) {
appendTail(b, arr2[i]);
}
printf("連結清單a的資料:");
printList(a);
printf("連結清單b的資料:");
printList(b);
Node *c = creatHead();
MergeList(a, b, c);
printf("合并後的連結清單資料:");
printList(c);
return 1;
}