• 【数据结构】线性表之顺序表

    目录

    一.线性表

    1.顺序存储

    2.链式存储

    二.顺序表

    分类：

    静态顺序表 

    问题：

    动态顺序表

    问题：

    如何解决问题：

    三.代码实现

    初始化

    尾插入

    首插入

    方法1：

    方法2：

    头删

     尾删

     选择插入

    方法1：

     方法2：

     选择删除

    查找

     修改

    四.完整代码

    SeqList.h文件

    SeqList.c文件

    text.c文件

    一.线性表

    线性表：全名线性存储结构

    线性存储结构分为顺序存储结构和链式存储结构，前者称为顺序表，后者称为链表

    1.顺序存储

    顺序表就是把线性表中的所有元素按照某种逻辑顺序，依次存储到指定位置的一块连续的存储空间。

    2.链式存储

    用于存储逻辑关系为“一对一”的数据

    用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），包括数据与和指针域。数据域存储数据，指针域存储后继的信息。

    二.顺序表

    分类：

    1. 静态顺序表：使用定长数组存储
    2. 动态顺序表：使用动态开辟的数组存储

    静态顺序表 

    问题：

    给少了不够用 ，给多了用不完，不能灵活控制

    动态顺序表

    问题：

    1. 如果空间不够，增容。增容会付出一定性能消耗，其次可能存在一定的空间浪费
    2. 头部或者中部左右的插入和删除效率低

    如何解决问题：

    1.  空间上，按需给空间
    2. 不要求物理空间的连续（比如使用链表）

    • 这里我们使用动态顺序表

    三.代码实现

    初始化

    1. //初始化
    2. void SeqListInit(SL* psl)
    3. {
    4.     assert(psl);//这里严格要加上断言，防止在代码行数过多时，传参错误，使我们知道错误发生在那
    5. 	psl->a = NULL;
    6. 	psl->capacity = 0;
    7. 	psl->sizel = 0;
    8. }

    尾插入

    1. //增容
    2. void SeqListCheckCapacity(SL* psl)
    3. {
    4.     assert(psl);
    5. 	if (psl->capacity == psl->sizel)
    6. 	{
    7. 		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    8. 		SQDataType* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
    9.         //realloc将第一个参数的值依次存入所申请的空间
    10. 		assert(temp);
    11.  
    12. 		psl->a = temp;
    13. 		psl->capacity = newcapacity;
    14. 	}
    15. }
    16.  
    17. //尾插
    18. void SeqListPushBack(SL* psl, SQDataType x)
    19. {
    20.     assert(psl);
    21. 	SeqListCheckCapacity(psl);//判断capacity是否足够，若不够进行增容
    22. 	psl->a[psl->sizel] = x;
    23. 	psl->sizel++;
    24. }

    首插入

    方法1：

    使用常规的for循环进行增容。

    1. void SeqListPushFront(SL* psl, SQDataType x)
    2. {
    3.     assert(psl);
    4. 	SeqListCheckCapacity(psl);//增容
    5. 	for (int i = psl->sizel-1; i >= 0; i--)
    6. 	{
    7. 		psl->a[i + 1] = psl->a[i];
    8. 	}
    9. 	psl->a[0] = x;
    10. 	psl->sizel++;
    11. }

    方法2：

    使用memmove函数，以字节为单位，拷贝链表，使其每个元素的位置增加一个SQDataType的大小。

    1. //头插——方法2
    2. void SeqListPushFront(SL* psl, SQDataType x)
    3. {
    4.     assert(psl);
    5. 	SeqListCheckCapacity(psl);//增容
    6. 	memmove(&(psl->a[1]), psl->a, psl->sizel * sizeof(SQDataType));
    7. 	psl->a[0] = x;
    8. 	psl->sizel++;
    9. }

    头删

    这里同样可以使用两种方法，这里我使用了最方便的memmove

    判断方法2可以准确的给出错误的位置，方便在代码行数过多时，找出错误

    判断方法1只是在发现出错后退出函数，不利于修改错误。

    大多情况我们使用方法2.

    1. //头删
    2. void SeqListPopFront(SL* psl)
    3. {
    4.     assert(psl);
    5.     //判断方法1：温柔检查
    6. 	//if (psl->size == 0)
    7. 	//{
    8. 	//	printf("顺序表以为空，无法删除！\n");
    9. 	//	return;
    10. 	//}
    11.  
    12. 	//判断方法2：暴力检查
    13. 	assert(psl->sizel > 0);//判断顺序表中是否有数据
    14. 	memmove(psl->a, &(psl->a[1]), (psl->sizel - 1) * sizeof(SQDataType));
    15. 	//psl->a[psl->sizel - 1] = 0;
    16.     //这行代码有点多余，下次尾插的值为0时将毫无意义，而顺序表是通过size1访问的，改变size1即可
    17. 	psl->sizel--;
    18. }

     尾删

    1. //尾删
    2. void SeqListPopBack(SL* psl)
    3. {
    4.     assert(psl);
    5.     //判断方法1：温柔检查
    6. 	//if (psl->size == 0)
    7. 	//{
    8. 	//	printf("顺序表以为空，无法删除！\n");
    9. 	//	return;
    10. 	//}
    11.  
    12.    	//判断方法2：暴力检查
    13. 	assert(psl->sizel > 0);//判断顺序表中是否有数据
    14. 	psl->a[psl->sizel - 1] = NULL;
    15. 	psl->sizel--;
    16. }

     选择插入

    方法1：

    使用memmove函数调整表中元素位置后插入

    1. //选择插入
    2. void SeqListInsert(SL* psl, int index, SQDataType x)
    3. {
    4.     assert(psl);
    5. 	assert(pos <= psl->sizel);
    6. 	SeqListCheckCapacity(psl);//增容
    7. 	memmove(&(psl->a[index + 1]), &(psl->a[index]), (psl->sizel - index) * sizeof(SQDataType));
    8. 	psl->a[index] = x;
    9. 	psl->sizel++;
    10. }

     方法2：

    使用循环依次移动元素最终插入

    1. //选择插入
    2. void SeqListInsert(SL* psl, int index, SQDataType x)
    3. {
    4.     assert(psl);
    5. 	assert(index <= psl->sizel);//判断index范围是否合法
    6. 	SeqListCheckCapacity(psl);//增容
    7. 	int cou = psl->sizel;
    8. 	while (cou > index)
    9. 	{
    10. 		psl->a[cou] = psl->a[cou - 1];
    11. 		cou--;
    12. 	}
    13. 	psl->a[index] = x;
    14. 	psl->sizel++;
    15. }

     选择删除

    使用memmove函数覆盖所要删除的位置

    1. //选择删除
    2. void SeqListErase(SL* psl, int index)
    3. {
    4.     assert(psl);
    5. 	assert(index < psl->sizel);
    6. 	memmove(&(psl->a[index]), &(psl->a[index + 1]), (psl->sizel - index - 1) * sizeof(SQDataType));
    7. 	psl->a[psl->sizel - 1] = NULL;
    8. 	psl->sizel--;
    9. }

    查找

    在顺序表中查找x，若找到返回下标，找不到则说明顺序表中没有改值

    1. //查找
    2. void SeqListFind(SL* psl, SQDataType x)
    3. {
    4.     assert(psl);
    5. 	int num = 0;
    6. 	while (num < psl->sizel)
    7. 	{
    8. 		if (psl->a[num] == x)
    9. 		{
    10. 			printf("%d\n", num);
    11. 			return;
    12. 		}
    13. 		num++;
    14. 	}
    15. 	printf("表中没有%d\b", x);
    16. 	return;
    17. }

     修改

    给出要修改元素的下标和替换的值，进行替换操作。

    1. //修改
    2. void SeqListModity(SL* psl, int pos, SQDataType x)
    3. {
    4.     assert(psl);
    5. 	assert(pos < psl->sizel && pos > 0);//判断给出的下标是否在范围内
    6. 	psl->a[pos] = x;
    7. }

    四.完整代码

    SeqList.h文件

    在头文件定义，存放函数、头文件和结构体的声明

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. #define N 10;
    8. typedef int SQDataType;
    9.  
    10. typedef struct SeqList
    11. {
    12. 	SQDataType* a;
    13. 	int sizel;     //有效数据个数
    14. 	int capacity;  //容量
    15. }SL;
    16.  
    17. //初始化
    18. void SeqListInit(SL* psl);
    19.  
    20. //尾插入
    21. void SeqListPushBack(SL* psl, SQDataType x);
    22.  
    23. //头插入
    24. void SeqListPushFront(SL* psl, SQDataType x);
    25.  
    26. //头删
    27. void SeqListPopFront(SL* psl);
    28.  
    29. //尾删
    30. void SeqListPopBack(SL* psl);
    31.  
    32. //选择插入
    33. void SeqListInsert(SL* psl, int index, SQDataType x);
    34.  
    35. //选择删除
    36. void SeqListErase(SL* psl, int index);
    37.  
    38. //查找
    39. void SeqListFind(SL* psl, SQDataType x);
    40.  
    41. //修改
    42. void SeqListModity(SL* psl, int pos, SQDataType x);
    43.  
    44. //打印
    45. void SeqListPrint(SL* psl);
    46.  
    47. //销毁空间
    48. void SeqListDestroy(SL* psl);

    SeqList.c文件

    函数的实现放在此文件

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include "SeqList.h"
    3.  
    4. //初始化
    5. void SeqListInit(SL* psl)
    6. {
    7. 	psl->a = NULL;
    8. 	psl->capacity = 0;
    9. 	psl->sizel = 0;
    10. }
    11.  
    12. //增容
    13. void SeqListCheckCapacity(SL* psl)
    14. {
    15. 	if (psl->capacity == psl->sizel)
    16. 	{
    17. 		int newcapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    18. 		SQDataType* temp = (SQDataType*)realloc(psl->a, newcapacity * sizeof(SQDataType));
    19. 		assert(temp);
    20.  
    21. 		psl->a = temp;
    22. 		psl->capacity = newcapacity;
    23. 	}
    24. }
    25.  
    26. //尾插
    27. void SeqListPushBack(SL* psl, SQDataType x)
    28. {
    29. 	SeqListCheckCapacity(psl);//判断capacity是否足够，若不够进行增容
    30. 	psl->a[psl->sizel] = x;
    31. 	psl->sizel++;
    32. }
    33.  
    34. //头插——方法1
    35. //void SeqListPushFront(SL* psl, SQDataType x)
    36. //{
    37. //	SeqListCheckCapacity(psl);//增容
    38. //	for (int i = psl->sizel-1; i >= 0; i--)
    39. //	{
    40. //		psl->a[i + 1] = psl->a[i];
    41. //	}
    42. //	psl->a[0] = x;
    43. //	psl->sizel++;
    44. //}
    45.  
    46. //头插——方法2
    47. void SeqListPushFront(SL* psl, SQDataType x)
    48. {
    49. 	SeqListCheckCapacity(psl);//增容
    50. 	memmove(&(psl->a[1]), psl->a, psl->sizel * sizeof(SQDataType));
    51. 	psl->a[0] = x;
    52. 	psl->sizel++;
    53. }
    54.  
    55. //头删
    56. void SeqListPopFront(SL* psl)
    57. {
    58. 	assert(psl->sizel > 0);//判断顺序表中是否有数据
    59. 	memmove(psl->a, &(psl->a[1]), (psl->sizel - 1) * sizeof(SQDataType));
    60. 	psl->a[psl->sizel - 1] = 0;
    61. 	psl->sizel--;
    62. }
    63.  
    64. //尾删
    65. void SeqListPopBack(SL* psl)
    66. {
    67. 	assert(psl->sizel > 0);//判断顺序表中是否有数据
    68. 	psl->a[psl->sizel - 1] = NULL;
    69. 	psl->sizel--;
    70. }
    71.  
    72. //选择插入
    73. //void SeqListInsert(SL* psl, int index, SQDataType x)
    74. //{
    75. //	assert(index <= psl->sizel);
    76. //	SeqListCheckCapacity(psl);//增容
    77. //	memmove(&(psl->a[index + 1]), &(psl->a[index]), (psl->sizel - index) * sizeof(SQDataType));
    78. //	psl->a[index] = x;
    79. //	psl->sizel++;
    80. //}
    81.  
    82. //选择插入
    83. void SeqListInsert(SL* psl, int index, SQDataType x)
    84. {
    85. 	assert(index <= psl->sizel);
    86. 	SeqListCheckCapacity(psl);//增容
    87. 	int cou = psl->sizel;
    88. 	while (cou > index)
    89. 	{
    90. 		psl->a[cou] = psl->a[cou - 1];
    91. 		cou--;
    92. 	}
    93. 	psl->a[index] = x;
    94. 	psl->sizel++;
    95. }
    96.  
    97. //选择删除
    98. void SeqListErase(SL* psl, int index)
    99. {
    100. 	assert(index < psl->sizel);
    101. 	memmove(&(psl->a[index]), &(psl->a[index + 1]), (psl->sizel - index - 1) * sizeof(SQDataType));
    102. 	psl->a[psl->sizel - 1] = NULL;
    103. 	psl->sizel--;
    104. }
    105.  
    106. //查找
    107. void SeqListFind(SL* psl, SQDataType x)
    108. {
    109. 	int num = 0;
    110. 	while (num < psl->sizel)
    111. 	{
    112. 		if (psl->a[num] == x)
    113. 		{
    114. 			printf("%d\n", num);
    115. 			return;
    116. 		}
    117. 		num++;
    118. 	}
    119. 	printf("表中没有%d\b", x);
    120. 	return;
    121. }
    122.  
    123. //修改
    124. void SeqListModity(SL* psl, int pos, SQDataType x)
    125. {
    126. 	assert(pos < psl->sizel);
    127. 	psl->a[pos] = x;
    128. }
    129.  
    130. //打印链表
    131. void SeqListPrint(SL* psl)
    132. {
    133. 	for (int i = 0; i < psl->sizel; i++)
    134. 	{
    135. 		printf("%d ", psl->a[i]);
    136. 	}
    137. 	printf("\n");
    138. }
    139.  
    140. //销毁空间
    141. void SeqListDestroy(SL* psl)
    142. {
    143. 	free(psl->a);
    144. 	psl->a = NULL;
    145. 	psl->capacity = 0;
    146. 	psl->sizel = 0;
    147. }

    text.c文件

    存放主函数，其它函数在此文件夹调用

    1. #define _CRT_SECURE_NO_WARNINGS 1
    2. #include
    3. #include "SeqList.h"
    4.  
    5. //菜单
    6. void menu()
    7. {
    8. 	printf("**********************\n");
    9. 	printf("1.尾插数据，2.头插数据\n");
    10. 	printf("3.尾删数据，4.头删数据\n");
    11. 	printf("5.选择插入，6.选择删除\n");
    12. 	printf("7.查找元素，8.修改链表\n");
    13. 	printf("9.打印数据，-1，退出\n");
    14. 	printf("**********************\n");
    15. 	printf("请输入你的选择:");
    16. }
    17.  
    18. int main()
    19. {
    20. 	SL slist;
    21. 	int choose = 0;
    22. 	SeqListInit(&slist);//初始化
    23. 	while (choose != -1)
    24. 	{
    25. 		int a = 0, b = 0;
    26. 		menu();
    27. 		scanf(" %d", &choose);
    28. 		switch (choose)
    29. 		{
    30. 		case 1://尾插
    31. 			printf("请输入你要插入的数据，以-1结束\n");
    32. 			while (a != -1)
    33. 			{
    34. 				scanf("%d", &a);
    35. 				if(a!=-1)
    36. 					SeqListPushBack(&slist, a);
    37. 			}
    38. 			break;
    39. 		case 2://头插
    40. 			printf("请输入你要插入的数据，以-1结束\n");
    41. 			while (a != -1) 
    42. 			{
    43. 				scanf("%d", &a);
    44. 				if (a != -1)
    45. 					SeqListPushFront(&slist, a);
    46. 			} 
    47. 			break;
    48. 		case 3://尾删
    49. 			SeqListPopBack(&slist);
    50. 			printf("尾删，删除成功！\n");
    51. 			break;
    52. 		case 4://头删
    53. 			SeqListPopFront(&slist);
    54. 			printf("头删，删除成功!\n");
    55. 			break;
    56. 		case 5://选择插入
    57. 			printf("请输入需要插入的下标和元素:");
    58. 			scanf("%d%d", &a, &b);
    59. 			SeqListInsert(&slist, a, b);
    60. 			break;
    61. 		case 6://选择删除
    62. 			printf("请输入需要删除的元素的下标:");
    63. 			scanf("%d", &a);
    64. 			SeqListErase(&slist, a);
    65. 			break;
    66. 		case 7://查找元素
    67. 			printf("请输入需要查找的元素的下标:");
    68. 			scanf("%d", &a);
    69. 			SeqListFind(&slist, a);
    70. 			break;
    71. 		case 8://修改链表
    72. 			printf("请输入需要修改的下标和元素:");
    73. 			scanf("%d%d", &a, &b);
    74. 			SeqListModity(&slist, a, b);
    75. 			break;
    76. 		case 9://打印
    77. 			SeqListPrint(&slist);
    78. 			break;
    79. 		case -1://退出
    80. 			SeqListDestroy(&slist);//销毁空间
    81. 			break;
    82. 		default:
    83. 			printf("输入错误，请重新输入！\n");
    84. 			break;
    85. 		}
    86. 		system("pause");
    87. 		system("cls");
    88. 	}
    89.  
    90. 	return 0;
    91. }

    上述分模块写的代码为修改后的，添加了一些细节性的东西，下方完整代码为修改前的，懒得改了，可以正常使用。

  • 相关阅读:
    什么是EventEmitter？它在Node.js中有什么作用？
    机器学习中的特征选择：方法和 Python 示例
    使用Docker安装部署ElasticSearch和ElasticSearch-Head
    【LLM】提示工程技术提炼精华分享
    Windows内的Ubuntu虚拟机安装docker
    SVM算法原理解读
    shell脚本处理日志转化为JsonArray
    【深度学习】图像修复的一些模型
    新手使用vue引入cesium
    交通流的微观模型（Matlab代码实现）
  • 原文地址：https://blog.csdn.net/m0_52094687/article/details/126881530