数据结构——顺序表（文字+代码+带图详细讲解）_顺序表代码

在 C 语言中，顺序表可以使用数组来实现。顺序表是一种线性表，其中的元素在物理上连续存储，可以通过下标访问任意元素。
顺序表的基本操作包括插入、删除、查找、遍历和初始化等。

这段代码定义了一个顺序表的结构体，其中包括三个成员变量：
SLDataType* array：指向动态开辟的数组，即顺序表的存储空间。
size_t size：有效数据个数，即当前顺序表中实际存储的元素个数。
size_t capicity：空间容量的大小，即当前顺序表的存储空间的大小。

typedef int SLDataType;
//定义了一个顺序表的结构体
typedef struct SeqList
{
	SLDataType* array;//指向动态开辟的数组
	size_t size;	//有效数据个数
	size_t capicity;	//空间容量的大小
}SeqList;

1
2
3
4
5
6
7
8
9

这段代码实现了顺序表的初始化操作。该函数接受一个指向顺序表结构体的指针 psl，并在内存中动态分配了一个大小为4的数组来存储元素。

具体来说，该函数完成了以下操作：
使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
使用 malloc()函数动态分配了一个大小为4的数组来存储元素，并将其赋值给 psl->array，即顺序表的存储空间。
判断数组是否分配成功，如果分配失败则输出错误信息并返回。
将 psl->size 和 psl->capicity初始化为0和4，分别表示当前顺序表中实际存储的元素个数和存储空间的容量大小。

//顺序表初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->array= (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (psl->array == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capicity = 4;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这段代码实现了顺序表的动态增容操作。该函数接受一个指向顺序表结构体的指针 psl，并在顺序表中的元素个数等于容量大小时进行扩容操作。
具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
判断当前顺序表中实际存储的元素个数 psl->size是否等于存储空间的容量大小 psl->capicity，如果相等则说明顺序表已满，需要进行扩容操作。
使用 realloc()函数对顺序表存储空间进行扩容，将原来的空间大小 psl-capicity 扩大一倍，即 psl->capicity * 2，并将扩容后的空间大小赋值给 psl->capicity。
判断扩容是否成功，如果扩容失败则输出错误信息并返回。
将扩容后的新空间地址赋值给 psl->array，即顺序表的存储空间。

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->size == psl->capicity)
	{
		SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * psl->capicity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->array = tmp;
		psl->capicity *= 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这段代码实现了顺序表尾插操作。该函数接受一个指向顺序表结构体的指针 psl 和要插入的元素值 x，并将元素插入到顺序表的末尾。

具体来说，该函数完成了以下操作：
使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
调用 CheckCapacity()，函数检查顺序表的存储空间是否已满，如果已满则进行动态增容操作。
将要插入的元素值 x 赋值给顺序表存储空间中下一个可用的位置，即
psl->array[psl->size]。 将顺序表中实际存储的元素个数 psl->size 加1，表示顺序表中又插入了一个元素。

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->array[psl->size] = x;
	psl->size++;
}

1
2
3
4
5
6
7
8
9

这段代码实现了顺序表尾删操作。该函数接受一个指向顺序表结构体的指针 psl，并将顺序表中的最后一个元素删除。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
使用 assert() 宏判断顺序表中实际存储的元素个数psl->size 是否大于0，如果不大于0则说明顺序表为空，无法进行删除操作。
将顺序表存储空间中最后一个元素位置 psl->array[psl->size-1] 的值清空，即置为0。
将顺序表中实际存储的元素个数 psl->size减1，表示顺序表中又删除了一个元素。

// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->array[psl->size-1] = 0;
	psl->size--;
}
1
2
3
4
5
6
7
8

这段代码实现了顺序表头插操作。该函数接受一个指向顺序表结构体的指针 psl 和要插入的元素值 x，并将元素插入到顺序表的头部。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
调用 CheckCapacity()函数检查顺序表的存储空间是否已满，如果已满则进行动态增容操作。
从顺序表存储空间中最后一个元素位置开始，向后逐个将每个元素向后移动一个位置，直到顺序表存储空间中的所有元素都向后移动了一个位置。
将要插入的元素值 x 赋值给顺序表存储空间中第一个位置，即 psl->array[0]。 将顺序表中实际存储的元素个数 psl->size加1，表示顺序表中又插入了一个元素。

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->array[end + 1] = psl->array[end];
		--end;
	}
	psl->array[0] = x;
	psl->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

这段代码实现了顺序表头删操作。该函数接受一个指向顺序表结构体的指针 psl，并将顺序表中的第一个元素删除。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
使用 assert() 宏判断顺序表中实际存储的元素个数 psl->size 是否大于0，如果不大于0则说明顺序表为空，无法进行删除操作。
从顺序表存储空间中第二个元素位置开始，向前逐个将每个元素向前移动一个位置，直到顺序表存储空间中的所有元素都向前移动了一个位置。
将顺序表中实际存储的元素个数 psl->size 减1，表示顺序表中又删除了一个元素。

// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	int begin = 1;
	while (begin < psl->size)
	{
		psl->array[begin - 1] = psl->array[begin];
		++begin;
	}
	psl->size--;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

这段代码实现了顺序表的查找操作。该函数接受一个指向顺序表结构体的指针 psl 和要查找的元素值 x，并在顺序表中查找该元素。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
在顺序表存储空间中逐个查找元素，如果找到了元素值等于 x的元素，则返回该元素在顺序表中的下标。
如果在顺序表中没有找到元素值等于 x 的元素，则返回-1，表示查找失败。

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

