【数据结构】线性表之顺序表详解

🧑‍💻作者： @情话0.0
📝专栏：《数据结构》
👦个人简介：一名双非研究生的编程菜鸟，在这里分享自己的编程学习笔记，欢迎大家的指正与点赞，谢谢！

---

前言

数据的逻辑结构分为线性结构和非线性结构，线性结构中的线性表根据存储结构又分为顺序表和链表。这篇博客主要讲的是顺序表的定义和基本操作，以及它是如何实现的。

---

一、线性表的定义和基本操作

1. 线性表的定义

线性表是具有相同数据类型的 n (n>=0)个数据元素的有限序列，其中 n 为表长，当n=0时线性表是一个空表。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，
线性表在物理上存储时，通常以数组和链式结构的形式存储。

2. 线性表的特点

表中元素的个数有限。
表中元素具有逻辑上的顺序性，表中元素有其先后次序。
表中元素都是数据元素，每个元素都是单个元素。
表中元素的数据类型都相同，这意味着每个元素占有相同大小的存储空间。
表中元素具有抽象性，即讨论元素间的逻辑关系，而不考虑元素究竟表示什么内容。

注意：线性表示一种逻辑结构，表示元素之间一对一的相邻关系。顺序表和链表是指存储结构，两者属于不同层面的概念，因此不要将其混淆。

3. 线性表的基本操作

一个数据结构的基本操作是指其最核心、最基本的操作。其他较复杂的操作可通过调用其基本操作来实现。线性表的主要操作如下：

void ListInit(List* s); 初始化表。构造一个空的线性表。
void CheckCapacity(List* s); 检查空间，若表空间已满，进行扩容
void ListPushBack(List* s, SLDataType x) 线性表尾插
void ListPopBack(List* s); 线性表尾删
void ListPushFront(List* s, SLDataType x);线性表头插
void ListPopFront(List* s);线性表头删
int ListFind(List* s, SLDataType x); 线性表查找,返回查找元素的位置
void ListInsert(List* s, size_t pos, SLDataType x);线性表在pos位置插入x
void ListErase(List* s, size_t pos);线性表删除pos位置的值
void ListDestory(List* s);线性表销毁
void ListPrint(List* s);线性表打印

二、线性表的顺序表示（顺序表）

1. 顺序表的定义

线性表的顺序存储称为顺序表。它是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑上相邻的两个元素在物理位置上也相邻。顺序表的特点是表中元素的逻辑顺序与其物理顺序相同。线性表的顺序存储结构是一种随机存取的存储结构。一般情况通过数组来描述顺序表结构。

顺序表一般可分为：

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

#define Maxsize 50 //定义顺序表的最大长度
typedef int SLDataType;
typedef struct SeqList
{
	SLDataType data[Maxsize];  //定长数组
	size_t size;  //有效数据个数
}SeqList;
1
2
3
4
5
6
7

在静态分配时，由于数组的大小和空间事先已经固定，一旦空间站满，再加入新的数据就会产生溢出，进而导致程序崩溃。

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

typedef int SLDataType;
typedef struct SeqList
{
  SLDataType* array;  // 指向动态开辟数组的指针
  size_t size ;       // 有效数据个数
  size_t capicity ;   // 容量空间的大小
}SeqList;
1
2
3
4
5
6
7

2. 顺序表的特点

顺序表最主要的特点是随机访问，即通过首地址和元素序号可在时间 O(1) 内找到指定的元素。
顺序表的存储密度高，每个节点只存储数据元素。
顺序表逻辑上相邻的元素物理上也相邻，所以插入和删除操作需要移动大量元素。

3. 顺序表的动态实现

typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array; // 指向动态开辟的数组
	size_t size; // 有效数据个数
	size_t capacity; // 容量空间的大小

}SeqList;
1
2
3
4
5
6
7
8
9

3.1 顺序表初始化

