3.cpp

折半查找

#include<stdio.h>   
#include<stdlib.h>   
#include<string.h>   
#define  INF  "in.txt"   
typedef   struct   Node
{   
   char  *word;   
   int   count;   
   struct   Node   *left,*right;   
}Node,*BiTree;   
    
int searchBst(BiTree T,char *keyword,BiTree *p)   
{   
                //二叉排序   树中(*T批向树根结点)杳找单调deyword，若找到，令p   指向该结点并返回１   
                //否则,p指向路径上出现的最后一个结点并返回0   
   int cmpres=0;   
   BiTree ptr;   
   *p=NULL;
   ptr=T;   
   while(ptr)   
   {   
     cmpres=strcmp(ptr->word,keyword);   
     if(cmpres==0)   
    {   
      *p=ptr; 
   //printf("查找成功！\n");
      return 0;     
    }   //查找成功，令p指向该结点，返回1   
     else     
    {     
      *p=ptr;   
      ptr=cmpres>0?ptr->left:ptr->right;   
    }   
   }//while  
   //printf("无此单词！\n");
   return   -1;       //查找失败   
  }//searchBst   
BiTree searchBst(BiTree p,char *keyword)   
{   
  BiTree t;
  if(p==NULL) 
     return NULL;
  
  if(strcmp( p->word, keyword )==0) 
  {
   printf("查找成功!\n");
   return p;
  }
  else if(strcmp( p->word, keyword )>0)
  {
   t=searchBst(p->left,keyword);
   if(t!=NULL)
   {
    
       return t;
   }
       
  }
  else if(strcmp( p->word, keyword )<0)
  {
   t=searchBst(p->right,keyword);
   if(t!=NULL)
   {
    
       return t;
   }
  
  }
  
   printf("查找失败 !\n");
 
 }//searchBst   
    
    
  int insertBst(BiTree *t,   char *keyword)                                                                     
  //在二叉排序树中(*T指向树根结点)插入单词   为dyword   的结点   
  //若该单词结点已在树中，则计数器增１；否则，在树中插入一个单词为keyword   的结点   
  {     
    BiTree s, p   ;   
    if(searchBst(*t,keyword,&p)==-1)   
 {   //找不到单词  deyword  的结点   
      s=(Node   *)malloc(sizeof(Node));   
      if(!s)     
   {   
         printf("   存储分配众所失败!   \n   " );     
         return   -1;     
   }   
     s->word=(char   *)malloc(strlen(keyword));   
     strcpy(s->word,keyword);   
     s->left=NULL;     
     s->right=NULL;     
     s->count=1;   
     if(p==NULL)   *t =s;   //keyword   是第一个出现的单词，令s作为根结点   
     else   if   (strcmp( p->word, keyword )< 0)   //deyword   比当前结点的单词大   
     p->right=s;   //将keyword插入当前结点的右子树上   
     else p->left=s;   //将keyword   插入当前结点的左子树上   
 }//if   
  else     
  p->count++;   
  return 0;   
  }//insertBst  
  void PrintBiTree(BiTree t,int n)
{
   int i;
   if(t==NULL) return;
      PrintBiTree(t->right,n+1);
  for(i=0;i<n;i++) printf("  ");
  if(n>=0)
  {
   printf("----");
   printf("%s\n",t->word);
  }
     PrintBiTree(t->left,n+1);
}
    
  void InOrder(BiTree root)     
  {   //中序遍历　root指向根的二叉排序树   
  
   if (root)     
   {   
       InOrder( root->left);   
       printf(" %s( %d )\n"   ,root->word,root->count);   
       InOrder(root->right);   
   }   
  }     
    
  int main()   
  {   
  
   char  ch[100], *word,buffer[5][100]; 
   
      BiTree root=NULL,p;   
      int i=0, tag,n ,j;  //i用于计算每个单词的长度，tag   标识当前读入的是英文字母
   printf("请输入要添加的单词数目：\n");  
   scanf("%d",&n);
      printf("请输入要添加的单词：\n"); 
       for(i=0;i<n;i++)
      
   {     //×将存储在buffer中的单词插入二叉排序树   
          scanf("%s",buffer[i]);
          word = (char *)malloc(strlen(buffer[i]));   
          strcpy(word,buffer[i]);   
          if (insertBst(&root,word)==-1)     
          return 0;   
   }//if   tag   
        
      PrintBiTree(root,0);
       printf("请输入要查找的单词数目\n");
    scanf("%d",&j);
      printf("请输入要查找的单词：\n"); 
   scanf("%d",&j);
       for(i=0;i<j;i++)
    {
     scanf("%s",ch);
           p=searchBst(root,ch) ;
    }
  }