数据结构入门：顺序表的实现与原理

2.2.3 销毁

释放动态数组内存，并将指针置空，防止野指针。

void SeqDestroy(SL* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

2.2.4 容量检查与扩容

当数据存满（size == capacity）时，需要扩容。通常采用 2 倍扩容策略。注意 realloc 成功后需更新指针，且计算字节数时要乘以元素大小。

void SLCheckCapacity(SL* ps) {
    assert(ps);
    if (ps->size == ps->capacity) {
        size_t newcap = ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcap);
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        ps->a = tmp;
        ps->capacity = newcap;
    }
}

2.2.5 尾插

先检查容量，再在末尾插入，时间复杂度 O(1)。

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

2.2.6 头插

需要将后续所有元素向后移动一位，时间复杂度 O(n)。

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

2.2.7 尾删

直接减少 size 即可，无需真正回收内存。注意判空。

void SLPopBack(SL* ps) {
    assert(ps && ps->size > 0);
    ps->a[ps->size - 1] = 0; // 可选：清除数据
    ps->size--;
}

2.2.8 头删

将后续元素向前覆盖，时间复杂度 O(n)。

void SLPopFront(SL* ps) {
    assert(ps && ps->size > 0);
    int begin = 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

2.2.9 指定位置插入

从 pos 开始后的元素全部后移，再填入新值。

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps && pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

2.2.10 指定位置删除

从 pos 之后的元素全部前移覆盖。

void SLErase(SL* ps, int pos) {
    assert(ps && pos >= 0 && pos < ps->size);
    int begin = pos + 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

2.2.11 查找

线性遍历，找到返回索引，否则返回 -1。

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

3. 顺序表的优劣分析

1. 优点：随机访问效率高，O(1) 时间复杂度；缓存友好。
2. 缺点：中间或头部插入/删除效率低，O(n)；增容涉及内存申请、拷贝、释放，消耗较大；预分配空间可能导致浪费。

4. 完整代码

以下是整合后的头文件与源文件示例。

SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLDataType;
#define INIT_CAPACITY 4

typedef struct SeqList {
    SLDataType* a;
    int size;
    int capacity;
} SL;

void SeqInit(SL* s);
void SeqDestroy(SL* s);
void SLCheckCapacity(SL* ps);
void SLPushBack(SL* ps, SLDataType x);
void SLPushFront(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPopFront(SL* ps);
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL* ps, SLDataType x);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

void SLPrint(SL* ps) {
    assert(ps);
    for (int i = 0; i < ps->size; ++i) {
        printf("%d ", ps->a[i]);
    }
    printf("\n");
}

void SeqInit(SL* ps) {
    assert(ps);
    ps->a = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
    if (ps->a == NULL) {
        perror("malloc fail");
        return;
    }
    ps->size = 0;
    ps->capacity = INIT_CAPACITY;
}

void SeqDestroy(SL* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->size = ps->capacity = 0;
}

void SLCheckCapacity(SL* ps) {
    assert(ps);
    if (ps->size == ps->capacity) {
        size_t newcap = ps->capacity * 2;
        SLDataType* tmp = (SLDataType*)realloc(ps->a, sizeof(SLDataType) * newcap);
        if (tmp == NULL) {
            perror("realloc fail");
            return;
        }
        ps->a = tmp;
        ps->capacity = newcap;
    }
}

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

void SLPushFront(SL* ps, SLDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= 0) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[0] = x;
    ps->size++;
}

void SLPopFront(SL* ps) {
    assert(ps && ps->size > 0);
    int begin = 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

void SLPopBack(SL* ps) {
    assert(ps && ps->size > 0);
    ps->a[ps->size - 1] = 0;
    ps->size--;
}

void SLInsert(SL* ps, int pos, SLDataType x) {
    assert(ps && pos >= 0 && pos <= ps->size);
    SLCheckCapacity(ps);
    int end = ps->size - 1;
    while (end >= pos) {
        ps->a[end + 1] = ps->a[end];
        end--;
    }
    ps->a[pos] = x;
    ps->size++;
}

void SLErase(SL* ps, int pos) {
    assert(ps && pos >= 0 && pos < ps->size);
    int begin = pos + 1;
    while (begin < ps->size) {
        ps->a[begin - 1] = ps->a[begin];
        ++begin;
    }
    ps->size--;
}

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