リスト構造

順序関係+頻繁に追加・削除があるデータ向け
リスト
スケジュール表のように、順序関係があり、頻繁に追加・削除があるような場合は、データ構造としてリストを用いるといい。
Python や C++は、言語仕様としてリストが用意されている。PHP はリストを備えていないが、ここでは双方向リストを扱うことができるユーザー・クラスを用意した。また、C言語では構造体を使ったリストを紹介する。

サンプル・プログラム

配列の弱点

今回は、スケジュール表のデータ構造を考えてみる。

たとえば、日時を添字として連想配列で扱うのであれば

$a['2018-06-18T13:00+09:00'] = '打ち合わせ';


のようなデータ構造が考えられる。

しかし、配列では添字が一意でなければならない(重複できない)という制約がある。予定をブッキングさせるような使い方があるとすると、要素が上書きされてしまう配列は使えない。
また、このままでは、開始・終了時刻がある予定を表現できない。

そこで、下記のような 2 次元連想配列にしてみたらどうだろうか。

$a[1]['start'] = '2018-06-18T13:00+09:00';
$a[1]['finish'] = '2018-06-18T14:00+09:00';
$a[1]['title'] = '打ち合わせ';


この場合、スケジュールを追加をしていくと、添字がどんどん増え、要素の順序は日時順ではなくなってしまう。これでは、日時順にスケジュール表を表示するたびに、配列の先頭から末尾までデータを取り出してソートしなければならない。データが増えれば増えるほど、処理系への負荷が増す。スケジュールを削除した場合も同様である。

つまり、次のような性質のデータに対しては、データ構造として配列を用いるのは適当ではない。こういうときは、リストというデータ構造を用いる。
  1. データに順序関係がある。
  2. データの追加・削除が頻繁にある。

リスト構造

リスト
リストは、添字のない 1 次元配列と考えてもらえばいい。
リストには先頭(root)と末尾(tail)があり、その間に複数の要素node)が数珠つなぎに連なっているデータ構造である。
要素には、数や文字列といった属性のデータを直接入れる場合もあるし、配列などの他のデータ構造を入れることもできる。リストの要素としてリストを入れることも可能だ。
上図のように、node にデータ構造がぶら下がっているという形をイメージしてもらえばいいだろう。

リストを扱える処理系では、あわせて要素の追加・削除のための関数やメソッドが用意されている。これにより、順序関係を維持したまま、頻繁に要素の追加・削除することができるようになっている。

ここでは Python のメソッドを例に紹介する。
要素の追加は 2種類ある。リストの末尾に追加する append と、リストの途中に挿入する insert である。

append のイメージ
append - リスト
append だけであれば、配列要素を追加するのと変わりない。
Python では、便宜上、リスト要素に 1,2,3‥‥という番号が振られており、これを頼りに insert を行うことができる。

insert のイメージ
insert - リスト
常にスケジュール開始日時の順に insert していくようにプログラムを作ることで、日時の順序関係を維持したままスケジュールデータを追加していくことができる。
プログラム例は後述するが、このため実際の追加プログラムはやや複雑になり、append に比べて実行時間を要する。だが、スケジュール表のように、データの追加より参照回数の方が多い場合は、参照の際に並べ替えを行う配列より合理的である。

要素の削除には del メソッド を用いる。削除する要素のリンクを切り、その隣の要素とリンクし直す。

delete のイメージ
delete - リスト

Pythonによるリスト

0011: # データ(1行目:ラベル,列:タブ区切り,行:改行区切り)
0012: data = """
0013: start    finish    title
0014: 2018-06-18T13:00+09:00    2018-06-18T14:00+09:00    打ち合わせ
0015: 2018-06-19T15:00+09:00    2018-06-19T16:30+09:00    来客
0016: 2018-06-21T09:00+09:00    2018-06-21T10:00+09:00    事務作業
0017: 
""".strip()

Python を使ってリストを扱うプログラムを作ってみる。
スケジュール・データは、「ヒアドキュメント」を使って用意する。

