文章目录
- 前言
- 1.准备工作
- 2.代码的实现
- 2.1.顺序表的创建、销毁和打印
- 2.2.顺序表的扩容、头插\删、尾插\删
- 2.2.1.扩容
- 2.2.2.尾插
- 2.2.3.头插
- 2.2.3.尾删
- 2.2.4.头删
- 2.3.指定位置之前插入/删除数据/查找数据
- 2.3.1.指定位置之前插入数据
- 2.3.2.指定位置之前删除数据
- 2.3.3.查找特定数据
- 总结
前言
上一篇,我们认识到了顺序表,以及实现顺序表操作的相关函数,下面我们来一一实现。
1.准备工作
示例:
打开vs2022,创建三个文件
其中SeqList.h头文件是用来记录的,相当于一本书的目录
SeqList.c文件是用来实现函数的,相当于各种公式
test.c是用来测试的。
记住:一个好的习惯是,写完一个函数,要测试一个函数。
2.代码的实现
2.1.顺序表的创建、销毁和打印
//初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//销毁
void SLDestroy(SL* ps)
{
if (ps->arr)
{
free(ps->arr);
}
ps->capacity = ps->size = 0;
}
//打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
这个代码较为简单。
思考:为什么向函数中传递形参时,是用指针,如果不是指针,会发生什么,大家可以试试。
2.2.顺序表的扩容、头插\删、尾插\删
2.2.1.扩容
//扩容
void SLCheckCapacity(SL* ps)
{
if (ps->capacity == ps->size)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
SeqDataType* tmp = (SeqDataType*)realloc(ps->arr,sizeof(SeqDataType) * newCapacity);
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->capacity = newCapacity;
ps->arr = tmp;
}
}
2.2.2.尾插
void SLPushBack(SL* ps, SeqDataType x)
{
assert(ps);
//要判断arr空间是否充足
SLCheckCapacity(ps);
ps->arr[ps->size++] = x;
}
2.2.3.头插
void SLPushFront(SL* ps, SeqDataType x)
{
assert(ps);
SLCheckCapacity(ps);
//要将原来数组的每一个数,移动到前面
for (int i = ps->size; i>0; i--)
{
ps->arr[i] = ps->arr[i - 1];//arr[1]=arr[0]
}
ps->arr[0] = x;
ps->size++;
}
2.2.3.尾删
尾删可能是最简单的,但是可能第一次想象不到,只需要size–即可,在输出的结果上一看,便是少了一个,并且也是最后一个。
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->arr);//删着删着,最后要是顺序表为空,要报警
ps->size--;
}
2.2.4.头删
void SLPopFront(SL* ps)
{
assert(ps && ps->arr);
//删除第一个数字后,将后面的数字,移动到前面
for (int i=0; i<ps->size-1; i++)
{
ps->arr[i] = ps->arr[i+1];//arr[size-2]=arr[size-1]
}
ps->size--;
}
2.3.指定位置之前插入/删除数据/查找数据
2.3.1.指定位置之前插入数据
void SLInsert(SL* ps, int pos, SeqDataType x)
{
assert(ps && ps->arr);
assert(pos >= 0 && pos < ps->size);
SLCheckCapacity(ps);
for (int i = ps->size; i>pos; i--)
{
ps->arr[i] = ps->arr[i-1];
}
ps->arr[pos] = x;
ps->size++;
}
assert(pos >= 0 && pos < ps->size);为什么不是<=呢,是因为咱们得目的是让数据插入到指定位置之前,如果传入的位置是ps->size的话,最后的代码将会是在ps->size之后插入的,不符合需要的功能,所以是<
2.3.2.指定位置之前删除数据
void SLErase(SL* ps, int pos)
{
assert(ps->arr && ps);
assert(pos > 0 && pos <= ps->size);
for (int i = 0; i <=pos; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}
2.3.3.查找特定数据
int SLFind(SL* ps, SeqDataType x)
{
for (int i = 0; i < ps->size; i++)
if (ps->arr[i] == x)
return i;
return -1;
}
总结
上面便是顺序表的常见的操作,大家可以根据代码,自己理解,并掌握。