【リスト】検索について

Question

検索も、前回のコードを利用させていただき書いたのですが、リストの検索って以下のようなコードになるんでしょうか。まったくの見当ちがいでしょうか。利用したところ以外、へたくそです、

前回のコード

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

struct SUUJI{
    int suuji;
    struct SUUJI *next;
};

int main(void){


struct SUUJI *top1;
struct SUUJI *top2;
struct SUUJI *top3;
struct SUUJI *top4;
struct SUUJI *top5;
struct SUUJI *top6;
	
top1=(struct SUUJI *)malloc(sizeof(struct SUUJI));
top2=(struct SUUJI *)malloc(sizeof(struct SUUJI));
top3=(struct SUUJI *)malloc(sizeof(struct SUUJI));
top4=(struct SUUJI *)malloc(sizeof(struct SUUJI));
top5=(struct SUUJI *)malloc(sizeof(struct SUUJI));
top6=(struct SUUJI *)malloc(sizeof(struct SUUJI));
	
top1->suuji=1;
top1->next=top2;

top2->suuji=2;
top2->next=top3;
	
top3->suuji=3;
top3->next=top4;
	
top4->suuji=5;
top4->next=top5;
	
top5->suuji=5;  //数字が同じものを用意しました。
top5->next=top6;	

top6->suuji=6; 

top6->next=NULL;

	
for(struct SUUJI *p=top1; p!=NULL; p=p->next){

	printf("%d->",p->suuji);

}

int count=0;
int n;
  printf("\n1kara5de kennsakutiwonyuuryokusitekudasai\n");
  scanf("%d",&n);

for(struct SUUJI *p=top1; p!=NULL; p=p->next){
  if(p->suuji==n){
	
printf("%dga%dbanmedeixtutishimashita",n,count);}

  else if( n<1||5<n){printf("1kara5wonyuuryokusitekudasai\n");return -1;}

else {}

count=count+1;
}


printf("\n");

return 0;
}

1あってましたら１から5以外の数値を入力したときに、continue;かなんかで繰り返したかったけど、思いうかびませんでした。
2あと同じ数が複数個あったらどちらも抽出したいのですがどうしたらいいですか。（2はNULLのおかげでできてました）
3ノードの追加、削除のときでなくてもいいけど
検索範囲（１から5と想定してしまっている）追記、
一番大きい数と一番小さい数を見つけたいです。

Comments

[dodox86]

> リストの検索って以下のようなコードになるんでしょうか。まったくの見当ちがいでしょうか。

回答の着地点が分かりづらいようです。「検索」と言っても、要は質問者であるtxtyさんが見つけたいものを見つけられるコードなのであれば、それがtxtyさんにとって「検索」なのではないですか。まぁ、それは置いておいても、提示のコードはインデントが崩れまくっていたり、読みにくいのは確かです。また、いきなり「前回のコード」と書かれても、この質問を初めて読んだ方には分かりません。単なる質問文への指摘のみで恐縮ですが。

[txty]

リンク張りました。インデントは育ちがよくないので直せないと思ってもらうと幸いです。あと、どんな探索がいいかというととりあえず、これだけじゃわからないかもしれませんが、線形探索がしたいです。

[BeatStar]

『インデント』というのは、『段落』です。

