数据布局 之 【顺序表实现】(c语言实现)

剧烈发起看完上一期博客之后再来看这一期：
  数据布局之【顺序表简介】
  3.实现顺序表的增删查改

   静态顺序表的缺陷较大，
  所以下面展示的是动态顺序表的相关函数
  3.1初始化

   布局体变量创建之后，起首初始化一下才好

1. #define INIT_CAPACITY 10
2. void SLINIT(SL* ps)
3. {
4.     assert(ps);
6.         ps->arr = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);
7.         ps->capacity = INIT_CAPACITY;
8.         ps->size = 0;
9. }

复制代码

  1.传入的指针不能为空时
  为了节约调试时间，断言一下
  2.初始化的时候，传入的是布局体的地点
  由于
  传址传参，才气根据地点改变相应的值
  传值传参，会导致“形参改变，实参稳定”的情况
  传值传参时，形参是实参的临时拷贝
  3.2烧毁顺序表

   动态开发部分内存
  当不再利用的时候，需要程序员自动释放

1. void SLDestroy(SL* ps)
2. {
3.     assert(ps);
4.         free(ps->arr);
5.         ps->capacity = 0;
6.         ps->size = 0;
7. }

复制代码

  1.传入的指针不能为空时
  为了节约调试时间，断言一下
  2.烧毁的时候，传入的是布局体的地点
  由于
  传址传参，才气根据地点改变相应的值
  传值传参，会导致“形参改变，实参稳定”的情况
  传值传参时，形参是实参的临时拷贝
  3.3打印顺序表

   编写这个函数之后
  有利于我们调试自己的程序

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

复制代码

  (1)打印的时候，传入的是布局体的地点
  由于
  只管传值与传址传参都可以实现打印的功能
  但是传值传参会拷贝布局体的内容
  如果布局体太大，可能会导致栈溢出等现象
  而传址传参则不会有这种可能
  (2)传入的指针不能为空时
  为了节约调试时间，断言一下
  3.4顺序表扩容

   当有效数据个数与空间容量相等的时候
  就可以考虑扩容了

1. void CheckCapacity(SL* ps)
2. {
3.         assert(ps);
5.         if (ps->capacity == ps->size)
6.         {
7.                 ps->capacity *= 2;
8.                 SLDataType* temp = (SLDataType*)realloc(ps->arr, sizeof(SLDataType) * (ps->capacity));
10.                 if (temp == NULL)
11.                         return;
13.                 ps->arr = temp;
14.         }
15. }

复制代码

  (1).扩容的时候，传入的是布局体的地点
  由于
  传址传参，才气根据地点改变相应的值
  传值传参，会导致“形参改变，实参稳定”的情况
  传值传参时，形参是实参的临时拷贝
   (2).传入的指针不能为空时
  为了节约调试时间，断言一下
  (3).realloc 扩容可能会出现 异地扩容 的情况
  所以需要将扩容乐成的新指针temp赋值给布局体中的指针arr
  (4)扩容时，一般扩充到原来的两倍就可以了
  3.5增删查改 之【头插】

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

1. void PushFront(SL* ps, SLDataType x)
2. {
3.         //检查是否为空
4.         assert(ps);
5.         //检查是否需要扩容
6.         CheckCapacity(ps);
7.         //实现头插
8.         int end = ps->size - 1;
9.         while (end >= 0)
10.         {
11.                 (ps->arr)[end + 1] = (ps->arr)[end];
12.                 end--;
13.         }
14.         (ps->arr)[0] = x;
15.         (ps->size)++;
16. }

复制代码

  (1)头插的时候，传入的是布局体的地点
  由于
  传址传参，才气根据地点改变相应的值
  传值传参，会导致“形参改变，实参稳定”的情况
  传值传参时，形参是实参的临时拷贝
  (2)传入的指针不能为空时
  为了节约调试时间，断言一下
  (3)为了防止越界访问，即空间不够的情况
  先检查空间容量
  (4)从后往前遍历整个数组，
  将数据从前往后移动一个单元
  如许就可以空出 头 的位置
  (5)注意有效数据个数要改变
  3.6增删查改 之【头删】

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

