数据结构查找.docx

实验六查找【实验项目】：完成二叉树的基本运算，从而了解其基本特征，基本运算算法一、实验目的1. 掌握查找的含义。2. 掌握基本查找操作的算法与实现。3. 掌握二叉排序树查找的算法与实现。4. 掌握Hash表查找的算法与实现。二、实验要求（本次实验要求上交）【题目】--验证型实验1. 建立一个线性表，对表中数据元素存放的先后次序没有任何要求。输入待查数据元素的关键字进行查找。（为了简化算法，数据元素只含一个整型量关键字字段，数据元素的其余数据部分忽略不考虑。）顺序查找的基本思想及程序实现（参考代码见文件夹6-1）对于给定的关键字k，从表的一端开始，逐个进行数据元素的关键字和给定值的比较，若当前扫描到的结点关键字与k相等则查找成功；若扫描结束后，仍未找到关键字等于k的节点，则查找失败。建立一个顺序表，数据元素从下标为1的单元开始放入，下标为0的单元起监视哨作用，将待查的关键字存入下标为0的单元，顺序表从后向前查找，若直到下标为0时才找到关键字则说明查找失败；若不到下标为0时就找到关键字，则查找成功。2. 查找表的存储结构为有序表，即表中记录按关键字大小排序存放。输入待查数据元素的关键字进行查找。（为了简化算法，记录只含一个整型量关键字字段，记录的其余数据部分略不考虑。程序要求对整型量关键字数据的输入按从小到大排序输入。）折半查找的基本思想及程序实现：（参考代码见文件夹6-1）设查找表中的元素存放在数组r中，数据元素的下标范围为[low,high]，要查找的关键字值为key，中间元素的下标为mid=(low+high)／2 (向下取整)，令key与r[mid]的关键字比较：若key=r[mid].key，查找成功，下标为m的记录即为所求，返回mid。若keyr[mid].key，所要找的记录只能在左半部分记录中，再对左半部分使用折半查找法继续进行查找，有哪些信誉好的足球投注网站区间缩小了一半。若keyr[mid].key，所要找的记录只能在右半部分记录中，再对右半部分使用折半查找法继续进行查找，有哪些信誉好的足球投注网站区间缩小了一半。重复上述过程，直到找到查找表中某一个数据元素的关键字的值等于给定的值key说明查找成功；或者出现low的值大于high的情况，说明查找不成功。建立一个有序表，数据元素从下标为1的单元开始放入。实现查找算法时，首先将low赋值为l，high等于最后一个数据元素的下标，然后将给定的关键字的值与查找区间[low，high]中间的数据元素的关键字比较，实现查找过程。3.编程实现二叉排序树的创建、查找、插入、输出等算法。二叉排序树基本思想及程序实现（参考代码见文件夹6-1）二叉排序树就是指将原来已有的数据根据大小构成一棵二叉树，二叉树中的所有结点数据满足一定的大小关系，所有的左子树中的结点均比根结点小，所有的右子树的结点均比根结点大。二叉排序树查找是指按照二叉排序树中结点的关系进行查找，查找关键字首先同根结点进行比较，如果相等则查找成功；如果比根结点小，则在左子树中查找；如果比根结点大，则在右子树中进行查找。这种查找方法可以快速缩小查找范围，大大减少查找关键字的比较次数，从而提高查找效率。算法的关键过程实际上就是二叉排序树的创建和查找两个步骤。首先分析二叉排序树的创建运算，由于二叉排序树中的所有结点都有一个大小关系，因此，每个结点必须在二叉排序树中寻找其合适的位置。创建二叉排序树的第一步就是创建一个根结点，第二步就是将其他结点不断插入到二叉排序树中的合适位置。二叉排序树进行结点插入时，首先要为被插入结点寻找合适的插入位置。这个过程实际上就是一个关键值不断的比较的过程。第一次比较是与二叉排序树的根结点比较，如果比根结点的关键值小，则插入到他的左子树中；如果比根结点的关键值大，则插入到它的右子树中。在子树中重复这样过程，直到找到合适的位置为止。二叉排序树的查找运算实际上同二叉排序树的创建运算是一致的。区别在于，创建过程中要为二叉排序树中没有位置的关键字建立结点，而查找过程中，只是在二叉排序树中查找是否等于查找关键字值的结点存在，不管有还是没有，它都不会创建一个新的结点。【题目2】（注意：该程序将作为平时成绩的一部分计入期末总分，请认真完成。另外：请独立完成，在批改过程中若发现是抄袭的，相同版本第二份及其以上做不合格处理）编程实现一个开放式的高校本科招生最低录取分数线的查询系统，供师生和家长查询。高校自愿放入该校的信息，可能随时有高校加入。要求实现的查询功能有：①查询等于用户给定分数的高校；②查询大于(或小于)用户给定分数的高校；③查询最低录取分数线在用户给定的分数段中的高校。该实验主要的功能是查找，查找表为高校最低录取分数信息的集合。根据题意可知，该查找表中的元素个数可能随时增减，所以它是一个动态查找表，可采用树状结构保存。为了提高查询速度，可建立二叉排序树