【數據結構】單鏈表的使用

單鏈表的使用

- 1、基本概念
- 2、鏈表的分類
- 3、鏈表的基本操作
- - a、單鏈表節點設計
  - b、單鏈表初始化
  - c、單鏈表增刪節點
  - - **節點頭插：**
    - **節點尾插：**
    - **新節點插入指定節點后：**
    - 節點刪除：
  - d、單鏈表修改節點
  - e、單鏈表遍歷，并打印數據
- 4、鏈表優缺點
- 5、完整示例代碼

1、基本概念

順序表：順序存儲的線性表。
鏈式表：鏈式存儲的線性表，簡稱鏈表。
既然順序存儲中的數據因為擠在一起而導致需要成片移動，那很容易想到的解決方案是將數據離散地存儲在不同內存塊中，然后在用來指針將它們串起來。這種樸素的思路所形成的鏈式線性表，就是所謂的鏈表。

順序表和鏈表在內存在的基本樣態如下圖所示：

順序表：

在這里插入圖片描述
鏈表：

2、鏈表的分類

$\quad$ 根據鏈表中各個節點之間使用指針的個數，以及首尾節點是否相連，可以將鏈表細分為如下種類：
1.單向鏈表
2.單向循環鏈表
3.雙向循環鏈表
$\quad$ 這些不同鏈表的操作都是差不多的，只是指針數目的異同。以最簡單的單向鏈表為例，其基本示意圖如下所示：
在這里插入圖片描述上圖中，所有的節點均保存一個指針，指向其邏輯上相鄰的下一個節點（末尾節點指向空）。
另外注意到，整條鏈表用一個所謂的頭指針 head 來指向，由 head 開始可以找到鏈表中的任意一個節點。head 通常被稱為頭指針。

3、鏈表的基本操作

節點設計
初始化空鏈表
增刪節點
鏈表遍歷(改查)
銷毀鏈表

下面著重針對這幾項常見操作，講解單向鏈表的處理。

a、單鏈表節點設計

單向鏈表的節點非常簡單，節點中除了要保存用戶數據之外（這里以整型數據為例），只需要增加一個指向本類節點的指針即可，如下所示：

typedef struct single_list{// 數據域--》真實的數據int data;    				// 以整型數據為例// 指針域struct single_list *next; 	// //用來指向下一個元素在內存中的首地址
}single_list_t;

b、單鏈表初始化

$\quad$ 首先，空鏈表有兩種常見的形式。一種是帶頭結點的，一種是不帶頭結點的。所謂的頭結點是不存放有效數據的節點，僅僅用來方便操作，如下：
在這里插入圖片描述
而不帶頭結點的空鏈表如下所示：

$\quad$ 由于頭結點是不存放有效數據的，因此如果空鏈表中帶有頭結點，那么頭指針 head 將永遠不變，這會給以后的鏈表操作帶來些許便捷。
下面以帶頭結點的鏈表為例，展示單向鏈表的初始化的示例代碼：

single_list_t *single_list_init()
{single_list_t *head_node = malloc(sizeof(single_list_t));if (head_node != NULL){head_node->next = NULL;}return head_node;
}

c、單鏈表增刪節點

$\quad$ 相對于順序表需要整片移動數據，鏈表增刪節點只需要修改幾個相關指針的指向，動作非常快速。
$\quad$ 與順序表類似，可以對一條鏈表中的任意節點進行增刪操作，示例代碼：

節點頭插：

int insert_list_head(int newdata, single_list_t *list)
{// 申請一個節點 -堆空間single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化數據域new_node->data = newdata;new_node->next = NULL;// 插入節點new_node->next = list->next;list->next = new_node;return 0;
}

節點尾插：

int insert_list(int newdata, single_list_t *list)
{// 申請一個節點 -堆空間single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化數據域new_node->data = newdata;new_node->next = NULL;// 定義指針p去找到鏈表的尾部single_list_t *p = list;while (p->next != NULL){p = p->next;}// 此時p已經到最后一個節點的位置p->next = new_node;return 0;
}

新節點插入指定節點后：

