_2_顺序表

首先说到顺序表之前先说一下线性表的概念。
线性表就是n个具有相同特性元素的集合。线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的(注意，这句话只适用大部分线性表，而不是全部。比如，循环链表逻辑层次上也是一种线性表(存储层次上属于链式存储)，但是把最后一个数据元素的尾指针指向了首位结点)。
常见的线性表有：顺序表，链表，栈和队列，串；
下面介绍的就是顺序表

顺序表

概念

顺序表就是用物理地址连续的存储单元来存储数据，一般是使用数组来存储数据，在数组上面完成顺序表的增删查改，所以顺序表是支持随机访问的。

分类

顺序表分为两类
1，静态顺序表（也就是数组的大小是固定的）

2，动态顺序表（数组是动态开辟出来的长度可变）

这里的结构可以看到，如果使用了动态开辟的数组就需要额外的一个变量capacity来保存当前数组的容量是多少，如果使用静态顺序表则不用，因为容量是固定的，当size==capacity的时候就需要增容了。

关于动态顺序表这里还有一种结构，C++的STL库中的顺序表就是使用的这种成员结构，那就是用三个指针来管理整个动态数组

这里的start就是整个动态数组的开头，finish指向的位置就是当前数组最后一个元素的下一个位置，最后finish到endofstorage这块就是数组多开辟一部分空间预留，防止每次插入数据都要增容，实际上这两种结构都是一样的。finish - start就是size，endofstorage - start就是capacity。所以使用这两种都是可以的。

顺序表的数据必须从头开始依次向后存储，不可跳过一个位置，直接将数据存储到下一个位置。

顺序表代码实现

#pragma once
#include
#include
#include

typedef int SLDataType;
typedef struct SeqList
{
	SLDataType* val;
	size_t size;
	size_t capacity;
}SL;

//初始化
void SLInit(SL* ps);
//打印顺序表
void SLprint(SL* ps);
//尾插
void SLPushBack(SL* ps, SLDataType x);
//尾删
void SLPopBack(SL* ps);
//头插
void SLPushFront(SL* ps, SLDataType x);
//头删
void SLPopFront(SL* ps);
//查找
size_t SLFind(SL* ps, int x);
//随机插入
void insert(SL* ps, size_t pos, int x);
//删除
void erase(SL* ps, size_t pos);

//清空顺序表
void SLDestory(SL* ps);

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

上述就是头文件下面我们根据来逐步实现整个顺序表。线性表一般的实现都是覆盖了增删查改这几个方面。

---

void SLInit(SL* ps)
{
	assert(ps);
	ps->val = NULL;
	ps->size = 0;
	ps->capacity = 0;
}

void SLDestory(SL* ps)
{
	assert(ps);
	free(ps->val);
	ps->val = NULL;
	ps->size = 0;
	ps->capacity = 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这一块就是顺序表的初始化和清空，首先关于初始化一开始可以给一块malloc出来的空间，也可以不给都是额可以的。这里因为对ps这个指针进行了解引用，所以前面必须要断言，ps不能是空指针。

void SLprint(SL* ps)
{
	assert(ps);
	for (size_t i = 0; i < ps->size; i++)
	{
		printf("%d ", ps->val[i]);
	}
	puts("");
}
1
2
3
4
5
6
7
8
9

打印函数

//容量检查函数
void Check(SL* ps)
{
	if (ps->size == ps->capacity)
	{
		size_t newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
		SLDataType* tmp = (SLDataType*)realloc(ps->val, newcapacity*sizeof(int));
		if (tmp == NULL)
		{
			perror("realloc ");
			return;
		}
		ps->val = tmp;
		ps->capacity = newcapacity;
	}
}

void SLPushBack(SL* ps, SLDataType x)
{
	assert(ps);
	Check(ps);
	ps->val[ps->size] = x;
	ps->size++;
}

void SLPopBack(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	--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
31

这里独立出来了一个容量检查函数，每次插入之前都需要检查一下数组是否还有空间可以插入数据，空间不足对的时候就需要增容。增容这里要注意，不可以上来就二倍扩容，因为一开始的容量是0，二倍还是0，所以要进行判断。注意增容的时候也是不可以直接将增容后的空间地址赋值给val，如果增容失败就会导致原来的地址被覆盖成NULL了，所以需要先进行判断。

这里的删除不需要清空数据，赋值成0更是不可取，万一这里的数据本来就是0呢？所以直接size–就可以了。下次插入就会直接覆盖掉这个位置的数据。

void SLPushFront(SL* ps, SLDataType x)
{
	assert(ps);
	Check(ps);
	size_t end = ps->size;
	while (end > 0)
	{
		ps->val[end] = ps->val[end - 1];
		end--;
	}
	ps->val[0] = x;
	ps->size++;
}
void SLPopFront(SL* ps)
{
	assert(ps);
	assert(ps->size > 0);
	size_t begin = 0;
	while (begin < ps->size - 1)
	{
		ps->val[begin] = ps->val[begin + 1];
		begin++;
	}
	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

这里的函数就是头插和头删，这两个函数最主要的就是挪动数据，所以最好是先画图然后依照图来写代码，写法有很多，但是要注意这里的while边界条件判断的时候不可以写>=0因为无符号数是永远大于等于0的。

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

void insert(SL* ps, size_t pos, int x)
{
	assert(ps);
	Check(ps);
	size_t end = ps->size;
	while (end > pos)
	{
		ps->val[end] = ps->val[end - 1];
		end--;
	}
	ps->val[pos] = x;
	ps->size++;
}

void erase(SL* ps, size_t pos)
{
	assert(ps);
	assert(ps->size > 0);
	size_t begin = pos;
	while (begin < ps->size - 1)
	{
		ps->val[begin] = ps->val[begin + 1];
		begin++;
	}
	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
31
32
33
34
35
36
37

这里的查找函数可以配合后面在pos位置前插入一个数据或者是删除pos位置的数据一起使用。