C語言單向鏈表插入操作：後插演算法與完整程式碼實作

單向鏈表插入原理：後插法

已知連續兩節點 p（前驅）、q（後繼），在兩者間插入新節點 s：

1. 配置 s 記憶體並賦值
2. s->link = q（或 p->link）
3. p->link = s

順序關鍵：先連 s->link，再改 p->link，否則會丟失 q 位址。

完整程式碼實作

結構定義

typedef struct node {
    char name[20];
    struct node *link;
} stud;

建立鏈表 creat()

stud *creat(int n) {
    stud *p, *h, *s;
    int i;
    if ((h = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("記憶體配置失敗!");
        exit(0);
    }
    h->name[0] = '\0';
    h->link = NULL;
    p = h;
    for (i = 0; i < n; i++) {
        if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
            printf("記憶體配置失敗!");
            exit(0);
        }
        p->link = s;
        printf("請輸入第%d個人的姓名: ", i+1);
        scanf("%s", s->name);
        s->link = NULL;
        p = s;
    }
    return h;
}

查找節點 search()

stud *search(stud *h, char *x) {
    stud *p;
    char *y;
    p = h->link;
    while (p != NULL) {
        y = p->name;
        if (strcmp(y, x) == 0)
            return p;
        else
            p = p->link;
    }
    if (p == NULL)
        printf("沒有查找到該資料!\n");
    return NULL;
}

後插函數 insert()

void insert(stud *p) {
    char stuname[20];
    stud *s;
    if ((s = (stud *)malloc(sizeof(stud))) == NULL) {
        printf("記憶體配置失敗!");
        exit(0);
    }
    printf("請輸入你要插入的人的姓名: ");
    scanf("%s", stuname);
    strcpy(s->name, stuname);  // 複製姓名到新節點

    s->link = p->link;  // 1. 新節點指向原後繼
    p->link = s;        // 2. 前驅指向新節點
}

主程式

#include 
#include 
#include 

#define N 10

typedef struct node {
    char name[20];
    struct node *link;
} stud;

stud *creat(int n);
stud *search(stud *h, char *x);
void insert(stud *p);

main() {
    int number = N;
    char fullname[20];
    stud *head, *searchpoint;

    head = creat(number);
    printf("請輸入你要查找的人的姓名: ");
    scanf("%s", fullname);
    searchpoint = search(head, fullname);
    if (searchpoint)
        insert(searchpoint);
}

插入操作記憶體圖解

// 插入前：p → q
p → [name="Alice"][link=q]
q → [name="Bob"][link=...]

// 步驟 1：s->link = p->link (即 q)
s → [name="New"][link=q]

// 步驟 2：p->link = s
p → [name="Alice"][link=s]
s → [name="New"][link=q]

// 結果：p → s → q

關鍵技術點

1. malloc 檢查：每次配置必判斷 NULL
2. strcpy 複製字串：s->name 為陣列，不可直接指派指標，需 strcpy
3. 指標重連順序：先建立新連結（s->link），再斷舊連結（p->link）
4. 查找返回節點指標：search 返回 stud*，insert 直接操作該節點
5. 頭節點不存資料：h->name[0]='\0'，資料從 h->link 開始

插入位置變體

常見錯誤

1. 順序顛倒：p->link = s; s->link = p->link; → 丟失原後繼
2. 未複製字串：s->name = stuname; → 指向區域變數，函數返回失效
3. 忘記設 s->link = NULL（尾插時）
4. 查找失敗未檢查：insert(NULL) 導致崩潰

複雜度分析

• 查找：O(n)
• 插入操作本身：O(1)
• 總計：O(n)（以查找為主）

若頻繁插入，考慮雙向鏈表、跳表或平衡樹優化查找。

1. 上一篇文章： C語言雙向鏈表實作：建立、查找與列印完整程式碼解析
2. 下一篇文章： C語言單向鏈表查找演算法：建立、遍歷與字串比較完整實作

關於C語言

ASP.NET 2.0 自訂複合控件開發（進階篇）：客戶端排序、隱藏欄位同步與 ListMover 完整實作

EnhancedListBox 客戶端功能強化 1. 註冊

C# 開發 WPF/Silverlight 動畫與遊戲系列教程（十六）完美移動系統最終章（三）—— A* 關鍵幀動畫改造與最終測試

A* 移動方法改造 private void AStarMo

基於 libpcap 與 libnet 實現 ARP 欺騙與局域網 IP 劫持完整指南

本文詳細記錄如何在 Linux 環境下結合 libpcap（

Objective-C Runtime 核心技術總結：動態方法替換、消息轉發與屬性遍歷

Objective-C Runtime 核心技術總結：動態方