这段代码实现了顺序表在指定位置插入元素的操作。该函数接受一个指向顺序表结构体的指针 psl，要插入的位置 pos，以及要插入的元素值 x。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
使用 assert() 宏判断要插入的位置 pos 是否合法，即在顺序表的范围内。
调用 CheckCapacity() 函数检查顺序表的存储空间是否已满，如果已满则进行动态增容操作。
从顺序表存储空间中最后一个元素位置开始，向后逐个将每个元素向后移动一个位置，直到顺序表存储空间中的要插入位置 pos 的元素位置。
将要插入的元素值 x 赋值给顺序表存储空间中要插入位置 pos 的元素位置，即 psl->array[pos]。
将顺序表中实际存储的元素个数 psl->size 加1，表示顺序表中又插入了一个元素。

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

这段代码实现了顺序表删除指定位置的元素操作。该函数接受一个指向顺序表结构体的指针 psl 和要删除的位置 pos。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。
使用 assert() 宏判断要删除的位置 pos是否合法，即在顺序表的范围内。
从顺序表存储空间中要删除位置 pos的下一个元素位置开始，向前逐个将每个元素向前移动一个位置，直到顺序表存储空间中的所有元素都向前移动了一个位置。
将顺序表中实际存储的元素个数psl->size 减1，表示顺序表中又删除了一个元素。

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
assert(psl);
assert(pos >= 0 && pos <= psl->size);
int begin = pos + 1;
while (begin < psl->size)
{
psl->array[begin - 1] = psl->array[begin];
++begin;
}
psl->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这段代码实现了顺序表的销毁操作。该函数接受一个指向顺序表结构体的指针 psl，并释放掉顺序表所占用的内存空间。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。 调用 free() 函数释放顺序表存储空间所占用的内存空间。
将顺序表存储空间指针 psl->array 置为NULL，表示该存储空间已被释放。
将顺序表的容量 psl->capicity和实际存储的元素个数 psl->size 都置为0，表示顺序表已被销毁。
需要注意的是，在使用完顺序表后，需要及时调用该函数来释放顺序表所占用的内存空间，以避免内存泄漏。

// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array == NULL;
	psl->capicity = 0;
	psl->size = 0;
}
1
2
3
4
5
6
7
8
9

这段代码实现了顺序表的打印操作。该函数接受一个指向顺序表结构体的指针 psl，并将顺序表中存储的所有元素打印输出。

具体来说，该函数完成了以下操作：

使用 assert() 宏判断指针 psl 不为空，如果为空则程序会中止。 使用 for循环逐个遍历顺序表中实际存储的元素，将每个元素打印输出。
在打印完所有元素后，使用 printf()函数输出一个换行符，以便于显示下一行输出。

// 顺序表打印
void SeqListPrint(SeqList* psl)
{
assert(psl);
for (int i = 0; i < psl->size; i++)
{
printf("%d ", psl->array[i]);
}
printf("\n");

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

完整程序

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
//定义了一个顺序表的结构体
typedef struct SeqList
{
	SLDataType* array;//指向动态开辟的数组
	size_t size;	//有效数据个数
	size_t capicity;	//空间容量的大小
}SeqList;

//顺序表初始化
void SeqListInit(SeqList* psl);
// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl);
// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
// 顺序表尾删
void SeqListPopBack(SeqList* psl);
// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
// 顺序表头删
void SeqListPopFront(SeqList* psl);
// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos);
// 顺序表销毁
void SeqListDestory(SeqList* psl);
// 顺序表打印
void SeqListPrint(SeqList* psl);

//顺序表初始化
void SeqListInit(SeqList* psl)
{
	assert(psl);
	psl->array= (SLDataType*)malloc(sizeof(SLDataType) * 4);
	if (psl->array == NULL)
	{
		perror("malloc fail");
		return;
	}
	psl->size = 0;
	psl->capicity = 4;
}

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* psl)
{
	assert(psl);
	if (psl->size == psl->capicity)
	{
		SLDataType* tmp = (SLDataType*)realloc(psl->array, sizeof(SLDataType) * psl->capicity * 2);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		psl->array = tmp;
		psl->capicity *= 2;
	}
}

// 顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	psl->array[psl->size] = x;
	psl->size++;
}

// 顺序表尾删
void SeqListPopBack(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	psl->array[psl->size-1] = 0;
	psl->size--;
}

// 顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x)
{
	assert(psl);
	CheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= 0)
	{
		psl->array[end + 1] = psl->array[end];
		--end;
	}
	psl->array[0] = x;
	psl->size++;
}

// 顺序表头删
void SeqListPopFront(SeqList* psl)
{
	assert(psl);
	assert(psl->size > 0);
	int begin = 1;
	while (begin < psl->size)
	{
		psl->array[begin - 1] = psl->array[begin];
		++begin;
	}
	psl->size--;
}

// 顺序表查找
int SeqListFind(SeqList* psl, SLDataType x)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		if (psl->array[i] == x)
		{
			return i;
		}
	}
	return -1;
}

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	CheckCapacity(psl);
	int end = psl->size - 1;
	while (end >= pos)
	{
		psl->array[end + 1] = psl->array[end];
		--end;
	}
	psl->array[pos] = x;
	psl->size++;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* psl, size_t pos)
{
	assert(psl);
	assert(pos >= 0 && pos <= psl->size);
	int begin = pos + 1;
	while (begin < psl->size)
	{
		psl->array[begin - 1] = psl->array[begin];
		++begin;
	}
	psl->size--;
}
// 顺序表销毁
void SeqListDestory(SeqList* psl)
{
	assert(psl);
	free(psl->array);
	psl->array == NULL;
	psl->capicity = 0;
	psl->size = 0;
}

// 顺序表打印
void SeqListPrint(SeqList* psl)
{
	assert(psl);
	for (int i = 0; i < psl->size; i++)
	{
		printf("%d ", psl->array[i]);
	}
	printf("\n");

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177