顺序表的删除，插入和查找操作

顺序表的插入：

基本操作：在L的位序i处插入元素e
void ListInsert(SeqList& L,int i,int e)

假设，数组中的元素为5个，现在我们想实现在位序为3的位置插入一个数字。

那么内存中的空间分配。如下图所示：

#include
#include
#define Maxsize 10
//定义顺序表
typedef struct {
	int data[Maxsize];
	int length;
}SeqList;
//顺序表的初始化
void InitList(SeqList& L)
{
	L.length = 0;
}
//插入一个元素
void ListInsert(SeqList& L,int i,int e)//在i（表示位序）的位置，插入元素e
{
	for (int j = L.length; j >= i; j--)//将位置为3以后的元素整体向后移动一个位置
	{
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1 ]= e;//这里需要注意下表和位序的关系，下标是从0开始，位序是从1开始
	L.length++;//插入一个元素后，数组整体长度加一
}
int main()
{
	SeqList L;
	InitList(L);
	ListInsert(L, 3, 3);
	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
26
27
28
29
30

如果此时，你的小伙伴说想要使用你写的数据结构，他想在位序为9的位置插入3，请问这是可以实现的吗？

当然不可以，在经过上面的插入元素之后，此时我们的数组长度变为6，如果想在位序为9的位置插入3，那么：位序为6和7的地方是空的了，这显然不可以，因此，在插入元素的过程中，我们一定要注意位序i是有范围的：[i,length+1],那么针对上面小伙伴这种不能实现的情况，我们应实现在代码执行的时候进行错误或正确的提示。

因此代码可修改为：

bool ListInsert(SeqList& L,int i,int e)
{
	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];
	}
	L.data[i - 1 ]= e;
	L.length++;
	return true;//有效插入，返回true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

插入操作的时间复杂度：

要求时间复杂度，就要关注深层循环语句的执行次数与问题规模n的关系（这里不懂得同学移步至时间复杂度那篇文章）

而对于我们上述这个代码来说，时间复杂度和表长有关，原因是在插入的过程中，表中的元素需要不停的进行移动，而表长恰恰决定了循环的次数。

分析如下：

最好时间复杂度：新元素插入到表尾，不需要移动元素，i=n+1,循环0次时间复杂度:T=O（1）

最坏时间复杂度：新元素插入到表头，所有的元素都要进行移动，i=1,时间复杂度:T=O(n)

平均时间复杂度：新元素插到任何一个位置的概率相同，即i=1,2,3,4,length的概率都是p=1/n+1,i=1（插入表头）,循环n次，i=2，（插入到位序为2）循环n-1次…i=n+1,循环0次（插入表尾）
平均循环次数：=np+(n-1)p+(n-2)p+…+1*p=[n(n+1)/2]*1/n+1=(n/2)=O(n)

顺序表的删除：

删除表L中第i个位置的元素，并用e返回删除元素的值
void ListDelete(&L,i,&e)

