• 数据结构 顺序表1

    1. 何为顺序表：

            顺序表是一种线性数据结构，是由一组地址连续的存储单元依次存储数据元素的结构，通常采用数组来实现。顺序表的特点是可以随机存取其中的任何一个元素，并且支持在任意位置上进行插入和删除操作。在顺序表中，每个元素的下标都是唯一的，而且在顺序表中，相邻的元素在内存中也是相邻的。

            顺序表通常包含两个重要的属性：容量和长度。容量指该顺序表所能容纳的最大元素数量，而长度指当前已经存储的元素数量。当长度等于容量时，顺序表就已经满了，不能再插入元素。

    2. 静态顺序表和动态顺序表的区别：

            由于顺序表底层是用数组完成的，所以这个数组决定了我们这个顺序表的大小，同时也区分出了静态顺序表与动态顺序表，下面我们来一一了解：

            静态顺序表：有着静态两字顾名思义则这个顺序表写好以后大小就固定死了，是不可以改变的（为了方便我们后期更改顺序表的类型，此处我们define定义一个变量，专门存放顺序表类型）

    1. typedef int SLDataTYpe;
    2.  
    3. typedef struct SeqList
    4. {
    5. 	SLDataTYpe p[50];	//数组大小为50，代表这个顺序表可以存储50个元素
    6. 	int size;   //顺序表有效数据个数
    7. 	int capacity;	//顺序表空间大小
    8. }SL;   //将顺序表struct SeqList取别名为SL

            动态顺序表：相较于静态，动态顺序表则在定义并没有给定数组的大小，而是定义了一个指针，等到后边需要用到顺序表的时候，再动态分配内存空间（C语言动态内存空间分配-CSDN博客）

    1. typedef int SLDataTYpe;
    2.  
    3. typedef struct SeqList
    4. {
    5. 	SLDataTYpe* p;
    6. 	int size;   //顺序表有效数据个数
    7. 	int capacity;	//顺序表空间大小
    8. }SL;   //将顺序表struct SeqList取别名为SL

    3. 顺序表的实现：

            在本次项目当中我们以动态顺序表为例，来对顺序表各类功能的实现，项目文件分为SeqList.h（顺序表中各类函数的声明），SeqList.c（顺序表各类功能的实现），SeqList_test（对应顺序表各类功能的测试），实现环境为VS2022

    3.1. 顺序表的初始化：

            在SeqList.h声明一个函数用于实现顺序表的初始化，同时传入一个顺序表变量，SeqList.c实现顺序表的初始化，顺序表没被调用前，顺序表为NULL（注：要想调用SeqList.h中声明好的方法，则得包含该方法所在的头文件）

    SeqList.h：

    1. #pragma once
    2. #include 
    3. typedef int SLDataTYpe;
    4.  
    5. //动态顺序表
    6. typedef struct SeqList
    7. {
    8. 	SLDataTYpe* p;
    9. 	int size;   //顺序表有效数据个数
    10. 	int capacity;	//顺序表空间大小
    11. }SL;    //将顺序表struct SeqList取别名为SL
    12.  
    13. //顺序表的初始化
    14. void SLInit(SL* ps);

    SeqList.c：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"    //头文件包含
    3.  
    4. //顺序表初始化的实现
    5. void SLInit(SL* ps)
    6. {
    7. 	ps->p = NULL;   
    8. 	ps->size = 0;    //有效数据个数为0
    9. 	ps->capacity = 0;    //空间大小为0
    10. }

      SeqList_test（在SeqList_test中调用SLInit函数，打开监视查看是否赋值成功）：

    1. void SLTest01()
    2. {
    3. 	SL s1;
    4. 	SLInit(&s1);
    5. 	
    6. }
    7.  
    8. int main()
    9. {
    10. 	SLTest01();
    11. 	return 0;
    12. }

    测试结果：

    （如上图所示，则初始化成功）

    3.2. 顺序表的销毁：

            顺序表的销毁分为两种情况，一是顺序表已写入数据，二是没有写入数据

    SeqList.h：

    1. #pragma once
    2. #include 
    3. typedef int SLDataTYpe;
    4.  
    5. //动态顺序表
    6. typedef struct SeqList
    7. {
    8. 	SLDataTYpe* p;
    9. 	int size;   //顺序表有效数据个数
    10. 	int capacity;	//顺序表空间大小
    11. }SL;    //将顺序表struct SeqList取别名为SL
    12.  
    13. //顺序表的初始化
    14. void SLInit(SL* ps);
    15.  
    16. //顺序表的销毁
    17. void SLDesttroy(SL* ps);

    SeqList.c：

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3.  
    4. //顺序表初始化的实现
    5. void SLInit(SL* ps)
    6. {
    7. 	ps->p = NULL;
    8. 	ps->size = 0;
    9. 	ps->capacity = 0;
    10. }
    11.  
    12. //顺序表的销毁
    13. void SLDesttroy(SL* ps)
    14. {
    15. 	if (ps->p)    //判断是否为NULL
    16. 	{
    17. 		free(ps->p);
    18. 	}
    19. 	ps->p = NULL;
    20. 	ps->size = 0;
    21. 	ps->capacity = 0;
    22. }

    （由于代码量的缘故，后边只展示对应文件中要添加的代码）

    3.3. 顺序表插入数据：

            为了方便展示，关于SeqList.h文件当中的代码，统一展示在此处

    1. //顺序表头部插入删除 / 尾部插入删除
    2. void SLPushBack(SL* ps, SLDataTYpe x);
    3. void SLPushFront(SL* ps, SLDataTYpe x);
    4.  
    5. void SLPopBack(SL* ps);
    6. void SLPopFront(SL* ps);
    7.  
    8. //在指定位置之前插入数据
    9. void SLInsert(SL* ps, int pos, SLDataTYpe x);
    10.  
    11. //删除指定位置数据
    12. void SLErase(SL* ps, int pos);

    3.3.1. 头插：

    头插可以分为以下几点：

    1. 函数传参：

    void SLPushFront(SL* ps, SLDataTYpe x);   //x为要插入的元素

    2. 判断顺序表是否为空：

    1. #include <assert.h>    //头文件包含
    2. assert(ps);    //ps为要断言的变量

    3. 判断顺序表空间是否够用：

    由于后续我们要多次判断是否要增容，此处我们重新用一个函数完成顺序表的增容：

    （注：realloc函数如果申请内存空间失败，则返回NULL，所以此处不可将realloc申请的空间直接赋给p->p这样会导致原来p->p中的数据全部清空，应先判断增容是否成功，再进行赋值）

    1. void SLcheckCapacity(SL* p)
    2. {
    3. 	//插入数据前判断空间是否足够 如果数组大小与内存总大小相等，则申请空间
    4. 	if (p->size == p->capacity)
    5. 	{
    6. 		//判断capacity的值是否为0，不为0则2倍增容
    7. 		int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
    8. 		//增容空间
    9. 		SLDataTYpe* tmp = (SLDataTYpe*)realloc(p->p, 2 * newcapacity * sizeof(SLDataTYpe));
    10. 		//判断增容是否成功
    11. 		if (tmp == NULL)
    12. 		{
    13. 			perror("relloc fail");
    14. 			exit(1);
    15. 		}
    16. 		//申请成功以后
    17. 		p->p = tmp;
    18. 		p->capacity = newcapacity;
    19. 	}
    20. }

    4. 头部插入数据：

            假设一个数组中已有数据a，b，c，d，现在要在头部添加一个元素f，我们应该如何添加？

    思路分析：

    代码实现（SeqList.c）：

    1. void SLPushFront(SL* ps, SLDataTYpe x)
    2. {
    3. 	//判断ps是否为NULL
    4. 	assert(ps);
    5. 	//判断内存空间是否足够，是否需要增容
    6. 	SLcheckCapacity(ps);
    7. 	//将顺序表中原有的数据整体往后挪一位
    8. 	for (int i = ps->size; i > 0; i--)
    9. 	{
    10. 		ps->p[i] = ps->p[i - 1];
    11. 	}
    12.     //添加元素
    13. 	ps->p[0] = x;
    14.     //size向后挪动一位
    15. 	ps->size++;
    16. }

    3.3.2. 尾插：

             假设一个数组中已有数据a，b，c，d，现在要在最后添加一个元素f，我们应该如何添加？

    思路分析：

    代码实现（SeqList.c）：

    1. void SLPushBack(SL* ps, SLDataTYpe x)
    2. {
    3. 	//判断ps是否为NULL
    4. 	assert(ps);
    5.     //判断内存空间是否足够，是否需要增容
    6. 	SLcheckCapacity(ps);
    7. 	ps->p[ps->size++] = x;
    8. 	
    9. }

    3.3.3 头删：

            将除首地址的元素外其余所以元素往前挪动一位，同时size也需往前挪动一位（size--），覆盖首元素即可（注：如果数组中没有元素，即size=0，此时是没有元素可以删的，所以此处应还需断言size是否为0）

    思路分析：

    代码实现（SeqList.c）：

    1. void SLPopFront(SL* ps)
    2. {
    3.     //判断ps是否为NULL
    4. 	assert(ps);
    5.     //判断数组是否为空
    6. 	assert(ps->size);
    7. 	for (int i = 0; i < ps->size - 1; i++)
    8. 	{
    9. 		ps->p[i] = ps->p[i + 1];
    10. 	}
    11. 	ps->size--;
    12. }

    3.3.4 尾删：

            当数组不为空时，size往前挪一位（注size代表的是数组的大小，即下标+1，也就是说size前边为整个数组，因此删除末尾元素时，我们只需要将size--即可）

    思路分析：

    代码实现（SeqList.c）：

    1. void SLPopBack(SL* ps)
    2. {
    3. 	//断言
    4. 	assert(ps);
    5. 	//判断顺序表是否为NULL，为空删除等于-1，越界
    6. 	assert(ps->size);
    7. 	//删除数据
    8. 	ps->size--;
    9. }

    3.3.5 指定位置添加数据：

            与头插相类似，此处只需要将指定位置的数据整体往后挪一位size++，由于和头插相类似，就不在此处重复直接看代码：

    1. void SLInsert(SL* ps, int pos, SLDataTYpe x)
    2. {
    3. 	assert(ps);
    4. 	assert(pos >= 0 && pos <= ps->size);	//判断pos的有效范围
    5. 	//插入数据：空间够不够
    6. 	SLcheckCapacity(ps);
    7. 	//让pos下标对应的数据，全部往后挪一位
    8. 	for (int i = ps->size; i > pos; i--)
    9. 	{
    10. 		ps->p[i] = ps->p[i - 1];
    11. 	}
    12. 	ps->p[pos] = x;
    13. 	ps->size++;
    14.  
    15. }

    3.3.6 指定位置删除数据：

            与添加相反，删除指定对应数据以后，指定位置后的元素整体往前挪一位，size--

    1. void SLErase(SL* ps, int pos)
    2. {
    3. 	assert(ps);
    4. 	assert(pos >= 0 && pos < ps->size);
    5. 	for (int i = pos; i < ps->size - 1; i++)
    6. 	{
    7. 		ps->p[i] = ps->p[i + 1];
    8. 	}
    9. 	ps->size--;
    10. }

    3.4 顺序表的打印：

            遍历数组

    代码实现（SeqList.h  / SeqList.c）：

    1. //顺序表的打印
    2. void SLPrintf(SL s);
    1. void SLPrintf(SL s)
    2. {
    3. 	//打印
    4. 	for (int i = 0; i < s.size; i++)
    5. 	{
    6. 		printf("%d ", s.p[i]);
    7. 	}
    8. 	printf("\n");
    9. }

    3.5 顺序表的查找：

            遍历数组，查找对应的元素，存在返回元素的下标，不存在返回无效下标-1

    代码实现（SeqList.h  / SeqList.c）：

    1. //查找
    2. int SLFind(SL* ps, SLDataTYpe x);  //数据有，返回值的下标，否则返回-1
    1. 查找
    2. int SLFind(SL* ps, SLDataTYpe x)
    3. {
    4. 	assert(ps);
    5. 	for (int i = 0; i < ps->size; i++)
    6. 	{
    7. 		if (ps->p[i] == x)
    8. 		{
    9. 			//找到了
    10. 			return i;
    11. 		}
    12. 	}
    13. 	//没找到
    14. 	return -1;
    15. }

    4.实现代码：

    SeqList.h

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5. typedef int SLDataTYpe;
    6. //动态顺序表
    7. typedef struct SeqList
    8. {
    9. 	SLDataTYpe* p;
    10. 	int size;   //顺序表有效数据个数
    11. 	int capacity;	//顺序表空间大小
    12. }SL;
    13.  
    14. //顺序表的初始化
    15. void SLInit(SL* ps);
    16.  
    17. //顺序表的销毁
    18. void SLDesttroy(SL* ps);
    19.  
    20. //顺序表头部插入删除 / 尾部插入删除
    21. void SLPushBack(SL* ps, SLDataTYpe x);
    22. void SLPushFront(SL* ps, SLDataTYpe x);
    23.  
    24. void SLPopBack(SL* ps);
    25. void SLPopFront(SL* ps);
    26.  
    27. //在指定位置之前插入数据
    28. void SLInsert(SL* ps, int pos, SLDataTYpe x);
    29.  
    30. //删除指定位置数据
    31. void SLErase(SL* ps, int pos);
    32.  
    33. //顺序表的打印
    34. void SLPrintf(SL s);
    35.  
    36. //查找
    37. int SLFind(SL* ps, SLDataTYpe x);  //数据有，返回值的下标，否则返回-1
    38.

    SeqList.c

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3.  
    4. //顺序表初始化的实现
    5. void SLInit(SL* ps)
    6. {
    7. 	ps->p = NULL;
    8. 	ps->size = 0;
    9. 	ps->capacity = 0;
    10. }
    11.  
    12. //顺序表的销毁
    13. void SLDesttroy(SL* ps)
    14. {
    15. 	if (ps->p)
    16. 	{
    17. 		free(ps->p);
    18. 	}
    19. 	ps->p = NULL;
    20. 	ps->size = 0;
    21. 	ps->capacity = 0;
    22. }
    23.  
    24. //增容
    25. void SLcheckCapacity(SL* p)
    26. {
    27. 	//插入数据前判断空间是否足够 如果数组大小与内存总大小相等，则申请空间
    28. 	if (p->size == p->capacity)
    29. 	{
    30. 		//判断capacity的值是否为0
    31. 		int newcapacity = p->capacity == 0 ? 4 : 2 * p->capacity;
    32. 		//增容空间
    33. 		SLDataTYpe* tmp = (SLDataTYpe*)realloc(p->p, 2 * newcapacity * sizeof(SLDataTYpe));
    34. 		//判断增容是否成功
    35. 		if (tmp == NULL)
    36. 		{
    37. 			perror("relloc fail");
    38. 			exit(1);
    39. 		}
    40. 		//申请成功以后
    41. 		p->p = tmp;
    42. 		p->capacity = newcapacity;
    43. 	}
    44. }
    45.  
    46. //顺序表的尾插
    47. void SLPushBack(SL* ps, SLDataTYpe x)
    48. {
    49. 	//判断ps是否为NULL
    50. 	assert(ps);
    51. 	SLcheckCapacity(ps);
    52. 	ps->p[ps->size++] = x;
    53. 	
    54. }
    55.  
    56. //头插
    57. void SLPushFront(SL* ps, SLDataTYpe x)
    58. {
    59. 	//判断ps是否为NULL
    60. 	assert(ps);
    61. 	//增容
    62. 	SLcheckCapacity(ps);
    63. 	//将顺序表中原有的数据整体往后挪一位
    64. 	for (int i = ps->size; i > 0; i--)
    65. 	{
    66. 		ps->p[i] = ps->p[i - 1];
    67. 	}
    68. 	ps->p[0] = x;
    69. 	ps->size++;
    70. }
    71.  
    72. //顺序表的打印
    73. void SLPrintf(SL s)
    74. {
    75. 	//打印
    76. 	for (int i = 0; i < s.size; i++)
    77. 	{
    78. 		printf("%d ", s.p[i]);
    79. 	}
    80. 	printf("\n");
    81. }
    82.  
    83. //尾删
    84. void SLPopBack(SL* ps)
    85. {
    86. 	//断言
    87. 	assert(ps);
    88. 	//判断顺序表是否为NULL，为空删除等于-1，越界
    89. 	assert(ps->size);
    90. 	//删除数据
    91. 	ps->size--;
    92. }
    93.  
    94. //头删
    95. void SLPopFront(SL* ps)
    96. {
    97. 	assert(ps);
    98. 	assert(ps->size);
    99. 	for (int i = 0; i < ps->size - 1; i++)
    100. 	{
    101. 		ps->p[i] = ps->p[i + 1];
    102. 	}
    103. 	ps->size--;
    104. }
    105.  
    106. //在指定位置之前插入数据
    107. void SLInsert(SL* ps, int pos, SLDataTYpe x)
    108. {
    109. 	assert(ps);
    110. 	assert(pos >= 0 && pos <= ps->size);	//判断pos的有效范围
    111. 	//插入数据：空间够不够
    112. 	SLcheckCapacity(ps);
    113. 	//让pos下标对应的数据，全部往后挪一位
    114. 	for (int i = ps->size; i > pos; i--)
    115. 	{
    116. 		ps->p[i] = ps->p[i - 1];
    117. 	}
    118. 	ps->p[pos] = x;
    119. 	ps->size++;
    120.  
    121. }
    122.  
    123. //删除指定位置数据
    124. void SLErase(SL* ps, int pos)
    125. {
    126. 	assert(ps);
    127. 	assert(pos >= 0 && pos < ps->size);
    128. 	for (int i = pos; i < ps->size - 1; i++)
    129. 	{
    130. 		ps->p[i] = ps->p[i + 1];
    131. 	}
    132. 	ps->size--;
    133. }
    134.  
    135. //查找
    136. int SLFind(SL* ps, SLDataTYpe x)
    137. {
    138. 	assert(ps);
    139. 	for (int i = 0; i < ps->size; i++)
    140. 	{
    141. 		if (ps->p[i] == x)
    142. 		{
    143. 			//找到了
    144. 			return i;
    145. 		}
    146. 	}
    147. 	//没找到
    148. 	return -1;
    149. }

    SeqList_test.c（测试代码）

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3.  
    4. void SLTest01()
    5. {
    6. 	SL s1;
    7. 	SLInit(&s1);
    8. 	
    9. }
    10.  
    11. int main()
    12. {
    13. 	SLTest01();
    14. 	return 0;
    15. }
    16. 尾插
    17. //SLPushBack(&s1, 1);
    18. //SLPushBack(&s1, 2);
    19. //SLPushBack(&s1, 3);
    20. //SLPushBack(&s1, 4);
    21. //SLPrintf(s1);
    22. //SLPushBack(&s1, 5);
    23. //SLPrintf(s1);
    24. //SLPushFront(&s1, 5);
    25. //SLPushFront(&s1, 6);
    26. //SLPrintf(s1);
    27. //
    28. //
    29. 销毁
    30. //SLDesttroy(&s1);

    （有需要的小伙伴自取喔，最后还请点赞三联支持一下博主，Thanks♪(･ω･)ﾉ！！！）

  • 相关阅读:
    基于Chirp窄带扩频技术的无线混合组网应用，以多角色智能计量插座作为Chirp广域基站，构建边缘计算混合无线网络
    ＊Django中的Ajax jq的书写样式1
    UVa10537 The Toll! Revisited(Dijkstra)
    比较两组等数量等高度的结构间比值
    戴姆勒——从豪华私家车到无人驾驶飞机
    【图多预警】Pandas绘图函数总结
    HarmonyOS列表组件
    网络安全（黑客）自学
    【信号隐藏-数字水印】基于小波变换算法DWT结合离散余弦变换DCT实现音频数字水印嵌入提取附matlab代码
    视频融合云平台EasyCVR进程启动时报错“update cluster server”的排查及解决方法
  • 原文地址：https://blog.csdn.net/czzlv/article/details/138615237