C 語言實現集合運算：有序鏈表實現並集、交集、差集

編輯：關於C語言

一、題目需求

元素範圍：小寫字母 'a'~'z'。
數據結構：有序單鏈表（遞增）。
操作：並集、交集、差集（A - B）。

二、數據結構定義

typedef struct Node {
    char data;
    struct Node* next;
} Node;

三、核心算法邏輯

利用有序特性，雙指針同步遍歷，類似歸併排序的 merge 過程：

並集：較小者輸出並前進；相等輸出一個並雙前進。
交集：僅相等時輸出並雙前進；否則較小者前進。
差集 (A-B)：遍歷 A，若元素在 B 中存在則跳過，否則輸出。

四、完整可編譯代碼 (C99)

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

typedef struct Node {
    char data;
    struct Node* next;
} Node;

/* 尾插法建立有序鏈表（輸入以 '0' 結束） */
Node* createSet(const char* prompt) {
    Node* head = (Node*)malloc(sizeof(Node));
    head->next = NULL;
    Node* tail = head;
    char ch;
    printf("%s", prompt);
    while (scanf(" %c", &ch) == 1 && ch != '0') {
        // 保持有序插入（簡化：假設輸入已有序，直接尾插）
        Node* p = (Node*)malloc(sizeof(Node));
        p->data = ch;
        p->next = NULL;
        tail->next = p;
        tail = p;
    }
    return head;
}

/* 顯示集合 */
void display(Node* head) {
    for (Node* p = head->next; p; p = p->next)
        printf("%c ", p->data);
    printf("\n");
}

/* 釋放鏈表 */
void freeList(Node* head) {
    while (head) {
        Node* tmp = head;
        head = head->next;
        free(tmp);
    }
}

/* 並集：A ∪ B -> result */
void setUnion(Node* A, Node* B, Node* result) {
    Node *p1 = A->next, *p2 = B->next, *tail = result;
    while (p1 && p2) {
        Node* node = (Node*)malloc(sizeof(Node));
        if (p1->data < p2->data) {
            node->data = p1->data;
            p1 = p1->next;
        } else if (p1->data > p2->data) {
            node->data = p2->data;
            p2 = p2->next;
        } else {
            node->data = p1->data;
            p1 = p1->next;
            p2 = p2->next;
        }
        node->next = NULL;
        tail->next = node;
        tail = node;
    }
    while (p1) { tail->next = (Node*)malloc(sizeof(Node)); tail = tail->next; tail->data = p1->data; tail->next = NULL; p1 = p1->next; }
    while (p2) { tail->next = (Node*)malloc(sizeof(Node)); tail = tail->next; tail->data = p2->data; tail->next = NULL; p2 = p2->next; }
}

/* 交集：A ∩ B -> result */
void setIntersection(Node* A, Node* B, Node* result) {
    Node *p1 = A->next, *p2 = B->next, *tail = result;
    while (p1 && p2) {
        if (p1->data < p2->data) p1 = p1->next;
        else if (p1->data > p2->data) p2 = p2->next;
        else {
            Node* node = (Node*)malloc(sizeof(Node));
            node->data = p1->data;
            node->next = NULL;
            tail->next = node;
            tail = node;
            p1 = p1->next;
            p2 = p2->next;
        }
    }
}

/* 差集：A - B -> result */
void setDifference(Node* A, Node* B, Node* result) {
    Node *p1 = A->next, *p2 = B->next, *tail = result;
    while (p1) {
        while (p2 && p2->data < p1->data) p2 = p2->next;
        if (!p2 || p2->data > p1->data) { // p1 不在 B 中
            Node* node = (Node*)malloc(sizeof(Node));
            node->data = p1->data;
            node->next = NULL;
            tail->next = node;
            tail = node;
        } else { // 相等，跳過
            p2 = p2->next;
        }
        p1 = p1->next;
    }
}

int main() {
    Node* A = createSet("輸入集合 A (a-z, 0 結束): ");
    Node* B = createSet("輸入集合 B (a-z, 0 結束): ");

    printf("集合 A: "); display(A);
    printf("集合 B: "); display(B);

    Node* U = (Node*)malloc(sizeof(Node)); U->next = NULL;
    setUnion(A, B, U);
    printf("並集 A∪B: "); display(U); freeList(U);

    Node* I = (Node*)malloc(sizeof(Node)); I->next = NULL;
    setIntersection(A, B, I);
    printf("交集 A∩B: "); display(I); freeList(I);

    Node* D = (Node*)malloc(sizeof(Node)); D->next = NULL;
    setDifference(A, B, D);
    printf("差集 A-B: "); display(D); freeList(D);

    freeList(A); freeList(B);
    return 0;
}