0049: """
0050:  * スケジュール・リストにスケジュールを挿入
0051:  * @param dict d     スケジュール
0052:  * @param list items スケジュール・リスト
0053:  * @return なし
0054: 
"""
0055: def insertSchedule(ditems):
0056:     for ia in enumerate(items):
0057:         if (a['start'] >= d['start']):
0058:             items.insert(id)
0059:             return(0)
0060:     items.append(d)
0061:     return(0)
0062: 
0063: """
0064:  * スケジュール・リストからスケジュールを削除
0065:  * @param dict d     スケジュール
0066:  * @param list items スケジュール・リスト
0067:  * @return なし
0068: 
"""
0069: def deleteSchedule(ditems):
0070:     for ia in enumerate(items):
0071:         if ((a['start'] == d['start']) & (a['finish'] == d['finish'])):
0072:             items.pop(i)
0073:             break

insertSchedule は、予定開始の大小を比較してスケジュール(要素)を insert する。
deletSchedule は、予定開始と終了が合致するスケジュール(要素)を delete する。
リスト構造を使ってスケジュール・データを扱う
プログラムの実行結果は左図の通りである。
まず、ヒアドキュメントのスケジュール一覧を表示する。
続いて、スケジュール(要素)を 1 つ append する。リストの末尾に追加するから、日時の順番が狂ってしまっている。
次に、スケジュール(要素)を 1 つ insert する。日時の順番は正しく並んでいる。
最後に、insert したスケジュールを delete する。

PHPによるリスト

PHPによるリスト構造
PHP は Python と異なり、文法としてリスト構造が用意されていない。
そこで、リストを扱うためのクラス pahooList を用意した。1 つのリストが、1 つの pahooList オブジェクトに対応する。pahooList クラスの中では、2 次元連想配列を用いてリスト構造を実現している。

リスト構造のイメージを左図に示す。クラスは外部ファイル "pahooDataStructure.php" に分離している。

