数据结构：查找

实验目标：

提示

（1）创建查找表

（2）输出查找表元素

（3）在顺序表ST中顺序查找等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回0

（4）在有序表ST中折半查找等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回0

---

实验代码

#include <bits/stdc++.h>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

typedef int KeyType;

#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))

typedef struct{
    KeyType key;
}ElemType;

typedef struct{
    ElemType *elem;
    int length;
}SSTable;

void CreateTable(SSTable &ST)//创建查找表
{
    cout<<"请输入查找表的长度:";
    int len;
    cin>>len;
    cout<<endl;

    ST.elem=(ElemType *)malloc((len+1)*sizeof(ElemType));
    for(int i=1;i<=len;i++)
        cin>>ST.elem[i].key;
    ST.length=len;
}

void Traverse(SSTable ST)//输出查找表元素
{
    for(int i=1;i<=ST.length;i++){
        cout<<ST.elem[i].key<<" ";
    }
}

int Search_Seq(SSTable ST,KeyType key)//在顺序表ST中顺序查找等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回0
{
    int i=1;
    while(i<=ST.length && !EQ(ST.elem[i].key,(key)))
    ++i;
    if(i<=ST.length) return i;
    else return 0;
}

int Search_Bin(SSTable ST,KeyType key)//在有序表ST中折半查找等于key的数据元素。若找到，则返回该元素在表中的位置，否则返回0
{
    int low=1;
    int high=ST.length;
    while(low<=high){
        int mid=(low+high)/2;
        if(EQ(key,ST.elem[mid].key))
        return mid;
        else if(LT(key,ST.elem[mid].key))
        high=mid-1;
        else low=mid+1;
    }
}

int main()
{
    SSTable ST; 
    int c = 0;
    KeyType key;
    while (c != 3) {
        cout << endl << "1. 顺序查找法";
        cout << endl << "2. 折半查找法";
        cout << endl << "3. 退出";
        cout << endl << "选择功能(1~3):";
        cin>>c;
        switch (c)
        {
            case 1:
            CreateTable(ST); 
            Traverse(ST);
            
            cout<<"请输入要查找的数据:";
            cin>>key;
            cout<<Search_Seq(ST,key);
            break;

            case 2:
            CreateTable(ST); 
            Traverse(ST);
            
            cout<<"请输入要查找的数据:";
            cin>>key;
            cout<<Search_Bin(ST,key);
            break;

            case 3:
            cout<<"结束操作"<<endl;
            break;
        } 
    }
    system("pause");
    return 0;
}