• 顺序表漫谈

    目录

    ​编辑

    1.线性表

    2.顺序表

    2.1概念及结构

    2.2接口实现

    1.顺序表的动态存储

    2.顺序表初始化

    3.顺序表销毁

    4.顺序表增容

    5.顺序表头插

    6.顺序表尾插

    7.顺序表头删

    8.顺序表尾删

    9.顺序表打印

    10.顺序表在任意下标位置插入数据

    11.顺序表删除任意下标位置的值

    12.顺序表查找

    2.3菜单

    3.源码

    1.线性表

    • 线性表（linear list）是n个具有相同特性的数据元素的有限序列。
    • 线性表是一种在实际中广泛使用的数据结构，常见的线性表有：顺序表、链表、栈、队列、字符串...
    • 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。


     

    2.顺序表

    2.1概念及结构

    顺序表是一种线性表的实现方式，它通过一段物理地址连续的存储单元依次存储数据元素，数据元素之间的逻辑关系通过元素在内存中的相对位置来表示，一般情况下采用数组存储。在数组上完成数据的增删查改。

    顺序表简单来说就是一个数组，它和数组的唯一区别就是里边的数据只能从头开始连续存储。

    🌵顺序表一般可以分为：

    1.静态顺序表：使用定长数组存储元素

    2.动态顺序表：使用动态开辟的数组存储元素

    2.2接口实现

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

    1.顺序表的动态存储

    要实现动态的顺序表，我们首先得有一个指向数组的指针，因为内存是malloc或者realloc出来的。还得有一个size，知道到底存了多少个数据，以及得有一个capacity，用来记录空间容量。

    1. typedef int SLDataType;
    2.  
    3. typedef struct SeqList
    4. {
    5.     assert(psl);
    6.  
    7. 	SLDataType* arr; //指向动态开辟的数组
    8. 	int size;        //有效数据个数，看作下标时，它指向最后一个数据的下一个位置
    9. 	int capacity;    //空间容量
    10. }SeqList;

    2.顺序表初始化

    因为形参是实参的一份临时拷贝，改变形参的值不会影响实参，所以传值的时候要传地址，形参用指针接收。

    1. //顺序表初始化
    2. void SeqListInit(SeqList* psl)
    3. {
    4. 	assert(psl);
    5.  
    6. 	psl->arr = NULL;
    7. 	psl->size = 0;
    8. 	psl->capacity = 0;
    9. }

    3.顺序表销毁

    1. //顺序表销毁
    2. void SeqListDestory(SeqList* psl)
    3. {
    4. 	assert(psl);
    5.  
    6. 	if (psl->arr != NULL)
    7. 	{
    8. 		free(psl->arr);
    9. 		psl->arr = NULL;
    10. 		psl->size = 0;
    11. 		psl->capacity = 0;
    12. 	}
    13. }

    4.顺序表增容

    即检查空间，如果满了，就进行增容。因为头插和尾插都需要增容，所以我们把它成一个公共的函数，方便管理。 关于动态内存开辟有不清楚的铁子们可以看这篇博客：动态内存管理详解

    1. //增容
    2. void SeqListCheckCapacity(SeqList* psl)
    3. {
    4. 	assert(psl);
    5.  
    6. 	if (psl->size == psl->capacity)
    7. 	{
    8. 		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    9. 		//防止扩容失败将原来的空间给覆盖掉，所以用一个临时变量来接收
    10. 		SLDataType* tmp = (SLDataType*)realloc(psl->arr, sizeof(SLDataType) * newCapacity);
    11. 		if (tmp == NULL)
    12. 		{
    13. 			perror("realloc");
    14. 			return;
    15. 		}
    16. 		psl->arr = tmp;
    17. 		psl->capacity = newCapacity;
    18. 	}
    19. }

    5.顺序表头插

    要想在头部插入数据，必须将所有的数据先向后挪动一个位置，然后将要插入的数据放在第一个位置。我们可以先定义一个变量end，让它等于最后一个数据，然后利用while循环将所有的数据向后挪动一个位置，再将数据插入头部，然后让数据个数size+1。

    1. //头插
    2. void SeqListPushFront(SeqList* psl, SLDataType x)
    3. {
    4. 	assert(psl);
    5.  
    6. 	SeqListCheckCapacity(psl);
    7.  
    8. 	//挪动数据
    9. 	int end = psl->size - 1;
    10. 	while (end >= 0)
    11. 	{
    12. 		psl->arr[end + 1] = psl->arr[end];
    13. 		end--;
    14. 	}
    15. 	psl->arr[0] = x;
    16. 	psl->size++;
    17. }

    6.顺序表尾插

    尾插相对来说比较简单，如果空间不够，增容之后直接将要插入的数据放在尾部即可，然后将数据个数size+1。

    1. //尾插
    2. void SeqListPushBack(SeqList* psl, SLDataType x)
    3. {
    4. 	assert(psl);
    5.  
    6. 	//增容
    7. 	SeqListCheckCapacity(psl);
    8.  
    9. 	psl->arr[psl->size] = x;
    10. 	psl->size++;
    11. }

    7.顺序表头删

    头删时我们采用的方法还是挪动数据，但是要从前面开始挪动，因为如果从后往前挪的话会将前面的数据给覆盖掉。先定义一个变量begin，让它等于1，然后利用while循环将所有的数据向前挪动一个位置（让后一个数据将前一个数据覆盖掉），直到begin小于size就跳出循环，然后让数据个数size-1。

    1. //头删
    2. void SeqListPopFront(SeqList* psl)
    3. {
    4. 	assert(psl);
    5.  
    6. 	//暴力检查
    7. 	assert(psl->size);
    8.  
    9. 	int begin = 1;
    10. 	while (begin < psl->size)
    11. 	{
    12. 		psl->arr[begin - 1] = psl->arr[begin];
    13. 		begin++;
    14. 	}
    15. 	psl->size--;
    16. }

    8.顺序表尾删

    尾删时我们只需让有效数据 size-- 就行，但是必须进行检查看顺序表是否为空，因为如果为空，后面我们在头插时就会出现问题。

    1. //尾删
    2. void SeqListPopBack(SeqList* psl)
    3. {
    4. 	assert(psl);
    5.  
    6. 	//若顺序表为空，则进行检查
    7. 	//温柔的检查
    8. 	/*if (psl->size == 0)
    9. 	{
    10. 		return;
    11. 	}*/
    12.  
    13. 	//暴力检查
    14. 	assert(psl->size > 0);
    15.  
    16. 	psl->size--;
    17. }

    9.顺序表打印

    1. //顺序表打印
    2. void SeqListPrint(SeqList* psl)
    3. {
    4. 	assert(psl);
    5.  
    6. 	for (int i = 0; i < psl->size; i++)
    7. 	{
    8. 		printf("%d ", psl->arr[i]);
    9. 	}
    10. 	printf("\n");
    11. }

    10.顺序表在任意下标位置插入数据

    首先要保证指针不为空以及pos位置的合法性。然后定义变量end，让它指向最后一个数据的位置，通过while循环将 pos到end 位置的值向后挪动一个位置，将要插入的数据放入pos位置，再将size+1。

    1. //顺序表在任意下标位置插入数据
    2. void SeqListInsert(SeqList* psl, int pos, SLDataType x)
    3. {
    4. 	assert(psl);
    5. 	assert(pos >= 0 && pos <= psl->size);
    6.  
    7. 	int end = psl->size - 1;
    8. 	while (end >= pos)
    9. 	{
    10. 		psl->arr[end + 1] = psl->arr[end];
    11. 		end--;
    12. 	}
    13. 	psl->arr[pos] = x;
    14. 	psl->size++;
    15. }

    11.顺序表删除任意下标位置的值

    1. //顺序表删除任意下标位置的值
    2. void SeqListErase(SeqList* psl, int pos)
    3. {
    4. 	assert(psl);
    5. 	assert(pos >= 0 && pos < psl->size);
    6.     
    7.     //挪动数据
    8. 	int begin = pos + 1;
    9. 	while (begin < psl->size)
    10. 	{
    11. 		psl->arr[begin - 1] = psl->arr[begin];
    12. 		begin++;
    13. 	}
    14. 	psl->size--;
    15. }

    12.顺序表查找

    在顺序表中查找数据，如果找到了，就返回下标；如果没有找到，则返回-1。

    1. //顺序表查找
    2. int SeqListFind(SeqList* psl, SLDataType x)
    3. {
    4. 	assert(psl);
    5.  
    6. 	for (int i = 0; i < psl->size; i++)
    7. 	{
    8. 		if (psl->arr[i] == x)
    9. 		{
    10. 			return i;
    11. 			break;
    12. 		}
    13. 	}
    14. 	return -1;
    15. }

    2.3菜单

    1. void menu()
    2. {
    3. 	printf("*************************************\n");
    4. 	printf("***   1.头插数据    2.尾插数据    ***\n");
    5. 	printf("***   3.头删数据    4.尾删数据    ***\n");
    6. 	printf("***   5.查找数据    6.打印顺序表  ***\n");
    7. 	printf("***   7.在任意下标位置插入数据    ***\n");
    8. 	printf("***   8.删除任意下标位置的数据    ***\n");
    9. 	printf("***   0.退出系统                  ***\n");
    10. 	printf("*************************************\n");
    11. }
    12.  
    13. void Test()
    14. {
    15. 	SeqList sl;
    16. 	SeqListInit(&sl);//初始化
    17. 	int x = 0, pos = 0;
    18. 	int input = 0;
    19. 	do
    20. 	{
    21. 		printf("欢迎来到顺序表系统！\n");
    22. 		menu();
    23. 		printf("请输入你的选择:>");
    24. 		scanf("%d", &input);
    25. 		switch (input)
    26. 		{
    27. 		case 1:
    28. 			printf("请输入你要头插的数据：\n");
    29. 			scanf("%d", &x);
    30. 			SeqListPushFront(&sl, x);
    31. 			printf("头插成功！\n");
    32. 			break;
    33. 		case 2:
    34. 			printf("请输入你要尾插的数据：\n");
    35. 			scanf("%d", &x);
    36. 			SeqListPushBack(&sl, x);
    37. 			printf("尾插成功！\n");
    38. 			break;
    39. 		case 3:
    40. 			SeqListPopFront(&sl);
    41. 			printf("头删成功！\n");
    42. 			break;
    43. 		case 4:
    44. 			SeqListPopBack(&sl);
    45. 			printf("尾删成功！\n");
    46. 			break;
    47. 		case 5:
    48. 			printf("请输入你要查找的数据(查找成功则返回下标， 负责返回-1)：\n");
    49. 			scanf("%d", &x);
    50. 			int pos = SeqListFind(&sl, x);
    51. 			printf("%d\n", pos);
    52. 			break;
    53. 		case 6:
    54. 			printf("顺序表目前的数据为：\n");
    55. 			SeqListPrint(&sl);
    56. 			break;
    57. 		case 7:
    58. 			printf("请输入你要插入的数据：");
    59. 			scanf("%d", &x);
    60. 			printf("请输入你要插入数据的下标(下标从0开始)：");
    61. 			scanf("%d", &pos);
    62. 			SeqListInsert(&sl, pos, x);
    63. 			printf("插入数据成功！\n");
    64. 			break;
    65. 		case 8:
    66. 			printf("请输入你要删除数据的下标：");
    67. 			scanf("%d", &pos);
    68. 			SeqListErase(&sl, pos);
    69. 			printf("删除成功！\n");
    70. 			break;
    71. 		case 0:
    72. 			printf("退出系统！\n");
    73. 			break;
    74. 		default:
    75. 			printf("选择错误，请重新选择！\n");
    76. 			break;
    77. 		}
    78. 	} while (input);
    79.  
    80. 	SeqListDestory(&sl);//销毁
    81. }

    3.源码

    🌻test.c

    1. #include "SeqList.h"
    2.  
    3. void menu()
    4. {
    5. 	printf("*************************************\n");
    6. 	printf("***   1.头插数据    2.尾插数据    ***\n");
    7. 	printf("***   3.头删数据    4.尾删数据    ***\n");
    8. 	printf("***   5.查找数据    6.打印顺序表  ***\n");
    9. 	printf("***   7.在任意下标位置插入数据    ***\n");
    10. 	printf("***   8.删除任意下标位置的数据    ***\n");
    11. 	printf("***   0.退出系统                  ***\n");
    12. 	printf("*************************************\n");
    13. }
    14.  
    15. void Test()
    16. {
    17. 	SeqList sl;
    18. 	SeqListInit(&sl);
    19. 	int x = 0, pos = 0;
    20. 	int input = 0;
    21. 	do
    22. 	{
    23. 		printf("欢迎来到顺序表系统！\n");
    24. 		menu();
    25. 		printf("请输入你的选择:>");
    26. 		scanf("%d", &input);
    27. 		switch (input)
    28. 		{
    29. 		case 1:
    30. 			printf("请输入你要头插的数据：\n");
    31. 			scanf("%d", &x);
    32. 			SeqListPushFront(&sl, x);
    33. 			printf("头插成功！\n");
    34. 			break;
    35. 		case 2:
    36. 			printf("请输入你要尾插的数据：\n");
    37. 			scanf("%d", &x);
    38. 			SeqListPushBack(&sl, x);
    39. 			printf("尾插成功！\n");
    40. 			break;
    41. 		case 3:
    42. 			SeqListPopFront(&sl);
    43. 			printf("头删成功！\n");
    44. 			break;
    45. 		case 4:
    46. 			SeqListPopBack(&sl);
    47. 			printf("尾删成功！\n");
    48. 			break;
    49. 		case 5:
    50. 			printf("请输入你要查找的数据(查找成功则返回下标， 负责返回-1)：\n");
    51. 			scanf("%d", &x);
    52. 			int pos = SeqListFind(&sl, x);
    53. 			printf("%d\n", pos);
    54. 			break;
    55. 		case 6:
    56. 			printf("顺序表目前的数据为：\n");
    57. 			SeqListPrint(&sl);
    58. 			break;
    59. 		case 7:
    60. 			printf("请输入你要插入的数据：");
    61. 			scanf("%d", &x);
    62. 			printf("请输入你要插入数据的下标(下标从0开始)：");
    63. 			scanf("%d", &pos);
    64. 			SeqListInsert(&sl, pos, x);
    65. 			printf("插入数据成功！\n");
    66. 			break;
    67. 		case 8:
    68. 			printf("请输入你要删除数据的下标：");
    69. 			scanf("%d", &pos);
    70. 			SeqListErase(&sl, pos);
    71. 			printf("删除成功！\n");
    72. 			break;
    73. 		case 0:
    74. 			printf("退出系统！\n");
    75. 			break;
    76. 		default:
    77. 			printf("选择错误，请重新选择！\n");
    78. 			break;
    79. 		}
    80. 	} while (input);
    81.  
    82. 	SeqListDestory(&sl);
    83. }
    84.  
    85. int main()
    86. {
    87. 	Test();
    88.  
    89. 	return 0;
    90. }

    🌻SeqList.h

    1. #pragma once
    2. #include 
    3. #include 
    4. #include 
    5.  
    6. typedef int SLDataType;
    7.  
    8. typedef struct SeqList
    9. {
    10. 	SLDataType* arr;//指向动态开辟的数组
    11. 	int size;     //有效数据
    12. 	int capacity; //空间容量
    13. }SeqList;
    14.  
    15. //顺序表初始化
    16. void SeqListInit(SeqList* psl);
    17. //顺序表销毁
    18. void SeqListDestory(SeqList* psl);
    19. //顺序表打印
    20. void SeqListPrint(SeqList* psl);
    21. //增容
    22. void SeqListCheckCapacity(SeqList* psl);
    23.  
    24. //头插
    25. void SeqListPushFront(SeqList* psl, SLDataType x);
    26. //尾插
    27. void SeqListPushBack(SeqList* psl, SLDataType x);
    28. //头删
    29. void SeqListPopFront(SeqList* psl);
    30. //尾删
    31. void SeqListPopBack(SeqList* psl);
    32.  
    33. //顺序表在任意位置插入数据
    34. void SeqListInsert(SeqList* psl, int pos, SLDataType x);
    35. //顺序表删除任意位置的值
    36. void SeqListErase(SeqList* psl, int pos);
    37.  
    38. //顺序表查找
    39. int SeqListFind(SeqList* psl, SLDataType x);

    🌻SeqList.c

    1. #include "SeqList.h"
    2.  
    3. //顺序表初始化
    4. void SeqListInit(SeqList* psl)
    5. {
    6. 	assert(psl);
    7.  
    8. 	psl->arr = NULL;
    9. 	psl->size = 0;
    10. 	psl->capacity = 0;
    11. }
    12.  
    13. //顺序表销毁
    14. void SeqListDestory(SeqList* psl)
    15. {
    16. 	assert(psl);
    17.  
    18. 	if (psl->arr != NULL)
    19. 	{
    20. 		free(psl->arr);
    21. 		psl->arr = NULL;
    22. 		psl->size = 0;
    23. 		psl->capacity = 0;
    24. 	}
    25. }
    26.  
    27. //顺序表打印
    28. void SeqListPrint(SeqList* psl)
    29. {
    30. 	assert(psl);
    31.  
    32. 	for (int i = 0; i < psl->size; i++)
    33. 	{
    34. 		printf("%d ", psl->arr[i]);
    35. 	}
    36. 	printf("\n");
    37. }
    38.  
    39. //增容
    40. void SeqListCheckCapacity(SeqList* psl)
    41. {
    42. 	assert(psl);
    43.  
    44. 	if (psl->size == psl->capacity)
    45. 	{
    46. 		int newCapacity = psl->capacity == 0 ? 4 : psl->capacity * 2;
    47. 		//防止扩容失败将原来的空间给覆盖掉，所以用一个临时变量来接收
    48. 		SLDataType* tmp = (SLDataType*)realloc(psl->arr, sizeof(SLDataType) * newCapacity);
    49. 		if (tmp == NULL)
    50. 		{
    51. 			perror("realloc");
    52. 			return;
    53. 		}
    54. 		psl->arr = tmp;
    55. 		psl->capacity = newCapacity;
    56. 	}
    57. }
    58.  
    59. //头插
    60. void SeqListPushFront(SeqList* psl, SLDataType x)
    61. {
    62. 	assert(psl);
    63. 	SeqListCheckCapacity(psl);
    64.  
    65. 	//挪动数据
    66. 	int end = psl->size - 1;
    67. 	while (end >= 0)
    68. 	{
    69. 		psl->arr[end + 1] = psl->arr[end];
    70. 		end--;
    71. 	}
    72. 	psl->arr[0] = x;
    73. 	psl->size++;
    74. }
    75.  
    76. //尾插
    77. void SeqListPushBack(SeqList* psl, SLDataType x)
    78. {
    79. 	assert(psl);
    80.  
    81. 	//增容
    82. 	SeqListCheckCapacity(psl);
    83.  
    84. 	psl->arr[psl->size] = x;
    85. 	psl->size++;
    86. }
    87. //头删
    88. void SeqListPopFront(SeqList* psl)
    89. {
    90. 	assert(psl);
    91.  
    92. 	//暴力检查
    93. 	assert(psl->size);
    94.  
    95. 	int begin = 1;
    96. 	while (begin < psl->size)
    97. 	{
    98. 		psl->arr[begin - 1] = psl->arr[begin];
    99. 		begin++;
    100. 	}
    101. 	psl->size--;
    102. }
    103.  
    104. //尾删
    105. void SeqListPopBack(SeqList* psl)
    106. {
    107. 	assert(psl);
    108.  
    109. 	//若顺序表为空，则进行检查
    110. 	
    111. 	//温柔的检查
    112. 	/*if (psl->size == 0)
    113. 	{
    114. 		return;
    115. 	}*/
    116. 	//暴力检查
    117. 	assert(psl->size);
    118.  
    119. 	psl->size--;
    120. }
    121.  
    122. //顺序表在任意下标位置插入数据
    123. void SeqListInsert(SeqList* psl, int pos, SLDataType x)
    124. {
    125. 	assert(psl);
    126. 	assert(pos >= 0 && pos <= psl->size);
    127.  
    128. 	int end = psl->size - 1;
    129. 	while (end >= pos)
    130. 	{
    131. 		psl->arr[end + 1] = psl->arr[end];
    132. 		end--;
    133. 	}
    134. 	psl->arr[pos] = x;
    135. 	psl->size++;
    136. }
    137.  
    138. //顺序表删除任意下标位置的值
    139. void SeqListErase(SeqList* psl, int pos)
    140. {
    141. 	assert(psl);
    142. 	assert(pos >= 0 && pos < psl->size);
    143.  
    144. 	int begin = pos + 1;
    145. 	while (begin < psl->size)
    146. 	{
    147. 		psl->arr[begin - 1] = psl->arr[begin];
    148. 		begin++;
    149. 	}
    150. 	psl->size--;
    151. }
    152.  
    153. //顺序表查找
    154. int SeqListFind(SeqList* psl, SLDataType x)
    155. {
    156. 	assert(psl);
    157.  
    158. 	for (int i = 0; i < psl->size; i++)
    159. 	{
    160. 		if (psl->arr[i] == x)
    161. 		{
    162. 			return i;
    163. 			break;
    164. 		}
    165. 	}
    166. 	return -1;
    167. }
  • 相关阅读:
    乌克兰的 IT 外包，为什么如此“发达”？
    探索Django路由规则(路由匹配、路由命名空间、HTML中的跳转与Django集成、路由传参以及后端重定向）
    简述CompletableFuture异步任务编排
    HNU-CSer的推免经历记录
    1、风行内容仓的增效之路 - 前言
    Unity之ShaderGraph如何实现积雪效果
    深度学习在胰腺医学影像中的应用综述
    思维+启发式合并
    element ui 里面只能输入input 数字 +限制长度
    Alibaba Nacos注册中心源码剖析
  • 原文地址：https://blog.csdn.net/weixin_65931202/article/details/136177367