C 語言線性表順序儲存結構完整實作：動態擴容、增刪查改

編輯：關於C語言

一、抽象資料型別 (ADT) 定義

// Sqlist.h
#ifndef SQLIST_H
#define SQLIST_H

#include 
#include 

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int ElemType; // 可改為任意型別

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10

typedef struct {
    ElemType *elem;    // 資料基址
    int length;        // 當前長度
    int listSize;      // 當前分配容量
} SqList;

// 介面宣告
Status InitList(SqList *L);
Status ListInsert(SqList *L, int pos, ElemType e);
Status ListDelete(SqList *L, int pos, ElemType *e);
Status ListGet(SqList *L, int pos, ElemType *e);
int LocateElem(SqList L, ElemType e);
Status ListTraverse(SqList L, void (*visit)(ElemType));
Status ClearList(SqList *L);
Status DestroyList(SqList *L);
int ListLength(SqList L);
int ListEmpty(SqList L);

#endif

二、核心操作實作

初始化與銷毀

Status InitList(SqList *L) {
    if (!L) return ERROR;
    L->elem = malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L->elem) return ERROR;
    L->length = 0;
    L->listSize = LIST_INIT_SIZE;
    return OK;
}

Status DestroyList(SqList *L) {
    if (!L || !L->elem) return ERROR;
    free(L->elem);
    L->elem = NULL;
    L->length = L->listSize = 0;
    return OK;
}

動態擴容插入

Status ListInsert(SqList *L, int pos, ElemType e) {
    if (!L || !L->elem) return ERROR;
    if (pos < 1 || pos > L->length + 1) return ERROR; // 位置合法性
    
    // 滿容擴容
    if (L->length >= L->listSize) {
        ElemType *newBase = realloc(L->elem, (L->listSize + LIST_INCREMENT) * sizeof(ElemType));
        if (!newBase) return ERROR;
        L->elem = newBase;
        L->listSize += LIST_INCREMENT;
    }
    
    // 從尾端向前搬移
    ElemType *p = L->elem + pos - 1;        // 插入位置
    ElemType *q = L->elem + L->length - 1;  // 最後元素
    for (; q >= p; q--) *(q + 1) = *q;
    
    *p = e;
    L->length++;
    return OK;
}

刪除與查找

Status ListDelete(SqList *L, int pos, ElemType *e) {
    if (!L || !L->elem || !e) return ERROR;
    if (L->length == 0) return ERROR;
    if (pos < 1 || pos > L->length) return ERROR;
    
    ElemType *p = L->elem + pos - 1;
    *e = *p;
    ElemType *q = L->elem + L->length - 1;
    for (++p; p <= q; p++) *(p - 1) = *p; // 後續元素前移
    L->length--;
    return OK;
}

int LocateElem(SqList L, ElemType e) {
    if (!L.elem) return 0;
    for (int i = 0; i < L.length; i++)
        if (L.elem[i] == e) return i + 1; // 回傳 1-based 位置
    return 0; // 未找到
}

遍歷與清空

Status ListTraverse(SqList L, void (*visit)(ElemType)) {
    if (!L.elem) return ERROR;
    for (int i = 0; i < L.length; i++) visit(L.elem[i]);
    return OK;
}

Status ClearList(SqList *L) {
    if (!L) return ERROR;
    L->length = 0; // 邏輯清空，記憶體保留供下次使用
    return OK;
}

三、測試驗證主程式

#include "Sqlist.h"

void printElem(ElemType e) { printf("%d ", e); }

int main() {
    SqList L;
    InitList(&L);
    
    // 測試插入
    for (int i = 1; i <= 10; i++) ListInsert(&L, i, i * 10);
    printf("Length: %d\n", ListLength(L));
    ListTraverse(L, printElem); putchar('\n');
    
    // 測試指定位置插入
    ListInsert(&L, 5, 999);
    ListTraverse(L, printElem); putchar('\n');
    
    // 測試刪除
    ElemType delVal;
    ListDelete(&L, 3, &delVal);
    printf("Deleted: %d\n", delVal);
    ListTraverse(L, printElem); putchar('\n');
    
    // 測試查找
    printf("Locate 999: %d\n", LocateElem(L, 999));
    printf("Locate 888: %d\n", LocateElem(L, 888));
    
    DestroyList(&L);
    return 0;
}