if(p->suuji==n){

の部分のように、半角スペース(またはTabキー)でやるやつです。

というか、『ggりましょう』です。

プロでも調べながらやっています。

『IT プログラミング インデント とは』で検索するだけでもかなりヒットします。

検索力は必須です。

[txty]

BeatStarさん＞はい。では少しずつでも直します。

[dodox86]

> どんな探索がいいかというととりあえず、これだけじゃわからないかもしれませんが、線形探索がしたいです。

残念ながら指摘したことが伝わっていない感が漂いますが（まぁ、文だけでは伝わることに限界あるので仕方無いですね）、ご提示のリストは単方向リスト（頭から次へ、次へと一方向にしか進めない）ので、泣いても笑ってもひとつずつ辿る線形探索しかできません。と言うか、自然と線形探索しているかたちです。具体的な、参考になるコードが見たいのでしょうかね。

[txty]

dodoxさん＞線形探索しかできないのですか。驚きました。
はい、そうです。同意。

[BeatStar]

コードを学ぶよりも、『概念』を先に理解した方がよさそう。
配列で arr[1] とかみたいにアクセスできるのは、『メモリ上にその順番で配置されているから』的な理由です。
リスト構造はイメージとしては並んでいますが、ポインタを使うことからもわかる通り、
『順番に並んでいることは必須ではない』です。そのためにポインタで表現しているのです。

そして、arr[3] とかみたいな、『ランダムアクセス』は順番に並んでいる場合しかできません。
リスト構造はメモリ上ではバラバラに配置されている可能性もあるので、『ランダムアクセス』はできません。

バイナリサーチのようにリニアサーチ以外をやろうとすると、メモリ上に整列している状態とか、
ソート済みである事とかみたいな条件が付きます。(アルゴリズムによって変わる)

だからリスト構造はどうしてもリニアサーチ(線形探索)しかできません。

よって、リスト構造での検索は O(n) だと言われています。

詳しくは『計算量』をキーワードにして、『計算量 とは』とかで検索してみてください。

[txty]

コメントありがとうございます。
道はけわしいのですね。わかりました。
計算量とはでぐぐってみます。どうすればいいかわからなかったので助かります。

[BeatStar]

私は趣味でやっているので、その『どうすればいいかわからなかった』のは理解できます。
なのでちょっとアドバイスを。

まず、『データ構造とアルゴリズム』とかで検索して、それでヒットした記事を数件読みます。
そしてそこに出てきた新しいキーワード(たとえば『計算量』とか)を使って再度調べます。
これをひたすら繰り返します。

一つのサイト(あるいは書籍)では足りない場合もあるので副読本的な立ち位置でいろんなサイトや書籍を読む。

あとは、定義とかが分からない場合は『○○とは』とかのようにして、
実装レベルの内容なら言語名を付けて調べる。

例:『C言語 ファイル 書き込み』

そういう風に関係のある情報をひらすら読み漁り、自分の頭で考えるとある程度理解できるようになります。
後は実際にコードを書いてロジックを追うとか。

[txty]

何回かで読みとれるかわかりませんが繰り返し読ませていただきます。

[kaina]

txtyさん、あなた本当に本気で問題解決しようと思っていないでしょ。
本気で思っていれば「インデントは育ちがよくないので直せないと思ってもらうと幸いです。」なんて
ふざけたこと書けないはずです。
たかだかインデント程度を揃えることが出来ないとかふざけるのもいい下限にしたほうがいいんじゃないですか？
なんでもいいのでIDE（統合開発環境）を導入すればインデントなんてコマンド一つで揃えることが出来ます。
それをやらないまま何度も指摘されたことをそのまま放置して、時間の無駄だから止めたほうがいいんじゃないですか？
どうせそんなことが出来るとは知らなかったとか言ってくると思うので、先に言いますが
知らなければ調べろ、自分で物事を解決しようという意思が無い限り今あなたがやっていることは
時間の無駄です。

[dodox86]

ここ直近の繰り返される質問編集履歴を見て：
もっと文章を考えてから投稿しましょうよ。なぜ、回答が離れていくようなことをするのか。
3つも4つもご自身のやりたいことを書いても、（私を含め）逐一細かく回答する気にはなれないと思います。（現に、私も当初は回答しようかと思っていましたが、止めました）
低評価を入れたのは私ではありませんが、そんなところが評価されているのだと思います。
すみませんが私からは以上です。

[txty]

>kainaさん
過去に一度直そうと思ってぐぐって調べたんですが直せませんでした。
dodoxさん＞特になにもないです。ただ直す場所を見つけたら直した方がいいかと思いました。

[txty]

間違えてるかもしれないがやりたかったのはたぶんこう。

int count=0;

int n=0;

printf("\n1kara6de kennsakutiwonyuuryokusitekudasai\n");

scanf("%d",&n);

for(struct SUUJI *p=top1; p!=NULL; p=p->next){

if(p->suuji==n){

printf("%dga%dbanmedeixtutishimashita",n,count);

}//if

count=count+1;

if( n<1||6<n){

printf("ixtuchishimasen/n");

scanf("%d",&n);

continue;

}//if

}//for

printf("\n");

return 0;
}

ああ、ちょっと間違えた。範囲外押したあと、１とか押すと間違える。

