【数据结构】线性表的顺序存储结构（C 语言版）

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

#define OK 0
#define ERROR -1
// 分配存储空间的初始长度
#define LIST_INIT_SIZE 10

typedef int ElemType;

// 线性表的顺序存储结构
typedef struct {
    // 存储空间基址
    ElemType *elem;
    // 当前长度
    int length;
    // 当前分配的存储容量
    int listSize;
} List;

// 创建线性表
int create(List &L);

// 扩容
int grow(List &L);

// 查找元素，返回首次出现的下标，找不到返回-1
int get(List &L, ElemType e);

// 添加元素
int add(List &L, ElemType e);

// 在指定位置插入元素
int insert(List &L, int i, ElemType e);

// 删除指定位置的元素，并返回
ElemType remove(List &L, int i);

// 打印线性表
int display(List &L);

// 清空线性表
int clear(List &L);

// 销毁线性表
int destroy(List &L);

int create(List &L) {
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));

    // 存储空间分配失败
    if (!L.elem)return ERROR;

    L.length = 0;
    L.listSize = LIST_INIT_SIZE;

    return OK;
}

int grow(List &L) {
    if (L.length >= L.listSize) {
        // 扩容机制仿照 Java的ArrayList，为原大小的1.5倍，>>1 表示除以2的1次方
        ElemType *newBase = (ElemType *) realloc(L.elem, (L.listSize + (L.listSize >> 1)) * sizeof(ElemType));
        if (!newBase)return ERROR;
        L.elem = newBase;
        L.listSize += L.listSize >> 1;
    }

    return OK;
}

int get(List &L, ElemType e) {
    for (int i = 0; i < L.length; ++i) {
        if (L.elem[i] == e)return i;
    }

    return ERROR;
}

int add(List &L, ElemType e) {
    grow(L);
    L.elem[L.length++] = e;

    return OK;
}

int insert(List &L, int i, ElemType e) {
    if (i < 0 || i > L.length)return ERROR;
    grow(L);

    // p指向待插入位置，q指向最后一个元素
    ElemType *p = &L.elem[i], *q = &L.elem[L.length - 1];
    while (q >= p) {
        *(q + 1) = *q;
        q--;
    }

    *p = e;
    L.length++;

    return OK;
}

ElemType remove(List &L, int i) {
    if (i < 0 || i > L.length)return ERROR;

    // p指向待删除位置
    ElemType *p = &L.elem[i];
    // q指向最后一个元素
    ElemType *q = &L.elem[L.length - 1];
    ElemType del = *p;
    p++;

    while (p <= q) {
        *(p - 1) = *p;
        p++;
    }
    L.length--;

    // 最后一个元素并没有删除，由于length的限制没有打印出来，这句写不写无所谓，因为已经开辟了这一块的存储空间
    //L.elem[L.length] = NULL;

    return del;
}

int display(List &L) {
    if (L.elem == NULL || L.length == 0) {
        printf("[]\n");
        return ERROR;
    }

    printf("[");
    for (int i = 0; i < L.length - 1; i++) {
        printf("%d,", L.elem[i]);
    }
    // 最后一个元素单独打印，目的是让最后一个逗号不打印
    printf("%d]\n", L.elem[L.length - 1]);

    return OK;
}

int clear(List &L) {
    ElemType *temp = L.elem;

    // 将每一个元素设为NULL
    for (int i = 0; i < L.length; ++i) {
        *L.elem = NULL;
        L.elem++;
    }

    L.length = 0;
    L.elem = temp;

    return OK;
}

int destroy(List &L) {
    free(L.elem);
    L.elem = NULL;
    L.length = 0;
    L.listSize = 0;

    return OK;
}


int main() {
    List list;
    create(list);

    // 添加10个元素
    for (int i = 0; i < 5; ++i) {
        add(list, (i + 1) * 10);
    }

    printf("%d\n", list.length);
    display(list);

    insert(list, 3, 123);
    display(list);


    // 移除下标为0的元素，并返回
    printf("%d\n", remove(list, 0));
    display(list);
    printf("%d\n", list.elem[4]);

    printf("%d\n", get(list, 123));


    clear(list);
    display(list);

    add(list, 223);
    add(list, 233);
    add(list, 2233);

    display(list);
    printf("%d\n", list.length);

    destroy(list);
    printf("%d\n", list.length);
    display(list);


    return 0;
}

运行结果