如何从C中删除树词典中的单词?

问题描述 投票:2回答:1

我使用树在C中实现了一个字典,这个树存储了一个单词,其定义如下:

Dictionnary

如您所见,有些单词共享相同的字母。但现在我想实现一个删除功能,但不知道如何继续......我知道我应该开始删除这个词的结尾......这是我的代码,谢谢你将来的帮助!

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


typedef struct _noeud{
    char *value;
    struct _noeud *child[26];
}noeud_t;

typedef struct tree{
    node_t root;
}Tree;

Tree dict;

int getPos(char letter){
    char alpha[26]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    int i;
    for(i=0;i<strlen(alpha);i++){
        if(alpha[i]==letter){
            return i;
        }
    }
    return -1;

}

void addWord(node_t *node, char *word, char *def){
    int i;
    for(i = 0; i < strlen(word);i++){
        int letter=getPos(word[i]);
        if(letter==-1){
            printf("Unknown letter... \n");
        }
        node_t *parent = node;
        node = node->child[letter];
        if(!node){
            node = malloc(sizeof(node_t));
            parent->child[letter]=node;
        }
    }
    node->value = malloc(strlen(def)+1);
    strncpy(node->value,def,strlen(def)),
    printf("Word %s added to dictionnary.\n",word);
    fflush(stdin);
}

void findWord(node_t *node, char *word){
    printf("Looking for word %s \n",word);
    int i;
    for(i=0;i<strlen(word);i++) {
        int letter = getPos(word[i]);
        if(NULL ==node->child[letter]){
            printf("Unknown word ...\n");
            return;
        }
        else{
            node = node->child[letter];
        }
    }
    printf("Word found, its definition is : %s\n",node->value);

}

void deleteWord(node_t *node, char *word){
    int i=0;
    for(i=0;i<strlen(word);i++) {
        //...
    }
    printf("Word deleted !\n");
}


int main(){
    addWord(&dico.root,"dog","it's an animal");
    addWord(&dico.root,"pineapple","it's a fruit");
    addWord(&dico.root,"car","something to drive");
    findWord(&dico.root,"dog");
    findWord(&dico.root,"car");
    findWord(&dico.root,"pineapple");
    deleteWord(&dico.root,"pineapple");
    return 0;
}
c tree
1个回答
2
投票

我可以给你一个如何解决它的想法,但很抱歉我没有写代码。

所以从你的代码,我可以看到你有findWord函数,如果它完美的工作然后在你的删除内使用它去找到这个阶段,你指向它现在你必须想到三个可能性。

  1. 如果要删除的单词没有任何子项,则删除它而不再复杂化。
  2. 如果要删除的单词具有单个子项,则将该单词的父项指向该单词的子项。
  3. 如果要删除的单词有多个子项,则将该单词替换为其中一个子项,然后将其删除。

我希望这能帮到您