データ構造には、配列構造とリスト構造があります。
配列は、データもコンパクトでアクセスも高速ですが、編集時にデータをずらさなければならない欠点があります。
これに対して、リストは、編集が高速にできるという利点があります。
そこで、リスト構造を中心に、データ構造とアルゴリズムについて解説します。
配列は、同じ属性のデータの繰り返しで表します。 データへのアクセスは、インデックスと呼ばれる番号で、何番目の要素かを指定してアクセスします。 配列データは、以下のような構造となります。
[データ1] 配列の0番目 [データ2] 配列の1番目 [データ3] 配列の2番目 |
言語によって異なりますが、配列は、以下のようにアクセスします。
データ名[インデックス番号] $データ名[インデックス番号] |
リストは、データの場所を示すセルで連結して表します。
セル間の関係を示すために、次のデータへのポインタを持っています。
データ1、データ2、データ3があった場合、データ1はデータ2を示し、データ2はデータ3を示し、データ3はデータ1を示すことで、3つのデータを1つのデータとして管理しています。
リストには、片方向のポインタのみ持つ単方向リストと、逆方向のポインタも持つ双方向リストがあります。
単方向リストでは、ポインタを片方向しか持たないため、データはコンパクトになりますが、編集時にサーチ処理が必要となるため、遅くなります。
単方向リストと双方向リストは以下のような構造となります。
単方向リストの構造 +--> [データ1] ---> [データ2] ---> [データ3] ---+ | | +-----------------------------------------------+ 双方向リストの構造 #==> [データ1] <==> [データ2] <==> [データ3] <==# # # #===============================================# |
一般的に、リスト構造のセルは、以下のポインタで表します。
単方向リストのセル next: 次データへのポインタ（next） 双方向リストのセル next: 次データへのポインタ（next） prev: 前データへのポインタ（previous） |
言語によって異なりますが、リストは、以下のようにアクセスします。
データ名->next $next[データ識別子] |
子となるノードが1つしかない場合、次データと前データは、それぞれ自分を指します。 データの最後をNULLとする方法もありますが、ループさせた方が最後のデータを簡単に検索することができるため、ループさせた方が便利です。
双方向リストの単独ループ #==> [データ1] <==# # # #=================# |
階層構造を表すためには、セルに親子関係の情報を持ちます。
親は、先頭の子のみ示し、子はそれぞれの親を示します。
これらのセルによって連結される、各データのことを、ノード（節）と呼びます。
一般的に、階層構造を持つ双方向リストのセルは、以下の4つのポインタで表します。
prnt: 親ノードへのポインタ（parent node） chid: 子ノードへのポインタ（child node） next: 次ノードへのポインタ（next node） prev: 前ノードへのポインタ（previous node） |
データには必ずルート（根）ノードが必要です。 階層構造では、このルートノードからセルのポインタによって関連付けられています。
階層構造リストの構造
[ルートノード]
↓↑↑↑
↓↑↑＋−−−−−−−−−−−−＋
↓↑＋−−−−−＋ ↑
↓↑ ↑ ↑
#==> [データ1] <==> [データ2] <==> [データ3] <==#
# #
#===============================================#
↓↑↑
↓↑＋−−−−−＋
↓↑ ↑
#==> [データ4] <==> [データ5] <==#
# #
#================================#
|
このサンプルプログラムでは、階層構造を持った双方向リストを採用しています。 階層構造を持つデータを、最新日時順に表示したり、階層構造で表示したりすることができます。
サンプルプログラムは、以下のファイルから構成されています。
| list.pl | 双方向リストを使った最新日時順表示＋階層表示プログラム |
|---|---|
| data.txt | サンプルデータファイル |
list.plでは、data.txtから読み込み、配列を逆方向から表示することで、最新日時順の表示を実現しています。
また、ルートノードから検索することで、階層表示を実現しています。
階層構造を表すプリフィックス記号は、自分が最後のデータかどうかによって、切り替えています。
lst_cre関数で、各種双方向リストのポインタを設定し、lst_dsp関数で、階層表示を行っています。
lst_dsp関数は再帰的に呼びだされます。
以下に、サンプルソースを示します。
| list.pl |
|---|
#!/usr/local/bin/perl
#
# list edit: 双方向リスト編集処理
# prnt: 親ノード (parent node)
# chid: 子ノード (child node)
# next: 次ノード (next node)
# prev: 前ノード (previous node)
# data format: データファイルの形式
# date: 日時 (MM/DD hh:mm)
# prnt: 親データ行番号
# user: ユーザ名
# data: データ内容
#
{
my ($file, $buf);
my ($line, $num);
# initialize
$pre = '';
$pre1a = '├';
$pre1b = '└';
$pre2a = '│';
$pre2b = ' ';
# data file read
$file = "data.txt";
if (!open(FILE_IN, "<$file")) {
printf("File %s open error.\n",$file);
exit(1);
}
$prnt[0] = 0;
$chid[0] = 0;
for ($line = 1; $buf = <FILE_IN>; $line++) {
chomp($buf);
($date[$line], $prnt[$line], $user[$line], $data[$line])
= split(',', $buf);
}
$num = $line;
close(FILE_IN);
# 最新日付順表示
for ($line = $num - 1; $line > 0; $line--) {
printf("%-30s %-11s %-10s\n",
$data[$line], $date[$line], $user[$line]);
}
# create tree index
for ($line = 0; $line < $num; $line++) {
&lst_cre($line, $prnt[$line]);
}
# # tree disp
# for ($line = 0; $line < $num; $line++) {
# printf("%5d,%5d,%5d,%5d,%5d,%5s,%10s,%20s\n", $line,
# $prnt[$line], $chid[$line], $next[$line], $prev[$line],
# $date[$line], $user[$line], $data[$line]);
# }
# 階層表示
&lst_dsp($chid[0], $pre);
}
sub lst_cre {
# create list pointer
my ($idx, $pos) = @_;
my ($insnext, $insprev);
if ($chid[$pos] == 0) {
# 子がない場合
$chid[$pos] = $idx;
$next[$idx] = $idx;
$prev[$idx] = $idx;
} else {
# 子がある場合
$insnext = $chid[$pos];
$insprev = $prev[$insnext];
$next[$idx] = $insnext;
$prev[$idx] = $insprev;
$next[$insprev] = $idx;
$prev[$insnext] = $idx;
}
$chid[$idx] = 0;
}
sub lst_dsp {
# list display
my ($idx, $pre) = @_;
my ($i);
#printf("lst_dsp(%d)\n", $idx);
$i = $idx;
do {
if ($next[$i] == $chid[$prnt[$i]]) {
# 最後のノード
$pre1 = $pre.$pre1b;
$pre2 = $pre.$pre2b;
} else {
# 最後以外のノード
$pre1 = $pre.$pre1a;
$pre2 = $pre.$pre2a;
}
printf("%-40s %-11s %-10s\n",
$pre1.$data[$i], $date[$i], $user[$i]);
if ($chid[$i] != 0) {
if ($next[$i] == $chid[$prnt[$i]]) {
# 最後のノード
} else {
# 最後以外のノード
}
&lst_dsp($chid[$i], $pre2);
}
$i = $next[$i];
} until ($i == $idx);
}
|
list.plには、以下のデータを使用しています。
$data[0]: ルートノード @data: データ格納用配列（データは1オリジン） $pre*: 階層表示用のプリフィックス記号 $prnt: 親ノードへのポインタ（parent node） $chid: 子ノードへのポインタ（child node） $next: 次ノードへのポインタ（next node） $prev: 前ノードへのポインタ（previous node） |
data.txtの形式は以下の項目があります。 データは、CSV形式で格納してあります。
date: 日時 (MM/DD hh:mm) prnt: 親データ行番号 user: ユーザ名 data: データ内容 |
実際のデータ内容は、以下のような内容となります。
| data.txt |
|---|
09/01 10:10,000,joe,text001 09/02 10:10,001,sys,text002 09/03 10:10,002,joe,text003 09/04 10:10,001,sys,text004 09/05 10:10,004,joe,text005 09/06 12:34,005,sys,text006 09/07 12:34,000,joe,text007 09/08 12:34,007,sys,text008 09/09 12:34,001,joe,text009 09/10 12:34,003,sys,text010 |