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