用类写的。。麻烦高手看看啊
# include <iostream>
# include <cstdio>
# include <cstring>
using namespace std;
struct node
{
    char *data;
    int place;
    node *left;
    node *right;
};
class list
{
   public:
     int num;
     node* data[100000];
     list()
     {
      num=0;
     }
     void add(node *p)
     {
     data[++num]=p;
     }
     void sort()
     {
      for(int i=1;i<num;i++)
       for(int j=1;j<=num-i;j++)
         if(data[j]->place>data[j+1]->place)
         {
          node *temp=data[j];
          data[j]=data[j+1];
          data[j+1]=temp;
         }
      }
      void print()
      {
         for(int i=1;i<=num;i++) cout<<" "<<data[i]->data;  
         cout<<endl;
      }
};
   
class tree
{
  public:
    node *root;
  
    tree()
    {
     root=NULL;
    }
    void add(char *str,int count);
    node* search(char *str);
};
void tree::add(char *str,int count)
{
    if(!root)
    {
     root=new node;
     root->data=str;
     root->left=NULL;
     root->right=NULL;
     root->place=count;
    }
    else
    {
      node *p=root;
      while(1)
      {
       if(strcmp(str,p->data)==1)
       {
          if(p->right!=NULL) p=p->right;
          else break;
       }    
        else if(strcmp(str,p->data)==-1)
       {
          if(p->left!=NULL) p=p->left;
          else break;
       }  
       else return;
      }
      if(strcmp(str,p->data)==1)
      {
       p->right=new node;
       p=p->right;
      }
      else 
      {
       p->left=new node;
       p=p->left;
      }
      p->data=str;
      p->left=p->right=NULL;
      p->place=count;
    }
}
node* tree::search(char *str)
{
     node *p=root;
     if(root==NULL) return NULL;
     while(p)
     {
      switch(strcmp(str,p->data))
      {
       case 1:
          p=p->right;
          break;
       case 0:
          return p;
       case -1:
          p=p->left;
          break;
       };
      }
      return NULL;
}

int main()
{
    tree st;
    int count=1;
    while(1)
    {
     char *p=new char[19];
     cin>>p;
     if(!strcmp(p,"#")) 
     {
      delete[] p;
      break;
     }
     st.add(p,count++);
    }
    while(1)
    {
     char *p=new char[19];
     cin>>p;
     if(!strcmp(p,"#")) 
     {
      delete[] p;
      break;
     }
     if(st.search(p)!=NULL)
     {
       cout<<p<<" is correct"<<endl;
       delete[] p;
     }
     else
     {
       cout<<p<<":";
       list result;
       node* res;
       char temp[19];
        for(int i=0;i<strlen(p);i++) //删除
       {
          strcpy(temp,p);
          for(int j=i;j<strlen(p);j++) temp[j]=temp[j+1];
          if(res=st.search(temp)) result.add(res);
       }
       for(int i=0;i<strlen(p);i++)//替换 
       {
         strcpy(temp,p);
         for(char tempc='a';tempc<='z';tempc++)
         {
          temp[i]=tempc;
          if(res=st.search(temp)) result.add(res);
         }
       }
       for(int i=0;i<=strlen(p);i++)//增加 
       {
        strcpy(temp,p);
        for(int j=strlen(p);j>=i;j--) temp[j+1]=temp[j];
        for(char tempc='a';tempc<='z';tempc++)
        {
          temp[i]=tempc;
          if(res=st.search(temp)) result.add(res);
        }
       }
       result.sort();
       result.print();
       delete[] p;
       }
     }
     system("pause");
     return 0;
}
          
    
   
          
      
 

• Re:WA怕了。。怎么都找不到错。。用二叉搜索树做的 (18) yzhw 2009-01-23 19:44:02