查找

//算法7.3　折半查找



#include<iostream>
using namespace std;
#define MAXSIZE 100
#define OK 1;

typedef struct{
    int key;//关键字域
}ElemType;

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

int InitList_SSTable(SSTable &L)
{
    L.R=new ElemType[MAXSIZE];
    if (!L.R)
    {
        cout<<"初始化错误";
        return 0;
    }
    L.length=0;
    return OK;
}

int Insert_SSTable(SSTable &L) 
{
    int j=1;
    for(int i=1;i<MAXSIZE;i++)
    {
        L.R[i].key=j;
        L.length++;
        j++;
    }
    return 1;
}

int Search_Bin(SSTable ST,int key) {
   // 在有序表ST中折半查找其关键字等于key的数据元素。若找到，则函数值为
   // 该元素在表中的位置，否则为0
   int low=1,high=ST.length;                            //置查找区间初值
   int  mid;
   while(low<=high) {
       mid=(low+high) / 2;
      if (key==ST.R[mid].key)  return mid;              //找到待查元素
      else if (key<ST.R[mid].key)  high = mid -1;       //继续在前一子表进行查找
      else  low =mid +1;                                //继续在后一子表进行查找
   }//while
   return 0;                                        //表中不存在待查元素
}// Search_Bin
int Search_Bin2(SSTable ST,int key,int low,int high) {
   // 递归折半查找                            //置查找区间初值
   int  mid;
   //while(low<=high) {
      mid=(low+high) / 2;
      if (key==ST.R[mid].key)  return mid;              //找到待查元素
      else if (key<ST.R[mid].key)  return Search_Bin2(ST,key,low,mid-1);        //继续在前一子表进行查找
      else if (key>ST.R[mid].key)return Search_Bin2(ST,key,mid+1,high);  
      else return 0;
      //继续在后一子表进行查找
   //}//while
     
       
         
           
}// Search_Bin

void Show_End(int result,int testkey)
{
    if(result==0)
        cout<<"未找到"<<testkey<<endl;
    else
        cout<<"找到"<<testkey<<"位置为"<<result<<endl;
    return;
}

void main()
{
    SSTable ST;
    int low=1;
    InitList_SSTable(ST);
    Insert_SSTable(ST);
    int high=ST.length;
    int testkey1=8,testkey2=200;
    int result;
    cout<<"输入查找的数"<<endl;

    //cin>>testkey1>>testkey2;

    cout<<"非递归折半查找"<<endl;
    cout<<""<<endl;
    result=Search_Bin(ST, testkey1);
    Show_End(result,testkey1);
    result=Search_Bin(ST, testkey2);
    Show_End(result,testkey2);
    cout<<""<<endl;

    cout<<"递归折半查找"<<endl;
    cout<<""<<endl;
    result=Search_Bin2(ST, testkey1,low,high);
    Show_End(result,testkey1);
    result=Search_Bin2(ST, testkey2,low,high);
    Show_End(result,testkey2);
    cout<<""<<endl;
}

//文件名:exp9-5.cpp
#include<iostream>
using namespace std;
#define MAXWORD 100
typedef struct tnode 
{
    char ch;      //字符
    int count;    //出现次数
    struct tnode *lchild,*rchild;
}  tnode ,*BTree;
void CreaTree(BTree &p,char c) //采用递归方式构造一棵二叉排序树
{
    if (p==NULL)                //p为NULL,则建立一个新结点
    {
        p=new tnode;
        p->ch=c;
        p->count=1;
        p->lchild=p->rchild=NULL;
    }
    else if (c==p->ch){
        p->count++;
    }
    else if (c<p->ch) {
        p = p->lchild;
        p->ch=c;
    }
    else {
        p = p->rchild;
        p->ch=c;
    }
}
void InOrder(BTree p)   //中序遍历BST
{
    if (p!=NULL) 
    {
        InOrder(p->lchild);                 //中序遍历左子树
        cout<<p->ch<<":"<<p->count<<endl;//访问根结点
        InOrder(p->rchild);                 //中序遍历右子树
    }
}
int main()
{
    BTree root=NULL;
    int i=0;
    char str[MAXWORD];
    cout<<("输入字符串:");
    gets(str);
    while (str[i]!='\0') 
    {
        CreaTree(root,str[i]);
        i++;
    }
    cout<<"字符及出现次数:\n";
    InOrder(root);
    cout<<endl;
    return 0;
}