資料結構入門-C語言實作環狀串列教學

前導

環狀鏈結串列是一種特殊的鏈結串列，其最後一個節點的指標指向第一個節點，而非 NULL，形成一個循環結構。如下圖所示:

一、環狀鏈結串列的插入（Insertion）

1. 空串列時的插入
2. 頭部插入（Head insertion）
3. 尾部插入（Tail insertion）
4. 中間插入（After a given node）

1. 插入至空的環狀鏈結串列

1. 創建新節點 newNode
2. 設定 newNode->next = newNode 形成環狀
3. head = newNode，tail = newNode

2. 在頭部插入節點

1. 創建新節點 newNode
2. newNode->next = head（新節點指向當前頭部）
3. tail->next = newNode（尾部節點指向新頭部）
4. 更新 head = newNode

👉 效果：新節點變成 head，但環狀結構保持不變。

3. 在指定節點後插入

1. 找到目標節點 X
2. newNode->next = X->next
3. X->next = newNode

👉 效果：新節點插入 X 之後，環狀結構保持。

4. 在尾部插入節點

1. 創建新節點 newNode
2. tail->next = newNode（當前尾部指向新節點）
3. newNode->next = head（新節點指向 head）
4. 更新 tail = newNode
5. 讀者可以自行思考並繪圖。

👉 效果：新節點變成 tail，環狀結構保持。

二、環狀鏈結串列的刪除（Deletion）

刪除節點時，可能發生在：

1. 刪除頭部節點
2. 刪除中間節點
3. 刪除尾部節點
4. 刪除最後一個節點（使串列變空）

1. 刪除頭部節點

1. head = head->next（更新 head 指向下一個節點）
2. tail->next = head（尾部保持指向新的 head）

👉 效果：原head 被移除，環狀結構保持。

2. 刪除中間節點

1. 找到 X 的前一個節點 prev
2. prev->next = X->next

👉 效果：節點 X 被移除，環狀結構保持。

3. 刪除尾部節點

1. 找到 tail 的前一個節點 prev
2. prev->next = head
3. 更新 tail = prev
4. 讀者可以自行思考並繪圖。

👉 效果：新 tail 成為 prev，環狀結構保持。

C語言實作

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

// 定義節點結構
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 創建新節點
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = newNode;  // 初始指向自己
    return newNode;
}

// 插入到空的環狀鏈結串列
void insertEmpty(Node** head, int data) {
    if (*head != NULL) return;
    *head = createNode(data);
}

// 在頭部插入節點
void insertHead(Node** head, int data) {
    if (*head == NULL) {
        insertEmpty(head, data);
        return;
    }
    Node* newNode = createNode(data);
    newNode->next = *head;

    // 找到 tail
    Node* temp = *head;
    while (temp->next != *head) temp = temp->next;
    temp->next = newNode;
    *head = newNode; // 更新 head
}

// 在尾部插入節點
void insertTail(Node** head, int data) {
    if (*head == NULL) {
        insertEmpty(head, data);
        return;
    }
    Node* newNode = createNode(data);
    Node* temp = *head;

    while (temp->next != *head) temp = temp->next;

    temp->next = newNode;
    newNode->next = *head;
}

// 在指定節點後插入
void insertAfter(Node* prevNode, int data) {
    if (prevNode == NULL) return;

    Node* newNode = createNode(data);
    newNode->next = prevNode->next;
    prevNode->next = newNode;
}

// 刪除頭部節點
void deleteHead(Node** head) {
    if (*head == NULL) return;

    // 只有一個節點
    if ((*head)->next == *head) {
        free(*head);
        *head = NULL;
        return;
    }

    Node* temp = *head;
    while (temp->next != *head) temp = temp->next;

    Node* toDelete = *head;
    *head = (*head)->next;
    temp->next = *head;
    free(toDelete);
}

// 刪除尾部節點
void deleteTail(Node** head) {
    if (*head == NULL) return;

    // 只有一個節點
    if ((*head)->next == *head) {
        free(*head);
        *head = NULL;
        return;
    }

    Node* temp = *head;
    Node* prev = NULL;

    // 找到尾部與前一個節點
    while (temp->next != *head) {
        prev = temp;
        temp = temp->next;
    }

    prev->next = *head; // 讓前一個節點變成新的尾部
    free(temp);
}

// 刪除指定值的節點
void deleteNode(Node** head, int key) {
    if (*head == NULL) return;

    Node *curr = *head, *prev = NULL;
    while (curr->data != key) {
        if (curr->next == *head) return; // 沒找到
        prev = curr;
        curr = curr->next;
    }

    if (curr == *head) { // 如果刪除的是頭部
        deleteHead(head);
        return;
    }

    prev->next = curr->next;
    free(curr);
}

// 列印環狀鏈結串列
void printList(Node* head) {
    if (head == NULL) {
        printf("什麼都沒有啦~哥!!");
        return;
    }
    Node* temp = head;
    do {
        printf("%d -> ", temp->data);
        temp = temp->next;
    } while (temp != head);
    printf("(head)\n");
}

// 主程式
int main() {
    Node* head = NULL;

    insertHead(&head, 10);
    insertHead(&head, 20);
    insertTail(&head, 30);
    insertTail(&head, 40);
    printList(head); // 20 -> 10 -> 30 -> 40 -> (head)

    deleteHead(&head);
    printList(head); // 10 -> 30 -> 40 -> (head)

    deleteTail(&head);
    printList(head); // 10 -> 30 -> (head)

    insertAfter(head, 25); // 在 10 之後插入 25
    printList(head); // 10 -> 25 -> 30 -> (head)

    deleteNode(&head, 25);
    printList(head); // 10 -> 30 -> (head)
    
    deleteHead(&head); // 30 -> (head)
    printList(head);
    
    //deleteHead(&head); // 什麼都沒有啦~哥!!
    //deleteTail(&head); // 什麼都沒有啦~哥!!
    deleteNode(&head, 30); // 什麼都沒有啦~哥!!
    printList(head);

    return 0;
}

輸出:

20 -> 10 -> 30 -> 40 -> (head)
10 -> 30 -> 40 -> (head)
10 -> 30 -> (head)
10 -> 25 -> 30 -> (head)
10 -> 30 -> (head)
30 -> (head)
什麼都沒有啦~哥!!

主程式使用的函式總結

插入

• insertHead(&head, data) → 在頭部插入，當鏈結串列為空時呼叫insertEmpty(&head, data)。
• insertTail(&head, data) → 在尾部插入
• insertAfter(Node* prevNode, data) → 在指定節點後插入

刪除

• deleteHead(&head) → 刪除頭部節點
• deleteTail(&head) → 刪除尾部節點
• deleteNode(&head, key) → 刪除指定值的節點

額外

• printList(head) → 列印環狀鏈結串列