数据结构-顺序表
目录
数据结构–顺序表
1.定义
顺序表是线性表的一种存储结构，用一组地址连续的存储单元依次存储线性表的数据元素。它把逻辑上相邻的数据元素存储在物理位置上也相邻的存储单元中，元素之间的逻辑关系由存储单元的邻接关系来体现。
2.基本操作
- 容量检查和扩容 ：SeqListCheckCapacity 会检查顺序表是否已满，若满则进行扩容操作，扩容策略是初始容量为 4，后续每次扩容为原来的 2 倍。
- 插入和删除操作 ：支持头插（SeqListPushFront）、尾插（SeqListPushBack）、头删（SeqListPopFront）、尾删（SeqListPopBack），以及在指定位置插入（SeqListInsert）和删除元素（SeqListErase）。
- 查找和修改操作 ：SeqListFind 用于查找指定元素的位置，SeqListModity 用于修改指定位置的元素值。
- 打印操作 ：SeqListPrint 用于打印顺序表中的所有元素。
3.代码实现
3.1初始化
void SeqListInit(SL* ps)
{
ps->a = NULL;
ps->size = 0;
ps->capacity = 0;
}3.2销毁顺序表
void SeqListDestory(SL* ps)
{
free(ps->a);
ps->a = NULL;
ps->capacity = ps->size = 0;
}3.3检查空间(扩容）
void SeqListCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
if (tmp == NULL)
{
printf("realloc fail\n");
exit(-1);
}
else
{
ps->a = tmp;
ps->capacity = newcapacity;
}
}
}3.4打印顺序表
void SeqListPrint(SL* ps)
{
for (int i = 0; i < ps->size; ++i)
{
printf("%d ", ps->a[i]);
}
printf("\n");
}3.5尾插
void SeqListPushBack(SL* ps, SQDataType x)
{
SeqListCheckCapacity(ps);
ps->a[ps->size] = x;
ps->size++;
}3.6头插
void SeqListPushFront(SL* ps, SQDataType x)
{
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= 0)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[0] = x;
ps->size++;
}3.7头删
void SeqListPopFront(SL* ps)
{
assert(ps->size > 0);
int start = 1;
while (start < ps->size)
{
ps->a[start - 1] = ps->a[start];
++start;
}
ps->size--;
}3.8 尾删
void SeqListPopBack(SL* ps)
{
assert(ps->size > 0);
ps->a[ps->size - 1] = 0;
ps->size--;
}3.9任意位置插入
void SeqListInsert(SL* ps, int pos, SQDataType x)
{
assert(pos <= ps->size);
SeqListCheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
{
ps->a[end + 1] = ps->a[end];
--end;
}
ps->a[pos] = x;
ps->size++;
}3.10在任意位置删除
void SeqListErase(SL* ps, int pos)
{
assert(pos < ps->size);
int start = pos + 1;
while (start < ps->size)
{
ps->a[start-1] = ps->a[start];
++start;
}
ps->size--;
}3.11查找数据所在位置
int SeqListFind(SL* ps, SQDataType x)
{
for (int i = 0; i < ps->size; ++i)
{
if (ps->a[i] == x)
{
return i;
}
}
return -1;
}3.12在任意位置修改数据
void SeqListModity(SL* ps, int pos, SQDataType x)
{
assert(pos < ps->size);
ps->a[pos] = x;
}