数据结构【顺序表】

1.顺序表的概念

在认识顺序表之前，让我们先认识下线性表。

线性表

线性表是由n个相同类型的数据所组成的有限序列，线性表是一种在现实里被广泛使用的，常见的线性表有：顺序表、链表、栈、队列等等。
线性表在逻辑结构一定连续，但在物理结构中并不一定是连续的。

物理结构

物理结构就是数据存储于内存的结构，就那数组来说，数组开辟的空间是连续的，第x个数据的空间的下一块空间就是第x+1个数据，这就是物理结构连续。

如果我在设计表的时候，专门设计一个指针用来存放下一个数据的地址。
如下图：

第x数据和第x+1数据的空间并不是连续的，而是被指针位连接的，是像一个绳子，每个数据位就相当于绳结，指针位相当于绳结后面的绳子，这就是物理结构不连续。

逻辑结构

逻辑结构是我们自己抽象出来的，对于线性表来说，它的逻辑结构我们就可以把他想象成直线的线性结构，就拿上面物理结构不连续的例子来说，尽管它第一个数据和第二个数据在空间上并不是连续，但是我们可以把它们想象是连续的。
就类似于下图：

顺序表是线性表的一种，顺序表的特点就是物理层面和逻辑层面都连续，数据与数据之间都是相邻的
顺序表的底层是数组!!!

2.顺序表的分类

顺序表可以分为静态和动态两种

2.1静态顺序表

在创建之前将大小固定，这样虽然很简单，但是有局限性；如果给定的数据多了，就无法完整的存储数据；如果给定的数据少了，就会造成空间的浪费

typedef int SQLDATATYPE;
typedef struct SQList
{
	SQLDATATYPE a[100];//给定了100个数据，后续无法改动大小
	int size;//当前数据的个数
}SQList;

1
2
3
4
5
6
7

哪有什么方法可以解决呢？

2.2动态顺序表

内存大小是不固定的，需要使用时再进行动态开辟，如果后面有多的数据要存储，就可以使用realloc函数来进行增容，所以就更加的灵活

typedef int SQLDATATYPE;
typedef struct SQList
{
	SQLDATATYPE* a;
	int size;//当前数据的个数
	int capacity;//当前顺序表的容量
}SQList;
1
2
3
4
5
6
7

我们本章讲解的是动态顺序表

3.顺序表接口的实现

首先我们需要一个头文件和一个源文件；
头文件是用来声明顺序表函数的，源文件是用来实现顺序表函数的实现

头文件(SQList.h)如下

#pragma once

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

//typedef int SQLDATATYPE;
//typedef struct SQList
//{
//	SQLDATATYPE a[100];//给定了100个数据，后续无法改动大小
//	int size;//当前数据的个数
//}SQList;

typedef int SQLDATATYPE;
typedef struct SQList
{
	SQLDATATYPE* a;
	int size;//当前数据的个数
	int capacity;//当前顺序表的容量
}SQList;

//初始化顺序表
void SQListInit(SQList* plist);
//销毁顺序表
void SQListDestroy(SQList* plist);

//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x);
//删除(尾部)
void SQListPopBack(SQList* plist);

//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x);
//删除(头部)
void SQListPopFront(SQList* plist);

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x);

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x);
//删除(指定位置)
void SQListDelete(SQList* plist, int pst);


//打印顺序表
void SQListPrint(SQList* plist);

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

源文件

记住要包含头文件

#include"SQList.h"
1

初始化顺序表

//初始化顺序表
void SQListInit(SQList* plist)
{
	plist->a = NULL;
	//其实也可以在初始化的时候就给a开辟空间(看个人喜好)
	plist->size = plist->capacity = 0;
}
1
2
3
4
5
6
7

一定要传址调用，这样才能真正的改变到顺序表

销毁顺序表

//销毁顺序表
void SQListDestroy(SQList* plist)
{
	assert(plist);
	free(plist->a);
	plist->a = NULL;//这一步是为了让a不会野指针
					//也可以避免a被重复释放(free函数不会对NULL进行操作)
	plist->size = plist->capacity = 0;
}
1
2
3
4
5
6
7
8
9

