C 語言順序表有序插入：將元素插入適當位置保持有序性

編輯：關於C語言

問題描述

給定一個**已按升序排列**的順序表（動態陣列），將新元素 e 插入適當位置，使表仍保持有序。需處理：插入頭部、中間、尾部、擴容（若滿）等情況。

資料結構定義


#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10

typedef int ElemType;
typedef int Status;

typedef struct {
    ElemType *elem;   // 動態陣列基址
    int length;       // 當前長度
    int listsize;     // 當前分配容量
} SqList;

初始化函數


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

核心插入演算法（兩種實作）

版本一：分步驟清晰版


Status InsertOrdered_V1(SqList *L, ElemType e) {
    // 1. 擴容檢查
    if (L->length >= L->listsize) {
        ElemType *newbase = (ElemType *)realloc(L->elem,
            (L->listsize + LIST_INCREMENT) * sizeof(ElemType));
        if (!newbase) return ERROR;
        L->elem = newbase;
        L->listsize += LIST_INCREMENT;
    }

    // 2. 尋找插入位置：第一個大於 e 的元素索引
    int i;
    for (i = 0; i < L->length; i++) {
        if (L->elem[i] > e) break;
    }

    // 3. 後移元素騰出空位
    for (int j = L->length - 1; j >= i; j--) {
        L->elem[j + 1] = L->elem[j];
    }

    // 4. 插入並更新長度
    L->elem[i] = e;
    L->length++;
    return OK;
}

版本二：合併尋找與後移（更優雅）


Status InsertOrdered_V2(SqList *L, ElemType e) {
    // 擴容檢查同上...

    int j;
    // 從尾部向前掃描，邊掃描邊後移，直到找到 <= e 的位置
    for (j = L->length; j > 0 && e < L->elem[j - 1]; j--) {
        L->elem[j] = L->elem[j - 1];
    }
    L->elem[j] = e;
    L->length++;
    return OK;
}

版本二優勢： 單迴圈完成「找位置 + 移元素」，無需額外變數 i，邏輯緊湊，效能略優。

完整測試主程式


#include 
#include 

// ... 以上結構體、InitList、InsertOrdered_V2 定義 ...

int main() {
    SqList L;
    InitList(&L);

    // 預置有序資料 0~9
    L.length = 10;
    for (int i = 0; i < 10; i++) L.elem[i] = i;

    printf("插入前: ");
    for (int i = 0; i < L.length; i++) printf("%d ", L.elem[i]);
    printf("\n");

    int e;
    printf("請輸入要插入的整數: ");
    scanf("%d", &e);

    InsertOrdered_V2(&L, e);

    printf("插入後: ");
    for (int i = 0; i < L.length; i++) printf("%d ", L.elem[i]);
    printf("\n");

    free(L.elem);
    return 0;
}