数据结构——顺序表的概念和基本操作（超全超详细）_顺序表的基本操作 知识点总结

1. 线性表

• 是n个具有相同特性的数据元素的有限序列
• 当n=0时称为空表
• 常见的线性表有：顺序表、链表、栈、队列、字符串等

2. 顺序表（Sequence List）

• 本质上就是数组（静态/动态）

• 数据必须从头连续存储，不能跳跃间隔

2.1 静态顺序表

• 即直接在结构体中确定存储数据的数组的大小，之后不能对其进行改变

• 特点：MAX给小了不够用，MAX大了浪费空间

• 定义：

#define MAX 1000
typedef int SLDataType;	//定义顺序表存储的元素类型
typedef struct SeqList
{
    SLDataType[MAX];
    int size;	//数组中存储了多少个数据
}SL;
1
2
3
4
5
6
7

2.2 动态顺序表

• 定义：
• 利用动态管理，对内存进行动态开辟，方便后续调整数组大小

#define MAX 5

typedef int SLDataType;	//定义顺序表存储的元素类型
typedef struct SeqList
{
	SLDataType* data;
	int size;	//用来表示当前存储了多少个数据
	int capacity;	//用来表示最大容量
}SeqList;
1
2
3
4
5
6
7
8
9

3. 基本操作

注：以下都以动态顺序表为例：

3.1 顺序表的初始化

void SeqListInit(SeqList* ps);
1

要使用顺序表，我们首先就先要对其初始化：

• 确定确定初始最大容量
• 动态开辟内存
• 将size置零

void SeqListInit(SeqList* ps)	//初始化
{
	assert(ps);	//保证指针有效

	ps->capacity = MAX;	//确定初始最大容量
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity);	//动态开辟内存
	if (NULL == ps->data)	//检验
	{
		perror("malloc");
		exit(-1);
	}
	ps->size = 0;	//将`size`置零
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.2 顺序表的销毁

void SeqListDestory(SeqList* ps);
1

顺序表使用完后，就要对其进行销毁：

• 释放动态内存
• 将size，和最大容量capacity置零