插入

插入就意味这内容的增加，就必然会导致内容空间的不足，这时候我们就需要进行扩容。

扩容

我们在插入之前要看，内部是否还有空间可以让我们插入，当size==capacity时，就代表表内已经填满数据了，我们就需要进行扩容
扩容用到的是realloc函数，我们扩容是默认是以两倍来扩容

尾插

void SQListPushBack(SQList* plist, SQLDATATYPE x)
{
	assert(plist);//检查plist是否为空指针
	if (plist->size == plist->capacity)//判断空间是否满了
	{
		int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
		//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

		SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		plist->a = tmp;//将调整的空间赋给顺序表
		plist->capacity = NewCapacity;//调整容量
	}
	plist->a[plist->size] = x;
	plist->size++;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

头插

头插我们就会遇到一个问题。
我们不能直接在顺序表的头部进行插入，这样会覆盖掉顺序表原来的数据，会造成数据的丢失。

解决方法也很简单
我们将整个顺序表往后挪动一位，让下标为x的数据等于下标为x-1的数据。
因为我们size处是一个待插入数据的空间，所以这样并不会造成数据的丢失。

代码如下：

void SQListPushFront(SQList* plist, SQLDATATYPE x)
{
	assert(plist);//检查plist是否为空指针
	if (plist->size == plist->capacity)
	{
		int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
		//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

		SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		plist->a = tmp;//将调整的空间赋给顺序表
		plist->capacity = NewCapacity;//调整容量
	}

	for (int i = plist->size; i > 0; i--)//将整个顺序表往后挪动一位
	{
		plist->a[i] = plist->a[i - 1];
	}

	plist->a[0] = x;
	plist->size++;
}
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

封装扩容函数

这时候我们看到，尾插函数和头插函数有一段代码是一模一样的，我们接下来还有个指定位置前的插入，它也是可能会进行扩容函数的，如果这三个函数都使用一段相同的代码，就会显得代码很冗余。

我们就可以将这段代码抽离出来，封装成一个独立的函数，需要扩容的时候调用该函数就可以了。

代码如下：

//扩容函数
//因为扩容函数是在源代码运行的，所以可以不用在头文件进行声明(当然你也可以在头文件进行声明  看个人喜好)
void SQListAdd(SQList* plist)
{
	int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
	//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

	SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
	if (tmp == NULL)
	{
		perror("realloc fail");
		exit(1);
	}
	plist->a = tmp;//将调整的空间赋给顺序表
	plist->capacity = NewCapacity;//调整容量
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

删除

尾删

//删除(尾部)
void SQListPopBack(SQList* plist)
{
	assert(plist);
	assert(plist->size > 0);//如果为0了，我还删什么呢？

	plist->size--;//这里很简单，就是将他的size进行--
	//size指向的是尾数据的下一块空间，也就是待插入的空间
	//我们--size，就相当于把尾数据的空间变成了待插入的空间
	//我们新增数据的时候，会把原来的值覆盖掉的
}
1
2
3
4
5
6
7
8
9
10
11

头删

这里有个问题

因为是删除头元素，我们不能直接将size–。

解决方法也很简单

将整个顺序表往前挪动一位，原理和头插的解决方法是类似的。

代码如下：

//删除(头部)
void SQListPopFront(SQList* plist)
{
	assert(plist);
	assert(plist->size > 0);//如果为0了，我还删什么呢？

	for (int i = 0; i < plist->size - 1; i++)//将整个顺序表往前挪动一位
	{
		plist->a[i] = plist->a[i + 1];
	}

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

查找元素

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x)
{
	assert(plist);
	int i = 0;
	while (i < plist->size)//size-1处就是最后一个数据
	{
		if (plist->a[i] == x)//找到了
			return i;//返回的是下标
		i++;
	}
	//i=size 跳出循环
	//找不到
	return EOF;//EOF(-1)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在指定位置前插入数据

情况一(指定的位置不是首元素)

我们就将指定位置及以后的数据往后挪一位;，再将数据插入到指定位置的下标。

情况二(指定的位置是首元素)

那么是首元素了，我们在首元素前进行插入，这是什么？
这不就是头插吗
所以我们可以直接调用我们已经写好的头插函数

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x)
{
	assert(plist);
	if (plist->size == plist->capacity)
	{
		SQListAdd(plist);//这里就直接调用了增容函数
	}

	//这里有两种情况
	//第一种当pst不是首元素
	if (pst != 0)
	{
		for (int i = plist->size; i > pst; i--)//将顺序表pst后面的数据往后挪动一位
		{
			plist->a[i] = plist->a[i - 1];
		}
		plist->a[pst] = x;
	}

	//第二种:当pst是首元素
	//那么是首元素了，我们在首元素前进行插入，这是什么？
	//这不就是头插吗
	//所以我们可以直接调用我们已经写好的头插函数
	else
	{
		SQListPushFront(plist, 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

删除指定位置

我们只要将指定位置后面的数据往前挪动一位

//删除(指定位置)
void SQListDelete(SQList* plist, int pst)
{
	assert(plist);
	assert(plist->size > 0);//如果为0了，我还删什么呢

	for (int i = pst; i < plist->size - 1; i++)//将pst后面的数据往前挪动一位
	{
		plist->a[i] = plist->a[i + 1];
	}
	plist->size--;
}

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

打印顺序表

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

完整代码

SQList.h

#pragma once

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

//typedef int SQLDATATYPE;
//typedef struct SQList
//{
//	SQLDATATYPE a[100];//给定了100个数据，后续无法改动大小
//	int size;//当前数据的个数
//}SQList;

typedef int SQLDATATYPE;
typedef struct SQList
{
	SQLDATATYPE* a;
	int size;//当前数据的个数
	int capacity;//当前顺序表的容量
}SQList;

//初始化顺序表
void SQListInit(SQList* plist);
//销毁顺序表
void SQListDestroy(SQList* plist);

//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x);
//删除(尾部)
void SQListPopBack(SQList* plist);

//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x);
//删除(头部)
void SQListPopFront(SQList* plist);

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x);

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x);
//删除(指定位置)
void SQListDelete(SQList* plist, int pst);


//打印顺序表
void SQListPrint(SQList* plist);

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

SQList.c

#include"SQList.h"

//初始化顺序表
void SQListInit(SQList* plist)
{
	plist->a = NULL;
	//其实也可以在初始化的时候就给a开辟空间(看个人喜好)
	plist->size = plist->capacity = 0;
}

//销毁顺序表
void SQListDestroy(SQList* plist)
{
	assert(plist);
	free(plist->a);
	plist->a = NULL;//这一步是为了让a不会野指针
					//也可以避免a被重复释放(free函数不会对NULL进行操作)
	plist->size = plist->capacity = 0;
}

//扩容函数
//因为扩容函数是在源代码运行的，所以可以不用在头文件进行声明(当然你也可以在头文件进行声明  看个人喜好)
void SQListAdd(SQList* plist)
{
	int NewCapacity = plist->capacity == 0 ? 4 : 2 * plist->capacity;//此处为一个三目表达式
	//如果plist->capacity==0为真，将4赋给NewCapacity;反之则赋值2*plist->capacity

	SQLDATATYPE* tmp = (SQLDATATYPE*)realloc(plist->a, NewCapacity * sizeof(SQLDATATYPE));
	if (tmp == NULL)
	{
		perror("realloc fail");
		exit(1);
	}
	plist->a = tmp;//将调整的空间赋给顺序表
	plist->capacity = NewCapacity;//调整容量
}

//插入(尾部)
void SQListPushBack(SQList* plist, SQLDATATYPE x)
{
	assert(plist);//检查plist是否为空指针
	if (plist->size == plist->capacity)
	{
		SQListAdd(plist);
	}
	plist->a[plist->size] = x;
	plist->size++;
}

//删除(尾部)
void SQListPopBack(SQList* plist)
{
	assert(plist);
	assert(plist->size > 0);//如果为0了，我还删什么呢？

	plist->size--;//这里很简单，就是将他的size进行--
	//size指向的是尾数据的下一块空间，也就是待插入的空间
	//我们--size，就相当于把尾数据的空间变成了待插入的空间
	//我们新增数据的时候，会把原来的值覆盖掉的
}

//插入(头部)
void SQListPushFront(SQList* plist, SQLDATATYPE x)
{
	assert(plist);//检查plist是否为空指针
	if (plist->size == plist->capacity)
	{
		SQListAdd(plist);
	}

	for (int i = plist->size; i > 0; i--)//将整个顺序表往后挪动一位
	{
		plist->a[i] = plist->a[i - 1];
	}

	plist->a[0] = x;
	plist->size++;
}

//删除(头部)
void SQListPopFront(SQList* plist)
{
	assert(plist);
	assert(plist->size > 0);//如果为0了，我还删什么呢？

	for (int i = 0; i < plist->size - 1; i++)//将整个顺序表往前挪动一位
	{
		plist->a[i] = plist->a[i + 1];
	}

	plist->size--;
}

//查找元素
int SQListFind(SQList* plist, SQLDATATYPE x)
{
	assert(plist);
	int i = 0;
	while (i < plist->size)//size-1处就是最后一个数据
	{
		if (plist->a[i] == x)//找到了
			return i;//返回的是下标
		i++;
	}
	//i=size 跳出循环
	//找不到
	return EOF;//EOF(-1)
}

//插入(指定位置前)
void SQListInsect(SQList* plist, int pst, SQLDATATYPE x)
{
	assert(plist);
	if (plist->size == plist->capacity)
	{
		SQListAdd(plist);
	}

	//这里有两种情况
	//第一种当pst不是首元素
	if (pst != 0)
	{
		for (int i = plist->size; i > pst; i--)//将顺序表pst后面的数据往后挪动一位
		{
			plist->a[i] = plist->a[i - 1];
		}
		plist->a[pst] = x;
	}

	//第二种:当pst是首元素
	//那么是首元素了，我们在首元素前进行插入，这是什么？
	//这不就是头插吗
	//所以我们可以直接调用我们已经写好的头插函数
	else
	{
		SQListPushFront(plist, x);
	}
}

//删除(指定位置)
void SQListDelete(SQList* plist, int pst)
{
	assert(plist);
	assert(plist->size > 0);//如果为0了，我还删什么呢

	for (int i = pst; i < plist->size - 1; i++)//将pst后面的数据往前挪动一位
	{
		plist->a[i] = plist->a[i + 1];
	}
	plist->size--;
}

//打印顺序表
void SQListPrint(SQList* plist)
{
	assert(plist);
	if (plist->size == 0)
		printf(NULL);
	for (int i = 0; i < plist->size; i++)
	{
		printf("%d ", plist->a[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

test.c (测试部分)

#include"SQList.h"

void TestSQL()
{
	SQList sq;
	SQListInit(&sq);

	SQListPushBack(&sq, 1);
	SQListPushBack(&sq, 2);
	SQListPushBack(&sq, 3);
	SQListPushBack(&sq, 4);
	SQListPushBack(&sq, 5);
	SQListPushBack(&sq, 6);

	SQListPushFront(&sq, 0);

	SQListPopBack(&sq);
	SQListPushBack(&sq, 128);
	//SQListPrint(&sq);
	//SQListPopFront(&sq);
	//SQListPrint(&sq);

	int flag = SQListFind(&sq, 3);
	//if (flag != EOF)
	//{
	//	printf("找到了 下标为%d\n", flag);
	//}
	//else
	//{
	//	printf("找不到\n");
	//}

	SQListInsect(&sq, flag, 255);

	//SQListDelete(&sq, flag);

	SQListPrint(&sq);

	SQListDestroy(&sq);
}

int main()
{
	TestSQL();
	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

结语

最后感谢您能阅读完此片文章，如果有任何建议或纠正欢迎在评论区留言。

如果您认为这篇文章对您有所收获，点一个小小的赞就是我创作的巨大动力，谢谢！！！