查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置,需 和给定值进行比较的关键字个数的期望 值 ASL=∑PC i=1 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 查找算法的平均查找长度 (Average Search Length) 为确定记录在查找表中的位置，需 和给定值进行比较的关键字个数的期望 值 = = n i ASL Pi Ci 1
其中:n为表长,P;为查找表中 第个记录的概率,且∑P=1 C为找到该记录时,曾和给定值 比较过的关键字的个数 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 其中: n 为表长，Pi 为查找表中 第i个记录的概率，且 ， Ci为找到该记录时，曾和给定值 比较过的关键字的个数 1 1 = = n i Pi
在等概率情形P=1m,i=1,2,…,n ASL ∑(n-i+1)= ln(n+1)n+1 SuCC 在搜索不成功情 I AsVunsuce =n+1 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 . ( ) ( ) = + = + = − + = n i succ n n n n n i n ASL 1 2 1 2 1 1 1 1 在等概率情形 pi = 1/n, i = 1, 2, , n 在搜索不成功情形，ASLunsucc = n+1
查找成功最少比较次数1 最多比较次数n 平均比较次数(n+1)/2 查找失败:最少比较次数n+1 最多比较次数n+1 平均比较次数n+1 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 查找成功:最少比较次数 1 最多比较次数 n 平均比较次数 (n+1)/2 查找失败:最少比较次数 n+1 最多比较次数 n+1 平均比较次数 n+1
Key Denition in C++ To select existing types as records and keys, a client could use type denition statements such as typedef int Key typedef int Record; a client can design new classes that display appropriate behavior based on the following skeletons: 四川大学计算机(软件)学院
四川大学 计算机(软件)学院 Key Denition in C++ To select existing types as records and keys, a client could use type denition statements such as: typedef int Key; typedef int Record; A client can design new classes that display appropriate behavior based on the following skeletons: