一，鏈表描述
鏈表是一種常見的重要的數據結構,是動態地進行存儲分配的一種結構。常用于需存儲的數據的數目無法事先確定。
1.鏈表的一般結構
鏈表的組成：
頭指針：存放一個地址，該地址指向一個元素
結點：用戶需要的實際數據和鏈接節點的指針
2.結點結構體類型的定義
鏈表結點結構的 一般形式：
struct 結構體名{ 數據成員表；struct 結構體名 *指針變量名；}；
3.結點的動態分配
形式是：malloc(存儲區字節數)
該函數返回存儲區的首地址。
釋放存儲區用如下函數：?free(p)； 它表示釋放由p指向的存儲空間。
用結構體建立鏈表：
struct student｛ int num；float score；struct student *next ；};
其中成員num和score用來存放結點中的有用數據（用戶需要用到的數據），next是指針類型的成員，它指向struct student類型數據（這就是next所在的結構體類型）
二，鏈表的設計與實現
1.單向鏈表
1.1 單向鏈表的組成：
? ? ? ? 1）頭指針
2）結點
數據域 ? (保存實際數據)
指針域 ? (保存下一個結點地址)
1.2 ?單向鏈表的設計實現：
1）定義結點類型
typedef int data_t;
typedef strcut node
{data_t data;strcut node *next;
}node_t;
2）單向鏈表功能算法實現
? ? ? (1)?鏈表創建
int slist_create(node_t**,data_t);
(2)? 數據添加
(2.1) ?頭插
int slist_addhead(node_t**,data_t)
(2.2) ?尾插
int slist_addtail(node_t**,data_t)
(2.3) ?中間插入
int slist_insert(node_t**,data_t pos,data_t new);
(3) ?數據刪除
int ?slist_delete(node_t**,data_t);
(4) ?數據查詢
node_t* slist_query(node_t*,data_t);?
(5) ?數據更新
int ?slist_update(node_t*,data_t old,data_t new);
(6) ?數據遍歷
void slist_showall(node_t*);
(7) ?鏈表回收
void slist_destroy(node_t**);
1.3 單向鏈表示例程序
該示例程序涉及到鏈表創建、數據添加（頭插、尾插、中間插入）、數據刪除、數據查詢、數據更新、數據遍歷、鏈表回收。
slist.c
#include <stdio.h>
#include <stdlib.h>typedef int data_t;typedef struct node
{data_t data;struct node *next;
} node_t;/* 1. 鏈表創建（創建一個空頭指針，返回成功與否） */
int slist_create(node_t **head, data_t value)
{*head = (node_t *)malloc(sizeof(node_t));if (*head == NULL){perror("malloc");return -1;}(*head)->data = value;(*head)->next = NULL;return 0;
}/*頭插法 */
int slist_addhead(node_t **head, data_t value)
{node_t *new = (node_t *)malloc(sizeof(node_t));if (!new){perror("malloc");return -1;}new->data = value;new->next = *head;*head = new;return 0;
}/*尾插法 */
int slist_addtail(node_t **head, data_t value)
{node_t *new = (node_t *)malloc(sizeof(node_t));if (!new){perror("malloc");return -1;}new->data = value;new->next = NULL;if (*head == NULL){*head = new;}else{node_t *p = *head;while (p->next != NULL)p = p->next;p->next = new;}return 0;
}/*中間插入：在指定數據 pos 后插入 new */
int slist_insert(node_t **head, data_t pos, data_t newval)
{node_t *p = *head;while (p && p->data != pos){p = p->next;}if (!p){printf("未找到插入位置 %d\n", pos);return -1;}node_t *new = (node_t *)malloc(sizeof(node_t));if (!new){perror("malloc");return -1;}new->data = newval;new->next = p->next;p->next = new;return 0;
}/* 3. 刪除結點（按值刪除） */
int slist_delete(node_t **head, data_t value)
{node_t *p = *head, *q = NULL;while (p && p->data != value){q = p;p = p->next;}if (!p){printf("未找到要刪除的值 %d\n", value);return -1;}if (q == NULL)*head = p->next; // 刪除頭結點elseq->next = p->next;free(p);return 0;
}/* 4. 查詢（返回結點指針） */
node_t *slist_query(node_t *head, data_t value)
{while (head){if (head->data == value)return head;head = head->next;}return NULL;
}/* 5. 更新 */
int slist_update(node_t *head, data_t old, data_t newval)
{node_t *p = slist_query(head, old);if (!p){printf("未找到需要更新的值 %d\n", old);return -1;}p->data = newval;return 0;
}/* 6. 遍歷 */
void slist_showall(node_t *head)
{printf("鏈表內容: ");while (head){printf("%d -> ", head->data);head = head->next;}printf("NULL\n");
}/* 7. 鏈表回收 */
void slist_destroy(node_t **head)
{node_t *p = *head;while (p){node_t *tmp = p;p = p->next;free(tmp);}*head = NULL;
}/* ============= 測試主函數 ============= */
int main(void)
{node_t *head = NULL;/* 創建鏈表 */slist_create(&head, 10);slist_addhead(&head, 5);slist_addtail(&head, 20);slist_addtail(&head, 30);slist_insert(&head, 20, 25); // 在20后插入25slist_showall(head);/* 刪除 */slist_delete(&head, 10);slist_showall(head);/* 查詢并更新 */node_t *res = slist_query(head, 25);if (res)printf("找到結點: %d\n", res->data);slist_update(head, 25, 99);slist_showall(head);/* 回收 */slist_destroy(&head);slist_showall(head);return 0;
}
運行結果：
1.4 鏈表數據結構的小結
?? ? ? ??應用場景：?
1）鏈式結構是一種動態增加數據的結構，如果存儲的數據數量事先無法確定，使用鏈表是比較合適的;
2）常用于對數據進行頻繁的增加或者刪除的情況
?? ??? ? 缺點：
查詢效率比較低，主要原因是鏈表數據必須從頭結點開始遍歷。
2. 雙向鏈表設計實現
說明：雙向鏈表是在單向鏈表的基礎上，指針域增加了存儲上一個結點地址的指針變量(前驅指針)
優勢：由于雙向鏈表具有后繼指針，也有前驅指針，所以對數據的增加，刪除更加方便快捷，原因是鏈表結點的插入和刪除，往往會影響上一個結點，相比于單向鏈表需要查找上一個結點，雙向鏈表就可以通過結點的前驅指針直接獲取。
2.1雙向鏈表的組成
? ? ? ?1) ? 頭指針
2) ? 結點：
數據域 ? (保存實際數據)
指針域 ? (保存下一個結點地址) ?
(保存上一個結點地址)?
2.2 ?雙向鏈表的設計實現：
1) ?定義結點類型：? ? ? ? ??
?typedef int data_t;typedef strcut node{data_t ?data;strcut ?node ? *prev;strcut ?node ? *next;}node_t;?? ??? ? ? ?2) ?雙向鏈表功能算法實現：
（1) ?鏈表創建
int dlist_create(node_t**,data_t);
(2)?數據添加
(2.1) ?頭插
int dlist_addhead(node_t**,data_t)
(2.2) ?尾插
int dlist_addtail(node_t**,data_t)
(2.3) ?中間插入
int dlist_insert(node_t** head,data_t pos,data_t new);
(3) ?數據刪除
int ?dlist_delete(node_t**,data_t);
(4) ?數據查詢
node_t* dlist_query(node_t*,data_t);?
(5) ?數據更新
int ?dlist_update(node_t*,data_t old,data_t new);
(6) ?數據遍歷
void dlist_showall(node_t*);
(7) ?鏈表回收
void dlist_destroy(node_t**);
2.3 示例程序：
dlist.c
#include <stdio.h>
#include <stdlib.h>typedef int data_t;// 定義雙向鏈表結點
typedef struct node {data_t data;struct node *prev;struct node *next;
} node_t;/*鏈表創建 */
int dlist_create(node_t **head, data_t value) {*head = (node_t *)malloc(sizeof(node_t));if (*head == NULL) return -1;(*head)->data = value;(*head)->prev = NULL;(*head)->next = NULL;return 0;
}/*頭插 */
int dlist_addhead(node_t **head, data_t value) {node_t *newnode = (node_t *)malloc(sizeof(node_t));if (newnode == NULL) return -1;newnode->data = value;newnode->prev = NULL;newnode->next = *head;if (*head != NULL) {(*head)->prev = newnode;}*head = newnode;return 0;
}/*尾插 */
int dlist_addtail(node_t **head, data_t value) {node_t *newnode = (node_t *)malloc(sizeof(node_t));if (newnode == NULL) return -1;newnode->data = value;newnode->next = NULL;if (*head == NULL) {newnode->prev = NULL;*head = newnode;return 0;}node_t *p = *head;while (p->next != NULL) {p = p->next;}p->next = newnode;newnode->prev = p;return 0;
}/*中間插入（在pos位置前插入新節點） */
int dlist_insert(node_t **head, data_t pos, data_t value) {node_t *p = *head;while (p != NULL && p->data != pos) {p = p->next;}if (p == NULL) return -1;node_t *newnode = (node_t *)malloc(sizeof(node_t));if (newnode == NULL) return -1;newnode->data = value;newnode->next = p;newnode->prev = p->prev;if (p->prev != NULL) {p->prev->next = newnode;} else {*head = newnode; // 插在頭部}p->prev = newnode;return 0;
}/*刪除節點（刪除值為value的第一個節點） */
int dlist_delete(node_t **head, data_t value) {node_t *p = *head;while (p != NULL && p->data != value) {p = p->next;}if (p == NULL) return -1;if (p->prev != NULL) {p->prev->next = p->next;} else {*head = p->next; // 刪除頭節點}if (p->next != NULL) {p->next->prev = p->prev;}free(p);return 0;
}/*數據查詢 */
node_t* dlist_query(node_t *head, data_t value) {node_t *p = head;while (p != NULL) {if (p->data == value) {return p;}p = p->next;}return NULL;
}/*數據更新 */
int dlist_update(node_t *head, data_t old, data_t new) {node_t *p = head;while (p != NULL) {if (p->data == old) {p->data = new;return 0;}p = p->next;}return -1;
}/*遍歷（正向） */
void dlist_showall(node_t *head) {node_t *p = head;printf("DList: ");while (p != NULL) {printf("%d ", p->data);p = p->next;}printf("\n");
}/*鏈表回收 */
void dlist_destroy(node_t **head) {node_t *p = *head;while (p != NULL) {node_t *tmp = p;p = p->next;free(tmp);}*head = NULL;
}/* 測試主函數 */
int main() {node_t *head = NULL;// 創建鏈表dlist_create(&head, 10);dlist_addhead(&head, 5);dlist_addtail(&head, 20);dlist_addtail(&head, 30);dlist_insert(&head, 20, 15); // 在20前插入15dlist_showall(head);// 查詢node_t *q = dlist_query(head, 15);if (q) printf("Found: %d\n", q->data);// 更新dlist_update(head, 15, 18);dlist_showall(head);// 刪除dlist_delete(&head, 10);dlist_showall(head);// 回收dlist_destroy(&head);return 0;
}
運行結果：
鏈表小結：
1. 定義
單向鏈表（Singly Linked List）
每個節點只有一個指針next，指向下一個節點。
結構簡單，內存開銷小，但只能 單方向遍歷。雙向鏈表（Doubly Linked List）
每個節點有兩個指針：prev（前驅）和next（后繼）。
可以 雙向遍歷，刪除/插入更方便，但每個節點占用內存更大。
2. 節點結構
單向鏈表
typedef int data_t;
typedef struct node {data_t data;struct node *next;
} node_t;
雙向鏈表
typedef int data_t;
typedef struct node {data_t data;struct node *prev;struct node *next;
} node_t;
3. 基本功能函數
| 功能 | 單向鏈表 (slist) | 雙向鏈表 (dlist) |
|---|---|---|
| 創建鏈表 | slist_create() | dlist_create() |
| 頭插入 | slist_addhead() | dlist_addhead() |
| 尾插入 | slist_addtail() | dlist_addtail() |
| 中間插入 | slist_insert() | dlist_insert() |
| 刪除節點 | slist_delete() | dlist_delete() |
| 查詢節點 | slist_query() | dlist_query() |
| 更新節點 | slist_update() | dlist_update() |
| 遍歷輸出 | slist_showall() (等同于 print) | dlist_showall() (等同于 print) |
| 銷毀鏈表 | slist_destroy() | dlist_destroy() |
4. 主要區別
| 對比點 | 單向鏈表 | 雙向鏈表 |
|---|---|---|
| 內存占用 | 小，每個節點只需 next 指針 | 大，每個節點需 prev + next |
| 遍歷方向 | 只能從頭到尾 | 可從頭到尾，也能從尾到頭 |
| 插入效率 | 需要找到插入點的前驅節點 | 直接利用 prev / next 修改指針，效率更高 |
| 刪除效率 | 需要找到刪除節點的前驅節點 | 直接用 prev / next 修改即可 |
| 實現復雜度 | 簡單 | 稍復雜 |
| 適用場景 | 內存緊張、簡單隊列/棧結構 | 頻繁插入/刪除、需要雙向遍歷 |
5. 輸出函數
單向鏈表輸出
void slist_showall(node_t* head) {node_t* p = head;while (p) {printf("%4d\n", p->data); // 每行一個，右對齊p = p->next;}
}
雙向鏈表輸出
void dlist_showall(node_t* head) {node_t* p = head;while (p) {printf("%4d\n", p->data);p = p->next;}
}
總結：
單向鏈表：結構簡單，適合空間敏感、邏輯簡單的場景（如棧、隊列）。
雙向鏈表：操作靈活，適合需要頻繁插入/刪除和雙向遍歷的場景（如 LRU 緩存、雙端隊列）。
（DAY 002）)
