🖥️

【C言語入門の次】 第04.5回 連結リストのバリエーション

に公開
データ構造
入門
アルゴリズム
C言語
連結リスト
tech

https://youtu.be/MbRFn8_xqvY

四国めたん
\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{pink}{四国めたん:} 前回の 連結リスト では、ノードの連結先は単一のノードとなっていましたわ

\footnotesize \textcolor{lime}{ずんだもん:} 実際の構造体では、次のノードへのポインタは1つのみになっているのだ

typedef struct student {
  unsigned int id;
  char name[20];
  struct student* pnext;
} student;

\footnotesize \textcolor{pink}{四国めたん:} 双方向リスト では、ノードへのポインタは2つに増えていますわ

\footnotesize \textcolor{lime}{ずんだもん:} 1つは従来通り、次のノードへのポインタとして、もう1つはどのようなポインタなのだ？

\footnotesize \textcolor{pink}{四国めたん:} もう1つは、前のノードへのポインタですわ

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

typedef struct student {
  unsigned int id;
  char name[20];
  struct student* pprev;
  struct student* pnext;
} student;

\footnotesize \textcolor{pink}{四国めたん:} ここでは"pprev"が追加されたポインタで、前のノードを指していますわ

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

双方向リスト

双方向リストのメリット

\footnotesize \textcolor{lime}{ずんだもん:} ところで 双方向リスト は、単に前のノードの参照ができるだけで、特にメリットがあるようには思えないのだが...

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

\footnotesize \textcolor{pink}{四国めたん:} せいぜい、ノードの挿入や削除が簡単になる程度ですわ

\footnotesize \textcolor{lime}{ずんだもん:} メリットは無いのか？

\footnotesize \textcolor{pink}{四国めたん:} いえ、ソートされたデータに対して、逆方向にデータを連続して取得していく場合には、かなりの威力を発揮しますわ

\footnotesize \textcolor{lime}{ずんだもん:} ようは使いどころによるということか

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

双方向リストの実装

とりあえず 双方向リスト を実装してみましょう

まず、ヘッダーファイル"student.h"dです

student.h
#pragma once
#ifndef _INC_STUDENTS
#define _INC_STUDENTS

#include <stdio.h>

#define NAME_SIZE (20)

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

typedef struct {
  student* phead;
  student* ptail;
  student* pcurrent;
  size_t curr_idx;
  size_t num;
} student_list;

void init_student_list(student_list* plist);

void final_student_list(student_list* plist);

int move_forward(student_list* plist);

int move_backward(student_list* plist);

int move_to(student_list* plist, size_t idx);

int delete_node(student_list* plist);

int insert_node(student_list* plist, unsigned int id, const char name[]);

#endif  // _INC_STUDENTS

"student"構造体には、前のノードを参照する"pprev"を追加しています

"student_list"構造体には、 双方向リスト の先頭のノードへのポインタ"phead"のほかに最後のノードへのポインタ"ptail"を追加しています

また、挿入や削除を行うためのインデックスを示すため、"pcurrent"および"curr_idx"を設けています

初期化や終了の関数のほかに、インデックスを動かすための関数move_forward、move_backward、move_toを設けました

また、ノードの挿入、削除のためにdelete_nodeやinsert_node関数を設けています。

ちなみに、現在のインデックスのノードのデータを取得するには、"student_list"構造体の"pcurrent"を参照すればOKなので、特に関数は設けていません

次は実装です

students.c
#include "students.h"

#include <stdlib.h>
#include <string.h>

void init_student_list(student_list* plist) {
  plist->phead = NULL;
  plist->ptail = NULL;
  plist->pcurrent = NULL;
  plist->curr_idx = 0;
  plist->num = 0;
  return;
}

void final_student_list(student_list* plist) {
  int rc = -1;
  move_to(plist, 0);
  do {
    rc = delete_node(plist);
  } while (rc == 0);
  return;
}

int move_forward(student_list* plist) {
  int rc = -1;
  if (plist->pcurrent != NULL) {
    plist->pcurrent = plist->pcurrent->pnext;
    rc = ++(plist->curr_idx);
  }
  return rc;
}

int move_backward(student_list* plist) {
  int rc = -1;
  if (plist->pcurrent == NULL) {
    if (plist->phead != NULL) {
      plist->pcurrent = plist->ptail;
      rc = --(plist->curr_idx);
    }
  } else if (plist->pcurrent->pprev != NULL) {
    plist->pcurrent = plist->pcurrent->pprev;
    rc = --(plist->curr_idx);
  }
  return rc;
}

