C語言實現線性表順序存儲結構 - 完整教程與代碼

概述

在數據結構中，線性表的順序存儲是指用一組地址連續的存儲單元依次存儲線性表的數據元素。本文實現了一個基於動態數組的順序表，支持增、刪、改、查、插入、追加等操作，並提供菜單交互界面。

核心數據結構

// 順序表結構
typedef struct {
    int *data;      // 動態分配的數組指針
    int length;     // 當前長度
    int capacity;   // 容量
} SeqList;

主要功能實現

1. 初始化與銷毀

SeqList* createList(int capacity) {
    SeqList *L = (SeqList*)malloc(sizeof(SeqList));
    L->data = (int*)malloc(capacity * sizeof(int));
    L->length = 0;
    L->capacity = capacity;
    return L;
}

void destroyList(SeqList *L) {
    free(L->data);
    free(L);
}

2. 尾部追加

int append(SeqList *L, int val) {
    if (L->length == L->capacity) return 0; // 滿
    L->data[L->length++] = val;
    return 1;
}

3. 指定位置插入

int insert(SeqList *L, int pos, int val) {
    if (pos < 1 || pos > L->length + 1) return 0; // 位置非法
    if (L->length == L->capacity) return 0;       // 滿
    for (int i = L->length; i >= pos; i--)
        L->data[i] = L->data[i-1];
    L->data[pos-1] = val;
    L->length++;
    return 1;
}

4. 刪除指定位置

int deletePos(SeqList *L, int pos) {
    if (pos < 1 || pos > L->length) return 0;
    for (int i = pos; i < L->length; i++)
        L->data[i-1] = L->data[i];
    L->length--;
    return 1;
}

5. 修改指定位置

int modify(SeqList *L, int pos, int val) {
    if (pos < 1 || pos > L->length) return 0;
    L->data[pos-1] = val;
    return 1;
}

6. 查找與遍歷

int find(SeqList *L, int val) {
    for (int i = 0; i < L->length; i++)
        if (L->data[i] == val) return i+1; // 返回1-based位置
    return -1;
}

void printList(SeqList *L) {
    for (int i = 0; i < L->length; i++)
        printf("%d ", L->data[i]);
    printf("\n");
}

完整可運行程序（含菜單交互）

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

typedef struct { int *data; int length, capacity; } SeqList;

SeqList* init(int cap) {
    SeqList *L = malloc(sizeof(SeqList));
    L->data = malloc(cap * sizeof(int));
    L->capacity = cap; L->length = 0;
    return L;
}

void menu() {
    puts("\n1. Append  2. Insert  3. Delete  4. Modify  5. Find  6. Show  0. Exit");
}

int main() {
    int cap; printf("Capacity: "); scanf("%d", &cap);
    SeqList *L = init(cap);
    int op, pos, val;
    while (1) {
        menu(); printf("Choice: "); scanf("%d", &op);
        if (op == 0) break;
        switch (op) {
            case 1: printf("Value: "); scanf("%d", &val);
                    append(L, val) ? puts("OK") : puts("Full"); break;
            case 2: printf("Pos Value: "); scanf("%d%d", &pos, &val);
                    insert(L, pos, val) ? puts("OK") : puts("Invalid"); break;
            case 3: printf("Pos: "); scanf("%d", &pos);
                    deletePos(L, pos) ? puts("OK") : puts("Invalid"); break;
            case 4: printf("Pos Value: "); scanf("%d%d", &pos, &val);
                    modify(L, pos, val) ? puts("OK") : puts("Invalid"); break;
            case 5: printf("Value: "); scanf("%d", &val);
                    pos = find(L, val);
                    pos > 0 ? printf("Found at %d\n", pos) : puts("Not found"); break;
            case 6: printList(L); break;
        }
    }
    destroyList(L);
    return 0;
}

關鍵點總結

• 動態分配：用 malloc 分配數組，靈活指定容量。
• 邊界檢查：所有操作前檢查位置合法性、是否溢出。
• 元素移動：插入需後移，刪除需前移，注意循環方向。
• 內存管理：程序結束前務必 free 釋放內存，防止洩漏。

常見錯誤與改進

• 未檢查 malloc 返回值，可能導致空指針解引用。
• 插入/刪除循環邊界易出錯，建議畫圖驗證。
• 可擴展為動態擴容（realloc），支持不限長度。
• 泛型化：用 void* 存儲任意類型數據。