0767: // pahooListクラス ==========================================================
0768: class pahooList {
0769:     const ANCHOR = 0;                //先頭または末尾の識別
0770:     public $root;                    //インデックス:リストの先頭
0771:     public $tail;                    //インデックス:リストの末尾
0772:     public $imax;                    //インデックス:最大値
0773:     public $pointer;             //ポインタ
0774:     public $list;                    //リストの実体としての配列
0775:     public $error$errmsg;      //エラーフラグ,エラーメッセージ(未使用)
0776: 
0777: /**
0778:  * コンストラクタ
0779:  * @param なし
0780:  * @return なし
0781: */
0782: function __construct() {
0783:     $this->root = 1;
0784:     $this->tail = 1;
0785:     $this->imax = 1;
0786:     $this->pointer = self::ANCHOR;
0787:     $this->error  = FALSE;
0788:     $this->errmsg = '';
0789:     $this->list = array();
0790: }
0791: 
0792: /**
0793:  * デストラクタ
0794:  * @param なし
0795:  * @return なし
0796: */
0797: function __destruct() {
0798:     unset($this->list);
0799: }
0800: 
0801: /**
0802:  * 現在のポインタが先頭を指すかどうかを判定する
0803:  * @param なし
0804:  * @return bool TRUE:先頭である/FALSE:先頭でない
0805: */
0806: function isroot() {
0807:     if (! isset($this->list[$this->pointer]))    return TRUE;
0808:     else if ($this->pointer == self::ANCHOR)   return TRUE;
0809:     else if ($this->pointer == $this->root)   return TRUE;
0810:     return FALSE;
0811: }
0812: 
0813: /**
0814:  * 現在のポインタが末尾を指すかどうかを判定する
0815:  * @param なし
0816:  * @return bool TRUE:末尾である/FALSE:末尾でない
0817: */
0818: function istail() {
0819:     if (! isset($this->list[$this->pointer]))    return TRUE;
0820:     return ($this->pointer == self::ANCHOR);
0821: }
0822: 
0823: /**
0824:  * 現在のポインタが指す要素が存在するかどうかを判定する
0825:  * @param なし
0826:  * @return bool TRUE:存在する/FALSE:存在しない
0827: */
0828: function exist() {
0829:     $i = $this->pointer;
0830:     return ($i == self::ANCHOR) ? FALSE : isset($this->list[$i]);
0831: }
0832: 
0833: /**
0834:  * 現在のポインタが指す要素を1つ取り出す
0835:  * @param なし
0836:  * @return mixed 取り出した要素/NULL:要素がない
0837: */
0838: function get() {
0839:     $i = $this->pointer;
0840:     return $this->exist() ? $this->list[$i]['__item'] : NULL;
0841: }
0842: 
0843: /**
0844:  * リストの先頭にポインタをセットする
0845:  * @param なし
0846:  * @return int 先頭のインデックス
0847: */
0848: function moveRoot() {
0849:     return $this->pointer = $this->root;
0850: }
0851: 
0852: /**
0853:  * リストの末尾にポインタをセットする
0854:  * @param なし
0855:  * @return int 末尾のインデックス
0856: */
0857: function moveTail() {
0858:     return $this->pointer = $this->tail;
0859: }
0860: 
0861: /**
0862:  * 任意のインデックスをポインタにセットする
0863:  * @param int $i  インデックス
0864:  * @return int セットしたインデックス/0:対応する要素がない
0865: */
0866: function setPointer($i) {
0867:     return isset($this->list[$i]) ? ($this->pointer = $i) : self::ANCHOR;
0868: }
0869: 
0870: /**
0871:  * 次の要素のインデックスを返し、ポインタを進める
0872:  * @param なし
0873:  * @return int 前の要素のインデックス/0:次はない
0874: */
0875: function moveNext() {
0876:     if ($this->istail()) return self::ANCHOR;   //リストの末尾
0877:     if (! $this->exist()) return self::ANCHOR;   //要素がない
0878:     $i = $this->list[$this->pointer]['__next']; //次のインデックス
0879:     $this->pointer = $i;                          //ポインタにセット
0880: 
0881:     return $this->pointer;
0882: }
0883: 
0884: /**
0885:  * 前の要素のインデックスを返し、ポインタを戻す
0886:  * @param なし
0887:  * @return int 前の要素のインデックス/0:前はない
0888: */
0889: function moveForward() {
0890:     if ($this->isroot()) return self::ANCHOR;   //リストの先頭
0891:     if (! $this->exist()) return self::ANCHOR;   //要素がない
0892:     $i = $this->list[$this->pointer]['__forward']; //前のインデックス
0893:     $this->pointer = $i;                          //ポインタにセット
0894:     
0895:     return $this->pointer;
0896: }

クラスの中で 2 次元連想配列 $list[$i][xxxx] を用意する。
$i は Python のリストでいうところの「インデックス」である。PHP は配列の途中に要素を挿入する機能を備えていないため、個々の配列の 2 次元目に ['__next'] を用意し、次の要素のインデックスを代入しておく。そうすることで、インデックスが小さい順に並んでいなくても、root から要素を順にたどることができるようにした。
インデックスは自然数とし、先頭root と末尾 tail はゼロ(定数 ANCHOR に定義)としている。
要素の実体は、2 次元目 ['__item'] に代入する。PHP は、配列の要素として代入できるデータ属性が制限されていない。整数でも文字列でも配列でも構わない。また、リストの要素の 1 つ 1 つを異なるデータ属性にすることもできる。
削除したインデックスは再利用せず、追加・挿入を繰り返すたびにインデックスを増やしていく。インデックスの最大値は $imax に格納する。また、先頭のインデックスは $root に、末尾のインデックスは $tailに格納することでリスト構造を管理する。

リスト構造は、先頭から末尾へ向かってたどるのが基本だが(これを単方向リストと呼ぶ)、pahooList クラスのリスト構造は、末尾から先頭へ遡っていくことも可能にした。これを双方向リストと呼ぶ。2 次元目に前の要素のインデックスを格納する ['__forward'] を用意することで実現した。

リスト構造は添字のない配列と書いた。そこで、pahooList クラスのリストを使う際にインデックスを意識させないように、クラス内部のポインタ $pointer で処理中の要素を指し示すようにして、次のメソッドを用意した。
メソッド機能
isroot()現在のポインタが先頭を指すかどうかを判定する
istail()現在のポインタが末尾を指すかどうかを判定する
exist()現在のポインタが指す要素が存在するかどうかを判定する
get()現在のポインタが指す要素を1つ取り出す
moveRoot()リストの先頭にポインタをセットする
moveTail()リストの末尾にポインタをセットする
setPointer($i)任意のインデックスをポインタにセットする
moveNext()次の要素のインデックスを返し、ポインタを進める
moveForward()前の要素のインデックスを返し、ポインタを戻す
append($data)リストの末尾に要素を1つ追加する
insert($data)現在のポインタ位置(ポインタが示す要素の前)に要素を1つ挿入する
delete()現在のポインタが指す要素を1つ削除する
delete()現在のポインタが指す要素を1つ削除する
len()リストの長さ(要素数)を返す

 

PHP による append のイメージ
append - PHPによるリスト

0898: /**
0899:  * リストの末尾に要素を1つ追加する
0900:  * @param mixed $data 追加する要素
0901:  * @return int 追加したデータのインデックス
0902: */
0903: function append($data) {
0904:     //リスト長ゼロの時の追加
0905:     if ($this->len() == 0) {
0906:         $this->list[$this->imax]['__forward'] = self::ANCHOR;
0907:         $this->list[$this->imax]['__next']    = self::ANCHOR;
0908:     //それ以外の追加
0909:     } else {
0910:         $this->imax++;      //新しいインデックス
0911:         $this->list[$this->imax]['__forward'] = $this->tail;
0912:         $this->list[$this->imax]['__next']    = self::ANCHOR;
0913:         $this->list[$this->tail]['__next']    = $this->imax; //末尾の更新
0914:         $this->tail = $this->imax;
0915:     }
0916:     //要素の実体を追加
0917:     $this->list[$this->imax]['__item'] = $data;
0918:     //ポインタを更新
0919:     $this->pointer = $this->imax;
0920: 
0921:     return $this->imax;
0922: }

メソッド append は、リスト長がゼロと、そうでない場合とで処理が異なる。リスト長がゼロでないときは、イメージ図の通り、直前の要素の __next を更新する。
PHP による insert のイメージ
insert - PHPによるリスト

0924: /**
0925:  * 現在のポインタ位置(ポインタが示す要素の前)に要素を1つ挿入する
0926:  * @param mixed $data 挿入する要素
0927:  * @return int 挿入した要素のインデックス
0928: */
0929: function insert($data) {
0930:     $i = $this->pointer;
0931:     //末尾に挿入
0932:     if ($i == self::ANCHOR) {
0933:         $tail = $this->append($data);
0934:         $this->tail = $tail;                  //末尾の更新
0935:     //途中に挿入
0936:     } else {
0937:         $this->imax++;                              //新しいインデックス
0938:         $forward = $this->list[$i]['__forward'];    //前のインデックス
0939:         $this->list[$this->imax]['__forward'] = $forward;
0940:         $this->list[$this->imax]['__next']    = $i;
0941:         $this->list[$this->imax]['__item']    = $data;
0942:         $this->list[$i]['__forward']          = $this->imax; //次の要素を更新
0943:         if ($i == $this->root) {
0944:             $this->root = $this->imax;                         //先頭を更新
0945:         } else {
0946:             $this->list[$forward]['__next']   = $this->imax;  //前の要素を更新
0947:         }
0948:     }
0949:     return $this->imax;
0950: }

メソッド insert は、末尾に挿入する場合は append を呼び出す。それ以外の場合は、イメージ図の通り、直前の要素の __next を更新し、直後の要素の __forward を更新する。
リスト構造を持たない処理系では、このクラスを移植してみてほしい。
連想配列が利用できない場合は、2 次元目の添字を自然数に置き換えてみてほしい。

0011: //データ構造クラス
0012: require_once('pahooDataStructure.php');
0013: 
0014: //データ(1行目:ラベル,列:タブ区切り,行:改行区切り)
0015: $data =<<< EOT
0016: start    finish    title
0017: 2018-06-18T13:00+09:00    2018-06-18T14:00+09:00    打ち合わせ
0018: 2018-06-19T15:00+09:00    2018-06-19T16:30+09:00    来客
0019: 2018-06-21T09:00+09:00    2018-06-21T10:00+09:00    事務作業
0020: 
0021: EOT;
0022: 
0023: /**
0024:  * CSV形式テキストを読み込んで、リストに展開する
0025:  * @param string    $data   CSV形式テキスト(列:タブ,行:改行)
0026:  * @param pahooList $labels ラベルを格納するリスト(1行目のテキスト)
0027:  * @param pahooList $items  要素を格納するリスト
0028:  * @return int 要素数
0029: */
0030: function parseList($data, &$labels, &$items) {
0031:     $item = array();
0032:     $rec = preg_split("/\n/ui", $data);       //行に分解
0033:     $cnt = 0;
0034:     foreach ($rec as $str) {
0035:         $str = trim($str);
0036:         if (mb_strlen($str) == 0)   continue;
0037:         $col = preg_split("/\t/ui", $str);        //列に分解
0038:         if ($cnt == 0) {                     //ラベルを格納
0039:             foreach ($col as $key=>$val) {
0040:                 $labels->append(trim($val));
0041:             }
0042:         } else {                              //要素を格納
0043:             $labels->moveRoot();
0044:             foreach ($col as $key=>$val) {
0045:                 $label = $labels->get();
0046:                 $item[$label] = trim($val);
0047:                 $labels->moveNext();
0048:             }
0049:             $items->append($item);
0050:         }
0051:         $cnt++;
0052:     }
0053:     return $cnt;
0054: }
0055: 
0056: /**
0057:  * スケジュール・リストにスケジュールを挿入
0058:  * @param array     $d     スケジュール
0059:  * @param pahooList $items スケジュール・リスト
0060:  * @return なし
0061: */
0062: function insertSchedule($d, &$items) {
0063:     $items->moveRoot();                       //リストの先頭へ
0064:     while (! $items->istail()) {               //リスト末尾まで繰り返し
0065:         $a = $items->get();
0066:         if ($a['start'] >= $d['start']) {      //開始日時が大きければ
0067:             $items->insert($d);               //要素を挿入
0068:             return;
0069:         }
0070:         $items->moveNext();                   //次の要素へ
0071:     }
0072:     $items->append($d);                       //そうでなければ末尾に追加
0073: }
0074: 
0075: /**
0076:  * スケジュール・リストからスケジュールを削除
0077:  * @param array     $d     スケジュール
0078:  * @param pahooList $items スケジュール・リスト
0079:  * @return なし
0080: */
0081: function deleteSchedule($d, &$items) {
0082:     $items->moveRoot();                       //リストの先頭へ
0083:     while (! $items->istail()) {               //リスト末尾まで繰り返し
0084:         $a = $items->get();
0085:         if (($a['start'] == $d['start']) &&   //開始・終了日時が等しければ
0086:             ($a['finish'] == $d['finish'])) {
0087:             $items->delete();                 //要素を削除
0088:             return;
0089:         }
0090:         $items->moveNext();                   //次の要素へ
0091:     }
0092: }
0093: 
0094: /**
0095:  * スケジュール表示
0096:  * @param pahooList $items スケジュール・リスト
0097:  * @return なし
0098: */
0099: function printSchedule(&$items) {
0100:     $items->moveRoot();                       //リストの先頭へ
0101:     while (! $items->istail()) {               //リスト末尾まで繰り返し
0102:         $a = $items->get();                   //要素を取り出して表示
0103:         printf('%s - ', date('Y/m/d H:i', strtotime($a['start'])));
0104:         printf('%s  ',  date('H:i', strtotime($a['finish'])));
0105:         printf("%s\n",  $a['title']);
0106:         $items->moveNext();                   //次の要素へ
0107:     }
0108: }
0109: 
0110: // メイン・プログラム ======================================================
0111: // リストへ読み込み
0112: $labels = new pahooList();                       //リストを用意
0113: $items  = new pahooList();
0114: $cnt = parseList($data$labels$items);        //元データの読み込み
0115: 
0116: // 出力(1)
0117: printf("\n*original\n");
0118: printSchedule($items);
0119: 
0120: $b = array('start'=>'2018-06-20T15:00+09:00', 'finish'=>'2018-06-20T16:00+09:00', 'title'=>'報告会');
0121: $items->append($b);                           //スケジュールの追加
0122: 
0123: // 出力(2)
0124: printf("\n*append\n");
0125: printSchedule($items);
0126: 
0127: deleteSchedule($b$items);                  //追加したスケジュールを削除
0128: insertSchedule($b$items);                  //スケジュールの挿入
0129: 
0130: // 出力(3)
0131: printf("\n*insert\n");
0132: printSchedule($items);

これが、Python から移植したスケジュール・プログラム "dt03-21-02.php" である。
PHP では for 文によってリストを扱うことができない。代わりに、moveRoot メソッドで先頭に移動し、末尾まで(istail メソッドの結果)while ループを回すことによって、スケジュールの追加、削除、一覧表示を実現している。

C++によるリスト

リスト構造
C++には双方向リストクラス list が用意されている。
ここでは、最初に紹介したリスト構造にしたがい、list の要素として連想配列 map を代入する形にしたプログラムが "dt03-21-03.cpp" である。

0044: /**
0045:  * CSV形式テキストを読み込んで、リストに展開する
0046:  * @param char      *data  CSV形式テキスト(列:タブ,行:改行)
0047:  * @param vector    labels ラベルを格納(1行目のテキスト)
0048:  * @param list<map> items  要素を格納するリスト
0049:  * @return int    要素数
0050: **/
0051: int parseList(char *datavector<string> &labelslist<map<string,string>> &items) {
0052:     map<string,string> *item;
0053:     int cnt = 0;
0054:     for (string &rec : split(data, '\n')) {              //行に分解
0055:         if (rec.size() > 0) {
0056:             if (cnt == 0) {                              //ラベルを格納
0057:                 for (string &col : split(rec, '\t')) {       //列に分解
0058:                     labels.push_back(col);
0059:                 }
0060:             } else {                                      //要素を格納
0061:                 item = new map<string,string>;
0062:                 int i = 0;
0063:                 for (string &col : split(rec, '\t')) {       //列に分解
0064:                     item->insert(make_pair(labels[i], col));
0065:                     i++;
0066:                 }
0067:                 items.push_back(*item);                   //リストに加える
0068:             }
0069:             cnt = cnt + 1;
0070:         }
0071:     }
0072:     return(cnt);
0073: }

まず、CSV 形式テキストを読み込んでリストに展開する parseList 関数だが、ラベルは動的配列クラス vector に代入してゆく。
要素部分は、まず、タブ区切りで分解し、連想配列 map クラスへ格納し、それをリストクラス list へ格納してゆく。

0075: /**
0076:  * スケジュール・リストにスケジュールを挿入
0077:  * @param map d      スケジュール
0078:  * @param list<map>  items スケジュール・リスト
0079:  * @return なし
0080: **/
0081: void insertSchedule(map<string,string> &dlist<map<string,string>> &items) {
0082:     list<map<string,string>>::iterator a;
0083:     for (a = items.begin(); a != items.end(); a++) {
0084:         if (a->at("start") >= d["start"]) {
0085:             items.insert(ad);
0086:             break;
0087:         }
0088:     }
0089: }
0090: 
0091: /**
0092:  * スケジュール・リストからスケジュールを削除
0093:  * @param map d      スケジュール
0094:  * @param list<map>  items スケジュール・リスト
0095:  * @return なし
0096: **/
0097: void deleteSchedule(map<string,string> &dlist<map<string,string>> &items) {
0098:     list<map<string,string>>::iterator a;
0099:     for (a = items.begin(); a != items.end(); a++) {
0100:         if ((a->at("start") == d["start"]) && (a->at("finish") == d["finish"])) {
0101:             items.erase(a);
0102:             break;
0103:         }
0104:     }
0105: }
0106: 
0107: /**
0108:  * スケジュール表示
0109:  * @param list<vector> items スケジュール・リスト
0110:  * @return なし
0111: **/
0112: void printSchedule(list<map<string,string>> &items) {
0113:     list<map<string,string>>::iterator a;
0114:     for (a = items.begin(); a != items.end(); a++) {
0115:         cout << a->at("start") << " - " << a->at("finish") << " " << a->at("title") << endl;
0116:     }
0117: }
0118: 
0119: // メイン・プログラム ======================================================
0120: int main() {
0121:     vector<stringlabels;
0122:     list<map<string,string>> items;
0123: 
0124:     parseList(datalabelsitems);
0125: 
0126:     //出力(1)
0127:     cout << endl << "*original" << endl;
0128:     printSchedule(items);
0129: 
0130:     //追加データ
0131:     map<string,stringb = {{"start", "2018-06-20T15:00+09:00"}, {"finish", "2018-06-20T16:00+09:00"}, {"title", "報告会"}};
0132:     items.push_back(b);
0133: 
0134:     //出力(2)
0135:     cout << endl << "*append" << endl;
0136:     printSchedule(items);
0137: 
0138:     deleteSchedule(bitems);
0139:     insertSchedule(bitems);
0140: 
0141:     //出力(3)
0142:     cout << endl << "*insert" << endl;
0143:     printSchedule(items);
0144: 
0145:     return (0);
0146: }

それ以外の部分は PHP プログラム "dt03-21-02.php" を忠実に移植した。
実行結果は下図の通りである。ISO8601 フォーマットを処理できる適当なクラスが見当たらなかったので、日時はオリジナルのままを表示している。
リスト構造を使ってスケジュール・データを扱う

C言語によるリスト

C言語によるリスト構造
C言語(C99)もリスト構造をもたない。クラスを使うことができないので、上図のような構造体を使ってリストを実現することにした。連想配列も使うことができないので、要素として代入できるのは、今回のスケジュール表(開始日時、終了日時、タイトルの 3 つの文字列)という形に限定した。プログラムが "dt03-21-05.c" である。

0020: // スケジュールを格納する構造体=リスト
0021: struct schedule {
0022:     char start[MAXLEN_STRING];     // 開始日時
0023:     char finish[MAXLEN_STRING];    // 完了日時
0024:     char title[MAXLEN_STRING];     // 予定
0025:     struct schedule *forward;        // 前の要素を指すポインタ
0026:     struct schedule *next;           // 次の要素を指すポインタ
0027: };
0028: 
0029: struct schedule *rootList;           /* ルート */
0030: struct schedule *ptrList;            /* ポインタ */
0031: 
0032: /**
0033:  * リストを初期化する
0034:  * @return struct schedule* ルートへのポインタ
0035: **/
0036: struct schedule *initList(void) {
0037:     rootList = (struct schedule *)malloc(sizeof(struct schedule));
0038:     rootList->forward = NULL;
0039:     rootList->next    = NULL;
0040:     return rootList;
0041: }

構造体 struct schedule がリスト構造となっている。
要素を 1 つ格納するには、構造体 struct schedule を 1 つ malloc 関数で確保してやる必要がある。C++に比べると、自力でメモリ管理をしなければならないので、どうしてもプログラムが長くなってしまう。

0043: /**
0044:  * 現在のポインタが先頭を指すかどうかを判定する
0045:  * @param なし
0046:  * @return bool TRUE:先頭である/FALSE:先頭でない
0047: */
0048: bool isroot() {
0049:     return (ptrList == rootList);
0050: }
0051: 
0052: /**
0053:  * 現在のポインタが末尾を指すかどうかを判定する
0054:  * @param なし
0055:  * @return bool TRUE:末尾である/FALSE:末尾でない
0056: */
0057: bool istail() {
0058:     return (ptrList->next == NULL);
0059: }
0060: 
0061: /**
0062:  * リストの先頭にポインタをセットする
0063:  * @param なし
0064:  * @return なし
0065: */
0066: void moveRoot(void) {
0067:     ptrList = rootList;
0068: }
0069: 
0070: /**
0071:  * 次の要素のインデックスを返し、ポインタを進める
0072:  * @param なし
0073:  * @return int 前の要素のインデックス/0:次はない
0074: */
0075: void moveNext(void) {
0076:     if (ptrList->next != NULL)    ptrList = ptrList->next;
0077: }
0078: 
0079: /**
0080:  * リストの末尾にポインタをセットする
0081:  * @param なし
0082:  * @return int 末尾のインデックス
0083: */
0084: void moveTail(void) {
0085:     moveRoot();
0086:     while (! istail())   moveNext();
0087: }
0088: 
0089: /**
0090:  * リストの長さ(要素数)を返す
0091:  * @param なし
0092:  * @return int リストの長さ
0093: */
0094: size_t listlen(void) {
0095:     size_t l = 0;
0096:     ptrList = rootList;              //リストの先頭へ
0097:     while (ptrList->next != NULL) {    //リスト末尾まで繰り返し
0098:         l++;
0099:         ptrList++;                     //次の要素へ
0100:     }
0101:     if (strlen(ptrList->start) > 0)  l++;
0102:     return l;
0103: }
0104: 
0105: /**
0106:  * リストの末尾に要素を1つ追加する
0107:  * @param char *start  開始日時
0108:  * @param char *finish 終了日時
0109:  * @param char *title  予定
0110:  * @return なし
0111: */
0112: void append(char *startchar *finishchar *title) {
0113:     //リスト長ゼロの時の追加
0114:     if (listlen() == 0) {
0115:         ptrList = rootList;
0116:         strcpy(ptrList->start,  start);
0117:         strcpy(ptrList->finishfinish);
0118:         strcpy(ptrList->title,  title);
0119: 
0120:     //それ以外の追加
0121:     } else {
0122:         struct schedule *p = (struct schedule *)malloc(sizeof(struct schedule));
0123:         strcpy(p->start,  start);
0124:         strcpy(p->finishfinish);
0125:         strcpy(p->title,  title);
0126:         moveTail();
0127:         ptrList->next = p;
0128:         p->forward = ptrList;
0129:         p->next    = NULL;
0130:         ptrList = p;
0131:     }
0132: }
0133: 
0134: /**
0135:  * 現在のポインタ位置(ポインタが示す要素の前)に要素を1つ挿入する
0136:  * @param char *start  開始日時
0137:  * @param char *finish 終了日時
0138:  * @param char *title  予定
0139:  * @return なし
0140: */
0141: void insert(char *startchar *finishchar *title) {
0142:     struct schedule *forward = ptrList->forward;
0143: 
0144:     struct schedule *p = (struct schedule *)malloc(sizeof(struct schedule));
0145:     strcpy(p->start,  start);
0146:     strcpy(p->finishfinish);
0147:     strcpy(p->title,  title);
0148: 
0149:     if (forward == NULL)    rootList = p;        //ルートに挿入
0150:     else                    forward->next = p;
0151:     ptrList->forward = p;
0152:     p->next = ptrList;
0153:     p->forward = forward;
0154:     ptrList = p;
0155: }
0156: 
0157: /**
0158:  * 現在のポインタが指す要素を1つ削除する
0159:  * @param なし
0160:  * @return なし
0161: */
0162: void delete(void) {
0163:     if (ptrList == NULL)    return;
0164: 
0165:     struct schedule *p = ptrList;
0166:     struct schedule *forward = ptrList->forward;
0167:     struct schedule *next    = ptrList->next;
0168:     ptrList = next;
0169:     if (ptrList != NULLptrList->forward = forward;
0170:     if (forward != NULLforward->next = ptrList;
0171:     free(p);
0172: }

それ以外の部分は、PHP プログラム "dt03-21-02.php" を比較的充実に移植した。
実行結果は下図の通りである。ISO8601 フォーマットを処理する関数を用意しなかったこと、日本語文字列(UTF-8)を処理することが面倒であることから、データは全て英数字にしてある。
リスト構造を使ってスケジュール・データを扱う
(この項おわり)
header