どうも〜、シュモクザメです。
以前、線形リストの追加と削除の関数の記事を書かせていただきました。
今回はその発展で、線形リスト内を探索する関数を作ってみます。
全体のコードも貼ってあるのでぜひ参考にしてください！！
まずは軽〜く線形リストについて解説
線形リストっていうのは以下の図のような構造のものです。
それぞれのノードは値と次のノードをさすためのポインタを持っています。（これは構造体で実現する。）
まあここら辺は前回の記事で解説しているのでわからない方はぜひご覧あれ⬆︎
コードの実装
ここから少し配列と構造体の違いについて考えながらコードを実装していきます。
配列のメリット
まず配列とリストの大きな違いの一つとして、
要素（ノード）を番号で管理しているかいないかが挙げられます。
何が問題かっていうとfor文です。
よく配列を扱う時にみるfor文は以下のような感じです。
for(int i=0; i<N; i++){
v[i] = i;
}毎度のように
for(int i=0; i<N; i++)のように書いていますが、
これは配列の要素が連続する整数の添字で管理しているから実現できるんですよね。
for文に限らず、操作したい要素の添字番号さえ分かればダイレクトに操作できるのも配列の強みかも。
線形リストの操作にもfor文が使える!!
じゃあリストにはfor文が使えないの？？
いえいえ、もちろん使えます。
ただ配列のように整数を定義してインクリメントして、、というやり方は微妙ですね。
なぜならリストは具体的な長さが決まっていないからです。
てことで他の方法を考えましょう。
そもそもfor文の引数は
for(①; ②; ③)
- ループに入る前の、最初に行う処理
- ループの継続条件
- 一つのループが終わる度に行う処理
という風に書くルールがあります。
脳死でfor(int i=0; i<N; i++)としてたひとも多いのではないのでしょうか？
必ずしもこういう風に書く必要はないんですね。
なのでこの引数のルールを考慮してリスト用に作り替えましょう。
リストを探索する関数
とりあえずコードです。
typedef struct list{
int date;
struct list *next;
}list;
void list_search(list *head, int value){
int flag = 0;
for(list *p=head; p->next!=NULL; p=p->next){
if(p->date==value){
printf("%d を見つけました\n",value);
flag = 1;
break;
}
}
if(flag==0){
printf("%d を見つけられませんでした\n",value);
}
}まずリストのノードは上部に記述した構造体listとします。（よくわからない人は前回の記事みてね）
関数list_searchが今回の探索の関数。
引数のlist *head は探索したいリストの先頭を指すポインタで、int valueは探索したい値です。
難しいのはfor文ですね。じっくりやっていきましょう。
for文の第一引数
配列ではここをint i=0などとしがちですが、これは先頭から始めるよって意味ですよね。
list *p = headとしてます
今回はちょうど仮引数でheadを受け取っているのでこれを利用しましょう。
list *pでノードのポインタ型を作ってそこにheadの指している場所を代入すればおkです。
for文の第二引数
配列ではi<Nなどとしがちな部分ですね。ここは継続条件なので今回は
p->next != NULLとしてます。
この文の意味は、
pが指している要素の次の要素がNULL出ない限り、ループを継続するよって感じですね。
これはリストの最後の要素がNULLを指すことを利用してます。
つまりNULLではない=次の要素があるので継続できるってことです。
for文の第三引数
配列ではi++などとしがちな部分。つまり次の要素(ノード)に焦点を変える処理を入れたいってことですね。今回は、
p = p->nextとしています。
この文の意味は、
pをpが今指している要素の次の要素に指すようにするよって感じです。
まあいわゆるつなぎ変えですね。
このようなイメージです。⬇︎
for文の中身
あとは簡単ですね。
ループの中でif文で、そのノードの持つ値が求めてる値かどうか判定しているだけです。
見つかった場合はbreakを利用してループから抜け出してます。
また見つからなかった時用にflagで管理してます。
まとめ
ポインタを用いたfor文てやっぱり最初はよくわからないですよね。
でも使えたらかっこいいし、
大学の課題などでポインタを用いたfor文を含めたコードで提出したらTAや教授に
「こいつ、、、理解ってるな、、」
って思われるかも。
ではまた〜
全体のコード
#include <stdio.h>
#include <stdlib.h>
typedef struct list{
int date;
struct list *next;
}list;
void list_search(list *head, int value){
int flag = 0;
for(list *p=head; p->next!=NULL; p=p->next){
if(p->date==value){
printf("%d を見つけました\n",value);
flag = 1;
break;
}
}
if(flag==0){
printf("%d を見つけられませんでした\n",value);
}
}
int main(int argc, const char * argv[]) {
list A,B,C,D,E;
A.date = 1;
B.date = 3;
C.date = 5;
D.date = 7;
E.date = 9;
list *head;
head = &A;
A.next = &B;
B.next = &C;
C.next = &D;
D.next = &E;
E.next = NULL;
list_search(head, 5);
list_search(head, 2);
return 0;
}
コメント