🐱作者：一只大喵咪1201
🐱专栏：《数据结构与算法》
🔥格言：你只管努力，剩下的交给时间！

🐥线性表

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

本喵今天讲解的是动态的顺序表，也是我门最常用的顺序表结构。

🐥顺序表

🕊概述

顺序表是用一段连续的物理地址来存储一些相同类型的数据，一般都是用数组来存储，由此来实现对顺序表中数据的增删查改。

通常都是通过一个结构体来管理整个顺序表，增删查改不同的操作对应着不同的接口，也就是不同的函数。

当顺序表中的空间不够用时，可以使用realloc调整空间的大小。

🕊接口的实现

首先我门需要定义一个结构体类型，用来管理顺序表

typedef int SLDateType;//重命名数据类型

typedef struct SeqList
{
	SLDateType* a;
	int size;//数据个数
	int capacity;//顺序表容量
}SL;
1
2
3
4
5
6
7
8

为了以后能够更好的和C++中的库联系起来，我们采用比较标准的写法。

• 将int类型重命名为SLDateType，表示顺序表中的数据类型
• 将结构体重命名为SL，为了后面方便使用

接下来我们实现各个接口。

1. 顺序表初始化

void SLInit(SL* ps)
{
	assert(ps);//防止空指针
	ps->a = NULL;//数据存放地址初始化为空
	ps->capacity = ps->size = 0;//容量和数据个数初始化为0
}
1
2
3
4
5
6

• 将顺序表初始化为空，什么数据都没有。

2. 顺序表摧毁

void SLDestroy(const SL* ps)
{
	assert(ps);//防止空指针
	free(ps);//释放动态空间
	ps = NULL;//使指针失忆
}
1
2
3
4
5
6

• 在使用完顺序表以后，为了防止造成内存泄漏，必须将在堆区动态开辟的内存空间释放，还给操作系统。

3. 顺便表打印

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

• 打印主要是为了我们在调试的过程中看到结果

4. 尾增（从数组的末尾增加数据）

static void SLCheckCapacity(SL* ps)
{
	assert(ps);
	if (ps->size == ps->capacity)//数据个数和容量相等时增容
	{
		//新容量是旧容量的2倍
		int newcapacity = ps->capacity == 0 ? 2 : 2 * ps->capacity;
		//旧容量是0时，新容量是2
		ps->a = (SLDateType*)realloc(ps->a, newcapacity * sizeof(SLDateType));//扩容到新容量
		//检查是否扩容成功
		if (ps->a == NULL)
		{
			perror("realloc fail");
			return;
		}
		ps->capacity = newcapacity;//改变容量
	}
}

//尾增
void SLPushBack(SL* ps, SLDateType x)
{
	assert(ps);
	//判断是否增容
	SLCheckCapacity(ps);
	//插入数据
	ps->a[ps->size] = x;
	//增加数据个数
	ps->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
27
28
29
30

注意点：

在增加数据的时候，首先需要判断顺序表的容量是否够用，如果不够用就需要增容。

每次扩容扩成原来容量二倍的原因：

• 如果一次扩多了，会造成空间的浪费
• 扩的少了在增加数据的时候就需要频繁扩容，降低了程序的效率。
  realloc函数扩容存在原地扩容和异地扩容俩种情况，如果是异地的话无疑会更加增加扩容的成本，需要花费更多时间。
• 综合考虑俩种因素，扩成原来的二倍是比较合理的

我们知道，开辟动态空间使用的是malloc或者calloc函数，而realloc是用来扩容的，而我们这里仅使用realloc既实现开辟，又实现扩容。

仅用realloc不用malloc的原因：

• malloc仅在初始化后容量为0的时候开辟动态空间使用，之后的扩容都是使用到realloc，如果分情况写就会比较冗余
• realloc同样可以实现malloc的功能，当传给realloc的指针是空指针NULL的时候，realloc的功能和malloc是一样的，所以我们在初始化时也是将管理数据的指针设为空指针的

数据个数size的秒用：

• 当以数据个数为数组的下标时，它指向的是数组最后一个元素再往后一个元素的地址
  
  所以在尾增的时候，直接将数据放在数据个数为下标的位置即可。

5. 头增（从数组的开始处增加数据）

//头增
void SLPushFront(SL* ps, SLDateType x)
{
	assert(ps);
	//判断是否增容
	SLCheckCapacity(ps);
	//增加数据
	int end = ps->size;//指向原本数据中的下一个元素
	//将数据整体向后移动一位
	while (end > 0)
	{
		ps->a[end] = ps->a[end - 1];//从后向前覆盖
		end--;
	}
	ps->a[0] = x;
	ps->size++;//数据个数增加一个
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

• 头增时，需要将所有数据整体向后移动一个空间，而且必须是从后面的数据开始向前移动，否则会覆盖原有的数据。
• 头增的时间复杂度是O(N)，是有代价的，要谨慎使用

6. 尾删（从数组的末尾处删除数据）

//尾删
void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);//防止越界
	ps->size--;//数据个数减少一个
}
1
2
3
4
5
6
7

尾删后不减小动态空间的原因：

