C言語教室 解答編 第21回 - と C言語あれこれ
今回は C++ の話も出てきて、ちょっとばかり難しく感じたかもしれないので、元になるコードを示したのですが、いかがでしょうか。
C言語教室 第21回 - 循環リスト
単方向リスト、双方向リスト、そして今回の循環リストとクドいほどリストでポインタと戦ったので、そろそろポインタの扱い方にも慣れてきたのではと思います。やはりポインタを扱う時は、コードだけでは見通しが悪いので、図を書いて見るのがオススメです。
さて、まだ課題を解いていないよという方は、ここから先を読まずにまず課題に挑戦してみてください。そして是非、結果を見せていただければ幸いです。
うっかり解答を見ないためのお話ですが、今回は雑談めいたものでお茶を濁します。
C言語も最初に覚えた時は、カーニハン＆リッチーのCの時代で「はじめてのC」なんていう本で覚えたものです。実行文を書く前に全ての宣言を済ませなければならなかったり、構造体の引き数渡しも出来なかったり、今のCとは違うところも多いものでした。コンパイラのエラーチェックも不親切で、わざわざ lint というツールを使って怪しい部分をあぶり出す必要がありました。他のコンパイラと違って、Cコンパイラはエラーが表示されずにバイナリが生成されたとしても、no error と表示されないのは、エラーが無かったのではなくて、コンパイラが見つけられなかっただけと言われる始末です。実際、書く人の練度が低かったこともあって、他の言語に比べても、出来上がったプログラムを走らせて無限ループに陥ったりメモリ保護違反で終了してしまうことも多かったのです。
それでもC言語が大切にされてきたのは、他の言語と違い、システムを記述することができるからだと思います。特にマイコン、パソコンの世界ではそれまでシステムはアセンブラを使わざる得なかったのが、C言語で記述できるようになったのは、大きな変革でした。ファームであるとかカーネルはもちろん、言語自身もだいたいはC言語で記述されています。
その時代からかれこれ40年も経過すれば、世の中はもちろんコンピュータの世界も大きく変わりました。C言語自身も何度もの改訂を繰り返し、昔は許されていた書き方も怒られるとまではいかなくても、相応しくない書き方となってしまった書き方もたくさんあります。そういった言語上の変化よりも大きな変化は、使えるメモリが大幅に増えてメモリを舐めるだけでも１Gとかになると、逐次探索をやっていたのでは時間がかかり過ぎるので、何らかの検索アルゴリズムをきちんと実装する必要が出てきたり、CPUがたくさんあるので、スレッドなどの並行処理を活用するのが日常になったことです。またメモリ管理もきめ細かにやっていられなくなってきたので、ガベージコレクションができるメモリ管理機構が無いとかなり辛いことになってきました。
今では普段使いはすっかり python の人になってしまったのですが、python を覚える時も最初はインタプリタのCのコードを読んで勉強したものです。お陰で細かな python の使いこなし(ラムダ式とか)は今でも不得意なところがあるのですが、オブジェクトの実装やメモリ管理とかだけは滅法詳しいです。でも最近、かなり書き換えられたので追いついていませんけど。
そろそろ課題に進みます。今回の課題は以下の内容です。
課題
1. リストの先頭に要素を追加する。
2. リストの最後に要素を追加する。
3. リストの先頭の要素を削除する。
4. リストの最後の要素を削除する。
課題で使うために以下のコードを示しておきました。
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int val;
struct node* next;
struct node* prev;
} Node;
typedef struct list {
struct node* top;
} List;
Node* create_node(int val) {
Node *node = (Node*)malloc(sizeof(Node));
node->val = val;
node->next = NULL;
node->prev = NULL;
return node;
}
void create_list(List* list) {
Node *dummy = (Node*)malloc(sizeof(Node));
dummy->next = dummy;
dummy->prev = dummy;
list->top = dummy;
}
void destroy_list(List* list) {
Node *current = list->top->next;
Node *next;
while (current != list->top) {
next = current->next;
free(current);
current = next;
}
free(list->top);
list->top = NULL;
}
void print_list(List* list) {
Node *current = list->top->next;
while (current != list->top) {
printf("%d ", current->val);
current = current->next;
}
printf("\n");
}これだけだと、テストするのに不便なので、以下の関数も使ってみてください。
typedef unsigned int uint;
void dump_list(List* list) {
printf("Top :%08x next:%08x prev:%08x\n",
(uint)list->top, (uint)list->top->next, (uint)list->top->prev);
Node *current = list->top->next;
while (current != list->top) {
printf("Node:%08x next:%08x prev:%08x val:%d\n",
(uint)current, (uint)current->next, (uint)current->prev, current->val);
current = current->next;
}
}これでリストの内部構造を見ることができます。課題に対応する関数を以下に示します。
void push_front(List* list, int val) {
Node *node = create_node(val);
node->next = list->top->next;
node->prev = list->top;
list->top->next->prev = node;
list->top->next = node;
}
void push_back(List* list, int val) {
Node *node = create_node(val);
node->next = list->top;
node->prev = list->top->prev;
list->top->prev->next = node;
list->top->prev = node;
}
void pop_front(List* list) {
Node *node = list->top->next;
if (node != list->top) {
list->top->next = node->next;
node->next->prev = list->top;
free(node);
}
}
void pop_back(List* list) {
Node *node = list->top->prev;
if (node != list->top) {
list->top->prev = node->prev;
node->prev->next = list->top;
free(node);
}
}この例でも戻り値はありません。もしかしたら追加は追加したノード、削除は削除したノードを返すのが良いかもしれません。その場合、freeは呼び出し元で行う必要が出るので、ノードの生成と削除は関数から出すことになりそうです。なお値を戻すのはエラー値を用意できないので、避けたほうが良さそうです。
演習は以下の内容です。
演習
1. リストに引き数で渡した値を持つノードのアドレスを返す関数を書きなさい。
2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数を書きなさい。その結果、渡したノードは挿入したノードの次のノードとなります。
3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数を書きなさい。なお番兵ノードを渡した場合は削除してはいけません。
それぞれの関数を示します。
Node* find_list(List* list, int val) {
Node* current = list->top->next;
while (current != list->top) {
if (current->val == val)
return current;
current = current->next;
}
return NULL;
}
void insert_node(Node *pos, int val) {
Node *new_node = create_node(val);
new_node->next = pos->next;
new_node->prev = pos;
pos->next->prev = new_node;
pos->next = new_node;
}
void erase_node(Node *pos) {
if (pos->next != pos) {
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
}
}挿入と削除は渡したノードがリストに含まれるかのチェックをさぼりました。もしかしたらチェックしたほうが良いのかもしれませんが、ループで大量に挿入することも多いと思うので、都度チェックした場合のコストが気になりました。もっとも一度のたくさん挿入する関数を書くという解決もありますね。
まだまだ工夫できるところもたくさんあると思うので、このコードを元に自分なりに工夫を試みてください。解答例のコードを貼っておきます。
今回も、Akio van der Meer さんから答案を提出して頂きました。
（答案提出）C言語教室 第21回 - 循環リスト（設計編）
（答案提出）C言語教室 第21回 - 循環リスト（コーディング編）
いよいよ一度に提出するのは大変になってきたかもしれませんね。設計は大事なので、まずそこでまとめるのは良いアイデアだと思います。
解答のコードを書いた時は、鼻歌まじりに描いた図をみながら、これとこれを入れ替えてと、図の矢印を順序に注意しながらコードにして、ダンプした結果がOKだったので、どうしてそうなるのかあまり自信があるわけでもありません。大丈夫かなぁ。
さてそれぞれの関数を追ってみます。
prepend_node は、いったん next を保存してから使っていますが、私は先に作ったばかりの node に代入してしまいまいした。その所為で list->top->next->prev に node を入れるというややこしい式になってしまったので、あまり読みやすくないです。このくらいはコンパイラがなんとかしてくれる範囲だと思うので、わかりやすさ優先で良いと思います。append_node も、ほぼ同じですね。
delete_first_node は、削除が行えたかを戻り値で教えてくれるのは、私のコードより気が利いています。delete_last_node も同じです。
演習の方にいきましょう。
search_node ですが、何番目の要素であるかを戻り値に返してくれるんですね。見つかったノードは引き数で渡した新しいリストの先頭にしてくれるのですか。見つかったノードを返すのに苦労してしまったようです。ここは素直に見つかったノードのアドレスを戻り値としてしまうのが無難だと思います。何番目であるかを知りたければ、ノードのアドレスを渡して何番目なのかを返す関数を別に用意しても良いとは思います。せっかく何番目なのかを数えたのに、数え直すのが勿体ないと思うのであれば、引き数に結果を返すための整数へのポインタを渡すことにして、この値が NULL でないときに返してあげれば良さそうです。
気になったのが、リスト構造体を結果を返すために使っているのですが、それが指すノードが別のリストに含まれる形になってしまうのはトラブルの元です。実はこの関数の仕様を考えた時に、同じ値を持つノードが複数あった場合、最初のノードしか返すことが出来ないので、リスト構造体ではなく探し始める最初のノードのアドレスを渡そうかとも考えていたのですが、その方が良かったのかなぁ。いずれにしても何番目かはあまり使わないです。
insert_node と delete_node ですが、リスト構造体を渡す形を取ると任意の位置にあるノードを操作することができません。リストに含まれるノードさえ渡せば、その前後にあるノードの情報は手に入るので挿入も削除も出来るはずです。演習の日本語の説明が不十分だったのかもしれません。今回はそれなりに難しいかなと思い、参考にするコードを載せたのですが、作るべき関数の仕様（プロトタイプ）も提示してしまったほうが良かったのかなぁ。
2023.4.26 追記
上記のコメントを反映させた答案をあらためて頂きました。
（答案再提出）C言語教室 第21回 - 循環リスト（アフターパーリィ編）
答案を出して終わりではなくて、ちゃんと適切な修正をしてきちんと課題を自分のモノにしていただくなんて、学生の鑑です。課題の文章での説明が不十分で、あれこれ悩ませてしまうこともあるようで、それは申し訳ありません。毎回いろいろな試行錯誤を試みられていて、こちらも勉強になります。
コードは一通り試されて入るようで、ところどころ値をマクロで定義しているので、いろいろ確認したのだろうと推測します。私もあまり細かなテストはサボっているのですが、そろそろテストの良し悪しなんかもやっておきたいですね。
もう少しだけポインタの嵐が続く予定ですが、辛抱強くお付き合いいただければ幸い。
(追記はここまで)
いやぁC言語でバリバリとプログラムを書いている人の頭の中は、結構、こういったポインタ操作とメモリを誰が押さえているのかで占められていたりします。渡す方と渡される方で型がズレるので、"&"をつけたり"*"を外したり、慣れていても忘れることがあります。そこはキッチリ値を確認する作業を怠ってはいけないところです。これに const が絡んだ暁には少しばかりC言語が嫌いになるところです。自分で作った関数で const を付けても、そこから更に呼び出す奥の方で使うライブラリ関数の引き数に const が無いために手前から const がつけられなくなって困ったことは数知れずです。ここで大丈夫と const を剥がしてしまうことが出来なくはないので、C言語のプログラムが不安定になるのは痛し痒しで、Rust に注目が集まるのは判らなくもないです。もっとも Rust も言語仕様というよりかはランタイムの実装で苦しんでいるので、全てが解決するわけではないなぁと思いますけど。
2023.4.26 追記
AyumiKatayama さん からも答案を提出していただきました。少々、遅くなろうと構いませんので、是非ともお付き合いの程を。
C言語教室 第21回 - 循環リスト（回答提出）
循環リストの特徴を補足して頂いてありがとうございます。駆け足で説明を流してしまうこともあると思うので、判りにくいところがあればどんどん突っ込んでくださいませ。
今回の課題は少し手強いと思ったのと、細かく日本語で説明するほうが面倒だと思ったので、一部のコードを載せましたが、もちろん、自分の好みで改変して頂いて構いません。関数の分け方や引き数の選択、名前の付け方など、いろいろな流儀があります。まあ名前に関しては、C言語では名前空間が殆ど無いので、簡単にするほど衝突は避けられませんね。私のコードもあくまで例であって、これだけが正解ということは決してありません。
かなりガッツリとツールを使ったときのようなテストコードを書かれているのが、プロの技とお見受けします。最近は仕事のコードは書いていませんし、テストはいったんコードを仕上げて忘れた頃になってあらためて行うようにしていたので（先入観をいったん捨てないとバグを見つけにくい）、ザーと書く段階ではサボりまくりです。
ここのところ教室で使うコードもややこしく長くなってきたので、集中力が持たずに時間がかかるようになっています。コードを書き出すと脳みそがだんだん CPU になってきて、頭の中にメモリの状態が見えるようになってくるのですが、いちいち可視化しないと辛い今日このごろです。今後ともよろしくお願いします。
(追記はここまで)
ヘッダ画像は、いらすとや さんより
https://www.irasutoya.com/2020/04/blog-post_243.html
この記事が気に入ったらサポートをしてみませんか？