devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C语言数据结构】顺序表详解（动态版本）_详解动态顺序表

作者：繁依Fanyi0 | 2024-04-28 06:39:20

赞

踩

详解动态顺序表
作者：热爱编程的小y
专栏：C语言数据结构
格言：能打败你的只能是明天的你

一、概念

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表是线性表的一种，他的孪生兄弟是链表。

二、结构

顺序表一般可以分为：

  1. 静态顺序表

使用定长数组存储元素。

  1. 动态顺序表

使用动态开辟的数组存储。

三、接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。所以现实中基本都是使用动态顺序表，根据需要动态地分配空间大小，所以下面我们实现动态顺序表。

（一）准备工作

1.创立文件

我们需要创立三个文件，分别是SeqList.c，SeqList.h，Test.c。

SeqList.h 内包含引用的头文件，函数的声明，结构体的声明，宏的声明与定义。

SeqList.c 内包含函数的主体，增删查改的具体过程在这里实现。

Test.c 负责对各项功能的测试与具体运用。

2.函数与结构体的定义

我们需要定义一个结构体类型用于数据的存放，结构体内需要包含三个参数，分别是一个指针，一个表示当前已存放的数据个数的整形，一个表示当前最多存放的数据个数的整形。因为我们不仅需要把数据存放进去，还要知道它的存放位置便于后续的更改，第三个参数则是确保开辟的空间大小在一个合理的范围内。具体如下。

  1.  
  2. typedef struct SeqList
  3. {
  4.     SLDateType* a;//存放数据的地址
  5.     int size;//当前已存放的数据个数
  6.     int capacity;//当前最多存放的数据个数
  7. }SeqList;

因为我们并不能确定存放数据的类型是什么，所以我们需要重新命名一个类型，就像这样。

  1.  
  2. typedef int SLDateType;//想修改顺序表内数据的类型可以直接在这修改

之后不论是想存放什么类型的数据，只要在这里修改一遍就可以了。

我们还需要定义各种函数来分别实现各种功能，功能就不一一介绍了，具体如下。

  1.  
  2. // 对数据的管理:增删查改 
  3. //初始化
  4. void SeqListInit(SeqList* ps);
  5.  
  6. //销毁
  7. void SeqListDestroy(SeqList* ps);
  8.  
  9. //显示(打印)
  10. void SeqListPrint(SeqList* ps);
  11.  
  12. //尾插
  13. void SeqListPushBack(SeqList* ps, SLDateType x);
  14.  
  15. //头插
  16. void SeqListPushFront(SeqList* ps, SLDateType x);
  17.  
  18. //头删
  19. void SeqListPopFront(SeqList* ps);
  20.  
  21. //尾删
  22. void SeqListPopBack(SeqList* ps);
  23.  
  24. // 顺序表查找
  25. void SeqListFind(SeqList* ps, SLDateType x);
  26.  
  27. // 顺序表在pos位置插入x
  28. void SeqListInsert(SeqList* ps, int pos, SLDateType x);
  29.  
  30. // 顺序表删除pos位置的值
  31. void SeqListErase(SeqList* ps, int pos);

（二）功能实现

  1. 初始化与销毁

我们先给定一个内存大小初始值，按照这个初始值通过malloc或者calloc函数给参数ps->a开辟空间，

#define INIT_CAPACITY 4

我们将初始值定义成一个宏，方便随时修改。

空间有开辟失败的可能性（虽然可能性很小很小就是了），因此还要对其进行排除。

销毁顺序表的时候我们用free函数来释放掉里面的空间，并顺带把原先指向存放数据地址的指针赋为空，避免其成为野指针。

  1.  
  2. //初始化
  3. void SeqListInit(SeqList* ps)
  4. {
  5.     ps->a = (SLDateType*)malloc(INIT_CAPACITY * sizeof(SLDateType));
  6.     if (NULL == ps->a)
  7.     {
  8.         perror("SeqListInit::calloc");
  9.         return;
  10.     }
  11.     ps->size = 0;
  12.     ps->capacity = INIT_CAPACITY;
  13.     return;
  14. }
  15.  
  16. //销毁
  17. void SeqListDestroy(SeqList* ps)
  18. {
  19.     free(ps->a);
  20.     ps->a = NULL;
  21.     ps->capacity = ps->size = 0;
  22.     return;
  23. }

  1. 头插与尾插

