计算机软件及应用查找.pptx

Page12020/2/5学习目标理解“查找表”的结构特点以及各种表示方法的适用性;熟练掌握以顺序表或有序表表示静态查找表时的查找方法;熟练掌握二叉查找树的构造和查找方法;理解二叉平衡树的构造过程;熟练掌握哈希表的构造方法,深刻理解哈希表与其它结构的表的实质性的差别;掌握描述查找过程的判定树的构造方法,以及按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。Page22020/2/5重点和难点重点:理解查找表的结构特点及其各种表示方法的特点和适用场合。知识点顺序表、有序表、索引顺序表二叉查找树、二叉平衡树哈希表Page72020/2/{数据对象:D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字,可唯一标识数据元素。数据关系:D中所有数据元素同属一个集合。基本操作: CreateTable(&ST,n); 操作结果:构造一个含n个数据元素的静态查找表ST。 DestroyTable(&ST); 初始条件:静态查找表ST存在; 操作结果:销毁查找表ST。Page82020/2/5Search(ST,kval);初始条件:静态查找表ST存在,kval为和查找表中元素的关键字类型相同的给定值;操作结果:若ST中存在其关键字等于kval的数据元素,则函数值为该元素的值或在表中的位置,否则为“空”。 Traverse(ST,visit());初始条件:静态查找表ST存在,visit是对元素操作的应用函数;操作结果:按某种次序对ST的每个元素调用函数visit()一次且仅一次,一旦visit()失败,则操作失败。}ADTStaticSearchTablePage92020/2/。查找过程从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较;若某个记录的关键字和给定值比较相等,则查找成功,找到所查记录;反之,若直至第一个记录,其关键字和给定值比较都不相等,则表明表中没有所查记录,查找不成功。Page102020/2/:typedefstruct{ElemType*elem;//数据元素存储空间基址,建表//时按实际长度分配,0号单元留空intlength;//表中元素个数}SSTable;i找6464监视哨iiii比较次数=