顺序表的定义和基本操作

顺序表：

用顺序存储的方式实现线性表顺序存储，把逻辑上相邻的元素存储在物理位置也相邻的存储单元中，元素之间的关系有存储单元的邻接关系来体现。

二者之间关系如下图所示：

顺序表的实现-----静态分配：

设置数据元素默认值的重要性：

设置的：

#include
#define Maxsize 10
typedef struct
{
	int data[Maxsize];
	int length;
}SqList;
void InitList(SqList &L)
{
	for (int i = 0; i < Maxsize; i++)
	{
		L.data[i] = 0;//初始化顺序表：设置数据元素的默认值
	}
	L.length = 0;//顺序表中最开始没有任何数据，因此长度为0
}
int main()
{
	SqList L;//声明顺序表
	InitList(L);//初始化顺序表
	for (int i = 0; i < Maxsize; i++)
	{
		printf("data[%d]=%d\n", i, L.data[i]);
	}
	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

输出如下：

将设置默认值的代码删去：

输出如下：
出现这些数据的原因即为我们进行初始化顺序表之后，系统为其开辟了一段空间，但由于我们对其中的值并没有设置默认值，这块空间之前存有的数据还保留在这个空间中。

但其实我们所编写的main函数也是有问题的：

//尝试“违规打印整个data数组”
for (int i = 0; i < Maxsize; i++)
{
	printf("data[%d]=%d\n", i, L.data[i]);
}
1
2
3
4
5

违规的原因在于Maxsize是顺序表的最大长度，并不是当前长度，那有的小伙伴会说，既然用不了Maxsize,那么L.length总可以吧？其实也不可以，不信你替换成L.length你会发现程序是没有任何输出的,因为我们不应该访问大于顺序表实际长度的元素。

最好的做法就是使用我们上篇文章所讲的基本操作中的GetElem（L,I）进行访问，选用这种正确的方法，把各个数据元素的值设为默认值这一步骤就可以省略了。

但是L.length=0（将顺序表的长度初始化为0），这一步骤可不能省略哦，和上面的原因相同，内存为顺序表开辟的这一块空间，你并不知道之前存放了什么样的数据。

直接放图会比较好理解：

相信不少学过C语言的同学会有这样的疑问，那在C语言中为什么我没有设定初始值，系统就会默认给初始值为0呢？实际上做这个初始化工作的是编译器，你在VS编译器下系统会帮你进行初始化，但并不是所有的编译器都像VS那么暖心，因此我们还是自己操作吧。

静态分配的缺点：

原因：

int data[Maxsize];
1

上述这种用静态数组存放数据元素，这里的Maxsize一旦设置好是不能改变的，因此，如果当数组元素放满了之后，只能拜拜了，因为存储空间是静态的，无法被改变。

既然我们“怕存满”，那为什么不直接在设置长度的时候设置一个超大的呢？
这样根本就不怕，enmmm,确实是空间足够大了，但是你不觉得这样很浪费？假设你在设置长度的时候给定的长度为10000，结果你实际只用了10，这样就浪费了一大块的存储空间啊，所以还是好好继承中华传统美德“节约光荣，浪费可耻”。

由此我们可得出一个结论：静态分配具有很大的局限性，因为容量是固定不变的。

顺序表的实现-----动态分配：

C语言规定了动态空间的申请函数malloc和释放该空间的函数free，他们所包含的头文件#include

malloc函数：

功能：分配所需的连续内存空间

free函数：

free 函数没有返回值，它的功能是释放指针变量 data所指向的内存单。此时data所指向的那块内存单元将会被释放并还给操作系统，不再归它使用。

操作系统可以重新将它分配给其他变量使用，但释放并不是指清空内存空间，而是指将该内存空间标记为 “可用”状态，使操作系统在分配内存时可以将它重新分配给其他变量使用。

注：

只有动态创建的内存才能用 free 把它释放掉，静态内存是不能用free释放的。静态内存只能由系统释放。

代码实现动态内存分配：

#include
#include
#define Initsize 10
//顺序表的定义
typedef struct {
	int* data;
	int length;
	int Maxsize;
}SeqList;
//顺序表的内存分配
void InitList(SeqList& L)
{
	L.data = (int*)malloc(sizeof(int*)*Initsize);
	L.length = 0;
	L.Maxsize = Initsize;
}
//调用顺序表
int main()
{
	SeqList L;
	InitList(L);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

如果此时出现了上述静态分配中出现的问题，数组存满了，该怎么办呢？
此时我们可以使用Increasesize(SeqList &L, int len)函数。

Increasesize函数：

该函数的功能是把已有元素的数组赋值给新建的int *p。自己再从新开辟一片能够存下原来的值和新增加的长度的空间。

此时L.data是为没有元素的，下面进行循环遍历把旧的元素给赋值过来。还剩下给新的元素留下的空间地址。这样就实现了动态分配了。

用代码实现：

#include
#include
#define Initsize 10
---snip---
void Inicreasesize(SeqList& L, int len)
{
	int* p = L.data;//将扩充前的数据赋值给新的指针P
	L.data = (int*)malloc(sizeof(int) * (L.Maxsize + len));//扩宽顺序表的长度
	for (int i = 0; i < L.length; i++)//实现原数据的复制
	{
		L.data[i] = p[i];
	}
	L.Maxsize = L.Maxsize + len;//将最大长度修改为扩宽后的长度
	free(p);//释放内存空间
}
int main()
{
	SeqList L;
	InitList(L);
	Inicreasesize(L, 5);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

分析过程如下：

顺序表的特点：

1：随机访问：可实现在O(1)【常数级】时间内找到第i个元素，这也得益于它的按顺序存储的特点。
代码实现方法：data[i-1]

2:存储密度高，每个节点只存储数据元素。

相比于链式存储模式，既存放数据元素还存放对应的指针来说，顺序存储模式只存储数据元素。

3：拓展容量不方便（静态分配直接就是不能拓展容量，虽然动态分配可以拓展，但是拓展长度的时间复杂度也比较高）

4：插入，删除操作不方便，需要移动大量元素，这个特点也是和顺序存储模式有关