#include #include using namespace std;typedef int KeyType;typedef struct {KeyType key;}ElemType;typedef struct {ElemType* data;int length;}SSTable;bool Create(SSTable& ST, int n);int Search_Seq(SSTable ST, KeyType kval);//线性查找int Search_Bin(SSTable ST, KeyType kval);//折半查找bool Create(SSTable& ST, int n) {ST.data = new ElemType[n];if (!ST.data)return 0;cout << "请输入查找表各元素:" << endl;for (int i = 1; i <= n; i++)cin >> ST.data[i].key;ST.length = n;return 1;}int Search_Seq(SSTable ST, KeyType kval) {//在顺序表ST中顺序查找其关键字等于kval的记录 //若找到则函数值为该元素在表中的位置，否则为0ST.data[0].key = kval; //设置"哨兵“//从后往前查找int i;for (i = ST.length; ST.data[i].key != kval; i--);return i; //找不到时，i为0}int Search_Bin(SSTable ST, KeyType kval){//在有序表ST中折半查找关键字等于kval的数据元素。 //若找到，则函数值为该元素在表中的位置，否则为0。int low, high, mid;low = 1; high = ST.length; //置区间初值while (low <= high) {mid = (low + high) / 2;if (kval == ST.data[mid].key) return mid; //找到else if (kval < ST.data[mid].key)high = mid - 1; //继续在前半区间内进行查找else low = mid + 1; //继续在后半区间内进行查找} return 0; //顺序表中不存在待查元素}int main(){SSTable ST;int n, i;KeyType key;cout << "请输入查找表中元素个数:" << endl;cin >> n;if (!Create(ST, n)) {cout << "查找表赋值失败" << endl;return 1;}cout << "请输入要查找的元素值:" << endl;cin >> key;cout << "线性查找:" << endl;i = Search_Seq(ST, key);if (i == 0)cout << "未找到！" << endl;elsecout << "找到，位序为" << i << endl;cout << "-----------------------------------" << endl;cout << "折半查找:" << endl;i = Search_Bin(ST, key);if (i == 0)cout << "未找到！" << endl;elsecout << "找到，位序为" << i << endl;cout << "-----------------------------------" << endl;return 0;}
实验样例