顺序表是线性表的一种数组实现,逻辑上元素连续排列,物理上也是连续存储。相比链表,它支持随机访问,但中间插入删除需要移动数据。下面直接动手写一个动态扩容的顺序表。
结构定义
静态顺序表用定长数组,容量写死,灵活性太差,实际很少用。这里采用动态数组方案,结构体里放指针、当前元素个数和容量。初始容量设为4,方便观察扩容。
typedef int SLDataType;
#define INIT_CAPACITY 4
typedef struct SeqList {
SLDataType* a;
int size;
int capacity;
} SL;
基本操作
初始化时分配初始内存,销毁时释放并置空。容量检查采用2倍扩容,realloc 可能失败,这里简单打印错误并返回,生产环境需要更健壮的处理。
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;
}
}


