教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 l、初始化操作InitList Sq Status InitList Sq(SqList &L) ∥构造一个空的线性表L L.elem =(ElemType *)malloc(LIST_INIT_SIZE*sizeof(Elem Type)); if(L.elem=NULL)exit(OVERFLOW);∥存储分配失败 L.length=0; ∥空表长度为0 L.listsize LIST INIT SIZE; ∥初始存储容量 return OK: }/∥InitList Sq 2、插入操作ListInsert_Sq 1)算法设计 参数：顺序表&L、插入位置i、插入元素e 插入分析：第i个位置放e,则原来第i~L.length个数据元素必须先后移，以腾出第i 个位置； 注意后移的顺序为：从最后一个元素开始，逐个往后移 for (j=L.length;j>=i;j--)L.elem[i]L.elem[j-1]; ∥后移 L.clem[i-1]=e,/第i个元素存放在L.elem[i-l]中，数组下标的起始为0 L.length L.length+1; 合法的位置：i:l.L.length+1 上溢及处理：上溢发生的条件：L.length≥L.listsize,此时要先申请一个有一定增量的 空间：申请成功则原空间的元素复制到新空间，修改L.listsiz心，再进行插 入工作：否则报错退出。 算法 Status ListInsert_Sq(SqList &L,int i,ElemType e){ ∥位置合法性的判断 if(i<1 i>L.length+1)return ERROR; ∥上溢时增加空间的分配 if(L.length >=L.listsize) newbase =(ElemType *)realloc(L.elem, (L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(newbase =NULL exit(OVERFLOW); L.elem newbase; L.listsize +LISTINCREMENT; ∥插入元素 for (j=L.length;j>=i;j--)L.elem[j]=L.elem[j-1]; L.elem[i-1]=e; L.length++; return OK; 2)算法分析—一时间 频次最高的操作：移动元素。另外，上溢时的空间的再分配与复制(realloc操作)的时 间复杂度与realloc的算法以及当前的表长相关，至少为On):但它仅在插入元素会引起上 溢时才执行。 若线性表的长度为n,则： 最好情况：插入位置i为+1，此时无须移动元素，时间复杂度为O(1): 最坏情况：插入位置i为1，此时须移动n个元素，时间复杂度为O(n: 文档编号 完成时间 完成人张昱 修改时间2003-9-10 第5页
程序设计——数据结构 第二章 线性表 基本概念、线性表的应用 第 5 页 第 5 页 文档编号 完 成 人 张 昱 完成时间 完成时间 修改时间 修改时间 2003-9-10 1、初始化操作 InitList_Sq Status InitList_Sq( SqList &L) { // 构造一个空的线性表 L L.elem = (ElemType *)malloc(LIST_INIT_SIZE*sizeof(ElemType)); if ( L.elem == NULL ) exit(OVERFLOW); // 存储分配失败 L.length = 0; // 空表长度为 0 L.listsize = LIST_INIT_SIZE; // 初始存储容量 return OK; } // InitList_Sq 2、插入操作 ListInsert_Sq 1) 算法设计 参数：顺序表&L、插入位置 i、插入元素 e 插入分析：第 i 个位置放 e，则原来第 i~L.length 个数据元素必须先后移，以腾出第 i 个位置; 注意后移的顺序为：从最后一个元素开始，逐个往后移 for ( j = L.length; j >= i; j--) L.elem[j] = L.elem[j-1]; // 后移 L.elem[i -1] = e; //第 i 个元素存放在 L.elem[i-1]中，数组下标的起始为 0 L.length = L.length+1; 合法的位置：i:1..L.length+1 上溢及处理：上溢发生的条件：L.length≥L.listsize，此时要先申请一个有一定增量的 空间：申请成功则原空间的元素复制到新空间，修改 L.listsize，再进行插 入工作；否则报错退出。 算法 Status ListInsert_Sq( SqList &L, int i, ElemType e) { // 位置合法性的判断 if ( i<1 || i>L.length +1 ) return ERROR; // 上溢时增加空间的分配 if( L.length >= L.listsize){ newbase = (ElemType *) realloc(L.elem, (L.listsize+ LISTINCREMENT)*sizeof(ElemType)); if ( newbase == NULL ) exit(OVERFLOW); L.elem = newbase; L.listsize += LISTINCREMENT; } // 插入元素 for ( j = L.length; j >= i; j--) L.elem[j] = L.elem[j-1]; L.elem[i-1] = e; L.length++; return OK; } 2) 算法分析——时间 频次最高的操作：移动元素。另外，上溢时的空间的再分配与复制(realloc 操作)的时 间复杂度与 realloc 的算法以及当前的表长相关，至少为 O(n)；但它仅在插入元素会引起上 溢时才执行。 若线性表的长度为 n，则： ➢ 最好情况：插入位置 i 为 n+1，此时无须移动元素，时间复杂度为 O(1); ➢ 最坏情况：插入位置 i 为 1，此时须移动 n 个元素，时间复杂度为 O(n);
教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 平均情况：假设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）即使表的容量可以扩充（针对顺序表的方案二），由于其空间再分配和复制的开销，也 不允许它频繁地使用；