[dodox86]

先のコメントで「私からは以上です。」と書いた上で大きなお世話なのでしょうが、気の毒に思えるので指摘します。本人が「間違えているかもしれなく、多分こう」と思えるレベルのコードを提示しても高い可能性で他人に伝わりません。 1 ≦ n ≦ 6の範囲を意識するのは本来は検索処理を呼びだす方なのではないでしょうか。または、そのリスト中にその値があるかどうか、ですよね。continueはループを「続行」します。for文の中でscanf～continueしても、ループは続きから行われる訳で、先頭からまた回り始める訳ではありません。それはtxtyさんの望む動作なのか、ということです。txtyさん自身がそれで良いというのであれば、それで良いのでしょう。

ですが、失礼ながら、質問が混迷を極めつつあるので誰もが回答しづらいのだと思います。あえて書きませんが、以前の質問より指摘されたことを振り返ってみてください。

[txty]

アクティブからはずれているから指摘してもらって大丈夫です。アドバイス読みました。そのうえで再度、聞いてしまうのですが..仕様の実現は可能なのでしょうか。仕様では１から６までを検索範囲にする。forループでnullまでを一括検索する、数が範囲外だったら、再度入力を求めるなのですがcontinueを使うとforループのしたに戻るのですが、scanfがなんかうまいこといかないのです。また、ループが６回しか入力できないので入力した数が範囲内のときはいいのですが範囲外を入力してそのあとcontinueで１から順に出力されないのです。アドレスをたどってるから不可能なのでしょうか。すいません。誤記があるかもしれませんがよろしくお願いします。

[dodox86]

> 仕様の実現は可能なのでしょうか。仕様では

それはtxtyさんが独自にやりたいことですね。単方向リストの検索とはあまり関係なく、単にプログラムのロジック／フローの問題です。その程度であれば、普通に「可能」です。
例えば以下のようなかんじのフローでできるはずです。（あくまで例えであり、疑似コードですが）
ループ1 {
ループ2 {
scanfで値を入力
if (入力された値が1以上5以下) {
ループ2をbreakで抜ける
}
ループ2の先頭へ戻る
}

入力された値を探すよう、リストを辿る。（つまり検索）
検索したものが見つかれば何かする

ループ1の先頭に戻る
}

scanfでの入力がうまくいかないと言うのであれば、scanfを使うことでの特有の問題かもしれません。teratailでもたびたび質問回答が挙がっています。ですが、それは今回の本質ではありません。

失礼を承知で指摘させてもらうと、リストの要素の検索以前にプログラミングのロジックの組み方（考え方）につたなさを感じます。まず頭の中で考えてペンと紙で表現できるようでないと、コードに書けません。書いているとしても恐らくそれはコードと意思が一致してない、間違い、と言うか思い込みです。そんなことが「かもしれない。たぶん」などの言葉遣いに表れています。コードは自分の頭の中の意思（やること）を反映したものです。

[txty]

コメントありがとうございます。紙などに書いてもう少し考えてみます。どうしてもできなかったら再度質問するかもしれません。その際には、よろしくお願いします。

[txty]

すいません。疑似コードについて教えてもらえませんか。３ｈ程試したのですができなくてちょっと落ち着かないです。後生で教えてもらえませんか。
すぐできないならいつでもいいのですが駄目でしょうか

[txty]

一応仕様どうりできたと思う。たしかにできました。付き合っていただきありがとうございました。
入力する数字の４だけできてない。でももう自分では無理なのでクローズします。
追記　追記：指定した範囲をwhile(n<-30||n>10){とかすると除外するループにはいれません。（どうしたらいいんだ）できてなかった。

int count=0;
int n=0;

while(n<1||n>6){

printf("1kara6wonnyuuryokusitekudasai\n");

scanf("%d",&n);
}

for(struct SUUJI *p=top1; p!=NULL; p=p->next){

if(p->suuji==n)
{

printf("%dga%dbanmedeixtutishimashita",n,count);
}//if

count=count+1;

}

printf("\n");

return 0;
}

Answer 1

なんか、本当にかわいそうになってきたので、真面目に回答します。(最初は不真面目っていうことでもないが)

---

まず、リスト構造云々の前に、『プログラムの考え方』を学ぶべきです。

