(答案提出) C言語教室第19回 - 単方向リスト

Akio van der Meer

2023年3月19日 12:21

このC言語教室、前回（第18回）からいきなり難易度が上がり、kzn先生が同じ日本語を話しておられるような気がとてもしない。

幸運（？）にも前回は課題がなかったからボロがでなかったけど、今回（第19回）はもうアカン。

サンプルコードを眺めて、眺めて、眺めて、、、

、、、無理！頭がついていけない。

こんなとき、諦めの悪いおっさんはどうするのか？

、、、そう、
サンプルを弄って弄って弄り倒して、身体で理解するのでした。

結果は、以下の通り。
なんとなく動いているみたいという感じで、全てを理解仕切れている気がしませんが、結果オーライ！？めでたし、めでたし。

冒頭の写真にあるように、トルココーヒーでも頂いて、一服しますか。

課題

・リストの要素の数を返す関数を書きなさい。
・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。

https://note.com/kazushinakamura/n/n64a0ba7d3d09

答案 - 課題

Lesson19−1 リストの要素の数を返す関数

int count_list(Node *head) {
  int cnt = 0;

  while (head != NULL) {
    cnt++;
    head = head->next;
  }

  return cnt;
}

これは、サンプルコードの中のprint_list(Node *head)関数を参考にしました。kzn先生のサンプルコードの要素をカウントしてみます。

Lesson19-1: リストの要素の数を返す関数
List: 1 2 3 
the number of elements in the list : 3

いいぞ、いけそうだ。

Lesson19−2 リストの最後に要素を追加する関数

Node * append(Node *head, int data) {
  Node *root, *buttom;
  root = head;
  buttom = head;

  Node *new_node = (Node*)malloc(sizeof(Node));
  new_node->data = data;

  if (head == NULL) {
    new_node->next = buttom->next;
    return new_node;
  } 

  else
  { 
    while (head != NULL) {
      buttom = head;
      head = head->next;
    }
    
    new_node->next = buttom->next;
    buttom->next = new_node;
    return root;  
  }
}

とりあえずリストの最後まで辿っていって最後の要素を見つけるんだけど、、、その時には既にポインタはNULLになってる！

そこで、毎回Node buttomを更新していき、最後の要素のポインタを保持することにしました。

新たに追加した要素に、
・引数で与えられたデータをセット
・それまでの最後の要素のポインタをセット

それまでの最後の要素のポイントに、
・新しく生成した要素へのポインタをセット

kzn先生のサンプルコードの後ろに、要素を３つ追加してみる。

Lesson19-2: リストの最後に要素を追加する関数
List: 1 2 3 4 5 6 
the number of elements in the list : 6

なんとか動くけど、kzn先生のprepend(Node **head, int data)関数と同じような引数の与え方だとうまくいかない。
（そもそも、私は**headの意味がいまいち理解出来ていないのが原因。
kzn先生、この辺り、もう少しご説明頂けませんでしょうか？）

課題では、「リストの最後に要素を追加」とありますが、リストがNULLだったときは異なる処理をしなければならないことも、動かしながら気付いた。なかなか奥が深い。

Lesson19−3 リストの先頭の要素を削除する関数

先頭のポインターを、次のポインターに書き換えるだけです。
こんなんでいいんかな。

Node * delete_first_item(Node *head) {
  return head->next;
}

要素が6つになったあと、上記のコードを1回実行すると、

Lesson19-3: リストの先頭の要素を削除する関数
List: 2 3 4 5 6 
the number of elements in the list : 5

先頭の要素が削除され、全体の要素数も５に減少しています。

Lesson19-4 n番目の要素を返す関数

int get_Nth_item(Node *head, int seq) {

  for (int i = 0; i < seq; i++) {
    if (head == NULL) return -1;
    head = head->next;
  }

  return head->data;
}

この関数を、次の形でコールした結果が以下の通り。

  for (int i = 0; i < count_list(head); i++) {
    printf("%dth data in the list : %d\n", i, get_Nth_item(head, i));  
  }

Lesson19-4: n番目の要素を返す関数
0th data in the list : 2
1th data in the list : 3
2th data in the list : 4
3th data in the list : 5
4th data in the list : 6

ふ〜。なんとか動いてるみたい。
この調子で演習に取り組んでみよう。

演習

・リストを配列にコピーする関数を書きなさい。
・配列からリストを作る関数を書きなさい。

https://note.com/kazushinakamura/n/n64a0ba7d3d09

答案 - 演習

Exercise19-1 リストを配列にコピーする関数