int move_to(student_list* plist, size_t idx) {
  int rc = -1;
  if (idx <= plist->num) {
    while (idx < plist->curr_idx) {
      move_backward(plist);
    }
    while (idx > plist->curr_idx) {
      move_forward(plist);
    }
    rc = plist->curr_idx;
  }
  return rc;
}

int delete_node(student_list* plist) {
  int rc = -1;
  if (plist->pcurrent != NULL) {
    student* p2delete = plist->pcurrent;
    if (plist->pcurrent->pprev == NULL) {
      plist->phead = plist->pcurrent->pnext;
      if (plist->phead != NULL) {
        plist->phead->pprev = NULL;
      }
      plist->pcurrent = plist->phead;
    } else if (plist->pcurrent->pnext == NULL) {
      student* pprev = plist->pcurrent->pprev;
      pprev->pnext = NULL;
      plist->ptail = pprev;
      plist->pcurrent = NULL;
    } else {
      student* pprev = plist->pcurrent->pprev;
      student* pnext = plist->pcurrent->pnext;
      pprev->pnext = pnext;
      pnext->pprev = pprev;
      plist->pcurrent = pnext;
    }
    free(p2delete);
    plist->num--;
    rc = plist->curr_idx;
  }
  return rc;
}

student* make_student_node(int id, const char name[]) {
  student* pstudent = (student*)malloc(sizeof(student));
  if (pstudent != NULL) {
    pstudent->id = id;
    snprintf(pstudent->name, NAME_SIZE, "%s", name);
    pstudent->pprev = NULL;
    pstudent->pnext = NULL;
  }
  return pstudent;
}

int insert_node(student_list* plist, unsigned int id, const char name[]) {
  int rc = -1;
  student* pnew_node = make_student_node(id, name);
  if (pnew_node != NULL) {
    if (plist->phead == NULL) {
      plist->phead = pnew_node;
      plist->ptail = pnew_node;
      plist->pcurrent = pnew_node;
    } else if (plist->pcurrent == NULL) {
      pnew_node->pprev = plist->ptail;
      plist->ptail->pnext = pnew_node;
      plist->ptail = pnew_node;
      plist->pcurrent = pnew_node;
    } else {
      student* pprev = plist->pcurrent->pprev;
      pnew_node->pprev = pprev;
      pnew_node->pnext = plist->pcurrent;
      if (pprev == NULL) {
        plist->phead = pnew_node;
      } else {
        pprev->pnext = pnew_node;
      }
      plist->pcurrent->pprev = pnew_node;
      plist->pcurrent = pnew_node;
    }
    plist->num++;
    rc = plist->curr_idx;
  }
  return rc;
}

まず初期化関数init_student_listですが、今回はダミーノードを使用しませんので、各メンバをNULLや0で初期化しています

次に終了関数final_student_listですが、インデックスを先頭に移動した後、全てのノードが削除されるまで、delete_node関数により、ノードの削除を行っています

非常に効率は悪いのですが、判り易いのでこの方法を取りました

リストを辿って、直接、ノードを解放すれば、効率は良くなります

たとえばこんな感じです

void final_student_list(student_list* plist) {
  int rc = -1;
  student* p2delete = plist->phead;
  while (p2delete != NULL) {
    student* pnext = p2delete->pnext;
    free(p2delete);
    p2delete = pnext;
  }
  init_student_list(plist);
  return;
}

move_forward関数は、現在のインデックスのノードを次のインデックスのノードに移動します

現在のインデックスのノード"pcurrent"がNULLの場合には、ノードが無いか、最後のノードの次を指しているので、移動はできません

move_backward関数は、現在のインデックスのノードを前のインデックスのノードに移動します

双方向リスト の威力が発揮される場面です

現在のインデックスのノード"pcurrent"がNULLの場合には、ノードが無いか、最後のノードの次を指しています

ノードが無い場合には移動はできませんが、最後のノードの次を指している場合には、最後のノードを指すようにします

また、"pcurrent"が最初のノードを指している場合にも移動はできませんのでスキップします

その他の場合には、"student"構造体の"pprev"を辿って、前のノードに"pcurrent"を移します

move_to関数については、指定のインデックスに"pcurrent"を移動します

指定のインデックスによって、move_backward関数やmove_forward関数で移動を行います