先说明一下，头插就是在顺序表的开头插入数据，尾插则是在顺序的末尾插入数据。

我们进行头插操作时，因为不能直接硬插，而是要先腾出空间才能插入，而且不能打乱后面数据的顺序，所以我们需要把所有数据由末向前依次往后挪一个位置。结束之后要记得让size+1。

相比头插，尾插就方便多了，我们可以直接插入数据，因为size的值不仅是已有数据的个数也是我们插入的下一个数据的地址。

不管是头插还是尾插，我们都需要先进行一个判断是否扩容的操作，判断条件很简单，只需要判断size与capacity就是已有数据的个数与最大空间是否相等了即可。与开辟空间一样，扩容也存在失败的可能性，也需要进行排除。

  1.  
  2. //尾插
  3. void SeqListPushBack(SeqList* ps, SLDateType x)
  4. {
  5.     /*增容*/
  6.     if (ps->size == ps->capacity)
  7.     {
  8.         SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType)*ps->capacity * 2);
  9.         /*增容失败*/
  10.         if (tmp == NULL)
  11.         {
  12.             perror("SeqListPushFront::realloc");
  13.             return;
  14.         }
  15.         /*增容成功*/
  16.         ps->a = tmp;
  17.         ps->capacity *= 2;
  18.     }
  19.     ps->a[ps->size++] = x;
  20.     return;
  21. }
  22.  
  23. //头插
  24. void SeqListPushFront(SeqList* ps, SLDateType x)
  25. {
  26.     /*扩容*/
  27.     if (ps->size == ps->capacity || ps->size + 1 == ps->capacity)
  28.     {
  29.         SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
  30.         /*增容失败*/
  31.         if (tmp == NULL)
  32.         {
  33.             perror("SeqListPushFront::realloc");
  34.             return;
  35.         }
  36.         /*增容成功*/
  37.         ps->a = tmp;
  38.         ps->capacity *= 2;
  39.     }
  40.     int i = 0;
  41.     for (i = ps->size; i>0; i -- )
  42.     {
  43.         ps->a[i] = ps->a[i - 1];
  44.     }
  45.     ps->a[0] = x;
  46.     ps->size++;
  47.     return;
  48. }

  1. 头删与尾删

在进行头删操作的时候，我们就不需要像头插一样考虑空间的问题了，我们只需要对头部数据进行重新赋值，效果就等同于删除了。因此我们需要从第二个数据开始，赋值给它的前一个数据，依次向后推，直到最后一个数据也完成对前一个数据的赋值为之。

尾插则更简单了，只需要让控制顺序表数据个数的size-1即可。

注意：在进行上述删除操作之前，都需要对size的值进行一个判断，当它为0时理应终止删除，即让size停止自减操作，否则size有可能减成负数，而导致后续插入操作出现问题。

  1.  
  2. //尾删
  3. void SeqListPopBack(SeqList* ps)
  4. {
  5.     if (0 == ps->size)
  6.         return;
  7.     ps->size--;
  8. }
  9.  
  10. //头删
  11. void SeqListPopFront(SeqList* ps)
  12. {
  13.     if (0 == ps->size)
  14.         return;
  15.     int i = 0;
  16.     for (i = 0; i < ps->size - 1; i++)
  17.     {
  18.         ps->a[i] = ps->a[i + 1];
  19.     }
  20.     ps->size--;
  21.     return;
  22. }

  1. 在指定位置插入与删除

不同于尾插尾删，要想在指定位置进行数据的插入与删除，需要考虑后面数据的影响，因此它与头插头删类似，只不过起始地址不同罢了。

类似于头插，在指定位置插入时，也要把后续数据不变顺序地向后挪一个空间，再把新数据插入到空出来的那个空间当中

