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

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

新規登録して質問してみよう
ただいま回答率
85.50%
C

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

Q&A

解決済

1回答

3560閲覧

連結リストを二分探索木につなぎ替える

Kassy11

総合スコア26

C

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

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

データ構造

データ構造とは、データの集まりをコンピュータの中で効果的に扱うために、一定の形式に系統立てて格納する形式を指します。(配列/連想配列/木構造など)

連結リスト

連結リストとは、データ構造のひとつであるリストの中で、要素が前後の要素の情報を持つことで、要素が連結(リンク)しているリストの事を呼びます。

0グッド

1クリップ

投稿2019/07/24 09:27

現在、事前に作成した連結リストをもとに二分探索木を作成しようとしています。

ノード定義:

node

1typedef struct school_record SRec; 2struct school_record{ 3 float gpa;/*累積GPA*/ 4 int credit;/*累積単位数*/ 5 char name[200];/*名前(アルファベット)*/ 6 SRec *next; /*次のセルへのポインタ*/ 7 SRec *left,*right;/*二分探索木で用いる部分木へのポインタ*/ 8};

連結リストとしてノードをつなぐ処理をした際に各ノードのleft,rightにはNULLを代入しています。

連結リストから二分探索木を作成するための関数(未完成):

C

1SRec *create_tree(SRec *front,int (*comp)(const void *, const void *)){ 2 int order;/*比較関数の結果を格納する*/ 3 SRec **p;/*二分探索木をたどるためのダブルポインタ,"ノードを指すポインタ"を指すポインタ*/ 4 SRec *tree;/*二分探索木の先頭*/ 5 tree = front;/*ポインタtreeがリストの先頭frontを指す*/ 6 p = &tree;/*ダブルポインタがリストの先頭を指しているポインタを指す*/ 7 8 9while((*p)->next != NULL){/*連結リストのノード回数繰り返す=nextがNULLになる(ノードの最後)まで*/ 10 while(*p){/*ダブルポインタpが指しているポインタがNULLポインタでない限り続ける*/ 11 12 13 order = (*comp)(*p,(*p)->next);/*ダブルポインタpが指しているポインタの指す先と、どこを比較するのか??*/ 14 15 if(order<0){ 16 p = &((*p)->right); 17 /*右部分木に進み、pを変更する*/ 18 }else{ 19 p = &((*p)->left); 20 /*左部分木に進み、pを変更する*/ 21 } 22 } 23 24 /*二分探索木をつなげる*/ 25} 26 27 28 return tree; 29} 30

第1引数で受け取るfrontは連結リストの先頭ノードへのポインタ、そして第2引数で受け取るのはノードの値を比較する自作比較関数で、比較するメンバはコマンドライン引数で指定し以下のように呼び出します。

if(strcmp(argv[1],"credit")==0){/*argv[1]で指定されたメンバでソートし、先頭要素のポインタををsort_frontに代入する*/ tree_front = create_tree(front,comp_credit); }else if(strcmp(argv[1],"gpa")==0){ tree_front = create_tree(front,comp_gpa); }else if(strcmp(argv[1],"name")==0){ tree_front = create_tree(front,comp_name); }else{ printf("ソートしたいフィールドをcredit/gpa/nameの中から正しく選択してください。\n"); }

以上のようにコードを書いていたのですが、
create_tree関数で、どのように繰り返し文を書きノードを書けばいいのかわかりません。
どなかたかわかる方がいればヒントなど教えていただければ幸いです。

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

単に tree を作るだけでしたら, リストのループの中にツリーを作るループを入れるだけかと思います.

以下はコンパイルは確認しましたが動作はさせていません

c

1SRec *create_tree(SRec *front, int (*comp)(const void *, const void *)){ 2 SRec *tree;/*二分探索木の先頭*/ 3 tree = front;/*ポインタtreeがリストの先頭frontを指す*/ 4 5 for(SRec *srec=front->next; srec!=NULL; srec=srec->next) { 6 SRec *p = tree; /*tree内のポインタ */ 7 while(1) { 8 if(comp(p, srec)<0) { 9 /*右*/ 10 if(p->right == NULL) { 11 p->right = srec; 12 break; 13 } 14 p = p->right; 15 } else { 16 /*左*/ 17 if(p->left == NULL) { 18 p->left = srec; 19 break; 20 } 21 p = p->left; 22 } 23 } 24 } 25 26 return tree; 27}

投稿2019/07/24 12:08

編集2019/07/24 17:03
jimbe

総合スコア12545

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Kassy11

2019/07/25 11:07

回答ありがとうございます。 jimbeさんの書いてくださったコードをもとにダブルポインタを利用したコードを書いてみたのですが、 SRec *create_tree(SRec *front,int (*comp)(const void *, const void *)){ SRec **p;/*二分探索木をたどるためのダブルポインタ,"ノードを指すポインタ"を指すポインタ*/ SRec *q;/*リストをたどるためのポインタ*/ SRec *tree;/*二分探索木の先頭を指すポインタ*/ tree = front;/*ポインタtreeがリストの先頭frontを指す*/ p = &tree;/*ダブルポインタがリストの先頭を指しているポインタを指す*/ for(q=front->next;q!=NULL;q=q->next){/*リストのループの中にツリーをつくるループを入れる*/ while(1){ if(comp(*p,q)<0){ /*右部分木への操作*/ if((*p)->right == NULL){ (*p)->right = q; break; } p = &((*p)->right); }else{ /*左部分木への操作*/ if((*p)->left == NULL){ (*p)->left = q; break; } p = &((*p)->left); } } printf("node:%p left:%p right:%p \n", q, q->left, q->right); } return tree;/*二分探索木の先頭へのポインタを返す*/ } アドレスを表示させるデバッグ用コード printf("node:%p left:%p right:%p \n", q, q->left, q->right); をwhileをbreakしたときに毎回表示させるようにしたのですが、 node:00000000009F2260 left:0000000000000000 right:0000000000000000 node:00000000009F2350 left:0000000000000000 right:0000000000000000 のように表示されます。 これはright,leftにつながっていないということでしょうか?? ちなみに与えるノードのデータは3つの整数値で、45,54,6と続きます。
jimbe

2019/07/25 12:24

なぜダブルポインタに拘られるのでしょう. 「ダブルポインタを使って作成」という縛りの課題等なのでしょうか.
jimbe

2019/07/25 12:33

while ループを抜けた時, q が示す SRec はツリーの末端に接続された"葉"です. ですので q->right/left とも NULL のままです.
Kassy11

2019/07/25 12:40

なるほど、基本的な質問で申し訳ありません(汗) ダブルポインタを用いて書きたかったのは、近々二分探索木でソートを行うようなコードを書こうとしているためです。
jimbe

2019/07/25 13:03

tree をバランス化するのであればダブルポインタは必要になるかと思いますが, それは create_tree の動作が Ok となってからが良いかと思います.
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問