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

Question

###前提・実現したいこと
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ファイルは昇順で並んでいるのですが，このプログラムだと表示するときに降順で表示されてしまいます．何故でしょうか？

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

Comments

[Cstdy_sun8]

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

Answer 2

さらに，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));
}

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

Comments

[yohhoy]

関連する参考情報という程度の位置づけですが：シンプルな単方向線形リストでの探索コスト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