C语言实现顺序表（图解增删查改+代码）

写在前面

源码在这里–>顺序表源码
顺序表是一种基本的数据结构，它是一种线性表，其元素在内存中是连续存储的。

本篇文章以c语言的形式实现了数据结构中的顺序表。顺序表分为静态和动态两个版本，静态版本是用数组来组织和存储数据的，这个版本的缺点是：空间给多了浪费，给少了不够用，下面是静态版本的定义：

#define N 50 //顺序表的容量
typedef int SlDataType;

struct SeqList
{
	SlDataType data[N];
	int size;//记录有效元素的个数
};
1
2
3
4
5
6
7
8

鉴于静态版本存在一定的缺陷，且实际用到的场景很少，因此这里就不实现静态的版本了。
动态版本的顺序表是通过malloc函数来动态申请一块连续的空间，刚开始空间给小一点，等空间不够了可以增容，因此动态版的顺序表能更加符合我们的需求，下面是动态版本的定义：

typedef struct Seqlist
{
	SlDataType* data;
	int size;//记录当前顺序表有效元素的个数
	int capacity;//记录当前顺序表的容量
}Seqlist;
1
2
3
4
5
6

该顺序表有三个成员变量，指针变量data是用来维护通过malloc函数动态申请的空间，size是用来记录当前顺序表中有效元素的个数，capacity是用来记录当前顺序表的容量。

1. 顺序表的初始化和销毁

1.1 顺序表的初始化(SLInit)

顺序表的初始化有多种方法，这里只是其中的一种，仅供参考。这里在初始化的时候给data分配了4个元素大小的空间，此时capacity就是4，size是指有效元素的个数，此时顺序表中没有元素，因此size等于0。代码如下：

