North China Electric Power University 在线性表L的第个位置上插入新元素x的算法 Procedure Insert(Var L: Linear list x: Elem Type) Begin if(i<1)or(i>n+1) then error(插入的位置非法’) else I For j: =n DownTo i Do L[j+1: Lll: °-X; n:=n+1; End: 在一个长度为n的线性表中插入一元素时需移动元素的平均次数为 +1 Em=2P*(m+1)=n2(当P3=1/(n+1)j=1,2,…』,n+1) 算法的时间复杂性为0(n)
在线性表L的第i个位置上插入新元素x的算法 Procedure Insert(Var L:Linear_list ; x:ElemType); Begin if (i<1) or (i>n+1) then Error(‘插入的位置非法’) else [ For j:=n DownTo i Do L[j+1]:=L[j]; L[i]:=x; n:=n+1; ] End; 在一个长度为n的线性表中插入一元素时需移动元素的平均次数为 Ein = ΣPj *(n-j+1)=n/2 (当Pj =1/(n+1) j=1,2,…n,n+1) 1 n+1 算法的时间复杂性为O(n) North China Electric Power University
North China Electric Power University 2)删除线性表L的第个元素 删除前:元素1114202528314378 序号1234/5/6/7/8 删除 插入后:元素11142028314378 序号1234567 主要操作:1将第计1到n个元素依次前移一个位置 3将线性表的表长由n修改为n-1
North China Electric Power University 2)删除线性表L的第i个元素 删除前：元素 序号 1 2 3 4 5 6 7 8 删除 插入后：元素 序号 1 2 3 4 5 6 7 主要操作：1.将第i+1到n个元素依次前移一个位置 3.将线性表的表长由n修改为n-1 11 14 20 25 28 31 43 78 11 14 20 28 31 43 78
North China Electric Power University 删除线性表L的第个元素的算法 Procedure Delete(var L Linear list i: Integer); Begin if(i<1)or(i>n) then error(没有这个元素’) else Forj:=i计+ I TonD0 Lj-1: Lll; n:=n-1 End: 在一个长度为n的线性表中删除一元素时需移动元素的平均次数为 Es=2B1*(n-j)=(n1)2(当P=1/nj=1,2,…n) 算法的时间复杂性为0(n)
North China Electric Power University 删除线性表L的第i个元素的算法 Procedure Delete(Var L:Linear_list ; i:Integer); Begin if (i<1) or (i>n) then Error(‘没有这个元素’) else [ For j:=i+1 To n Do L[j-1]:=L[j]; n:=n-1; ] End; 在一个长度为n的线性表中删除一元素时需移动元素的平均次数为 Ede = ΣPj *(n-j)=(n-1)/2 (当Pj =1/n j=1,2,…n) 算法的时间复杂性为O(n)
North China Electric Power University 3)定位运算:求x在线性表L中的最小序号 x|28 元素1114202528314378 序号12345678 Function Locate L: Linear list; x: ElemType): Integer; {在L中査找第一个值和x相等的元素,若存在,返回该元素L中 的序号,否则返回0} Begin while(isn) and (Lik< >x)Do i:=i+1 if (i<n) then Return(i) else return(o); ●End
3)定位运算：求x在线性表L中的最小序号 元素 序号 1 2 3 4 5 6 7 8 11 14 20 25 28 31 43 78 x 28 Function Locate(L:Linear_list ; x:ElemType):Integer; {在L中查找第一个值和x相等的元素，若存在，返回该元素L中 的序号，否则返回0} Begin i:=1; while (i≤n) and (L[i]< >x) Do i:=i+1; if (i<n) then Return(i) else Return(0); End; North China Electric Power University