三項探索木の挿入関数 - C

Question

私はC言語を新しくしており、主に三項探索木のデータ構造をコード化しようとしています。私は、有効なchar入力が渡されているという前提の下で作業しています。私は自分のinsert関数にいくつかの問題があります。最後のTSTnodeにもstrの最後の文字が保持される元の文字列を挿入することに注意してください。ここで

は、私はここで、これまで

struct TSTnode { 
    char* word; // NULL if no word ends here 
    char self; 
    struct TSTnode *left, *sub, *right; 
}; 


int insert_tst(struct TSTnode** tree, const char* str) { 
    return _insert(tree, str, 0); 
} 


int _insert(struct TSTnode** tree, const char* str, int position) { 

    if((*tree) == NULL) { 
     *tree = new_tst_node(*(str+position)); 
     position = position + 1; 
     if(*(str+position) == '\0') { 
      (*tree)->word = strcpy((*tree)->word,str); 
      return 1; 
     } 
    } 

    else if ((*tree)->self > *(str+position)) { 
     position = position + 1; 
     _insert(&((*tree)->left), str, position); 
    } 

    else if ((*tree)->self < *(str+position)) { 
     position = position + 1; 
     _insert(&((*tree)->right), str, position); 
    } 
    else { 
     position = position + 1; 
     _insert(&((*tree)->sub), str, position); 
    } 
    return 0; 

} 




struct TSTnode* new_tst_node(char self) { 
    struct TSTnode* newNode = (struct TSTnode*) malloc(sizeof(struct 
TSTnode)); 

    if (newNode == NULL) { 
     return NULL; 
    } 
    newNode->word = NULL; 
    newNode->self = self; 
    newNode->left = NULL; 
    newNode->right = NULL; 
    newNode->sub = NULL; 

    return newNode; 
}  

を持っているものである私がテストしてい方法です：

struct TSTnode* tree = NULL; 
char* words[1] = {"hello"}; 

for (int i = 0; i < 1; i++) { 
     if (insert_tst(&tree, words[i]) == 0) { 
      //print some error 
    } 
     else { //success } 

EDITを - 私の問題は私の条件分岐のどれも取らされていないことをされ、挿入機能単に0

Answer 1

注意を返すようにまっすぐ行く：あなたは紛らわしいTSTnode*との両方にtreeを使用。後者にはtree_ptrを使用し、同じことをしたふりをします。

---

あなたの主張は偽です。 if((*tree_ptr) == NULL)の本文が実行されます。あなたにはいくつかの問題があります。

1. *tree_ptr == NULL && *(str+position+1) != '\0'の場合は処理できません。

2. *tree_ptr != NULL && *(str+position+1) == '\0'の場合は正しく処理されません。

3. の場合は、常に0を返します。

4. あなたは決してwordを割り当てませんが、あなたはそれを尊重します。事は、とにかく再び文字列を格納するべきではありません！

5. str[0] == '\0'（空の文字列）の場合は処理しません。

   固定

：

int insert_tst(struct TSTnode** tree_ptr, const char* str) { 
    if (!*str) 
     return 0; /* Zero-length strings are not supported. */ 

    return insert_tst_helper(tree_ptr, str, 0); 
} 

int insert_tst_helper(struct TSTnode** tree_ptr, const char* str, int position) { 
    if (*tree_ptr == NULL) { 
     *tree_ptr = new_tst_node(*(str+position)); 
     if (*tree_ptr == NULL) 
      return 0; /* Memory allocation error. */ 
    } 

    if (*(str+position+1) == '\0') { /* If the next char is a NUL */ 
     (*tree_ptr)->is_word = 1; 
     return 1; 
    } 

    else if ((*tree_ptr)->self > *(str+position)) { 
     position = position + 1; 
     return insert_tst_helper(&((*tree_ptr)->left), str, position); 
    } 

    else if ((*tree_ptr)->self < *(str+position)) { 
     position = position + 1; 
     return insert_tst_helper(&((*tree_ptr)->right), str, position); 
    } 
    else { 
     position = position + 1; 
     return insert_tst_helper(&((*tree_ptr)->sub), str, position); 
    } 
} 

未テスト。

---

これをクリーンアップしましょう。

• *(str+position)

str[position]
ch == '\0'
• 
  に簡素化
  ch == 0
  に簡素化、次いで
  !ch
• position = position + 1; return insert_tst_helper(..., str, position);
  から
  return insert_tst_helper(..., str, position+1);
  に次いで
  ++position; return insert_tst_helper(..., str, position);
  に簡素化、次いで
  0123に
  から
  return insert_tst(..., str+1);
• なぜ再帰が使用されているのですか？
固定

：

int insert_tst(struct TSTnode** tree_ptr, const char* str) { 
    if (!*str) 
     return 0; /* Zero-length strings are not supported. */ 

    while (1) { 
     if (*tree_ptr == NULL) { 
      *tree_ptr = new_tst_node(*str); 
      if (*tree_ptr == NULL) 
       return 0; /* Memory allocation error. */ 
     } 

     if (!*(str+1)) { /* If the next char is a NUL */ 
      (*tree_ptr)->is_word = 1; 
      return 1; 
     } 

     int cmp = *str - (*tree_ptr)->self; 
     if  (cmp < 0) { tree_ptr = &((*tree_ptr)->left ); } 
     else if (cmp > 0) { tree_ptr = &((*tree_ptr)->right); } 
     else    { tree_ptr = &((*tree_ptr)->sub ); } 

     ++str; 
    } 
} 

未テスト。