数据结构第七章学习小结

Dyancsdn 2020-06-28

查找

(1)静态查找表:在查找的同时不对表进行修改操作。

(2)动态查找表:在查找的同时对表做修改操作(如插入、删除)。

平均查找长度(ASL):为了确定记录在查找表中的位置,需要对给定值进行比较的关键字个数的期望值

ASL = ∑ PiCi(从i = 1 到 i = n求和)

其中,Pi为查找表中第i个记录的概率,且∑ P = 1;

   Ci为找到表中其关键字与给定值相等的第i个记录时,和给定值已进行过比较的关键字个数。

线性表的查找:顺序查找,二分查找,分块查找

数表的查找:二叉排序树,AVL树

提高二叉排序树的查找效率,就是尽量让二叉排序树的形状均衡;

平衡树(AVL树)具有如下特征:

(1)左子树和右子树的深度之差的绝对值不超过1;

(2)左子树和右子树也是平衡二叉树;

散列表的查找

1、如何构造散列函数;

1)数字分析法; 2)平方取中法 ;3)折叠法; 4)除留余数法:H(key)=key%p(p为小于表长的最大质数);

2、如何处理冲突;

①开放地址法  (1)线性探测法 ; (2)二次探测法;(3)伪随机探测法;

②链地址法(实际上就是邻接表);

作业与实践

选择题有些平时没有注意到的地方,还有一些概念没有记住的,平时比较模糊的。

①多叉树试用于要求查找深度小的检索。

②哈希表平均查找长度与结点个数无关,其时间复杂度可达O(1)。

③正确率是评估捕获的成果中目标成果所占得比例;召回率,是从关注领域中,召回目标类别的比例。

数据结构第七章学习小结

相关推荐