int * list_to_table(Node *head, int cnt) {
  int i = 0;
  int *a;

  a = (int*)malloc(sizeof(int) * cnt);
	if ( a  == NULL) exit(-1);

  while (head != NULL) {
    a[i++] = head->data;
    head = head->next;
  }

  return a;
}

Exercise19-1: リストを配列にコピーする関数
List: 2 3 4 5 6 
table: 2 3 4 5 6

print_list(Node *head)関数を参考にしました。動的配列を用意しておいて、データを出力する代わりに配列にセットしています。

追記（2024.04.08）このコードには、リストのnode数よりも配列が小さかった場合が考慮されていないという潜在的なバグがあります。lesson19.r_1.3.c以降で修正済み。

Exercise19-2 配列からリストを作る関数

Node * table_to_list(Node *head, int *a, int cnt) {

  for (int i = 0; i < cnt; i++) {
    head = append(head, a[i]);
  }

  return head;
}

上記の「リストの最後に要素を追加する関数」を、配列の要素の数だけ順番に実行しています。

Exercise19-2: 配列からリストを作る関数
table: 0 3 6 9 12 
List: 0 3 6 9 12

実行結果

上記の記事のベースとなったコードはこちら。

Lesson19-1: リストの要素の数を返す関数
List: 1 2 3 
the number of elements in the list : 3

Lesson19-2: リストの最後に要素を追加する関数
List: 1 2 3 4 5 6 
the number of elements in the list : 6

Lesson19-3: リストの先頭の要素を削除する関数
List: 2 3 4 5 6 
the number of elements in the list : 5

Lesson19-4: n番目の要素を返す関数
0th data in the list : 2
1th data in the list : 3
2th data in the list : 4
3th data in the list : 5
4th data in the list : 6

Exercise19-1: リストを配列にコピーする関数
List: 2 3 4 5 6 
table: 2 3 4 5 6 

Exercise19-2: 配列からリストを作る関数
table: 0 3 6 9 12 
List: 0 3 6 9 12

後記

今回の課題で、自分がいかにポインタの使い方を理解していないかを実感。**って何？

追記（2023.3.21)

遊月さん、ChatGPT様にご教示いただき、**（ポインタのポインタ）を使ってみました。関数の呼び方は変えてますが、実行結果は上記と全く同じです。

こっちの方がコードがスッキリするけど、、、まだ頭がついていけてない。
なんで、table_to_list()関数内からappend()関数を呼び出すとき、引数は&headじゃなくてheadになるんだろう？

lesson19_r1.2.c　、、、削除済み。下記の最新版をご覧ください。

解答（2023.03.25）

これこれ！この図を早く見たかった。成程、そういうことなんですね。

リスト構造、、、なんとなく分かってきたような気がします。
でも、「あっ、リスト構造使ってみよう」という具体例が思い浮かばない。

うーん、

ランダムに発生する、複数の優先度の設定があるタスクのスケジュール管理とかどうですかね？各nodeのデータとしては、実際の詳細データへのリンク情報を入れておけばいいのかな。担当者ごとに未完了タスクを束ねるheadの下にプライオリティごとに並べ替えられたタスクのリストがぶら下がり、それとは別に月別作業済みタスクのheadが用意されていて、完了したタスクはそちらのリストに移行していくとか、、、。

ならば次回の双方向リストは、どういった用途なんだろう？
できれば具体的な実用例を交えてご説明いただけると理解が早いと思います。宜しくお願いします。

追記（2023.04.08-09)

kznさんからのご指摘に基づき、
Node * get_Nth_node(Node *head, int seq) 関数を修正しました。(lesson19_r1.3.c)
Ayumiさんからのご指摘に基づき、
int * list_to_table(Node *head, int cnt)関数を修正しました。(lesson19_r1.3.c)
遊月さんからのご指摘に基づき、list_to_table()に代替する
int * make_table_from_list(Node *head)を作成しました。(lesson19_r1.4.c)
ポインタへのポインタ(**)を使って、関数内で生成した配列を戻すため、
int make_table_from_list(Node *head)に代替する
void build_table_from_list(Node *head, int **arr)を作成しました。(lesson19_r1.5.c)
Ayumiさんからのご指摘に基づき、動的配列作成失敗のチェックを変更。
（(lesson19_r1.51.c)

皆様のおかげで、さらに理解が深まりました。改めて御礼申し上げます。

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

これまでの収益は全て、それを必要としておられる方々へ、支援機関を通して寄付させていただきました。この活動は今後も継続したいと思っています。引き続きよろしくお願いいたします。