（C語言）單鏈表（1.0）（單鏈表教程）（數據結構，指針）

目錄

1. 什么是單鏈表？

2. 單鏈表的代碼表示

3. 單鏈表的基本操作

3.1 初始化鏈表

3.2 插入結點（頭插法）

3.3 插入結點（尾插法）

3.4 遍歷鏈表

4. 單鏈表的優缺點

代碼：*L=(LinkList)malloc(sizeof(LNode))

1.?malloc?的作用

2.?sizeof(LNode)?的作用

3.?類型轉換?(LinkList)

4.?*L?的含義

5.?整體流程

6.?實際效果

7.?常見問題解答

Q1：為什么用?malloc?而不是直接聲明變量？

Q2：頭結點的?data?字段有意義嗎？

Q3：為什么要用二級指針?LinkList* L？

8.?圖解過程

DestoryLinkList?函數原理詳解

1. 函數參數?LinkList* L（二級指針）

2.?while (*L != NULL)?循環

3. 銷毀過程圖解

循環步驟：

4. 最終效果

5. 為什么需要這樣實現？

6. 對比?ClearLinkList（清空鏈表）

7. 常見問題

Q1：為什么用?while (*L)?而不是?while ((*L)->next)？

Q2：如果鏈表為空（只有頭結點），會發生什么？

Q3：為什么不用遞歸實現？

8. 代碼驗證

總結

1. 函數參數

2. 創建頭結點

3. 頭插法循環（for (i = n; i > 0; i--)）

步驟拆解：

插入過程圖示：

4. 輸入順序與鏈表順序的關系

6. 關鍵代碼解析

7. 內存管理注意事項

8. 示例輸入輸出

輸入：

鏈表結構：

9. 常見問題

Q1：為什么頭插法會導致順序相反？

Q2：如果?n?為負數會發生什么？

Q3：頭插法的時間復雜度是多少？

總結

ShowLinkList?函數原理詳解（顯示單鏈表內容）

1. 函數參數?const LinkList* L

2. 初始化指針?p

3. 檢查鏈表是否為空

4. 遍歷鏈表并打印數據

5. 示例輸出

6. 遍歷過程圖解

7. 為什么用?while (p)?而不是?while (p->next)？

8. 時間復雜度

9. 安全性注意事項

總結

1. 函數參數

2. 創建頭結點

3. 尾指針?p?的初始化

4. 尾插法循環（for (i = n; i > 0; i--)）

步驟拆解：

插入過程圖示：

5. 輸入順序與鏈表順序的關系

7. 關鍵代碼解析

8. 內存管理注意事項

9. 示例輸入輸出

輸入：

鏈表結構：

10. 常見問題

Q1：為什么需要尾指針?p？

Q2：如果?p?不更新會怎樣？

Q3：尾插法的時間復雜度是多少？

總結

#include <stdio.h>
#include <stdlib.h>//函數結果狀態代碼
#define OK 1
#define ERROR 0typedef int Status;//函數返回狀態，ok，error
typedef int Elemtype;//鏈表元素為整形
typedef struct Lnode//定義結構體
{Elemtype data;//數據域struct Lnode* next;//指針域
}Lnode,*LinkList;//單個結點，整個鏈表（指向結點的指針）//初始化鏈表（建立一個頭結點）
Status InitLinkList(LinkList* L){*L=(LinkList)malloc(sizeof(Lnode));//分配頭結點內存if(*L==NULL){return ERROR;//判斷是否分配成功}(*L)->next=NULL;//頭結點的指針域為空return OK;
}//判斷鏈表是否為空
Status IsEmptyLinkList(const LinkList* L){if((*L)->next==NULL){return ERROR;}else{return OK;}
}//銷毀鏈表
Status DestoryLinkList(LinkList* L){LinkList p;//定義一個臨時的指向結點的指針while (*L!=NULL){p=*L;//儲存原來的指針（結點）*L=(*L)->next;//往后移動結點free(p);//釋放原來的指針}return OK;
}//鏈表的插入，頭插法
Status CreateLinkList_h(LinkList* L,int n){InitLinkList(L);//創建頭結點for(int i=0;i<n;i++){LinkList newlnode;//創建一個新結點newlnode=(Lnode*)malloc(sizeof(Lnode));//為新節點分配內存if(newlnode==NULL){return ERROR;//判斷是否分配成功}printf("請輸入數據：\n");scanf("%d",&newlnode->data);newlnode->next=(*L)->next;//使新結點指向原指針(*L)->next=newlnode;//使頭指針指向新結點}return OK;
}//鏈表的插入，尾插入
Status CreateLinkList_r(LinkList* L,int n){InitLinkList(L);//創建頭結點LinkList p=*L;//定義臨時尾結點for(int i=0;i<n;i++){LinkList newlnode;newlnode=(Lnode*)malloc(sizeof(Lnode));//給新結點分配內存if(newlnode==NULL){return ERROR;//判斷是否分配成功}printf("請輸入數據：\n");scanf("%d",&newlnode->data);newlnode->next=NULL;//使新結點指向空p->next=newlnode;//使原結點指向新結點p=p->next;//后移一次，定義新的尾結點}return OK;
}//查看鏈表
Status ShowLinkList(const LinkList* L){Lnode* p=(*L)->next;//定義個臨時結點if(p==NULL){printf("鏈表為空！\n");return OK;}int i=1;while (p!=NULL){printf("%d : %d\n", i, p->data);  // 打印序號和數據i++;            // 序號遞增p = p->next;    // p 移動到下一個結點}return OK;
}//查看第i個元素
Status LocatElem(const LinkList* L,int i){int j=i;//賦值給ji=1;//初始化iLinkList p=(*L)->next;//創建臨時結點表示第一個結點if(p==NULL){printf("鏈表為空！\n");//判斷鏈表是否為空return OK;}//逐步后移，直到i和j相等while (i!=j){i++;p=p->next;}printf("第%d個 : %d\n", j, p->data);  // 打印第i個序號，和數據return OK;
}//主函數
int main(){LinkList mylist;mylist=NULL;//CreateLinkList_h(&mylist,3);//頭插CreateLinkList_r(&mylist,3);//尾插ShowLinkList(&mylist);LocatElem(&mylist,2);
}

