//算法7.3　折半查找



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

typedef struct{
    int key;//關(guān)鍵字域
}ElemType;

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

int InitList_SSTable(SSTable &L)
{
    L.R=new ElemType[MAXSIZE];
    if (!L.R)
    {
        cout<<"初始化錯(cuò)誤";
        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中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素。若找到，則函數(shù)值為
   // 該元素在表中的位置，否則為0
   int low=1,high=ST.length;                            //置查找區(qū)間初值
   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;       //繼續(xù)在前一子表進(jìn)行查找
      else  low =mid +1;                                //繼續(xù)在后一子表進(jìn)行查找
   }//while
   return 0;                                        //表中不存在待查元素
}// Search_Bin
int Search_Bin2(SSTable ST,int key,int low,int high) {
   // 遞歸折半查找                            //置查找區(qū)間初值
   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);        //繼續(xù)在前一子表進(jìn)行查找
      else if (key>ST.R[mid].key)return Search_Bin2(ST,key,mid+1,high);  
      else return 0;
      //繼續(xù)在后一子表進(jìn)行查找
   //}//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<<"輸入查找的數(shù)"<<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;    //出現(xiàn)次數(shù)
    struct tnode *lchild,*rchild;
}  tnode ,*BTree;
void CreaTree(BTree &p,char c) //采用遞歸方式構(gòu)造一棵二叉排序樹
{
    if (p==NULL)                //p為NULL,則建立一個(gè)新結(jié)點(diǎn)
    {
        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;//訪問根結(jié)點(diǎn)
        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<<"字符及出現(xiàn)次數(shù):\n";
    InOrder(root);
    cout<<endl;
    return 0;
}