(8)--lecture8数据结构数据结构.ppt

*从以上结果可见：哈希表的平均查找长度是?的函数，而不是n的函数。这说明，用哈希表构造查找表时，可以选择一个适当的装填因子?，使得平均查找长度限定在某个范围内。——这是哈希表所特有的特点*假设采用链地址法处理冲突要求1+?/2≤3,即?≤4则表长m≥250假设采用开方定址线性探测再散列要求(1+1/(1-?))/2≤3,即?≤0.8则表长m≥1250例设计哈希表已知n=1000,要求ASL≤3*从哈希表中删除记录时，要作特殊处理，相应地，需要修改查找的算法。五、哈希表的删除操作简单的删除记录操作（置null），会将冲突的链条“断裂”，使其后的关键字查找失败。办法:在删除点填入区别于null的其它标记。*六、哈希表可构造静态查找表在关键字的集合明确已知的前提下，可构造静态哈希查找表，甚至可以找到不发生冲突的哈希函数。即，此时的哈希表的ASL=0,称此类哈希函数为理想（perfect）的哈希函数。对于Java(或C)语言的保留字集都可以设计出理想的哈希函数。*理想哈希函数的经典公式H(word)=(length(word)+g(firstletter(word))+g(lastletter(word)))MODTsize其中g()是给字母分配数值的函数，可由字母出现的次数等因素决定。*本章学习要点

*1.熟练掌握顺序表的查找方法及其平均查找长度的计算方法。3.熟练掌握二叉排序树的构造和查找、插入、删除方法。2.熟练掌握有序表的折半查找方法及其平均查找长度的计算方法。*4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。5.掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。*习题解答实例*算法设计题8-16判断一棵二叉树是否为二叉查找树（二叉排序树）如果按二叉排序树的定义来设计算法，运行效率会比较低。换个角度来思考：二叉查找树本质是一个有序表，通过测试有序表相邻元素间的有序性，可以设计出有效率的算法。具体是，设T为二叉查找树的根指针，pre在遍历过程中始终指向T的前驱，其初值为NULL，由verdict给出判定结果，其初值为TRUE，否定后为FALSE，并终止遍历。*voiddivideBST(BiTreeT,Bitreepre,boolverdict){if(T){ divideBST(T-lchild,pre,verdict);if(!pre||verdictT-datapre-data){//当前结点数据域值大于前驱时pre=T;//把当前指针交给前驱，pre比T迟一步完成中序遍历divideBST(T-rchild,pre,verdict);}elseverdict=FALSE;//当前结点数据域值不比前驱大，给出否定的结论}} *503080209010854035252788TpreTpreTpreTTpreverdict=TRUE;T-datapre-data﹤FALSE；*只有一个办法：预先知道所查关键字在表中的位置，对于频繁使用的查找表，希望ASL=0。即，要求：记录在表中位置和其关键字之间存在一种确定的关系。*若以下标为000~999的顺序表表示之。例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000~xx999(前两位为年份)。则查找过程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。*但是，对于动态查找表而言，因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(ke