【数据结构】5.1 顺序表的查找以及二分查找的实现

完整代码：

/*设计查找顺序表类，实现顺序表（在无序和有序两种情况）
的顺序查找和折半查找等操作。*/
#include<iostream>
#include<ctime>
using namespace std;
class StaticSearchTable {
private:
    int *data;
    int data_number;
    bool search_seq(int loc,bool flag);
    int Search_Seq(int key);//顺序查找
    int Search_Bs(int key);//折半查找（前提是必须是有序表）
    void print();
};
StaticSearchTable::StaticSearchTable(int n,bool flag)
{
    this->flag = flag;
    srand(time(NULL));
    //n为数组元素个数，但是0是不存放数值的故data空间要多开一个
    data = new int[n + 1];
    for (int i = 0; i < n; i++)
    {
        data[i + 1] = rand()%100;//0~99
    }
    data_number = n + 1;
    if (flag)
    {
        select_sort();
    }
    
}
bool StaticSearchTable::search_seq(int loc,int key)
{
    if (!data)
    {
        exit(1);
    }
    return data[loc] == key;
}
int StaticSearchTable::Search_Seq(int key)
{
    int i;
    data[0] = key;//哨兵，判断是否已经完成整个顺序表的遍历操作
    for (i = data_number; !search_seq(i,key); i--);//从后往前查找
    return i;//i若返回0即查找失败
}
int StaticSearchTable::Search_Bs(int key)
{
    
    //设置三个变量low,表示要查找的数据x位于mid+1与high序号之间，就不需要再去查找low
      与mid序号之间的元素了。因此，将low变量的值改为mid+1，重新查找mid+1(即low变
      量的新值)与high之间的数据
    4.逐步循环，如果到low>high时还未找到目标数据x，则表示数组中无此数据*/
    while (low <= high)
    {
        int mid = (low + high) / 2;
        if (data[mid] == key)
        {
            result = mid;
            break;
        }
        else if (key < data[mid])
        {
            high = mid - 1;
        }
        else
        {
            low = mid + 1;
        }
    }
    return result;
}
void StaticSearchTable::select_sort()
{
    for (int i = 1; i < data_number; i++)
    {
        for (int j = i + 1; j < data_number; j++)
        {
            if (data[i] > data[j])
            {
                int temp = data[j];
                data[j] = data[i];
                data[i] = temp;
            }
        }
    }
    flag = true;//是顺序表
}
void StaticSearchTable::print()
{
    if (flag)
    {
        cout << "顺序表为:  ";
    }
    else
    {
        cout << "无序表为:  ";
    }
    for (int i = 1; i < data_number; i++)
    {
        cout << data[i] << " ";
    }
    cout << endl;
    
}
void menu()//模拟菜单选项
{
    cout << " ------------------------------------------------------" << endl;
    cout << " |       1____________无序顺序表查找                  |" << endl;
    cout << " |       2____________有序顺序表查找                  |" << endl;
    cout << " |       0____________退出系统                        |" << endl;
    cout << " ------------------------------------------------------" << endl;
}
void SortedMenu()//有序顺序表模拟菜单选项
{
    cout << " ------------------------------------------------------" << endl;
    cout << " |       1____________有序顺序查找                    |" << endl;
    cout << " |       2____________有序折半查找                    |" << endl;
    cout << " |       0____________返回                            |" << endl;
    cout << " ------------------------------------------------------" << endl;
}

int main()
{

    while (1)
    {
        menu();
        int select;
        cout << "请输入您的选择：";    
        cin >> select;
        switch (select)
        {
        case 1:    //无序顺序表查找
        {    
            cout << "请输入无序表中的元素个数：";
            int n;
            cin >> n;
            StaticSearchTable L(n,true);
            L.print();//输出产生的有序表的元素
            SortedMenu();//有序顺序表查找选项菜单
            while (1)
            {
                int subSelect;
                cout << "请输入选择：";
                cin >> subSelect;
                if (subSelect == 0)//返回上一级
                    break;
                int k;
                cout << "请输入待查找的关键字：";
                cin >> k;
                int result;
                if (subSelect == 1)
                    result = L.Search_Seq(k);//有序顺序查找
                else if (subSelect == 2)
                    result = L.Search_Bs(k);//折半查找
                else
                {
                    cout << "选择错误，请重新输入！" << endl;
                    continue;
                }
                if (result > 0)
                    cout << "查找成功，为第" << result << "个元素." << endl;
                else
                    cout << "查找失败，没有关键字为" << k << "的元素." << endl;
            }
            break;
        }
        case 0:
            exit(0);
        default:
            cout << "您输入的选项有误，请重新输入：";
        }
    }
    system("pause");
    return 0;
}

?

测试结果：

（编辑：核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!