C語言單向鏈表查找演算法：建立、遍歷與字串比較完整實作

完整程式碼實作

結構定義

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)  // 字串比較，相等返回 0
            return p;           // 找到，返回節點指標
        else
            p = p->link;        // 移向下一節點
    }
    if (p == NULL)
        printf("沒有查找到該資料!\n");
    return NULL;
}

主程式

#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);

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

    head = creat(number);
    printf("請輸入你要查找的人的姓名: ");
    scanf("%s", fullname);
    searchpoint = search(head, fullname);
    // 後續可根據 searchpoint 進行插入、刪除等操作
}

查找過程記憶體圖解

頭節點 h → [name=""][link] → 節點1 → 節點2 → 節點3 → ... → NULL
                    ↑
                    p (遍歷指標)

搜尋 "Bob"：
p=節點1: strcmp("Alice","Bob")≠0 → p=p->link
p=節點2: strcmp("Bob","Bob")==0 → return 節點2 指標

字串比較關鍵：strcmp()

• #include
• strcmp(s1, s2)：依 ASCII 逐字元比較
• 返回值：< 0（s1 0（s1>s2）
• 不可用 == 比較字串：比較的是指標位址而非內容

查找變體與優化

複雜度分析

• 時間：O(n) — 最壞遍歷全表
• 空間：O(1) — 僅少量指標變數
• 平均比較次數：(n+1)/2

進階：有序鏈表二分查找？

不可直接套用。鏈表不支援隨機存取（無法 O(1) 存取中間元素），二分查找退化為 O(n)。
若需高效查找，考慮：

• 跳表
• 平衡二叉樹（AVL、紅黑樹）
• 雜湊表
• 陣列 + 排序 + 二分查找

常見錯誤與修正

1. 字串比較用 == → if (p->name == x) ✗ → if (strcmp(p->name, x) == 0) ✓
2. 未包含 string.h → strcmp 隱式宣告警告/錯誤
3. 查找失敗未處理：直接使用返回的 NULL 指標 → 段錯誤
4. 頭節點資料域干擾：頭節點 name[0]='\0' 不參與查找，從 h->link 開始
5. scanf 讀取含空格姓名失敗：用 gets/fgets 替代

擴展：刪除操作預覽

// 刪除節點 p（需前驅 prev）
prev->link = p->link;
free(p);

// 查找前驅輔助函數
stud *find_prev(stud *h, char *x) {
    stud *p = h;
    while (p->link != NULL) {
        if (strcmp(p->link->name, x) == 0)
            return p;
        p = p->link;
    }
    return NULL;
}

1. 上一篇文章： C語言單向鏈表插入操作：後插演算法與完整程式碼實作
2. 下一篇文章： C語言動態記憶體分配完全指南：malloc、free 原理與實戰應用

關於C語言

C 語言實現文本統計：行數、單詞數與字符數計算器

問題描述 從標準輸入讀取文本（以 EOF 結束），統計行數（

設計模式 (C#) 實戰：模板方法模式 — 核心概念與實體類定義 (上)

模式意圖：定義算法骨架，將特定步驟延遲到子類。模板方法使子類

Windows C語言網絡編程速成：從Hello World到獲取本機IP

前言：跳過C++，直通Windows系統編程 傳統學習路徑「

Visual C# .NET 入門指南（九）

檢查變數值 當您能控制偵錯工具時，可將滑鼠指標移至變數上以取