資料結構：C 語言實作多維陣列順序儲存表示

資料結構：C 語言實作多維陣列順序儲存表示

本文實作通用的多維陣列順序儲存結構，支援任意維度（上限 8 維），包含初始化、銷毀、定位、賦值、取值等核心操作，並展示記憶體映射函數的計算邏輯。

資料結構定義

#define MAX_ARRAY_DIM 8
#define OK 1
#define ERROR 0
#define UNDERFLOW 2

typedef int Status;
typedef int ElemType;

typedef struct {
    ElemType *base;      // 陣列元素儲存空間基址
    int dim;             // 陣列維數
    int *bounds;         // 各維長度陣列
    int *constants;      // 映射函數常數（跨度）陣列
} Array;

核心操作實作

1. 初始化

Status InitArray(Array *A, int dim, ...) {
    va_list ap;
    int elemtotal = 1, i;

    if (dim < 1 || dim > MAX_ARRAY_DIM) return ERROR;
    A->dim = dim;
    A->bounds = (int*)malloc(dim * sizeof(int));
    if (!A->bounds) return ERROR;

    va_start(ap, dim);
    for (i = 0; i < dim; i++) {
        A->bounds[i] = va_arg(ap, int);
        if (A->bounds[i] < 0) return UNDERFLOW;
        elemtotal *= A->bounds[i];
    }
    va_end(ap);

    A->base = (ElemType*)malloc(elemtotal * sizeof(ElemType));
    if (!A->base) return ERROR;

    A->constants = (int*)malloc(dim * sizeof(int));
    if (!A->constants) return ERROR;

    // 計算映射常數：row-major order
    A->constants[dim - 1] = 1;
    for (i = dim - 2; i >= 0; --i)
        A->constants[i] = A->bounds[i + 1] * A->constants[i + 1];

    return OK;
}

2. 定位函數

Status Locate(Array A, va_list ap, int *off) {
    int ind, i;
    *off = 0;
    for (i = 0; i < A.dim; i++) {
        ind = va_arg(ap, int);
        if (ind < 0 || ind >= A.bounds[i]) return ERROR;
        *off += A.constants[i] * ind;
    }
    return OK;
}

3. 賦值與取值

Status Assign(Array *A, ElemType e, ...) {
    va_list ap; int off; Status result;
    va_start(ap, e);
    if ((result = Locate(*A, ap, &off)) != OK) return result;
    *(A->base + off) = e;
    va_end(ap);
    return OK;
}

Status Value(Array A, ElemType *e, ...) {
    va_list ap; int off; Status result;
    va_start(ap, e);
    if ((result = Locate(A, ap, &off)) != OK) return result;
    *e = *(A.base + off);
    va_end(ap);
    return OK;
}

4. 銷毀

Status DestroyArray(Array *A) {
    free(A->base);
    free(A->bounds);
    free(A->constants);
    return OK;
}

測試主程式

int main() {
    Array A; ElemType e;
    InitArray(&A, 3, 2, 2, 2); // 2x2x2 陣列
    printf("這是一個 %d 維的陣列!\n", A.dim);
    // ... 後續測試賦值/取值
    DestroyArray(&A);
    return 0;
}

記憶體映射原理圖解

關鍵點總結

• Row-major 映射：offset = Σ (index[i] * constants[i])，constants[i] = Π bounds[j] (j>i)。
• 可變參數 va_list 處理不定維度的下標輸入。
• 動態配置三個陣列（base、bounds、constants），銷毀時必須全部釋放。
• 錯誤碼設計：OK、ERROR、UNDERFLOW 區分不同失敗原因。