Question

顺序表中插入和删除需要的平均移动次数，怎么算啊？请求大神们回答。求详解

Answer 1

我们假设顺序表长度为n，由于顺序表的结点之间逻辑关系为邻接关系，所以当我们要将一个结点插入时，这个插入位置的后面的结点每一个都要移动以给新插入的结点让出位置，同时顺序表的长度加一，所以顺序表插入一个结点，平均需要移动n/2个结点，由于移动了n/2个结点我们插入一个结点的移动次数就是n/2。当我们删除一个结点时，由于顺序表的结点之间为邻接关系所以在删除结点之后的每一个结点都要往前移动一位，整个顺序表的长度减一，所以删除一个结点时我们需要移动（n-1）/2个结点，此时我们平均需要移动（n-1）/2次。
首答送给你，这个问题我也是刚学不久正好今天正在思考，可能会有不正确的地方，如果出错望谅解。

Answer 2

首先说插入：假如顺序表有n个元素，则插入位置应该为n+1个（表尾可以插入），如果插在第一个位置，那么第一个元素到最后一个元素都需要往后移动一个位置，把第一个位置空出来，总共移动n次，如果插在第二个位置，则除了第一个位置的元素不需要移动外，剩下n-1个元素都要往后移，以此类推，如果插在表尾，则不需要移动任何元素。把所有移动次数加起来(n+n-1+ .... + 1 +0 )/(n+1) = n/2,
删除类似，这里不再赘述

Answer 3

一、考试大纲的性质

数据结构是我校计算机科学与技术（高起本、专升本）的学位考试科目之一。为帮助考生明确考试复习范围和有关要求，特制定本考试大纲。
二、考试范围和内容
第一章 概论
1、基本概念：理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、数据结构的抽象层次。
2、算法渐进时间复杂度分析
第二章 线性表
1、顺序表：顺序表的定义、搜索、插入与删除
重点：➢​插入与删除算法、平均移动次数的计算
2、单链表：单链表定义、相应操作的实现。
重点：➢​单链表的搜索算法与插入、删除算法
3、循环链表：单链表与循环链表的异同
4、双向链表：带表头结点的双向循环链表
重点：​➢​双向循环链表的定义
​➢​双向链表的插入与删除算法
5、顺序实现与链接实现的比较
6、字符串：字符串的定义及其操作的实现
​重点：​➢​串的操作的定义与实现
➢​字符串的模式匹配

追答

求采纳

追问

很感谢你的回答，但无法采纳，不好意思，因为问题回答方向不对。再次感谢

Answer 4

插入时：
假设在第i个新元素前插入一个新元素的概率喂1/n+1，即在表任何位置插入元素的概率是相等的，可算平均移动次数 T=1/(n+1)乘以}{i从1到n+1求积分(n-i+1)}=n/2;
删除时：
方法同上，最后可得结果喂n-1/2