C++ 單鏈表學生管理系統：排序功能實現（冒泡/歸併）

現有結構

struct Student {
    int number;
    char name[20], sex[6], old[20], place[6], ment[20], clas[10];
    Student *next;
};

class School {
    Student *head; // 帶頭結點
    // ... 增刪改查方法
};

排序需求

按學號 (number) 升序排列單鏈表。

方案一：冒泡排序（交換數據域，簡單但效率低）

void School::sortByNumberBubble() {
    if (!head || !head->next || !head->next->next) return; // 0或1個節點
    bool swapped;
    Student *p, *q, *last = nullptr;
    do {
        swapped = false;
        p = head;
        while (p->next != last && p->next->next != last) {
            q = p->next;
            if (q->number > q->next->number) {
                // 交換數據域（除 next 指針外所有字段）
                Student tmp = *q;
                q->number = q->next->number;
                strcpy(q->name, q->next->name);
                strcpy(q->sex, q->next->sex);
                strcpy(q->old, q->next->old);
                strcpy(q->place, q->next->place);
                strcpy(q->ment, q->next->ment);
                strcpy(q->clas, q->next->clas);
                // 注意：不交換 next 指針！
                q->next->number = tmp.number;
                strcpy(q->next->name, tmp.name);
                strcpy(q->next->sex, tmp.sex);
                strcpy(q->next->old, tmp.old);
                strcpy(q->next->place, tmp.place);
                strcpy(q->next->ment, tmp.ment);
                strcpy(q->next->clas, tmp.clas);
                swapped = true;
            }
            p = p->next;
        }
        last = p->next;
    } while (swapped);
}

方案二：歸併排序（調整指針，O(n log n)，推薦）

// 切分鏈表
Student* split(Student* head) {
    Student *slow = head, *fast = head->next;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Student* mid = slow->next;
    slow->next = nullptr;
    return mid;
}

// 合併兩個有序鏈表
Student* merge(Student* a, Student* b) {
    Student dummy;
    Student* tail = &dummy;
    while (a && b) {
        if (a->number <= b->number) {
            tail->next = a; a = a->next;
        } else {
            tail->next = b; b = b->next;
        }
        tail = tail->next;
    }
    tail->next = a ? a : b;
    return dummy.next;
}

// 遞歸歸併排序
Student* mergeSort(Student* head) {
    if (!head || !head->next) return head;
    Student* mid = split(head);
    Student* left = mergeSort(head);
    Student* right = mergeSort(mid);
    return merge(left, right);
}

// 類方法調用
void School::sortByNumberMerge() {
    head->next = mergeSort(head->next);
}

整合到主菜單

case '8': pp.sortByNumberMerge(); pp.show(); break; // 新增排序選項

參考資源

• 單鏈表歸併排序詳解：CPPBlog
• C++ 鏈表排序總結：CNBlogs

建議

教學/小數據量用冒泡（交換數據域）易理解；實際項目/大數據量必用歸併排序（調整指針），避免大量字符串拷貝開銷。