类似于头删，我们只需要从指定位置的后一个数据开始，向前赋值，依次往后直到最后一个数据。

  1.  
  2. //在pos位置插入x
  3. void SeqListInsert(SeqList* ps, int pos, SLDateType x)
  4. {
  5.     /*扩容*/
  6.     if (ps->size == ps->capacity || ps->size + 1 == ps->capacity)
  7.     {
  8.         SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
  9.         /*增容失败*/
  10.         if (tmp == NULL)
  11.         {
  12.             perror("SeqListPushFront::realloc");
  13.             return;
  14.         }
  15.         /*增容成功*/
  16.         ps->a = tmp;
  17.         ps->capacity *= 2;
  18.     }
  19.     int i = 0;
  20.     for (i = ps->size; i > pos; i--)
  21.     {
  22.         ps->a[i] = ps->a[i - 1];
  23.     }
  24.     ps->a[pos] = x;
  25.     ps->size++;
  26.     return;
  27. }
  28.  
  29. //删除pos位置的值
  30. void SeqListErase(SeqList* ps, int pos)
  31. {
  32.     if (0 == ps->size)
  33.         return;
  34.     if (pos > ps->size-1)
  35.         return;
  36.     int i = 0;
  37.     for (i = pos; i < ps->size-1; i++)
  38.     {
  39.         ps->a[i] = ps->a[i + 1];
  40.     }
  41.     ps->size--;
  42.     return 0;
  43. }

  1. 数据的显示与查找

显示与查找操作比较简单，都只用直接打印出来即可，就不过多介绍了，直接看代码。

  1.  
  2. //显示(打印)
  3. void SeqListPrint(SeqList* ps)
  4. {
  5.     for (int i = 0; i < ps->size; i++)
  6.     {
  7.         printf("%d ", ps->a[i]);
  8.     }
  9.     printf("\n");
  10.     return;
  11. }
  12.  
  13. //查找
  14. void SeqListFind(SeqList* ps, SLDateType x)
  15. {
  16.     int i = 0, flag = 0;
  17.     for (i = 0; i < ps->size; i++)
  18.     {
  19.         if (x == ps->a[i])
  20.         {
  21.             printf("找到了，下标是：%d\n", i);
  22.             flag++;
  23.         }
  24.     }
  25.     if (flag == 0)
  26.         printf("没找到\n");
  27.     return;
  28. }

四、代码呈现

