在顺序表中,线性表的有些运算很容易实现。例如取第 i个数据元素 Getnode(L,e)和求表长 ListLength(L) 以下主要讨论插入和删除两种运算。 1插入 线性表的插入运算是指:在表的第i(1≤i≤n+1)个 位置上,插入新数据元素e,使长度为n的线性表: 152 ■■■ 3(i-13i·"cn 变成长度为n+1的线性表: (a1,a2,…a1,e,a1,…,an)
线性表的插入运算是指：在表的第i (1 i n+1)个 位置上，插入新数据元素e，使长度为n的线性表： （a1 ,a2 , …, ai-1 , ai , …, an ） 变成长度为n+1的线性表： （a1 ,a2 , …, ai-1 , e , ai , …, an ） 在顺序表中，线性表的有些运算很容易实现。例如取第 i个数据元素GetNode (L,i,e)和求表长ListLength(L)。 以下主要讨论插入和删除两种运算。 ⒈插入
分析: 线性表采用顺序存储结构时,由于数据元素 的物理顺序必须和数据元素的逻辑顺序保持 一致,因些我们必须将表中位置n,n-1,i上 的元素依次后移到位置n+1,n,,i+1上,腾 出第i个位置,然后在该位置上插入新数据元 素e,仅当插入位置i=n+1时,才无需移动数 据元素,直接将e插入表尾
线性表采用顺序存储结构时，由于数据元素 的物理顺序必须和数据元素的逻辑顺序保持 一致，因此我们必须将表中位置n ,n-1 ,…,i上 的元素依次后移到位置n+1 ,n ,…,i+1上，腾 出第i个位置，然后在该位置上插入新数据元 素e，仅当插入位置i=n+1时，才无需移动数 据元素，直接将e插入表尾。 分析：
bool InsertNode (sqList &L, int e, int i) ∥插入新元素e使其成为表L的第个元素; ∥若正常完成插入返回true,否则返回 false。 I int j; bool r= false;∥预置插入标志 if(i<1‖|> L Size+1)∥非法插入位置 cout < ERROR: invalid i !! else if(L. isFull()∥表满(溢谥出 cout < error: overflow !n else∥正常插入
bool InsertNode (sqList &L, int e, int i) // 插入新元素e使其成为表L的第i个元素； // 若正常完成插入返回true，否则返回false。 { int j ; bool r = false; // 预置插入标志 if( i<1 || i>L.Size+1) // 非法插入位置 cout << " ERROR:invalid i !!\n"; else if(L.isFull()) // 表满 (溢出) cout << " ERROR: overflow !!\n"; else // 正常插入
tfor(j=L.Size;j>≡i;j-)∥数据元素依次后移 L elem]L elem[j-11 L.elem[]=e;∥插入新数据元素 L_.Size+t;∥表长增1 r=true;∥设置插入正常标志 return r 注意元素后移的方向,必须从表中最后一个元素开 始后移,直至将第个元素后移为止
{ for( j=L.Size;j>=i; j -- ) // 数据元素依次后移 L.elem[j]=L.elem[j-1]; L.elem[j]=e; // 插入新数据元素 L.Size++; // 表长增1 r = true; // 设置插入正常标志 } return r; } 注意元素后移的方向，必须从表中最后一个元素开 始后移，直至将第i个元素后移为止
算法的时间复杂度分析: 问题的规模是表的长度L.Size,将其记为n,显然 该算法的时间主要花费在for循环中的元素后移语句 上,该语句的循环执行次数即移动元素的次数是n +1。由此可见,所需移动元素的次数不仅依赖于表 的长度,而且还与插入位置有关。 由于插入可能在表中任何位置上进行,因此需分析 算法的平均性能
问题的规模是表的长度L.Size，将其记为n ，显然 该算法的时间主要花费在for循环中的元素后移语句 上，该语句的循环执行次数(即移动元素的次数)是ni+1。由此可见，所需移动元素的次数不仅依赖于表 的长度，而且还与插入位置i有关。 由于插入可能在表中任何位置上进行，因此需分析 算法的平均性能。 算法的时间复杂度分析：