int insert_list_mid(int olddata, int newdata, single_list_t *list)
{// 找到要插入的節點single_list_t *p = list;while (p->next != NULL){p = p->next;if (p->data == olddata) // 待插入的節點在鏈表中間{break;}}// 申請一個新的節點 single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化數據域new_node->data = newdata;new_node->next = NULL;// p指向最后一個節點if (p->next == NULL){// 最后一個節點是要插入的節點if (p->data == olddata){new_node->next = p->next; // 先讓新增加的節點指向找到節點的下一個節點p->next = new_node;   // 再將該節點指向新增加的節點}else{printf("要插入的數據不存在\n");return -1;}}else // 遍歷到中間找到需要插入的節點{new_node->next = p->next; // 先讓新增加的節點指向找到節點的下一個節點p->next = new_node;   // 再將該節點指向新增加的節點}return 0;
}

節點刪除：

int list_delnode(int deldata, single_list_t *list)
{single_list_t *q = list;single_list_t *p = list->next;while (p->next != NULL){// 找到要刪除的節點并進行刪除if (p->data == deldata){q->next = p->next;  // 將q指向的節點指向被刪除節點的下一個節點p->next = NULL;     // p節點的next指針指向NULLfree(p);    // 釋放p后此時p是野指針p = q->next;// 將p指向被刪除節點的下一個節點}else{p = p->next;q = q->next;}  }// 遍歷到最后一個節點if (p->next == NULL){// 若最后一個節點是要刪除的節點，則刪除if (p->data == deldata){q->next = p->next;p->next = NULL;free(p);}else{printf("最后一個節點不是要刪除的節點\n");return 0;}}
}

d、單鏈表修改節點

int list_update_node(int old_data, int new_data, single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;  // p指向下一個節點if (p->data == old_data){p->data = new_data;}}return 0;
}

e、單鏈表遍歷，并打印數據

int list_show(single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;printf("當前p指向的節點數據:%d\n", p->data);}
}

4、鏈表優缺點

$\quad$ 鏈式存儲中，所有節點的存儲位置是隨機的，他們之間的邏輯關系用指針來確定，跟物理存儲位置無關，因此從上述示例代碼可以很清楚看到，增刪數據都非常迅速，不需要移動任何數據。另外，又由于位置與邏輯關系無關，因此也無法直接訪問某一個指定的節點，只能從頭到尾按遍歷的方式一個個找到想要的節點。簡單講，鏈式存儲的優缺點跟順序存儲幾乎是相對的。
總結其特點如下：

優點
a.插入、刪除時只需要調整幾個指針，無需移動任何數據
b.當數據節點數量較多時，無需一整片較大的連續內存空間，可以靈活利用離散的內存
c.當數據節點數量變化劇烈時，內存的釋放和分配靈活，速度快
缺點
a.在節點中，需要多余的指針來記錄節點之間的關聯
b.所有數據都是隨機存儲的，不支持立即訪問任意一個隨機數據。

5、完整示例代碼