最后附上完整代码：

  1.  
  2. SeqList.h部分
  3. #pragma once
  4. #include <stdio.h>
  5. #include <assert.h>
  6. #include <stdlib.h>
  7. #define INIT_CAPACITY 4
  8.  
  9. typedef int SLDateType;//想修改顺序表内数据的类型可以直接在这修改
  10. typedef struct SeqList
  11. {
  12.     SLDateType* a;//存放数据的地址
  13.     int size;//当前已存放的数据个数
  14.     int capacity;//当前最多存放的数据个数
  15. }SeqList;
  16.  
  17. // 对数据的管理:增删查改 
  18. //初始化
  19. void SeqListInit(SeqList* ps);
  20.  
  21. //销毁
  22. void SeqListDestroy(SeqList* ps);
  23.  
  24. //显示(打印)
  25. void SeqListPrint(SeqList* ps);
  26.  
  27. //尾插
  28. void SeqListPushBack(SeqList* ps, SLDateType x);
  29.  
  30. //头插
  31. void SeqListPushFront(SeqList* ps, SLDateType x);
  32.  
  33. //头删
  34. void SeqListPopFront(SeqList* ps);
  35.  
  36. //尾删
  37. void SeqListPopBack(SeqList* ps);
  38.  
  39. // 顺序表查找
  40. void SeqListFind(SeqList* ps, SLDateType x);
  41.  
  42. // 顺序表在pos位置插入x
  43. void SeqListInsert(SeqList* ps, int pos, SLDateType x);
  44.  
  45. // 顺序表删除pos位置的值
  46. void SeqListErase(SeqList* ps, int pos);
  1.  
  2. SeqList.c部分
  3. #pragma once
  4. #include"SeqList.h"
  5.  
  6. //初始化
  7. void SeqListInit(SeqList* ps)
  8. {
  9.     ps->a = (SLDateType*)malloc(INIT_CAPACITY * sizeof(SLDateType));
  10.     if (NULL == ps->a)
  11.     {
  12.         perror("SeqListInit::calloc");
  13.         return;
  14.     }
  15.     ps->size = 0;
  16.     ps->capacity = INIT_CAPACITY;
  17.     return;
  18. }
  19.  
  20. //销毁
  21. void SeqListDestroy(SeqList* ps)
  22. {
  23.     free(ps->a);
  24.     ps->a = NULL;
  25.     ps->capacity = ps->size = 0;
  26.     return;
  27. }
  28.  
  29. //显示(打印)
  30. void SeqListPrint(SeqList* ps)
  31. {
  32.     for (int i = 0; i < ps->size; i++)
  33.     {
  34.         printf("%d ", ps->a[i]);
  35.     }
  36.     printf("\n");
  37.     return;
  38. }
  39.  
  40. //尾插
  41. void SeqListPushBack(SeqList* ps, SLDateType x)
  42. {
  43.     /*增容*/
  44.     if (ps->size == ps->capacity)
  45.     {
  46.         SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType)*ps->capacity * 2);
  47.         /*增容失败*/
  48.         if (tmp == NULL)
  49.         {
  50.             perror("SeqListPushFront::realloc");
  51.             return;
  52.         }
  53.         /*增容成功*/
  54.         ps->a = tmp;
  55.         ps->capacity *= 2;
  56.     }
  57.     ps->a[ps->size++] = x;
  58.     return;
  59. }
  60.  
  61. //尾删
  62. void SeqListPopBack(SeqList* ps)
  63. {
  64.     if (0 == ps->size)
  65.         return;
  66.     ps->size--;
  67. }
  68.  
  69. //头插
  70. void SeqListPushFront(SeqList* ps, SLDateType x)
  71. {
  72.     /*扩容*/
  73.     if (ps->size == ps->capacity || ps->size + 1 == ps->capacity)
  74.     {
  75.         SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
  76.         /*增容失败*/
  77.         if (tmp == NULL)
  78.         {
  79.             perror("SeqListPushFront::realloc");
  80.             return;
  81.         }
  82.         /*增容成功*/
  83.         ps->a = tmp;
  84.         ps->capacity *= 2;
  85.     }
  86.     int i = 0;
  87.     for (i = ps->size; i>0; i -- )
  88.     {
  89.         ps->a[i] = ps->a[i - 1];
  90.     }
  91.     ps->a[0] = x;
  92.     ps->size++;
  93.     return;
  94. }
  95.  
  96. //头删
  97. void SeqListPopFront(SeqList* ps)
  98. {
  99.     if (0 == ps->size)
  100.         return;
  101.     int i = 0;
  102.     for (i = 0; i < ps->size - 1; i++)
  103.     {
  104.         ps->a[i] = ps->a[i + 1];
  105.     }
  106.     ps->size--;
  107.     return;
  108. }
  109.  
  110. //查找
  111. void SeqListFind(SeqList* ps, SLDateType x)
  112. {
  113.     int i = 0, flag = 0;
  114.     for (i = 0; i < ps->size; i++)
  115.     {
  116.         if (x == ps->a[i])
  117.         {
  118.             printf("找到了，下标是：%d\n", i);
  119.             flag++;
  120.         }
  121.     }
  122.     if (flag == 0)
  123.         printf("没找到\n");
  124.     return;
  125. }
  126.  
  127. //在pos位置插入x
  128. void SeqListInsert(SeqList* ps, int pos, SLDateType x)
  129. {
  130.     /*扩容*/
  131.     if (ps->size == ps->capacity || ps->size + 1 == ps->capacity)
  132.     {
  133.         SLDateType* tmp = (SLDateType*)realloc(ps->a, sizeof(SLDateType) * ps->capacity * 2);
  134.         /*增容失败*/
  135.         if (tmp == NULL)
  136.         {
  137.             perror("SeqListPushFront::realloc");
  138.             return;
  139.         }
  140.         /*增容成功*/
  141.         ps->a = tmp;
  142.         ps->capacity *= 2;
  143.     }
  144.     int i = 0;
  145.     for (i = ps->size; i > pos; i--)
  146.     {
  147.         ps->a[i] = ps->a[i - 1];
  148.     }
  149.     ps->a[pos] = x;
  150.     ps->size++;
  151.     return;
  152. }
  153.  
  154. //删除pos位置的值
  155. void SeqListErase(SeqList* ps, int pos)
  156. {
  157.     if (0 == ps->size)
  158.         return;
  159.     if (pos > ps->size-1)
  160.         return;
  161.     int i = 0;
  162.     for (i = pos; i < ps->size-1; i++)
  163.     {
  164.         ps->a[i] = ps->a[i + 1];
  165.     }
  166.     ps->size--;
  167.     return 0;
  168. }
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/500881
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号