void SeqListInit(SeqList* s)
{
	s->array = (SLDateType*)malloc(sizeof(SLDateType)* 5);//将顺序表中的数组元素个数初始化为5个
	
	if (s->array == NULL)
	{
		return;
	}
	s->capacity = 5;
	s->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11

3.2 顺序表检查空间

void CheckCapacity(SeqList* s)
{
	assert(s);
	//当数组有效元素个数与数组容量相等时进行扩容，每次扩容后的元素个数为原来的2倍
	if (s->capacity == s->size)
	{
		SLDateType* array = (SLDateType*)realloc(s->a,sizeof(SLDateType)* (s->capacity*2));
		if(array==NULL)
		{
			return;
		}
		s->array = array;
		s->capacity *= 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

3.3 顺序表打印

void SeqListPrint(SeqList* s)
{
	assert(s);
	for (int i = 0; i < (s->size); i++)
	{
		printf("%d ", s->a[i]);
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9

3.4 顺序表尾插

void SeqListPushBack(SeqList* s, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	s->array[s->size] = x;
	s->size++;
}
1
2
3
4
5
6
7

3.5 顺序表头插

void SeqListPushFront(SeqList* s, SLDataType x)
{
	CheckCapacity(s);
	for (SLDataType i = s->size - 1; i >= 0; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[0] = x;
	s->size++;
}
1
2
3
4
5
6
7
8
9
10

3.6 顺序表尾删

void SeqListPopBack(SeqList* s)
{
	s->size--;//对于尾删，只需要将数组元素个数减一就行，第一，在打印时不会再访问到该元素，第二，在插入时会将这个元素覆盖
}
1
2
3
4

3.7 顺序表头删

void SeqListPopFront(SeqList* s)
{
	for (size_t i = 1; i < s->size; i++)
	{
		s->array[i-1] = s->array[i];
	}
	s->size--;
}
1
2
3
4
5
6
7
8

3.8 顺序表任意位置插入

void SeqListInsert(SeqList* s, size_t pos, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	for (size_t i = s->size - 1; i >= pos; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[pos] = x;
	s->size++;
}
1
2
3
4
5
6
7
8
9
10
11

3.9 顺序表任意位置删除

void SeqListErase(SeqList* s, size_t pos)
{
	assert(s);
	for (size_t i = pos; i < s->size; i++)
	{
		s->array[i] = s->array[i + 1];
	}
	s->size--;
}
1
2
3
4
5
6
7
8
9

3.10 顺序表查找

int SeqListFind(SeqList* s, SLDataType x)
{
	for (size_t i = 0; i < s->size; i++)
	{
		if (s->array[i] == x)
		{
			//找到
			return i + 1;
		}
	}
	//没找到
	return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3.11 顺序表销毁

void SeqListDestory(SeqList* s)
{
	free(s->array);  //顺序表的数组是动态申请的，所以需要通过 free 函数进行释放
	s->array = NULL;
	s->size = 0;
	s->capacity = 0;
}
1
2
3
4
5
6
7

三、源代码及运行结果展示

1. SeqList.h

#include 
#include 
#include 
typedef int SLDataType;
// 顺序表的动态存储
typedef struct SeqList
{
	SLDataType* array; // 指向动态开辟的数组
	size_t size; // 有效数据个数
	size_t capacity; // 容量空间的大小
}SeqList;

// 基本增删查改接口
// 顺序表初始化
void SeqListInit(SeqList* s, size_t capacity);

// 顺序表销毁
void SeqListDestory(SeqList* s);

// 顺序表打印
void SeqListPrint(SeqList* s);

// 检查空间，如果满了，进行增容
void CheckCapacity(SeqList* s);

// 顺序表尾插
void SeqListPushBack(SeqList* s, SLDataType x);

// 顺序表尾删
void SeqListPopBack(SeqList* s);

// 顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x);

// 顺序表头删
void SeqListPopFront(SeqList* s);

// 顺序表查找
int SeqListFind(SeqList* s, SLDataType x);

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x);

// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos);
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

2. SeqList.c

#include "Seqlist.h"

// 对数据的管理:增删查改 
void SeqListInit(SeqList* s)
{
	s->array = (SLDateType*)malloc(sizeof(SLDateType)* 5);
	if (s->array == NULL)
	{
		return;
	}
	s->capacity = 5;
	s->size = 0;
}

void SeqListDestroy(SeqList* s)
{
	assert(s);
	free(s->array);
	s->array = NULL;
	s->capacity = 0;
	s->size = 0;
}

void CheckCapacity(SeqList* s)
{
	assert(s);
	//当数组有效元素个数与数组容量相等时进行扩容，每次扩容后的元素个数为原来的2倍
	if (s->capacity == s->size)
	{
		SLDateType* array = (SLDateType*)realloc(s->a,sizeof(SLDateType)* (s->capacity*2));
		if(array==NULL)
		{
			return;
		}
		s->array = array;
		s->capacity *= 2;
	}
}

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

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

//顺序表头插
void SeqListPushFront(SeqList* s, SLDataType x)
{
	CheckCapacity(s);
	for (SLDataType i = s->size - 1; i >= 0; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[0] = x;
	s->size++;
}

//顺序表尾删
void SeqListPopBack(SeqList* s)
{
	s->size--;//对于尾删，只需要将数组元素个数减一就行，第一，在打印时不会再访问到该元素，第二，在插入时会将这个元素覆盖
}

void SeqListPopFront(SeqList* s)
{
	for (size_t i = 1; i < s->size; i++)
	{
		s->array[i-1] = s->array[i];
	}
	s->size--;
}

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

// 顺序表在pos位置插入x
void SeqListInsert(SeqList* s, size_t pos, SLDataType x)
{
	assert(s);
	CheckCapacity(s);
	for (size_t i = s->size - 1; i >= pos; i--)
	{
		s->array[i + 1] = s->array[i];
	}
	s->array[pos] = x;
	s->size++;
}

// 顺序表删除pos位置的值
void SeqListErase(SeqList* s, size_t pos)
{
	assert(s);
	for (size_t i = pos; i < s->size; i++)
	{
		s->array[i] = s->array[i + 1];
	}
	s->size--;
}

void SeqListTest()
{
	SeqList s;
	SeqListInit(&s);
	SeqListPushBack(&s, 1);
	SeqListPushBack(&s, 2);
	SeqListPushBack(&s, 3);
	SeqListPushBack(&s, 4);
	SeqListPushBack(&s, 5);
	SeqListPrint(&s);

	SeqListPushFront(&s, 0);
	SeqListPrint(&s);

	SeqListPopFront(&s);
	SeqListPrint(&s);

	SeqListPopBack(&s);
	SeqListPrint(&s);

	SeqListInsert(&s, 1, 6);
	SeqListPrint(&s);

	SeqListErase(&s, 1);
	SeqListPrint(&s);
}
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

3. test.c

#include "seqlist.h"
int main()
{
	SeqListTest();
	return 0;
}
1
2
3
4
5
6

结果展示:

---

总结

对于顺序表来说，它有着自己的特点：可在时间 O(1) 内查找元素，存储密度高。
但是，顺序表的插入删除，时间复杂度为O(N)；
增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗；
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
对于上述的问题，我们可通过链表进行解决，下篇博客将会对链表进行详细讲解。