您现在的位置：程式碼之家 >> 數據庫知識 > >> Oracle 資料庫 >> Oracle 資料庫基礎

資料結構教學：單向循環鏈表的 C 語言實作與操作詳解

編輯：Oracle 資料庫基礎

實驗主題：單向循環鏈表實作

本實驗旨在讓學習者掌握單向鏈表的儲存結構與基本操作實作，重點在於理解節點的動態記憶體配置、指標操作以及鏈表的插入、查找、合併等核心演算法。實驗難點在於正確處理指標的指向關係，避免記憶體洩漏與野指標問題。

一、單向鏈表的儲存表示

單向鏈表由一系列節點組成，每個節點包含資料域與指向下一個節點的指標。在 C 語言中，我們定義學生資料結構 STU 作為元素型別，並建立鏈表節點結構 LNODE：

#include <stdio.h>
#include <malloc.h>
#include <conio.h>
#include <string.h>

#define ERROR 0
#define OK 1
#define EQUAL 1
#define OVERFLOW -1

typedef struct STU {
    char name[20];
    char stuno[10];
    int age;
    int score;
} ElemType;

typedef struct LNODE {
    ElemType data;
    struct LNODE *next;
} LNode, *LinkList;

初始化鏈表

建立帶頭節點的空鏈表，頭節點不存放資料，其 next 指向 NULL：

int InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (!*L) exit(OVERFLOW);
    (*L)->next = NULL;
    return OK;
}

二、單向鏈表的基本操作

1. 求鏈表長度

從頭節點開始遍歷，計數非空節點數量：

int ListLength(LinkList L) {
    int len = 0;
    LinkList p = L->next;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}

2. 按位置查找元素

獲取第 i 個節點的資料，位序從 1 開始：

int GetElem(LinkList L, int i, ElemType *e) {
    LinkList p = L->next;
    int j = 1;
    while (p && j < i) {
        p = p->next;
        j++;
    }
    if (!p || j > i) return ERROR;
    *e = p->data;
    return OK;
}

3. 按姓名比較與查找

使用 strcmp 實現學生姓名的精確匹配與大小比較：

int EqualList(ElemType *e1, ElemType *e2) {
    return strcmp(e1->name, e2->name) == 0;
}

int LessEqualList(ElemType *e1, ElemType *e2) {
    return strcmp(e1->name, e2->name) <= 0;
}

int LocateElem(LinkList L, ElemType e) {
    LinkList p = L->next;
    while (p) {
        if (EqualList(&p->data, &e)) return 1;
        p = p->next;
    }
    return 0;
}

4. 有序鏈表合併

將兩個按姓名遞增排序的鏈表 La、Lb 合併為 Lc，利用尾插法構建新鏈表，最後釋放 Lb 頭節點：

void MergeList(LinkList La, LinkList Lb, LinkList *Lc) {
    LinkList pa = La->next, pb = Lb->next;
    *Lc = pc = La;  // 以 La 的頭節點作為 Lc 的頭節點
    while (pa && pb) {
        if (LessEqualList(&pa->data, &pb->data)) {
            pc->next = pa; pc = pa; pa = pa->next;
        } else {
            pc->next = pb; pc = pb; pb = pb->next;
        }
    }
    pc->next = pa ? pa : pb;
    free(Lb);
}

5. 鏈表輸出

遍歷並格式化輸出所有學生資訊：

void PrintList(LinkList L) {
    LinkList p = L->next;
    printf("%-10s %-10s %-5s %-8s\n", "name", "stuno", "age", "score");
    while (p) {
        printf("%-10s %-10s %-5d %-8d\n",
               p->data.name, p->data.stuno, p->data.age, p->data.score);
        p = p->next;
    }
    printf("\n");
}

6. 指定位置插入節點

在第 i 個位置前插入新節點，需先找到第 i-1 個節點：

int ListInsert(LinkList L, int i, ElemType e) {
    LinkList p = L, s;
    int j = 0;
    while (p && j < i-1) { p = p->next; j++; }
    if (!p || j > i-1) return ERROR;
    s = (LinkList)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return OK;
}

三、主程式測試流程

main() 函式示範了完整的操作流程：初始化兩個鏈表、分別插入學生資料、列印內容、最後合併兩個有序鏈表並輸出結果。程式使用 getch() 分階段暫停，方便觀察每步執行結果。

int main() {
    ElemType e;
    LinkList La, Lb, Lc;
    clrscr();
    printf("--- List Demo Running ---\n\n");

    InitList(&La);
    strcpy(e.name, "stu1"); strcpy(e.stuno, "100001"); e.age=20; e.score=90;
    ListInsert(La, 1, e);
    strcpy(e.name, "stu3"); strcpy(e.stuno, "100002"); e.age=21; e.score=85;
    ListInsert(La, 2, e);
    PrintList(La); getch();

    strcpy(e.name, "stu5"); strcpy(e.stuno, "100003"); e.age=22; e.score=88;
    ListInsert(La, 3, e);
    PrintList(La); getch();

    InitList(&Lb);
    strcpy(e.name, "stu2"); strcpy(e.stuno, "100004"); e.age=20; e.score=92;
    ListInsert(Lb, 1, e);
    strcpy(e.name, "stu4"); strcpy(e.stuno, "100005"); e.age=21; e.score=87;
    ListInsert(Lb, 2, e);
    strcpy(e.name, "stu6"); strcpy(e.stuno, "100006"); e.age=22; e.score=95;
    ListInsert(Lb, 3, e);
    PrintList(Lb); getch();

    MergeList(La, Lb, &Lc);
    PrintList(Lc); getch();
    return 0;
}