サンプル・プログラム
配列の弱点
たとえば、日時を添字として連想配列で扱うのであれば
$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'] = '打ち合わせ';
この場合、スケジュールを追加をしていくと、添字がどんどん増え、要素の順序は日時順ではなくなってしまう。これでは、日時順にスケジュール表を表示するたびに、配列の先頭から末尾までデータを取り出してソートしなければならない。データが増えれば増えるほど、処理系への負荷が増す。スケジュールを削除した場合も同様である。
つまり、次のような性質のデータに対しては、データ構造として配列を用いるのは適当ではない。こういうときは、リストというデータ構造を用いる。
- データに順序関係がある。
- データの追加・削除が頻繁にある。
リスト構造
リストには先頭(root)と末尾(tail)があり、その間に複数の要素(node)が数珠つなぎに連なっているデータ構造である。
要素には、数や文字列といった属性のデータを直接入れる場合もあるし、配列などの他のデータ構造を入れることもできる。リストの要素としてリストを入れることも可能だ。
上図のように、node にデータ構造がぶら下がっているという形をイメージしてもらえばいいだろう。
リストを扱える処理系では、あわせて要素の追加・削除のための関数やメソッドが用意されている。これにより、順序関係を維持したまま、頻繁に要素の追加・削除することができるようになっている。
ここではPythonのメソッドを例に紹介する。
要素の追加は2種類ある。リストの末尾に追加する append と、リストの途中に挿入する insert である。
append のイメージ
Pythonでは、便宜上、リストの要素に1,2,3‥‥という番号が振られており、これを頼りに insert を行うことができる。
insert のイメージ
プログラム例は後述するが、このため実際の追加プログラムはやや複雑になり、append に比べて実行時間を要する。だが、スケジュール表のように、データの追加より参照回数の方が多い場合は、参照の際に並べ替えを行う配列より合理的である。
要素の削除には delメソッド を用いる。削除する要素のリンクを切り、その隣の要素とリンクし直す。
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()
スケジュール・データは、「ヒアドキュメント」を使って用意する。
0049: """
0050: * スケジュール・リストにスケジュールを挿入
0051: * @param dict d スケジュール
0052: * @param list itemsスケジュール・リスト
0053: * @returnなし
0054: """
0055: def insertSchedule(d, items):
0056: for i, a in enumerate(items):
0057: if (a['start'] >= d['start']):
0058: items.insert(i, d)
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(d, items):
0070: for i, a in enumerate(items):
0071: if ((a['start'] == d['start']) & (a['finish'] == d['finish'])):
0072: items.pop(i)
0073: break
deletSchedule は、予定開始と終了が合致するスケジュール(要素)を delete する。
まず、ヒアドキュメントのスケジュール一覧を表示する。
続いて、スケジュール(要素)を1つ append する。リストの末尾に追加するから、日時の順番が狂ってしまっている。
次に、スケジュール(要素)を1つ insert する。日時の順番は正しく並んでいる。
最後に、insert したスケジュールを delete する。
PHPによるリスト
そこで、リストを扱うためのクラス 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: }
$i はPythonのリストでいうところの「インデックス」である。PHPは配列の途中に要素を挿入する機能を備えていないため、個々の配列の2次元目に ['__next'] を用意し、次の要素のインデックスを代入しておく。そうすることで、インデックスが小さい順に並んでいなくても、rootから要素を順にたどることができるようにした。
インデックスは自然数とし、先頭rootと末尾tailはゼロ(定数 ANCHOR に定義)としている。
要素の実体は、2次元目 ['__item'] に代入する。PHPは、配列の要素として代入できるデータ属性が制限されていない。整数でも文字列でも配列でも構わない。また、リストの要素の1つ1つを異なるデータ属性にすることもできる。
リスト構造は、先頭から末尾へ向かってたどるのが基本だが(これを単方向リストと呼ぶ)、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() | リストの長さ(要素数)を返す |
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: }
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: }
連想配列が利用できない場合は、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);
PHPではfor文によってリストを扱うことができない。代わりに、moveRoot メソッドで先頭に移動し、末尾まで(istail メソッドの結果)while ループを回すことによって、スケジュールの追加、削除、一覧表示を実現している。
C++によるリスト
ここでは、最初に紹介したリスト構造にしたがい、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 *data, vector<string> &labels, list<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: }
要素部分は、まず、タブ区切りで分解し、連想配列 map クラスへ格納し、それをリストクラス list へ格納してゆく。
0075: /**
0076: * スケジュール・リストにスケジュールを挿入
0077: * @param map d スケジュール
0078: * @param list<map> itemsスケジュール・リスト
0079: * @returnなし
0080: **/
0081: void insertSchedule(map<string,string> &d, list<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(a, d);
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> &d, list<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<string> labels;
0122: list<map<string,string>> items;
0123:
0124: parseList(data, labels, items);
0125:
0126: //出力(1)
0127: cout << endl << "*original" << endl;
0128: printSchedule(items);
0129:
0130: //追加データ
0131: map<string,string> b = {{"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(b, items);
0139: insertSchedule(b, items);
0140:
0141: //出力(3)
0142: cout << endl << "*insert" << endl;
0143: printSchedule(items);
0144:
0145: return (0);
0146: }
実行結果は下図の通りである。ISO8601フォーマットを処理できる適当なクラスが見当たらなかったので、日時はオリジナルのままを表示している。
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: }
要素を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 *start, char *finish, char *title) {
0113: //リスト長ゼロの時の追加
0114: if (listlen() == 0) {
0115: ptrList = rootList;
0116: strcpy(ptrList->start, start);
0117: strcpy(ptrList->finish, finish);
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->finish, finish);
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 *start, char *finish, char *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->finish, finish);
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 != NULL) ptrList->forward = forward;
0170: if (forward != NULL) forward->next = ptrList;
0171: free(p);
0172: }
実行結果は下図の通りである。ISO8601フォーマットを処理する関数を用意しなかったこと、日本語文字列(UTF-8)を処理することが面倒であることから、データは全て英数字にしてある。
PythonやC++は、言語仕様としてリストが用意されている。PHPはリストを備えていないが、ここでは双方向リストを扱うことができるユーザー・クラスを用意した。また、C言語では構造体を使ったリストを紹介する。