静态顺序表

顺序表

顺序表和链表都是线性表的一种，此处介绍顺序表

数据的存储结构有分为逻辑存储结构和物理存储结构。

顺序表和链表(之后的文章会详解)实际上都是线性表，是因为他们的逻辑存储关系都是线性的，只是因为在计算机内存中存储的方式(物理存储结构)不同。

两种物理存储结构各有优劣，作为开发者，在不同的场景需要灵活选用相应的数据结构来存储数据，来促使我们的程序更高效的运行。

静态顺序表

静态顺序表，顾名思义，即为顺序表的大小一旦确定，在程序的运行过程中不能修改，通常利用数组来实现。

由于顺序表的大小不能修改，因此我们通过宏定义的方式来规定顺序表的大小

类型定义

#define MaxSize 10
typedef struct {
	int data[MaxSize];	//定义数组来存储数据
	int length;	//length表示当前表的长度
}Sqlist;

在结构体中，我们声明了一个数组用来存放数据，为了方便起见，笔者将数组的数据类型规定成了 int , 实际上，顺序表中的元素可以是任何数据类型。

我们将顺序表定义在结构体内，是为了更方便一点。因为这样我们不仅可以存储所有的数据，还可以补充存储关于顺序表的某些信息(视需求而定)， 这些另外存储的信息可以帮助我们更好的操作顺序表(其他数据结构也是类似)。

在操作的同时，只需要对函数传入指向结构体的指针(或者引用)就可以很方便的操作顺序表。

初始化

void Initlist(Sqlist& L) {
	L.length = 0;
	for (int i = 0; i < MaxSize; i++) {
		L.data[i] = 0;
	}
}

在C++中，新开辟的空间可能会有之前内存中遗留的数据，因此我们需要初始化数组中的内容，同时将数组的长度置为0.

在顺序表中插入元素

• i 传入需要插入的位置
• ele 需要插入的元素
  需要注意的是，插入后，插入的元素变成顺序表中的第 i 个元素

为了保留之前表中的数据，我们需要将原来的第 i 个元素以及之后的元素都后移，才能流出空余空间用于插入新元素。

数组中第 i 个元素 的下标为 i-1

bool ListInsert(Sqlist& L, int i, int ele) {
	if (i<1 || i>L.length + 1)//判断i是否有效
		return false;
	if (L.length >= MaxSize)//判断顺序表是否存满
		return false;
	for (int j = L.length; j >= i; j--) {//插入
		L.data[j] = L.data[j - 1];	//将第i个元素及之后的元素后移
	}
	L.data[i - 1] = ele;	//在位置i出放入元素ele
	L.length++;				//顺序表总长度+1
	return true;
}

插入完成后，顺序表的长度要加1

另外，插入元素时，需要判断插入的元素位置是否合法。总不能插到数组之外。另外也需要注意顺序表的容量。

删除顺序表中的元素

我们删除顺序表中的元素，不仅要删除，更要将被删除的元素返回，以便让使用我们的函数的清楚地知道自己删除了哪个元素。

因此我们传入一个引用类型的参数来接收被删除的值

此处同上，删除表中 第 i 个元素，下标为 i-1

bool ListDelete(Sqlist& L, int i, int& ele) {
	if (i<1 || i>L.length + 1)//判断i是否有效
		return false;
	ele = L.data[i - 1];//被删除的元素需要返回给调用函数的人
	for (int j = i-1; j <= L.length-1; j++)
		L.data[j] = L.data[j+1];
	L.length--;
	return true;
}

现将被删除的元素返回给参数 ele, 再将第 i 个元素后面元素全部向前移动,同时顺序表的长度减一。

顺序表的查找

以指定的方式查找顺序表中的元素

按值查找

按值查找返回相应元素在表中的位序

因此只需要遍历顺序表，当有元素与传入的元素相同时，返回其下标

int LocateEle(Sqlist& L, int ele) {
	for (int i = 0; i < L.length; i++)
		if (ele == L.data[i])	//	比较的时候需要考虑元素的类型，例如结构体和字符串不能直接用==判断
			return i + 1;	//返回其位序 i+1
}

按位查找

按位查找，即查找表中位序 为 i 的元素，并返回其值

需要判断传入的位序是否合理，不合理就抛出异常

int GetEle(Sqlist &L, int i) {	//查找顺序表中第i个(数组下标为i-1)元素的值
	if (i > L.length || i <= 0)
		return 1;   //如果下标越界需要进行报错处理，可以选择其他的抛出异常方式
	return L.data[i - 1];
}

从以上操作我们不难看出，顺序表在存储方面的优点和缺点

优点

• 存储密度大(数据本身的存储空间/结点所占的存储空间)
• 随机访问 我们在访问表中的元素时只需传入值或者位序即可，访问速度较快

缺点

• 在插入，删除相应的元素时，需要移动大量的元素，插入和删除操作的时间复杂度较高。
• 静态存储，初始化的表的大小难以更改，数据元素的更熟不能任意扩充。

综合优缺点，顺序表适合存储元素数量相对固定，访问较多，而插入和删除较少的线性数据类型。