顺序表的插入和删除操作

• C语言线性表的插入和删除操作
• • 一、插入操作
  • • 插入操作的时间复杂度分析：
  • 二、删除操作
  • • 删除操作的时间复杂度分析：

#include
#define MaxSize 10
typedef struct{
	int data[MaxSize];     //用静态(整数int/抽象，泛型ElemType)数组存放数据元素
	int length;					//顺序表当前长度
}SqList;					//顺序表的类型定义

//基本操作——初始化一个顺序表
void InitList(SqList &L){
	for(int i=0;i		//如果不将所有数据元素设置为默认初始值就会出现脏数据
		L.data[i]=0;			//将所有数据元素设置为默认初始值
	}
	L.length=5;				//顺序表初始长度为5(不能超过MaxSize)
}



//顺序表元素的插入操作(L-线性表，i-要插入的位置，e-要插入的元素)
bool ListInsert(SqList &L,int i,int e){
	//为了保证一个合法的i，这里需要加判断
	//线性表是连续存储空间，所以需要判断i的合法性
	if(i<1||i>L.length+1){
		return false;
	}
	//顺序表已经存满，不能再存了
	if(L.length>=MaxSize){
		return false;
	}

	//将插入位置之后的所有元素向后移一位  
	//按数组下标是从0开始的，所以length-1就是他的最后一个元素
	for(int j = L.length;j>=i;j--){
		L.data[j] = L.data[j-1];
	}
	L.data[i-1] = e;		//在i位置处放入e
	L.length++;			//更新线性表的长度
	return true;
}

int main(){
	SqList L;			//声明一个顺序表
	InitList(L);		//初始化顺序表
	if(ListInsert(L,4,10)==true){
		printf("插入元素之后的线性表长度为%dn:",L.length);
		printf("插入元素之后线性表的元素为:n");
		for(int i =0;i
			printf("data[%d] = %dn",i,L.data[i]);
		}
		
	}else{
		printf("线性表已经插满或检查要插入的位置是否合法n");
	}
	return 0;
}

综上，插入操作的平均时间复杂度是O(n)。

#include
#define MaxSize 10
typedef struct{
	int data[MaxSize];     //用静态(整数int/抽象，泛型ElemType)数组存放数据元素
	int length;					//顺序表当前长度
}SqList;					//顺序表的类型定义

//基本操作——初始化一个顺序表
void InitList(SqList &L){
	for(int i=0;i		//如果不将所有数据元素设置为默认初始值就会出现脏数据
		L.data[i]=0;			//将所有数据元素设置为默认初始值
	}
	L.length=5;				//顺序表初始长度为0
}



//顺序表元素的插入操作(L-线性表，i-要插入的位置，e-要插入的元素)
bool ListInsert(SqList &L,int i,int e){
	//为了保证一个合法的i，这里需要加判断
	//线性表是连续存储空间，所以需要判断i的合法性
	if(i<1||i>L.length+1){
		return false;
	}
	//顺序表已经存满，不能再存了
	if(L.length>=MaxSize){
		return false;
	}

	//将插入位置之后的所有元素向后移一位  
	//按数组下标是从0开始的，所以length-1就是他的最后一个元素
	for(int j = L.length;j>=i;j--){
		L.data[j] = L.data[j-1];
	}
	L.data[i-1] = e;		//在i位置处放入e
	L.length++;			//更新线性表的长度
	return true;
}
//加上引用符号&说明传入的e和本函数中的元素e是同一个引用地址，若是不加，那么他们两个就只是值相同，但是引用地址不同的元素
bool ListDelete(SqList &L,int i,int &e){
	//先判断删除位置是否合法
	if(i<1||i>L.length+1){
		return false;
	}
	e = L.data[i-1];	//将要删除的元素赋给e
	//将i之后的元素依次向前移一位
	for(int j = i;j
		L.data[j-1] = L.data[j];
	}
	L.length--;		//更新线性表的长度
	return true;
}


int main(){
	SqList L;			//声明一个顺序表
	InitList(L);		//初始化顺序表

	//插入一些元素...
	int e = -1;		//用变量e把删除的元素带回来
	if(ListDelete(L,3,e)){
		printf("删除成功，删除的元素为%d",e);
	}else{
		printf("删除失败，检查你要删除的位置是否合法n");
	}
	return 0;
}

综上，删除操作的平均时间复杂度也是O(n)。