前缀树实现
我正在处理存储城市列表(从文件中读取)及其相应的纬度和经度值。 在每个城市的尽头,我试图追加经度和纬度值。
因此,例如,特里的弗里蒙特看起来像
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); }
首先, longi
和lat
的类型为char *
,而不是char
作为value
,因此初始化
pNode->longi = '\0'; pNode->lat = '\0'; pNode->value = '\0';
看起来不太对劲。
它应该是
pNode->longi = NULL; pNode->lat = NULL; pNode->value = '\0';
(我不想问为什么value
只是一个字符 – 它是数据表示的特殊方式)
下一个注意点是使用strncpy
和strlen
函数。
当您运行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 )
之后使用它。
这是一种很好的做法。