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

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

ただいまの
回答率

91.36%

  • C

    2525questions

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

  • ポインタ

    81questions

    ポインタはアドレスを用いてメモリに格納された値を"参照する"変数です。

線形リストに対して二分探索をしたいのですが,リストから関数への値の渡し方が分かりません。

解決済

回答 2

投稿 2017/11/21 23:06

  • 評価
  • クリップ 0
  • VIEW 119

Cstdy_sun8

score 1

前提・実現したいこと

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ページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

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

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

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

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

    詳細な説明はこちら

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

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

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

回答 2

checkベストアンサー

+2

このプログラムだと表示するときに降順で表示されてしまいます.何故でしょうか

1番目に読み込んだデータと2番目に読み込んだデータがどうつながるかといった点をよく把握しておられない気がします。紙と鉛筆でデータの繋がりを書いてみればこうなることに気づけるはずです。

head -> 2番目のデータ -> 1番目のデータ (tail)

view_listはheadからtailに向かって順に出力しているので逆順に印字されるわけです。

コードの文面を見るだけでなく、そのコードがどのようなデータ構造を生み出すかをビジュアルにイメージできるよう訓練することをお勧めします。

線形リストに対して二分探索

書けなくはないですが「線形リストは二分探索には向かない構造」であることを認識しておられるでしょうか?そうではない気がします。

二分探索を採用する条件は以下です。

(1) ソートされている(必須条件)
(2) ある範囲を決めたとき、ちょうど真ん中にあるデータに即座にアクセスできる

(2)の条件を満たすものとして思いつくのは以下の2つぐらいです。

(2-A) 配列のようなもの
ランダムアクセスできるので中央にも即座にアクセスできる。

(2-B) ニ分木のようなもの
ニ分木で任意のノードの左右にぶら下がるデータ数がほぼ一致するなら二分探索に向いています。

線形リストはランダムアクセス性がありません。また先頭や末尾は管理できたとしても中央は管理しないのが普通です。よって中央値を求めるとすれば、リストの端から順番に探すしかなく、それをするぐらいなら目的の要素を最初から線形探索したほうが自然だと思います。

投稿 2017/11/22 00:16

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/11/27 22:44

    回答ありがとうございました。
    元々実装には向いておらず理解があやふやなままでは難しかったようです。

    キャンセル

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));
}

二分探索ですが、真ん中を見つける方法が、線形リストだと良い方法が浮かびませんでした。

投稿 2017/11/22 08:02

編集 2017/11/22 08:12

  • 回答の評価を上げる

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

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

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

  • 回答の評価を下げる

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

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

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

  • 2017/11/28 17:29 編集

    関連する参考情報という程度の位置づけですが:シンプルな単方向線形リストでの探索コストO(n)を緩和する「スキップリスト(skip list)」というデータ構造も存在します。計算量は二分探索のコストに近づきますが、ポインタを追加するため空間オーバーヘッドは増えてしまいます。

    https://ja.wikipedia.org/wiki/%E3%82%B9%E3%82%AD%E3%83%83%E3%83%97%E3%83%AA%E3%82%B9%E3%83%88

    キャンセル

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

ただいまの回答率

91.36%

関連した質問

  • 受付中

    HTMLPARSER タグ取り出し C++

    HTMLページの<p><p></p></p>に囲まれた文字を取り出したいのですが、うまくできません。下記のプログラムを基に取り出せるプログラムを作りたいです。よろしくお願いします。

  • 解決済

    c言語 リスト構造の検索

    アドレス帳の検索機能だけのプログラムを作っています。 作りたいプログラムは、  1,検索したい人の名前を入力する  2,事前に登録された情報の中から部分一致検索する 

  • 解決済

    オーバーフローします...

    前提・実現したいこと アルファベット順に表示したいです どうやったらアルファベット順に表示できますか? もし,このままでいいならオーバーフローを直して欲しいです... アル

  • 解決済

    C言語のエラー修正について

    コード #include <stdio.h> #define New (element) RealNew( & element ) #define InputInt( number

  • 解決済

    C言語で住所録管理ソフトを作成しているが、CSVファイルのデータを構造体にコピーする方法が分からない

    CSVファイルの中身は1行ごとに「名前,電話番号,住所」が記述されていてそれぞれの情報を構造体にコピーする形です。 線形リストで各個人のデータを管理したいと思っています。 構造

  • 受付中

    プログラムを見やすく改良したい

    正常に動くプルグラムを見やすく改良したい。 具体的に教えていただければありがたいです。セグメンテーションフォルトでベスト7まで表示して停止します。173行あたりだと思うのですが、よ

  • 解決済

    c言語 リスト構造について...

    前提・実現したいこと 最近C言語でリスト構造を勉強したので自己流でリスト構造のプログラムを作成したのですが正常に作動しません。どなたか解決法を教えてください。 説明不足だったの

  • 解決済

    リストを逆順に表示するための関数が、上手く機能しません。

    前提・実現したいこと Cでノードを使った線形リストを作っており、元からあるリストを逆順に表示するための関数を作っていました。 発生している問題・エラーメッセージ 逆順に表示する

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

  • C

    2525questions

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

  • ポインタ

    81questions

    ポインタはアドレスを用いてメモリに格納された値を"参照する"変数です。

  • トップ
  • Cに関する質問
  • 線形リストに対して二分探索をしたいのですが,リストから関数への値の渡し方が分かりません。