数据结构之【顺序表实现】(c语言实现)

强烈建议看完上一期博客之后再来看这一期：

数据结构之【顺序表简介】

3.实现顺序表的增删查改

静态顺序表的缺陷较大，

所以下面展示的是动态顺序表的相关函数

3.1初始化

结构体变量创建之后，首先初始化一下才好

#define INIT_CAPACITY 10 void SLINIT(SL* ps) { assert(ps); ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY); ps->capacity = INIT_CAPACITY; ps->size = 0; }

1.传入的指针不能为空时

为了节约调试时间，断言一下

2.初始化的时候，传入的是结构体的地址

因为

传址传参，才能根据地址改变相应的值

传值传参，会导致“形参改变，实参不变”的情况

传值传参时，形参是实参的临时拷贝

3.2销毁顺序表

动态开辟部分内存

当不再使用的时候，需要程序员主动释放

void SLDestroy(SL* ps) { assert(ps); free(ps->arr); ps->capacity = 0; ps->size = 0; }

1.传入的指针不能为空时

为了节约调试时间，断言一下

2.销毁的时候，传入的是结构体的地址

因为

传址传参，才能根据地址改变相应的值

传值传参，会导致“形参改变，实参不变”的情况

传值传参时，形参是实参的临时拷贝

3.3打印顺序表

编写这个函数之后

有利于我们调试自己的程序

void SLPrint(SL* ps) { assert(ps); //每个数据元素之后有空格 for (int i = 0; i < ps->size; ++i) { printf("%d ", ps->arr[i]); } //打印完一行就换行 print("\n"); }

(1)打印的时候，传入的是结构体的地址

因为

尽管传值与传址传参都可以实现打印的功能

但是传值传参会拷贝结构体的内容

如果结构体太大，可能会导致栈溢出等现象

而传址传参则不会有这种可能

(2)传入的指针不能为空时

为了节约调试时间，断言一下

3.4顺序表扩容

当有效数据个数与空间容量相等的时候

就可以考虑扩容了

void CheckCapacity(SL* ps) { assert(ps); if (ps->capacity == ps->size) { ps->capacity *= 2; SLDataType* temp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * (ps->capacity)); if (temp == NULL) return; ps->arr = temp; } }

(1).扩容的时候，传入的是结构体的地址

因为

传址传参，才能根据地址改变相应的值

传值传参，会导致“形参改变，实参不变”的情况

传值传参时，形参是实参的临时拷贝

 (2).传入的指针不能为空时

为了节约调试时间，断言一下

(3).realloc 扩容可能会出现 异地扩容 的情况

所以需要将扩容成功的新指针temp赋值给结构体中的指针arr

(4)扩容时，一般扩充到原来的两倍就可以了

3.5增删查改 之【头插】

头插的意思就是将数据插入到顺序表的最前面

void PushFront(SL* ps, SLDataType x) { //检查是否为空 assert(ps); //检查是否需要扩容 CheckCapacity(ps); //实现头插 int end = ps->size - 1; while (end >= 0) { (ps->arr)[end + 1] = (ps->arr)[end]; end--; } (ps->arr)[0] = x; (ps->size)++; }

(1)头插的时候，传入的是结构体的地址

因为

传址传参，才能根据地址改变相应的值

传值传参，会导致“形参改变，实参不变”的情况

传值传参时，形参是实参的临时拷贝

(2)传入的指针不能为空时

为了节约调试时间，断言一下

(3)为了防止越界访问，即空间不够的情况

先检查空间容量

(4)从后往前遍历整个数组，

将数据从前往后移动一个单元

这样就可以空出 头 的位置

(5)注意有效数据个数要改变

3.6增删查改 之【头删】

头删的意思就是将顺序表最前面的数据删除

void PopFront(SL* ps) { //检查为空 assert(ps); //检查有效数据个数 assert(ps->size > 0); //实现头删 int begin = 1; while (begin < ps->size) { (ps->arr)[begin - 1] = (ps->arr)[begin]; ++begin; } (ps->size)--; }

(1)头删的时候，传入的是结构体的地址

因为

传址传参，才能根据地址改变相应的值

传值传参，会导致“形参改变，实参不变”的情况

传值传参时，形参是实参的临时拷贝

(2) 传入的指针不能为空时

为了节约调试时间，断言一下

(3) 顺序表中必须要有数据

即 ps->size > 0 时

才能进行删除操作

不然会出现未定义行为

(4) 从前往后遍历整个数组，

将数据从后往前移动一个单元

(5) 注意有效数据个数要改变

 3.7增删查改 之【尾插】

尾插的意思就是将数据插入到顺序表的最后面

void PushBack(SL* ps, SLDataType x) { //检查是否为空 assert(ps); //检查是否需要扩容 CheckCapacity(ps); //实现尾插 (ps->arr)[ps->size] = x; (ps->size)++; }

(1)有效数据个数 ps->size 正好是顺序表最后面的下标

(2)注意)有效数据个数变化

3.8增删查改 之【尾删】

尾删的意思就是将顺序表最后面的数据删除

void PopBack(SL* ps) { //检查为空 assert(ps); //检查有效数据个数 assert(ps->size > 0); //实现尾删 (ps->size)--; }

(1)让有效数据个数直接减一即可

直接不访问就好了

有效数据个数为0，插入N个数据时，

头插的时间复杂度:O(N^2)

尾插的时间复杂度:O(N)

有效数据个数为N，删除N个数据时，

头删的时间复杂度:O(N^2)

尾删的时间复杂度:O(1)

 3.9增删查改 之【有效范围内插入】

有效范围内插入的意思就是将数据插入到顺序表当中

0<= 下标 <= (ps->size)

这样，

头插尾插也包含在内了

void Insert(SL* ps, int pos, SLDataType x) { //检查是否为空 assert(ps); //检查下标位置 assert(pos >= 0 && pos <= ps->size); //检查是否需要扩容 CheckCapacity(ps); //实现插入 int end = ps->size - 1; while (end >= pos) { (ps->arr)[end + 1] = (ps->arr)[end]; --end; } (ps->arr)[pos] = x; (ps->size)++; }

(1)从后往前遍历，实现移动即可

 3.10增删查改 之【有效范围内删除】

有效范围内删除的意思就是将顺序表当中的数据删除

0<= 下标 <= (ps->size - 1)

这样，

头删尾删也包含在内了

void Erase(SL* ps, int pos) { //检查为空 assert(ps); //检查下标位置 assert(pos >= 0 && pos < ps->size); //实现删除 int begin = pos + 1; while (begin < ps->size) { ps->arr[begin - 1] = ps->arr[begin]; ++begin; } ps->size--; }

(1)注意下标位置的范围

(2)从前向后遍历，从后向前移动

 这样，你只需要写

Insert 和 Erase 两个函数

就可以实现头删尾删头插尾插等了

 3.11增删查改 之【有效范围内查找】

 有效范围内查找的意思就是在顺序表当中查找想要的值

没有技巧可言，直接暴力查找就好

int Find(SL* ps, SLDataType x) { for (int i = 0; i < ps->size; ++i) { if (ps->arr[i] == x) return i; } return -1; }