清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 线性表顺序存储结构下的主要运算 (1)在线性表的指定位置处加入一个新的元素(即线性表的插入); (2)在线性表中删除指定的元素(即线性表的删除); (3)在线性表中查找某个(或某些)特定的元素(即线性表的查找); (4)对线性表中的元素进行整序(即线性表的排序); (5)按要求将一个线性表分解成多个线性表(即线性表的分解); (6)按要求将多个线性表合并成一个线性表(即线性表的合并) (7)复制一个线性表(即线性表的复制) (8)逆转一个线性表(即线性表的逆转)等
2.1 线性表的基本概念 线性表顺序存储结构下的主要运算： (1)在线性表的指定位置处加入一个新的元素（即线性表的插入）； (2)在线性表中删除指定的元素（即线性表的删除）； (3)在线性表中查找某个（或某些）特定的元素（即线性表的查找）； (4)对线性表中的元素进行整序（即线性表的排序）； (5)按要求将一个线性表分解成多个线性表（即线性表的分解）； (6)按要求将多个线性表合并成一个线性表（即线性表的合并）； (7)复制一个线性表（即线性表的复制）； (8)逆转一个线性表（即线性表的逆转）等
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 2.1.3线性表在顺序存储下的插入运算 v(1:10) v(1:10 v(1:10 29 29 29 团→2 18 67 87 56 18 18 3456789 63 56 56 35 23456789 63 23456789 63 24 35 31 24 24 47 31 31 47 14 10 47 (a)长度为8的线性表0b)插入元素87后(c)又插入元素14后
2.1 线性表的基本概念 2.1.3 线性表在顺序存储下的插入运算
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 在长度为n的线性表 的第i个元素a1之前插入一个新元素b后为 ai,a2…,a1,a+1;…,2n,a2+1) 其中 1≤i≤ a 人1i+1≤j≤n+1
2.1 线性表的基本概念
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 线性表在顺序存储下的插入算法 输入:线性表的存储空间V(1:m);线性表的长度n(n≤m);插入 的位置i(i表示在第i个元素之前插入);插入的新元素b。 输出:插入后的线性表存储空间V(1:m)及线性表的长度n。 PROCEDURE INSL (V, m, n, i, b) 1. IF (n=m) then OVERFLOW; RETURNI 2. IF(i>n)Then i=n+1 3. IF(i<1 ThEN i=1 4. FoR j=n to i BY -1 Do V(j+1)=v(i) 5.V(i)=b 6.n=n+1 7. RETURN
2.1 线性表的基本概念 线性表在顺序存储下的插入算法 输入：线性表的存储空间V(1：m)；线性表的长度n（n≤m）；插入 的位置i（i表示在第i个元素之前插入）；插入的新元素b。 输出：插入后的线性表存储空间V(1：m)及线性表的长度n。 PROCEDURE INSL(V，m，n，i，b) 1. IF (n＝m) THEN { OVERFLOW；RETURN} 2. IF (i＞n) THEN i＝n＋1 3. IF (i＜1) THEN i＝1 4. FOR j＝n TO i BY －1 DO V(j＋1)＝V(j) 5. V(i)＝b 6. n＝n＋1 7. RETURN
清华大学出版社 TSINGHUA UNIVERSITY PRESS 2.1线性表的基本概念 void insl(v, m, n, i, b) ET V, b: int m, *n, i I if (*n==m) I printf( overflow \n); return; if(i>-1)i=n+1; if(i<1)i=1; for (j=n; j<=i; j--vljl-vLj-1 v[i-1]=b; 米n=*n+1; return:
2.1 线性表的基本概念 void insl(v，m，n，i，b) ET v[]，b； int m，*n，i； { if (*n＝＝m) { printf("overflow \n")； return； } if (i＞*n－1) i＝*n＋1； if (i＜1) i＝1； for (j＝*n；j＜＝i；j――) v[j]＝v[j－1]； v[i－1]＝b； *n＝ *n＋1； return； }