C言語教室解答編第20回 - とアルゴリズムと計算量(O)

2023年4月4日 09:04

今回は、

C言語教室第20回 - 双方向リスト

の課題の解答をしていきます。

既に単方向リストの説明は済んでいるので、そちらを参考にすればさほど難しくはないと思います。まだ課題を済ませていない方は、ここから先を読む前に、ぜひ課題に挑戦していただければ幸いです。

解答に進む前に、恒例の「うっかり答えを見ないための」閑話など。

C言語よりモダンな言語である C++ であるとか Java、C#、python などでは、最初から配列以外にリストが用意されているので、その違いをキチンと理解せずに使ってしまっていることがあるようですが、それらの内部構造はここで解説しているような作りになっています。大切なことは配列とリストにはそれぞれ得意、不得意があることで、特に検索速度には大きな違いが出ることがあります。これはループの内側になるような繰り返し実行される場合には顕著になります。

多くのデータを使って処理を書くときに、どのような方法を使うかと言うときに、その方法を特に「アルゴリズム」と呼ぶことがあります。この言葉自身はもっと広義な意味を持つのですが、どの方法を取ると、どのくらいの数のデータが有るときに、どのくらいの時間がかかるのかという部分を「計算量」と呼ぶ習わしで、データが多い時には、このアルゴリズムの選択がプログラムのパフォーマンスを決めることになります。まあデータが少ない時には、ほぼ影響は無く、処理が簡単に済むほうがバグも入り込みにくく、余計なお世話ではあるのですが、実用的なコードを書くにはとても大事なことです。

これからしばらくは教室でも、このアルゴリズムに関連した課題をとりあげる予定です。普段は C言語なんか使っていないという方も、ちょっと興味を持って頂ければ幸いです。

アルゴリズム解析

特集！知らないと損をする計算量の話

さて、前回、双方向リストを扱うコードを説明していなかったので、個別の課題に入る前に、基本をおさらいしておきましょう。

双方向リストのひとつのデータを格納するノードには、値の他に前のノードへのポインタと、次のノードへのポインタを持ちます。この構造体を使ってリストの主な操作である挿入と削除の例をあげます。なお今回は先頭のノードへのポインタだけでリストを管理しています。


#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
  int data;
  struct Node *prev;
  struct Node *next;
} Node;

Node *createNode(int data) {
  Node newNode = (Node)malloc(sizeof(Node));
  newNode->data = data;
  newNode->prev = NULL;
  newNode->next = NULL;
  return newNode;
}

void insertAtHead(Node **headRef, int data) {
  Node *newNode = createNode(data);
  if (*headRef == NULL) {
    *headRef = newNode;
  } else {
    newNode->next = *headRef;
    (*headRef)->prev = newNode;
    *headRef = newNode;
  }
}

void insertAtTail(Node **headRef, int data) {
  Node *newNode = createNode(data);
  if (*headRef == NULL) {
    *headRef = newNode;
  } else {
    Node *temp = *headRef;
    while (temp->next != NULL) {
      temp = temp->next;
    }
    temp->next = newNode;
    newNode->prev = temp;
  }
}

void deleteNode(Node **headRef, Node *delNode) {
  if (*headRef == NULL || delNode == NULL) {
    return;
  }
  if (*headRef == delNode) {
    *headRef = delNode->next;
  }
  if (delNode->next != NULL) {
    delNode->next->prev = delNode->prev;
  }
  if (delNode->prev != NULL) {
    delNode->prev->next = delNode->next;
  }
  free(delNode);
}

int countNodes(Node *head) {
  int count = 0;
  while (head != NULL) {
    count++;
    head = head->next;
  }
  return count;
}

void printList(Node *head) {
  while (head != NULL) {
    printf("%d ", head->data);
    head = head->next;
  }
  printf("\n");
}

void main() {
  Node *head = NULL;

  insertAtHead(&head, 10);
  insertAtHead(&head, 20);
  insertAtTail(&head, 30);
  printf("count=%d\n", countNodes(head));
  printList(head); 
  deleteNode(&head, head);
  printList(head); 
  deleteNode(&head, head->next);
  printList(head); 
  deleteNode(&head, head);
}

実行結果は以下です。

count=3
20 10 30
10 30
10

単方向リストの時もそうでしたが、リストの端に対する操作は例外的な処理が必要になることに注意してください。ポインタのポインタの使い方はもう大丈夫ですね。

