【初阶数据结构】——顺序表详解（C描述）

前言

线性表是最基本、最简单、也是最常用的一种数据结构。线性表（linear list）是数据结构的一种。

1. 认识线性表

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

2. 顺序表详解

这篇文章我们先来学习顺序表，它是线性表的一种。

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般有两种：

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

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

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

那动态顺序表怎么实现呢？

还是用数组，只不过我们使用动态开辟的数组，这样的话一开始我们不用给太多空间，如果不够用我们可以进行扩容。

接下来，我们就对动态顺序表进行一个详细的讲解和实现。

2.2 结构讲解及接口实现

2.2.1 结构

大家思考一下，动态顺序表我们采用了一个动态开辟的数组来实现，那我们是不是就搞一个数组就OK了。

不是的，除了用来存放数据的数组，我们还要定义一个size（当然变量名是自己起的），用来记录有效数据个数，因为我们会往顺序表里面放数据，放进去一个，size就应该增1，当然还要有一个变量capacity来记录容量，因为对于动态的顺序表来说，我们可以扩容，它的容量是可变的。

所以，顺序表的结构是这样的：

typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	int size;//有效数据个数
	int capacity;//顺序表容量
}SL
1
2
3
4
5
6

使用时，我们拿这个结构体类型直接创建结构体变量就行了，定义的结构体变量就是我们创建的顺序表。

好，那顺序表的结构定义好之后，接下来就是实现它的功能了，我们把这些功能都封装成一个个的函数，接下来我们就来一一实现它们：

2.2.2 顺序表初始化

在初始化的时候，我们可以给顺序表一个合适的大小，也可以先不给它分配空间，在我们插入元素时再分配空间。

在这里，我们就先不给它分配空间，这样初始化：

//顺序表初始化
void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8

参数SL* ps是一个结构体指针，用来接收我们创建的顺序表的地址。
assert(ps);进行断言，避免传过来的是空指针。
因为我们这里没有给它分配空间，所以指向动态开辟的数组的指针arr 先初始化为NULL，有效数据个数和容量都是0。

2.2.3 销毁

因为动态顺序表的空间时我们在堆上动态开辟的，这些空间时需要我们最后使用free释放的，否则会发生内存泄漏。

//销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	//if(ps->arr!=NULL)
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capacity = ps->size = 0;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12

释放完最好置空，不置空的话ps->arr 就成为野指针了。

2.2.4 打印顺序表

怎么打印？

很简单，就是对数组进行遍历打印元素就行了。

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

2.2.5 检查容量

我们说动态顺序表空间不够可以扩容，那怎么知道空间不够呢？

是不是要对占用的容量进行检查啊，头插尾插等各种插入操作在进行插入元素之前是不是都要检查一下容量啊。如果没剩余空间是不是就不能再插入数据了啊。

那什么时候是没有可用空间了呢？

是不是有效数据个数等于容量大小的时候啊。
ps->size == ps->capacity

那现在有一个问题：

我们初始化的时候是不是没给空间啊，所以顺序表为空时ps->size == ps->capacity是不是也成立啊。
那是不是要分情况来啊：
如果capacity等于0，这时我们应该用malloc开辟一点空间作为初始大小，如果capacity不等于0，证明是原来的空间用完了，这时要扩容，是不是要用realloc 啊。

那简便一点，可以这样写：

//检查空间是否满
void CheckCapacity(SL* ps)
{
	assert(ps);
	//如果满了（或是第一次插入数据），要扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		//assert(tmp);（这个地方用断言的话不太好，release下assert就失效了）
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

这里初始容量大小给的是4，大家可以自己调整。
开辟空间（或扩容）成功后，让ps->arr指向这块空间，然后就可以继续存放数据了，当然记得更新容量的大小。

2.2.6 在任意位置插入数据

建议大家先不要写头插尾插，因为这个函数实现完我们发现头插尾插就可以直接利用这个函数了。

那这个函数要怎么实现呢？

要实现的功能就是用户给我指定一个下标，我们把数据插入到这个位置。
那我们首先是不是要判断一下这个下标是否合法啊，虽说是在任意位置插入数据，但是不是有前提啊。
如果现在顺序表中只有两个元素，但是你想在下标为10的位置插入一个数据，这肯定不行。且不说空间够不够。

上面概念怎么说的？

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构.
即顺序表中的元素必须是一个一个挨着存放的。

所以：

要插入元素的位置必须满足：
pos >= 0 && pos <= ps->size

除了检查插入位置的合法性，是不是还要检查容量啊，函数我们上面已经写好了，直接调用。

那怎么插入数据呢？

既然是插入，是不是要挪动数据，腾出来一个位置，才能插进去啊。

转化为代码：

//在pos位置插入x（头插尾插就可以利用SLInsert了）
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);

	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}

	ps->arr[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.2.7 头插

直接利用SLInsert（在任意位置插入数据）：

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	/*assert(ps);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->size-1; i>=0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[0] = x;
	ps->size++;*/

	SLInsert(ps, 0, x); //直接利用SLInsert，x是要插入的数据，0是下标（头插所以下标是0）
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注释掉的是没有利用SLInsert，自己实现的，大家有兴趣可以看一看。

2.2.8 尾插

也可以利用SLInsert：

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	/*assert(ps);
	CheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;*/

	SLInsert(ps, ps->size, x);
}
1
2
3
4
5
6
7
8
9
10

2.2.9 在任意位置删除数据

怎么删呢？

