cy21 线性表--顺序表.pptVIP

在线性表的第i个位置前插入一个元素的示意图如下： 12 13 21 24 28 30 42 77 12 13 21 24 25 28 30 42 77 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 9 插入25? for (j=n; j=i; j--) a[j+1]=a[ j ]; a[ i ]=x; n++; // 元素后移一个位置 // 插入x // 表长加1 核心语句 在顺序表L的第i个位置上插入新的元素e 如果i值不正确,则显示相应错误信息(1≤i≤ListLength(L)+1) 如果i值正确, 将顺序表原来第i个元素及以后元素均后移一个位置, 腾出一个空位置插入新元素, 顺序表长度增1 在长度为n的线性表中插入一个元素时所需移动元素的平均次数为: 插入算法的平均时间复杂度为O(n) int ListInsert(SqList *L,int i,ElemType e) { int j; if (i1 || iL-length+1) return 0; i--; /*将顺序表逻辑位序转化为elem下标即物理位序*/ for (j=L-length;ji;j--) L-data[j]=L-data[j-1]; /*将data[i]及后面元素后移一个位置*/ L-data[i]=e; L-length++; /*顺序表长度增1*/ return 1; } a0 … ai-1 ai … an-1 … … 逻辑位序　1 　　　　i i+1 n MaxSize (9) 删除数据元素ListDelete(L,i,e) 删除顺序表L中的第i(1≤i≤ListLength(L))个元素 使长度为n的线性表： (a1，…a i-1，ai，a i+1…，an) 变成长度为n-1的线性表 (a1，…a i-1，a i+1，…，an) 1 2 3 4 5 6 7 8 9 12 13 21 24 25 28 30 42 77 1 2 3 4 5 6 7 8 12 13 21 24 28 30 42 77 删除顺序表中某个指定的元素的示意图如下： for ( j=i+1; j=n; j++ ) a[j-1]=a[j]; n--; // 元素前移一个位置 // 表长减1 核心语句： 删除顺序表L中的第i个元素 如果i值不正确,则显示相应错误信息(1≤i≤ListLength(L)) 如果i值正确,则 将线性表第i个元素以后元素均向前移动一个位置, 顺序表长度减1 在长度为n的线性表中删除一个元素时所需移动元素的平均次数为: 删除算法的平均时间复杂度为O(n) int ListDelete(SqList *L,int i,ElemType e) { int j; if (i1 || iL-length) return 0; i--; /*将顺序表逻辑位序转化为elem下标即物理位序*/ e=L-data[i]; for (j=i;jL-length-1;j++) L-data[j]=L-data[j+1]; /*将data[i]之后的元素后前移一个位置*/ L-length--; /*顺序表长度减1*/ return 1; } a0 … ai-1 ai … an-1 … … 逻辑位序　1 　　　　i i+1 n MaxSize 讨论 设计一个算法,将x插入到一个有序(从小到大排序)的线性表(顺序存储结构即顺序表)的适当位置上,并保持线性表的有序性。 思路： 比较在顺序表L中找到存放x的位置i, 将x插入到L.data[i]中, 将顺序表的长度增1 void Insert(SqList *L,ElemType x) { int i=0,j; while (iL-length L-data[i]x) i++; for (j=L-length-1;j=i;j--) L-data[j+1]=L-data[j]; L-data[i]=x; L-length++; } 查找插入位置 元素