プログラムは『こう書けばこう動く』っていうものでは無いです。

『プログラムは魔法でもなんでもなく、人間が現実世界でやっていることを逐一指示されながら処理しているだけの代物である』です。

つまり、言い換えると、『現実世界で我々がやっている手順を独自の言語(C言語等)に書き下したもの』です。

なので、『現実世界でならどうするか』を考えてみてください。

まず、リスト構造だと大げさになるので、とりあえず、マインドセットをどうにかするために、
サンプルを簡略化しましょうか。

リスト構造から最小値および最大値を取り出す……ではなく、『配列から最小値および最大値を取り出す』と考えてみましょうか。

(これが出来ないとリスト構造なんて無理です)

えーっと、まず、これを言い換えた、現実世界での例だと、

ホワイトボードに { 1, 4, 10, 2, 5 ... } のように数字が書かれている。
この中での最小値と最大値を計算せよ。

という感じの依頼ですね。

質問者さんはどのようにしますか?

私なら、ひとつずつ見ていって、最大値と最小値を更新していく。ですね。

たとえばホワイトボードの余白に 最小値: ?, 最大値: ? の状態でやる。

でも最小値って、1 とか 0 とか -1 とかのような小さい値になるので、初期値はデカすぎる値にしておきましょうか。例えば 千とか。

最大値は小さい値ではなく、逆に大きい値なので、負の数のみとかでない限りは 0 以上なので
初期値は 0 としておきます。
もし負の数のみのデータの並びであれば マイナス千 とかみたいなのが望ましいかなぁ。
(仕様による)

// ホワイトボード

{ 20, 4, 2, 6, 10, 11, 3, 7 }

最小値: 1000
最大値: 0

で、一個目の 20 を チェックします。
最小値, 最大値ともにまだやっていないので暫定一位としておきます。(20 を)

一個目はチェック済みなのでわかりやすくするために "-" で伏せるとします。

最小値の暫定一位は 1000 です。
で、現在位置(一個目)の値は 1 なので

最小値: 20 < 1000 → 満たす → 更新
最大値: 20 > 0 → 満たす → 更新

ですね。

// ホワイトボード

{ -, 4, 2, 6, 10, 11, 3, 7 }

最小値: 20
最大値: 20

で、二個目の 4 も同様にやると、

現在の最小値と最大値それぞれ見ると、

最小値: 4 < 20 → 満たす → 更新
最大値: 4 > 20 → 満たさない → 更新せず

なので、

// ホワイトボード

{ -, -, 2, 6, 10, 11, 3, 7 }

最小値: 4
最大値: 20

となるはずです。

これを最後の 7 (八個目) までやると、

// ホワイトボード

{ -, -, -, -, -, -, -, - }

最小値: 2
最大値: 20

のようになるはずです。

これをコードにするだけです。

ホワイトボードの余白に書いた、一時的な最大値やら最小値は、『変数』で出来そうです。

8回処理しているのはforとかで出来そうですね。

現在の最小値と比較してさらに小さいかどうかを調べる…系はifで出来そうですね。

後はこれを組み合わせてやるだけです。

そして、今回のリスト構造であれば、ポインタをたどって行きながらチェックする……みたいになるはずです。

もし追加や削除等の編集時であれば、

編集時に if文で 現在の最小値と比較して……とかみたいな感じでやります。
(削除の場合はちょっと工夫する必要があるが、発想は同じ)

Comments

[BeatStar]

あ、ちなみに、計算ミスしている可能性もあるので、そこはご自分で読み替えてください。

[txty]

ありがとうございます。参考にして勉強します。

Answer 2

追記：指定した範囲をwhile(n<-30||n>10){とかすると除外するループにはいれません。（どうしたらいいんだ）

3以外仕様どうりにできたと思うのでクローズします。入力する数字の４だけできてない。

後、数字以外を想定してなかった。でももう自分では無理なのでクローズします。

int count=0;
int n=0;

while(n<1||n>6){

printf("1kara6wonnyuuryokusitekudasai\n");

scanf("%d",&n);
}

for(struct SUUJI *p=top1; p!=NULL; p=p->next){


if(p->suuji==n)
{



printf("%dga%dbanmedeixtutishimashita",n,count);
}//if


count=count+1;

}



printf("\n");

return 0;
}