顺序表的操作

顺序表的建立

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

为了方便进行数据类型的修改，将数据类型进行typedef的重命名，使得代码在需要修改数据类型时只需要修改第一行的代码即可，无需将每个数据的数据类型进行修改

顺序表的初始化

void SLInit(SL* ps)
{
ps->a = NULL;
ps->size = ps->capacity = 4;
}

将size和capacity赋值为4是为了方便后续的扩容环节

顺序表的销毁

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

注意free后需要将a置空，避免出现野指针

顺序表的尾插

void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));
if (tmp == NULL)
{
perror("errno\n");
}
ps->a = tmp;
ps->capacity *= 2;
}
ps->a[ps->size] = x;
ps->size++;
}

头插分为两种情况：

1. 空间足够，直接插入数据（插入数据时记得将size++）
2. 空间不够，进行扩容后再插入数据（扩容时需要注意判断，空间开辟是否成功）

顺序表的头插

void SLPushFront(SL* ps, SLDataType x)
{
assert(ps);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));
if (tmp == NULL)
{
perror("errno\n");
}
ps->a = tmp;
ps->capacity *= 2;
}
for (int i = ps->size; i > 0; i--)
{
ps->a[i] = ps->a[i - 1];
}
ps->a[0] = x;
ps->size++;
}

与尾插类似，同样要分为两种情况

1. 空间足够，直接插入数据（插入数据时，需要将数据从后往前进行后移一位的操作，使第一个位置空出来，方便数据的插入）
2. 空间不够，进行扩容后再插入数据（记得将顺序表的size++）

顺序表的头删

bool SLIsEmpty(SL* ps)
{
assert(ps);
return ps->size == 0;
}
void SLPopFront(SL* ps)
{
assert(ps);
assert(SLIsEmpty(ps));
for (size_t i = 0; i < ps->size-1; i++)
{
ps->a[i] = ps->a[i+1];
}
ps->size--;
}

1. 判断顺序表不为空
2. 将数据从前往后进行遍历，将除第一个数据外的所有数据往前移一位
3. 记得将顺序表的size–

顺序表的尾删

bool SLIsEmpty(SL* ps)
{
assert(ps);
return ps->size == 0;
}
void SLPopBack(SL* ps)
{
assert(ps);
assert(SLIsEmpty(ps));
ps->size--;
}

1. 判断顺序表不为空
2. 直接将size–，size–后，下一次的插入直接会将上一个待删的数据进行覆盖，所以不需要将数据进行其他的操作

在顺序表指定位置前插入数据

void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(ps);
assert(pos >= 0 && pos <= ps->size);
if (ps->size == ps->capacity)
{
SLDataType* tmp = (SLDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(SLDataType));
if (tmp == NULL)
{
perror("errno\n");
}
ps->a = tmp;
ps->capacity *= 2;
}
for (int i = ps->size; i > pos; i--)
{
ps->a[i] = ps->a[i-1];
}
ps->a[pos] = x;
ps->size++;
}

1. 判断pos是否在顺序表的范围内
2. 若空间不够时进行扩容，若足够，则将pos及以后的数据按从后往前的顺序进行后移一位的操作
3. 最后将数据插入到pos的位置上，将顺序表的size++

该操作包含了上述头插和尾插的操作

删除顺序表的指定数据

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

1. 判断顺序表是否为空
2. 将待删除数据以后的数据，按从前往后的顺序向前移动一位，从而将待删除数据进行覆盖，从而带到删除的目的
3. 记得将顺序表的size–

该操作包含了上述头删和尾删的操作

查找指定数据是否在顺序表中

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

从前往后遍历顺序表，若数据为待查找数据，则返回true，否则返回false

原文地址：https://blog.csdn.net/2302_79180171/article/details/140329137

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！