数据结构：顺序表详解_数据结构顺序表

---

---

一、 线性表

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

---

二、 顺序表概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。

顺序表一般可以分为:

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

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

---

三、接口实现

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

基本增删查改接口

//对数据管理 --- 增删查改
void SLInit(SL* ps);			//初始化
void SLDestory(SL* ps);			//释放
void SLPrint(SL* ps);        	//打印
void SLCheakCapacity(SL* ps);	//检查容量 -- 扩容

//头插头删 尾插尾删
void SLPushBack(SL* ps, SLDateType x); //尾插
void SLPopBack(SL* ps);				   //尾删
void SLPushFront(SL* ps, SLDateType x);//头插
void SLPopFront(SL* ps);			   //头删

//返回下标，没找到返回-1
int SLFind(SL* ps, SLDateType);		   //查找元素，返回下标

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x);	//任意位置插入
//在pos位置删除x
void SLErase(SL* ps, int pos);					//任意位置删除

void SLModify(SL* ps, int pos, SLDateType x);//修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

---

1. 创建

由于在实际工程中，项目的实现都是采用模块化进行实现的。所以在此处博主也采用了模块化的方式进行实现。

#pragma once

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;//指向动态开辟的数组
	int size;	//有效数据的个数
	int capacity;//容量空间的大小
}SL;

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

为了后续好修改类型数据，在此采用typedef将结构体类型struct SeqList 重新命名为SL。
在实际开发过程中，为了开发人员更好的输入数据，一般我们会将输入数据的数据类型重命名为SLDateType。（在本篇博客中，采用typedef将其数据类型int重命名为SLDateType）

---

2. 初始化

初始化时，理论上我们只需要开辟一个空间并置为空指针，并将结构体中的数据全部初始化为0即可。
但在实际开发过程中，我们一般会开辟一定大小的空间（本篇博客开4个空间，但具体开多少，各位可自行选择）。

代码实现：

void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType));//开辟4个空间
	if (ps->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//开辟成功
	ps->capacity = 4;//开辟多少空间，容量变为多少
	ps->size = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

---

3. 扩容

在后续我们插入数据时，已开辟容量可能已经无法满足需求了。这是就需要扩容。
那一次扩到多少呢？
在实际开发过程中我们一般是扩到原有空间的两倍。（当然你也可以开1000倍，只要后台空间足够大）

代码实现：

void SLCheakCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		//开辟空间X2
		SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * sizeof(SLDateType) * 2);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		//开辟成功
		ps->a = tmp;
		ps->capacity *= 2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

---

4. 打印

上述函数定义完成后，我们通常需要测试打印以下相关数据，来判断相关函数定义是否成功.

代码实现：

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

---

5. 销毁

由于上述空间是动态开辟的。所以当我们使用完时，要及时销毁，释放空间。

代码实现：

void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}
1
2
3
4
5
6
7

---

6. 尾插

尾插：在尾部插入一个数据。

但是在数据的尾部插入一个数据时，我们需要考虑一个问题：原有空间是否可以容纳新的数据，是否需要扩容。
所以我们在插入数据时，要先调用 SLCheakCapacity函数来检查是否需要扩容。

代码实现：

void SLPushBack(SL* ps, SLDateType x)
{
	assert(ps);
	SLCheakCapacity(ps);//检查是否需要扩容
	ps->a[ps->size] = x;
	ps->size++;
}
1
2
3
4
5
6
7

---

7. 尾删

尾删：删除尾部最后的一个元素。

但尾删同样也要考虑一个问题，空间中是否还有数据给我们删除。
所以在进行尾删时，我们可以采用assert函数断言空间中还有数据。

代码实现：

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size >= 0);//断言空间中还有元素
	ps->size--;//下标减1
}
1
2
3
4
5
6

在删除数据时，我们不用将原有数据删除。只需要下标减1即可。
原因在于我们时根据下标来使用数据的，当下标减1后，尾部最后一个数据便无法进行访问。

Tips:

• 越界是不一定报错的，系统对越界的检查是一种设岗抽查。
• 以VS2022为例，微软公司在数据的开始前和结尾后的一小段空间设有一些特殊值。当程序结束或内存空间释放时，编译器就会检查这些值是否发生改变, 从而触发程序的保护机制。但如果这些值没有发生改变，即使发生越界访问，程序也不会报错。就像如果你酒驾，交警只在二环设关卡，但只要你不去二环，你就没事不会被发现。（每个编译器略有差异）

---

8. 头插

头插：在数据最开始地方插入数据。

同样，头插也要调用 SLCheakCapacity函数来检查空间是否足够，是否需要扩容。

代码实现：

void SLPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	SLCheakCapacity(ps);//检查是否需要扩容

	//移动数据
	int i = ps->size-1;
	while (i >= 0)
	{
		ps->a[i + 1] = ps->a[i];
		i--;
	}
	//移动数据完成，插入元素。同时有效个数加1
	ps->a[0] = x;
	ps->size++;
}

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

