2.2.1顺序表的插入代码实现以及时间复杂度分析1、插入

101 阅读 0 评论 67 点赞

我是靠谱客的博主朴素热狗，这篇文章主要介绍2.2.1顺序表的插入代码实现以及时间复杂度分析1、插入，现在分享给大家，希望可以做个参考。

文章目录

1、插入
- 1.1 静态分配顺序表的插入操作
- 1.2 动态分配顺序表的插入操作
- 1.3 时间复杂度分析

1、插入

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

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

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#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形的插入函数如下：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 动态分配顺序表的插入操作

复制代码

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
#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）定义指针data时，有一个强制类型转换的操作
（2）可以用指针名定义数组，和其他类型名一样，例如动态分配中的定义方式一样

1.3 时间复杂度分析

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

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

迷茫的背后是光亮