第１０回 線型リスト・その２（６／１２）

今日のキーワード

• サーチ
• インサート

■ 探索

□ 例題１

正の値である間、または、リストのノードが無くなるまで、リストを先頭から順に辿り、正数の和を求める関数 int sum_positive(Node *root); を作れ。⇒ list1001.c

ただし、push 操作でリストに値を追加しているので、入力した10個の数は、入力順とは逆順でリストに格納されていることに注意せよ。

実行例： 1 2 3 4 -1 10 20 30 40 50 と入力すると、150 が出力される。

□ 演習１

リスト内の値のうち、指定する値より大きい値であり、かつ、先頭から見て最初に出現するものを返す関数 int find_first_larger(Node *root, int t); を作成せよ。なお、指定値より大きい値が存在しない場合は、指定値を返せ。⇒ prac1001.c

■ 挿入(insert)

リストの途中に新しいノードを追加することを挿入という。入力する値がリスト内の値より大きいならば次ノードを辿り、そうでないならば、その位置に入力する値を持つノードを追加する。こうすることで、昇順にソートされたリストが作られる。

ｖｏｉｄ　ｌｉｓｔ＿ｉｎｓｅｒｔ（Ｎｏｄｅ　＊ｒｏｏｔ，ｉｎｔ　ｎｕｍ）｛
　　Ｎｏｄｅ　＊ｐ，＊ｑ；

　　ｆｏｒ（　ｐ＝ｒｏｏｔ；　（ｐ−＞ｎｅｘｔ　！＝　ＮＵＬＬ）＆＆
　　　　　　　　　　　　　　　　　（ｐ−＞ｎｅｘｔ−＞ｖａｌ　＜　ｎｕｍ）；　ｐ＝ｐ−＞ｎｅｘｔ）｛｝
　　ｑ　＝　ｌｉｓｔ＿ｍａｋｅ＿ｎｏｄｅ（ｎｕｍ）；
　　ｑ−＞ｎｅｘｔ　＝　ｐ−＞ｎｅｘｔ
　　ｐ−＞ｎｅｘｔ　＝　ｑ；
｝

□演習２

１０個の整数を入力し、リストに蓄え、最後に全てを表示するプログラムを、上記の関数 list_insert を用いて作成せよ。list_push を用いる場合との違いを確認せよ。⇒prac1002.c

■ 宿題

以下のメイン関数を実行した場合、どのようにノードが作られるかを、処理過程に沿って作図し、説明せよ。ただし、先週のプリントにあった10コマの図を参考に list_push, list_insert の関数内の処理ステップまで分解し説明すること。⇒prac1003.c

ｍａｉｎ（）｛
　　Ｎｏｄｅ　ｒｏｏｔ；

　　ｒｏｏｔ．ｎｅｘｔ　＝　ＮＵＬＬ；
　　ｌｉｓｔ＿ｉｎｓｅｒｔ（＆ｒｏｏｔ，７）；
　　ｌｉｓｔ＿ｐｕｓｈ（＆ｒｏｏｔ，５）；
　　ｌｉｓｔ＿ｉｎｓｅｒｔ（＆ｒｏｏｔ，８）；
　　ｌｉｓｔ＿ｉｎｓｅｒｔ（＆ｒｏｏｔ，４）；
　　ｌｉｓｔ＿ｉｎｓｅｒｔ（＆ｒｏｏｔ，６）；
　　ｌｉｓｔ＿ｐｒｉｎｔ（＆ｒｏｏｔ）；
｝

※ 普通は、insert 操作によりリストを作っているときに、push 操作は行わない。今回は練習問題なので、insert 操作と push 操作が混在している。