なお、指定のインデックスがリストの最初や最後に近い場合に、リストの最初や最後からノードを辿るようにすれば、効率が良くなります

次にdelete_node関数ですが、"pcurrent"がNULL、つまりノードが無いか、最後のノードの次を指している場合には、ノードの削除はできません

その他の場合、削除するノードがリストの最初か、最後か、途中かでリンクのつなぎ直しの方法が変わるので、場合分けしています

最後にinsert_node関数ですが、まず、make_student_node関数で挿入するノードを作成します

そして、挿入するノードが最初のノードか、リストの最後への挿入か、途中への挿入かでリンクのつなぎ直しの方法が変わるので、場合分けしています

それではメイン関数で 双方向リスト を使ってみましょう

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

#include "students.h"

int main(int argc, char* argv[]) {
  student_list list;
  init_student_list(&list);
  insert_node(&list, 1, "佐藤紬");
  insert_node(&list, 2, "鈴木陽翔");
  insert_node(&list, 3, "高橋翠");
  insert_node(&list, 4, "田中朝陽");
  insert_node(&list, 5, "伊藤凛");
  move_to(&list, 2);
  delete_node(&list);
  insert_node(&list, 6, "渡辺暖");

  move_to(&list, 0);
  student* pstudent = list.pcurrent;
  while (pstudent != NULL) {
    printf("学生番号: %d, 名前: %s\n", pstudent->id, pstudent->name);
    move_forward(&list);
    pstudent = list.pcurrent;
  }

  final_student_list(&list);

  return 0;
}

双方向リスト

環状リスト

\footnotesize \textcolor{pink}{四国めたん:} 次は 環状リスト ですわ

\footnotesize \textcolor{lime}{ずんだもん:} 環状リスト ？

\footnotesize \textcolor{pink}{四国めたん:} はい、前回の 連結リスト では、最後のノードの連結先である"pnext"はNULLになっていましたわ

\footnotesize \textcolor{lime}{ずんだもん:} "pnext"がNULLであることで最後のノードであることがわかったのだ

\footnotesize \textcolor{pink}{四国めたん:} 環状リスト では、最後のノードの連結先を最初のノードにするのですわ

\footnotesize \textcolor{lime}{ずんだもん:} 最後のノードはどうすれば確認できるのだ？

\footnotesize \textcolor{pink}{四国めたん:} 環状リスト では 最後のノード という概念はありませんわ

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

環状リスト

環状リストのメリット

\footnotesize \textcolor{lime}{ずんだもん:} ところで 環状リスト のメリットはなんなのだ？

\footnotesize \textcolor{pink}{四国めたん:} 環状リスト のメリットは、ノードの最初と最後の区別を付ける必要が無いということですわ

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

\footnotesize \textcolor{pink}{四国めたん:} はい、FIFOのバッファなどにはうってつけですわね

環状リストの実装

とりあえず 環状リスト を実装してみましょう

まず、ヘッダーファイル"student.h"です

student.h
#pragma once
#ifndef _INC_STUDENTS
#define _INC_STUDENTS

#include <stdio.h>

#define INIT_NODE_NUM (5)
#define NAME_SIZE (20)

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

typedef struct {
  student* ppop;
  student* ppush;
  student* pprev;
  size_t data_num;
  size_t node_num;
} student_list;

int init_student_list(student_list* plist);

void final_student_list(student_list* plist);

int push(student_list* plist, unsigned int id, const char name[]);

int pop(student_list* plist, student* pstudent);

#endif  // _INC_STUDENTS

"student"構造体は 連結リスト と同じです

"student_list"構造体は、データを書き込むノードへのポインタ"ppush"と、データを読み出すためのノードへのポインタ"ppop"を設けています

"pprev"は、データが満杯の時にノードを追加する際に必要な、"ppush"の前のノードを指すようにします

また、挿入や削除を行う際のノードの使用状態を確認するため、"data_num"および"node_num"を設けています

関数としては、初期化や終了の関数のほかに、データの入出力のためのpopおよびpush関数を宣言しています

次は実装です

students.c
#include "students.h"

#include <stdlib.h>
#include <string.h>

student* make_student_node() {
  student* pstudent = (student*)malloc(sizeof(student));
  if (pstudent != NULL) {
    pstudent->id = 0;
    pstudent->name[0] = 0;
    pstudent->pnext = NULL;
  }
  return pstudent;
}

