• 顺序表详解（SeqList）

    本文使用C语言进行顺序表的代码实现。

    博主将使用代码和相关知识相结合的方式进行讲解，简单易懂，懵懂的大学生一听就会~

    顺序表是一种线性表的存储结构，它将数据元素存储在一段连续的存储空间中，每个元素占据一个存储单元，并按照逻辑顺序依次存放。顺序表可以采用数组来实现，通过数组的下标来表示元素在顺序表中的位置，从而实现对元素的快速访问和操作。

    一、顺序表的定义

    线性表是一种基本的数据结构，它是由一组相同类型的数据元素组成的有序序列。线性表的特点是元素之间的关系是线性的，即每个元素都有一个唯一的索引（也称为位置），并且可以通过索引访问元素。

    线性表有两种常见的实现方式：顺序表和链表。顺序表是使用一组连续的内存空间来存储元素，而链表则是使用一组离散的内存空间来存储元素，并通过指针将它们连接起来。

    本文讲解顺序表的代码实现。

    二、顺序表的实现

    我们使用多文件的方法来进行顺序表的实现。

    • SeqList.h用存放需要使用的头文件及声明函数
    • SeqList.c用来实现对于顺序表的操作函数
    • test用来进行顺序表的功能测试和使用

    1.顺序表的初始化

    1. //结构体创建
    2. typedef int SQDataType;
    3.  
    4. typedef struct SeqList
    5. {
    6. 	SQDataType* a;
    7. 	int size;     // 有效数据的个数
    8. 	int capacity; // 容量
    9. }SL;
    10.  
    11.  
    12. //顺序表初始化
    13. void SeqListInit(SL* ps)
    14. {
    15. 	ps->a = NULL;
    16. 	ps->size = 0;
    17. 	ps->capacity = 0;
    18. }

    首先创建一个结构体用来存放一个指针a，数据个数和顺序表的容量。

    2.设置修改检查函数

    1. //作为每次增添时的检查函数，如果顺序表的存储满了就进行扩容
    2. void SeqListCheckCapacity(SL* ps)
    3. {
    4. 	// 满了就要扩容
    5. 	if (ps->size == ps->capacity)
    6. 	{
    7. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    8. 		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
    9. 		if (tmp == NULL)
    10. 		{
    11. 			printf("realloc fail\n");
    12. 			exit(-1);
    13. 		}
    14. 		else
    15. 		{
    16. 			ps->a = tmp;
    17. 			ps->capacity = newcapacity;
    18. 		}
    19. 	}
    20. }

     该函数用于检查顺序表（a）是否大小足够进行添加数据，如果大小为0那么将空间设置为4，如果不够用即用realloc扩容到原大小的二倍。，之后再对相关数值进行修改。

    3.从头部插入数据

    1. void SeqListPushFront(SL* ps, SQDataType x)
    2. {
    3. 	SeqListCheckCapacity(ps);
    4.  
    5. 	int end = ps->size - 1;
    6. 	while (end >= 0)
    7. 	{
    8. 		ps->a[end + 1] = ps->a[end];
    9. 		--end;
    10. 	}
    11.  
    12. 	ps->a[0] = x;
    13. 	ps->size++;
    14.  
    15. }

    头插的方法相当于是将整个顺序表向后挪动一位，最后将第一个位置空下然后插入数据。但是挪动的顺序是从后往前挪动，如果是从前往后的话就会将数据覆盖，从而无法正常插入。

    4.从尾部插入数据

    1. void SeqListPushBack(SL* ps, SQDataType x)
    2. {
    3. 	SeqListCheckCapacity(ps);
    4.  
    5. 	ps->a[ps->size] = x;
    6. 	ps->size++;
    7.  
    8. }

    尾插就是直接向顺序表最后添加数据。

    5.指定位置插入数据

    1. void SeqListInsert(SL* ps, int pos, SQDataType x)
    2. {
    3. 	assert(pos <= ps->size);
    4. 	SeqListCheckCapacity(ps);
    5.  
    6. 	int end = ps->size - 1;
    7. 	while (end >= pos)
    8. 	{
    9. 		ps->a[end + 1] = ps->a[end];
    10. 		--end;
    11. 	}
    12. 	//将pos位置及之后全部向后移动一位，然后再pos位置上插入x
    13. 	ps->a[pos] = x;
    14. 	ps->size++;
    15. }

    关于assert断言相关知识如果想深入学习可以点击这段话跳转至博主的另一篇博客~

    首先使用assert断言进行一个条件判断，确保插入的位置合法。之后的移动数据位置的操作和头插的方法类似，将pos位置和之后的数据全部向后移动一个位置，然后再在pos这个下标的位置上添加数据。

    6.从头部删除数据

    1. void SeqListPopFront(SL* ps)
    2. {
    3. 	assert(ps->size > 0);
    4.  
    5. 	
    6. 	int start = 1;
    7. 	while (start < ps->size)
    8. 	{
    9. 		ps->a[start - 1] = ps->a[start];
    10. 		++start;
    11. 	}
    12. 	ps->size--;
    13. }

    代码实现的操作就是将第一个位置上的位置进行覆盖，用第一个之后的数据逐一将前面一个的数据进行覆盖，从而达到删除第一个数据的效果。最后将size进行修改。

    7.从尾部删除数据

    1. void SeqListPopBack(SL* ps)
    2. {
    3. 	assert(ps->size > 0);
    4.  
    5. 	ps->size--;
    6. }

    直接将顺序表的size进行-1就可以实现删除最后一个数据的操作。

    8.指定位置删除数据

    1. void SeqListErase(SL* ps, int pos)
    2. {
    3. 	assert(pos < ps->size);
    4. 	int start = pos + 1;
    5. 	while (start < ps->size)
    6. 	{
    7. 		ps->a[start - 1] = ps->a[start];
    8. 		++start;
    9. 	}
    10. 	ps->size--;
    11. }

    操作与头删类似，先设置start的数值为要删除的那个下标，然后将start之后的数据依次向前挪动覆盖数据实现在该指定位置的数据删除。

    9.指定位置修改数据

    1. void SeqListModity(SL* ps, int pos, SQDataType x)
    2. {
    3. 	assert(pos < ps->size);
    4. 	ps->a[pos] = x;
    5. }

    修改数据的操作十分简单，找到该位置的下标然后进行修改即可完成操作。

    10.查找数据

    1. int SeqListFind(SL* ps, SQDataType 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.  
    11. 	return -1;
    12. }

    遍历顺序表，逐个进行对比，与要查找的数据相同时返回该数据位置的下标，未找到返回-1.

    三、整体程序代码展现

    因为指定位置插入数据的函数和指定位置删除数据的函数可以完成头插尾插，头删尾删的操作，所以在程序中直接使用这两个插入方法进行头尾的操作减少了代码量。

    在test.c中通过简单的菜单和分支操作可以对顺序表进行简单的操作。

    SeqList.h

    1. #pragma once
    2.  
    3. #define _CRT_SECURE_NO_WARNINGS 1
    4. #include
    5. #include
    6. #include 
    7. #include 
    8.  
    9.  
    10. // 增强程序可维护性
    11. typedef int SQDataType;
    12. // 动态的
    13. typedef struct SeqList
    14. {
    15. 	SQDataType* a;
    16. 	int size;     // 有效数据的个数
    17. 	int capacity; // 容量
    18. }SL;
    19.  
    20. //typedef struct SeqList SL;
    21.  
    22. // 增删查改等接口函数
    23. void SeqListInit(SL* ps);
    24. void SeqListPrint(SL* ps);
    25. void SeqListDestory(SL* ps);
    26.  
    27. // 头插 尾插 头删 尾删
    28. void SeqListPushBack(SL* ps, SQDataType x);
    29. void SeqListPushFront(SL* ps, SQDataType x);
    30. void SeqListPopBack(SL* ps);
    31. void SeqListPopFront(SL* ps);
    32. void SeqListInsert(SL* ps, int pos, SQDataType x);
    33. void SeqListErase(SL* ps, int pos);
    34.  
    35. int SeqListFind(SL* ps, SQDataType x);
    36. void SeqListModity(SL* ps, int pos, SQDataType x);

    SeqList.c

    1. #include "SeqList.h"
    2.  
    3. // 增删查改等接口函数
    4.  
    5. //初始化数组
    6. void SeqListInit(SL* ps)
    7. {
    8. 	ps->a = NULL;
    9. 	ps->size = 0;
    10. 	ps->capacity = 0;
    11. }
    12.  
    13. //清除内存
    14. void SeqListDestory(SL* ps)
    15. {
    16. 	free(ps->a);
    17. 	ps->a = NULL;
    18. 	ps->capacity = ps->size = 0;
    19. }
    20.  
    21. //作为每次增添时的检查函数，如果顺序表的存储满了就进行扩容
    22. void SeqListCheckCapacity(SL* ps)
    23. {
    24. 	// 满了就要扩容
    25. 	if (ps->size == ps->capacity)
    26. 	{
    27. 		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
    28. 		SQDataType* tmp = (SQDataType*)realloc(ps->a, newcapacity * sizeof(SQDataType));
    29. 		if (tmp == NULL)
    30. 		{
    31. 			printf("realloc fail\n");
    32. 			exit(-1);
    33. 		}
    34. 		else
    35. 		{
    36. 			ps->a = tmp;
    37. 			ps->capacity = newcapacity;
    38. 		}
    39. 	}
    40. }
    41.  
    42. // 头插 尾插 头删 尾删
    43. void SeqListPushBack(SL* ps, SQDataType x)
    44. {
    45. 	/*SeqListCheckCapacity(ps);
    47. 	ps->a[ps->size] = x;
    48. 	ps->size++;*/
    49.  
    50. 	SeqListInsert(ps, ps->size, x);
    51. }
    52.  
    53. void SeqListPushFront(SL* ps, SQDataType x)
    54. {
    55. 	//SeqListCheckCapacity(ps);
    56.  
    57. 	 1、初始条件
    58. 	 2、结束条件
    59. 	 3、迭代过程
    60. 	//int end = ps->size - 1;
    61. 	//while (end >= 0)
    62. 	//{
    63. 	//	ps->a[end + 1] = ps->a[end];
    64. 	//	--end;
    65. 	//}
    66.  
    67. 	//ps->a[0] = x;
    68. 	//ps->size++;
    69.  
    70. 	SeqListInsert(ps, 0, x);
    71.  
    72. }
    73.  
    74. void SeqListPopBack(SL* ps)
    75. {
    76. 	//assert(ps->size > 0);
    77.  
    78. 	ps->a[ps->size - 1] = 0;
    79. 	//ps->size--;
    80. 	SeqListErase(ps, ps->size - 1);
    81. }
    82.  
    83. void SeqListPopFront(SL* ps)
    84. {
    85. 	assert(ps->size > 0);
    86.  
    87. 	/*
    88. 	int start = 1;
    89. 	while (start < ps->size)
    90. 	{
    91. 		ps->a[start - 1] = ps->a[start];
    92. 		++start;
    93. 	}
    94. 	ps->size--;*/
    95. 	SeqListErase(ps, 0);
    96. }
    97.  
    98. void SeqListInsert(SL* ps, int pos, SQDataType x)
    99. {
    100. 	assert(pos <= ps->size);
    101. 	SeqListCheckCapacity(ps);
    102.  
    103. 	int end = ps->size - 1;
    104. 	while (end >= pos)
    105. 	{
    106. 		ps->a[end + 1] = ps->a[end];
    107. 		--end;
    108. 	}
    109. 	//将pos位置及之后全部向后移动一位，然后再pos位置上插入x
    110. 	ps->a[pos] = x;
    111. 	ps->size++;
    112. }
    113.  
    114. void SeqListErase(SL* ps, int pos)
    115. {
    116. 	assert(pos < ps->size);
    117. 	int start = pos + 1;
    118. 	while (start < ps->size)
    119. 	{
    120. 		ps->a[start - 1] = ps->a[start];
    121. 		++start;
    122. 	}
    123. 	ps->size--;
    124. }
    125.  
    126. int SeqListFind(SL* ps, SQDataType x)
    127. {
    128. 	for (int i = 0; i < ps->size; ++i)
    129. 	{
    130. 		if (ps->a[i] == x)
    131. 		{
    132. 			return i;
    133. 		}
    134. 	}
    135.  
    136. 	return -1;
    137. }
    138.  
    139. //修改pos位置上的值为x
    140. void SeqListModity(SL* ps, int pos, SQDataType x)
    141. {
    142. 	assert(pos < ps->size);
    143. 	ps->a[pos] = x;
    144. }
    145.  
    146. void SeqListPrint(SL* ps)
    147. {
    148. 	for (int i = 0; i < ps->size; ++i)
    149. 	{
    150. 		printf("%d ", ps->a[i]);
    151. 	}
    152. 	printf("\n");
    153. }

    test.c

    1. #include "SeqList.h"
    2.  
    3. void TestSeqList1()
    4. {
    5. 	SL sl;
    6. 	SeqListInit(&sl);
    7. 	SeqListPushBack(&sl, 1);
    8. 	SeqListPushBack(&sl, 2);
    9. 	SeqListPushBack(&sl, 3);
    10. 	SeqListPushBack(&sl, 4);
    11. 	SeqListPushBack(&sl, 5);
    12. 	SeqListPushBack(&sl, 6);
    13. 	SeqListPushBack(&sl, 7);
    14. 	SeqListPushBack(&sl, 8);
    15. 	SeqListPushBack(&sl, 9);
    16. 	SeqListPushBack(&sl, 10);
    17. 	SeqListPushBack(&sl, 11);
    18. 	SeqListPushBack(&sl, 11);
    19. 	SeqListPushBack(&sl, 11);
    20. 	SeqListPushBack(&sl, 11);
    21. 	SeqListPushBack(&sl, 11);
    22. 	SeqListPushBack(&sl, 11);
    23. 	SeqListPushBack(&sl, 11);
    24. 	SeqListPushBack(&sl, 11);
    25. 	SeqListPushBack(&sl, 11);
    26. 	SeqListPushBack(&sl, 11);
    27. 	SeqListPushBack(&sl, 11);
    28. 	SeqListPushBack(&sl, 11);
    29. 	SeqListPushBack(&sl, 11);
    30. 	SeqListPushBack(&sl, 11);
    31. 	SeqListPushBack(&sl, 11);
    32. 	SeqListPushBack(&sl, 11);
    33. 	SeqListPushBack(&sl, 11);
    34. 	SeqListPrint(&sl);
    35.  
    36. 	SeqListDestory(&sl);
    37. }
    38.  
    39. void TestSeqList2()
    40. {
    41. 	SL sl;
    42. 	SeqListInit(&sl);
    43. 	SeqListPushFront(&sl, 1);
    44. 	SeqListPushFront(&sl, 2);
    45. 	SeqListPushFront(&sl, 3);
    46. 	SeqListPushFront(&sl, 4);
    47. 	SeqListPushFront(&sl, 5);
    48. 	SeqListPushFront(&sl, 6);
    49. 	SeqListPrint(&sl);
    50.  
    51. 	SeqListPopBack(&sl);
    52. 	SeqListPopBack(&sl);
    53. 	SeqListPopBack(&sl);
    54. 	SeqListPrint(&sl);
    55.  
    56. 	SeqListPopFront(&sl);
    57. 	SeqListPrint(&sl);
    58.  
    59. 	SeqListDestory(&sl);
    60. }
    61.  
    62. void TestSeqList3()
    63. {
    64. 	SL sl;
    65. 	SeqListInit(&sl);
    66. 	SeqListPushFront(&sl, 1);
    67. 	SeqListPushFront(&sl, 2);
    68. 	SeqListPushFront(&sl, 3);
    69. 	SeqListPushFront(&sl, 4);
    70. 	SeqListPushFront(&sl, 5);
    71. 	SeqListPushFront(&sl, 6);
    72. 	SeqListPrint(&sl);
    73. 	SeqListInsert(&sl, 1, 20);
    74. 	SeqListPrint(&sl);
    75.  
    76. 	SeqListErase(&sl, 1);
    77. 	SeqListPrint(&sl);
    78.  
    79. 	SeqListDestory(&sl);
    80. }
    81.  
    82. void menu()
    83. {
    84. 	printf("**********************************************\n");
    85. 	printf("1.尾插数据， 2.头插数据\n");
    86. 	printf("3.尾删数据， 4.头删数据\n");
    87. 	printf("5.打印数据，-1.退出\n");
    88. 	printf("**********************************************\n");
    89. 	printf("请输入你操作选项:");
    90. }
    91.  
    92. int main()
    93. {
    94. 	SL s;
    95. 	SeqListInit(&s);
    96. 	int option = 0;
    97. 	int x = 0;
    98. 	while (option != -1)
    99. 	{
    100. 		menu();
    101. 		scanf("%d", &option);
    102. 		switch (option)
    103. 		{
    104. 		case 1:
    105. 			printf("请输入你要插入的数据，以-1结束\n");
    106. 			do {
    107. 				scanf("%d", &x);
    108. 				if (x != -1)
    109. 				{
    110. 					SeqListPushBack(&s, x);
    111. 				}
    112. 			} while (x != -1);
    113. 			break;
    114. 		case 2:
    115. 			break;
    116. 		case 3:
    117. 			break;
    118. 		case 4:
    119. 			break;
    120. 		case 5:
    121. 			SeqListPrint(&s);
    122. 			break;
    123. 		default:
    124. 			break;
    125. 		}
    126. 	}
    127.  
    128. 	SeqListDestory(&s);
    129.  
    130. 	return 0;
    131. }

    那么本篇博客到此就结束了，如果可以帮助到你是博主的荣幸！

  • 相关阅读:
    Socks5代理技术：驱动数字化时代跨界发展的利器
    php生成器
    应用开发平台能力扩展——集成echarts组件实现图表展现能力
    C++之IO流
    Ansible如何使用lookup插件模板化外部数据
    宇宙的尽头是编制？七成毕业生进体制，清北2021届学子就业报告出炉
    算法提升（一）二分法
    【微信小程序】网络请求
    Golang zip压缩及加密
    Oracle（15）Managing Users
  • 原文地址：https://blog.csdn.net/SDFsoul/article/details/136197107