18、查找实验(一)

一、实验目的

1、 掌握用VC工具上机调试集合结构基于线性表的查找操作。2、 掌握在线性表的顺序存储结构下顺序查找和折半查找算法实

现。

二、实验学时

2学时三、实验类型

验证型四、实验内容

集合的顺序存储结构下顺序查找和折半查找算法的实现。五、实验原理

1、 基于线性表的查找法概述

集合结构是数据对象之间关系松散的一种数据结构，对其进行查找是根据给定的关键字，在特定的列表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在列表中的位置。查找的方法有基于比较查找的方法和计算得方法，其中比较式查找法可分为基于线性表的查找法和基于树的查找法，而计算式查找法也称为HASH（哈希）查找法。基于线性表的查找法是将集合的数据对象组织成为线性表形式进行查找，即用给定的关键字与线性表中各元素的关键字逐个比较，直到成功或失败，线性表的存储结构通常为顺序结构，也可使用链式结构。

查找时可在表的一端设置一个“监视哨”，存放要查找元素的关键字，从表的另一端开始查找，若在“监视哨”找到要查找元素的关键字，返回失败信息，否则返回关键字的位序。基于线性表的查找技术有着非常广泛的应用。

2、基于线性表的查找的基本算法

(1) CreatList(RecordList *l) 建立数据对象集合的线性表结构(2) int SeqSearch(RecordList *l,KeyType k) 有哨兵的顺序查找(3) int BinSrch(RecordList *l,KeyType k) 折半查找

(4) void Display(RecordList *l) 将输入的集合结构输出(5) void shunxu() 顺序查找结果(6) void zheban() 折半查找结果(7) void menu() 程序中使用的菜单(8) void func() 程序的功能函数

3、模块层次图

要求画出二叉树的程序模块层次图。如图所示

图19 基于线性表的查找算法模块层次图

4、关键算法NS图

六、测试数据：

1、顺序查找线性表长度：6

线性表：23,34,6,178,35,查找关键字:178,802、折半查找有序表长度:6

有序表:12,34,44,46,58,90查找关键字:58,900七、实验步骤及要求

用VC语言编程实现线性表的顺序查找和折半查找算法。1. 输入操作序号1选择顺序查找；

2. 输入顺序表长度及相应的顺序表；；3. 输出顺序表；

4. 输入要查找的关键字数据；5. 输出查找结果；

6. 输入操作序号2选择折半查找；

7. 输入有序表长度及相应的有序表；；8. 输出有序表；

9. 输入要查找的关键字数据；10. 输出查找结果；11. 程序运行结束。

八、运行结果

图24 顺序查找算法运行图

图 折半查找算法运行图

九、思考问题

结合实验过程，回答下列问题：

1、 顺序查找算法运行步骤？试写出相应的算法。2、 折半查找算法运行步骤? 试写出相应的算法。3、 基于线性表的查找算法可用于哪些实际问题？十、实验报告要求

1、 调试程序过程中遇到的问题及解决方案；2、 本次实验的结论与体会。