リスト構造

順序関係+頻繁に追加・削除があるデータ向け
リスト
スケジュール表のように、順序関係があり、頻繁に追加・削除があるような場合は、データ構造としてリストを用いるといい。
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によるリスト

# データ(1行目:ラベル,列:タブ区切り,行:改行区切り)
data = """
start	finish	title
2018-06-18T13:00+09:00	2018-06-18T14:00+09:00	打ち合わせ
2018-06-19T15:00+09:00	2018-06-19T16:30+09:00	来客
2018-06-21T09:00+09:00	2018-06-21T10:00+09:00	事務作業
""".strip()
Pythonを使ってリストを扱うプログラムを作ってみる。
スケジュール・データは、「ヒアドキュメント」を使って用意する。
"""
 * スケジュール・リストにスケジュールを挿入
 * @param	dict d     スケジュール
 * @param	list items スケジュール・リスト
 * @return	なし
"""
def insertSchedule(d, items):
	for i, a in enumerate(items):
		if (a['start'] >= d['start']):
			items.insert(i, d)
			return(0)
	items.append(d)
	return(0)

""" * スケジュール・リストからスケジュールを削除 * @param dict d スケジュール * @param list items スケジュール・リスト * @return なし """ def deleteSchedule(d, items): for i, a in enumerate(items): if ((a['start'] == d['start']) & (a['finish'] == d['finish'])): items.pop(i) break
insertSchedule は、予定開始の大小を比較してスケジュール(要素)を insert する。
deletSchedule は、予定開始と終了が合致するスケジュール(要素)を delete する。
リスト構造を使ってスケジュール・データを扱う
プログラムの実行結果は左図の通りである。
まず、ヒアドキュメントのスケジュール一覧を表示する。
続いて、スケジュール(要素)を1つ append する。リストの末尾に追加するから、日時の順番が狂ってしまっている。
次に、スケジュール(要素)を1つ insert する。日時の順番は正しく並んでいる。
最後に、insert したスケジュールを delete する。