int insert_node(student_list* plist) {
  int rc = -1;
  student* pnew_student = make_student_node();
  if (pnew_student != NULL) {
    plist->pprev->pnext = pnew_student;
    pnew_student->pnext = plist->ppush;
    plist->ppush = pnew_student;
    plist->node_num++;
    rc = 0;
  }
  return rc;
}

int init_student_list(student_list* plist) {
  int rc = -1;
  student* pnew_student = make_student_node();
  if (pnew_student != NULL) {
    pnew_student->pnext = pnew_student;
    plist->ppush = pnew_student;
    plist->pprev = pnew_student;
    plist->node_num = 1;
    for (size_t i = 0; i < (INIT_NODE_NUM - 1); i++) {
      rc = insert_node(plist);
    }
    plist->ppop = plist->ppush;
    plist->data_num = 0;
  }
  return rc;
}

void final_student_list(student_list* plist) {
  for (size_t i = 0; i < plist->node_num; i++) {
    student* p2delete = plist->ppop;
    plist->ppop = plist->ppop->pnext;
    free(p2delete);
  }
  plist->ppop = NULL;
  plist->ppush = NULL;
  plist->data_num = 0;
  plist->node_num = 0;
  return;
}

int push(student_list* plist, unsigned int id, const char name[]) {
  int rc = 0;
  if (plist->data_num == plist->node_num) {
    rc = insert_node(plist);
  }
  if (rc == 0) {
    plist->ppush->id = id;
    snprintf(plist->ppush->name, NAME_SIZE, "%s", name);
    plist->pprev = plist->ppush;
    plist->ppush = plist->ppush->pnext;
    plist->data_num++;
  }
  return rc;
}

int pop(student_list* plist, student* pstudent) {
  int rc = -1;
  if ((pstudent != NULL) && (plist->data_num > 0)) {
    pstudent->id = plist->ppop->id;
    snprintf(pstudent->name, NAME_SIZE, "%s", plist->ppop->name);
    pstudent->pnext = NULL;
    plist->ppop = plist->ppop->pnext;
    plist->data_num--;
    rc = 0;
  }
  return rc;
}

まず初期化関数init_student_listですが、とりあえず5つの空のノードを作成、連結しています

最初のノードは特殊なので別途作成し、その後はinsert_nodeで残りの4つのノードを作例、連結しています

insert_node内では、 make_student_node で新たなノードを作成し、"student_list"の"pprev"が指すノードと"ppush"が指すノードの間に挿入します

なお、初期化時には"student_list"の"ppop"と"ppush"は同じノードを指していますが、"data_num"は0となっています

次に終了関数final_student_listですが、"student_list"の"ppop"が指すノードを辿って、"node_num"だけfree関数でノードを解放しています

データの挿入については、push関数を用意しています

基本的には"student_list"の"ppush"が指すノードに指定されたデータをコピーし、"ppush"を次のノードに移動します

ただ、"student_list"の"data_num"と"node_num"が等しい場合は空のノードが無いため、insert_nodeで新たなノードを追加します

データの取得はpop関数を使います。

引数として渡された"student"構造体に、"student_list"の"ppop"が指すノードのデータをコピーします

それではメイン関数で 環状リスト を使ってみましょう

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

#include "students.h"

int main(int argc, char* argv[]) {
  student_list list;
  init_student_list(&list);
  push(&list, 1, "佐藤紬");
  push(&list, 2, "鈴木陽翔");
  push(&list, 3, "高橋翠");
  push(&list, 4, "田中朝陽");
  push(&list, 5, "伊藤凛");
  push(&list, 6, "渡辺暖");

  student person;
  int rc = pop(&list, &person);
  while (rc == 0) {
    printf("学生番号: %d, 名前: %s\n", person.id, person.name);
    rc = pop(&list, &person);
  }

  final_student_list(&list);

  return 0;
}

環状リスト2

二分木

\footnotesize \textcolor{pink}{四国めたん:} 最後は 二分木 ですわ

\footnotesize \textcolor{lime}{ずんだもん:} 二分木 ？

\footnotesize \textcolor{pink}{四国めたん:} はい、 二分木 には用途によってバリエーションが豊富なのですが、今回は基本的な構造をお話ししますわ

\footnotesize \textcolor{lime}{ずんだもん:} よろしくなのだ

\footnotesize \textcolor{pink}{四国めたん:} 二分木 の構造は、1つのノードに対して2つのノードが連結されていますわ

\footnotesize \textcolor{lime}{ずんだもん:} 双方向リスト のようになっているのか？

