1、插入

ListInsert(&L,i,e):插入操作。在表L的第i个位置插入指定元素e

1.1 静态分配顺序表的插入操作

#define MaxSize 10
//定义最大长度
typedef struct{
int data[MaxSize];
int length;
}SqList;
//顺序表的类型定义
void ListInsert(SqList &L,int i,int e){
for(int j=L.length;j>=i;j--){
L.data[j]=L.data[j-1];
//将第i个元素之后的元素从后往前一次后移
L.data[i-1]=e;
//在第i个位置插入e
L,length++;
//当前长度加1
}

为了检查i的范围是否有效和存储空间是否足够，可以用定义返回值为bool形的插入函数如下：

bool ListInsert(SqList &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
}

1.2 动态分配顺序表的插入操作

#define InitSize 10
//定义顺序表的初始长度
typedef struct{
int data*;
//指示动态分配数组的指针
int MaxSize;
//动态分配数组的最大长度
int length;
//当前顺序表的长度
}SqList;
void ListInist(SqList &L){
L.data=(int *)malloc(InitSize*sizeof(int));
L.length=0;
L.MaxSize=InitSize;
}
bool ListInsert(SqList &L,int i,int e){
if(i<1||i>L.length+1)
return False;
if(L.length++>InitSize)
return False;
for(int j=L.length;j>=i;j--){
L.data[j]=L.data[j-1];
}
L.data[i]=e;
L.length++;
}

通过对以上代码的分析可以看出：

1. 静态分配和动态分配实现的顺序表的插入操作几乎是一模一样的。
2. 需要注意的几个语法点包括：
   （1）定义指针data时，有一个强制类型转换的操作
   （2）可以用指针名定义数组，和其他类型名一样，例如动态分配中的定义方式一样

1.3 时间复杂度分析

此处的时间复杂度要关注最深层循环语句的执行次数和文体规模n的关系，其中问题规模为顺序表的长度n，时间复杂度分析如下：

1. 最好情况，新元素插入到表尾，i=n+1,循环0次，最好时间复杂度为O（1）
2. 最坏情况，新元素插入到表头，i=1,循环n次，最坏时间复杂度为O（n）
3. 平均时间复杂度，假设新元素插入到每个位置的概率相同，则插入每个位置的概率都是1/（n+1）则平均循环次数为（n(n+1)/2）/(n+1)=n/2，所以平均时间复杂度为O(n/2）,即O(n）

迷茫的背后是光亮

最后

以上就是朴素热狗为你收集整理的2.2.1顺序表的插入代码实现以及时间复杂度分析1、插入的全部内容，希望文章能够帮你解决2.2.1顺序表的插入代码实现以及时间复杂度分析1、插入所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。