【C言語入門の次】 第03回 配列リスト

https://youtu.be/VS9KDgG2bgI

$\textcolor{pink}{四国めたん: }$教師役ですわ

$\textcolor{lime}{ずんだもん: }$生徒役なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ こんにちは。四国めたんです

$\footnotesize \textcolor{lime}{ずんだもん:}$ ずんだもんなのだ。こんにちはなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 今回からアルゴリズムの説明の前提となる データ構造 についてお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ データ構造 ？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、今回は、一番簡単な 配列リスト についてお話ししますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ 配列とは違うのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ ほとんど違いはありませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ リストに重点を置くか、配列に重点を置くかで違いが出ますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ その辺りも含めて詳しく教えて欲しいのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ わかりましたわ

配列によるリスト

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで リスト とは何なのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 一般的には「データを一定の規則に従って並べたもの」ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ プログラミングではどんな感じなのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ リスト と云えば、次回以降でお話しする 連結リスト などを指しますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか

$\footnotesize \textcolor{pink}{四国めたん:}$ ただ広い意味では 配列 なども リスト に分類できますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ と云う訳で、今回は リスト としての 配列 を扱いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 配列 は以前の解説でも取り上げたのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まぁ、 配列 は非常に判り易く、扱い易いと思いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 例えば学生番号と学生の名前を保持する構造体を学生の数だけ 配列 として リスト にすることを考えますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ メモリ上ではこのように配置されますわ

$\footnotesize \textcolor{pink}{四国めたん:}$ 実際にリストを作成して表示するプログラムを見てみましょう

#include <stdio.h>

#define NAME_SIZE (20)

typedef struct {
  unsigned int id;
  char name[NAME_SIZE];
} student;