void SeqListDestory(SeqList* ps)	//销毁
{
	assert(ps);//保证指针有效

	free(ps->data);
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8

3.3 尾插SeqListPushBack()

void SeqListPushBack(SeqList* ps, SLDataType val);
1

在插入之前，我们必须要对存储数据的数组进行检查，如果size已经等于最大容量capacity，那么我们首先就要对其进行增容

3.3.1 判满SeqListFull()

bool SeqListFull(const SeqList* ps)	//判满
{
	assert(ps);

	return ps->capacity == ps->size;
}
1
2
3
4
5
6

3.3.2 增容SeqListIncreaseCapacity()

void SeqListIncreaseCapacity(SeqList* ps)	//增容
{
	assert(ps);

	ps->capacity *= 2;	//每次将容量扩大为原来的两倍
	SLDataType* temp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity);
	if (NULL == temp)
	{
		perror("realloc");
		exit(-1);
	}
	ps->data = temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.3.3 SeqListPushBack()

尾插的逻辑十分简单，检查完容量后，直接将新数据插入到最后即可：

提醒：不要忘了将size加一

void SeqListPushBack(SeqList* ps, SLDataType val)	//尾插
{
	assert(ps);	//检验指针有效性
	
    //检查容量
	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

    //实现尾插
	ps->data[ps->size++] = val;
}
1
2
3
4
5
6
7
8
9
10
11

3.4 尾删SeqListPopBack()

void SeqListPopBack(SeqList* ps);
1

注意，在删除数据之前，必须保证顺序表中存放了数据，即size > 0，因此首先要进行判空操作

3.4.1 判空SeqListEmpty()

bool SeqListEmpty(const SeqList* ps)	//判空
{
	assert(ps);

	return ps->size == 0;
}
1
2
3
4
5
6

3.4.2 SeqListPopBack()

尾删操作也十分简单，如果顺序表中存储了数据，那么直接将size减一就可以了，因为这样就访问不到最后一个数据，也就可以看作是删除了。

void SeqListPopBack(SeqList* ps)	//尾删
{
	assert(ps);	//检验指针有效性
	assert(!SeqListEmpty(ps));	//顺序表不能为空

	ps->size--;	//尾删
}
1
2
3
4
5
6
7

3.5 头插SeqListPushFront()

void SeqListPushFront(SeqList* ps, SLDataType val);	
1

和尾插一样，同样首先要对容量进行检查。

要将新数据插入到数组的第一个位置，那么我们就先要将原来的数据全部往后移动一位。

而为了原有数据不被覆盖，必须从后往前挪动数据（如果有疑惑，可以通过画图来理解）

void SeqListPushFront(SeqList* ps, SLDataType val)	//头插
{
	assert(ps);	//检验指针有效性

    //检查容量
	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);
	
    //挪动数据
	for (int i = ps->size - 1; i >= 0; i--)
		ps->data[i + 1] = ps->data[i];
    
    //头插
	ps->data[0] = val;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3.6 头删SeqListPopFront()

void SeqListPopFront(SeqList* ps)
1

和尾删一样，也先要对顺序表判空，如果为空，就不能进行删除

要实现头删，我们就需要将出第一个元素之外的所有元素向前挪动一位，这样，第一个元素就会被覆盖，从而也就实现了头删

而为了确保原有数据不被覆盖，我们要从前往后挪动数据（有疑惑的可以画图理解）

提醒：删完之后，记得将size减一

void SeqListPopFront(SeqList* ps)	//头删
{
	assert(ps);	//检验指针有效性
	assert(!SeqListEmpty(ps));	//判空

    //挪动数据，实现头删
	for (int i = 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11

3.7 在下标pos处插入SeqListInsert()

void SeqListInsert(SeqList* ps, int pos, SLDataType val);	
1

和头插的逻辑类似，要在下标为pos处插入新元素，我们就要将pos和pos之后的元素都向后挪动一位

注意1：同样先要进行容量检查，要注意控制循环边界，防止越界

注意2：由于顺序表要求必须对数据进行连续的存储，因此我们对下标pos也有要求

void SeqListInsert(SeqList* ps, int pos, SLDataType val)	//在pos处插入
{
	assert(ps);	//检验指针有效性
	assert(pos >= 0 && pos <= ps->size);	//检验pos的有效性
	
    //检查容量
	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

    //挪动数据
	for (int i = ps->size - 1; i >= pos; i--)
		ps->data[i + 1] = ps->data[i];
    
    //实现插入
	ps->data[pos] = val;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3.8 删除下标为pos的数据SeqListErase(SeqList* ps, int pos)

void SeqListErase(SeqList* ps, int pos);
1

和头删的逻辑类似，我们只需要将pos后面的所有数据向前挪动一位就可以实现将pos位置的数据删除了

注1：删除之前要判空

注2：要记得检查pos的有效性，防止越界访问

void SeqListErase(SeqList* ps, int pos)	//删除pos处元素
{
	assert(ps);	//检验指针有效性
	assert(!SeqListEmpty(ps));	//判空
	assert(pos < ps->size);	//检验pos有效性
	
    //挪动数据实现删除
	for (int i = pos + 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

3.9 查找值为val的数据SeqListFind()

int SeqListFind(const SeqList* ps, SLDataType val);	//找到后返回下标，否则返回-1
1

这个操作逻辑十分简单，遍历一遍顺序表，如果找到了，就返回这个下标，否则就返回-1

int SeqListFind(const SeqList* ps, SLDataType val)	//查找值为val的数据
{
	assert(ps);//检验指针有效性

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

3.10 修改下标为pos处的数据

这个操作也十分简单，直接访问下标为pos处的元素就可以了。只是同样需要注意对pos的有效性进行检查

void SeqListModify(SeqList* ps, int pos, int val)	//将下标为pos处的数据修改为val
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->data[pos] = val;
}
1
2
3
4
5
6
7

4. 顺序表的优缺点

4.1 优点

• 实现尾删和尾插的效率很高
• 随机访问：由于顺序表使用数组来表示元素，因此可以通过索引快速地随机访问元素。这种特性使得顺序表在查找特定元素时非常高效。
• 内存连续：顺序表中的元素在内存中是连续存储的，这有助于提高缓存的利用率，从而提高访问效率。
• 直接存取：相比于其他数据结构，如链表，顺序表的存取操作较为简单，不需要像链表那样处理节点指针，使得存取操作速度更快。
• 适合小规模数据：对于元素数量较少的情况，顺序表通常比较适用，因为它的内存开销相对较小。

4.2 缺点

• 插入和删除低效：当需要在顺序表中插入或删除元素时，需要将后续元素移动，以保持连续存储的特性。这样的操作导致插入和删除操作的时间复杂度为O(n)，其中n是元素数量。对于频繁的插入和删除操作，顺序表的性能较差。

• 固定大小：顺序表在创建时需要预先分配一定的存储空间，因此其大小是固定的。如果需要存储的元素数量超过了初始大小，就需要进行扩容操作，这可能导致额外的内存分配和数据搬移开销。

• 内存浪费：如果实际存储的元素数量远小于顺序表的最大容量，会造成内存空间的浪费。

• 不易动态调整：由于顺序表的大小固定且内存连续，动态调整其大小较为复杂。在某些场景下，需要频繁调整大小的数据结构时，顺序表可能不是最佳选择。

5. 参考代码

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

#define MAX 5

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* data;
	int size;
	int capacity;
}SeqList;

void SeqListInit(SeqList* ps);	//初始化
void SeqListDestory(SeqList* ps);	//销毁
void SeqListPrint(const SeqList* ps);	//打印
bool SeqListEmpty(const SeqList* ps);	//判空
bool SeqListFull(const SeqList* ps);	//判满
void SeqListIncreaseCapacity(SeqList* ps);	//增容
void SeqListPushBack(SeqList* ps, SLDataType val);	//尾插
void SeqListPopBack(SeqList* ps);	//尾删
void SeqListPushFront(SeqList* ps, SLDataType val);	//头插
void SeqListPopFront(SeqList* ps);	//头删
void SeqListInsert(SeqList* ps, int pos, SLDataType val);	//在pos处插入
void SeqListErase(SeqList* ps, int pos);	//删除pos处元素
int SeqListFind(const SeqList* ps, SLDataType val);	//查找值为val的数据
void SeqListModify(SeqList* ps, int pos, int val);	//将下标为pos处的数据修改为val

void SeqListInit(SeqList* ps)	//初始化
{
	assert(ps);

	ps->capacity = MAX;
	ps->data = (SLDataType*)malloc(sizeof(SLDataType) * ps->capacity);
	if (NULL == ps->data)
	{
		perror("malloc");
		exit(-1);
	}
	ps->size = 0;
}

void SeqListDestory(SeqList* ps)	//销毁
{
	assert(ps);

	free(ps->data);
	ps->size = 0;
	ps->capacity = 0;
}

void SeqListPrint(const SeqList* ps)	//打印
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
		printf("%d ", ps->data[i]);
	printf("\n");
}

bool SeqListEmpty(const SeqList* ps)	//判空
{
	assert(ps);

	return ps->size == 0;
}

bool SeqListFull(const SeqList* ps)	//判满
{
	assert(ps);

	return ps->capacity == ps->size;
}

void SeqListIncreaseCapacity(SeqList* ps)	//增容
{
	assert(ps);

	ps->capacity *= 2;
	SLDataType* temp = (SLDataType*)realloc(ps->data, sizeof(SLDataType) * ps->capacity);
	if (NULL == temp)
	{
		perror("realloc");
		exit(-1);
	}
	ps->data = temp;
}

void SeqListPushBack(SeqList* ps, SLDataType val)	//尾插
{
	assert(ps);

	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

	ps->data[ps->size++] = val;
}

void SeqListPopBack(SeqList* ps)	//尾删
{
	assert(ps);
	assert(!SeqListEmpty(ps));

	ps->size--;
}

void SeqListPushFront(SeqList* ps, SLDataType val)	//头插
{
	assert(ps);

	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

	for (int i = ps->size - 1; i >= 0; i--)
		ps->data[i + 1] = ps->data[i];
	ps->data[0] = val;

	ps->size++;
}

void SeqListPopFront(SeqList* ps)	//头删
{
	assert(ps);
	assert(!SeqListEmpty(ps));

	for (int i = 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}

void SeqListInsert(SeqList* ps, int pos, SLDataType val)	//在pos处插入
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);

	if (SeqListFull(ps))
		SeqListIncreaseCapacity(ps);

	for (int i = ps->size - 1; i >= pos; i--)
		ps->data[i + 1] = ps->data[i];
	ps->data[pos] = val;

	ps->size++;
}
void SeqListErase(SeqList* ps, int pos)	//删除pos处元素
{
	assert(ps);
	assert(!SeqListEmpty(ps));
	assert(pos < ps->size);

	for (int i = pos + 1; i < ps->size; i++)
		ps->data[i - 1] = ps->data[i];

	ps->size--;
}

int SeqListFind(const SeqList* ps, SLDataType val)	//查找值为val的数据
{
	assert(ps);

	for (int i = 0; i < ps->size; i++)
	{
		if (ps->data[i] == val)
		{
			return i;
		}
	}
	return -1;
}

void SeqListModify(SeqList* ps, int pos, int val)	//将下标为pos处的数据修改为val
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	ps->data[pos] = val;
}

int main()
{
	SeqList* sl;
	sl = (SeqList*)malloc(sizeof(SeqList));
	if (NULL == sl)
	{
		perror("malloc");
		return -1;
	}

	SeqListInit(sl);

    //……………………
    
	SeqListDestory(sl);

	return 0;
}
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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200