前言：大家好😍，本文主要介紹數據結構——單鏈表

目錄

一、單鏈表

二、使用步驟

1.結構體定義

2.初始化

3.插入

3.1 頭插

3.2 尾插?

3.3 按位置插

?四.刪除

4.1頭刪

4.2 尾刪

4.3 按位置刪

4.4按值刪

五 統計有效值個數?

六 銷毀1

銷毀2

七 查找

八 打印

---

一、單鏈表

概念：單鏈表邏輯上相鄰，物理上不一定相鄰的鏈式存儲結構

所以一個結點不僅僅要保存自身的數據，還要保存自己下一個連接結點的地址

所以每一個結點需要倆個域：一個數據域，一個指針域

二、使用步驟

1.結構體定義

typedef int Elem_Type;
struct Node
{Elem_Type data;//數據域 存儲有效數據struct Node* next;//指針域  存下一個有效結點的地址
};typedef struct Node Node;
typedef struct Node* pNode;

struct Node：定義了一個 結構體 Node，它包含兩個成員：
Elem_Type data;： 數據域，用于存儲節點中的數據。由于 Elem_Type 被定義為 int，所以這里的 data 可以存儲一個整數。
struct Node* next;： 指針域，用于存儲指向下一個節點的地址。這樣，每個節點都可以通過 next 指針鏈接到下一個節點，形成鏈表。
typedef struct Node Node;：為結構體 Node 創建了一個別名 Node，這樣在代碼中可以直接 使用 Node 來聲明這種類型的變量。
typedef struct Node* pNode;：定義了一個 pNode 類型，它實際上是 指向 Node 結構體的指針類型。這通常用于表示鏈表的頭指針或遍歷鏈表時的指針變量。

2.初始化

//初始化
void Init_List(struct Node* head)
{assert(head != NULL);if (NULL == head){exit(EXIT_FAILURE);}head->next = nullptr;
}

• 參數 head 是指向 Node 結構體的指針。

• 初始化鏈表：head->next = nullptr; 將 head 節點的 next 指針設置為 nullptr，表示鏈表為空，即沒有其他節點。

3.插入

3.1 頭插

bool Insert_head(struct Node* head, Elem_Type val)
{assert(head != NULL);if (NULL == head){exit(EXIT_FAILURE);}Node* pnewnode=(Node*)malloc(sizeof(Node));if (NULL == pnewnode)exit(1);pnewnode->data = val;pnewnode->next = head->next;head->next = pnewnode;
}

? Node* pnewnode = (Node*)malloc(sizeof(Node));：使用 malloc 函數分配內存以創建一個新的 Node 結構體實例，并將其地址賦給指針 pnewnode

1. pnewnode->data = val;：將傳入的數據 val 存儲在新節點的 data 成員中。

2. pnewnode->next = head->next;：將新節點的 next 指針指向當前頭節點的下一個節點，即鏈表的第二個節點。

3. head->next = pnewnode;：將頭節點的 next 指針指向新節點，這樣新節點就成為了鏈表的第一個節點。

3.2 尾插?

bool Insert_tail(struct Node* head, Elem_Type val)
{assert(head != NULL);if (NULL == head){exit(EXIT_FAILURE);}Node* pnewnode = (Node*)malloc(sizeof(Node));if (NULL == pnewnode)exit(1);pnewnode->data = val;Node* p = head;while (p->next != NULL){p = p->next;}//pnewnode->next = head->next;//head->next = pnewnode;pnewnode->next = p->next;p->next = pnewnode;return true;
} 

3.3 按位置插

bool Insert_pos(struct Node* head, Elem_Type val, int pos)
{assert(head != NULL);assert(pos >= 0 && pos <= Get_Length(head));Node* pnewnode = (Node*)malloc(sizeof(Node));if (NULL == head){exit(1);}pnewnode->data = val;Node* p = head;for (int i = 0; i < pos; i++)p = p->next;//pnewnode->next = head->next;//head->next = pnewnode;pnewnode->next = p->next;p->next = pnewnode;return true;
}

?

?四.刪除

4.1頭刪

bool Del_head(struct Node* head)
{assert(head != NULL);if (Is_Empty(head))return false;Node* p = head->next;head->next = p->next;free(p);p = NULL;return true;
}

4.2 尾刪

bool Del_tail(struct Node* head)
{assert(head != NULL);if (Is_Empty(head))return false;Node* p = head;while (p->next->next != NULL)p = p->next;Node* q = p->next;p->next = q->next;free(p);p = NULL;return true;
}

4.3 按位置刪

//8.按值刪(刪除值val出現的第一次的地方)
bool Del_val(struct Node* head, Elem_Type val)
{//0.assertassert(head != NULL);//0.5 判斷鏈表是否是空鏈表if (Is_Empty(head))return false;//1.調用Search函數，查找當前值val是否存在，用臨時指針q接收Node* q = Search(head, val);if (q == NULL){return false;}//2.申請臨時指針p，讓指針p停留在指針q指向節點的上一個節點Node* p = head;for ( ; p->next != q; p = p->next);//3.跨越指向p->next = q->next;//4.釋放free(q);q = NULL;return true;
}

4.4按值刪

bool Del_val(struct Node* head, Elem_Type val)
{//0.assertassert(head != NULL);//0.5 判斷鏈表是否是空鏈表if (Is_Empty(head))return false;//1.調用Search函數，查找當前值val是否存在，用臨時指針q接收Node* q = Search(head, val);if (q == NULL){return false;}//2.申請臨時指針p，讓指針p停留在指針q指向節點的上一個節點Node* p = head;for ( ; p->next != q; p = p->next);//3.跨越指向p->next = q->next;//4.釋放free(q);q = NULL;return true;
}

五 統計有效值個數?

int Get_Length(struct Node* head)
{int count = 0;for (Node* p = head->next; p != NULL; p = p->next){count++;}return count;
}

六 銷毀1

//11.銷毀1(需要輔助節點參與進來)
void Destroy1(struct Node* head)
{//只要不是空鏈表，則頭刪一次，直到鏈表為空/*while (!Is_Empty(head)){Del_head(head);}*/while (head->next != NULL){Node* q = head->next;head->next = q->next;free(q);q = NULL;}
}

銷毀2

//12.銷毀2(不需要輔助節點參與進來)
void Destroy2(struct Node* head)
{//0.assert  head  //1.申請指針p，讓其保存輔助節點的指針域Node* p = head->next;//p有可能為NULL， 有可能不空//2.申請指針q，先不給q賦值Node* q = NULL; //因為p有可能是NULL，所以不能現在直接把p->next給到q//3.反復通過p和q打配合，去銷毀后續節點while (p != NULL){q = p->next;free(p);p = q;}//4.節點全部銷毀完畢，別忘了把輔助節點的指針域置空head->next = NULL;//這一行代碼可以幫助，下一次啟用的時候，輔助節點不用初始化了}

七 查找

//9.查找(查找值val出現的第一次的地方)
struct Node* Search(struct Node* head, Elem_Type val)
{//0.assertfor (Node* p = head->next; p != NULL; p = p->next){if (p->data == val){return p;}}return NULL;
}

八 打印

//15.打印
void Show(struct Node* head)
{//assertfor (Node* p = head->next; p != NULL; p = p->next){printf("%d ", p->data);}printf("\n");}