#include<stdio.h>
#include<stdlib.h>
#define maxSize 10
// listInsert(&L,i,e) 在第i个位置插入指定元素e
typedef struct {
int data[maxSize];
int length;
}SqList;
void initList(SqList &L) {
for(int i=0;i<L.length; i++) {
L.data[i]=i;
}
L.length = 0;
}
/**
* 思路:第i个元素及其之后的元素都向后移,i-1后面就空出来一个空地址
* 那么新加元素就变成了第i个,原i就变成了i+1个
* 在空出来的这个地址,即第i的位置,赋值data[i]=e
*
*
* 怎么后移:data[i] = data[i-1] 那么i-1的位置不就空出来了吗
* 注意: i是位序,位序从1开始,下标从0开始,位序和下标是两东西
* data[下标]获取当前位置的数据元素,
* 也就是说,第i=1个位置的元素是data[0],...第i=L.length个位置的元素是data[L.length-1]
*/
bool listInsert(SqList &L, int i, int e) {
/* i是位序,从1开始,
* 显然:<1或者超过顺序表长度就是不合法的,
* 因为第1个位置前面没有位置,
* 第L.length个位置后面插入一个叫做在最后一个元素后面插入,即在第L.length+1个位置
* 如果直接跳L.length+1个位置,就是不合法
* 还有就是,插入新元素之前,要先判断下顺序表的连续存储空间是否还有空位置,如果已经满了,那肯定没法插入
*/
// 为了代码的健壮性,要加些判断
if(i<1 || i>L.length+1)
return false;
if(L.length > maxSize)
return false;
/**
* 假设i=6,就是要在第6个位置插入新元素e
* 那就要将原i=6位置的元素及其之后的以此向后移,为了拿到原i=6及其之后的元素,此时就要遍历
* 但是,i=5及其之前的元素是不应该移动的,所以在遍历的时候,j<i=6的元素就不要操作,只操作j>=i的
*/
for(int j=L.length;j>=i;j--) {
L.data[j] = L.data[j-1];
}
// for循环执行完后,此时原第i个及其之后的元素已经后移了,目前第i个位置已经空出来了,插入新元素e
L.data[i-1] = e; // 第i=6个位置,实际上它的数组下标为5,就是L.data[i-1],将数据项赋值为e
L.length++; // 长度加1
return true;
}
int main() {
SqList L;
initList(L);
for(int k=0;k<maxSize;k++){
listInsert(L,k,k);
}
printf("%d\t数据长度\n",L.length);
for(int h=0;h<L.length;h++){
printf("%d\t数组元素依次输出\n",L.data[h]);
}
return 0;
}
分析一下当前算法的时间复杂度,注意:顺序表的元素移动,是从最后一个元素依次移动的
1、新元素插入到表尾,i=n+1,就不用移动元素,不移动就不要走for循环,for循环0次,时间复杂度为O(1)
2、新元素插入到表头,i=1,就要移动所有元素,有n个元素移动n个,for循环n次,时间复杂度为O(n)
3、随机插入除表头和表尾的任意一个位置,它们的概率都相同,即i=1、2、3...length+1的概率都是P=1/(n+1)
i=1,循环n次,i=2,循环n-1次,...i=n+1,循环0次
平均循环次数=循环总次数*概率= (1+2+3+...+n+1)*1/(n+1)=(n+1)n/2 * 1/(n+1)=n/2
时间复杂度为O(n)
文章来源地址https://www.toymoban.com/news/detail-726396.html
文章来源:https://www.toymoban.com/news/detail-726396.html
到了这里,关于【数据结构】静态分配的顺序表插入元素的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!