【数据结构】— —查找（折半查找，二叉排序树）

/*如果此程序运行不成功，请您做以下操作
 工具–编译选项—编译器
勾选编译时加入以下命令
并加入下面代码：-std=c++11
 */
#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
typedef string KeyType;
typedef int InfoType;
 
// 数据元素类型定义
struct ElemType {
    KeyType key;        // 关键字域
    InfoType otherinfo; // 其他域
};
 
// 顺序表的定义
struct SeqList {
    ElemType* R;   // 储存空间的基地址
    int length;    // 当前长度
};
 
// 折半查找函数，返回查找到的位置，若未找到，返回 -1
int binary_search(SeqList& list, int target_score) {
    int left = 0;
    int right = list.length - 1;
    while (left <= right) {
        int mid = (left + right) / 2;
        if (list.R[mid].otherinfo == target_score) {
            return mid;
        } else if (list.R[mid].otherinfo < target_score) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}
 
int main() {
    // 从键盘输入若干个学生成绩，并将其存储在顺序表中
    SeqList list = {new ElemType[6], 6};
    list.R[0] = {"ava", 35};
    list.R[1] = {"emy", 57};
    list.R[2] = {"jack", 62};
    list.R[3] = {"lily", 71};
    list.R[4] = {"lucy", 83};
    list.R[5] = {"mary", 90};
 
    // 输出所有学生成绩
    cout << "所有学生成绩：\n";
    for (int i = 0; i < list.length; ++i) {
        cout << list.R[i].key << " " << list.R[i].otherinfo << endl;
    }
    cout << endl;
 
    // 从键盘输入要查找的成绩
    int target_score;
    cout << "请输入要查找的成绩：";
    cin >> target_score;
 
    // 查找成绩为 target_score 的学生信息并输出
    int pos = binary_search(list, target_score);
    if (pos != -1) {
        cout << "成绩为 " << target_score << " 的学生信息：\n";
        cout << list.R[pos].key << " " << list.R[pos].otherinfo << endl;
    } else {
        cout << "未找到成绩为 " << target_score << " 的学生信息\n";
    }
    cout << endl;
 
    // 从键盘输入要查找的姓名
    string target_name;
    cout << "请输入要查找的姓名：";
    cin >> target_name;
 
    // 查找姓名为 target_name 的学生信息并输出
    pos = -1;
    for (int i = 0; i < list.length; ++i) {
        if (list.R[i].key == target_name) {
            pos = i;
            break;
        }
    }
    if (pos != -1) {
        cout << "姓名为 " << target_name << " 的学生信息：\n";
        cout << list.R[pos].key << " " << list.R[pos].otherinfo << endl;
    } else {
        cout << "未找到姓名为 " << target_name << " 的学生信息\n";
    }
 
    return 0;
}

#include "iostream"
using namespace std;
typedef int KeyType;
typedef int InfoType;
typedef int Elemtype;
 
//二叉排序树的二叉链表储存表示
typedef struct{
  KeyType key;//关键字项 
  InfoType otherinfo;//其他数据项 
}ElemType;//每个结点的数据域的类型
typedef struct BSTNode{
  ElemType data;//每个结点的数据域包括关键字和其他数据域
  struct BSTNode *lchild,*rchild;//左右孩子指针 
}BSTNode,*BSTree;
 
//二叉树的插入
void InsertBST(BSTree &T,KeyType key){
  //当二叉树不存在关键字等于e.key时，则插入
  if(!T){
    BSTree S;
    S=new BSTNode;//生成新的结点*S
    S->data.key=key;
    S->lchild=S->rchild=NULL;//把结点S作为叶子结点
    T=S;//把S插入到找到的位置 
  } 
  else if(key<T->data.key)
    InsertBST(T->lchild,key);//插入到左子树 
  else if(key>T->data.key)
    InsertBST(T->rchild,key);//插入到右子树 
} 
 
//二叉树的创建
void CreatBST(BSTree &T){//依次读入关键字为的结点，将相应的结点插入到二叉排序树T中
  T=NULL;//将二叉排序树T初始化为空树
  ElemType e;
  cin>>e.key;
  while(e.key!=-1){//以-1结束 
    InsertBST(T,e.key);
    cin>>e.key;
  } 
}
 
//二叉树的查找 
BSTree SearchBST(BSTree T,KeyType key){
  //查找成功，返回节点指针：查找失败，返回空指针 
  if((!T)||key==T->data.key) 
    return T;//如果为空树或查找成功
  else if(key<T->data.key)
    return SearchBST(T->lchild,key);//在左子树上找 
  else
    return SearchBST(T->rchild,key);//在右子树上找 
}
 
void InOrderTraverse(BSTree T){//中序遍历输出
  if(T){
    InOrderTraverse(T->lchild);//遍历左子树 
    cout<<T->data.key<<" ";
    InOrderTraverse(T->rchild);//遍历右子树 
  } 
}
 
int main(){
  BSTree T; 
  KeyType key;
  ElemType e;
  cout<<"请您输入整数构建二叉排序树(以-1结尾)"<<endl; 
  CreatBST(T);
  cout<<"中序遍历为："<<endl;
  InOrderTraverse(T);
  cout<<"\n插入数据元素13后，遍历结果为："<<endl;
  InsertBST(T,13);
  InOrderTraverse(T);
  if(!SearchBST(T,37)){
    cout<<"\n数据元素37不存在,已将其插入树中"<<endl; 
    InsertBST(T,37);
  }else{
    cout<<"\n数据元素37已存在"<<endl; 
  }
  if(!SearchBST(T,20)){
    cout<<"数据元素20不存在,已将其插入树中"<<endl;
    InsertBST(T,20);
  }else{
    cout<<"\n数据元素20已存在"<<endl;
  }
  cout<<"查找37和20后，遍历结果为："<<endl;
  InOrderTraverse(T);
}