（答案提出）C言語教室 第21回 - 循環リスト（コーディング編）

前回の記事（設計編）に引き続いて、今回はいよいよコーディング編です。

「こいつの次のnodeの、前を指すポインタは、、、」

あかん、頭がこんがらがってきた。
前回、絵を描いていたのがとても役に立つ。
ときどき絵を見返しつつ、コーディングしていきます。

循環リストとなり、両端が無くなることで、随分と処理ロジックが簡素化されるのが実感できた。番兵くんがとても良い仕事をしてくれる。

相変わらず、わたしを一番悩ませるのはポインタの扱い。
プログラムのロジックを考えるよりも、こちらで悩んでいる方が長いかも。
やれやれ。

＊冒頭の写真は、福井県敦賀市の気比神宮の池の鯉。
池の中をぐるぐる泳ぎ回る（循環する）イメージで採用しました。

課題

番兵ノードを用い循環リストで実装した双方向リストを使って、以下のリスト処理を行う関数を書きなさい。
1. リストの先頭に要素を追加する。
2. リストの最後に要素を追加する。
3. リストの先頭の要素を削除する。
4. リストの最後の要素を削除する。

実装の方法は、いろいろあると思いますが、リストに格納する型は整数とし、以下のコードを元に書いてください。リスト構造体が指すノードが番兵ノードとします。

https://note.com/kazushinakamura/n/n6b9e768054cd?magazine_key=m07bb4da8df3e

課題1. リストの先頭に要素を追加する。

//lesson21-1. リストの先頭に要素を追加する。
void prepend_node(List * list_head, int val) {
  Node *node_new = create_node(val);
  Node *node_next = list_head->top->next;

  list_head->top->next = node_new;
  node_new->prev = list_head->top;
  node_new->next = node_next; 
  node_next->prev = node_new;

  printf("new node with value %d was prepended.\n", val);
}

create_node()関数を使って新たに生成したnode_newが、これから追加するnode。node_nextは、それまで番兵node（list_head->top）の次に居た（即ち先頭の）nodeです。番兵nodeとnode_nextの間に、node_newを追加します。

課題2. リストの最後に要素を追加する。

//lesson21-2. リストの最後に要素を追加する。
void append_node(List * list_head, int val) {
  Node *node_new = create_node(val);
  Node *node_prev = list_head->top->prev;

  list_head->top->prev = node_new;
  node_new->next = list_head->top;
  node_new->prev = node_prev; 
  node_prev->next = node_new;

  printf("new node with value %d was appended.\n", val);
}

create_node()関数を使って新たに生成したnode_newが、これから追加するnode。node_prevは、それまで番兵node（list_head->top）の前に居た（即ち最後尾の）nodeです。番兵nodeとnode_prevの間に、node_newを追加します。

課題3. リストの先頭の要素を削除する。

//lesson21-3. リストの先頭の要素を削除する。
int delete_first_node(List * list_head) {
  Node *node_del = list_head->top->next;
  if (node_del == list_head->top) return -1;

  Node *node_next = node_del->next;
  list_head->top->next = node_next;
  node_next->prev = list_head->top;

  printf("fisrt node with value %d was deleted.\n", node_del->val);

  free(node_del);
  return 0;
}

番兵nodeの次（list_head->top->next）をセットしたnode_delと、番兵node（list_head->top）が一致するということは、リスト中に番兵しか居なかったということなので、何も削除せずに-1を返します。正常終了なら0を返します。

node_nextは、それまでnode_delの次に居たnodeです。番兵nodeと、node_nextを連結して、その間のnode_delを解放します。

課題4. リストの最後の要素を削除する。

//lesson21-4. リストの最後の要素を削除する。
int delete_last_node(List * list_head) {
  Node *node_del = list_head->top->prev;
  if (node_del == list_head->top) return -1;

  Node *node_prev = node_del->prev;
  list_head->top->prev = node_prev;
  node_prev->next = list_head->top;

  printf("last node with value %d was deleted.\n", node_del->val);

  free(node_del);
  return 0;
}

番兵nodeの前（list_head->top->prev）をセットしたnode_delと、番兵node（list_head->top）が一致するということは、リスト中に番兵しか居なかったということなので、何も削除せずに-1を返します。正常終了なら0を返します。

node_prevは、それまでnode_delの前に居たnodeです。番兵nodeと、node_prevを連結して、その間のnode_delを解放します。

演習

1. リストに引き数で渡した値を持つノードのアドレスを返す関数を書きなさい。
2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数を書きなさい。その結果、渡したノードは挿入したノードの次のノードとなります。
3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数を書きなさい。なお番兵ノードを渡した場合は削除してはいけません。

https://note.com/kazushinakamura/n/n6b9e768054cd?magazine_key=m07bb4da8df3e

検索した時に無限ループを回避するためにも、番兵nodeの定義は大事なのでそのまま残しておく必要があります。これをList list_headと定義しましょう。

一方、ある条件を満たすnodeへのポインタの定義も必要となってくるようです。こちらはList list_pointerと定義して、番兵とは区別することとします。

