首页 > 其他分享 >顺序查找和二分查找实验

顺序查找和二分查找实验

时间:2023-01-18 15:35:24浏览次数:45  
标签:二分 std 顺序 cout int ST 查找 num key

数据结构课上的一份实验报告
主要是应对实验报告,应该存在逻辑错误的地方没改。

#include <iostream>

typedef int KeyType;
typedef int InfoType ;

#define MAXSIZE 100

typedef struct
{
    KeyType key;
    InfoType otherinfo;
}ElemType;

typedef struct
{
    ElemType *R;
    int lenght;
}SSTable;

int InitList_SSTable(SSTable &L)
{
    L.R = new ElemType[MAXSIZE];
    if (!L.R)
    {
        std::cout << "初始化错误";
        return 0;
    }
    L.lenght = 0;
    return 1;
}

int Create_list(SSTable &ST){
    int i,n,p;
    std::cout << "所需建立表的个数:" ;
    std::cin >> n;
    ST.lenght = n;
    for(i=1;i<=n;i++){
        std::cout << "输入表中第" << i << "个数:";
        std::cin >> p;
        ST.R[i].key = p;
    }
    return 0;
}//建表

int Insert_List(SSTable &ST, int e){
    std::cout << "没有此元素,自动为您将元素插入最后。" << std::endl;
    ST.R[ST.lenght].key = e;
    ST.lenght += 1;
    return 0;
}//插入

int Search_Seq(SSTable ST, KeyType key)
{
    std::cout << "顺序查找法:" << std::endl;
    int i,sum=0;
    std::cout << "当前比较的元素是:";
    for(i=ST.lenght;i>=1;--i){
        if(ST.R[i].key==key) {
            std::cout << "最终比较了" << sum << "次。" << std::endl;
            return i;
        }
        else{
            std::cout << ST.R[i].key;
            std::cout << ";";
            sum += 1;
        }
    }
    std::cout << std::endl;
    std::cout << "最终比较了" << sum << "次。" << std::endl;
    Insert_List(ST,key);
    return 0;
}//顺序查找

int Search_Bin(SSTable ST,KeyType key) {
    int i=0;
    std::cout << "二分查找法:" << std::endl;
    int low=1;
    int hight=ST.lenght;
    while(low<=hight) {
        int mid = (low + hight) / 2;
        if (key == ST.R[mid].key) {
            std::cout << "最终比较了" << i << "次。" << std::endl;
            return mid;
        } else if (key < ST.R[mid].key) {
            std::cout << ST.R[mid].key << ";";
            hight = mid - 1;
            i++;
        } else {
            std::cout << ST.R[mid].key << ";";
            low = mid + 1;
            i++;
        }
    }
    std::cout << std::endl;
    std::cout << "最终比较了" << i << "次。" << std::endl;
    Insert_List(ST,key);
    return 0;
}//二分




int main()
{
    SSTable ST;
    int key,Bin_num,Seq_num;
    InitList_SSTable(ST);

    std::cout << "********************当前建立第一个表********************" << std::endl;
    Create_list(ST);
    std::cout << "请输入需要查询的元素:";
    std::cin >> key;
    Seq_num = Search_Seq(ST,key);
    if(Seq_num){
        std::cout << "此元素在表中的位置是" << Seq_num << std::endl;
    }

    std::cout << "-------------------------------------------------" << std::endl;

    std::cout << "请输入第二次需要查询的元素:";
    std::cin >> key;
    Seq_num = Search_Seq(ST,key);
    if(Seq_num){
        std::cout << "此元素在表中的位置是" << Seq_num << std::endl;
    }

    std::cout << "********************当前建立第二个表********************" << std::endl;
    Create_list(ST);
    std::cout << "请输入需要查询的元素:";
    std::cin >> key;
    Bin_num = Search_Bin(ST,key);
    if(Bin_num){
        std::cout << "此元素在表中的位置是" << Bin_num << std::endl;
    }

    std::cout << "-------------------------------------------------" << std::endl;

    std::cout << "请输入第二次需要查询的元素:";
    std::cin >> key;
    Bin_num = Search_Bin(ST,key);
    if(Bin_num){
        std::cout << "此元素在表中的位置是" << Bin_num << std::endl;
    }


}

标签:二分,std,顺序,cout,int,ST,查找,num,key
From: https://www.cnblogs.com/qianyuzz/p/17059906.html

相关文章