---

9. 头删

头删：删除数据最开始的元素。

思路和头插类似，只要下标从1开始，所有数据依次向前移动1位，再把有限个数减1即可。
同时头删也需要使用assert函数断言原有空间中还有数据可以删除。

代码实现：

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size >= 0);//空间中还有数据可以删除
	//移动数据
	for (int begin = 1; begin < ps->size; begin++)
	{
		ps->a[begin - 1] = ps->a[begin];
	}
	ps->size--;//有效个数减1
}
1
2
3
4
5
6
7
8
9
10
11

---

10. 插入任意位置数据

由于顺序表要求数据是连续存放的,所以我们只需要找到输入位置的下标pos即可。

【代码思路】：首先我们要检查输入下标是否合法，是有效下标；并检查是否有足够空间来容纳新数据，是否需要扩容。之后从输入的数据下标开始，所有元素向后移动一位，并把新数据插入到下标为pos处即可。

代码实现：

void SLInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);//检查下标是否合法
	SLCheakCapacity(ps);  //检查空间是否足够
	//移动数据
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

11. 删除任意位置数据

【代码思路】：和插入任何位置数据思想类似。首先我们要检查输入下标pos是否合法。之后从输入下标开始，后一个元素拷贝到前一个元素空间。

代码实现：

void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);//下标是否合法
	//移动数据
	int begin = pos+1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}

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

---

12. 查找

【代码思路】：要查找某个元素。由于这里只是最简单的查找，我们直接暴力查找，遍历整个数组返回下标即可。更为复杂的数据查找，会有更高阶的数据结构来实现。

代码实现：

int SLFind(SL* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->a[i])
			return i;
	}
	return -1;
}
1
2
3
4
5
6
7
8
9
10

---

13. 修改

【代码思路】： 要实现修改数据，我们只需要先判断输入下标是否合法。在将对应下标数据进行修改即可。

代码实现：

void SLModify(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = x;
}
1
2
3
4
5
6

---

四：所有代码

SeqList.h源文件

#include <assert.h>
#include <stdlib.h>


//动态顺序表
typedef int SLDateType;
typedef struct SeqList
{
	SLDateType* a;
	int size;
	int capacity;
}SL;


//对数据管理 --- 增删查改
void SLInit(SL* ps);
void SLDestory(SL* ps);
void SLPrint(SL* ps);
void SLCheakCapacity(SL* ps);

//头插头删 尾插尾删
void SLPushBack(SL* ps, SLDateType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDateType x);
void SLPopFront(SL* ps);


//返回下标，没找到返回-1
int SLFind(SL* ps, SLDateType);

//在pos位置插入x
void SLInsert(SL* ps, int pos, SLDateType x);
//在pos位置删除x
void SLErase(SL* ps, int pos);


void SLModify(SL* ps, int pos, SLDateType 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
36
37
38

SeqList.c头文件

#define _CRT_SECURE_NO_WARNINGS

#include "SeqList.h"


void SLInit(SL* ps)
{
	assert(ps);
	ps->a = (SLDateType*)malloc(4 * sizeof(SLDateType));
	if (ps->a == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	//开辟成功
	ps->capacity = 4;
	ps->size = 0;
}


void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = ps->size = 0;
}

void SLPrint(SL* ps)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->a[i]);
	}
	printf("\n");
}

void SLCheakCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)
	{
		SLDateType* tmp = (SLDateType*)realloc(ps->a, ps->capacity * sizeof(SLDateType) * 2);
		if (tmp == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity *= 2;
	}
}


void SLPushBack(SL* ps, SLDateType x)
{
	assert(ps);
	/*SLCheakCapacity(ps);
	ps->a[ps->size] = x;
	ps->size++;*/

	SLInsert(ps, ps->size, x);
}


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


void SLPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	SLCheakCapacity(ps);

	//移动数据
	/*int i = ps->size-1;
	while (i >= 0)
	{
		ps->a[i + 1] = ps->a[i];
		i--;
	}
	ps->a[0] = x;
	ps->size++;*/
	SLInsert(ps, 0, x);
}


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


int SLFind(SL* ps, SLDateType x)
{
	assert(ps);
	for (int i = 0; i < ps->size; i++)
	{
		if (x == ps->a[i])
			return i;
	}
	return -1;
}


void SLInsert(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos <= ps->size);
	SLCheakCapacity(ps);

	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	ps->a[pos] = x;
	ps->size++;

}



void SLErase(SL* ps, int pos)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);

	int begin = pos+1;
	while (begin < ps->size)
	{
		ps->a[begin - 1] = ps->a[begin];
		begin++;
	}
	ps->size--;
}



void SLModify(SL* ps, int pos, SLDateType x)
{
	assert(ps);
	assert(pos >= 0 && pos < ps->size);
	ps->a[pos] = 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
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

---