字典树

#include 
  #include 
  #include 
 using namespace std; 
 struct node { 
     int ji, num;     //这个num没有用  
     node *next[26];  //定义指向这个节点向下的26个方向  
     node(){ji=1;for(int i=0;i<26;++i) next[i]=NULL;}//每次申请空间的时候都把这26个指向下的方向变为空 ———————1  
    // node(){ji=0;for(int i=0;i<26;++i) next[i]=NULL;}//每次申请空间的时候都把这26个指向下的方向变为空 ———————2  
 }*head; //定义一个头指针  
 void insert(char *shu)    //插入数组shu  
 { 
     node *head1 = head;         //定义一个别名为head指针  
     int len = strlen(shu);      //计算出shu的长度  
     for (int i = 0;i < len;i++)  
     { 
         int cur = shu[i] - ‘a’; 
         if (head1->next[cur] == NULL) 
             head1->next[cur] = new node();  //每次初始化的时候ji为0next为空  
         else head1->next[cur]->ji++;    //这个不能忘了——————————————-1 
         head1=head1->next[cur];//—————————————————————-1
//    head1=head1->next[cur];  -----------------------------//每次弄完之后不能忘了自加------------------------------2 
//    head1->ji++;-------------------------------------------------------------------------------------2
}
} 
 void release(node *head2)          //这个是用来删除在堆中申请的空间 
 { 
     if(head2==NULL) return;         //判断head2的是否为空  
     for (int i = 0;i < 26;i++) 
     { 
         if (head2->next[i] != NULL)     //如果为非空则就把这个释放  
             release(head2->next[i]);      //递归调用 
     } 
     delete head2; 
 } 
 void delet(char *shu)            //删除  
 { 
     node *head1 = head;          // //定义一个别名为head指针  
     int len = strlen(shu); 
     for (int i = 0;i < len;i++) 
     { 
         int cur = shu[i] - ‘a’; 
         if (head1->next[cur] == NULL )      //  
             return; 
         else 
             head1 = head1->next[cur]; 
     } 
     int jilu = head1->ji;   //得出的是当删除的这个字符串结尾字符的那个ji存的包含这些字符串的个数  
     head1 = head; 
     node *p=head1; 
     int cur;  //cur定义在上边为了在for循环外边也可以用  
     for (int i = 0;i < len;i++) 
     { 
         cur = shu[i] - ‘a’; 
         p=head1; 
         head1 = head1->next[cur]; 
         head1->ji-=jilu; 
     } 
      release(head1);  //清空要删除的字符串前缀的空间 
      p->next[cur]= NULL;//head1=NULL  是错的因为head1只是那个地址的一个别名，  
 }//把那个地址的别名置为NULL没有用必须得是记录head1上一个地址然后把那个最后的  
 //p->next[cur]=NULL,才是有效的。  
 int search(char *shu)    //查找前缀包含这个字符串的字符串  
 { 
     node *head1 = head; 
     int len = strlen(shu); 
     for (int i = 0;i < len;i++) 
     { 
         int cur = shu[i] - ‘a’; 
         if (head1->next[cur] == NULL || head1->ji == 0)    //如果前缀没有查完就空了，说明没有这个前缀的字符串。————————–1 
             return 0;///—————————————————————————————————————–1 
         // if (head1->next[cur] == NULL || head1->ji <0) ——————————————————————————–2  
         //return 0;———————————————————————————————————————2 
         else 
             head1 = head1->next[cur]; 
     } 
   //  if(head1->ji>=0)           //因为第二种申请的时候ji为0 ——————————-2 
 //      return  1;————————————————————————-2 
 //      else return 0; ———————————————————————-2 
     return head1->ji;///—————————————————————–1
} 
 //void display(node *head1) 
 //{ 
 //    for(int i=0;i<26;i++) 
 //    if(head1->next[i]!=NULL) 
 //    cout<<”!NULL”;  
 //} 
 int main() 
 { 
     head = new node(); 
     int n; 
     cin >> n; 
     char s1[10], s2[35]; 
     while (n–) 
     { 
         cin >> s1 >> s2; 
         if (strcmp(s1, “insert”) == 0) 
             insert(s2); 
         else if (strcmp(s1, “delete”) == 0) 
             delet(s2); 
         else if (strcmp(s1, “search”) == 0) 
         { 
 //            display(head,0); 
             if (search(s2)) 
             printf(“Yes\n”); 
             else printf(“No\n”); 
         } 
     } 
     release(head);  
 }