//删除pos位置的值（头删尾删就可以复用SLErase了）
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos + 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}
1
2
3
4
5
6
7
8
9
10
11
12

2.2.20 头删

即删除下标为0的元素：

//头删
void SLPopFront(SL* ps)
{
	/*assert(ps);
	assert(ps->size > 0);
	int i = 0;
	for (i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;*/
	
	SLErase(ps, 0);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.2.11 尾删

即删除下标为size-1的元素：

//尾删
void SLPopBack(SL* ps)
{
	/*assert(ps);
	assert(ps->size > 0);
	ps->size--;*/
	SLErase(ps, ps->size - 1);
}
1
2
3
4
5
6
7
8

2.2.12 查找元素

怎么实现？

遍历返回下标即可，找不到可以返回-1

//查找元素x，返回下标，找不到返回-1
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12

3. 测试

简单给大家测试一下，大家可以自己写一个比较完整的菜单：

void test3()
{
	SL sl;
	SLInit(&sl);
	
	SLPushFront(&sl, 1);
	SLPushFront(&sl, 2);
	SLPushFront(&sl, 3);
	SLPushFront(&sl, 4);
	SLPushFront(&sl, 5);
	SLPrint(&sl);
	SLInsert(&sl, 3, 7);
	SLPrint(&sl);
	SLErase(&sl,2);
	SLPrint(&sl);
	SLErase(&sl,3);
	SLPrint(&sl);

	SLDestroy(&sl);
}
int main()
{
	test3();
	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

看看效果：

4. 源码展示

这里结构体定义，头文件包含，和函数实现放在了不同文件中，方便对代码管理。

SeqList.h

#pragma once
#include 
#include 
#include 

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* arr;//指向动态开辟的数组
	int size;//有效数据个数
	int capacity;//顺序表容量
}SL;

//顺序表初始化
void SLInit(SL* ps);
//销毁
void SLDestroy(SL* ps);
//打印顺序表
void SLPrint(SL* ps);
//检查空间是否满
void CheckCapacity(SL* ps);
//尾插
void SLPushBack(SL* ps,SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDataType x);
//删除pos位置的值
void SLErase(SL* ps, int pos);
//查找元素x
int SLFind(SL* ps, SLDataType x);
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

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

//顺序表初始化
void SLInit(SL* ps)
{
	assert(ps);
	ps->arr = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

//销毁
void SLDestroy(SL* ps)
{
	assert(ps);
	//if(ps->arr!=NULL)
	if (ps->arr)
	{
		free(ps->arr);
		ps->arr = NULL;
		ps->capacity = ps->size = 0;
	}
}

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

//检查空间是否满
void CheckCapacity(SL* ps)
{
	assert(ps);
	//如果满了（或是第一次插入数据），要扩容
	if (ps->size == ps->capacity)
	{
		int newcapacity = (ps->capacity == 0 ? 4 : ps->capacity * 2);
		SLDataType* tmp = (SLDataType*)realloc(ps->arr, newcapacity * sizeof(SLDataType));
		//assert(tmp);（这个地方用断言的话不太好，release下assert就失效了）
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		ps->arr = tmp;
		ps->capacity = newcapacity;
	}
}

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
	/*assert(ps);
	CheckCapacity(ps);
	ps->arr[ps->size] = x;
	ps->size++;*/
	SLInsert(ps, ps->size, x);
}

//尾删
void SLPopBack(SL* ps)
{
	/*assert(ps);
	assert(ps->size > 0);
	ps->size--;*/
	SLErase(ps, ps->size - 1);
}

//头插
void SLPushFront(SL* ps, SLDataType x)
{
	/*assert(ps);
	CheckCapacity(ps);
	int i = 0;
	for (i = ps->size-1; i>=0; i--)
	{
		ps->arr[i + 1] = ps->arr[i];
	}
	ps->arr[0] = x;
	ps->size++;*/

	SLInsert(ps, 0, x);
}

//头删
void SLPopFront(SL* ps)
{
	/*assert(ps);
	assert(ps->size > 0);
	int i = 0;
	for (i = 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;*/
	SLErase(ps, 0);
}

//在pos位置插入x（头插尾插就可以利用SLInsert了）
void SLInsert(SL* ps, int pos, SLDataType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	CheckCapacity(ps);

	int i = 0;
	for (i = ps->size; i > pos; i--)
	{
		ps->arr[i] = ps->arr[i - 1];
	}

	ps->arr[pos] = x;
	ps->size++;
}

//删除pos位置的值（头删尾删就可以复用SLErase了）
void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	int i = 0;
	for (i = pos + 1; i < ps->size; i++)
	{
		ps->arr[i - 1] = ps->arr[i];
	}
	ps->size--;
}

//查找元素x，返回下标，找不到返回-1
int SLFind(SL* ps, SLDataType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		if (ps->arr[i] == x)
			return i;
	}
	return -1;
}
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

5. 顺序表存在的问题

顺序表的实现我们已经学完了，那大家思考一下，顺序表又没有什么问题或者或缺陷呢？

是有的。

1. 中间/头部的插入删除，时间复杂度为O(N)
2. realloc扩容（特别是异地扩，需要申请新空间，拷贝数据，释放旧空间）会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

思考：如何解决以上问题呢？

针对这些问题，又引出了另一种线性表——链表。
对于链表的讲解，放在下一篇文章。

以上就是对顺序表的一个讲解，希望能帮到大家，如果有写的不好的地方，也欢迎大家指正！！！