鏈表實戰：學生管理系統完整實現 (增刪改查、排序、文件持久化)

系統功能總覽

核心數據結構

typedef struct student {
    long long studentID;   // 學號
    char studentName[10];  // 姓名
    char studentSex[4];    // 性別
    int score[4];          // 四門課成績
} STU;

struct link {
    STU student;
    struct link *next;
};

struct link *head = NULL;   // 原始數據鏈表
struct link *head1 = NULL;  // 排序後鏈表

關鍵算法實現

尾插法建立鏈表 (O(1) 尾指針優化)

void AppendNode(long long id, char *name, char *sex, int *score) {
    struct link *p = malloc(sizeof(struct link));
    if (!p) { printf(\"記憶體分配失敗\\n\"); return; }
    
    p->student.studentID = id;
    strcpy(p->student.studentName, name);
    strcpy(p->student.studentSex, sex);
    memcpy(p->student.score, score, sizeof(int)*4);
    p->next = NULL;
    
    if (!head) {
        head = p;
    } else {
        struct link *pr = head;
        while (pr->next) pr = pr->next;  // 可優化為維護 tail 指針
        pr->next = p;
    }
}

插入排序建立有序鏈表 (避免破壞原鏈表)

// 按總分降序插入
void InsertNode(long long id, char *name, char *sex, int *score) {
    struct link *p = malloc(sizeof(struct link));
    // ... 填充數據 ...
    int sum = score[0]+score[1]+score[2]+score[3];
    
    if (!head1) { head1 = p; return; }
    
    struct link *pr = head1, *temp = NULL;
    int sum1 = pr->student.score[0]+pr->student.score[1]+
               pr->student.score[2]+pr->student.score[3];
    
    while (sum1 > sum && pr->next) {  // 找到插入位置
        temp = pr;
        pr = pr->next;
        sum1 = pr->student.score[0]+pr->student.score[1]+
               pr->student.score[2]+pr->student.score[3];
    }
    
    if (sum1 <= sum) {  // 插在 pr 前面
        if (pr == head1) { p->next = head1; head1 = p; }
        else { pr = temp; p->next = pr->next; pr->next = p; }
    } else {  // 插在最後
        pr->next = p;
    }
}

// 按學號升序插入 (類似邏輯)
void InsertNodeNumber(...) { ... }

單鏈表節點刪除 (統一模式)

void DeleteNodeID() {
    long long id; scanf(\"%lld\", &id);
    struct link *p = head, *pr = head;
    
    while (p && p->student.studentID != id) {
        pr = p; p = p->next;
    }
    
    if (!p) { printf(\"未找到\\n\"); return; }
    
    if (p == head) head = p->next;  // 刪除頭節點
    else pr->next = p->next;        // 刪除中間/尾節點
    
    free(p);
    printf(\"刪除成功\\n\");

文件持久化

保存 (程式退出時調用)

void Save() {
    FILE *fp = fopen(\"demo.txt\", \"w\");
    if (!fp) { printf(\"打開文件失敗\\n\"); return; }
    
    struct link *p = head;
    while (p) {
        fprintf(fp, \"%20lld%10s%5s%4d%4d%4d%4d\",
                p->student.studentID,
                p->student.studentName,
                p->student.studentSex,
                p->student.score[0], p->student.score[1],
                p->student.score[2], p->student.score[3]);
        p = p->next;
    }
    fclose(fp);
}

載入 (程式啟動時調用)

void Open() {
    FILE *fp = fopen(\"demo.txt\", \"r\");
    if (!fp) { printf(\"文件不存在或打開失敗\\n\"); return; }
    
    long long id; char name[10], sex[4]; int score[4];
    while (fscanf(fp, \"%20lld%10s%5s%4d%4d%4d%4d\", 
                  &id, name, sex, &score[0], &score[1], &score[2], &score[3]) == 7) {
        AppendNode(id, name, sex, score);
    }
    fclose(fp);
}

內存管理

void DeleteMemory(struct link *h) {
    struct link *p = h, *pr;
    while (p) {
        pr = p;
        p = p->next;
        free(pr);
    }
}

// 主程式結束時
DeleteMemory(head);
DeleteMemory(head1);

遞歸遍歷顯示

void DisplayNode(struct link *h) {
    if (!h) return;
    printf(\"%lld%10s%5s\", h->student.studentID, 
           h->student.studentName, h->student.studentSex);
    for (int i=0; i<4; i++) printf(\"%4d\", h->student.score[i]);
    printf(\"\\n\");
    DisplayNode(h->next);  // 遞歸 (注意棧深度)
}

主程式流程

int main() {
    Open();  // 啟動載入
    
    while (1) {
        system(\"pause\");
        Menu();  // 顯示選單
        int menu; scanf(\"%d\", &menu);
        
        switch (menu) {
            case 0: exit(0);
            case 1: /* 添加邏輯 */ break;
            case 2: FindID(); break;
            case 3: FindName(); break;
            case 4: DeleteNodeID(); break;
            case 5: DeleteNodeName(); break;
            case 6: NumberSorting(1); break;  // 總分排序
            case 7: NumberSorting(2); break;  // 學號排序
        }
    }
}

改進建議

1. 維護尾指針：AppendNode 從 O(n) 優化為 O(1)
2. 迭代替代遞歸：DisplayNode 改用 while 迴圈，避免棧溢出
3. 輸入驗證：學號唯一性、成績範圍、字串長度檢查
4. 排序算法優化：大數據量改用歸併排序 (O(n log n))
5. 文件格式健壯性：採用結構化格式 (JSON/CSV) 或二進制序列化
6. 模組化重構：拆分為 list.c/h, student.c/h, file.c/h, main.c
7. 單元測試：為每個函數編寫測試用例

鏈表 vs 陣列 選型指南