それでは、そろそろ課題に進みましょう。今回の課題は以下の内容でした。

課題
・リストの最後に要素を追加する関数を書きなさい。
・リストの先頭の要素を削除する関数を書きなさい。
・n番目の要素を返す関数を書きなさい。
・要素の中に指定した値が含まれるかを返す関数を書きなさい。

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

最初の課題と次の課題は、既に説明したコードに含まれているので、飛ばします。

n番目の要素を返すには、以下のような関数が使えます。該当する要素が存在しなければ NULL を返しています。

Node* getNode(Node *head, int n) {
  int count = 0;
  while (head != NULL && count < n) {
    count++;
    head = head->next;
  }
  if (count == n && head != NULL) {
    return head;
  } else {
    return NULL;
  }
}

引き数で指定した値がリストに含まれているかは、以下のような関数で調べられます。存在すれば -1、しなければ 0 を返します。

int contains(Node *head, int value) {
  while (head != NULL) {
    if (head->data == value) {
      return -1;
    }
    head = head->next;
  }
  return 0;
}

C言語では、異なる型に対する処理をまとめる方法が無いので、値が整数以外の場合には、都度、型に合わせた関数を用意する必要があります。実際にリストで処理を書くのは、対象が文字列の場合が多いのですが、その場合には値の部分の方が char* になるわけです。値としてポインタが入る場合には、比較の際にポインタを比べるのではなく、ポインタの指す先を比べる場合があったり、値が NULL になっていないか、など、もうひと手間増えるのですが、基本が出来ていれば恐れることはありません。

今回も Akio van der Meer さんから答案を頂きました。いつもありがとうございます。

（答案提出）C言語教室第20回 - 双方向リスト

教室で使ったコードを元にされたとは言え、手をいれるべきところにきちんと手が入っているので、かなり理解は進まれているように見えます。

ところで Lesson20−3 n番目の要素を返す関数ですが、与えた n が要素の数よりひとつだけ大きかった場合に、おかしな値が返るようです。それからエラーの時に -1 を返すと、要素が -1 だった時に困ってしまいます。ここは値ではなくポインタを返す関数を書いてください。

英語で序数を使うときの接尾語を作る関数をお作りになるあたり脱帽です。ただ序数に負は無いので、答えが負のときは違う表現が良かろうかと。

だいぶポインタ操作にも慣れてきたようなので、もう少しあれこれ書いてみれば、次のステップに進めそうですよ。

2023.4.5 追記

上記のコメントを反映させた答案を再提出して頂きました。何だか補習みたいですね。

（答案再提出）C言語教室第20回 - 双方向リスト

序数のくだりは半ばジョークではあったのですが、しっかり修正をしていただいて、こちらが恐縮です。そうかぁ、関数の相互参照とかも説明しないとならないですね。今後ともお付き合いのほど、よろしくお願いします。

2023.4.15 追記

AyumiKatayama さんにも答案を頂きました。いつもありがとうございます。

C言語教室第20回 - 双方向リスト（回答提出）

はい。単方向リストの延長なので、NULL終端でございます。正直、自分で書く時は循環リストにしてしまうので、確かに例外的な処理があって面倒で、書き方を忘れていました。

解答で示したコードは、単方向リストを参考にしたので手を抜いて、リストへの末尾のポインタを管理せず、末尾への挿入は少しばかり勿体ないコードの書き方になっております。きちんと、そのアタリをフォローして頂いたコードになっていて感謝します。

一応、コードを走らせて追ったのですが、テストは通っているし、怪しいところを見つけられていません。引き数の組み立てと戻り値などが解答例と違っているところもありますが、その辺は実装する人の趣味というか好みの範疇だとは思います。もちろん解答例の中に怪しい部分が見つかったら、どんどん指摘してくださいませ。

ここまで追記分。

次は循環リストを取り上げます。

ヘッダ画像は、いらすとやさんよりhttps://www.irasutoya.com/2020/04/blog-post_243.html

#C言語 #答え合わせ #プログラミング講座 #双方向リスト #ポインタ #序数

いいなと思ったら応援しよう！

頂いたチップは記事を書くための資料を揃えるために使わせていただきます！

C言語教室 解答編 第20回 - と アルゴリズムと計算量(O)

いいなと思ったら応援しよう！

C言語教室解答編第20回 - とアルゴリズムと計算量(O)