C++ 純虛析構函數深度探究與快排、歸並排序實現

前言

本文通過一道 C++ 作業題（D&A 5 Collection with Inheritance），深入探討抽象類析構函數的調用機制、純虛析構函數的必要性，並完整實現基於數組的快速排序與基於雙向鏈表的歸並排序。

核心知識點：純虛析構函數

為什麼抽象類需要純虛析構函數？

抽象類雖不能實例化，但作為基類指針刪除派生類對象時，必須調用派生類析構函數再調用基類析構函數。若基類析構函數非虛，delete basePtr 僅調用基類析構，導致派生類資源洩露。

實驗驗證：四種場景對比

結論：通過基類指針動態分配派生類對象時，必須定義虛析構函數（推薦純虛並提供實現），否則會導致資源洩露。棧上創建對象則不受影響。

純虛析構函數的正確寫法

class Base {
public:
    virtual void funA() = 0;
    virtual ~Base() = 0;  // 純虛聲明
};

// 必須在類外提供實現！
Base::~Base() {
    cout << "Base destructor called" << endl;
}

注意：純虛析構函數 必須提供函數體，否則鏈接階段報錯。接口類通常只提供接口不提供實現，但析構函數例外。

工程實踐：防止頭文件重複包含

使用 #ifndef/#define/#endif 守護宏：

#ifndef LIST_H_
#define LIST_H_
// 類定義...
#endif

排序算法實現詳解

1. 數組快速排序

採用經典雙向掃描分區法，遞歸處理左右子區間。關鍵點：選取基準值、雙指針向中間收縮、交換元素、遞歸終止條件。

void quick_sort(int *arr, int left, int right) {
    if (left >= right) return;
    int pivot = left, i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= arr[pivot]) --j;
        while (i < j && arr[i] <= arr[pivot]) ++i;
        swap(arr[i], arr[j]);
    }
    swap(arr[pivot], arr[i]);
    quick_sort(arr, left, i - 1);
    quick_sort(arr, i + 1, right);
}

2. 雙向鏈表歸並排序

歸並排序天然適合鏈表：分割只需找中點斷開，合併只需調整指針，無需額外空間搬移數據。步驟：

1. 分割：快慢指針找中點，斷開前後兩部分鏈表
2. 遞歸排序：分別對左右部分調用 merge_sort
3. 合併：雙指針比較節點值，串聯成新有序鏈表
4. 清理：釋放臨時節點，更新 head/tail

void merge_sort(Node** head, int size) {
    if (!*head || !(*head)->next) return;
    
    // 1. 找中點分割
    Node *slow = *head, *fast = *head;
    while (fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    Node *mid = slow->next;
    slow->next = nullptr;
    if (mid) mid->prev = nullptr;
    
    // 2. 遞歸排序
    merge_sort(head, size/2);
    merge_sort(&mid, size - size/2);
    
    // 3. 合併
    Node dummy(0);
    Node *tail = &dummy;
    Node *p1 = *head, *p2 = mid;
    while (p1 && p2) {
        if (p1->data <= p2->data) {
            tail->next = p1;
            p1->prev = tail;
            p1 = p1->next;
        } else {
            tail->next = p2;
            p2->prev = tail;
            p2 = p2->next;
        }
        tail = tail->next;
    }
    tail->next = p1 ? p1 : p2;
    if (tail->next) tail->next->prev = tail;
    
    // 4. 更新頭尾
    *head = dummy.next;
    if (*head) (*head)->prev = nullptr;
    while (tail->next) tail = tail->next;
}

完整項目結構

項目包含：Collection.hpp（抽象基類）、List.hpp（鏈表接口）、ArrayList（動態數組實現快排）、LinkedList（雙向鏈表實現歸並）、main.cpp（測試驅動）。禁止使用 STL 容器與算法，純手工實現數據結構與排序。

補充：C++ 多態機制

動態多態通過 虛函數表 實現：含虛函數的類生成 vtable，對象持有 vptr 指向 vtable。運行時通過 vptr 查表調用最具體實現。dynamic_cast 依賴 RTTI 安全向下轉型；static_cast 編譯期綁定無開銷。經驗法則：類中有虛函數則析構函數應為虛；構造函數不能為虛。