C言語で連結リストを書く初心者
C言語で連結リストを書くにあたって、初心者がつまずきやすいところ
ネットで探しても初心者向けにC言語の連結リストについて書いてある記事がなかなかみつからず、またPaizaには例によってC言語の解答例はありませんので、初心者の拙いコードではもしかしたら不備があるかもしれませんが一応書いておきます。
最初に結論から書きますと、自分がつまずいていたところを振り返るに、
node tmpとnode *tmpのどちらを使うべき場面か、きちんと選択出来ていなかった。連結リストで頻出する”連結し直す”という場面ではnode*型を使わないと、tmpのメンバであるnextやprevのポインタの値を書き換えることができない、ということになかなか気付けなかった。
ポインタに関する演算子（*, &, ->）の使い分けの理解が不十分だった
つまり、総じてポインタについての理解が甘かったからですね。
おそらく初心者はみんな同じようなところでつまずくと思うので、どなたかの参考になれば。
また、あらかじめ断っておきますが、チケットが足らず全ての問題で公式のテストケースを走らせたわけではないので、もしミスがあって通らなかったら、ごめんなさいね。
Paizaで習った方針で片方向連結リストを書く(あまりオススメではない)
CS50で連結リストの考え方は習ったものの、なかなか思った通りに書くことが出来ないでいた私は、Paizaのレベルアップ問題集にある連結リストメニューを参考に書いてみようと思ったのですが、ここに書いてあったのは私の知っていた連結リストと少し違う、変わったやり方をしていました。
Paizaの連結リストの概要についてはこちらをご覧ください。
(構造体を使わずに、「value配列」と、次のノードのインデックスを保持する「next_ptr 配列」の二つの配列を使うのはあまりにもアレなので、「ノード」を「value」と「next_ptr」の二つのメンバを持った構造体として暗黙的に読み換えています。
またnext_ptrについて、次のノードを「インデックス」で管理するのはC言語らしくなくて逆にやりにくいと思うので、「次のノードのポインタ」を記録する変数として置き換えています）
Paizaの連結リストのやり方をざっくり説明すると、
構造体ノードの配列を、十分な余裕を持ったサイズで作る（ここでは1024）。
配列の最初のノード[0]と最後のノード[1023]は番兵とする。
挿入するときは、配列の要素のうち、空である最小のインデックス番目の要素にいったんノードを置き（[empty_min_idx]）、そのうえで必要な各ノードのメンバnext_ptr を操作し、うまいこと連結を実現する。
必要な変数（backとempty_min_idx）を更新する。
最初は『え？これじゃあ必要な分だけnodeをmallocして、サイズを最小限に抑えるという連結リストのメリットを殺してんじゃん』と目を疑いましたが、
素人の足りない知識では、どういうやり方が一般的なのか、私の限られた知識では判断できかねる、というのが正直なところです（かくいう私はPaizaとCS50でしかプログラミングを習ったことがないのです）。
ですがまあ、この方法はこの方法で、初心者が練習をするにはイメージの掴みやすいやり方ではったということは確かです。
とやかく言うのはここまでにして、とりあえずいったん、Paiza先生の指示通りに書いてみましょう。
また、単に値を連結リストの末尾に追加するだけではつまらないので、ここではPaizaの片方向連結リスト実装編step5の、末尾にノードを追加したのち、先頭から連続するK個の要素を削除する問題をやってみます。
#include <stdio.h>
#define S 1024
typedef struct node{
int value;
struct node *next_ptr;
}node;
int main(void){
// リストを初期化する。
node list[S];
list[0].value = -1;
list[0].next_ptr = &list[S - 1];
list[S - 1].value = -1;
list[S - 1].next_ptr = NULL;
int back = 0;
int empty_min_idx = 1;
// N行の入力を取得し、各値をメンバに持つノードをリストの末尾に追加していく。
int N, K;
int value;
scanf("%d %d", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%d", &value);
list[empty_min_idx].value = value;
list[empty_min_idx].next_ptr = &list[S - 1];
list[back].next_ptr = &list[empty_min_idx];
back = empty_min_idx;
empty_min_idx++;
}
// 先頭からK個のノードを削除する。
node* del = &list[0];
for (int i = 0; i < K; i++) {
del = del->next_ptr;
}
list[0].next_ptr = del->next_ptr;
// 連結リストを先頭から出力する（番兵は除く）
for (node *travarse = list[0].next_ptr; travarse->next_ptr != NULL; travarse = travarse->next_ptr){
printf("%d\n", travarse->value);
}
}
CS50で習った方針で片方向連結リストを書く
CS50ではデータ構造の回で触れていました。が、本当に触れただけで、『あとは自力で練習すれば使いこなせそう』と確信できる程には扱ってくれませんでした。
とにかく私が最初に連結リストというのを教わったのがCS50だったので、Paizaのやり方を見て『え？これが連結リスト・・・？』という違和感がすごかったです。が、それは私がCS50贔屓のDavidファンだからなのでしょうか？
いずれにしろ、Paiza式の連結リストから変更した点は以下の通り。
Paizaで習った「サイズに余裕を持った配列を作る」から始まるやり方は納得が行かない。ノードを都度mallocして連結させる方法で書く。
よって「要素が入っていない最も小さいインデックス」である変数empty_min_idxは不要。
一方、Paizaで習って勉強になったのが、変数back（末尾の番兵を除く、最後の要素のインデックスを管理する変数）です。
これがあると、「末尾に挿入する」という処理を何度も行う場合、毎回末尾の挿入箇所までノードをループさせないで済むから楽なんですよね。値の更新さえ忘れなければ、ですけど。
ですからこれを参考にして、ここではポインタのbackを使って応用してみます。
解くのはPaizaの片方向連結リスト実装編step6の、末尾にノードを追加したあと、任意の位置にノードを挿入する問題です。
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int value;
struct node *next;
}node;
node* make_node(int value){
node *tmp = malloc(sizeof(node));
tmp->value = value;
tmp->next = NULL;
return tmp;
}
int main(void){
// リストを初期化する。
node *left = make_node(-1);
node *right = make_node(-1);
left->next = right;
node *back = left;
// N行の入力を取得し、各値をメンバにもつノードを作り、リストの末尾に追加する。
int N, P, X;
int value;
scanf("%d %d %d", &N, &P, &X);
node *tmp;
for (int i = 0; i < N; i++) {
scanf("%d", &value);
tmp = make_node(value);
tmp->next = right;
back->next = tmp;
back = tmp;
}
// 挿入する箇所の一つ前のノードのポインタを取得し、挿入する。
node *insert = left;
for (int i = 0; i < P - 1; i++) {
insert = insert->next;
}
tmp = make_node(X);
tmp->next = insert->next;
insert->next = tmp;
// 連結リストを先頭から出力する（番兵は除く）。
for (node *travarse = left->next; travarse->next != NULL; travarse = travarse->next){
printf("%d\n", travarse->value);
}
// メモリを解放する。
while(left != NULL){
tmp = left->next;
free(left);
left = tmp;
}
}
CS50で習った方針で双方向連結リストを書く
片方向連結リストと比べて変わる点は
構造体nodeのメンバにnode* prevが加わる。
連結するときの手順が若干複雑になる（まずは挿入するノードtmpのnextとprevの値を書き換える。次に挿入位置の前のノードのnextと、挿入位置の次のノードのprevを書き換えるのだが、場面によってどっちを先にやるか考える必要がある）。
末尾への挿入には番兵のprevを使って簡単に辿れるようになるので、ポインタbackが不要になる。
ここではPaizaの双方向リスト実装編step7の、末尾にノードを追加したのち、任意の区間のノードを削除する問題を題材に書いてみます。
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int value;
struct node *next;
struct node *prev;
}node;
node* make_node(int value){
node* tmp = malloc(sizeof(node));
if (tmp == NULL)
exit(1);
tmp->value = value;
tmp->next = NULL;
tmp->prev = NULL;
return tmp;
}
int main(void){
// リストを初期化する。
node *left = make_node(-1);
node *right = make_node(-1);
left->next = right;
right->prev = left;
// N行の入力を取得し、各値をメンバとするノードをリストの末尾に追加していく。
int N, L, R;
scanf("%d %d %d", &N, &L, &R);
int value;
node *tmp;
for (int i = 0; i < N; i++) {
scanf("%d", &value);
tmp = make_node(value);
tmp->next = right;
tmp->prev = right->prev;
right->prev->next = tmp;
right->prev = tmp;
}
// 削除する半開区間[L, R)について、Lの一つ前のノードをa、Rのノードをbとして、nextやprevの値を書き換える。
node *a, *b;
a = left;
for (int i = 0; i < L - 1; i++) {
a = a->next;
}
b = a;
for (int i = 0; i < R - L + 1; i++) {
b = b->next;
}
node *del = a->next;
a->next = b;
b->prev = a;
// 削除した区間のノードのメモリを解放する。
for (int i = 0; i < R - L; i++) {
tmp = del->next;
free(del);
del = tmp;
}
// 連結リストを先頭から出力する（番兵は除く）。
for(node *travarse = left->next; travarse->next != NULL; travarse = travarse->next){
printf("%d\n", travarse->value);
}
// メモリを解放する。
while(left != NULL){
tmp = left->next;
free(left);
left = tmp;
}
}
いまだよくわからない点、不安な点。
make_node関数のexit(1)の前に、うまいことfree()する書き方がよくわからない。ネットで調べたら「exit()のときはfree()をやらなくてもいい」という話を聞いたけど、真相は不明。
たとえばnode* tmpとnode *tmpみたいに、*の位置を書き分けることがあるのかよくわからん。CS50のshortでは「両者は少し意味が違う」みたいなことを言っていたような気がする。が、今のところ特に困る場面はないからスルーしている。
こんな感じで以上です。
データ構造楽しい。
語学勉強の費用の足しにさせていただきます_(._.)_