線形リストに対して二分探索をしたいのですが，リストから関数への値の渡し方が分かりません。
解決済
回答 2
投稿
- 評価
- クリップ 1
- VIEW 3,367
前提・実現したいこと
C言語で，線形リストに対して二分探索をするプログラムを作りたいです．
リストはcsvファイルから読み込んで作成します．
発生している問題・エラーメッセージ
リストを作成(し表示して確認も)するところまでは出来たのですが，
二分探索で使う，リストの先頭・末尾・中央の値をどうやって関数に渡したらいいのかが分からず，リストを作成しただけで作業が止まってしまいました．
該当のソースコード
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define DATA_FILE "test_search.csv"
typedef struct _Node {
int data;
struct _Node *next;
} Node;
Node *make_node(void);
int make_list(void);
int disp_list(void);
Node *head;
Node *tail;
Node *center;
//リストの末尾と先頭,中央
int main(void){
make_list();//リスト作成
view_list();//リスト閲覧(確認用)
return 0;
}
//リスト作成
int make_list(void)
{
Node *p;
FILE *fp;
char *data_file=DATA_FILE;
if((fp=fopen(data_file,"r"))==NULL){
printf("%s can not be open\n",data_file);
return 1;
}
head=NULL;
while(p=make_node(),fscanf(fp,"%d",&p->data)!=EOF){
p->next=head;
head=p;
}
return 0;
}
int view_list(void)//リスト表示(確認用)
{
Node *p;
p=head;
printf("\n");
while(p!=NULL){
printf("%d\n",p->data);
p=p->next;
}
return 0;
}
Node *make_node(void)
{
return (Node *)malloc(sizeof(Node));
}さらに，csvファイルは昇順で並んでいるのですが，このプログラムだと表示するときに降順で表示されてしまいます．何故でしょうか？
-
気になる質問をクリップする
クリップした質問は、後からいつでもマイページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
クリップを取り消します
-
良い質問の評価を上げる
以下のような質問は評価を上げましょう
- 質問内容が明確
- 自分も答えを知りたい
- 質問者以外のユーザにも役立つ
評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。
質問の評価を上げたことを取り消します
-
評価を下げられる数の上限に達しました
評価を下げることができません
- 1日5回まで評価を下げられます
- 1日に1ユーザに対して2回まで評価を下げられます
質問の評価を下げる
teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。
- プログラミングに関係のない質問
- やってほしいことだけを記載した丸投げの質問
- 問題・課題が含まれていない質問
- 意図的に内容が抹消された質問
- 過去に投稿した質問と同じ内容の質問
- 広告と受け取られるような投稿
評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。
質問の評価を下げたことを取り消します
この機能は開放されていません
評価を下げる条件を満たしてません
質問の評価を下げる機能の利用条件
この機能を利用するためには、以下の事項を行う必要があります。
- 質問回答など一定の行動
-
メールアドレスの認証
メールアドレスの認証
-
質問評価に関するヘルプページの閲覧
質問評価に関するヘルプページの閲覧
checkベストアンサー
+2
このプログラムだと表示するときに降順で表示されてしまいます．何故でしょうか
１番目に読み込んだデータと2番目に読み込んだデータがどうつながるかといった点をよく把握しておられない気がします。紙と鉛筆でデータの繋がりを書いてみればこうなることに気づけるはずです。
head -> 2番目のデータ -> 1番目のデータ (tail)
view_listはheadからtailに向かって順に出力しているので逆順に印字されるわけです。
コードの文面を見るだけでなく、そのコードがどのようなデータ構造を生み出すかをビジュアルにイメージできるよう訓練することをお勧めします。
線形リストに対して二分探索
書けなくはないですが「線形リストは二分探索には向かない構造」であることを認識しておられるでしょうか？そうではない気がします。
二分探索を採用する条件は以下です。
(1) ソートされている(必須条件)
(2) ある範囲を決めたとき、ちょうど真ん中にあるデータに即座にアクセスできる
(2)の条件を満たすものとして思いつくのは以下の２つぐらいです。
(2-A) 配列のようなもの
ランダムアクセスできるので中央にも即座にアクセスできる。
(2-B) ニ分木のようなもの
ニ分木で任意のノードの左右にぶら下がるデータ数がほぼ一致するなら二分探索に向いています。
線形リストはランダムアクセス性がありません。また先頭や末尾は管理できたとしても中央は管理しないのが普通です。よって中央値を求めるとすれば、リストの端から順番に探すしかなく、それをするぐらいなら目的の要素を最初から線形探索したほうが自然だと思います。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
0
さらに，csvファイルは昇順で並んでいるのですが，このプログラムだと表示するときに降順で表示されてしまいます．何故でしょうか？
headに保存した前のアドレスを新線形（構造体）のnext（次）に登録している事になり、最後のもののアドレスがheadに入ります。 (新)->(旧)
線形の部分のみのサンプルです。
#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define DATA_FILE "test_search.csv"
typedef struct _Node {
int data;
struct _Node *next;
} Node;
Node *make_node(void);
int make_list(void);
int disp_list(void);
Node *head;
Node *tail;
Node *center;
//リストの末尾と先頭,中央
int main(void){
make_list();//リスト作成
view_list();//リスト閲覧(確認用)
return 0;
}
//リスト作成
int make_list(void)
{
Node *p;
FILE *fp;
char *data_file=DATA_FILE;
if((fp=fopen(data_file,"r"))==NULL){
printf("%s can not be open\n",data_file);
return 1;
}
head=make_node();
p=head;
while(fscanf(fp,"%d",&p->data)!=EOF){
p->next=make_node();
tail=p;
p=p->next;
}
tail->next=NULL;
free(p);
return 0;
}
int view_list(void)//リスト表示(確認用)
{
Node *p;
p=head;
printf("\n");
while(p!=NULL){
printf("%d\n",p->data);
p=p->next;
}
return 0;
}
Node *make_node(void)
{
return (Node *)malloc(sizeof(Node));
}二分探索ですが、真ん中を見つける方法が、線形リストだと良い方法が浮かびませんでした。
投稿
-
回答の評価を上げる
以下のような回答は評価を上げましょう
- 正しい回答
- わかりやすい回答
- ためになる回答
評価が高い回答ほどページの上位に表示されます。
-
回答の評価を下げる
下記のような回答は推奨されていません。
- 間違っている回答
- 質問の回答になっていない投稿
- スパムや攻撃的な表現を用いた投稿
評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。
15分調べてもわからないことは、teratailで質問しよう！
- ただいまの回答率 88.35%
- 質問をまとめることで、思考を整理して素早く解決
- テンプレート機能で、簡単に質問をまとめられる
2017/11/27 22:44
元々実装には向いておらず理解があやふやなままでは難しかったようです。