1. void PopFront(SL* ps)
2. {
3.         //检查为空
4.         assert(ps);
5.         //检查有效数据个数
6.         assert(ps->size > 0);
7.         //实现头删
8.         int begin = 1;
9.         while (begin < ps->size)
10.         {
11.                 (ps->arr)[begin - 1] = (ps->arr)[begin];
12.                 ++begin;
13.         }
14.         (ps->size)--;
15. }

复制代码

  (1)头删的时候，传入的是布局体的地点
  由于
  传址传参，才气根据地点改变相应的值
  传值传参，会导致“形参改变，实参稳定”的情况
  传值传参时，形参是实参的临时拷贝
  (2) 传入的指针不能为空时
  为了节约调试时间，断言一下
  (3) 顺序表中必须要有数据
  即 ps->size > 0 时
  才气举行删除操作
  不然会出现未界说行为
  (4) 从前往后遍历整个数组，
  将数据从后往前移动一个单元
  (5) 注意有效数据个数要改变
   3.7增删查改 之【尾插】

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

1. void PushBack(SL* ps, SLDataType x)
2. {
3.         //检查是否为空
4.         assert(ps);
5.         //检查是否需要扩容
6.         CheckCapacity(ps);
7.         //实现尾插
8.         (ps->arr)[ps->size] = x;
9.         (ps->size)++;
10. }

复制代码

  (1)有效数据个数 ps->size 正好是顺序表最反面的下标
  (2)注意)有效数据个数变化
  3.8增删查改 之【尾删】

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

1. void PopBack(SL* ps)
2. {
3.         //检查为空
4.         assert(ps);
5.         //检查有效数据个数
6.         assert(ps->size > 0);
7.         //实现尾删
8.         (ps->size)--;
9. }

复制代码

  (1)让有效数据个数直接减一即可
  直接不访问就好了
    有效数据个数为0，插入N个数据时，
  头插的时间复杂度:O(N^2)
  尾插的时间复杂度:O(N)
  有效数据个数为N，删除N个数据时，
  头删的时间复杂度:O(N^2)
  尾删的时间复杂度:O(1)
   3.9增删查改 之【有效范围内插入】

   有效范围内插入的意思就是将数据插入到顺序表当中
  0<= 下标 <= (ps->size)
  如许，
  头插尾插也包罗在内了

1. void Insert(SL* ps, int pos, SLDataType x)
2. {
3.         //检查是否为空
4.         assert(ps);
5.         //检查下标位置
6.         assert(pos >= 0 && pos <= ps->size);
7.         //检查是否需要扩容
8.         CheckCapacity(ps);
9.         //实现插入
10.         int end = ps->size - 1;
11.         while (end >= pos)
12.         {
13.                 (ps->arr)[end + 1] = (ps->arr)[end];
14.                 --end;
15.         }
16.         (ps->arr)[pos] = x;
17.         (ps->size)++;
18. }

复制代码

  (1)从后往前遍历，实现移动即可
   3.10增删查改 之【有效范围内删除】

   有效范围内删除的意思就是将顺序表当中的数据删除
  0<= 下标 <= (ps->size - 1)
  如许，
  头删尾删也包罗在内了

1. void Erase(SL* ps, int pos)
2. {
3.         //检查为空
4.         assert(ps);
5.         //检查下标位置
6.         assert(pos >= 0 && pos < ps->size);
7.         //实现删除
8.         int begin = pos + 1;
9.         while (begin < ps->size)
10.         {
11.                 ps->arr[begin - 1] = ps->arr[begin];
12.                 ++begin;
13.         }
14.         ps->size--;
15. }

复制代码

  (1)注意下标位置的范围
  (2)从前向后遍历，从后向前移动
     如许，你只需要写
  Insert 和 Erase 两个函数
  就可以实现头删尾删头插尾插等了
   3.11增删查改 之【有效范围内查找】
    有效范围内查找的意思就是在顺序表当中查找想要的值
    没有本事可言，直接暴力查找就好

1. int Find(SL* ps, SLDataType x)
2. {
3.         for (int i = 0; i < ps->size; ++i)
4.         {
5.                 if (ps->arr[i] == x)
6.                         return i;
7.         }
8.         return -1;
9. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。