字典树 5687

详解

---

列表内容

字典树

标记为 1的是第一种，标记为2的是第二种做法

#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); }