數据结构课程的内容课件.pptVIP

数据结构课程的内容;8.1 基本概念 8.2 静态查找表 8.3 动态查找表 8.4 哈希表;8.1 基本概念;（2）对查找表常用的操作有哪些？ 查询某个“特定的”数据元素是否在表中； 查询某个“特定的”数据元素的各种属性； 在查找表中插入一元素； 从查找表中删除一元素。 ;（4）如何评估查找方法的优劣？;针对静态查找表的查找算法主要有： ;一、顺序查找（ Linear search，又称线性查找 ）;（2）算法的实现：;——返回特殊标志，例如返回空记录或空指针。前例中设立了“哨兵”，就是将关键字送入末地址ST.elem[0].key使之结束并返回 i=0。 讨论② 查找效率怎样计算？ ——用平均查找长度ASL衡量。;二、折半查找（又称二分查找或对分查找）;② 运算步骤： (1) low =1,high =11 ,mid =6 ，待查范围是 [1,11]； (2) 若 ST.elem[mid].key key，说明 key?[ mid+1,high] ， 则令：low =mid+1;重算 mid＝ ?(low+high)/2?；. (3) 若 ST.elem[mid].key key，说明key?[low ,mid-1]， 则令：high =mid–1;重算 mid ； (4)若 ST.elem[ mid ].key = key，说明查找成功，元素序号=mid; 结束条件： （1）查找成功 ： ST.elem[mid].key = key （2）查找不成功 ： high≤low （意即区间长度小于0）;讨论① 若关键字不在表中，怎样得知何时停止？;平均每个数据的查找时间还要除以n，所以：;查找过程可用二叉树描述：每个记录用一个结点表示；结点中值为该记录在表中位置，这个描述查找过程的二叉树称为判定树。n个元素的表的折半查找的判定树是唯一的，即：判定树由表中元素个数决定。 找到有序表中任一记录的过程就是：走了一条从根结点到与该记录相应的结点的路径。 比较的关键字个数：为该结点在判定树上的层次数。 查找成功时比较的关键字个数最多不超过树的深度 d : d = ? log2 n ? + 1 若所有结点的空指针域设置为一个指向一个方形结点的指针，称方形结点为判定树的外部结点；对应的，圆形结点为内部结点。 查找不成功的过程 就是走了一条从根结点到外部结点的路径。 做习题新建 Microsoft Word 文档.doc ;三、静态树表的查找;四、分块查找（索引顺序查找）;查找步骤分两步进???：;习题  要进行线性查找，则线性表 A ；要进行二分查找，则线性表 B ；要进行散列查找，则线性表 C 。顺序存储的表格，其中有90000个元素，已按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。当用顺序查找法查找时，平均比较次数约为 D ，最大比较次数为 E 。 供选择的答案：A~C：① 必须以顺序方式存储 ② 必须以链表方式存储 ③ 必须以散列方式存储 ④ 既可以以顺序方式，也可以以链表方式存储 ⑤ 必须以顺序方式存储且数据元素已按值递增或递减的次序排好 ⑥ 必须以链表方式存储且数据元素已按值递增或递减的次序排好D，E： ① 25000 ② 30000 ③ 45000 ④ 90000 答案： A= ④ B= ⑤ C= ③ D＝ ③ E＝ ④ ;特点：;一、二叉排序树的定义;二、二叉排序树的插入与删除;45;二叉排序树的查找插入算法如何实现？;对于二叉排序树，删除树上一个结点相当于删除有序序列中的一个记录，删除后仍需保持二叉排序树的特性。 （对链表进行删除操作是很方便的）;*p有两棵子树时，如何进行删除操作？;F;1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度），即 ?log2 n?+1 2) 一棵二叉排序树的平均查找长度为： ;最好情况：即：与折半查找中的判定树相同（形态比较均衡）