数据结构查找A.ppt

数据结构课程的内容 第8章 查找 (4)评估查找方法优劣的标准 8.2 静态查找 1.顺序查找（又称线性查找） 1、顺序查找（ Linear search，又称线性查找 ） （2）算法的改进： 讨论① 查不到怎么办？ 二、折半查找（又称二分查找或对分查找） 讨论① 若关键字不在表中，怎样得知和停止？ 平均每个数据的查找时间还要除以n，所以： 折半查找效率分析法2（参见严教材P220）： 三、静态树表的查找（自学） 四、分块查找（索引顺序查找） 查找步骤分两步进行： 8.3 动态查找表 1、二叉排序树的定义回顾 2、二叉排序树的插入与删除 讨论1：二叉排序树的插入和查找操作 3.二叉排序树的查找分析 最好情况：即：与折半查找中的判定树相同（形态比较均衡） 针对动态查找表的查找算法主要有： 一、二叉排序树（BST） 二、平衡二叉树（AVL树） 三、 B- 、 B+树 ----或是一棵空树；或者是具有如下性质的非空二叉树： （1）左子树的所有结点均小于根的值； （2）右子树的所有结点均大于根的值； （3）它的左右子树也分别为二叉排序树。递归定义 （4）其中序遍历序列为一个递增序列 一. 二叉排序树有哪些信誉好的足球投注网站 将数据元素构造成二叉排序树的优点： ① 查找过程与顺序结构有序表中的折半查找相似，查找效率高； ② 如果查找不成功，能够方便地将被查元素插入到二叉树的叶子结点上，而且插入或删除时只需修改指针而不需移动元素。 注：若数据元素的输入顺序不同，则得到的二叉排序树形态也不同！ ——这种既查找又插入的过程称为动态查找。 二叉排序树既有类似于折半查找的特性，又采用了链表存储，它是动态查找表的一种适宜表示。 45 24 53 12 90 如果待查找的关键字序列输入顺序为： （24，53， 45，45，12，24，90） 24 53 45 12 90 查找成功，返回 查找成功，返回 则生成二叉排序树的过程为： 例：输入待查找的关键字序列=（45，24，53，45，12，24，90） 则生成的二叉排序树形态不同： 查找成功返回 查找成功返回 bstnode *BSTSEARCH(bstnode *t, keytype k) { bstnode *p; p=t; while (p) { if (p-key==k) return p; if (p-keyk) p=p-lchild; else p=p-rchild; } return NULL; } 1. 二叉排序树的查找 45 24 53 12 28 90 二叉排序树的查找插入算法如何实现？ 2. 二叉排序树的结点插入 45 24 53 12 28 90 a.若原树为空，返回以新插入结点为树根的树。 b. 否则，找到要插入的父结点。 c. 将新结点插入到确定位置 47 4745,向右子树有哪些信誉好的足球投注网站 4753,向左子树有哪些信誉好的足球投注网站 53左子树为空，47应该插入到此处, 47 1) 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。 比较的关键字次数＝此结点的层次数; 最多的比较次数＝树的深度（或高度），即 ?log2 n?+1 X？ 2) 一棵二叉排序树的平均查找长度为： 其中： ni 是每层结点个数； ci 是结点所在层次数； m 为树深。 * 数据结构 计算机与信息学院 刘勇 课前思考题： 猜价格游戏：已知主持人手中的物品价格为1至31元之间的整数，猜中者可得该奖品。 1. 如果你猜错时主持人只告诉你所猜价格错了让你重新猜，平均要几次才能猜对? 2. 如果你猜错时主持人告诉你所猜价格是高了还是低了再让你重新猜，最少要几次才可保证对任意一个价格都能猜对？ 如何应用数据结构知识求解实际问题？ 根据实际问题数据之间的关系确定其数据结构。 例如图的n各城市架设最经济通信线路问题，数据之间存在多对多的关系，因此对应数据结构为带权图。 根据问题需求基于该数据结构基本操作定义相应算法。 实际问题是求最经济通信线路，实际上就是求带权图的极小连通子图，也就是求图的最小生成树。因此应该采用图的最小生成树算法进行求解。 根据数据特征选择存储结构，并选择该数据存储结构 的对应算法进行求解。 如果是稀疏图，采用邻接表存储，调用kruskal算法 如果是稠密图，采用邻接矩阵存储，调用Prim算法 一个乡镇有6个村且各村之间是连通的，要在其中一个村建立急救中心，希望到各村去急救的平均时间最短，应该把急救中心建在哪个村？－最短路径和最小问题！如果考虑各村