#include
#include
#define Maxsize 10
//定义顺序表
typedef struct {
	int data[Maxsize];
	int length;
}SeqList;
//顺序表的初始化
void InitList(SeqList& L)
{
	L.length = 0;
}
//删除一个元素
bool ListDelete(SeqList& L,int i,int &e)//注意：必须有引用符号，才会实现真正意义上e的改变，否则我们进行的一系列操作都是其复制品，值实质并没有发生改变
{
	if (i<1 || i>L.length)//判断i的范围是否有效
		return false;
		e=L.data[i-1];//返回删除元素的值
	for (int j = i; j <L.length; j++)//依次向前移动
	{
		L.data[j-1] = L.data[j];
	}
	L.length--;
	return true;//有效插入，返回true
}
int main()
{
	SeqList L;
	int e=-1;//定义和数组中元素类型相同的变量，作用：将删除的元素“带回”
	InitList(L);
	if(ListDelete(L,3,e))//判断ListDelete函数的返回值
		printf("已经删除第三个元素，删除元素值为=%d\n",e);
	else
		printf("位序i不合法，删除失败\n");
	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
26
27
28
29
30
31
32
33
34
35
36
37

分析如下图所示：

注：
删除某元素后，其后面的元素移动先后顺序是：位序在前的先进行移动。
插入某元素后，其后面的元素移动先后顺序是：位序在后的先进性移动。

删除操作的时间复杂度：

和插入操作一样，同样需要关注深层循环语句的执行次数与问题规模n的关系

最好时间复杂度：删除表尾元素，不需要移动其他的元素，i=n,循环0次，此时时间复杂度为：T=O(1)

最坏时间复杂度：删除表头元素，所有的元素都需要发生移动，i=1,循环n-1次，此时时间复杂度为T=O(n)

平均时间复杂度：假设删除任何一个元素的概率相同，即i=1,2,3,…,length的概率都是p=1/n,i=1,（删除表头元素）循环n-1次，i=2（删除位序为2的元素）,循环n-2次…i=n（删除表尾元素）,循环0次
平均循环次数=（n-1）p+(n-2)p+…+1*p=[n(n-1)/2]*1/n=(n-1)/2=O(n)

顺序表的查找：

顺序表的按位查找：

GetElem(L,i):按位查找操作。获取表L中第i个位置的元素的值。

代码如下所示：

静态分配的方式：

#define Maxsize 10
typedef struct {
	ElemType data[Maxsize];
	int length;
}SqList;
ElemType GetElem(SqList L,int i)
{
	return L.data[i-1];
}
1
2
3
4
5
6
7
8
9

动态分配方式：

#define InitSize 10
typedef struct
{
	ElemType*data;//动态分配数组的指针，该指针指向顺序表中的第一个元素
	int Maxsize;
	int length;
}SeqList;
ELemType GetElem(SeqList L,int i)
{
	return L.data[i-1];
}
ElemType*data
1
2
3
4
5
6
7
8
9
10
11
12

分析如下所示：
向后查找的字节数与元素类型有关！

由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素----“随机存取”特性，因此它的时间复杂度为O（1）

顺序表的按值查找：

LocateElem(L,e):按值查找。在表L中查找具有给定关键字值的元素。

代码如下所示：

#define InitSize 10
typedef struct
{
	ElemType*data;//动态分配数组的指针，该指针指向顺序表中的第一个元素
	int Maxsize;
	int length;
}SeqList;
//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, ElemType e)
{
	for (int i = 0; i < L.length; i++)
	{
		if (L.data[i] == e)//所有的基本数据类型：int,char,double,foat等可以直接运用运算符'=='进行比较
		{
			return i + 1;//数组下标为1的元素值等于e,返回其位序i+1
		}
	}
	return 0;//退出循环，查找失败
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

但对于结构体这种类型是不能直接使用’=='来进行比较的，必须将结构的每个变量分别进行比较。

错误演示：

typedef struct {
	int num;
	int people;
}Customer;
void test()
{
	Customer a;
	a.num = 1;
	a.people = 1;
	Customer b;
	b.num = 1;
	b.people = 1;
	if (a == b)
		printf("相等");
	else
		printf("不相等");
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

正确如下所示：

if (a.num == b.num && a.people == b.people)
	printf("相等");
else
	printf("不相等");
1
2
3
4

按值查找的时间复杂度：

//在顺序表L中查找第一个元素值等于e的元素，并返回其位序
int LocateElem(SeqList L, ElemType e)
{
	for (int i = 0; i < L.length; i++)
		if (L.data[i] == e)
			return i + 1;
	return 0;
}
1
2
3
4
5
6
7
8

和删除插入相同，计算时间复杂度，其关注点即为最深层次循环语句的执行次数与问题规模n的关系。

分析如下：
最好时间复杂度：目标元素在表头，循环一次：时间复杂度为O（1）

最坏时间复杂度：目标元素在表尾，循环n次，时间复杂度为O（n）

平均时间复杂度：假设目标元素出现在任何一个位置的概率相同，都是1/n,那么当目标元素在表头，循环一次，在第二位，循环两次，以此类推，
平均循环次数=11/n+21/n+…+n*1/n=[[n(n+1)]/2]*1/n=(n+1)/2
平均复杂度=O（n）