数据结构基础：顺序表的定义与实现

2. 初始化

初始化需改变实参，因此传递指针。

void SLInit(SL* sl) {
    assert(sl);
    sl->arr = NULL;
    sl->size = 0;
    sl->capacity = 0;
}

3. 销毁

由于内存由动态申请，需要释放堆区内存。回收后手动置空指针，防止野指针。

void SLDestroy(SL* sl) {
    assert(sl);
    free(sl->arr);
    sl->arr = NULL;
    sl->size = 0;
    sl->capacity = 0;
}

4. 数据的增添

a. 尾插

核心思路：检查空间是否充足，若不足则扩容，然后在末尾插入数据。

void SLCheckCapacity(SL* sl) {
    assert(sl);
    if (sl->size == sl->capacity) {
        int newCapacity = sl->capacity == 0 ? 4 : sl->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(sl->arr, newCapacity * sizeof(SLDataType));
        if (tmp == NULL) {
            perror("realloc");
            exit(1);
        }
        sl->capacity = newCapacity;
        sl->arr = tmp;
    }
}

void SLPushBack(SL* sl, SLDataType x) {
    assert(sl);
    SLCheckCapacity(sl);
    sl->arr[sl->size] = x;
    sl->size++;
}

b. 头插

核心思路：整体元素向后移动，然后将数据添加在首元素位置。移动时应从后往前，避免数据覆盖丢失。

void SLPushFront(SL* sl, SLDataType x) {
    assert(sl);
    SLCheckCapacity(sl);
    for (int i = sl->size; i > 0; i--) {
        sl->arr[i] = sl->arr[i - 1];
    }
    sl->arr[0] = x;
    sl->size++;
}

c. 指定位置插入

void SLPushInsert(SL* sl, int pos, SLDataType x) {
    assert(sl);
    assert(pos >= 0 && pos <= sl->size);
    SLCheckCapacity(sl);
    for (int i = sl->size; i > pos; i--) {
        sl->arr[i] = sl->arr[i - 1];
    }
    sl->arr[pos] = x;
    sl->size++;
}

5. 数据的删除

a. 尾删

减少有效数据个数即可。

void SLPopBack(SL* sl) {
    assert(sl);
    if (sl->size > 0) {
        sl->size--;
    }
}

b. 头删

首元素后面的元素依次往前移动一个位置。

void SLPopFront(SL* sl) {
    assert(sl);
    if (sl->size > 0) {
        for (int i = 0; i < sl->size - 1; i++) {
            sl->arr[i] = sl->arr[i + 1];
        }
        sl->size--;
    }
}

c. 指定位置删除

void SLErase(SL* sl, int pos) {
    assert(sl);
    assert(pos >= 0 && pos < sl->size);
    for (int i = pos; i < sl->size - 1; i++) {
        sl->arr[i] = sl->arr[i + 1];
    }
    sl->size--;
}

6. 查找

通过遍历找寻给定数据。

int SLFind(SL* sl, SLDataType x) {
    assert(sl);
    for (int i = 0; i < sl->size; i++) {
        if (sl->arr[i] == x) {
            return i;
        }
    }
    return -1;
}

7. 修改

找到数据后覆盖即可。

void SLModify(SL* sl, SLDataType x, SLDataType y) {
    assert(sl);
    for (int i = 0; i < sl->size; i++) {
        if (sl->arr[i] == x) {
            sl->arr[i] = y;
            break;
        }
    }
}

通过学习顺序表，可以完成如通讯录等项目，只需将数组改为存放姓名、联系方式的结构体即可。