C 語言實作有序單向鏈表插入：完整修正版與常見錯誤解析

原始碼問題盤點

1. scanf("%d", s->data) 缺少 & 取址符，導致寫入錯誤位址。
2. 插入邏輯未處理「插入頭節點」與「插入尾節點」的邊界情況。
3. 變數 q 未宣告即使用，應為 p。
4. 函式回傳型別為 LinkList 卻回傳 0，語意不符。
5. 建立鏈表時頭節點資料域未初始化，遍歷列印會輸出垃圾值。

修正後完整程式碼

#include <stdio.h>
#include <stdlib.h>

typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

/* 尾插法建立有序鏈表（輸入已排序） */
LinkList CreateListR() {
    LinkList head = (LinkList)malloc(sizeof(LNode));
    head->next = NULL;
    LinkList tail = head;
    int n, val;
    printf("輸入節點數: ");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        printf("輸入第 %d 個值: ", i+1);
        scanf("%d", &val);
        LinkList node = (LinkList)malloc(sizeof(LNode));
        node->data = val;
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    return head; // 返回頭節點
}

/* 有序插入：維持遞增序 */
LinkList ListInsert(LinkList head, int val) {
    LinkList prev = head;
    LinkList curr = head->next;
    // 尋找插入位置：prev->data <= val < curr->data
    while (curr && curr->data < val) {
        prev = curr;
        curr = curr->next;
    }
    LinkList node = (LinkList)malloc(sizeof(LNode));
    node->data = val;
    node->next = curr;
    prev->next = node;
    return head;
}

void PrintList(LinkList head) {
    LinkList p = head->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

void FreeList(LinkList head) {
    LinkList p = head;
    while (p) {
        LinkList tmp = p;
        p = p->next;
        free(tmp);
    }
}

int main() {
    LinkList list = CreateListR();
    printf("原鏈表: ");
    PrintList(list);
    int x;
    printf("輸入欲插入值: ");
    scanf("%d", &x);
    ListInsert(list, x);
    printf("插入後: ");
    PrintList(list);
    FreeList(list);
    return 0;
}

關鍵修正說明

進階建議

• 輸入驗證：檢查 malloc 回傳值、scanf 回傳值。
• 遞減序只需將比較條件改為 curr->data > val。
• 大量資料建議改用雙向鏈表或跳表，降低插入複雜度至 O(log n)。