线性表顺序存储插入和删除新节点时平均移动次数

80 阅读 0 评论 53 点赞

我是靠谱客的博主时尚导师，最近开发中收集的这篇文章主要介绍线性表顺序存储插入和删除新节点时平均移动次数，觉得挺不错的，现在分享给大家，希望可以做个参考。

对于长度为n的顺序存储的线性表，当随机插入和删除一个元素时，需平均移动元素的个数是不同的。

1、当对n个元素进行插入操作时，有n+1个位置可以进行插入，如下所示（“.”代表可以插入的位置）。

.1.2.3.4. －－ .n.

在每个位置插入时需要移动的元素个数分别为n,n-1,n-2...,1,0，所以，总共需要移动的元素个数为(1+2+3+4+...+n)=n*(n+1)/2。

故平均需要移动的元素个数为n*(n+1)/2(n+1)=n/2;

2、当对N个元素进行删除操作时，有N个位置可以删除。

1,2,3,4...n

每个位置需要移动的元素个数分别为n-1,n-2,n-3...1,0个。所以平均需要移动的元素个数为(n-1)n/2n=(n-1)/2个。

另可参考： http://hi.baidu.com/cicicolar/item/68dee8c70619696bf7c95d81

转载于:https://blog.51cto.com/3961409/1045218

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

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。