void SLInit(Seqlist* psl)
{
	assert(psl);//检查参数的有效性
	SlDataType* tmp = malloc(sizeof(SlDataType)* 4);
	//判断是否成功申请空间
	if (tmp == NULL)
	{
		perror("SLInit()->malloc");
		return;
	}
	
	psl->data = tmp;
	psl->capacity = 4;
	psl->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

1.2 顺序表的销毁(SLDestroy)

由于data指向的空间是动态申请的，因此在程序结束之前，要将data指向的空间给释放，以避免造成内存泄漏，同时将data置为空指针，以避免野指针的问题。代码如下：

void SLDestroy(Seqlist* psl)
{
	assert(psl);//检查参数有效性
	
	free(psl->data);
	psl->data = NULL;
	psl->capacity = psl->size = 0;
}
1
2
3
4
5
6
7
8

顺序表是一种线性数据结构，它可以存储一组元素，并支持增加、删除、查找和修改元素的操作。下面详细介绍顺序表的增加（插入）、删除、查找和修改操作。

2. 插入数据

2.1 尾插数据(SLPushBack)

尾插数据的步骤如下：

1. 判断顺序表是否已满，如果满了要进行扩容操作。
   由于后面的头插，和在指定位置插入数据都需要来判断顺序表是否已满，因此这里直接封装一个函数用来检查顺序表的容量。
   代码如下：

static void CheckCapacity(Seqlist* psl)
{
	assert(psl);//检查参数的有效性
	if (psl->size == psl->capacity)
	{
		//采取2倍扩容的方式
		SlDataType* tmp = realloc(psl->data, sizeof(SlDataType)* psl ->capacity * 2);
		if (tmp == NULL)
		{
			perror("CheckCapacity()->realloc");
			return;
		}
		psl->data = tmp;
		psl->capacity = psl->capacity * 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2. 在插入位置放置新元素。
   

3. 更新顺序表的大小。

尾插一个元素的代码如下：

void SLPushBack(Seqlist* psl, SlDataType x)
{
	assert(psl);//检查参数的有效性
	//判断顺序表是否已满
	CheckCapacity(psl);
	//尾插数据

	psl->data[psl->size] = x;
	psl->size++;

}
1
2
3
4
5
6
7
8
9
10
11

2.2 头插数据(SLPushFront)

头插数据的步骤如下：

1. 判断顺序表是否已满，如果满了要进行扩容操作。
2. 从插入位置开始，依次将后续元素向后移动一个位置，以腾出空间。
3. 在插入位置放置新元素。
4. 更新顺序表的大小。

例如，在 {1,2,3,4} 的中头插元素 0，实现过程如下：

• 找到目标位置，如下图所示：
  

• 将元素 1 以及后续元素 2 、3、4 整体向后移动一个位置，如下图所示：
  

• 将新元素 0 放入腾出的位置，如下图所示：
  

代码如下：

void SLPushFront(Seqlist* psl, SlDataType x)
{
	assert(psl);//检查参数有效性

	//判断顺序表是否已满
	CheckCapacity(psl);
	//从后往前移动数据
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->data[end + 1] = psl->data[end];
		end--;
	}
	
	psl->data[0] = x;//将数据插入目标位置
	psl->size++;//更新顺序表有效元素个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.3 指定位置插入数据(SLInsert)

指定位置插入数据的步骤如下：

1. 检查插入位置的有效性，确保位置在合理范围内。
2. 判断顺序表是否已满，如果满了要进行扩容操作。
3. 从插入位置开始，依次将后续元素向后移动一个位置，以腾出空间。
4. 在插入位置放置新元素。
5. 更新顺序表的大小。

例如，在 {0,1,2,3,4,5,6,7} 的下标为 3 的位置上插入元素 8，实现过程如下：

• 找到目标位置，如下图所示：
  
• 将元素 3 以及后续元素 4 、5、6、7 整体向后移动一个位置，如下图所示：
  
• 将新元素 8 放入腾出的位置，如下图所示：
  

代码如下:

void SLInsert(Seqlist* psl, int pos, SlDataType x)
{
	assert(psl);//检查参数的有效性
	assert(pos >= 0 && pos <= psl->size);//检查插入位置的有效性

	//判断顺序表是否已满
	CheckCapacity(psl);

	//从后往前移动数据，直到挪动到pos位置
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->data[end + 1] = psl->data[end];
		end--;
	}
	
	psl->data[pos] = x;//将数据插入到指定位置
	psl->size++;//更新顺序表有效元素个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3. 删除数据

3.1 尾删数据(SLPopBack)

尾删数据的步骤如下：

1. 检查线性表是否为空，不为空在进行删除。
2. size代表当前有效元素的个数，直接将size - 1，就访问不到最后一个元素了，即达到了尾删数据的目的了。
   代码如下：

void SLPopBack(Seqlist* psl)
{
	assert(psl);//检查参数有效性
	assert(psl->size > 0);//判断线性表是否为空

	psl->size--;//尾删数据
}
1
2
3
4
5
6
7

3.2 头删数据(SLPopFront)

头删数据的步骤如下：

1. 检查线性表是否为空，不为空在进行删除。
2. 从删除位置开始，依次将后续元素向前移动一个位置，以填补删除的位置。
3. 更新顺序表的大小。
   例如，头删 {1,2,3,4} 中的 1，实现过程如下：

• 后续元素整体前移一个位置，会直接将目标元素覆盖以实现删除元素的目的。
  

代码如下：

void SLPopFront(Seqlist* psl)
{
	assert(psl);//检查参数有效性
	assert(psl->size > 0);//判断线性表是否为空

	//后续元素往前移动一个位置
	int start = 1;
	while (start < psl->size)
	{
		psl->data[start - 1] = psl->data[start];
		start++;
	}
	psl->size--;//更新顺序表有效元素个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.3 删除指定位置的数据(SLErase)

删除指定位置数据的步骤如下：

1. 检查线性表是否为空，不为空在进行删除。
2. 检查删除位置的有效性，确保位置在合理范围内。
3. 从删除位置开始，依次将后续元素向前移动一个位置，以填补删除的位置。
4. 更新顺序表的大小。

例如，在 {0,1,2,3,4,5,6,7} 中删除下标为3的元素，实现过程如下：

• 找到目标位置，如下图所示：
  

• 从删除位置开始，依次将后续元素向前移动一个位置，以填补删除的位置。
  

代码如下：

void SLErase(Seqlist* psl, int pos)
{
	assert(psl);//检查参数有效性
	assert(pos >= 0 && pos < psl->size);//检查位置的有效性(间接检查了判断线性表是否为空)
	
	//后续元素往前移动一个位置
	int start = pos + 1;
	while (start < psl->size)
	{
		psl->data[start - 1] = psl->data[start];
		start++;
	}
	psl->size--;//更新顺序表有效元素个数
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

4. 查找数据(SLFind)

查找元素的一般步骤：

1. 检查查找条件的有效性，确保条件合理。
2. 根据条件，从顺序表的头部开始逐个元素进行比较，直到找到满足条件的元素或者遍历整个顺序表。
3. 找到了返回元素的所在位置的下标， 找不到返回 -1。

代码如下：

void SLFind(Seqlist* psl, SlDataType x)
{
	assert(psl);//检查参数有效性

	for (int i = 0; i < psl->size; ++i)
	{
		if (psl->data[i] == x)
		{
			return i;
		}
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

5. 修改指定位置的元素(SLModify)

修改元素的一般步骤：

1. 检查修改位置的有效性，确保位置在合理范围内。
2. 更新指定位置的元素的值为新值。

代码如下：

void SLModify(Seqlist* psl, int pos, SlDataType x)
{
	assert(psl);//检查参数有效性
	assert(pos >= 0 && pos < psl->size);//检查位置的有效性

	psl->data[pos] = x;

}
1
2
3
4
5
6
7
8

顺序表的实现可能因编程语言而异，但上述操作的核心思想是相似的。

至此，本片文章就结束了，若本篇内容对您有所帮助，请三连点赞，关注，收藏支持下。
创作不易，白嫖不好，各位的支持和认可，就是我创作的最大动力，我们下篇文章见！
如果本篇博客有任何错误，请批评指教，不胜感激 ！！！