Order table delete, insert and search operations

顺序表的插入：

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

假设,数组中的元素为5个,Now we want to implement the in-bit order as 3的位置插入一个数字.

Then the space allocation in memory.如下图所示：

#include<stdio.h>
#include<stdlib.h>
#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--)//将位置为3Subsequent elements are moved back one position as a whole
	{
    
		L.data[j] = L.data[j - 1];
	}
	L.data[i - 1 ]= e;//Here you need to pay attention to the relationship between the following table and bit order,下标是从0开始,位序是从1开始
	L.length++;//插入一个元素后,Increase the overall length of the array by one
}
int main()
{
    
	SeqList L;
	InitList(L);
	ListInsert(L, 3, 3);
	return 0;
}

如果此时,Your friend said he wanted to use the data structure you wrote,He wants to be in rank9的位置插入3,I wonder if this is achievable？

当然不可以,After going through the insert element above,At this point our array length becomes 6,If you want to be in bit order9的位置插入3,那么：位序为6和7The place is empty,这显然不可以,因此,在插入元素的过程中,We must pay attention to the bit orderi是有范围的：[i,length+1],So for the situation that the above small partners can't achieve,We should implement error or correct prompts when the code is executed.

So the code can be modified to：

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;//effective insertion,返回true
}

插入操作的时间复杂度：

要求时间复杂度,It is necessary to pay attention to the number of executions of the deep loop statement and the scale of the problemn的关系（I don't understand the article about the students moving to the time complexity here）

And for our above code,The time complexity is related to the table length,The reason is during insertion,Elements in the table need to keep moving,The length of the table just determines the number of cycles.

分析如下：

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

最坏时间复杂度：新元素插入到表头,All elements have to be moved,i=1,时间复杂度:T=O(n)

平均时间复杂度：The probability of a new element being inserted at any one position is the same,即i=1,2,3,4,length的概率都是p=1/n+1,i=1（插入表头）,循环n次,i=2,（Insert in the order of 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<stdio.h>
#include<stdlib.h>
#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)//注意：Quote symbols are required,in the true sensee的改变,Otherwise, the series of operations we perform are copies of it,The value has not changed substantially
{
    
	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;//effective insertion,返回true
}
int main()
{
    
	SeqList L;
	int e=-1;//Define a variable of the same type as the elements in the array,作用：将删除的元素“带回”
	InitList(L);
	if(ListDelete(L,3,e))//判断ListDelete函数的返回值
		printf("已经删除第三个元素,删除元素值为=%d\n",e);
	else
		printf("位序i不合法,删除失败\n");
	return 0;
}

分析如下图所示：

注：
删除某元素后,The order in which the elements behind it are moved is：The bit sequence is moved first.
After inserting an element,The order in which the elements behind it are moved is：The advanced nature of the bit sequence is moved later.

删除操作的时间复杂度：

和插入操作一样,It is also necessary to pay attention to the number of executions of deep loop statements and the size of the problemn的关系

最好时间复杂度：删除表尾元素,No other elements need to be moved,i=n,循环0次,此时时间复杂度为：T=O(1)

最坏时间复杂度：删除表头元素,All elements need to move,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个位置的元素的值.

代码如下所示：

way of static allocation：

#define Maxsize 10
typedef struct {
    
	ElemType data[Maxsize];
	int length;
}SqList;
ElemType GetElem(SqList L,int i)
{
    
	return L.data[i-1];
}

动态分配方式：

#define InitSize 10
typedef struct
{
    
	ElemType*data;//动态分配数组的指针,The pointer points to the first element in the sequence table
	int Maxsize;
	int length;
}SeqList;
ELemType GetElem(SeqList L,int i)
{
    
	return L.data[i-1];
}
ElemType*data

分析如下所示：
The number of bytes to look backwards depends on the element type！

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

顺序表的按值查找：

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

代码如下所示：

#define InitSize 10
typedef struct
{
    
	ElemType*data;//动态分配数组的指针,The pointer points to the first element in the sequence table
	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,foatEtc. operators can be used directly'=='进行比较
		{
    
			return i + 1;//数组下标为1的元素值等于e,返回其位序i+1
		}
	}
	return 0;//退出循环,查找失败
}

But this type of structure cannot be used directly’=='来进行比较的,Each variable of the structure must be compared separately.

错误演示：

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("不相等");
}

正确如下所示：

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

按值查找的时间复杂度：

//在顺序表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;
}

Same as delete insert,计算时间复杂度,The focus is on the execution times and problem size of the deepest loop statementn的关系.

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

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

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