int main(int argc, char* argv[]) {
  student student_list[] = {
      {1, "佐藤紬"},   {2, "鈴木陽翔"}, {3, "高橋翠"},
      // さとうつむぎ すずきはると たかはしみどり
      {4, "田中朝陽"}, {5, "伊藤凛"},
      // たなかあさひ いとうりん
  };

  size_t size = sizeof(student_list) / sizeof(student);

  for (size_t i = 0; i < size; i++) {
    printf("学生番号: %d, 名前: %s\n", student_list[i].id,
           student_list[i].name);
  }
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ 最初に学生番号と学生の名前を要素に持つ構造体studentを定義していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ "name"の配列のサイズ"NAME_SIZE"は適当なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数内では、5人分の学生のデータを初期値としてstudentの配列を宣言、初期化していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 配列の要素数の指定はないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 配列 の要素数"size"は、sizeofを使って取得していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ よく使われるテクニックなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、 配列 のサイズを要素のサイズで割っていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ どちらもバイト単位なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、forループで全ての学生のデータを出力していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 構造体の要素を出力しているだけなのだ

配列のリストは余裕を持って

$\footnotesize \textcolor{pink}{四国めたん:}$ 配列リスト は簡単なのが利点ですが、問題点もありますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ どのような問題点なのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ データの挿入や追加、削除などが難しい点ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしかにその通りなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ サンプルプログラムでは、 配列 のサイズが固定されているため、そのままではデータの追加はできませんわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ どうすればいいのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 回避策としては、 配列 の要素数を余裕をもって準備しておくことですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 意外に単純なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ サンプルプログラムでは、 配列 のサイズは初期値を収めるぎりぎりの要素数となっていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ これを例えば10人分の学生のデータを収めるだけの要素数を準備すれば、あと5人分の追加は可能となりますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず 配列 のサイズを10にして、学生のデータを途中に追加するプログラムを見てみましょう

#include <stdio.h>
#include <string.h>

#define NAME_SIZE (20)
#define LIST_SIZE (10)

typedef struct {
  unsigned int id;
  char name[NAME_SIZE];
} student;

size_t insert(student list[], size_t num, size_t index, unsigned int id, char name[]) {
  size_t rc = 0;
  if ((num < LIST_SIZE) && (index <= num)) {
    size_t dst_size = sizeof(student) * (LIST_SIZE - index - 1);
    size_t src_size = sizeof(student) * (num - index);
    memmove_s(&(list[index + 1]), dst_size, &(list[index]), src_size);
    list[index].id = id;
    strcpy_s(list[index].name, NAME_SIZE, name);
    rc = num + 1;
  }
  return rc;
}

int main(int argc, char* argv[]) {
  size_t student_num = 5;
  student student_list[LIST_SIZE] = {
      {1, "佐藤紬"},   {2, "鈴木陽翔"}, {3, "高橋翠"},
      {4, "田中朝陽"}, {5, "伊藤凛"},
  };
  student_num = insert(student_list, student_num, 3, 6, "渡辺暖");

  for (size_t i = 0; i < student_num; i++) {
    printf("学生番号: %d, 名前: %s\n", student_list[i].id,
           student_list[i].name);
  }
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ insert関数ではこのような引数を取りますわ

1. list[]: データを挿入するリスト
2. num: 現在のデータの数
3. index: 挿入する位置
4. id: 挿入するデータのID
5. name[]: 挿入するデータの学生名

$\footnotesize \textcolor{pink}{四国めたん:}$ 第1引数にデータを挿入する 配列リスト を指定しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 第2引数と第3引数には、現在のデータ数と、挿入する位置を指定しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後に、第4引数と第5引数には挿入するデータを指定しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そしてinsert関数の最初で、データ数が、配列の要素数を超えないか、チェックしていますわ

$\footnotesize \textcolor{pink}{四国めたん:}$ 同時に、挿入位置がデータの最後よりも後ろを指していないかのチェックもしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、挿入箇所以降のデータをmemmove_sで1つづつずらしています。

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後に、空いたデータ部分に、新規のデータを挿入していますわ

$\footnotesize \textcolor{pink}{四国めたん:}$ なお、移動するデータサイズと、移動先のデータサイズは間違わないように、慎重な計算が必要ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 気を付けるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最終的に、戻り値としてデータサイズ、つまり挿入前のデータサイズに1を足した値を戻しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数では要素数10の配列を用意して、5人分のデータで初期化しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次にinsert関数でインデックス3の部分に新しいデータを追加しますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後にfor文でデータの出力を行いますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 実行するとこのようになるのだ

配列のデータの削除

$\footnotesize \textcolor{pink}{四国めたん:}$ 次はデータの削除ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 指定したインデックスのデータを削除するのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、削除によって空いた要素の部分は、後に続くデータで詰めることで、要素の空きを埋めますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ イメージとしてはどのようになるのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ こんな感じですわ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実装してみましょう

#include <stdio.h>
#include <string.h>

#define NAME_SIZE (20)
#define LIST_SIZE (10)

typedef struct {
  unsigned int id;
  char name[NAME_SIZE];
} student;

size_t delete(student list[], size_t num, size_t index) {
  size_t rc = num;
  if ((num > 0) && (index < num)) {
    size_t dst_size = sizeof(student) * (LIST_SIZE - index);
    size_t src_size = sizeof(student) * (num - index - 1);
    memmove_s(&(list[index]), dst_size, &(list[index + 1]), src_size);
    list[num - 1].id = 0;
    list[num - 1].name[0] = 0;
    rc--;
  }
  return rc;
}

int main(int argc, char* argv[]) {
  size_t student_num = 5;
  student student_list[LIST_SIZE] = {
      {1, "佐藤紬"},   {2, "鈴木陽翔"}, {3, "高橋翠"},
      {4, "田中朝陽"}, {5, "伊藤凛"},
  };
  student_num = delete(student_list, student_num, 2);

  for (size_t i = 0; i < student_num; i++) {
    printf("学生番号: %d, 名前: %s\n", student_list[i].id,
           student_list[i].name);
  }
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ まずdelete関数はリストと要素数、削除するインデックスを引数に取りますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ ふむふむ

$\footnotesize \textcolor{pink}{四国めたん:}$ そして削除後の要素数が返りますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ まず最初に、戻り値"rc"を最初の要素数で初期化しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次に、要素数とインデックスに問題がないかチェックしています

$\footnotesize \textcolor{lime}{ずんだもん:}$ 要素数は正数、インデックスは要素数より小さい必要があるのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 削除については、データの移動でおこないますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ memmove_s関数を使うのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ コピーするデータサイズ等を予めバイト単位で計算しておきますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 少し複雑なのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 最後に無効となった要素のデータを初期化した後、要素数を1つだけ減らしていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数はデータの挿入の場合と概ね同じですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ insert関数の呼び出しがdelete関数に変わっているのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ それでは実行してみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ インデックス2の要素「3, 高橋翠」が削除されているのだ

簡単な配列のデータ削除

$\footnotesize \textcolor{lime}{ずんだもん:}$ データの削除はできたが、データの移動を伴うなど、大変ではないのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、ですので配列からのデータ削除でよく使われるのが、 マーキング という方法ですわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ マーキング？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、削除したことを示すマークをデータに埋め込む方法ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず、student構造体の"id"の値が0の場合に、データが削除されたとみなして実装してみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ おねがいするのだ

#include <stdio.h>
#include <string.h>

#define NAME_SIZE (20)
#define LIST_SIZE (10)

typedef struct {
  unsigned int id;
  char name[NAME_SIZE];
} student;

void delete(student list[], size_t index) {
  list[index].id = 0;
  return;
}

int main(int argc, char* argv[]) {
  size_t student_num = 5;
  student student_list[LIST_SIZE] = {
      {1, "佐藤紬"},   {2, "鈴木陽翔"}, {3, "高橋翠"},
      {4, "田中朝陽"}, {5, "伊藤凛"},
  };
  delete (student_list, 2);

  for (size_t i = 0; i < student_num; i++) {
    if (student_list[i].id != 0) {
      printf("学生番号: %d, 名前: %s\n", student_list[i].id,
             student_list[i].name);
    }
  }
  return 0;
}

$\footnotesize \textcolor{pink}{四国めたん:}$ まずdelete関数は、指定したインデックスのstudent構造体の"id"を0として、データの削除としていますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ チェックなどをかなり省いていないか？

$\footnotesize \textcolor{pink}{四国めたん:}$ まぁ、そこはサンプルと云うことでスルーして下さいね

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ ここで重要なのがメイン関数です

$\footnotesize \textcolor{lime}{ずんだもん:}$ そうなのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ メイン関数のリストの表示をおこなうループ内で、student構造体の"id"が0ではないデータのみ表示するように変更していますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ とりあえず実行してみましょう

$\footnotesize \textcolor{lime}{ずんだもん:}$ 削除したデータが表示されていないのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ そうですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ ところで、データの削除が多くなると、配列のデータがスカスカになるのではないのか？

$\footnotesize \textcolor{pink}{四国めたん:}$ たしかに、用意した配列のサイズが足りなくなってしまう可能性もあるので、問題ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ どうするのだ？

$\footnotesize \textcolor{pink}{四国めたん:}$ 通常は、定期的に削除マークのある要素を完全に削除し、データを詰めるための追加の作業が必要になりますわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ なるほどなのだ

まとめ

$\footnotesize \textcolor{pink}{四国めたん:}$ お疲れさまでした。

$\footnotesize \textcolor{lime}{ずんだもん:}$ おつかれさまなのだ

$\footnotesize \textcolor{pink}{四国めたん:}$ 以上で 配列リスト を一旦、終了しますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ 一旦？

$\footnotesize \textcolor{pink}{四国めたん:}$ はい、配列によるリストの操作は、意外と使う場面があったりしますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ たしかに...

$\footnotesize \textcolor{pink}{四国めたん:}$ インデックスの指定の間違いによるバグなども多いので、結構、慣れが必要ですわね

$\footnotesize \textcolor{lime}{ずんだもん:}$ うむ

$\footnotesize \textcolor{pink}{四国めたん:}$ 次回はその辺りをまとめて 配列リスト の続きをお話ししますわ

$\footnotesize \textcolor{lime}{ずんだもん:}$ りょうかいなのだ