8章查找表
第章查找表 8.1静态查找表 8.2动态查找树表 8.3哈希表
学习是要 熟练掌握顺序表和有序表的查找方法。 熟练掌握二叉排序树的构造和查找方法。 掌握二叉平衡树的维护平衡方法。 理解B-树的特点以及它们的建树过程 熟练掌握哈希表的构造方法,深刻理解哈希表 与其它结构的表的实质性的差别。 掌握描述查找过程的判定树的构造方法,以及 按定义计算各种查找方法在等概率情况下查找 成功时的平均查找长度
何谓童找裹? 查找表是由同一类型的数据元素(或记录)构成的 集合。 由于“集合”中的数据元素之间存在着松散的关系,因 此查找表是一种应用灵便的结构。 对查找表经常进行的操作: 1)查询某个“特定的”数据元素是否在查找表中; 2)检索某个“特定的”数据元素的各种属性; 3)在查找表中插入一个数据元素; 4)从查找表中删去某个数据元素
童感分提 静态查找表仅作查询和检索操作的查找表 动态查找表在查询之后,还需要将“查询”结果为 “不在查找表中”的数据元素插入到查找 表中;或者,从查找表中删除其“查询” 结果为“在查找表中”的数据元素 关键字是数据元素(或记录)中某个数据项的值, 用以标识(识别)一个数据元素(或记录)。 若此关键字识别唯一的一个记录,则称之谓“主关键 著署此关键字能识别若干记录,则称之谓“次关键字
查找根据给定的某个值,在查找表中确定一个其关键 字等于给定值的数据元素或(记录) 若查找表中存在这样一个记录,则称查找成功查找结果: 给出整个记录的信息或指示该记录在查找表中的位置 否则称查找不成功查找结果:给出空记录或空指针。 如何进行查找?查找的方法取决于查找表的结构。 由于查找表中的数据元素之间不存在明显的组织规律 因此不便于查找。为了提高查找的效率,需要在查找表 中的元素之间人为地附加某种确定的关系,换句话说, 用另外一种结构来表示查找表
查找表 Search Table:是一种以集合为逻辑结构 以查找为核心运算的数据结构。 静态查找表:只对查找表进行查询某个特定的数 据元素或某个特定数据元素的各种属性的操作。 如:查询成绩表中是否有某学生或该学生某门课 程的成绩。 动态查找表:对查找表进行插入或删除某个数据 元素的操作。如:修改某个学生某门课程的成绩 衡量查找算法的标准: (1)平均查找长度; (②)算法所需要的存储量和算法的复杂性等
平均宣找长度 定义:为确定记录在表中的位置,需和给定值进 行比较的关键字的个数的期望值叫查找算法在查 找成功时的平均查找长度。 对含有n个记录的表,ASL= 2PC 其中:为查找表中第计个元素的概率∑P=1 c为找到表中第i个元素所需比较次数 物理意义:假设每一元素被查找的概率相同,则查找每 一元素所需的比较次数之总和再取平均,即为ASL 显然,ASL值越小,时间效率越高
基操作 Create(&sT, n) 操作结果:构造一个含n个数据元素的静态查找表ST Destroy(&st); 初始条件:静态查找表ST存在; 操作结果:销毁表ST。 Search(sT, kval; 初始条件:静态查找表ST存在,kwal为和查找表中元素的关键字 类型相同的给定值; 操作结果:若ST中存在其关键字等于kval的数据元素,则函数 值为该元素的值或在表中的位置,否则为“空” Traverse(ST, VisitO); 初始条件:静态查找表ST存在,Ⅴsi是对元素操作的应用函数; 操作结果:按某种次序对ST的每个元素调用函数vsi0次且仅 一次,一旦Ⅴisit失败,则操作失败
8。|静恋宣找表 、顺序查找( Linear search,又称线性查线) 顺序查找:用逐一比较的办法顺序查找关键字。 冷对顺序结构如何线性查找? 心对单链表结构如何线性查找? 对非线性树结构如何顺序查找?借助各种遍历操作! 顺序表的机内存储结构: typedef struct t Elem Type *elem;∥表基址,0号单元留空 int length;表长 I SSTable, typedef struct i key Type key;∥关键字域 ∥/其它属性域 F Elem Type