下面來解釋相關知識點和部分代碼：

單鏈表是數據結構中最基礎的一種鏈式存儲結構，非常適合新手學習指針和動態內存管理的概念。下面我會用最易懂的方式講解單鏈表的核心知識。

1. 什么是單鏈表？

單鏈表就像一列火車：

  • 每節車廂（結點）包含兩部分：貨物（數據）和連接鉤（指針）

  • 車頭（頭結點）不裝貨物，只負責帶領整列火車

  • 最后一節車廂的連接鉤是空的（NULL）

2. 單鏈表的代碼表示

typedef struct Node {int data;           // 數據域（可以是任意類型）struct Node* next;  // 指針域（指向下一個結點）
} Node, *LinkedList;    // Node表示單個結點，LinkedList表示整個鏈表

3. 單鏈表的基本操作

3.1 初始化鏈表

LinkedList initList() {LinkedList L = (LinkedList)malloc(sizeof(Node)); // 創建頭結點L->next = NULL;     // 初始為空鏈表return L;
}

3.2 插入結點（頭插法）

void headInsert(LinkedList L, int data) {Node* newNode = (Node*)malloc(sizeof(Node)); // 創建新結點newNode->data = data;newNode->next = L->next;  // 新結點指向原第一個結點L->next = newNode;        // 頭結點指向新結點
}

特點：新結點總是插在最前面，鏈表順序與插入順序相反

3.3 插入結點（尾插法）