\footnotesize \textcolor{pink}{四国めたん:} 双方向リスト では前のノードへのポインタでしたが、 二分木 では別々のノードへのポインタとして実装されますわね

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

二分木

\footnotesize \textcolor{pink}{四国めたん:} ちなみに、連結元のノード、ここでは"id = 2、 name = 鈴木陽翔"のノードを 親ノード と云いますわ

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

\footnotesize \textcolor{pink}{四国めたん:} また、連結先のノード、ここでは"id = 1、 name = 佐藤紬"、"id = 3、 name = 高橋翠"のノードを 子ノード と云いますわ

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

\footnotesize \textcolor{pink}{四国めたん:} なお、 親ノード を持たない、一番上のノードは ルート と云いますわ

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

\footnotesize \textcolor{pink}{四国めたん:} ところで 二分木 には1つだけルールを設けますわ

\footnotesize \textcolor{lime}{ずんだもん:} どのようなルールなのだ？

\footnotesize \textcolor{pink}{四国めたん:} それは「左の子ノードの値 < 親ノードの値 < 右の子ノードの値」というルールですわ

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

\footnotesize \textcolor{pink}{四国めたん:} まぁ、用途等によって、そのルールは「左の子ノードの値 <= 親ノードの値 < 右の子ノードの値」のように変化する場合もありますが...

\footnotesize \textcolor{lime}{ずんだもん:} 「左の子ノードの値 > 親ノードの値 > 右の子ノードの値」とする場合もあるのか...

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

\footnotesize \textcolor{pink}{四国めたん:} ちなみに、今回比較する値は"id"になっていますわ

\footnotesize \textcolor{lime}{ずんだもん:} どうして"id"なのだ？

\footnotesize \textcolor{pink}{四国めたん:} 通常"id"は重複しないので、都合が良いのですわ

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

二分木のメリット

\footnotesize \textcolor{lime}{ずんだもん:} ところで 二分木 のメリットはなんなのだ？

\footnotesize \textcolor{pink}{四国めたん:} 二分木 のメリットは検索の速さですわ

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

\footnotesize \textcolor{pink}{四国めたん:} はい、 連結リスト で"id"の検索を行う場合、先頭から順番に"id"を比較して検索しましたわ

\footnotesize \textcolor{lime}{ずんだもん:} それはしかたがないのだ

\footnotesize \textcolor{pink}{四国めたん:} これではリストの最後の方の値を検索すると、大変な時間がかかりますわ

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

\footnotesize \textcolor{pink}{四国めたん:} 二分木 では、1回の比較で右もしくは左の子ノードを捨て去ることができるので、非常に高速に検索できるのですわ

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

\footnotesize \textcolor{pink}{四国めたん:} ただ、 ルート が適切に選択されている必要はありますが...

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

\footnotesize \textcolor{pink}{四国めたん:} たとえば ルート の"id"が最小値だった場合、 連結リスト と同じになってしまうので、意味がありませんわ

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

二分木の実装

とりあえず簡単な二分木を実装してみましょう

まず、ヘッダーファイル"students.h"です

students.h
#pragma once
#ifndef _INC_STUDENTS
#define _INC_STUDENTS

#include <stdio.h>

#define NAME_SIZE (20)

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

typedef struct {
  student* proot;
} student_tree;

int init_student_tree(student_tree* ptree);

void final_student_tree(student_tree* ptree);

int insert(student_tree* ptree, unsigned int id, const char name[]);

const student* at(const student_tree* plist, unsigned int id);

#endif  // _INC_STUDENTS

今回は簡易な実装のため、ノードの削除は省いています

"student"構造体は、子ノードを2つ持つので、"pleft"と"pright"ポインタを設けています

"student_tree"構造体は、 ルート へのポインタ"proot"のみとなっています

"student_tree"構造体として設けなくても実装は可能なのですが、意外と便利なのでこのようにしています

後は初期化関数と終了関数、ノードの追加関数とデータ取得関数の宣言を追加しています

次は実装です

students.c
#include "students.h"

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

int init_student_tree(student_tree* ptree) {
  int rc = -1;
  if (ptree != NULL) {
    ptree->proot = NULL;
  }
  return rc;
}

void free_subtree(student* pnode) {
  if (pnode != NULL) {
    free_subtree(pnode->pright);
    free_subtree(pnode->pleft);
    free(pnode);
  }
  return;
}

