VB公共基础 第1讲 - 算法与数据结构 - 图文(6)

顺序表的插入和删除分析插入算法的分析?假设线性表中含有n个数据元素，在进行插入操作时，若假定在n+1个位置上插入元素的可能性均等，则平均移动元素的个数为：1n?1nEis?pi(n?i?1)??n?1i?12删除算法的分析?在进行删除操作时，若假定删除每个元素的可能性均等，则平均移动元素的个数为：分析结论1nn?1Edl??pi(n?i)?ni?12?顺序存储结构表示的线性表，在做插入或删除操作时，平均需要移动大约一半的数据元素。当线性表的数据元素量较大，并且经常要对其做插入或删除操作时，这一点需要值得考虑261.4 栈和队列271.4.1 栈及其基本运算1．栈的定义?栈（stack）：一种只允许在表的一端进行插入或删除操作的特殊的线性表?栈顶(top) ：允许进行插入与删除操作的一端?栈底(bottom)：不允许插入与删除操作的另一端?先进后出（FILO）或后进先出(LIFO)的线性表入栈出栈栈顶 topan…a2栈底 bottoma1281.4.1 栈及其基本运算2．栈的顺序存储及其运算?top=0：栈空?栈的基本运算入栈运算?退栈运算?读栈顶元素?V(1..10)1098765432bottomtop1(a)空栈bottomtop10987654321FEDCBAbottomtopV(1..10)10987654321YXFEDCBAbottomtopV(1..10)10987654321XFEDCBAV(1..10)top=m：栈满(b)有6个元素的栈(c)插入X和Y后的栈(d)退出Y元素后的栈291.4.2 队列及其基本运算1．队列的定义?限定只能在表的一端进行插入和在另一端进行删除操作的线性表?队尾(rear)：允许插入的一端?队头(front)：允许删除的另一端?先进先出（FIFO）表或后进后出（LILO）线性表退队ABCDEF入队队头front队尾rear?基本操作??入队运算：往队列的队尾插入一个元素，队尾指针rear的变化退队运算：从队列的排头删除一个元素，队头指针front的变化30