其物理存储关系也要发生相应的变化因此,除非i=n+1, 否则必须将第i、i+1 n这些数据元素向后移动空 出第个位置并将新的数据元素存入.设有线性表 an)存储于数组(向量)vmkm>n+1) 中,则插入过程如下图所示 插入前ia 移动i 插入后1 +1 +1 +2 i+2 i+1 n+1 n+1
其物理存储关系也要发生相应的变化. 因此, 除非i = n+1, 否则必须将第i ﹑ i +1 ﹑… ﹑ n这些数据元素向后移动,空 出第i个位置并将新的数据元素存入. 设有线性表 ( , , , , , ) a1 a2 ai a n 存储于数组(向量) vm(m n +1) 中, 则插入过程如下图所示: n i i a a a a a 1 2 1 + 1 1 2 1 0 − + m n i i 插入前 移动 n i i a a a a a 1 2 1 + 1 1 2 1 2 1 0 − + + + m n i i i 插入后 1 1 2 1 2 1 0 − + + + m n i i i n i i a a a x a a 1 2 1 +
插入算法的框图请见教材P14,下面给出C函数 struct ist /结构类型 { int V MAXNE;/*整型数组,MAXN为预估数组容量* int n; /表长 typedef struct list LIST;/定义LNT为上述结构类型* int sqinsert(p,i, x) LIST *P; /指向结构类型的指针 int l, x; /i为插入位置,x为被插入元素* f int j if(p>n<=0) { printf(“表长错误Ⅷ”); return(-1)
插入算法的框图请见教材P.14, 下面给出C函数. struct list /* 结构类型*/ { int v[MAXN]; /* 整型数组, MAXN为预估数组容量*/ int n; /* 表长 */ }; typedef struct list LIST; /* 定义LIST为上述结构类型*/ int sqinsert(p,i,x) LIST *p; /* 指向结构类型的指针 */ int i,x; /* i为插入位置, x为被插入元素*/ { int j; if (p->n<=0) { printf(“表长错误\n ”); return(-1); }
if(i<l‖i>p->n+1) { printf(“插入位置i不恰当n”); return(1); for(i→p->n;j>=i:j-) p>v+1l=p->vjl;/移动 p->vFx; 将x存入第个位置 p->n++; /表长加1*/ printf(“插入成功n”); return(O); 对于顺序表的插入算法,主要操作是元素的移动,即 for循环语句中的循环体,它执行的后移元素次数为n-i+1 由此可见它不仅依赖于线性表的长度n,还与元素插入位置 i关.当i=1时,全部元素都被移动,移动n次;当i=n+1时
if (i<1 || i>p->n+1) { printf(“插入位置i不恰当\n ”）; return(-1); } for(j=p->n;j>=i;j--) p->v[j+1]=p->v[j]; /* 移动 */ p->v[i]=x; /* 将x存入第i个位置*/ p->n++; /* 表长加1 */ printf(“插入成功\n ”）; return(0); } 对于顺序表的插入算法, 主要操作是元素的移动, 即 for循环语句中的循环体, 它执行的后移元素次数为n- i +1 由此可见它不仅依赖于线性表的长度n, 还与元素插入位置 i有关. 当i =1时, 全部元素都被移动, 移动n次; 当i = n +1时
不需移动元素,可见算法的时间复杂度为O(n) 由于元素移动的次数直接影响算法的执行时间,下面 讨论平均移动次数 设P为在第个元素之前插入一个元素的概率,且设在 线性表的任何位置上的插入机会相等,即等概,则平均移动 次数(期望值为: En=∑n(m-i+1)=-∑(n-i+1) n+l i 顺序表的删除 删除运算是指将表中第i(1≤i≤m)个元素删除,使线 性表的长度由m变为n-1,且其逻辑结构和顺序存储结构也 发生相应的变化,除非i=n时可直接将第个元素删除,否 则需移动第i+1、i+2 n这些元素以填充由删除运算 而造成的间隔
不需移动元素, 可见算法的时间复杂度为O(n). 由于元素移动的次数直接影响算法的执行时间, 下面 讨论平均移动次数. 设 i p 为在第i个元素之前插入一个元素的概率, 且设在 线性表的任何位置上的插入机会相等, 即等概, 则平均移动 次数(期望值)为: 2 ( 1) 1 1 ( 1) 1 1 1 1 n n i n E p n i n i n i i n i − + = + = − + = + = + = 二﹑ 顺序表的删除 删除运算是指将表中第 i(1 i n) 个元素删除, 使线 性表的长度由n变为n-1, 且其逻辑结构和顺序存储结构也 发生相应的变化, 除非i = n时可直接将第i个元素删除, 否 则需移动第i +1﹑ i +2﹑… ﹑ n这些元素以填充由删除运算 而造成的间隔
删除过程如下图所示: 删除前ia 删除后i 移动 i+1 n 设有线性表(a12a2…a12…an)存储于数组vmkm≥m) 中,要求删除线性表中第f个元素并将其存入y中,描述上述 要求的算法框图请见教材P.16
删除过程如下图所示: 设有线性表 n i i a a a a a 1 2 1 + 1 1 2 1 0 − + m n i i 删除前 删除后 1 1 2 1 0 − + m n i i n i a a a a 1 2 1 + 移动 1 1 2 1 0 − − m n i n i a a a a 1 2 1 + ( , , , , , ) a1 a2 ai a n 存储于数组 vm(m n) 中, 要求删除线性表中第i个元素并将其存入y中, 描述上述 要求的算法框图请见教材P.16