中国矿业大学计算机学院实验报告 "课程名称 数据结构 实验名称__搜索 " "实验报告要求：1.实验目的 2.实验内容 3.实验步骤 " "4.运行结果 5.流程图 6.实验体会 " " 一、实验目的 " "1 " "熟练掌握顺序搜索、折半搜索和索引搜索等基本搜索算法，熟悉这些算法" "适合在何种存储结构下实现 " "2 熟练掌握二叉排序树的特性、建立方法以及动态搜索算法 " "3 熟练掌握散列表的特点及构造方法 " "二、实验要求 " "1 实验之前认真准备，编写好源程序。 " "2 " "实验中认真调试程序，对运行结果进行分析，注意程序的正确性和健壮性" "的验证。 " "3 不断积累程序的调试方法。 " "三、实验内容 " "基本题: " "1、实现基于有序顺序表的折半搜索 " "源程序： " "#include <iostream> " "#define MaxSize 100 " "using namespace std; " "// 排序连续顺序文件的折半查找方法 " "int Binary_Search(int key[],int h,int k) " "{ " "int low=1,high=h,mid=0; " "while(low<=high) " "{ " "mid=(low+high)/2; " "if(key[mid]==k) " "{return mid;} " "if (k>key[mid]) " "{low=mid+1;} " "else " "{high=mid-1;} " "} " "return 0; " "} " " " "int main() " "{ " "cout<<"用整形数组来实现折半查找："<<endl; " "int Arr[MaxSize]={0}; " "int n=0,m; " "cout<<"请输入你想查找的数组的长度："<<endl; " "cin>>n; " "cout<<"请输入一组数字，按照从小到大的顺序排列："<<endl; " "for(int i=0;i<n;++i) " "{ " "cin>>Arr[i]; " "} " "cout<<"请输入你想搜索的整数的值："<<endl; " "cin>>m; " "cout<<"该整数的位置为："<<Binary_Search(Arr,n,m)+1<<endl; " "return 0; " "} " "运行结果： " " " " " "2、设单链表的结点是按关键字的值从小到大排列的，试写出对此表的搜 " "索程序并调试。 " "源程序： " "#include <iostream> " "#include <conio.h> " "#include <list> " "using namespace std; " "void disp(list<int> List) " "{ " "list<int>::iterator p; " "for(p=List.begin();p!=List.end();p++) " "cout<<*p<<" "; " "}//disp " "int Search(list<int> List,int key) " "{ " "list<int>::iterator q; " "int i=1; " "for(q=List.begin();q!=List.end();q++) " "{ " "if(key==*q) " "{return i;} " "i++; " "} " "return 0; " "}//Search " " " "void main() " "{ " "list<int>L; " "int m[100]; " "int i=0; " "cout<<"请输入您想建立的链表的各个节点的关键字，以0为结束！"<<end" "l; " "do{ " "cin>>m[i++]; " "}while(m[i-1]!=0); " "for(int j=0;j<i-1;j++) " "{ " "L.push_back(m[j]); " "cout<<"插入成功！"<<endl; " "}L.sort(); " "cout<<"单链表节点顺序为："<<endl; " "disp(L); " "int n,x; " "do{ " "cout<<"1.查找 2.退出"; " "cin>>n; " "if(n==1) " "{ " "cout<<"请输入要查找的数："; " "cin>>x; " "if(Search(L,x)) " "{ " "cout<<"查找成功！您要查找的节点为单链表的第"<<Search(L,x)<<"个节" "点"<<endl; " "} " "els
实验报告的目的是让学生深入理解和应用数据结构中的搜索算法，包括顺序搜索、折半搜索和索引搜索等。在实验过程中，学生需要编写源程序，并通过实际运行和调试来验证算法的正确性和效率。
折半搜索（Binary Search）是一种在有序数组中查找特定元素的搜索算法。它通过不断将搜索范围减半来提高查找速度。实验中的`Binary_Search`函数实现了这个过程。在给定的有序数组中，程序初始化低指针`low`为1，高指针`high`为数组长度`h`，中间位置`mid`由`low`和`high`的平均值决定。如果找到目标值，返回其索引；如果目标值小于中间值，则将`high`更新为`mid - 1`，否则将`low`更新为`mid + 1`。重复此过程，直到找到目标值或搜索范围为空。在主函数中，用户输入数组长度和元素，然后输入要查找的数值，程序调用`Binary_Search`函数并输出结果。
对于单链表的搜索，实验要求实现一个按关键字从小到大排序的单链表的搜索程序。链表的搜索通常比数组慢，因为它需要遍历每个节点。实验提供的`Search`函数遍历链表，当找到目标值时返回其在链表中的位置。在`main`函数中，用户输入一系列节点关键字构建链表，链表使用C++的`std::list`容器表示，然后调用`Search`函数查找指定值。
实验还涵盖了二叉排序树（Binary Sort Tree）和散列表（Hash Table）的特性，虽然没有提供具体的代码实现。二叉排序树是一种特殊的二叉树，左子树上的所有节点值小于根节点，右子树上的所有节点值大于根节点，适用于动态搜索。散列表则通过哈希函数将键映射到数组的索引，提供快速查找，但可能需要处理哈希冲突。
实验过程中，学生不仅需要编写和运行程序，还要对结果进行分析，确保程序的正确性和健壮性。这有助于提升学生的编程技巧和问题解决能力，同时积累程序调试经验。
总结实验体会，学生应能认识到不同搜索算法在不同数据结构中的适用性，如有序数组适合折半搜索，链表适合顺序搜索，而二叉排序树和散列表则提供高效的动态查找。此外，通过调试程序，学生会增强对错误定位和修复的理解，这对于成为一个合格的程序员至关重要。
