教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 平均情况：假设p:为在第ⅰ个元素之前插入一个元素的概率，则： 入时移动次数的期望值：E。三∑P(n-1+1） 等概率时，即p= n+11 2-+0- ∴.Tn)=On) 3、删除操作ListDelete_Sq 1)算法设计 参数：顺序表&L、删除位置i 删除分析：去掉第i个元素，则原来第i+l~L.length个数据元素须前移，以覆盖第i个 位置； 前移的顺序为for(j=ij<L.length;j++)L.elem[-jl]=L.elem[]j L.length =L.length-1 合法的位置：il.L.length 下溢：L.length≤0一一隐含在i的条件中 算法 Status ListDelete Sq(SqList &L,int i) ∥位置合法性的判断 if (i<1 i>L.length)return ERROR; ∥删除 for (j=i;j<L.length;j++)L.elem[j-1]=L.elem[jl]; L.length--; return OK: 2)算法分析——时间 频次最高的操作：移动元素 若线性表的长度为n,则： 最好情况：删除位置i为，此时无须移动元素，时间复杂度为O(1); 最坏情况：删除位置i为1，此时须前移n-1个元素，时间复杂度为O(n少： 平均情况：假设4：为删除第ⅰ个元素的概率，则： 删除时移动次数的期望值：E=29(n-) 等展率时，即=，5之u-)=” n ∴.T(n)=On) 2.3线性表的链式表示和实现 2.3.1线性链表 1、顺序映像的弱点 1)空间利用率不高（预先按最大空间分配）： 2)表的容量不可扩充（针对顺序表的方案一）： 3)即使表的容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销，也 不允许它频繁地使用： 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第6页程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 6 页 第 6 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 ➢ 平均情况：假设 pi 为在第 i 个元素之前插入一个元素的概率，则： 插入时移动次数的期望值：  + = = − + 1 1 ( 1) n i is i E p n i 等概率时，即 1 1 + = n pi ， 2 ( 1) 1 1 1 1 n n i n E n i is − + = + =  + = ∴ T(n) = O(n) 3、删除操作 ListDelete_Sq 1) 算法设计 参数：顺序表&L、删除位置 i 删除分析：去掉第 i 个元素，则原来第 i+1~L.length 个数据元素须前移，以覆盖第 i 个 位置; 前移的顺序为 for ( j = i; j < L.length ; j++) L.elem[j-1] = L.elem[j]; L.length = L.length-1 合法的位置：i:1..L.length 下溢：L.length≤0 —— 隐含在 i 的条件中 算法 Status ListDelete_Sq( SqList &L, int i) { // 位置合法性的判断 if ( i<1 || i>L.length ) return ERROR; // 删除 for ( j = i; j < L.length ; j++) L.elem[j-1] = L.elem[j]; L.length--; return OK; } 2) 算法分析——时间 频次最高的操作：移动元素 若线性表的长度为 n，则： ➢ 最好情况：删除位置 i 为 n，此时无须移动元素，时间复杂度为 O(1); ➢ 最坏情况：删除位置 i 为 1，此时须前移 n-1 个元素，时间复杂度为 O(n); ➢ 平均情况：假设 qi 为删除第 i 个元素的概率，则： 删除时移动次数的期望值： = = − n i de i E q n i 1 ( ) 等概率时，即 n qi 1 = ， 2 1 ( ) 1 1 − =  − = = n n i n E n i de ∴ T(n) = O(n) 2.3 线性表的链式表示和实现 2.3.1 线性链表 1、顺序映像的弱点 1）空间利用率不高（预先按最大空间分配）； 2）表的容量不可扩充（针对顺序表的方案一）； 3）即使表的容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销，也 不允许它频繁地使用；