前缀树实现

我正在处理存储城市列表(从文件中读取)及其相应的纬度和经度值。 在每个城市的尽头,我试图追加经度和纬度值。

因此,例如,特里的弗里蒙特看起来像

F-> R-> E-> M-> O-> N-> T – >(纬度和经度)

我能够成功地将值插入到trie中,但是当我尝试搜索特定城市时,经度和纬度值将返回为(null)

这是我的实施

void readFile(){ //the functions that deal with the trie struct trieNode *node = initializeTrie(); trieInsert(node, place, longitude, latitude); getTrie(node, place); trieFree(node); } struct trieNode{ char *longi; char *lat; struct trieNode *children[27]; char value; }; struct trieNode *initializeTrie(){ struct trieNode *pNode = NULL; pNode = (struct trieNode *)malloc(sizeof(struct trieNode)); if(pNode){ pNode->longi = '\0'; pNode->lat = '\0'; pNode->value = '\0'; memset(pNode->children, 0, sizeof(pNode->children)); } return pNode; } void trieFree(struct trieNode *root){ int i; if(root){ for(i = 0; ichildren[i]); } } free(root); } int trieInsert(struct trieNode *node, char *key, char *longitude, char *latitude){ struct trieNode *parent = node; //printf("Longi: %s", longitude); //printf(" "); //printf("Latitude: %s \n", latitude); if(key){ int index = 0; int i = 0; if(node){ while(key[i] != '\0'){ int indexVal = convertLetterToIndex(key[i]); if(!parent->children[indexVal]){ parent->children[indexVal] = initializeTrie(); parent->children[indexVal]->value = key[i]; } parent = parent->children[indexVal]; i++; } int longitudeLen = strlen(longitude); int latitudeLen = strlen(latitude); node->longi = malloc(longitudeLen + 1); strncpy(node->longi, longitude, longitudeLen + 1); node->longi[longitudeLen] = '\0'; //printf("Longi: %s", node->longi); node->lat = malloc(latitudeLen + 1); strncpy(node->lat, latitude, latitudeLen + 1); node->lat[latitudeLen] = '\0'; //printf("Lati: %s \n", node->lat); //free(node->longi); //free(node->lat); } } } //function to print the long and lat values based on the city void getTrie(struct trieNode *root, char *key){ struct trieNode *pNode = root; //bool flag = false; if(!key){ printf("Not found \n"); } if(!root){ printf("Not found \n"); } int i = 0; while(key[i] != '\0'){ int indexVal = convertLetterToIndex(key[i]); if(!pNode->children[indexVal]){ printf("Not found \n"); } pNode = pNode->children[indexVal]; i++; } printf("Longitude: %s", pNode->longi); printf(" "); printf("Latitude: %s \n", pNode->lat); } 

首先, longilat的类型为char * ,而不是char作为value ,因此初始化

  pNode->longi = '\0'; pNode->lat = '\0'; pNode->value = '\0'; 

看起来不太对劲。

它应该是

  pNode->longi = NULL; pNode->lat = NULL; pNode->value = '\0'; 

(我不想问为什么value只是一个字符 – 它是数据表示的特殊方式)

下一个注意点是使用strncpystrlen函数。

当您运行trieInsert接收指向char的指针时,您应该在使用strlen(longitude)strncpy(node->longi, longitude, longitudeLen + 1)类的表达式之前检查它们if(longitude != NULL) strncpy(node->longi, longitude, longitudeLen + 1) 。 当然,带指针的逻辑必须如下:

  • 定义指针并使用NULL初始化它;

  • 使用malloc或任何其他函数分配内存进行分配(如果分配失败,C标准动态内存分配函数返回空指针);

  • 检查指针的值,并在if( p != NULL)if( p )之后使用它。

这是一种很好的做法。