演習1. リストに引き数で渡した値を持つノードのアドレスを返す関数

//exercise21-1. リストに引き数で渡した値を持つノードのアドレスを返す関数
int search_node(List *list_head, List *list_pointer, int val) {
  Node *current_node = list_head->top->next;
  int seq = 1;

  while (current_node != list_head->top) {
    if (current_node->val == val) {
      list_pointer->top = current_node;
      return seq;
    }
    seq++;
    current_node = current_node->next;
  }

  list_pointer->top = list_head->top;
  return -1;
}

指定された値を持つnodeが最初から何番目なのかを返します。
番兵nodeの次（list_head->top->next）から、番兵nodeに至るまでの間、指定された値を持つnodeを探します。同時に何番目かをカウントします。

見つかれば、何番目のnodeであったかを返し、見つからなければ、ポインタを番兵nodeにセットして、−1を返します。

※ （リスト中の何番目かをカウントする時、０から始めるか１から始めるか迷いましたが、C言語の作法的にどうなんでしょうね？私的には、番兵が０番目、その次から１番目と考えました。）

演習2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数

//exercise21-2. リストに含まれるノードへのポインタと値を引き数とし、渡したノードの位置に渡した値のノードを挿入する関数
void insert_node(List *list_pointer, int val) {
  Node *node_new = create_node(val);
  Node *node_next = list_pointer->top->next;

  list_pointer->top->next = node_new;
  node_new->prev = list_pointer->top;
  node_new->next = node_next; 
  node_next->prev = node_new;
}

create_node()関数を使って新たに生成したnode_newが、これから追加するnode。node_nextは、指定したnodeの次のnode（list_pointer->top->next）です。list_pointer->topと、node_nextの間に、node_newを追加します。

演習3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数

//exercise21-3. リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数
int delete_specified_node(List *list_head, List *list_pointer) {
  Node *node_del = list_pointer->top;
  if (node_del == list_head->top) return -1;

  Node *node_next = node_del->next;
  Node *node_prev = node_del->prev;
  node_prev->next = node_next;
  node_next->prev = node_prev;

  printf("specified node with value %d was deleted.\n", node_del->val);

  free(node_del);
  return 0;
}

list_pointerで示されるnode（node_del）と番兵node（list_pointer->top）が一致する場合は、何も削除せずに-1を返します。正常終了なら0を返します。

削除対象のnode（node_del）の次のnode （node_next）と、前（node_del->prev）を連結して、その間のnode_delを解放します。

実行結果

jm3nrhMac-mini-:c akio$ gcc lesson21.c
jm3nrhMac-mini-:c akio$ ./a.out
空の状態のlist
list: 

Lesson21-1: リストの先頭に要素を追加する(20, 10)
new node with value 20 was prepended.
new node with value 10 was prepended.
list: 10 20 

Lesson21-2: リストの最後に要素を追加する(30, 40)
new node with value 30 was appended.
new node with value 40 was appended.
list: 10 20 30 40 

Lesson21-3: リストの先頭の要素を削除する(要素数よりも一回多く実行する)
fisrt node with value 10 was deleted.
fisrt node with value 20 was deleted.
fisrt node with value 30 was deleted.
fisrt node with value 40 was deleted.
*** warning: nothing to delete.
list: 

Lesson21-4: リストの最後の要素を削除する(要素数よりも一回多く実行する)
new node with value 60 was appended.
new node with value 70 was appended.
new node with value 80 was appended.
list: 60 70 80 

last node with value 80 was deleted.
last node with value 70 was deleted.
last node with value 60 was deleted.
*** warning: nothing to delete.
list: 

exercise21-1: リストに引き数で渡した値(30)を持つノードのアドレスを返す関数
new node with value 10 was appended.
new node with value 30 was appended.
new node with value 50 was appended.
value 30 was found in 2nd node.
list: 10 30 50 

exercise21-2: 値(30)を持つノードへのポインタと値(40)を引き数とし、
    指定したnodeの次の位置に、値(40)をもつ新しいノードを挿入する関数
list: 10 30 40 50 

exercise21-3: リストに含まれるノードへのポインタを渡して、そのノードをリストから削除する関数
value 30 was found in 2nd node.
specified node with value 30 was deleted.
list: 10 40 50 

*** warning: specified value 60 was not found.
*** warning: nothing to delete.
list: 10 40 50 

jm3nrhMac-mini-:c akio$ 

ソースコード

lesson21.c

8.44 KB

ファイルダウンロードについて

ダウンロード

後記

わたしにはまだ、ポインタの設定に迷いがある。
最近少し慣れてきて、コンパイラのエラーメッセージを見て、どう対処すべきかなんとなくわかるようになってきたけど、相変わらずよく間違えてしまう。

今回も、参照渡しで値を更新するわけでもないlist_headは、&付じゃないといけないことを理解するのに時間がかかってしまった。
関数内から更に別の関数へと変数を受け渡す場合でも&が必要だったり不要だったり。
コンパイラ様からの懇切丁寧（？）なメッセージがなければ解決しなかったかもしれない。

ここまで読んでいただき有り難うございました。