帶頭節點單鏈表核心操作庫：插入、刪除、交集、並集、相鄰交換完整實現

編輯：關於C語言

單鏈表標準操作庫：模組化設計與完整實現

採用帶頭節點單鏈表，實現初始化、增刪改查、遍歷、交集、並集、相鄰元素交換等核心操作。模組劃分清晰：頭文件聲明、庫函數實現、測試驗證。

模組文件結構

list.h：類型定義、函數聲明
fatal.h：錯誤處理宏
list.c：所有操作實現
testlist.c：功能測試

核心類型定義

// list.h
typedef int ElementType;
struct Node;
typedef struct Node *PtrToNode;
typedef PtrToNode List;
typedef PtrToNode Position;

List MakeEmpty(List L);
void DeleteList(List L);
int IsEmpty(List L);
int IsLast(Position P, List L);
Position Find(ElementType X, List L);
void Delete(ElementType X, List L);
Position FindPrevious(ElementType X, List L);
void Insert(ElementType X, List L, Position P);
Position Header(List L);
Position First(List L);
Position Advance(Position P);
ElementType Retrieve(Position P);
void PrintList(const List L);
void PrintLots(List L, List P);
void SwapWithNext(Position BeforeP, List L);
List IntersectList(List L, List P);
List UnionList(Position L, Position P);

關鍵操作實現精要

初始化與銷毀

List MakeEmpty(List L) {
    if (L != NULL) DeleteList(L);
    L = malloc(sizeof(struct Node));
    if (!L) FatalError("Out of memory!");
    L->Next = NULL;
    return L;
}

void DeleteList(List L) {
    Position P = L->Next, Tmp;
    L->Next = NULL;
    while (P) { Tmp = P->Next; free(P); P = Tmp; }
}

插入與刪除

void Insert(ElementType X, List L, Position P) {
    Position Tmp = malloc(sizeof(struct Node));
    if (!Tmp) FatalError("Out of Space!!!");
    Tmp->Element = X;
    Tmp->Next = P->Next;
    P->Next = Tmp;
}

void Delete(ElementType X, List L) {
    Position P = FindPrevious(X, L);
    if (!IsLast(P, L)) {
        Position Tmp = P->Next;
        P->Next = Tmp->Next;
        free(Tmp);
    }
}

相鄰元素交換（僅調整指標）

void SwapWithNext(Position BeforeP, List L) {
    Position P = Advance(BeforeP);
    if (!P) return;
    Position AfterP = Advance(P);
    if (!AfterP) return;

    P->Next = AfterP->Next;
    BeforeP->Next = AfterP;
    AfterP->Next = P;
}

有序鏈表交集與並集（歸併思想）

List IntersectList(List L1, List L2) {  // 假設輸入有序
    List R = MakeEmpty(NULL);
    Position p1 = First(L1), p2 = First(L2), r = Header(R);
    while (p1 && p2) {
        if (p1->Element < p2->Element) p1 = Advance(p1);
        else if (p1->Element > p2->Element) p2 = Advance(p2);
        else {
            Insert(p1->Element, R, r);
            r = Advance(r);
            p1 = Advance(p1); p2 = Advance(p2);
        }
    }
    return R;
}

List UnionList(List L1, List L2) {  // 假設輸入有序
    List R = MakeEmpty(NULL);
    Position p1 = First(L1), p2 = First(L2), r = Header(R);
    ElementType val;
    while (p1 && p2) {
        if (p1->Element < p2->Element) { val = p1->Element; p1 = Advance(p1); }
        else if (p1->Element > p2->Element) { val = p2->Element; p2 = Advance(p2); }
        else { val = p1->Element; p1 = Advance(p1); p2 = Advance(p2); }
        Insert(val, R, r); r = Advance(r);
    }
    while (p1) { Insert(p1->Element, R, r); r = Advance(r); p1 = Advance(p1); }
    while (p2) { Insert(p2->Element, R, r); r = Advance(r); p2 = Advance(p2); }
    return R;
}

測試驗證

// testlist.c 片段
L = MakeEmpty(NULL);
for (i=0; i<50; i+=2) Insert(i, L, P), P=Advance(P);  // 0,2,4...48
L1 = MakeEmpty(NULL);
for (i=1; i<100; i+=3) Insert(i, L1, P1), P1=Advance(P1); // 1,4,7...97
PrintList(IntersectList(L, L1));  // 應輸出 4,10,16...46
PrintList(UnionList(L, L1));      // 合併去重