教黎 第二章线性表 程序设计—数据结构 基本概念、线性表的应用 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);