void final_student_tree(student_tree* ptree) {
  if (ptree != NULL) {
    free_subtree(ptree->proot);
    ptree->proot = NULL;
  }
  return;
}

student* make_student_node(unsigned int id, const char name[]) {
  student* pnode = (student*)malloc(sizeof(student));
  if (pnode != NULL) {
    pnode->id = id;
    snprintf(pnode->name, NAME_SIZE, "%s", name);
    pnode->pleft = NULL;
    pnode->pright = NULL;
  }
  return pnode;
}

int insert(student_tree* ptree, unsigned int id, const char name[]) {
  int rc = -1;
  if (ptree != NULL) {
    student* pnew_node = make_student_node(id, name);
    if (pnew_node != NULL) {
      if (ptree->proot == NULL) {
        ptree->proot = pnew_node;
        rc = 0;
      } else {
        student* pnode = ptree->proot;
        student* pparent = NULL;
        while ((pnode != NULL) && (pnew_node != NULL)) {
          pparent = pnode;
          if (id < pnode->id) {
            pnode = pnode->pleft;
          } else if (id > pnode->id) {
            pnode = pnode->pright;
          } else {  // IDの重複
            free(pnew_node);
            pnew_node = NULL;
          }
        }
        if (pnew_node != NULL) {
          if (id < pparent->id) {
            pparent->pleft = pnew_node;
          } else {
            pparent->pright = pnew_node;
          }
          rc = 0;
        }
      }
    }
  }
  return rc;
}

const student* at(const student_tree* ptree, unsigned int id) {
  const student* pnode = NULL;
  if (ptree != NULL) {
    pnode = ptree->proot;
    while ((pnode != NULL) && (pnode->id != id)) {
      if (id < pnode->id) {
        pnode = pnode->pleft;
      } else if (id > pnode->id) {
        pnode = pnode->pright;
      }
    }
  }
  return pnode;
}

まず、初期化関数init_student_treeですが、単に"proot"をNULLにセットしているだけです

次に終了関数final_student_treeですが、ノードを順番に解放するためにfree_subtreeを呼び出しています

free_subtreeは再帰関数で、"pleft"および"pright"の指す子ノード以下をfree_subtreeで解放しています

なお、終了条件は渡された"pnode"がNULLの場合です

次に挿入関数insertです

まず、make_student_nodeで新たなノードを取得します

次に、各ノードの"id"と比較して、小さければ左の、大きければ右のノードに移って比較を継続します

なお、今回は"id"の重複を許可していませんので、重複した場合は挿入失敗とします

一番最後のノードでは、"id"の値により"pleft"もしくは"pright"に新規のノードを配置します

今回は 二分木 の紹介のようなものなので、ここで終わりです

ただ、もう少し実用的な 二分木 では、左右のノードの数が概ね同じになるよう、追加で木構造の組み換えを行います

最後はデータ取得関数atです

引数の"id"と同じ値を持ったノードを探して、そのノードを返します

今回はノードを削除する関数を作成していませんので、ノードは終了関数が呼ばれるまで残っています

なので、無効な領域を指す心配が少ないことから、at関数ではノードへのポインタをそのまま返しています

それではメイン関数で 二分木 を使ってみましょう

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

#include "students.h"

int main(int argc, char* argv[]) {
  student_tree tree;
  init_student_tree(&tree);
  insert(&tree, 3, "高橋翠");
  insert(&tree, 2, "鈴木陽翔");
  insert(&tree, 1, "佐藤紬");
  insert(&tree, 5, "伊藤凛");
  insert(&tree, 4, "田中朝陽");
  insert(&tree, 6, "渡辺暖");

  for (unsigned int i = 1; i <= 6; i++) {
    const student* pperson = at(&tree, i);
    printf("学生番号: %d, 名前: %s\n", pperson->id, pperson->name);
  }

  final_student_tree(&tree);

  return 0;
}

初期化関数を呼び出した後、insert関数でデータを追加しています

ただし、順番は"id"順ではありません

今回のようなinsert関数では、"id"順にデータを挿入すると、 連結リスト と同じように直線的なリストとなってしまいます

そこで左右のノード数が概ね均等になるように、"id"の順番を入れ替えて挿入しています

二分木2

後は"id"を順番に指定してデータを取得し、コンソールに表示しています

二分木3

まとめ

\footnotesize \textcolor{pink}{四国めたん:} おつかれさまでした

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

\footnotesize \textcolor{pink}{四国めたん:} 以上で 連結リストのバリエーション を終わります

Discussion