顺序表(C语言源码详解,附加测试代码)
目录
顺序表的基本实现
顺序表结构
顺序表的初始化
检查顺序表容量空间
顺序表的头插
顺序表的打印
顺序表的头删
顺序表的尾插
顺序表的尾删
顺序表的查找
编辑指定位置之前插入数据
指定位置删除数据
顺序表的销毁
顺序表的基本实现
顺序表结构
对顺序表的数据类型进行重命名,方便以后给顺序表进行修改数据类型
size 记录顺序表中有多少个数据
capacity 采用动态开辟空间
typedef int SLDateType;
//顺序表结构
typedef struct SeqList
{
SLDateType* arr;
int size;
int capacity;
}SL;顺序表的初始化
//顺序表的初始化
void SLInit(SL* ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}测试:
void test1()
{
SL s1;
SLInit(&s1);
}
int main()
{
test1();
return 0;
}预期结果:对顺序表s1进行初始化成功
实际结果:
检查顺序表容量空间
使用顺序表的头插前 应该先扩容,我们把扩容的代码包装了成了一个函数
判断顺序表数据的个数是否和容量相等,如果相等则 进行二倍扩容,第一次进入 分配四个空间
这段代码要添加在增加顺序表数据代码的前面,或者添加一个声明
//检查顺序表容量
void CheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity > 0 ? 4 : ps->capacity * 2;
SLDateType* tmp = (SLDateType*)realloc(ps->arr, newcapacity * sizeof(SLDateType));
if (tmp == NULL)
{
perror("realloc is fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newcapacity;
}
}
顺序表的头插
思路:让元素依次往后挪动,留下首元素的空间进行插入
先检查顺序表的容量是否够插入数据,不够则扩容,
void SLPushFront(SL* ps, SLDateType x)
{
CheckCapacity(ps);
assert(ps->arr);
for (int i = ps->size; i > 0; i--)
{
ps->arr[i] = ps->arr[i - 1];
}
ps->arr[0] = x;
ps->size++;
}测试代码:
void test1()
{
SL s1;
SLInit(&s1);
SLPushFront(&s1, 1);
SLPushFront(&s1, 2);
SLPushFront(&s1, 3);
SLPushFront(&s1, 4);
SLPushFront(&s1, 5);
SLPrint(&s1);
}
int main()
{
test1();
return 0;
}预期结果:
插入4 3 2 1 之后,进行扩容,顺序表容量翻倍,在头部添加5
5 4 3 2 1
实际结果:
顺序表的打印
//顺序表的打印
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
}
预期结果:
打印顺序表
实际结果:
如上,已经进行打印
顺序表的头删
思路:让后一个数据依次覆盖前一个数据
如果顺序表没有元素的话,要判断一下
最简单直接有效的办法就是断言一下
//顺序表的头删
void SLPopFront(SL* ps)
{
assert(ps->arr);
assert(ps->size > 0);
for (int i = 0; i < ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
} 测试代码:
void test1()
{
SL s1;
SLInit(&s1);
SLPushFront(&s1, 1);
SLPushFront(&s1, 2);
SLPushFront(&s1, 3);
SLPushFront(&s1, 4);
SLPushFront(&s1, 5);
SLPopFront(&s1);
SLPopFront(&s1);
SLPopFront(&s1);
SLPrint(&s1);
}
int main()
{
test1();
return 0;
}预期结果:
依次删除 5 4 3 输出 2 1
实际结果:
顺序表的尾插
思路:依次插入数据,每插入完一个顺序表数据,顺序表大小+1
//顺序表的尾插
void SLPushBack(SL* ps, SLDateType x)
{
CheckCapacity(ps);
assert(ps->arr);
ps->arr[ps->size] = x;
ps->size++;
}测试代码:
void test2()
{
SL s2;
SLInit(&s2);
SLPushBack(&s2, 1);
SLPushBack(&s2, 2);
SLPushBack(&s2, 3);
SLPushBack(&s2, 4);
SLPushBack(&s2, 5);
SLPrint(&s2);
}
int main()
{
test2();
return 0;
}预期结果
依次插入 1 2 3 4 5
实际结果:
顺序表的尾删
//顺序表的尾删
void SLPushBack(SL* ps)
{
assert(ps->arr);
assert(ps->size > 0);
ps->size--;
}测试代码:
void test2()
{
SL s2;
SLInit(&s2);
SLPushBack(&s2, 1);
SLPushBack(&s2, 2);
SLPushBack(&s2, 3);
SLPushBack(&s2, 4);
SLPushBack(&s2, 5);
SLPopBack(&s2);
SLPopBack(&s2);
SLPopBack(&s2);
SLPopBack(&s2);
SLPrint(&s2);
}
int main()
{
test2();
return 0;
}预期结果
依次删除5 4 3 2 输出结果为1
实际结果:
顺序表的查找
//顺序表查找
int SLFind(SL* ps, SLDateType x)
{
assert(ps->arr);
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
return -1;
}顺序表查找不到元素的情况:
测试代码:
void test2()
{
SL s2;
SLInit(&s2);
SLInsert(&s2,5,s2.size);
SLInsert(&s2,6,s2.size);
SLInsert(&s2,10,0);
SLInsert(&s2,7,s2.size);
SLInsert(&s2,8,s2.size);
SLPrint(&s2);
int ret = SLFind(&s2, 6);
printf("\n");
if (ret == -1)
printf("该顺序表无元素\n");
else
printf("找到了,该元素的位置在顺序表下标%d\n",ret);
}
int main()
{
test2();
return 0;
}预期结果:
找到了,该元素的位置下在顺序表下表2
实际结果
指定位置之前插入数据
//指定位置之前插入数据
void SLInsert(SL* ps, SLDateType x, int pos)
{
CheckCapacity(ps);
assert(ps->arr);
assert(pos >= 0 && pos <= ps->size);
for (int i = ps->size; i > pos; i--)
{
ps->arr[i] = ps->arr[i - 1];//ps->arr[1] = ps->arr[0]
}
ps->arr[pos] = x;
ps->size++;
}可以模拟头插和尾插
测试代码:
void test2()
{
SL s2;
SLInit(&s2);
SLInsert(&s2,5,s2.size);
SLInsert(&s2,6,s2.size);
SLInsert(&s2,10,0);
SLInsert(&s2,7,s2.size);
SLInsert(&s2,8,s2.size);
SLPrint(&s2);
}
int main()
{
test2();
return 0;
}
预期结果:先模拟进行尾插 插入5 6 模拟进行头插 插入10 后进行头插
输出结果为 10 5 6 7 8
实际结果:
指定位置删除数据
//指定位置删除数据
void SLErase(SL* ps, int pos)
{
assert(ps->arr);
assert(ps->size != 0);
assert(pos >= 0 && pos < ps->size);
for (int i = pos; i<ps->size-1;i++)
{
ps->arr[i] = ps->arr[i + 1];
}
ps->size--;
}测试代码:
void test2()
{
SL s2;
SLInit(&s2);
SLInsert(&s2,5,s2.size);
SLInsert(&s2,6,s2.size);
SLInsert(&s2,10,0);
SLInsert(&s2,7,s2.size);
SLInsert(&s2,8,s2.size);
SLErase(&s2, 1);
SLErase(&s2, 2);
SLErase(&s2, 0);
SLPrint(&s2);
}
int main()
{
test2();
return 0;
}预期输出
先删除下标位置为1的数据,接着删除下标为2的数据,再模拟进行头删
输出为6 8
实际输出:
顺序表的销毁
void SLDestory(SL* ps)
{
assert(ps->arr);
free(ps->arr);
ps->arr = NULL;
ps->size = ps->capacity = 0;
}个人水平不足 如果代码中有错误，可以多多在评论区指出，一定会及时修改！
谢谢大家看到这里 觉得有收获的话可以三连一下 大家一起加油！