#include <stdio.h>
#include <stdlib.h>// 1.封裝一個結構體來表示單鏈表
typedef struct single_list{int data;struct single_list *next;
}single_list_t;// 2.初始化單鏈表-->定義結構體變量 創建頭節點
single_list_t *single_list_init()
{single_list_t *head_node = malloc(sizeof(single_list_t));if (head_node != NULL){head_node->next = NULL;}return head_node;
}// 頭插
int insert_list_head(int newdata, single_list_t *list)
{// 申請一個節點 -堆空間single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化數據域new_node->data = newdata;new_node->next = NULL;// 插入節點new_node->next = list->next;list->next = new_node;return 0;
}
/*@brief:3.插入數據-->尾插(在最后一個有效成員的后面插入數據)*@param(in):  newdata :待插入的數據  list:待插入的鏈表*@param(out):  *@retval:    
*/
int insert_list(int newdata, single_list_t *list)
{// 申請一個節點 -堆空間single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化數據域new_node->data = newdata;new_node->next = NULL;// 定義指針p去找到鏈表的尾部single_list_t *p = list;while (p->next != NULL){p = p->next;}// 此時p已經到最后一個節點的位置p->next = new_node;return 0;
}// 中間插入
int insert_list_mid(int olddata, int newdata, single_list_t *list)
{// 找到要插入的節點single_list_t *p = list;while (p->next != NULL){p = p->next;if (p->data == olddata){break;}}// 申請一個節點 -堆空間single_list_t *new_node = malloc(sizeof(single_list_t));// 初始化數據域new_node->data = newdata;new_node->next = NULL;// p指向最后一個節點if (p->next == NULL){if (p->data == olddata){new_node->next = p->next; // 先讓新增加的節點指向找到節點的下一個節點p->next = new_node;   // 再將該節點指向新增加的節點}else{printf("要插入的數據不存在\n");return -1;}}else // 遍歷到中間找到需要插入的節點{new_node->next = p->next; // 先讓新增加的節點指向找到節點的下一個節點p->next = new_node;   // 再將該節點指向新增加的節點}return 0;
}
// 刪除節點
int list_delnode(int deldata, single_list_t *list)
{single_list_t *q = list;single_list_t *p = list->next;while (p->next != NULL){// 找到要刪除的節點并進行刪除if (p->data == deldata){q->next = p->next;  // 將q指向的節點指向被刪除節點的下一個節點p->next = NULL;     // p節點的next指針指向NULLfree(p);    // 釋放p后此時p是野指針p = q->next;// 將p指向被刪除節點的下一個節點}else{p = p->next;q = q->next;}  }// 遍歷到最后一個節點if (p->next == NULL){// 若最后一個節點是要刪除的節點，則刪除if (p->data == deldata){q->next = p->next;p->next = NULL;free(p);}else{printf("最后一個節點不是要刪除的節點\n");return 0;}}
}
// 修改節點
int list_update_node(int old_data, int new_data, single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;  // p往后移動if (p->data == old_data){p->data = new_data;}}return 0;
}// 4.遍歷鏈表,打印節點數據
int list_show(single_list_t *list)
{single_list_t *p = list;while (p->next != NULL){p = p->next;printf("當前p指向的節點數據:%d\n", p->data);}
}int main(int argc, char const *argv[])
{// 初始化單鏈表single_list_t *my_list = single_list_init();// 往鏈表插入數據insert_list(15, my_list);insert_list(18, my_list);insert_list(15, my_list);insert_list(25, my_list);insert_list(666, my_list);insert_list(123, my_list);insert_list(11111111, my_list);insert_list_mid(666, 777, my_list);insert_list_mid(1, 222, my_list);insert_list_head(15, my_list);printf("============插入的節點============\n");list_show(my_list);printf("============插入的節點============\n");// 刪除節點list_delnode(25,my_list);printf("============刪除后的節點============\n");list_show(my_list); // 打印數據printf("============刪除后的節點============\n");// 修改數據list_update_node(123, 234, my_list);printf("============修改后的節點============\n");list_show(my_list); // 打印數據printf("============修改后的節點============\n");return 0;
}
/*
執行結果：
要插入的數據不存在
============插入的節點============
當前p指向的節點數據:15
當前p指向的節點數據:15
當前p指向的節點數據:18
當前p指向的節點數據:15
當前p指向的節點數據:25
當前p指向的節點數據:666
當前p指向的節點數據:777
當前p指向的節點數據:123
當前p指向的節點數據:11111111
============插入的節點============
最后一個節點不是要刪除的節點
============刪除后的節點============
當前p指向的節點數據:15
當前p指向的節點數據:15
當前p指向的節點數據:18
當前p指向的節點數據:15
當前p指向的節點數據:666
當前p指向的節點數據:777
當前p指向的節點數據:123
當前p指向的節點數據:11111111
============刪除后的節點============
============修改后的節點============
當前p指向的節點數據:15
當前p指向的節點數據:15
當前p指向的節點數據:18
當前p指向的節點數據:15
當前p指向的節點數據:666
當前p指向的節點數據:777
當前p指向的節點數據:234
當前p指向的節點數據:11111111
============修改后的節點============
*/