2.1 线性表的逻辑结构及基本运算1.线性表简单的定义n个数据元素的的有限序列其特点是除了表头和表尾外，表中的每一个元素有且仅有唯一的前驱和唯一的后继，表头有且只有一个后继，表尾有且只有一个前驱。2.线性表的基本运算length（L) 返回表L的长度，即元素个数。 IsEmpty(L) 如果表L为空表(长度为0)则返回true，否则返回false。 next(L,p) 这是一个函数，函数值为表L中位置p的后继位置。如果p是L中结束元素的位置，则L.Next(p)=L.end。当L中没有位置p或p=L.end时，该运算无定义。 prev(L,p) 这是一个函数，函数值为表L中位置p的前驱位置。当L中没有位置p或p是L中开始元素的位置时，该运算无定义。 get(L,p) 这是一个函数，函数值为L中位置p处的元素。当p=L.end或L中没有位置p时，该运算无定义。 insert(L,x,p) 在表L的位置p处插入元素x，并将原来占据位置p的元素及其后面的元素都向后推移一个位置。例如，设L为a1,a2,…,an，那么在执行insert(L,x,p)后，表L变为a1,a2,…ap-1,x,ap,…,an 。若p为L.end，那么表L变为a1,a2,…,an,x 。若表L中没有位置p，则该运算无定义。 delete(L,p) 从表L中删除位置p处的元素。例如，当L为a1,a2,…,an时，执行delete(L,p)后，L变为a1,a2,…,ap-1,ap+1,…,an 。当L中没有位置p或p=L.end时，该运算无定义。 locate(L,x) 这是一个函数，函数值为元素x在L中的位置。若x在L中重复出现多次，则函数值为x第一次出现的位置。当x不在L中时，函数值为0 MakeEmpty(L) 这是一个将L变为空表的方法。 例1 假设两个线性表LA,LB分别代表两个集合A和B:求A=A U Bproc union(var la:linear_list;lb:linear_list); begin n:=length(la); for i:=1 to length(lb) do x:=get(lb,i); k:=locate(la,x); if k=0 then begin insert(la,n+1,x);n:=n+1 end;end例2 已知线性表la，lb中的数据元素按值非递减有序排列，现要求将la，lb归并为一个新的线性表lc且lc按值非递减。proc merge(la,lb:linear_list;var lc:linear_list);begin i:=1;j:=1;k:=0; while (i<=length(la)) and (j<=length(lb)) do if get(la,i)<=get(lb,j) then begin insert(lc,k+1,get(la,i));k:=k+1;i:=i+1 end else begin insert(lc,k+1,get(lb,j));k:=k+1;j:=j+1 end while i<=length(la) do begin insert(lc,k+1,get(la,i));k:=k+1;i:=i+1; endwhile j<=length(lb) do begin insert(lc,k+1,get(lb,j));k:=k+1;j:=j+1 endend; 2.2 线性表的顺序存储结构线性表的顺序存储即用一组地址连续的存储单元依次存储线性表中的元素。设线性表中每个元素需占用r个存储单元则 loc（ai+1 ）=loc（ai）+r loc（ai）=loc（a1）+（i-1）*r这时可以这样定义线性表类型type sqlist=record data：array[1..maxlen] of datatype; last:0..maxlenend在这种存储方式下，容易实现对表的遍历。要在表的尾部插入一个新元素，也很容易。但是要在表的中间位置插入一个新元素，就必须先将其后面的所有元素都后移一个单元，才能腾出新元素所需的位置。执行删除运算的情形类似。如果被删除的元素不是表中最后一个元素，则必须将它后面的所有元素前移一个位置，以填补由于删除所造成的空缺。这两种运算的时间复杂度均为O(n)n为表的长度。 

又有好的资料上线了

insert(L,x,p) 
 在表L的位置p处插入元素x
为什么下面的例二却是insert(lc,k+1,get(la,i));呢？
有些不对吧？