• 数据结构之顺序表

    顺序表就是数组，但是在数组的基础上，它要求数据是从头开始并且连续存储的，不能间隔存储

    静态顺序表

    静态顺序表中如果数据满了则不让继续存储，因此我们无法确定该给它多少内存

    其头文件：

    1. #pragma once
    2. #define N 1000
    3. typedef int SLDataType
    4.  
    5. //静态顺序表 
    6. typedef struct SeqList
    7. {
    8. 	SLDataType a[N];
    9. 	int size;//表示数组中存储了多少个数据 
    10.  }SL; 
    11.  
    12.  //接口函数 
    13.  void SeqListInit(SL* ps);
    14.   
    15.  void SeqListPushBack(SL* ps,SLDataType x);
    16.  void SeqListPopBack(SL* ps);
    17.  void SeqListPushFront(SL* ps,SLDataType x);
    18.  void SeqListPopFront(SL* ps);

    动态顺序表

    动态顺序表：

    1. typedef int SLDataType;
    2.  
    3. //动态顺序表 
    4. typedef struct SeqList
    5. {
    6. 	SLDataType* a;
    7. 	int size;//表示数组中存储了多少个数据 
    8. 	int capacity;//表示数组时间能存储多少个数据 
    9.  }SL;

    各接口函数实现

    顺序表初始化：

    1. void SeqListInit(SL *ps)//顺序表初始化 
    2.  {
    3.  	ps->a = NULL;
    4.  	ps->size = ps->capacity = 0;
    5.  }

    顺序表销毁：

    1. void SeqListDestory(SL* ps)
    2. {
    3.     free(ps->a);
    4.     ps->a = NULL;
    5.     ps->capacity = ps->size = 0;
    6. }

    顺序表检查内存空间是否足够：

    1. void SeqListCheckCapacity(SL* ps)//检查内存空间是否足够
    2. {
    3.     if (ps->size == ps->capacity)//没有空间或者空间不足的情况下
    4.     {
    5.         int newcapacity = ps->capacity = 0 ? 4 : ps->capacity * 2;
    6.         SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//没有空间则申请内存空间，有则进行扩容
    7.         if (tmp == NULL)
    8.         {
    9.             printf("realloc fail \n");
    10.             exit(-1);
    11.         }
    12.         ps->a = tmp;
    13.         ps->capacity = newcapacity;
    14.     }
    15. }

    顺序表尾插：

    尾插时需考虑三种情况：

    1. 整个顺序表没有空间
    2. 空间不够，需要扩容
    3. 空间足够，直接插入数据
    1. void SeqListPushBack(SL* ps, SLDataType x)//顺序表尾插
    2. {
    3.     SeqListCheckCapacity(ps);
    4.     ps->a[ps->size] = x;
    5.     ps->size++;
    6. }

    顺序表尾插：

    1. void SeqListPopBack(SL* ps)//数据表尾删
    2. {
    3.     if(ps->size > 0)
    4.     {
    5.         ps->size--;
    6.     }
    7. }

    顺序表头插：

    1. void SeqListPushFront(SL* ps, SLDataType x)//顺序表头插
    2. {
    3.     SeqListCheckCapacity(ps);
    4.     int end = ps->size - 1;
    5.     while(end >= 0)//数据向后挪动
    6.     {
    7.         ps->a[end+1] = ps->a[end];
    8.         --end;
    9.     }
    10.     ps->a[0] = x;
    11.     ps->size++;
    12. }

    顺序表头删：

    1. void SeqListPopFront(SL* ps)
    2. {
    3.     assert(ps->size > 0);//存储数据不能为零，否则会终止
    4.     int begin = 1;
    5.     while(begin < ps->size)//数据向前挪动
    6.     {
    7.         ps->a[begin-1] = ps->a[begin];
    8.         begin++;
    9.     }
    10.     ps->size--;
    11. }

    使用assert方法时需导入assert库

    顺序表中查找数据位置（找到了返回数据位置下标，没有找到则返回-1）：

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

    顺序表指定位置插入：

    1. void SeqListInsert(SL* ps,int pos,SLDataType x)
    2. {
    3.     if(pos > ps->size || pos < 0)
    4.     {
    5.         printf("pos invalid \n")
    6.         return ;
    7.     }
    8.     
    9.     //assert(pos <= ps->size && pos => 0)//暴力方法不得输入非法pos
    10.     SeqListCheckCapcaity(ps);
    11.     int end = ps->size-1;
    12.     while(end >= pos)
    13.     {
    14.         ps->a[end+1] = ps->a[end];
    15.         end--;
    16.     }
    17.     ps->a[pos] = x;
    18.     ps->size++;
    19. }

    顺序表指定位置删除：

    1. void SeqListErase(SL* ps,int pos)
    2. {
    3.     if(pos > ps->size || pos < 0)
    4.     {
    5.         printf("pos invalid \n")
    6.         return ;
    7.     }
    8.     int begin = pos + 1;
    9.     while(begin < ps->size)
    10.     {
    11.         ps->a[begin-1] = ps->a[begin];
    12.         begin++;
    13.     }
    14.     ps->size--;
    15. }

    通过顺序表的指定位置删除我们可以改善顺序表的头删

    动态顺序表（完整版）

    头文件：

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. typedef int SLDataType;
    6.  
    7. //动态顺序表
    8. typedef struct SeqList
    9. {
    10. 	SLDataType* a;
    11. 	int size;//表示数组中存储了多少个数据
    12. 	int capacity;//表示数组时间能存储多少个数据
    13. }SL;
    14.  
    15. //接口函数
    16. void SeqListInit(SL* ps);
    17. void SeqListDestory(SL* ps);
    18. void SeqListPrint(SL* ps);
    19. void SeqListPushBack(SL* ps, SLDataType x);
    20. void SeqListPopBack(SL* ps);
    21. void SeqListPushFront(SL* ps, SLDataType x);
    22. void SeqListPopFront(SL* ps);
    23. void SeqListCheckCapcaity(SL* ps);
    24.  
    25. int SeqListFind(SL* ps,SLDataType x);
    26. void SeqListInsert(SL* ps,int pos,SLDataType x);
    27. void SeqListErase(SL* ps,int pos);

    接口函数以及结构体的.c文件：

    1. #include "SeqList.h"
    2.  
    3. void SeqListInit(SL* ps)//顺序表初始化
    4. {
    5.     ps->a = NULL;
    6.     ps->size = ps->capacity = 0;
    7. }
    8.  
    9. void SeqListDestory(SL* ps)
    10. {
    11.     free(ps->a);
    12.     ps->a = NULL;
    13.     ps->capacity = ps->size = 0;
    14. }
    15.  
    16. void SeqListPrint(SL* ps)//顺序表销毁
    17. {
    18.     for(int i = 0; i < ps->size; i++)
    19.     {
    20.         printf("%d ", ps->a[i]);
    21.     }
    22.     printf("\n");
    23. }
    24.  
    25. void SeqListCheckCapacity(SL* ps)//检查内存空间是否足够
    26. {
    27.     if (ps->size == ps->capacity)//没有空间或者空间不足的情况下
    28.     {
    29.         int newcapacity = ps->capacity = 0 ? 4 : ps->capacity * 2;
    30.         SLDataType* tmp = (SLDataType*)realloc(ps->a, newcapacity * sizeof(SLDataType));//没有空间则申请内存空间，有则进行扩容
    31.         if (tmp == NULL)
    32.         {
    33.             printf("realloc fail \n");
    34.             exit(-1);
    35.         }
    36.         ps->a = tmp;
    37.         ps->capacity = newcapacity;
    38.     }
    39. }
    40.  
    41. void SeqListPushBack(SL* ps, SLDataType x)//顺序表尾插
    42. {
    43.     SeqListCheckCapacity(ps);
    44.     ps->a[ps->size] = x;
    45.     ps->size++;
    46. }
    47.  
    48. void SeqListPopBack(SL* ps)//数据表尾删
    49. {
    50.     if(ps->size > 0)
    51.     {
    52.         ps->size--;
    53.     }
    54. }
    55.  
    56. void SeqListPushFront(SL* ps, SLDataType x)//顺序表头插
    57. {
    58.     SeqListCheckCapacity(ps);
    59.     int end = ps->size - 1;
    60.     while(end >= 0)//数据向后挪动
    61.     {
    62.         ps->a[end+1] = ps->a[end];
    63.         --end;
    64.     }
    65.     ps->a[0] = x;
    66.     ps->size++;
    67. }
    68.  
    69. void SeqListPopFront(SL* ps)
    70. {
    71.     assert(ps->size > 0);//存储数据不能为零，否则会终止
    72.     int begin = 1;
    73.     while(begin < ps->size)//数据向前挪动
    74.     {
    75.         ps->a[begin-1] = ps->a[begin];
    76.         begin++;
    77.     }
    78.     ps->size--;
    79. }
    80.  
    81. int SeqListFind(SL* ps,SLDataType x)
    82. {
    83.     for(int i = 0;i < ps->size;i++)
    84.     {
    85.         if(ps->a[i] == x)
    86.         {
    87.             return i;
    88.         }
    89.     }
    90.     return -1;
    91. }
    92.  
    93. void SeqListInsert(SL* ps,int pos,SLDataType x)
    94. {
    95.     if(pos > ps->size || pos < 0)
    96.     {
    97.         printf("pos invalid \n");
    98.         return ;
    99.     }
    100.  
    101.     //assert(pos <= ps->size && pos => 0)//暴力方法不得输入非法pos
    102.     SeqListCheckCapacity(ps);
    103.     int end = ps->size-1;
    104.     while(end >= pos)
    105.     {
    106.         ps->a[end+1] = ps->a[end];
    107.         end--;
    108.     }
    109.     ps->a[pos] = x;
    110.     ps->size++;
    111. }
    112.  
    113. void SeqListErase(SL* ps,int pos)
    114. {
    115.     if(pos > ps->size || pos < 0)
    116.     {
    117.         printf("pos invalid \n");
    118.         return ;
    119.     }
    120.     int begin = pos + 1;
    121.     while(begin < ps->size)
    122.     {
    123.         ps->a[begin-1] = ps->a[begin];
    124.         begin++;
    125.     }
    126.     ps->size--;
    127. }

    测试顺序表的.c文件：

    1. #include "SeqList.h"
    2.  
    3. void TestSeqList1() {
    4. 	SL s1;
    5. 	SeqListInit(&s1);
    6. 	SeqListPushBack(&s1, 1);
    7. 	SeqListPushBack(&s1, 2);
    8. 	SeqListPushBack(&s1, 3);
    9. 	SeqListPopBack(&s1);
    10. 	SeqListPopBack(&s1);
    11.  
    12. 	SeqListPrint(&s1);
    13. 	SeqListDestory(&s1);
    14. }
    15.  
    16. void TestSeqList2()
    17. {
    18.     SL s1;
    19. 	SeqListInit(&s1);
    20.     SeqListPushBack(&s1,1);
    21.     SeqListPushBack(&s1,2);
    22.     SeqListPushBack(&s1,3);
    23.     SeqListPushBack(&s1,4);
    24.     SeqListPushBack(&s1,5);
    25.  
    26.     SeqListPushFront(&s1,10);
    27.     SeqListPushFront(&s1,20);
    28.     SeqListPushFront(&s1,30);
    29.     SeqListPushFront(&s1,40);
    30.     SeqListPushFront(&s1,50);
    31.     SeqListPushFront(&s1,60);
    32.     SeqListPushFront(&s1,70);
    33.  
    34.     SeqListPopFront(&s1);
    35.     SeqListPopFront(&s1);
    36.     SeqListPopFront(&s1);
    37.     SeqListPopFront(&s1);
    38.  
    39.     SeqListPrint(&s1);
    40. 	SeqListDestory(&s1);
    41. }
    42.  
    43. void TestSeqList3()
    44. {
    45.     SL s1;
    46. 	SeqListInit(&s1);
    47.     SeqListPushBack(&s1,1);
    48.     SeqListPushBack(&s1,2);
    49.     SeqListPushBack(&s1,3);
    50.     SeqListPushBack(&s1,4);
    51.     SeqListPushBack(&s1,5);
    52.  
    53.     SeqListInsert(&s1,1,10);
    54.     SeqListInsert(&s1,2,200);
    55.     SeqListErase(&s1,5);
    56.     SeqListErase(&s1,2);
    57.  
    58.     SeqListPrint(&s1);
    59.  
    60.     int pos = SeqListFind(&s1,5);
    61.     printf("%d",pos);
    62.  
    63. 	SeqListDestory(&s1);
    64. }
    65.  
    66.  
    67. int main() {
    68.     TestSeqList1();
    69.     TestSeqList2();
    70. 	TestSeqList3();
    71.  
    72. 	return 0;
    73. }

    顺序表缺点：

    1. 空间不够时需要扩容，而扩容需要付出代价。扩容时当内存后面有足够空间时会原地扩容，没有足够空间时会重新找一块内存申请空间
    2. 为了避免频繁扩容，当内存空间满了时，基本都是扩容两倍，这就可能导致内存一定空间的浪费
    3. 顺序表要求从头开始连续存储数据，因此我们在头部或中间插入删除数据时就需要挪动数据，效率不高

    顺序表优点：

    1. 存储密度大
    2. 可随机存取某一元素

  • 相关阅读:
    spark深度剖析
    计算机毕业设计Python+Django的毕业设计过程管理系统(源码+系统+mysql数据库+Lw文档）
    深度学习遇到内存溢出的情况
    广州搬砖第三年，从一枚小菜鸡到架构师
    wsl2迁移镜像虚拟磁盘
    [DevOps云实践] 彻底删除AWS云资源
    Redis高可用方案之主从复制
    IO 模型的演变
    git实现服务器自动push拉取代码--webhooks
    DSGC：双空间图对比学习
  • 原文地址：https://blog.csdn.net/Thewei666/article/details/127588064