【数据结构】第7章查找实验11：查找

浅浅的花香味﹌ 2022-12-02 10:46 188阅读 0赞

【折半查找、[平衡二叉树的调整][Link 1]、[B树][B]和[B+树][B 1]、[哈希表][Link 2]】

--------------------

题目：折半查找

## 一、实验目的和要求 ##

（1）熟悉C++的上机环境，进一步掌握C++的结构特点；  
（2）掌握查找。

## 二、实验环境 ##

Windows10, CodeBlocks.

## 三、实验内容及实施 ##

【实验内容】  
实验11：折半查找  
要求：给定一组数序列，输入key, 用折半查找算法查找，并输出查找结果  
【源程序】

#include <bits/stdc++.h>
    using namespace std;
    
    typedef int KeyType;
    typedef int InfoType;
    const int N = 100000;
    typedef struct 
    {
        
        KeyType key;
        InfoType otherinfo;
    }ElemType;
    typedef struct 
    {
        
        ElemType R[N];
        int length;
    }SSTable;
    
    int Search_Bin(SSTable ST, KeyType key)
    {
        
        int low = 1, high = ST.length;
        while(low <= high)
        {
        
            int mid = (low + high) / 2;
            if(key == ST.R[mid].key)
                return mid;
            else if(key < ST.R[mid].key)
                high = mid - 1;
            else
                low = mid + 1; 
        }
        return 0;
    }
    
    int main()
    {
        
        int key;
        SSTable ST;
        cout<<"请输入数据个数：";
        cin>>ST.length;
        cout<<"请依次输入这"<<ST.length<<"个数据："<<'\n';
        for(int i = 1; i <= ST.length; i++)
            cin>>ST.R[i].key;
        while(1)
        {
        
            cout<<"请输入要查找的key值(输入0退出本程序)：";
            cin>>key;
            if(key == 0)
            {
        
                cout<<"感谢使用本程序，祝您生活愉快！"<<'\n';
                break;
            }
            cout<<"查找结果为：";
            if(Search_Bin(ST, key))
                cout<<Search_Bin(ST, key)<<'\n';
            else
                cout<<"此数据不存在！"<<'\n';
        }
        return 0;
    }
    /*
    11
    5 16 20 27 30 36 44 55 60 67 71
    */

## 四、实验结果 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]

## 五、实验讨论 ##

（1）熟悉了C++的上机环境，进一步掌握C++的结构特点；  
（2）掌握了查找。

[Link 1]: https://www.bilibili.com/video/BV1CJ411D7Kk
[B]: https://www.bilibili.com/video/BV1qE411273M
[B 1]: https://www.bilibili.com/video/BV1ot41127vG
[Link 2]: https://www.bilibili.com/video/BV11W41187eR
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1ODc4Mjky_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/5820d77de00e4889a2513123fc6374d8.png