插入操作:
#define MaxSize 10 //定义最大长度
typedef struct {
int data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
//基本操作-初始化顺序表
void InitList(SqList &L);
//基本操作-插入元素
bool ListInsert(SqList &L, int i, int e);
int main(void) {
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
ListInsert(L,1,1);
ListInsert(L,2,2);
ListInsert(L,3,3);
return 0;
}
void InitList(SqList &L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0; //将所有数据元素设置为默认初始值
} //顺序表初始长度为0
L.length = 0;
}
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--) { //将第i个元素及之后的元素后移
L.data[j] = L.data[j-1];
}
L.data[i-1] = e; //在位置i处放入e
L.length++; //长度加1
return true;
}
时间复杂度
最好情况:新元素插入到表尾,不需要移动元素,其中i = n + 1时循环0次,最好时间复杂度为 O(1)
最坏情况:新元素插入到表头,需要将原有的n个元素全部都向后移动,其中i = 1,循环n次,最坏时间复杂度O(n)
平均情况:假设新元素插入任何一个位置的概率相同,即i = 1, 2,3, ..., length+1的概率都是 p = 1 / (n + 1),i = 1, 循环n次;i = 2时,循环n-1次;i=3,循环n-2次...i = n + 1时循环0次
删除操作:
#define MaxSize 10 //定义最大长度
typedef struct {
int data[MaxSize]; //用静态的“数组”存放数据元素
int length; //顺序表的当前长度
}SqList; //顺序表的类型定义
//基本操作-初始化顺序表
void InitList(SqList &L);
//基本操作-插入元素
bool ListInsert(SqList &L, int i, int e);
bool ListDelete(SqList &L, )
int main(void) {
SqList L; //声明一个顺序表
InitList(L); //初始化顺序表
ListInsert(L,1,1);
ListInsert(L,2,2);
ListInsert(L,3,3);
return 0;
}
void InitList(SqList &L) {
for (int i = 0; i < MaxSize; i++) {
L.data[i] = 0; //将所有数据元素设置为默认初始值
} //顺序表初始长度为0
L.length = 0;
}
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--) { //将第i个元素及之后的元素后移
L.data[j] = L.data[j-1];
}
L.data[i-1] = e; //在位置i处放入e
L.length++; //长度加1
return true;
}
时间复杂度
最好情况:删除表尾元素,不需要移动元素,其中i = n 时循环0次,最好时间复杂度为 O(1)
最坏情况:删除表头元素,需要将后续的n-1个元素全部都向前移动i = 1,循环n-1次,最坏时间复杂度O(n)
平均情况:假设删除任何一个位置元素的概率相同,即i = 1, 2,3, ..., length+1的概率都是 p = 1 / n,其中i = 1, 循环n-1次,i=2时,循环n-2次;i = 3,循环n-3次, ..., i = n 时,循环0次