• realloc减小动态空间和扩容一样，也是有原地减容和异地减容，如果是异地减容的情况，无疑会增大减容成本，增加执行时间，减少效率
• 只减少数据个数，原本的空间不会被访问，而且可能被后来的数据覆盖掉

注意：
多次尾删可能会导致越界访问。

• 当数据的个数是0的时候，继续尾删会是size的值为-1，再次使用的时候就会造成越界访问
• 使用断言，将size的值控制在最小为0，否则就报错

6. 头删（从数组的开始处删除数据）

//头删
void SLPopFront(SL* ps)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size - 1; i++)
	{
		ps->a[i] = ps->a[i + 1];//从前向后覆盖
	}
	ps->size--;//数据个数减1
}
1
2
3
4
5
6
7
8
9
10
11

头删同样是覆盖，而且不需要减小动态内存空间。

• 头删时，将所有数据整体向前移动一个空间单位
• 要从前向后移动，否则前面的数据会被覆盖掉

7. 查找

//查找
int SLFind(const SL* ps, SLDateType x)
{
	assert(ps);
	int i = 0;
	for (i = 0; i < ps->size; i++)
	{
		//找到后返回下标
		if (ps->a[i] == x)
			return i;
	}
	return -1;//没有找到返回-1
}
1
2
3
4
5
6
7
8
9
10
11
12
13

8. 指定位置插入

//指定位置插入
void SLInsert(SL* ps, size_t pos, SLDateType x)
{
	assert(ps);
	//向后移动
	int end = ps->size - 1;
	while (end >= pos)
	{
		ps->a[end + 1] = ps->a[end];
		end--;
	}
	//插入
	ps->a[pos] = x;
	ps->size++;//数据个数加1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

插入的数据在原本指定位置的前面。

• 为了和以后C++的库相匹配，将形参的位置类型设置成size_t类型

上面的程序如果是size_t类型存在一个问题，当插入的位置是0的时候。

会出现如上错误。

原因：

• end是int类型的数据，当它为0时，再减1，在内存中的样子是0xffffffff
• 与size_t类型的pos比较的时候会发生算术转化，此时将0xffffffff看成是一个unsigned int类型的数据与pos比较，结果肯定是大，所以符合while的控制条件，循环会继续
• 如此一来就会形成死循环，所以会报错

如何解决这个问题，

1. 将pos强制类型转化成int类型
2. end直接定位在数组最后一个数据的下一个数据处

//指定位置插入
void SLInsert(SL* ps, size_t pos, SLDateType x)
{
	assert(ps);
	assert(pos <= ps->size);//确保插入的位置在数组中,可以尾插
	//向后移动
	size_t end = ps->size;
	while (end > pos)
	{
		ps->a[end] = ps->a[end - 1];
		end--;
	}
	//插入
	ps->a[pos] = x;
	ps->size++;//数据个数加1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

如此一来便解决了指定位置是0的这个问题。

9. 指定位置删除

//指定位置删除
void SLErase(SL* ps, size_t pos)
{
	assert(ps);
	assert(pos < ps->size);//确保位置在数组内
	//删除
	while (pos < ps->size - 1)
	{
		ps->a[pos] = ps->a[pos + 1];
		pos++;
	}
	ps->size--;//数据个数减1
}
1
2
3
4
5
6
7
8
9
10
11
12
13

将指定位置以后的数据整体向前移动一个空间大小

• 必须从前向后移动，否则会覆盖掉原本的数据

10. 指定位置修改

//指定位置修改
void SLModify(SL* ps, size_t pos, SLDateType x)
{
	assert(ps);
	assert(pos < ps->size);//确保该位置在数组内
	//修改
	ps->a[pos] = x;
}
1
2
3
4
5
6
7
8

顺序表源文件中的程序都在上面，最后给大家看一下自定义都文件SeqList.h中的代码：

#ifndef __SERLIST_H
#define __SERLIST_H

//共同用到的头文件
#include 
#include 
#include 

typedef int SLDateType;//重命名数据类型

typedef struct SeqList
{
	SLDateType* a;
	int size;//数据个数
	int capacity;//顺序表容量
}SL;

//顺序表初始化
void SLInit(SL* ps);

//顺序表摧毁
void SLDestroy(const SL* ps);

//顺序表打印
void SLPrint(const SL* ps);

//尾增
void SLPushBack(SL* ps, SLDateType x);

//头增
void SLPushFront(SL* ps, SLDateType x);

//尾删
void SLPopBack(SL* ps);

//头删
void SLPopFront(SL* ps);

//查找
int SLFind(const SL* ps, SLDateType x);

//指定位置插入
void SLInsert(SL* ps, size_t pos, SLDateType x);

//指定位置删除
void SLErase(SL* ps, size_t pos);

//指定位置修改
void SLModify(SL* ps, size_t pos, SLDateType x);

#endif
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

其中条件编译是为了避免多次引用该头文件，也可以用指令

#pragma once
1

可以达到同样的效果，但是不是所有的编译器都可以这样使用。

🐥总结

以上便是动态顺序表的详细介绍，我们在使用的时候，直接使用搭好的顺序表框架对内存中的数据进行管理就行，所以说这个框架是通用的。希望对各位有所帮助。