您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C語言順序表有序插入：兩種實現方案深度解析

編輯：關於C

順序表結構定義

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 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 insert_suitable_position(SqList *L, ElemType e) {
    int i, j;
    
    // 1. 查找第一個大於 e 的位置
    for (i = 0; i <= L->length - 1; i++) {
        if (L->elem[i] > e) break;
    }
    
    // 2. 若所有元素都 ≤ e，直接尾插
    if (i > L->length - 1) {
        L->elem[L->length] = e;
        L->length++;
        return OK;
    }
    
    // 3. 從後向前移動元素騰出位置
    for (j = L->length - 1; j >= i; j--) {
        L->elem[j + 1] = L->elem[j];
    }
    
    L->elem[i] = e;
    L->length++;
    return OK;
}

方案二：優化版——邊查找邊後移

Status insert_suitable_position_better(SqList *L, ElemType e) {
    int j;
    
    // 從後向前：同時完成查找與後移
    for (j = L->length; j > 0 && e < L->elem[j - 1]; j--) {
        L->elem[j] = L->elem[j - 1];
    }
    
    L->elem[j] = e;  // j 即為插入位置
    L->length++;
    return OK;
}

兩種方案對比分析

維度	方案一	方案二
代碼行數	較多	精簡
循環次數	兩次遍歷	單次遍歷
邏輯清晰度	步驟分明	緊湊但需理解
性能	O(n)	O(n)，常數因子更小

測試主程序

void main() {
    SqList L;
    int i, e;
    
    InitList(&L);
    L.length = 10;
    for (i = 0; i < L.length; i++) L.elem[i] = i;  // 有序數據 0~9
    
    printf("原序列: ");
    for (i = 0; i < L.length; i++) printf("%d\t", L.elem[i]);
    
    printf("\n插入的數字: ");
    scanf("%d", &e);
    
    insert_suitable_position_better(&L, e);
    
    printf("插入後: ");
    for (i = 0; i < L.length; i++) printf("%d\t", L.elem[i]);
}