当前位置:   article > 正文

【考研数据结构知识点详解及整理——C语言描述】第二章 线性表顺序存储结构上的基本操作——顺序表的插入操作

【考研数据结构知识点详解及整理——C语言描述】第二章 线性表顺序存储结构上的基本操作——顺序表的插入操作

25计算机考研,数据结构知识点整理(内容借鉴了王道408+数据结构教材),还会不断完善所整理的内容,后续的内容也会不断更新(可以关注),若有错误和不足欢迎各位朋友指出!

目录

一.插入操作

1.算法思想

2.算法描述

3.算法分析


一.插入操作

顺序表的插入运算是指在表的第i(1≤i≤n+1)个位置插入一个新元素e,使长度为n的顺序表(e_{1},…,e_{i-1}e_{i},…,e_{n})变成长度为n+1的顺序表(e_{1},…,e_{i-1},e,e_{i},…,e_{n})(其中n为L的表长度)。 

1.算法思想

用顺序表作为线性表的存储结构时,由于结点的物理顺微视频 2-2序必须和结点的逻辑顺序保持一致,因此必须将原表中位置n,n-1,…,i上顺序表插入的结点,依次后移到位置n+1,n,…,i+1上,空出第i个位置,然后在该位置插入新结点e。当i=n+1时,是指在顺序表的末尾插人结点,所以无须移动结点,直接将e插人表的末尾即可。

2.算法描述

  1. #define OK 1
  2. #define ERROR O
  3. int InsList( SeqList * L,int i,ElemType e)
  4. /*在顺序表L中第i个数据元素之前插入一个元素e,i的合法取值范围是1≤i≤L->last+2*/
  5. {
  6. int k;
  7. if((i<1)||(i>L->last+2)) /*首先判断插入位置是否合法*/
  8. {
  9. printf("插人位置i值不合法");
  10. return(ERROR);
  11. }
  12. if(L->last>=MAXSIZE-1)
  13. {
  14. printf("表已满,无法插人");
  15. return(ERROR);
  16. }
  17. for(k=L->last;k>=i-1;k--) /*为插入元素而移动位置,i-1为最后一个元素移动的下标*/
  18. L->elem[k+1]=L->elem[k]; //插入位置及之后的元素后移动
  19. L->elem[i-1]=e; //在c语言数组中,第i个元素的下标为i-1,将新元素e放入第i个元素
  20. L->last++; //表长增1
  21. return(OK);
  22. }

3.算法分析

最好情况:当在表尾(i=L->last+2)插人元素时,因为循环的终值大于初值,此时不需要移动元素,可直接在表尾插人e,元素后移语句将不执行,时间复杂度为O(1)。

最坏情况:在表头(i=1)插入元素时,移动元素的语句L->elem[k+1]=L->elem[k]需执行n次,即将表中已存在的n个元素依次后移一个位置才能将e插入,时间复杂度为O(n)。因此,语句L->elem[k+1]=L->elem[k]的语句执行频度与插入位置i有关。

平均情况:E_{ins}为在长度为n的表中插入一个元素所需移动元素的平均次数,假设P_{i}为在第i个元素之前插入元素的概率,并假设在任何位置上插人的概率相等,P_{i }=1/(n+1),i=1,2,n+1,则有

因此,顺序表的插入算法的平均时间复杂度为O(n) 

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小蓝xlanll/article/detail/674071
推荐阅读
相关标签
  

闽ICP备14008679号