《数据结构》课程设计实验报告---有关查找的操作.doc

《数据结构》课程设计 实验报告 题 目 有关查找的操作 学 院 南湖学院 专 业 信息管理和信息系统 班 级 信息N091 学 号 200945209223 目 录 一、问题描述 2 二、问题分析 4 三、数据结构描述 4 四、算法设计 5 五、详细程序清单 10 六、程序运行结果 24 七、心得体会 26 一、问题描述 1、顺序表的查找问题描述 顺序查找又称线性查找，它是一种最简单、最基本的查找方法。它从顺序表的一端开始，依次将每一个数据元素的关键字值与给定Key进行比较，若某个数据元素的关键字值等于给定值Key，则表明查找成功；若直到所有数据元素都比较完毕，仍找不到关键字值为Key的数据元素，则表明查找失败。 2、有序表的查找问题描述 所谓“折半”也称为“二分”，故二分查找又称为折半查找。作为二分查找对象的数据必须是顺序存储的有序表，通常假定有序表是按关键字值从小到大排列有序，即若关键字值为数值，则按数值有序，若关键字值为字符数据，则按对应的Unicode码有序。二分查找的基本思想是：首先取整个有序表的中间记录的关键字值与给定值相比较，若相等，则查找成功；否则以位于中间位置的数据元素为分界点，将查找表分成左、右两个子表，并判断待查找的关键字值key是在左子表还是在右子表，再在左或右子表中重复上述步骤，直到找待查找的关键字值为key的记录或子表长度为0. 3、哈希表的查找问题描述 在哈希表上进行查找的过程和哈希表构造的过程基本一致。给定要查找的关键字K的值，根据构造哈希表时设定的哈希函数求得哈希地址，若此哈希地址上没有数据元素，则查找不成功；否则比较关键字，若相等，则查找成功；若不相等，则根据构造哈希表时设置的处理冲突的方法找下一个地址，直至某个位置上为空或关键字比较相等为止。 从哈希表的查找过程可见，虽然哈希表是在关键字和存储位置之间直接建立了映像，然而由于冲突的产生，哈希表的查找过程仍然是一个和关键字比较的过程。因此，仍需用平均查找长度来衡量哈希表的查找效率。查找过程中与关键字比较的次数取决于构造哈希表时选择的哈希函数和处理冲突的方法。哈希函数的“好坏”首先影响出现冲突的频率，假设哈希函数是均匀的，即它对同样一组随机的关键字出现冲突的可能性是相同的。因此，哈希表的查找效率主要取决于构造哈希表时处理冲突的方法。 4、二叉树排序数的查找问题描述 在顺序表的3中查找方法中，二分查找具有最高的查找效率，但是由于二分查找要求表中记录按关键字有序，且不能用链表做存储结构，因此当表的插入、删除操作非常频繁时，为维护表的有序性，需要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点。这里讨论的不仅是二叉排序树具有二分查找的效率，同时又便于在查找表中进行记录的增加和删除操作。 5、界面设计模块问题描述 设计一个菜单式界面，让用户可以选择要解决的问题，同时可以退出程序。界面要求简洁明了，大方得体，便于用户的使用，同时，对于用户的错误选择可以进行有效的处理。 二、问题分析 在这次的课程设计中，我主要负责二叉排序树查找的这一部分设计，二叉排序树查找属于动态查找表，它不仅具有二分查找的效率，同时也便于在查找表中进行记录的增加和删除操作。若将查找表组织为一棵二叉排序树，则根据二叉排序树的特点，查找过程的主要步骤归纳如下： （1）若查找树为空，则查找失败。 （2）若查找树非空，则进行如下操作。 1）若给定值k等于根结点的关键字值，则查找成功，结束查找过程，否则转步骤2） 2）若给定值k小于根结点的关键字值，则继续在根结点的左子树上进行，否则转步骤3） 3）若给定值k大于根结点的关键字值，则继续在根结点的右子树上进行。 三、数据结构描述 class BiTreeNode{ private Object data; //结点的数据域 private BiTreeNode lchild,rchild; //左、右孩子树 public BiTreeNode(){ this(null); } //构造一棵左、右孩子域为空的二叉树 public BiTreeNode(Object data){ this(data,null,null); } //构造一棵数据域和左、右孩子域都不为空的二叉树