C語言實現線性表：順序表與鏈表完整指南

線性表基礎概念

線性表是數據結構中最基礎、最常用的結構之一。它由 n 個數據元素組成的有限序列，每個元素可以是基本類型（如整數、字符），也可以是復雜的結構體或對象。生活中的例子包括：整數序列 1,2,3,4,5；字母序列 A,B,C...Z；火車車廂 1,2...n 等。

線性表的兩種存儲結構

順序存儲結構（順序表）

順序表將數據元素按邏輯順序依次存儲在連續的物理存儲單元中。相鄰元素在物理位置上也相鄰。假設每個 int 型元素佔 4 個存儲單元，首元素地址為 1000，則第 n 個元素地址為 LOC(aₙ) = LOC(a₁) + (n-1)×k，其中 k 為每個元素佔用的存儲長度。

鏈式存儲結構（線性鏈表）

鏈表不要求邏輯相鄰的元素在物理上也相鄰。每個節點包含數據域（存儲元素值）和指針域（存儲直接後繼地址）。節點之間通過指針建立邏輯關係，實現靈活的動態存儲管理。

C語言實現順序表

結構定義

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef int ElemType;
typedef struct {
    ElemType *elem;  // 存儲空間基地址
    int length;      // 當前長度
    int listsize;    // 當前分配容量
} SqList;

核心操作實現

1. 初始化線性表

int InitList(SqList &L) {
    L.elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem) return -1;  // 分配失敗
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return 0;
}

2. 按值查找元素

int LocateElem(SqList L, ElemType x) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == x) return i;
    }
    return -1;  // 未找到
}
// 時間複雜度：O(n)

3. 插入元素

int ListInsert(SqList &L, int i, ElemType e) {
    if (i < 1 || i > L.length + 1) return -1;  // 位置非法
    if (L.length >= L.listsize) {  // 擴容
        ElemType *newbase = (ElemType *)realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if (!newbase) return -1;
        L.elem = newbase;
        L.listsize += LISTINCREMENT;
    }
    ElemType *q = &(L.elem[i-1]);  // 插入位置
    for (ElemType *p = &(L.elem[L.length-1]); p >= q; --p) {
        *(p+1) = *p;  // 後移元素
    }
    *q = e;
    ++L.length;
    return 0;
}
// 時間複雜度：O(n)

4. 刪除元素

int ListDelete(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) return -1;
    ElemType *p = &(L.elem[i-1]);  // 被刪除元素
    e = *p;  // 保存被刪除值
    ElemType *q = L.elem + L.length - 1;  // 表尾元素
    for (++p; p <= q; ++p) {
        *(p-1) = *p;  // 前移元素
    }
    --L.length;
    return 0;
}
// 時間複雜度：O(n)

C語言實現線性鏈表

節點結構定義

typedef struct LNode {
    ElemType data;      // 數據域
    struct LNode *next; // 指針域
} LNode;

核心操作實現

1. 頭插法創建鏈表

LNode* CreateListHead(int n) {
    LNode *L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = n; i > 0; --i) {
        LNode *p = (LNode *)malloc(sizeof(LNode));
        scanf("%d", &p->data);
        p->next = L->next;
        L->next = p;
    }
    return L;
}

2. 尾插法創建鏈表

LNode* CreateListTail() {
    LNode *L = (LNode *)malloc(sizeof(LNode));
    L->next = NULL;
    LNode *r = L;  // 尾指針
    int x, flag = 0;
    scanf("%d", &x);
    while (x != flag) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

3. 查找第 i 個元素

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

4. 插入元素

int ListInsert(LNode *L, int i, ElemType e) {
    LNode *p = L;
    int j = 0;
    while (p && j < i-1) {  // 找第 i-1 個節點
        p = p->next;
        ++j;
    }
    if (!p) return -1;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return 0;
}

5. 刪除元素

int ListDelete(LNode *L, int i, ElemType &e) {
    LNode *p = L;
    int j = 0;
    while (p->next && j < i-1) {
        p = p->next;
        ++j;
    }
    if (!(p->next) || j > i-1) return -1;
    LNode *q = p->next;
    p->next = q->next;
    e = q->data;
    free(q);
    return 0;
}

總結與對比

選擇哪種結構取決於具體應用場景：頻繁查找少增刪用順序表；頻繁增刪少查找用鏈表。