質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • C

    4370questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

C言語 二分木探索による辞書の作成

受付中

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 1,681
退会済みユーザー

退会済みユーザー

前提・実現したいこと

以下のようなコマンドを入力としてうけつける辞書を作ろうと考えています。
「insert <word> <tango>」: <word>の翻訳が<tango>であるとデータベースに登録する。既に登録されている場合は上書きする。
「delete <word>」: <word>をデータベースから削除する。
「search <word>」: <word>をデータベースから検索し、その翻訳を表示する。 単語がデータベースに存在しないときには、「(not found)」と表示する。
「quit」: プログラムを終了する。

例えば、以下のような入力が想定されています。

insert apple 林檎
insert orange オレンジ
insert grape 葡萄
insert pear 梨
insert strawberry 苺
insert raspberry 木苺
insert fig 無花果
insert kaki 柿
insert apricot 杏
insert peach 桃
search orange
insert orange 蜜柑
search orange
delete orange
search orange
search strawberry
quit

これを入力すると、以下のように出力されるはずです。
オレンジ
蜜柑
(not found)

発生している問題・エラーメッセージ

deleteの動作を行うと、セグフォに陥ってしまいますが、なぜかがわかりません。

該当のソースコード

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

typedef char *String;
typedef struct tnode *BTree;
struct tnode {
    String key;
    String value;
    BTree left;
    BTree right;
};

BTree btree_empty()
{
    /* 空木を返す。 */
  return NULL;
}

int btree_isempty(BTree t)
{
    /* `t'が空木なら0以外を、そうでないなら0を返す。 */
  if (t == (btree_empty())) return 1;
      return 0;
}

BTree btree_insert(String key, String val, BTree t)
{
    /*
    * 文字列`key'をキーとして、文字列`val'を二分探索木`t'に挿入し、その木を返す。
    * `key'と`val'の内容はデータベースにコピーされる。
    * 同じキーを持つ項目が既に存在する場合は、その項目を上書きする。
    */
    if(btree_isempty(t) != 0){
      BTree tree = malloc(sizeof(struct tnode));
      tree->key = key;
      tree->value = val;
      tree->left = btree_empty();
      tree->right = btree_empty();
      return tree;
    }
    if(strcmp(key, t->key) < 0){
      t->left = btree_insert(key, val, t->left);
      return t;
    }else if(strcmp(key, t->key) > 0){
      t->right = btree_insert(key,val, t->right);
      return t;
    }
    t->value = val;
    return t;
}

BTree btree_searchmin(BTree t)
{
  while(btree_isempty(t->left) != 0) t = t->left;
  return t;
}

 BTree btree_deletemin(BTree t)
{
  if(btree_isempty(t->left) == 0){
    BTree tree = malloc(sizeof(struct tnode));
    tree->left = btree_deletemin(t);
    tree->right = t->right;
    tree->key = t->key;
    tree->value = t->value;
    return tree;
  }
  return t->right;
}


BTree btree_delete(String key, BTree t)
{
    /*
    * 文字列`key'をキーとする項目を、二分探索木`t'から削除し、その木を返す。
    */
  if (btree_isempty(t) != 0) return t;

  if(strcmp(key, t->key) < 0){
      t->left = btree_delete(key, t->left);
      return t;
    }else if(strcmp(key, t->key) > 0){
      t->right = btree_delete(key, t->right);
      return t;
    }
  BTree min = btree_searchmin(t);
  BTree del = btree_deletemin(t);
  del->key = min->key;
  del->value = min->value;
  return del;
}



struct tnode *btree_search(String key, BTree t)
{
    /*
    * 二分探索木`t'を検索し、文字列`key'をキーとするノードへのポインタを返す。
    * 見付からない場合は、NULLを返す。
    */
  if(btree_isempty(t) != 0) return NULL;

    if(strcmp(key, t->key) < 0){
      return btree_search(key, t->left);
    }else if(strcmp(key, t->key) > 0){
      return btree_search(key, t->right);
    }
    return t;
}
void btree_free(BTree t)
{
    /*
     * 二分探索木`t'の内容を全て消去し、メモリを解放する。
     */
     if(t == NULL)
      return;
    btree_free(t->left);
    btree_free(t->right);
    free(t);
}

int main(int argc, char *argv[])
{
  char cmd[100];
  char key[100];
  char val[100];
  struct tnode *search;
  BTree t = btree_empty();
      while (scanf("%99s", cmd) != EOF) {
      if (strncmp(cmd,"insert",6) == 0) {

//insertの操作

scanf("%99s", key);

scanf("%99s", val);

t = btree_insert(key, val, t);
      } else if (strncmp(cmd,"delete",6) == 0) {

scanf("%99s", key);

t = btree_delete(key, t);
        } else if (strncmp(cmd,"search",6) == 0) {

 scanf("%99s", key);

 search = btree_search(key, t);

 if(btree_isempty(search) != 0){

  printf("(not found)\n");

  }else printf("%s\n",search->value);

  }else if(strcmp(cmd,"quit") == 0){
 return 0;

  }else{
            printf("(unknown command)\n");
  }
        cmd[0] = '\0';
}
  btree_free(t);
   return 0;
}

試したこと

自分なりに、gdbを用いてデバッグしてみたのですが、よくわかりませんでした。

補足情報(言語/FW/ツール等のバージョンなど)

より詳細な情報

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

0

ぱっと見バグだらけで、どこから話すべきか悩ましいですが…
まず、ツリーに登録されている要素へのポインタvalは、常にmain関数の中のvalへのポインタになりますよね…? (複製されていない)
あとquitしたときの解放処理もないですし…。

消去するときのアルゴリズムをゆっくり、口に出してみてください。それが答えです。

追記: 肝心のヒントを書き忘れていました。
参考文献
https://www.google.co.jp/url?sa=t&source=web&rct=j&url=http://f-server.ics.kagoshima-u.ac.jp/~fuchida/algorithm/alg10-%25E4%25BA%258C%25E5%2588%2586%25E6%258E%25A2%25E7%25B4%25A2%25E6%259C%25A8.pdf&ved=0ahUKEwjKz6XPx83RAhXLerwKHf2iAhUQFggaMAA&usg=AFQjCNHVcPps2iWdIZJ67uq6m8U1e5tTNg

暴走した理由ですが、

BTree btree_deletemin(BTree t)
{
...
    tree->left = btree_deletemin(t);
...
}


この行のどこかが間違ってましたとだけ。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

同じタグがついた質問を見る

  • C

    4370questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。