void tailInsert(LinkedList L, int data) {Node* p = L;while(p->next != NULL) {  // 找到最后一個結點p = p->next;}Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;p->next = newNode;  // 最后一個結點指向新結點
}

特點：新結點總是插在最后面，鏈表順序與插入順序相同

3.4 遍歷鏈表

void printList(LinkedList L) {Node* p = L->next;  // 跳過頭結點while(p != NULL) {printf("%d ", p->data);p = p->next;    // 移動到下一個結點}printf("\n");
}

4. 單鏈表的優缺點

優點：

  • 插入/刪除速度快（O(1)時間復雜度）

  • 不需要預先知道數據規模

  • 不需要連續的內存空間

缺點：

  • 查找速度慢（O(n)時間復雜度）

  • 需要額外的空間存儲指針

下面來解釋代碼，更加了解單鏈表：

代碼：*L=(LinkList)malloc(sizeof(LNode))

這行代碼是單鏈表初始化中的核心操作，涉及指針、動態內存分配和類型轉換。讓我們用新手能理解的方式逐步拆解：

1.?malloc?的作用

malloc?是內存分配函數（memory allocation），它的作用是從堆（Heap）內存中申請一塊指定大小的內存空間。

  • 比喻：就像在倉庫里預訂一個儲物柜，告訴管理員你需要多大的空間。

  • 語法：void* malloc(size_t size);

    • 參數?size：需要申請的字節數

    • 返回值：成功時返回指向分配內存的指針，失敗返回?NULL

2.?sizeof(LNode)?的作用

sizeof?是一個運算符，用來計算數據類型或變量占用的字節數。

  • sizeof(LNode)：計算結構體?LNode?的大小。

    • 假設?LNode?包含一個?int（4字節）和一個指針（8字節，64位系統），則?sizeof(LNode) = 12?字節。

    • 意義：告訴?malloc?要申請一個足夠存放?LNode?的內存塊。

3.?類型轉換?(LinkList)

malloc?返回的是?void*（通用指針），需要強制轉換為?LinkList?類型。

  • LinkList?是什么？
    根據代碼中的定義：

    typedef struct Signle_Link_List LNode, *LinkList;

    • LNode?是結構體類型（結點）

    • LinkList?是?LNode*?的別名（指向結點的指針）

  • 轉換目的：明確告訴編譯器，這塊內存將被當作?LinkList（即指向?LNode?的指針）使用。

4.?*L?的含義

函數的參數是?LinkList* L（二級指針）：

  • LinkList* L?可以理解為：指向頭指針的指針。

  • *L?解引用后得到的是頭指針（LinkList?類型）。

  • 操作目的：通過?*L = ...?修改外部的頭指針，使其指向新分配的內存。

5.?整體流程

這行代碼的完整意義是：

  1. 申請內存：在堆內存中申請一塊大小為?sizeof(LNode)?的內存。

  2. 類型轉換：將返回的?void*?轉換為?LinkList?類型（即?LNode*）。

  3. 賦值給頭指針：讓外部的頭指針?*L?指向這塊內存。

6.?實際效果

這行代碼執行后：

  • 創建了一個頭結點：頭結點的?data?字段未初始化（可能是垃圾值），但?next?指針會被初始化為?NULL（見后續代碼?(*L)->next = NULL;）。

  • 鏈表結構：

    *L（頭指針）│▼
[頭結點] → next = NULL

7.?常見問題解答

Q1：為什么用?malloc?而不是直接聲明變量？

  • 答：鏈表結點需要動態增減，malloc?允許在運行時按需申請內存。

  • 對比：

    LNode node;        // 棧內存，函數結束后自動釋放
LNode* p = malloc(...); // 堆內存，需要手動釋放（用 free）
Q2：頭結點的?data?字段有意義嗎？

  • 答：在標準實現中，頭結點的?data?通常不存儲有效數據（僅作為鏈表入口），但代碼中可能用它存儲元信息（如長度）。

Q3：為什么要用二級指針?LinkList* L？

  • 答：需要修改外部傳入的頭指針的值。C語言中，若想通過函數修改指針的值，必須傳遞指針的地址（即二級指針）。

  • 示例：

    void Init(LinkList* L) {*L = malloc(...); // 修改外部的頭指針
}
int main() {LinkList myList;  // 此時 myList 是野指針Init(&myList);    // 傳遞頭指針的地址
}

8.?圖解過程

Before malloc:
+------+
|  L  | --> 隨機值（野指針）
+------+After malloc:
+------+       +---------------------+
|  L  | -->   | data（未初始化）     |
+------+       | next = NULL         |+---------------------+

DestoryLinkList?函數原理詳解

這個函數的作用是?銷毀整個單鏈表，包括?頭結點?和所有?數據結點，并釋放它們占用的內存。讓我們一步步解析它的工作原理：

1. 函數參數?LinkList* L（二級指針）

  • LinkList?是?LNode*?的別名（指向結點的指針）。

  • LinkList* L?是一個?指向頭指針的指針（二級指針），目的是?修改外部的頭指針，使其最終變為?NULL。

    • 如果只傳?LinkList L（一級指針），函數內部修改?L?不會影響外部的頭指針，導致內存泄漏。

2.?while (*L != NULL)?循環

  • 循環條件：只要?*L（當前頭指針）不為?NULL，就繼續釋放內存。

  • 循環過程：

    1. p = *L：臨時指針?p?保存當前要釋放的結點（頭結點或數據結點）。

    2. *L = (*L)->next：讓頭指針?*L?指向下一個結點（相當于鏈表“跳過”當前結點）。

    3. free(p)：釋放?p?指向的結點內存。

3. 銷毀過程圖解

假設鏈表結構如下：

頭指針 *L│▼
[頭結點] → [結點1] → [結點2] → NULL
循環步驟：

  1. 第一次循環：

    • p = *L（p?指向頭結點）

    • *L = (*L)->next（頭指針?*L?指向結點1）

    • free(p)（釋放頭結點）

    *L → [結點1] → [結點2] → NULL

  2. 第二次循環：

    • p = *L（p?指向結點1）

    • *L = (*L)->next（頭指針?*L?指向結點2）

    • free(p)（釋放結點1）

    *L → [結點2] → NULL

  3. 第三次循環：

    • p = *L（p?指向結點2）

    • *L = (*L)->next（頭指針?*L?指向?NULL）

    • free(p)（釋放結點2）

    *L → NULL

  4. 循環結束：

    • *L?為?NULL，退出循環。

4. 最終效果

  • 鏈表被完全銷毀：所有結點（包括頭結點）的內存被釋放。

  • 頭指針?*L?被置為?NULL：防止外部代碼誤用已釋放的內存（避免野指針）。

5. 為什么需要這樣實現？

  • 防止內存泄漏：必須逐個釋放所有結點，否則未釋放的內存會一直占用堆空間。

  • 安全性：將頭指針置為?NULL，避免后續代碼誤操作已釋放的內存。

6. 對比?ClearLinkList（清空鏈表）

ClearLinkList?只釋放數據結點，保留頭結點（鏈表可復用）：

Status ClearLinkList(LinkList* L) {LNode* p, *q;q = (*L)->next;  // q 指向第一個數據結點while (q != NULL) {p = q;q = q->next;free(p);}(*L)->next = NULL;  // 頭結點的 next 置空return OK;
}

  • 區別：

    • DestoryLinkList：銷毀整個鏈表（頭結點+數據結點）。

    • ClearLinkList：只清空數據結點，保留頭結點。

7. 常見問題

Q1：為什么用?while (*L)?而不是?while ((*L)->next)？

  • 答：*L?是當前頭指針，需要釋放所有結點（包括頭結點）。如果檢查?(*L)->next，會漏掉頭結點。

Q2：如果鏈表為空（只有頭結點），會發生什么？

  • 答：*L?指向頭結點，第一次循環釋放頭結點后，*L?被置為?NULL，循環結束。

Q3：為什么不用遞歸實現？

  • 答：遞歸實現可能因鏈表過長導致棧溢出。迭代（循環）更安全高效。

8. 代碼驗證

可以通過打印結點地址驗證釋放過程：

Status DestoryLinkList(LinkList* L) {LNode* p;while (*L != NULL) {p = *L;printf("Freeing node at address: %p\n", p);  // 打印釋放的結點地址*L = (*L)->next;free(p);}return OK;
}

總結

  • 核心操作：循環遍歷鏈表，逐個釋放結點，并更新頭指針。

  • 關鍵點：二級指針修改頭指針、free?釋放內存、防止野指針。

  • 適用場景：當確定鏈表不再使用時調用，避免內存泄漏。

這個函數的作用是?用頭插法創建一個包含?n?個結點的單鏈表。特點是?新結點總是插入在頭結點之后，因此鏈表的順序與輸入順序?相反。下面逐步解析其工作原理：

1. 函數參數

  • LinkList* L：二級指針，用于修改外部的頭指針。

  • int n：要創建的結點數量。

2. 創建頭結點

*L = (LinkList)malloc(sizeof(LNode));  // 分配頭結點內存
(*L)->next = NULL;                     // 頭結點的 next 初始化為 NULL

  • 作用：初始化一個空鏈表，只有頭結點（不存儲實際數據）。

  • 圖示：

    *L（頭指針）│▼
[頭結點] → NULL

3. 頭插法循環（for (i = n; i > 0; i--)）

循環?n?次，每次創建一個新結點并插入到?頭結點之后。

步驟拆解：

  1. 申請新結點內存：

    LNode* newlnode = (LNode*)malloc(sizeof(LNode));

    • 為新結點分配內存，并通過?scanf?輸入數據。

  2. 插入新結點：

    newlnode->next = (*L)->next;  // 新結點的 next 指向原第一個結點
(*L)->next = newlnode;        // 頭結點的 next 指向新結點

    • 關鍵點：新結點插入后成為鏈表的?第一個數據結點。

插入過程圖示：

  • 初始狀態（只有頭結點）：

    [頭結點] → NULL

  • 插入第一個結點（值為 1）：

    [頭結點] → [1] → NULL

  • 插入第二個結點（值為 2）：

    [頭結點] → [2] → [1] → NULL

  • 插入第三個結點（值為 3）：

    [頭結點] → [3] → [2] → [1] → NULL

4. 輸入順序與鏈表順序的關系

  • 輸入順序：假設依次輸入?1, 2, 3。

  • 鏈表順序：3 → 2 → 1（與輸入相反）。

  • 原因：每次新結點都插入在鏈表頭部。

頭插法尾插法
新結點插入頭結點之后新結點追加到鏈表末尾
鏈表順序與輸入順序相反鏈表順序與輸入順序相同
無需維護尾指針需要維護尾指針?tail
時間復雜度：O(n)（每次插入為 O(1)）時間復雜度：O(n)

6. 關鍵代碼解析

newlnode->next = (*L)->next;  // 新結點的 next 指向原第一個結點
(*L)->next = newlnode;        // 頭結點的 next 指向新結點

  • 類比：像排隊時每次都讓新來的人站到隊伍最前面。

  • 操作順序：必須先設置?newlnode->next，再修改?(*L)->next，否則會丟失原鏈表的引用。

7. 內存管理注意事項

  • 每個?malloc?分配的內存必須在鏈表銷毀時通過?free?釋放（如調用?DestoryLinkList）。

  • 如果輸入?n?為 0，函數會創建一個只有頭結點的空鏈表。

8. 示例輸入輸出

輸入：
CreateLinkList_H(&myList, 3);
// 依次輸入：10, 20, 30
鏈表結構：
頭結點 → [30] → [20] → [10] → NULL

9. 常見問題

Q1：為什么頭插法會導致順序相反？

  • 答：每次新結點都插入在鏈表頭部，類似“后來居上”。

Q2：如果?n?為負數會發生什么？

  • 答：循環不會執行，鏈表只有頭結點（需在函數開頭添加參數檢查）。

Q3：頭插法的時間復雜度是多少？

  • 答：O(n)，因為每個結點的插入操作是 O(1)，共?n?次。

總結

  • 核心思想：通過每次在頭部插入新結點構建鏈表。

  • 特點：簡單高效，但順序與輸入相反。

  • 適用場景：不需要保持輸入順序，或需要頻繁在頭部插入的場景（如棧的實現）。

ShowLinkList?函數原理詳解（顯示單鏈表內容）

這個函數的作用是?遍歷并打印單鏈表中的所有數據結點，同時顯示每個結點的序號。如果鏈表為空，會提示用戶。以下是逐步解析：

1. 函數參數?const LinkList* L

  • const?修飾符：表示不會修改鏈表內容（安全保護）。

  • LinkList* L：二級指針，用于訪問頭結點（但這里只讀不修改）。

2. 初始化指針?p
LNode* p = (*L)->next;  // p 指向第一個數據結點（跳過頭結點）

  • 為什么從?(*L)->next?開始？
    頭結點（*L）不存儲實際數據，它的?next?才指向第一個有效結點。

3. 檢查鏈表是否為空
if (!p) {  // 等價于 if (p == NULL)puts("The LinkList is empty");return;
}

  • 邏輯：如果?p?為?NULL，說明頭結點的?next?為空，鏈表無數據結點。

4. 遍歷鏈表并打印數據
int i = 1;          // 結點序號從1開始
while (p != NULL) {  // 遍歷直到鏈表末尾printf("%d : %d\n", i, p->data);  // 打印序號和數據i++;            // 序號遞增p = p->next;    // p 移動到下一個結點
}

  • 關鍵點：

    • p->data：當前結點的數據。

    • p = p->next：指針后移，實現遍歷。

5. 示例輸出

假設鏈表結構：

頭結點 → [10] → [20] → [30] → NULL

調用?ShowLinkList(&list)?輸出：

1 : 10
2 : 20
3 : 30

如果鏈表為空，輸出：

The LinkList is empty
6. 遍歷過程圖解
初始狀態：
p = 頭結點->next → [10] → [20] → [30] → NULL第一次循環：
打印 1:10，p 移動到 [20]第二次循環：
打印 2:20，p 移動到 [30]第三次循環：
打印 3:30，p 移動到 NULL（循環結束）
7. 為什么用?while (p)?而不是?while (p->next)？

  • while (p)：確保當前結點?p?有效時才打印數據（包括最后一個結點）。

  • 如果寫成?while (p->next)，會漏掉最后一個結點的數據！

8. 時間復雜度

  • O(n)：需要遍歷所有?n?個數據結點，每個結點訪問一次。

9. 安全性注意事項

  1. const?保護：防止函數內意外修改鏈表。

  2. 空指針檢查：避免訪問?NULL->next（已通過?if (!p)?處理）。

總結

  • 功能：按順序顯示鏈表所有結點的數據和序號。

  • 關鍵操作：指針遍歷 (p = p->next)、空鏈表檢查。

  • 適用場景：調試、查看鏈表內容、交互式程序輸出。

這個函數的作用是?用尾插法創建一個包含?n?個結點的單鏈表。特點是?新結點總是插入在鏈表末尾，因此鏈表的順序與輸入順序?一致。下面逐步解析其工作原理：

1. 函數參數

  • LinkList* L：二級指針，用于修改外部的頭指針。

  • int n：要創建的結點數量。

2. 創建頭結點

*L = (LinkList)malloc(sizeof(LNode));  // 分配頭結點內存
(*L)->next = NULL;                     // 頭結點的 next 初始化為 NULL

  • 作用：初始化一個空鏈表，只有頭結點（不存儲實際數據）。

  • 圖示：

    *L（頭指針）│▼
[頭結點] → NULL

3. 尾指針?p?的初始化

LNode* p = *L;  // p 初始指向頭結點

  • p?的作用：始終指向當前鏈表的?最后一個結點（尾結點）。

  • 初始時：鏈表只有頭結點，所以?p?指向頭結點。

4. 尾插法循環（for (i = n; i > 0; i--)）

循環?n?次，每次創建一個新結點并插入到?鏈表末尾。

步驟拆解：

  1. 申請新結點內存：

    LNode* newlnode = (LNode*)malloc(sizeof(LNode));

    • 為新結點分配內存，并通過?scanf?輸入數據。

  2. 初始化新結點：

    newlnode->next = NULL;  // 新結點的 next 置空（因為它將是新的尾結點）

  3. 插入新結點到末尾：

    p->next = newlnode;  // 原尾結點的 next 指向新結點
p = newlnode;        // p 移動到新結點（更新尾指針）

    • 關鍵點：通過?p?直接找到鏈表末尾，實現 O(1) 時間復雜度的插入。

插入過程圖示：

  • 初始狀態（只有頭結點）：

    [頭結點] → NULL
p → [頭結點]

  • 插入第一個結點（值為 1）：

    [頭結點] → [1] → NULL
p → [1]

  • 插入第二個結點（值為 2）：

    [頭結點] → [1] → [2] → NULL
p → [2]

  • 插入第三個結點（值為 3）：

    [頭結點] → [1] → [2] → [3] → NULL
p → [3]

5. 輸入順序與鏈表順序的關系

  • 輸入順序：假設依次輸入?1, 2, 3。

  • 鏈表順序：1 → 2 → 3（與輸入一致）。

  • 原因：每次新結點都追加到鏈表尾部。

尾插法頭插法
新結點插入鏈表末尾新結點插入頭結點之后
鏈表順序與輸入順序相同鏈表順序與輸入順序相反
需要維護尾指針?p無需維護尾指針
時間復雜度：O(n)時間復雜度：O(n)

7. 關鍵代碼解析

p->next = newlnode;  // 將新結點鏈接到末尾
p = newlnode;        // 更新尾指針

  • 類比：像排隊時每次都讓新來的人站到隊伍最后面。

  • 必要性：必須更新?p，否則下次插入無法找到新的末尾。

8. 內存管理注意事項

  • 每個?malloc?分配的內存必須在鏈表銷毀時通過?free?釋放（如調用?DestoryLinkList）。

  • 如果輸入?n?為 0，函數會創建一個只有頭結點的空鏈表。

9. 示例輸入輸出

輸入：
CreateLinkList_R(&myList, 3);
// 依次輸入：10, 20, 30
鏈表結構：
頭結點 → [10] → [20] → [30] → NULL

10. 常見問題

Q1：為什么需要尾指針?p？

  • 答：直接通過頭指針找到鏈表末尾需要 O(n) 時間，而維護?p?可以在 O(1) 時間內訪問末尾。

Q2：如果?p?不更新會怎樣？

  • 答：所有新結點都會插入到原尾結點之后，但原尾結點不會更新，導致鏈表斷裂。

Q3：尾插法的時間復雜度是多少？

  • 答：O(n)，因為每個結點的插入操作是 O(1)，共?n?次。

總結

  • 核心思想：通過維護尾指針，每次在鏈表末尾插入新結點。

  • 特點：保持輸入順序，適合需要順序一致的場景。

  • 關鍵操作：尾指針更新 (p = newlnode)、內存分配與釋放。

運行結果如下：

請輸入數據：
90
請輸入數據：
60
請輸入數據：
45
1 : 90
2 : 60
3 : 45
第2個 : 60請按任意鍵繼續. . .

注：該代碼是本人自己所寫，可能不夠好，不夠簡便，歡迎大家指出我的不足之處。如果遇見看不懂的地方，可以在評論區打出來，進行討論，或者聯系我。上述內容全是我自己理解的，如果你有別的想法，或者認為我的理解不對，歡迎指出！！！如果可以，可以點一個免費的贊支持一下嗎？謝謝各位彥祖亦菲！！！！！?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/web/74757.shtml
繁體地址，請注明出處：http://hk.pswp.cn/web/74757.shtml
英文地址，請注明出處：http://en.pswp.cn/web/74757.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Sentinel-自定義資源實現流控和異常處理

Sentinel-自定義資源實現流控和異常處理

目錄 使用SphU的API實現自定義資源 BlockException 使用SentinelResource注解定義資源 SentinelResourceAspect 使用Sentinel實現限流降級等效果通常需要先把需要保護的資源定義好&#xff0c;之后再基于定義好的資源為其配置限流降級等規則。 Sentinel對于主流框架&#…
閱讀更多...
Linux信號處理解析：從入門到實戰

Linux信號處理解析：從入門到實戰

Linux信號處理全解析&#xff1a;從入門到實戰 一、初識Linux信號&#xff1a;系統級的"緊急電話" 信號是什么&#xff1f; 信號是Linux系統中進程間通信的"緊急通知"&#xff0c;如同現實中的交通信號燈。當用戶按下CtrlC&#xff08;產生SIGINT信號&…
閱讀更多...
Java的Selenium的特殊元素操作與定位之select下拉框

Java的Selenium的特殊元素操作與定位之select下拉框

如果頁面元素是一個下拉框&#xff0c;我們可以將此web元素封裝為Select對象 Select selectnew Select(WebElement element); Select對象常用api select.getOptions();//獲取所有選項select.selectBylndex(index);//根據索引選中對應的元素select.selectByValue(value);//選…
閱讀更多...
藍橋云客 刷題統計

藍橋云客 刷題統計

刷題統計 問題描述 小明決定從下周一開始努力刷題準備藍橋杯競賽。他計劃周一至周五每天做 a 道題目&#xff0c;周六和周日每天做 b 道題目。請你幫小明計算&#xff0c;按照計劃他將在第幾天實現做題數大于等于 n 題&#xff1f; 輸入格式 輸入一行包含三個整數 a, b 和 …
閱讀更多...
三防筆記本有什么用 | 三防筆記本有什么特別

三防筆記本有什么用 | 三防筆記本有什么特別

在現代社會&#xff0c;隨著科技的不斷進步&#xff0c;筆記本電腦已經成為人們工作和生活的重要工具。然而&#xff0c;在一些特殊的工作環境和極端條件下&#xff0c;普通筆記本電腦往往難以滿足需求。這時&#xff0c;三防筆記本以其獨特的設計和卓越的性能&#xff0c;成為…
閱讀更多...
智能體和RPA都需要程序思維，如何使用影刀的變量？

智能體和RPA都需要程序思維，如何使用影刀的變量？

歡迎來到濤濤聊AI&#xff0c; 不管AI還是RPA&#xff0c;都需要用到編程思想才能完成批量工作。今天研究了下影刀的變量。 變量類型 根據變量值選擇相應的類型&#xff0c;可選擇任意一種影刀所支持的數據類型 變量值 指定變量中保存的值&#xff0c;會根據不同的類型設置…
閱讀更多...
【藍橋杯】算法筆記3

【藍橋杯】算法筆記3

1. 最長上升子序列（LIS） 1.1. 題目 想象你有一排數字，比如：3, 1, 2, 1, 8, 5, 6 你要從中挑出一些數字，這些數字要滿足兩個條件： 你挑的數字的順序要和原來序列中的順序一致（不能打亂順序） 你挑的數字要一個比一個大（嚴格遞增） 問：最多能挑出多少個這樣的數字？ …
閱讀更多...
性能測試之jmeter的基本使用

性能測試之jmeter的基本使用

簡介 Jmeter是Apache的開源項目&#xff0c;基于Java開發&#xff0c;主要用于進行壓力測試。 優點&#xff1a;開源免費、支持多協議、輕量級、功能強大 官網&#xff1a;https://jmeter.apache.org/index.html 安裝 安裝步驟&#xff1a; 下載&#xff1a;進入jmeter的…
閱讀更多...
【NLP 面經 7、常見transformer面試題】

【NLP 面經 7、常見transformer面試題】

目錄 1. 為何使用多頭注意力機制&#xff1f; 2. Q和K使用不同權重矩陣的原因 3. 選擇點乘而非加法的原因 4. Attention進行scaled的原因 5. 對padding做mask操作 6. 多頭注意力降維原因 7. Transformer Encoder模塊簡介 8. 乘以embedding size的開方的意義 9. 位置編碼 10. 其…
閱讀更多...
【深度學習】CNN簡述

【深度學習】CNN簡述

文章目錄 一、卷積神經網絡&#xff08;CNN&#xff09;二、CNN結構特性1. CNN 典型結構2. 局部連接3. 權重共享4.空間或時間上的次采樣 三、理解層面 一、卷積神經網絡&#xff08;CNN&#xff09; 卷積神經網絡(Convolutional Neural Network&#xff0c;CNN)是一種用于處理…
閱讀更多...
理解OSPF 特殊區域NSSA和各類LSA特點

理解OSPF 特殊區域NSSA和各類LSA特點

本文基于上文 理解OSPF Stub區域和各類LSA特點 在理解了Stub區域之后&#xff0c;我們再來理解一下NSSA區域&#xff0c;NSSA區域用于需要引入少量外部路由&#xff0c;同時又需要保持Stub區域特性的情況 一、 網絡總拓撲圖 我們在R1上配置黑洞路由&#xff0c;來模擬NSSA區域…
閱讀更多...
論文閱讀筆記：Denoising Diffusion Implicit Models （5）

論文閱讀筆記：Denoising Diffusion Implicit Models （5）

0、快速訪問 論文閱讀筆記&#xff1a;Denoising Diffusion Implicit Models &#xff08;1&#xff09; 論文閱讀筆記&#xff1a;Denoising Diffusion Implicit Models &#xff08;2&#xff09; 論文閱讀筆記&#xff1a;Denoising Diffusion Implicit Models &#xff08…
閱讀更多...
藍橋杯2024年第十五屆省賽真題-R 格式

藍橋杯2024年第十五屆省賽真題-R 格式

題目鏈接&#xff1a; 思路&#xff1a; 通過數組模擬d的每一位&#xff0c;逐位進行計算&#xff0c;從而實現對d的精確處理。 代碼&#xff1a; #include<bits/stdc.h> #define int long long using namespace std; const int N 2020;int n; string s; vector<i…
閱讀更多...
深入探索 Linux Top 命令：15 個實用示例

深入探索 Linux Top 命令：15 個實用示例

在 Linux 系統管理中&#xff0c;top 命令是系統性能監控不可或缺的工具。它能夠實時顯示系統的 CPU、內存、進程等資源的使用情況&#xff0c;幫助您快速識別性能瓶頸和異常進程。本文將詳細介紹 15 個實用的 top 命令使用示例&#xff0c;旨在幫助您更高效地進行系統管理與優…
閱讀更多...
15.1linux設備樹下的platform驅動編寫(知識)_csdn

15.1linux設備樹下的platform驅動編寫(知識)_csdn

上一章我們詳細的講解了 Linux 下的驅動分離與分層&#xff0c;以及總線、設備和驅動這樣的驅動框架。基于總線、設備和驅動這樣的驅動框架&#xff0c; Linux 內核提出來 platform 這個虛擬總線&#xff0c;相應的也有 platform 設備和 platform 驅動。 上一章我們講解了傳統的…
閱讀更多...
Eclipse 視圖(View)

Eclipse 視圖(View)

Eclipse 視圖(View) Eclipse 視圖（View）是 Eclipse 界面的重要組成部分，它提供了用戶交互的平臺，使得用戶可以通過圖形界面來編輯、調試、分析代碼等。在本文中，我們將深入探討 Eclipse 視圖的功能、使用方法以及它們在軟件開發中的作用。 1. 視圖的功能 Eclipse 視圖具…
閱讀更多...
Python解決“數字插入”問題

Python解決“數字插入”問題

Python解決“數字插入”問題 問題描述測試樣例解題思路代碼 問題描述 小U手中有兩個數字 a 和 b。第一個數字是一個任意的正整數&#xff0c;而第二個數字是一個非負整數。她的任務是將第二個數字 b 插入到第一個數字 a 的某個位置&#xff0c;以形成一個最大的可能數字。 你…
閱讀更多...
ubuntu部署ollama+deepseek+open-webui

ubuntu部署ollama+deepseek+open-webui

ubuntu部署ollamadeepseekopen-webui 全文-ubuntu部署ollamadeepseekopen-webui 大綱 Ollama部署 安裝Ollama&#xff1a;使用命令apt install curl和curl -fsSL https://ollama.com/install.sh | sh ollama-v網絡訪問配置&#xff1a;設置環境變量OLLAMA_HOST0.0.0.0:11434&…
閱讀更多...
Java的Selenium常用的元素操作API

Java的Selenium常用的元素操作API

click 觸發當前元素的點擊事件 clear() 清空內容 sendKeys(...) 往文本框一類元素中寫入內容 getTagName() 獲取元素的的標簽名 getAttribute(屬性名) 根據屬性名獲取元素屬性值 getText() 獲取當前元素的文本值 isDisplayed() 查看元素是否顯示 get(String url) 訪…
閱讀更多...
洛谷題單3-P1035 [NOIP 2002 普及組] 級數求和-python-流程圖重構

洛谷題單3-P1035 [NOIP 2002 普及組] 級數求和-python-流程圖重構

題目描述 已知&#xff1a; S n 1 1 2 1 3 … 1 n S_n 1\dfrac{1}{2}\dfrac{1}{3}…\dfrac{1}{n} Sn?121?31?…n1?。顯然對于任意一個整數 k k k&#xff0c;當 n n n 足夠大的時候&#xff0c; S n > k S_n>k Sn?>k。 現給出一個整數 k k k&#xff0…
閱讀更多...
最新文章

Copyright @ 2022~2023