PHPによるリスト

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

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

 767:     else if ($hour == 12)   $res = 12;
 768:     else                    $res = $hour % 12;
 769:     return $res;
 770: }
 771: 
 772: /**
 773:  * 時差を文字列に変換
 774:  * @param   double $tdiff  時差(秒数)
 775:  * @return  string 時差を表す文字列
 776: */
 777: function tdiff2str($tdiff) {
 778:     list($hour, $min, $sec) = $this->sec2HMS(abs($tdiff));
 779:     return sprintf("%s%02d:%02d", ($tdiff >0? '+' : '-', $hour, $min);
 780: }
 781: 
 782: /**
 783:  * 日時フォーマットで文字列に変換
 784:  * @param   string $format 日時フォーマット
 785:  *              date()のサブセットで利用可能書式は
 786:  *              ‥‥Y,y,n,m,j,d,G,H,a,A,g,h,i,s,Z,c
 787:  * @return  string 変換後の文字列
 788: */
 789: function date($format) {
 790:     $res = '';
 791:     $i = 0;
 792:     while ($i < mb_strlen($format)) {
 793:         $c = mb_substr($format, $i, 1);
 794:         switch ($c) {
 795:             case 'Y':   $cc = sprintf('%d', $this->year);               break;
 796:             case 'y':   $cc = sprintf('%2d', $this->year);              break;
 797:             case 'n':   $cc = sprintf('%d', $this->month);              break;
 798:             case 'm':   $cc = sprintf('%02d', $this->month);            break;
 799:             case 'j':   $cc = sprintf('%d', $this->day);                break;
 800:             case 'd':   $cc = sprintf('%02d', $this->day);              break;
 801:             case 'G':   $cc = sprintf('%d', $this->hour);               break;
 802:             case 'H':   $cc = sprintf('%02d', $this->hour);         break;
 803:             case 'a':   $cc = $this->hour < 12 ? 'am' : 'pm';            break;
 804:             case 'A':   $cc = $this->hour < 12 ? 'AM' : 'PM';            break;
 805:             case 'g':
 806:                 $cc = sprintf('%d', $this->h24to12($this->hour));       break;
 807:             case 'h':
 808:                 $cc = sprintf('%02d', $this->h24to12($this->hour)); break;
 809:             case 'i':   $cc = sprintf('%02d', $this->minuite);          break;
 810:             case 's':   $cc = sprintf('%02d', $this->second);           break;
 811:             case 'Z':   $cc = sprintf('%d', $this->tdiff);              break;
 812:             case 'c':
 813:                 $cc = sprintf('%d-%02d-%02dT%02d:%02d:%02d%s',
 814:                     $this->year, $this->month, $this->day,
 815:                     $this->hour, $this->minuite, $this->second,
 816:                     $this->tdiff2str($this->tdiff));
 817:                 break;
 818:             case 'P':
 819:                 $hh = $this->tdiff / 3600;
 820:                 $mm = abs($this->tdiff - $hh * 3600) / 60;
 821:                 $cc = sprintf('%02d:%02d', $hh, $mm);
 822:                 break;
 823:             default:    $cc = $c;                                       break;
 824:         }
 825:         $i++;
 826:         $res .$cc;
 827:     }
 828:     return $res;
 829: }
 830: 
 831: // End of Class
 832: }
 833: 
 834: // pahooListクラス ==========================================================
 835: class pahooList {
 836:     const ANCHOR = 0;               //先頭または末尾の識別
 837:     public $root;                   //インデックス:リストの先頭
 838:     public $tail;                   //インデックス:リストの末尾
 839:     public $imax;                   //インデックス:最大値
 840:     public $pointer;                //ポインタ
 841:     public $list;                   //リストの実体としての配列
 842:     public $error, $errmsg;     //エラーフラグ,エラーメッセージ(未使用)
 843: 
 844: /**
 845:  * コンストラクタ
 846:  * @param   なし
 847:  * @return  なし
 848: */
 849: function __construct() {
 850:     $this->root = 1;
 851:     $this->tail = 1;
 852:     $this->imax = 1;
 853:     $this->pointer = self::ANCHOR;
 854:     $this->error  = FALSE;
 855:     $this->errmsg = '';
 856:     $this->list = array();
 857: }
 858: 
 859: /**
 860:  * デストラクタ
 861:  * @param   なし
 862:  * @return  なし
 863: */
 864: function __destruct() {
 865:     unset($this->list);
 866: }
 867: 
 868: /**
 869:  * 現在のポインタが先頭を指すかどうかを判定する
 870:  * @param   なし
 871:  * @return  bool TRUE:先頭である/FALSE:先頭でない
 872: */
 873: function isroot() {
 874:     if (! isset($this->list[$this->pointer]))   return TRUE;
 875:     else if ($this->pointer == self::ANCHOR)    return TRUE;
 876:     else if ($this->pointer == $this->rootreturn TRUE;
 877:     return FALSE;
 878: }
 879: 
 880: /**
 881:  * 現在のポインタが末尾を指すかどうかを判定する
 882:  * @param   なし
 883:  * @return  bool TRUE:末尾である/FALSE:末尾でない
 884: */
 885: function istail() {
 886:     if (! isset($this->list[$this->pointer]))   return TRUE;
 887:     return ($this->pointer == self::ANCHOR);
 888: }
 889: 
 890: /**
 891:  * 現在のポインタが指す要素が存在するかどうかを判定する
 892:  * @param   なし
 893:  * @return  bool TRUE:存在する/FALSE:存在しない
 894: */
 895: function exist() {
 896:     $i = $this->pointer;

クラスの中で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によるリスト

 898: }
 899: 
 900: /**
 901:  * 現在のポインタが指す要素を1つ取り出す
 902:  * @param   なし
 903:  * @return  mixed 取り出した要素/NULL:要素がない
 904: */
 905: function get() {
 906:     $i = $this->pointer;
 907:     return $this->exist() ? $this->list[$i]['__item': NULL;
 908: }
 909: 
 910: /**
 911:  * リストの先頭にポインタをセットする
 912:  * @param   なし
 913:  * @return  int 先頭のインデックス
 914: */
 915: function moveRoot() {
 916:     return $this->pointer = $this->root;
 917: }
 918: 
 919: /**
 920:  * リストの末尾にポインタをセットする
 921:  * @param   なし
 922:  * @return  int 末尾のインデックス

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

 924: function moveTail() {
 925:     return $this->pointer = $this->tail;
 926: }
 927: 
 928: /**
 929:  * 任意のインデックスをポインタにセットする
 930:  * @param   int $i  インデックス
 931:  * @return  int セットしたインデックス/0:対応する要素がない
 932: */
 933: function setPointer($i) {
 934:     return isset($this->list[$i]) ? ($this->pointer = $i: self::ANCHOR;
 935: }
 936: 
 937: /**
 938:  * 次の要素のインデックスを返し、ポインタを進める
 939:  * @param   なし
 940:  * @return  int 前の要素のインデックス/0:次はない
 941: */
 942: function moveNext() {
 943:     if ($this->istail())    return self::ANCHOR;    //リストの末尾
 944:     if (! $this->exist())   return self::ANCHOR;    //要素がない
 945:     $i = $this->list[$this->pointer]['__next']; //次のインデックス
 946:     $this->pointer = $i;                            //ポインタにセット
 947: 
 948:     return $this->pointer;
 949: }
 950: 

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

  11: //データ構造クラス
  12: require_once('pahooDataStructure.php');
  13: 
  14: //データ(1行目:ラベル,列:タブ区切り,行:改行区切り)
  15: $data =<<< EOT
  16: start   finish  title
  17: 2018-06-18T13:00+09:00  2018-06-18T14:00+09:00  打ち合わせ
  18: 2018-06-19T15:00+09:00  2018-06-19T16:30+09:00  来客
  19: 2018-06-21T09:00+09:00  2018-06-21T10:00+09:00  事務作業
  20: 
  21: EOT;
  22: 
  23: /**
  24:  * CSV形式テキストを読み込んで、リストに展開する
  25:  * @param   string    $data   CSV形式テキスト(列:タブ,行:改行)
  26:  * @param   pahooList $labels ラベルを格納するリスト(1行目のテキスト)
  27:  * @param   pahooList $items  要素を格納するリスト
  28:  * @return  int 要素数
  29: */
  30: function parseList($data, &$labels, &$items) {
  31:     $item = array();
  32:     $rec = preg_split("/\n/ui", $data);     //行に分解
  33:     $cnt = 0;
  34:     foreach ($rec as $str) {
  35:         $str = trim($str);
  36:         if (mb_strlen($str) == 0)   continue;
  37:         $col = preg_split("/\t/ui", $str);      //列に分解
  38:         if ($cnt == 0) {                        //ラベルを格納
  39:             foreach ($col as $key=>$val) {
  40:                 $labels->append(trim($val));
  41:             }
  42:         } else {                                //要素を格納
  43:             $labels->moveRoot();
  44:             foreach ($col as $key=>$val) {
  45:                 $label = $labels->get();
  46:                 $item[$label] = trim($val);
  47:                 $labels->moveNext();
  48:             }
  49:             $items->append($item);
  50:         }
  51:         $cnt++;
  52:     }
  53:     return $cnt;
  54: }
  55: 
  56: /**
  57:  * スケジュール・リストにスケジュールを挿入
  58:  * @param   array     $d     スケジュール
  59:  * @param   pahooList $items スケジュール・リスト
  60:  * @return  なし
  61: */
  62: function insertSchedule($d, &$items) {
  63:     $items->moveRoot();                     //リストの先頭へ
  64:     while (! $items->istail()) {                //リスト末尾まで繰り返し
  65:         $a = $items->get();
  66:         if ($a['start'>$d['start']) {       //開始日時が大きければ
  67:             $items->insert($d);             //要素を挿入
  68:             return;
  69:         }
  70:         $items->moveNext();                 //次の要素へ
  71:     }
  72:     $items->append($d);                     //そうでなければ末尾に追加
  73: }
  74: 
  75: /**
  76:  * スケジュール・リストからスケジュールを削除
  77:  * @param   array     $d     スケジュール
  78:  * @param   pahooList $items スケジュール・リスト
  79:  * @return  なし
  80: */
  81: function deleteSchedule($d, &$items) {
  82:     $items->moveRoot();                     //リストの先頭へ
  83:     while (! $items->istail()) {                //リスト末尾まで繰り返し
  84:         $a = $items->get();
  85:         if (($a['start'] == $d['start']) && //開始・終了日時が等しければ
  86:             ($a['finish'] == $d['finish'])) {
  87:             $items->delete();                   //要素を削除
  88:             return;
  89:         }
  90:         $items->moveNext();                 //次の要素へ
  91:     }
  92: }
  93: 
  94: /**
  95:  * スケジュール表示
  96:  * @param   pahooList $items スケジュール・リスト
  97:  * @return  なし
  98: */
  99: function printSchedule(&$items) {
 100:     $items->moveRoot();                     //リストの先頭へ
 101:     while (! $items->istail()) {                //リスト末尾まで繰り返し
 102:         $a = $items->get();                 //要素を取り出して表示
 103:         printf('%s - ', date('Y/m/d H:i', strtotime($a['start'])));
 104:         printf('%s  ',  date('H:i', strtotime($a['finish'])));
 105:         printf("%s\n",  $a['title']);
 106:         $items->moveNext();                 //次の要素へ
 107:     }
 108: }
 109: 
 110: // メイン・プログラム ======================================================
 111: // リストへ読み込み
 112: $labels = new pahooList();                      //リストを用意
 113: $items  = new pahooList();
 114: $cnt = parseList($data, $labels, $items);       //元データの読み込み
 115: 
 116: // 出力(1)
 117: printf("\n*original\n");
 118: printSchedule($items);
 119: 
 120: $b = array('start'=>'2018-06-20T15:00+09:00', 'finish'=>'2018-06-20T16:00+09:00', 'title'=>'報告会');
 121: $items->append($b);                         //スケジュールの追加
 122: 
 123: // 出力(2)
 124: printf("\n*append\n");
 125: printSchedule($items);
 126: 
 127: deleteSchedule($b, $items);                 //追加したスケジュールを削除
 128: insertSchedule($b, $items);                 //スケジュールの挿入
 129: 
 130: // 出力(3)
 131: printf("\n*insert\n");
 132: printSchedule($items);

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

C++によるリスト

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

  44: /**
  45:  * CSV形式テキストを読み込んで、リストに展開する
  46:  * @param   char      *data  CSV形式テキスト(列:タブ,行:改行)
  47:  * @param   vector    labels ラベルを格納(1行目のテキスト)
  48:  * @param   list<map> items  要素を格納するリスト
  49:  * @return  int    要素数
  50: **/
  51: int parseList(char *data, vector<string> &labels, list<map<string,string>> &items) {
  52:     map<string,string> *item;
  53:     int cnt = 0;
  54:     for (string &rec : split(data, '\n')) {             //行に分解
  55:         if (rec.size() > 0) {
  56:             if (cnt == 0) {                             //ラベルを格納
  57:                 for (string &col : split(rec, '\t')) {      //列に分解
  58:                     labels.push_back(col);
  59:                 }
  60:             } else {                                        //要素を格納
  61:                 item = new map<string,string>;
  62:                 int i = 0;
  63:                 for (string &col : split(rec, '\t')) {      //列に分解
  64:                     item->insert(make_pair(labels[i], col));
  65:                     i++;
  66:                 }
  67:                 items.push_back(*item);                 //リストに加える
  68:             }
  69:             cnt = cnt + 1;
  70:         }
  71:     }
  72:     return(cnt);
  73: }

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

  75: /**
  76:  * スケジュール・リストにスケジュールを挿入
  77:  * @param   map d      スケジュール
  78:  * @param   list<map>  items スケジュール・リスト
  79:  * @return  なし
  80: **/
  81: void insertSchedule(map<string,string> &d, list<map<string,string>> &items) {
  82:     list<map<string,string>>::iterator a;
  83:     for (a = items.begin(); a !items.end(); a++) {
  84:         if (a->at("start">d["start"]) {
  85:             items.insert(a, d);
  86:             break;
  87:         }
  88:     }
  89: }
  90: 
  91: /**
  92:  * スケジュール・リストからスケジュールを削除
  93:  * @param   map d      スケジュール
  94:  * @param   list<map>  items スケジュール・リスト
  95:  * @return  なし
  96: **/
  97: void deleteSchedule(map<string,string> &d, list<map<string,string>> &items) {
  98:     list<map<string,string>>::iterator a;
  99:     for (a = items.begin(); a !items.end(); a++) {
 100:         if ((a->at("start") == d["start"]) && (a->at("finish") == d["finish"])) {
 101:             items.erase(a);
 102:             break;
 103:         }
 104:     }
 105: }
 106: 
 107: /**
 108:  * スケジュール表示
 109:  * @param   list<vector> items スケジュール・リスト
 110:  * @return  なし
 111: **/
 112: void printSchedule(list<map<string,string>> &items) {
 113:     list<map<string,string>>::iterator a;
 114:     for (a = items.begin(); a !items.end(); a++) {
 115:         cout << a->at("start"<< " - " << a->at("finish"<< " " << a->at("title"<< endl;
 116:     }
 117: }
 118: 
 119: // メイン・プログラム ======================================================
 120: int main() {
 121:     vector<string> labels;
 122:     list<map<string,string>> items;
 123: 
 124:     parseList(data, labels, items);
 125: 
 126:     //出力(1)
 127:     cout << endl << "*original" << endl;
 128:     printSchedule(items);
 129: 
 130:     //追加データ
 131:     map<string,string> b = {{"start", "2018-06-20T15:00+09:00"}, {"finish", "2018-06-20T16:00+09:00"}, {"title", "報告会"}};
 132:     items.push_back(b);
 133: 
 134:     //出力(2)
 135:     cout << endl << "*append" << endl;
 136:     printSchedule(items);
 137: 
 138:     deleteSchedule(b, items);
 139:     insertSchedule(b, items);
 140: 
 141:     //出力(3)
 142:     cout << endl << "*insert" << endl;
 143:     printSchedule(items);
 144: 
 145:     return (0);
 146: }

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

C言語によるリスト

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

  20: 2018-06-18T13:00+09:00  2018-06-18T14:00+09:00  meeting\n\
  21: 2018-06-19T15:00+09:00  2018-06-19T16:30+09:00  visitor\n\
  22: 2018-06-21T09:00+09:00  2018-06-21T10:00+09:00  desk work\n\
  23: ";
  24: 
  25: // スケジュールを格納する構造体=リスト
  26: struct schedule {
  27:     char start[MAXLEN_STRING];      // 開始日時
  28:     char finish[MAXLEN_STRING]; // 完了日時
  29:     char title[MAXLEN_STRING];      // 予定
  30:     struct schedule *forward;       // 前の要素を指すポインタ
  31:     struct schedule *next;          // 次の要素を指すポインタ
  32: };
  33: 
  34: struct schedule *rootList;          /* ルート   */
  35: struct schedule *ptrList;           /* ポインタ */
  36: 
  37: /**
  38:  * リストを初期化する
  39:  * @return  struct schedule* ルートへのポインタ
  40: **/
  41: struct schedule *initList(void) {

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

  43:     rootList->forward = NULL;
  44:     rootList->next    = NULL;
  45:     return rootList;
  46: }
  47: 
  48: /**
  49:  * 現在のポインタが先頭を指すかどうかを判定する
  50:  * @param   なし
  51:  * @return  bool TRUE:先頭である/FALSE:先頭でない
  52: */
  53: bool isroot() {
  54:     return (ptrList == rootList);
  55: }
  56: 
  57: /**
  58:  * 現在のポインタが末尾を指すかどうかを判定する
  59:  * @param   なし
  60:  * @return  bool TRUE:末尾である/FALSE:末尾でない
  61: */
  62: bool istail() {
  63:     return (ptrList->next == NULL);
  64: }
  65: 
  66: /**
  67:  * リストの先頭にポインタをセットする
  68:  * @param   なし
  69:  * @return  なし
  70: */
  71: void moveRoot(void) {
  72:     ptrList = rootList;
  73: }
  74: 
  75: /**
  76:  * 次の要素のインデックスを返し、ポインタを進める
  77:  * @param   なし
  78:  * @return  int 前の要素のインデックス/0:次はない
  79: */
  80: void moveNext(void) {
  81:     if (ptrList->next !NULL)  ptrList = ptrList->next;
  82: }
  83: 
  84: /**
  85:  * リストの末尾にポインタをセットする
  86:  * @param   なし
  87:  * @return  int 末尾のインデックス
  88: */
  89: void moveTail(void) {
  90:     moveRoot();
  91:     while (! istail())  moveNext();
  92: }
  93: 
  94: /**
  95:  * リストの長さ(要素数)を返す
  96:  * @param   なし
  97:  * @return  int リストの長さ
  98: */
  99: size_t listlen(void) {
 100:     size_t l = 0;
 101:     ptrList = rootList;             //リストの先頭へ
 102:     while (ptrList->next !NULL) { //リスト末尾まで繰り返し
 103:         l++;
 104:         ptrList++;                      //次の要素へ
 105:     }
 106:     if (strlen(ptrList->start> 0l++;
 107:     return l;
 108: }
 109: 
 110: /**
 111:  * リストの末尾に要素を1つ追加する
 112:  * @param   char *start  開始日時
 113:  * @param   char *finish 終了日時
 114:  * @param   char *title  予定
 115:  * @return  なし
 116: */
 117: void append(char *start, char *finish, char *title) {
 118:     //リスト長ゼロの時の追加
 119:     if (listlen() == 0) {
 120:         ptrList = rootList;
 121:         strcpy(ptrList->start,  start);
 122:         strcpy(ptrList->finish, finish);
 123:         strcpy(ptrList->title,  title);
 124: 
 125:     //それ以外の追加
 126:     } else {
 127:         struct schedule *p = (struct schedule *)malloc(sizeof(struct schedule));
 128:         strcpy(p->start,  start);
 129:         strcpy(p->finish, finish);
 130:         strcpy(p->title,  title);
 131:         moveTail();
 132:         ptrList->next = p;
 133:         p->forward = ptrList;
 134:         p->next    = NULL;
 135:         ptrList = p;
 136:     }
 137: }
 138: 
 139: /**
 140:  * 現在のポインタ位置(ポインタが示す要素の前)に要素を1つ挿入する
 141:  * @param   char *start  開始日時
 142:  * @param   char *finish 終了日時
 143:  * @param   char *title  予定
 144:  * @return  なし
 145: */
 146: void insert(char *start, char *finish, char *title) {
 147:     struct schedule *forward = ptrList->forward;
 148: 
 149:     struct schedule *p = (struct schedule *)malloc(sizeof(struct schedule));
 150:     strcpy(p->start,  start);
 151:     strcpy(p->finish, finish);
 152:     strcpy(p->title,  title);
 153: 
 154:     if (forward == NULL)    rootList = p;       //ルートに挿入
 155:     else                    forward->next = p;
 156:     ptrList->forward = p;
 157:     p->next = ptrList;
 158:     p->forward = forward;
 159:     ptrList = p;
 160: }
 161: 
 162: /**
 163:  * 現在のポインタが指す要素を1つ削除する
 164:  * @param   なし
 165:  * @return  なし
 166: */
 167: void delete(void) {
 168:     if (ptrList == NULL)    return;
 169: 
 170:     struct schedule *p = ptrList;
 171:     struct schedule *forward = ptrList->forward;
 172:     struct schedule *next    = ptrList->next;

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