234 data2534571648 查找50i 2534571648 2534571648 i 2534571648 2534571648 计查找失败
25 34 57 16 48 0 1 2 3 4 data 查找 50 i 25 34 57 16 48 i 25 34 57 16 48 i 25 34 57 16 48 i 25 34 57 16 48 i 查找失败
查找成功的平均比较次数 ACN=∑mxcn i=0 若查找概率相等,则 ACN=∑(+1)=(1+2+…+n) 0 1(1+n)*n1+n 米 2 2 查找不成功数据比较n次
查找成功的平均比较次数 若查找概率相等，则 查找不成功 数据比较 n 次 i n i pi c − = 1 0 ACN = 2 1 2 1 (1 ) (1 2 ) 1 ( 1) 1 = 1 0 n n n n n n i n n i + = + = + = + + + = − = ACN
衰项的插入 01234567 data2534|5716480963 插入X50 01234567 data25345715016480963 1 AMN ∑(n-i)= (n+…+1+0 n+1 n+1 1 n(n+1) (n+1)2 2
2 2 ( 1) ( 1) 1 ( 1 0) 1 1 ( ) 1 1 = 0 n n n n n n n i n n i = + + = + + + + − = + = AMN 表项的插入 25 34 57 16 48 09 63 0 1 2 3 4 5 6 7 data 插入 x 50 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 data 50 i
表项的插入 int Insert( SeqList &L, ListData x, int 1)t ∥/在表中第i个位置插入新元素x if(1<Q‖Ii> Llength‖ Llength== Listsize) return o ∥/插入不成功 else i for( int j=Llength;j>1;j=-) Ldatal]=L. datalj-1] Ldata1]=x; Llength++ return 1 ∥/插入成功
◼ 表项的插入 int Insert ( SeqList &L, ListData x, int i ) { //在表中第 i 个位置插入新元素 x if (i < 0 || i > L.length || L.length == ListSize) return 0; //插入不成功 else { for ( int j = L.length; j > i; j-- ) L.data[j] = L.data[j -1]; L.data[i] = x; L.length++; return 1; //插入成功 } }
表项的删除 01234567 data2534575016480963 。。 删除x 01234″567 data 25345750480963 AMN=∑(m-i-1) 1(n-1)nn-1 0 2 2
表项的删除 − = − = − − − = 1 0 2 1 2 1 ( 1) ( 1) 1 = n i n n n n n i n AMN 25 34 57 50 16 48 09 63 0 1 2 3 4 5 6 7 data 16 删除 x 25 34 57 50 48 09 63 0 1 2 3 4 5 6 7 data