【手撕数据结构】把玩顺序表

顺序表介绍

顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组

线性结构又是什么意思，这就不得不提到线性表了

线性表（linear list）是n个具有相同特性的数据元素的有限序列线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串

注意的是，他在逻辑结构上一定是连续的，但在物理结构上不一定是连续的.线性
表在物理上存储时，通常以数组和链式结构的形式存储

那么我们知道，数组在内存中存储也是连续的，并且也是类型一致，那么他与顺序表的区别是什么呢.

• 顺序表的底层结构是数组，对数组的封装，实现了常⽤的增删改查等接⼝
• 顺序表的长度可以动态增长，普通数组的长度是固定的。

初始化顺序表

首先，我们要创建一个顺序表类型，该顺序表类型包括了顺序表的起始位置、记录顺序表内已有元素个数的计数器(size)，以及记录当前顺序表的容量的变量(capacity)。

typedef int SLDataType;//本篇博客以存放整型数据为例

typedef struct SeqList
{
	SLDataType* a;//声明了一个指向顺序表的指针，姑且称它为“顺序表指针”
	int size;//记录当前顺序表内元素个数
	int capacity;//记录当前顺序表的最大容量
}SeqList;

1
2
3
4
5
6
7
8
9

然后，我们需要一个初始化函数，对顺序表进行初始化。

//初始化顺序表
void SeqListInit(SeqList* ps)
{
	assert(ps);
	ps->a = NULL;//刚开始时顺序表为空，顺序表指针为NULL
	ps->size = 0;//起始时元素个数为0
	ps->capacity = 0;//容量为0
}

1
2
3
4
5
6
7
8
9

销毁顺序表

因为顺序表所用的内存空间是动态开辟在堆区的，所以我们在使用完后需要及时对其进行释放，避免造成内存

//销毁顺序表
void SeqListDestory(SeqList* ps)
{
	assert(ps);
	free(ps->a);//释放顺序表指针指向的空间
	ps->a = NULL;//及时置空
	ps->size = 0;//元素个数置0
	ps->capacity = 0;//容量置0
}

1
2
3
4
5
6
7
8
9
10

若需要对数据进行保存，可以使用文件操作函数将数据保存到一个文件中，下次使用顺序表的时候先读取文件数据即可

打印顺序表

void SeqListPrint(SeqList 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
11
12

增加数据

仔细想一想，我们每次增加数据的时候是不是应该都要检查一下存储数据的空间是否还足够存储增加的数据，如果不够我们是不是又要申请一块内存空间来存储数据，那一块一块的申请吗，是不是有点太麻烦了。所以由数学推理，这里最好每次申请原空间的2倍或3倍

//检查顺序表容量是否已满，若已满，则增容
void SeqCheckCapacity(SeqList* ps)
{
	if (ps->size == ps->capacity)//满了，需要增容
	{
		//判断顺序表容量是否为0，若为0，则先开辟用于存放4个元素的空间大小，若不为0，则扩容为原来容量的两倍
		int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* newA = realloc(ps->a, newcapacity*sizeof(SLDataType));
		if (newA == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		ps->a = newA;//开辟成功，将顺序表指针更新
		ps->capacity = newcapacity;//容量更新
	}
}


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

头插

要想在顺序表的表头插入数据，那么就需要先将顺序表原有的数据从后往前依次向后挪动一位，最后再将数据插入表头

//头插
void SeqListPushFront(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqCheckCapacity(ps);//检查容量
	int i = 0;
	for (i = ps->size; i > 0; i--)//将数据从后往前依次向后挪
	{
		ps->a[i] = ps->a[i - 1];
	}
	ps->a[0] = x;
	ps->size++;//顺序表元素个数加一
}


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

注意：注意：挪动数据的时候应从后向前依次挪动，若从前向后挪动，会导致后一个数据被覆盖。

尾插

尾插相对于头插就比较简单了，直接在表尾插入数据即可。

//尾插
void SeqListPushBack(SeqList* ps, SLDataType x)
{
	assert(ps);
	SeqCheckCapacity(ps);//检查容量,这里一定要注意传ps,而不是传&ps,&ps是二级指针，且穿过去会初始化一个随机值，
	ps->a[ps->size] = x;
	ps->size++;//顺序表元素个数加一
}

1
2
3
4
5
6
7
8
9

指定位置下标插入

void SLInsert(SL* ps, SLDataType x, int pos)
{
	assert(ps);
	//assert(pos >= 0 && pos < ps->size);
	assert(pos >= 0 && pos <= ps->size);	//这里之所以可以pos<=ps->size，因为我们是在之前插，这里就相当于是尾插
	CheckCapacity(ps);
	for (int 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

这里与上面的尾插和头插异曲同工，要注意的是pos的值是可以=ps->size的，当他在size的位置前插入的时候就相当于是尾插,然后根据从ps->size从后向前覆盖移动，直到i等于pos结束,这里i>pos，是因为我们要通过arr[i-1]来赋值,当pos等于0时i最小值是在1,也就是取到最小的下标就是1-1=0,不会造成段错误(数组越界).

删除顺序表元素

尾删

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size);	//顺序表得有有效的数据才能删除
	ps->size--;	//只要减去有效数据个数不管是后面插入还是打印都不影响，插入都可以通过在size的下一个位置直接插入覆盖元数据

}
1
2
3
4
5
6
7

这里肯定有人会疑惑为什么直接把size–就可以了，而不是把要删除数据的内存空间释放了，大可不必，我们建立顺序表就是为了使用增删查改的方法，而这些方法几乎都和我们size成员，即有效成员个数挂钩，比如说是打印方法，我们最多打印到ps->size个数据，头/尾插，我们在从size下标那里开始插入，所以我们–size就相当于删除了一个数据，即使是再次插入那个位置的数据，也不会影响结果，因为我们可以直接覆盖原来的数据.

头删

void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size);
	/*if (ps->size == 1)
	{
		ps->arr = NULL;
		ps->size--;
	}
	else
	{*/
	//这里之所以前面不进行单独只有一个节点判断，同尾删一样，即使下面把尾删的数据赋值到arr[0],下次插入数据时会覆盖
		for (int i = 0; i < ps->size-1; i++)
		{
			ps->arr[i] = ps->arr[i + 1];
		}
		--ps->size;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这里不用说了，与尾删一样

指定位置删除

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