#include<iostream> using namespace std; typedef int KeyType; typedef struct{ KeyType key; char name[30]; }ElemType; typedef struct{ ElemType *R; int length =0; }SSTable; int goujian(SSTable &S){ cout << "请输入你需要构建的表的大小" << endl; int tiaoshu; cin >> tiaoshu; S.R = new ElemType[tiaoshu]; for(int i=1;i<=tiaoshu;i++){ cin >>S.R[i].key>>S.R[i].name; S.length++; } cout << "构建完成" << endl; } int erfenchazhao(SSTable S,KeyType k,int i){ //i为计量进行多少次比较查找成功 int low=1,high = S.length,mid=0; cout << "请输入你要查找的信息的关键字" << endl; cin >> k; i=0; while(low<=high){ mid = (low + high)/2; if(k==S.R[mid].key) return mid; else if(k<S.R[mid].key) high = mid-1; else low=mid; i++; } return 0; } int main() { int c =-1; SSTable S1; int k; while(c=0){ cout << "输入功能序号" << endl; cout << "1 构建查找表 2 二分查找" << endl; cin >> c; int i; switch(c){ case 1: goujian(S1); break; case 2: int mid = erfenchazhao(S1,k,i); if(mid>0){ cout << "你要查找的数据元素信息：" <<endl; cout << "该信息在查找表中的序号(位置)" << mid; cout << "关键字(学号)：" << S1.R[mid].key; cout << "其他信息：" << S1.R[mid].name; }else{ cout <<" 你要查找的内容不存在!"<<endl; } break; case 3: break; case 4: break; case 0: break; } } return 0; }

这是一段 C++ 代码，实现了一个二分查找算法。它定义了三个结构体类型，分别是 ElemType、SSTable 和 KeyType，其中 ElemType 表示表中的元素类型，包括关键字和名称；SSTable 表示查找表类型，包括一个指向元素数组的指针和数组长度；KeyType 表示关键字类型。主函数中，用户可以选择构建一个查找表或者进行二分查找。如果选择构建查找表，则会提示用户输入元素关键字和名称，并创建一个 SSTable 类型的对象 S1，保存元素信息。如果选择二分查找，则会提示用户输入要查找的关键字，并调用 erfenchazhao 函数进行查找。erfenchazhao 函数接受 SSTable 类型的对象 S、要查找的关键字 k 和计数器 i 作为参数，返回查找结果，如果找到则返回元素在表中的位置，如果未找到则返回 0。在寻找过程中，每次比较将计数器 i 加 1，最后返回 i 的值，表示查找过程中进行的比较次数。如果找到了元素，则输出该元素的关键字和名称，否则输出“你要查找的内容不存在”。

相关问题

//折半查找 #include<iostream> #include<fstream> #include<string> #include <algorithm> using namespace std; #define MAXSIZE 10000 #define KEYSIZE 10//关键词个数 #define OK 0 #define ERROR -1 typedef string KeyType; typedef struct { KeyType key;//关键字域 int count;//词频 int index;//在关键词列表中的序号 }ElemType; typedef struct { ElemType *R;//存储空间基地址 int length;//当前长度 }SSTable; //关键词列表 KeyType key[KEYSIZE] = {"little","prince","sheep","flowers","believe","stars","one","my","he","the"}; //初始化一个空的查找表ST //ST的0号单元闲置不用 int InitSSTable(SSTable &ST) { /*-----------代码开始--------------*/ /*-----------代码结束--------------*/ return OK; }

折半查找（二分查找）是一种高效的查找算法，它要求待查找的序列必须是有序的。它的基本思想是：首先确定待查找区间的中间位置，然后将待查找关键字与中间位置关键字进行比较，如果相等则查找成功；否则根据比较结果确定下一步查找的区间，直到找到所需的关键字或者区间为空为止。

在代码中，SSTable是一个结构体，它包含了一个关键字数组和一些其他的属性，如当前长度等。InitSSTable函数的作用是初始化一个空的查找表ST，即将ST中的R指向一个新分配的空间，并将其长度初始化为0。

续写下列代码 #include <iostream> #include <stdio.h> #include <malloc.h> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)<=(b)) typedef int Elemtype; typedef int KeyType; using namespace std; typedef struct { KeyType key; } SElemtype; typedef struct { SElemtype *elem; int length; } SStable; void creatSStable(SStable &T) { int i; // cout <<"请输入顺序表的长度:"; cin >>T.length; // cout<<"请输入顺序表的数据：" ; T.elem=(SElemtype*)malloc((T.length+1)*sizeof(KeyType)); for (i=1; i<=T.length; i++) cin >>T.elem[i].key; } /////////////////////////3)实现直接插入排序算法。 void InsertSort (SStable &L) {

int i, j;
for (i = 2; i <= L.length; i++) {
if (LT(L.elem[i].key, L.elem[i - 1].key)) {
L.elem[0] = L.elem[i];
L.elem[i] = L.elem[i - 1];
for (j = i - 2; LT(L.elem[0].key, L.elem[j].key); j--) {
L.elem[j + 1] = L.elem[j];
}
L.elem[j + 1] = L.elem[0];
}
}
}

int main() {
SStable T;
creatSStable(T);
InsertSort(T);
cout << "排序后的结果为：" << endl;
for (int i = 1; i <= T.length; i++) {
cout << T.elem[i].key << " ";
}
cout << endl;
return 0;
}