ToB企服应用市场:ToB评测及商务社交产业平台

标题: 数据布局 之 【顺序表实现】(c语言实现) [打印本页]
作者: 天空闲话    时间: 3 天前
标题: 数据布局 之 【顺序表实现】(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企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4