リストはデータの挿入や削除が比較的頻繁に起こる動的なデータ処理に適している。本章ではリストを用いて動的な処理を伴うエディタを実現する。
６．１ テキストエディタ
○課題
テキストファイルの編集を行うテキストエディタを作成せよ。
|
○外部仕様
行単位にテキストファイルを編集するラインエディタとする。テキストファイルをメモリ（エディタ構造体）に読み込み、行の表示・変更・挿入・削除等の行単位の編集コマンドによりテキストの内容を変更し、テキストファイルを更新する。編集コマンドはアルファベット一文字と引数（必要な場合のみ）を指定する。
テキストファイル
ただし、上図のエディタ構造体は線形リストにより実現した様子を示している。
○概要設計
１．指定されたファイルをエディタ構造体に読み込む
２．標準入力から編集コマンドを読みとる
３．編集コマンドを実行する
rファイル名 現在行の前にファイルからデータを読み込む（read）
wファイル名 データをファイルに書き込む（write）
p 前の行に戻る（previous line）
n 次の行に進む（next line）
d 現在行を削除する（delete line）
i挿入データ 現在行の後ろにデータを挿入する（insert line）
l 現在の行を表示する（list line）
q エディタを終了する（quit）
○詳細設計
●アクセス関数
ａ．エディタ構造体の生成
E=CREATE() ：エディタ構造体を生成する
ｂ．行構造体の生成
L=NewLine(l)：内容を l とする新しい行 L を生成する
ｃ．ファイルの読み込み
ReadFile(E, F)：エディタ構造体 E にファイル F の内容を読み込む。既にエディタ構造体にデータが存在する場合は、現在行の後ろに読み込む
ｄ．ファイルへの書き込み
WriteFile(E, F)：エディタ構造体 E の内容をファイル F に書き込む
ｅ．次行へ移動
NextLine(E)：次行へ進む（次行を現在行とする）
ｆ．前行へ移動
PrevLine(E)：前行へ戻る（前行を現在行とする）
ｇ．行挿入
InsertLine(E, L)：現在行の後ろに新しい行 L を挿入する
ｈ．行削除
DeleteLine(E)：現在行を削除する
ｉ．行表示
ListLine(E)：現在行を標準出力へ出力する
ｊ．終了
Quit(E)：エディタを終了する
●データ構造
行挿入が現在行の後ろに行を挿入するので、先頭行（１行目）の前に行を挿入できない。このため、仮想的に１行目の前の行（０行目）を準備する。top は０行目を指すフィールドであり、current は現在行を指すフィールドである。
typedef struct {
Line top, current;
} EditorRec, *Editor;
ただし、行の構造を表現する Line は後述する。
○コーディング
【CREATE操作】
Editor CREATE()
{
Editor E;
if((E=malloc(sizeof(EditorRec)))==NULL) {
fprintf(stderr, "エディタ構造体を生成できませんでした\n");
exit(1);
}
E->top=E->current=NewLine("<<<<< 先頭行 >>>>>\n");
return(E);
}
問 6.1.1 計算機で利用されているラインエディタにはどのようなものがあるか。ラインエディタのコマンドについて調べて見よ。
問 6.1.2 問 6.1.1 で調べたコマンドについて、どのようなアクセス関数が必要であるか考えよ。
問 6.1.3 エディタ構造体をリストを用いて実現する方法以外に、どのようなデータ構造で実現することができるか。リストを用いる場合と比較してどのような得失があるかも考えよ。
６．２ 線形リストの実現
線形リストとは、情報を保持するフィールドと次の情報の位置を示すフィールドから構成されるセルが下図のように一方向に接続されているものである。
セルは、情報フィールド info と次のセルへのポインタフィールド next を持つ構造体として定義できる。
typedef struct cell {
DATATYPE info; /* データ型 DATATYPE の情報部 */
struct cell *next; /* 次のセルへのポインタ */
} CellRec, *Cell;
（注）DATATYPE は情報フィールドの型であり、利用する問題によって変化する。
線形リストに対する処理としては、挿入・削除・次のセルへの移動・前のセルへの移動がある。
・次のセルへの移動
次のセル
c=c->next;
・前のセルへの移動
現在のセルだけでは前のセルの情報を得ることができないため、線形リストの先頭のセル top と現在のセル c から前のセルを求める。
前のセル 現在のセル
for(p=top; p->next!=c; p=p->next); /* p->next が c になるまで */
c=p;
・セルの挿入
セル c１ の後ろにセル c２ を挿入する。
c２->next=c１->next;
c１->next=c２;
・セルの削除
現在のセルを削除するには前のセルの情報を得る必要があるため、線形リストの先頭のセル top を利用して前のセルを求め、現在のセル c を削除する。
prev 削除するセル
prev=前のセルへの移動（c の一つ前のセルを top を利用して求める）;
prev->next=c->next;
c のセルを解放する
●アクセス関数
ａ．セルの生成
C=NEW(info)：情報 info を保持する新しいセル C を生成する
ｂ．情報フィールド
INFO(current)：現在のセル current の情報フィールドを返す
ｃ．次のセルへの移動
next=NEXT(current)：現在のセル current の次のセル next を返す
ｄ．前のセルへの移動
prev=PREV(top, current)：先頭のセル top を起点にして、現在のセル current の前のセル prev を返す
ｅ．セルの挿入
new=INSERT(new, current)：現在のセル current の後ろにセル new を挿入し、セル new を返す
ｆ．セルの削除
prev=DELETE(top, current)：先頭のセル top につながる現在のセル current を削除し、現在のセルの前のセル prev を返す
●データ構造
ａ．セル構造体
typedef struct cell {
DATATYPE info; /* 情報部のデータ型 */
struct cell *next; /* 次のセルへのポインタ */
} CellRec, *Cell;
ｂ．情報部のデータ型
情報部では、行の内容を表現するため、DATATYPE を文字列（char *）とする。
○コーディング
【NEW操作】
【INFO操作】
DATATYPE INFO(Cell cell)
{
return(cell->info);
}
【NEXT操作】
Cell NEXT(Cell cell)
{
return(cell->next);
}
【PREV操作】
Cell PREV(Cell top, Cell cell)
{
Cell prev;
if(cell==top)
return(NULL);
else {
for(prev=top; prev->next!=cell; prev=prev->next);
return(prev);
}
}
【INSERT操作】
Cell INSERT(Cell new, Cell cell)
{
new->next=cell->next;
cell->next=new;
return(new);
}
【DELETE操作】
Cell DELETE(Cell top, Cell cell)
{
Cell prev;
prev=PREV(top, cell);
if(prev!=NULL) {
prev->next=cell->next;
free(cell);
}
return(prev);
}
○時間量
セルのフィールドを参照・更新する回数により評価する。
・次のセルへの移動は、セルの next フィールドを１回参照する。
・前のセルへの移動は、先頭のセルから辿るので、先頭のセルから現在のセルの間に含まれるセルの数をｎとすれば、２ｎ回である。
・セルの挿入は、next フィールドを１回参照、２回更新する。合計３回である。
・セルの削除は、PREV 操作により２ｎ回参照し、その他に next フィールドを１回参照、１回更新する。合計２ｎ＋２回である
問 6.2.1 NEXT操作をマクロで定義し、next フィールドを参照する時は必ず NEXT操作を利用するように他の操作を変更せよ。
問 6.2.2 INFO操作をマクロで定義し、info フィールドを参照する時は必ず INFO操作を利用するように他の操作を変更せよ。
問 6.2.3 リストの最後のセルを返すアクセス関数 LAST を定義せよ。
last=LAST(current)：現在のセル current につながる最後のセル last を返す
問 6.2.4 リストの先頭からｎ番目のセルを返すアクセス関数 NTH を定義せよ。
nth=NTH(current, n)：現在のセル current から n 個後ろのセル nth を返す
問 6.2.5 リストに含まれるセルの数を返すアクセス関数 LENGTH を定義せよ。
len=LENGTH(current)：現在のセル current につながるセルの数 len を返す
６．３ 線形リストによるテキストエディタ
テキストエディタのためのアクセス関数および行構造体を定義する。
●データ構造
行データの構造体 Line は線形リストのセル構造体 Cell を使用する。
○コーディング
【NewLine操作】
文字列 info の複製を strdup を用いて生成し、その複製を情報フィールドとして持つ新しいセルを生成する。
Line NewLine(char *info)
{
Line new;
if(info!=NULL) {
if((info=strdup(info))==NULL) { /* 行の複製 */
fprintf(stderr, "行データを生成できませんでした\n");
return(NULL);
}
}
if((new=NEW(info))==NULL) {
fprintf(stderr, "行構造体を生成できませんでした\n");
exit(1);
}
return(new);
}
【ReadFile操作】
linebuf に読み込んだ各行に対して行構造体 new を生成し、現在行 E->current の後ろに挿入して行く。ファイルが空でなければ、読み込んだ先頭行を現在行にする。
void ReadFile(Editor E, char *F)
{
FILE *stream;
Line L, new;
if((stream=fopen(F, "r"))==NULL) {
fprintf(stderr, "!!!!! %s は読めません !!!!!\n", F);
return;
}
for(L=E->current; fgets(linebuf, LINE_SIZE, stream)!=NULL;
L=NEXT(L)) {
new=NewLine(linebuf);
INSERT(new, L);
}
fclose(stream);
if(E->current!=L)
E->current=NEXT(E->current); /* 先頭行を指す */
}
【WriteFile操作】
１行目からセルを辿りながら、最終行までの各セルの内容をファイルに書き込む。
void WriteFile(Editor E, char *F)
{
FILE *stream;
Line L;
if((stream=fopen(F, "w"))==NULL) {
fprintf(stderr, "!!!!! %s は書けません !!!!!\n", F);
return;
}
for(L=NEXT(E->top); L!=NULL; L=NEXT(L))
fputs(INFO(L), stream);
fclose(stream);
}
【NextLine操作】
NEXT操作で次のセルへ移動する。次のセルがない場合（NULLの場合）には、最終行であることを表示し、セルの移動を行わない。
【PrevLine操作】
現在の行が０行目でなければ、PREV操作で前のセルへ移動する。現在行が１行目ならば、０行目（<<<<< 先頭行 >>>>> の表示）に移動し、１行目の前への行挿入を可能にする。
void PrevLine(Editor E)
{
if(E->current!=E->top)
E->current=PREV(E->top, E->current);
}
【InsertLine操作】
標準入力から読み込んだ新しい行のデータには改行コードがないため、改行コードを追加する。 NewLine操作により、このデータを持つ新しいセルを生成し、INSERT操作で現在行の後ろに挿入する。挿入した行を現在行とする。
void InsertLine(Editor E, char *line)
{
int length;
length=strlen(line);
line[length]='\n'; line[length+1]='\0'; /* 改行コードの挿入 */
E->current=INSERT(NewLine(line), E->current);
}
【DeleteLine操作】
０行目の削除についてはエラーメッセージを出力する。strdup で割り当てた行データを解放し、DELETE操作により現在行を削除するために、PREV操作で前の行に戻る。削除後は、削除された行の次の行を現在行にする。
void DeleteLine(Editor E)
{
Line L;
if(E->current==E->top)
fprintf(stderr, "!!!!! 先頭行は削除できません !!!!!\n");
else {
free(INFO(E->current));
E->current=DELETE(E->top, E->current);
L=NEXT(E->current);
if(L!=NULL)
E->current=L;
}
}
【ListLine操作】
現在行の内容を標準出力に出力する。
void ListLine(Editor E)
{
printf("%s", INFO(E->current));
}
【Quit操作】
終了する。本来ならば、データに変更がある場合はユーザに確認する処理が必要である。
void Quit(Editor E)
{
exit(0);
}
【Error関数】
未定義のコマンドが指定された場合に、エラーメッセージを出力する。
void Error(char *message)
{
fprintf(stderr, "!!!!! コマンド %s 解析不能 !!!!!\n", message);
}
【main関数】
CREATE操作でエディタ構造体を生成し、ファイル名が指定されていればその内容を読み込む。標準入力から読み込んだユーザのコマンドの種類に応じてテキストエディタのためのアクセス関数を呼び出す。
char linebuf[LINE_SIZE];
void main(int argc, char **argv)
{
Editor E;
switch(argc) {
case 1: E=CREATE();
break;
case 2: E=CREATE();
ReadFile(E, argv[1]);
break;
default:
fprintf(stderr, "使用法: %s [ファイル名]\n", argv[0]);
exit(1);
}
while(gets(linebuf)!=NULL) {
switch(linebuf[0]) {
case 'r': ReadFile(E, linebuf+1); break;
case 'w': WriteFile(E, linebuf+1); break;
case 'n': NextLine(E); break;
case 'p': PrevLine(E); break;
case 'i': InsertLine(E, linebuf+1); break;
case 'd': DeleteLine(E); break;
case 'l': break;
case 'q': Quit(E); break;
default: Error(linebuf);
}
ListLine(E);
}
}
○時間量
ｎ行のデータを処理している場合に、次行への移動、前行への移動、行挿入、行削除に関して、セルを辿る回数とセルへの代入操作の回数の和を時間量として評価する。
次行への移動は、セルの next フィールドを１回辿るだけである。
Ｔｎｅｘｔ(ｎ)＝１＝Ｏ(１)
前行への移動は、最悪の場合、先頭行から最終行まで辿ることになる。
Ｔｐｒｅｖ(ｎ)＝ｎ＝Ｏ(ｎ)
行挿入は、現在行の後ろに挿入するので、セルを辿る必要はないが、next フィールドを２つ更新する必要がある。
Ｔｉｎｓｅｒｔ(ｎ)＝２＝Ｏ(１)
行削除は、一つ前のセルに移動した後、next フィールドを更新する。
Ｔｄｅｌｅｔｅ(ｎ)＝ｎ＋１＝Ｏ(ｎ)
問 6.3.1 現在行の内容を変更するコマンドを実現せよ。
問 6.3.2 データが更新されたかどうかを判定するフラグを追加し、エディタ終了時にデータが更新されていれば、その旨をユーザに確認する処理を実現せよ。
問 6.3.3 先頭行へ移動するコマンドと最終行へ移動するコマンドを実現せよ。
問 6.3.4 行の内容を表示する際に行番号も表示するようにせよ。
問 6.3.5 行番号を指定した移動コマンドを実現せよ。
問 6.3.6 行番号を指定した削除・挿入コマンドを実現せよ。
６．４ 双方向リストの実現
双方向リストとは、情報を保持するフィールドと前の情報・次の情報の位置を示すフィールドから構成されるセルが下図のように双方向に接続されているものである。
セルは、情報フィールド info と前のセルへのポインタフィールド prev、次のセルへのポインタフィールド next を持つ構造体として定義できる。
typedef struct cell {
DATATYPE info; /* データ型 DATATYPE の情報部 */
struct cell *prev; /* 前のセルへのポインタ */
struct cell *next; /* 次のセルへのポインタ */
} CellRec, *Cell;
（注）DATATYPE は情報フィールドの型であり、利用する問題によって変化する。
双方向リストに対して、挿入・削除・次のセルへの移動・前のセルへの移動を考える。
・次のセルへの移動
次のセル
c=c->next;
・前のセルへの移動
前のセル 現在のセル
c=c->prev;
・セルの挿入
セル c１ の後ろにセル c２ を挿入する。
c２->next=c１->next;
c２->prev=c１;
c１->next->prev=c２;
c１->next=c２;
・セルの削除
セル c を削除する。
削除するセル
prev=c->prev;
prev->next=c->next;
c->next->prev=prev;
c のセルを解放する
●アクセス関数
ａ．セルの生成
C=NEW(info)：情報 info を保持する新しいセル C を生成する
ｂ．情報フィールド
INFO(current)：現在のセル current の情報フィールドを返す
ｃ．次のセルへの移動
next=NEXT(current)：現在のセル current の次のセル next を返す
ｄ．前のセルへの移動
prev=PREV(current)：現在のセル current の前のセル prev を返す
ｅ．セルの挿入
new=INSERT(new, current)：現在のセル current の後ろにセル new を挿入し、セル new を返す
ｆ．セルの削除
prev=DELETE(current)：現在のセル current を削除し、前のセル prev を返す
●データ構造
ａ．セル構造体
typedef struct cell {
DATATYPE info; /* 情報部のデータ型 */
struct cell *prev; /* 前のセルへのポインタ */
struct cell *next; /* 次のセルへのポインタ */
} CellRec, *Cell;
ｂ．情報部のデータ型
情報部では、行の内容を表現するため、DATATYPE を文字列（char *）とする。
○コーディング
【NEW操作】
Cell NEW(DATATYPE info)
{
Cell new;
new=malloc(sizeof(CellRec));
if(new!=NULL) {
new->info=info;
new->next=new->prev=NULL;
}
return(new);
}
【INFO操作】
DATATYPE INFO(Cell cell)
{
return(cell->info);
}
【NEXT操作】
Cell NEXT(Cell cell)
{
return(cell->next);
}
【PREV操作】
Cell PREV(Cell cell)
{
return(cell->prev);
}
【INSERT操作】
Cell INSERT(Cell new, Cell cell)
{
new->next=cell->next;
new->prev=cell;
cell->next->prev=new;
cell->next=new;
return(new);
}
【DELETE操作】
Cell DELETE(Cell cell)
{
Cell prev;
prev=cell->prev;
if(prev!=NULL) {
prev->next=cell->next;
cell->next->prev=prev;
free(cell);
}
return(prev);
}
○時間量
セルのフィールドを参照・更新する回数により評価する。
・次のセルへの移動は、セルの next フィールドを１回参照する。
・前のセルへの移動は、セルの prev フィールドを１回参照する。
・セルの挿入は、next フィールドを２回参照、２回更新し、prev フィールドを２回更新する。合計６回である。
・セルの削除は、next フィールドを２回参照、１回更新し、prev フィールドを１回参照、１回更新する。合計５回である。
線形リストと比較すれば、前のセルへの移動はセルの個数によらず１になり、非常に高速であるが、セルの挿入と削除は prev フィールドの処理のため遅くなる。
○領域量
線形リストと双方向リストでは、セルの数は同じとなる。１つのセルの占める領域は、全てのフィールドが同じ大きさならば、双方向リストは線形リストの１．５倍の領域を必要とする。
問 6.4.1 問 6.2.1、問 6.2.2 を双方向リストで実現せよ。
問 6.4.2 問 6.2.3、問 6.2.4、問 6.2.5 を双方向リストで定義せよ。
６．５ 双方向リストによるテキストエディタ
テキストエディタのためのアクセス関数を定義する。行構造体は線形リストと同様である。アクセス関数についても線形リストと異なる部分のみを記述する。
線形リストと双方向リストのアクセス関数では、PREV と DELETE の２つの操作の引数が異なるだけで、その他の操作に違いはない。したがって、エディタ用アクセス関数の違いは、PREV あるいは DELETE を呼び出している PrevLine および DeleteLine のみである。
○コーディング
【NewLine操作】
文字列 info の複製を strdup を用いて生成し、その複製を情報フィールドとして持つ新しいセルを生成する。
Line NewLine(char *info)
{
Line new;
if(info!=NULL) {
if((info=strdup(info))==NULL) { /* 行の複製 */
fprintf(stderr, "行データを生成できませんでした\n");
return(NULL);
}
}
if((new=NEW(info))==NULL) {
fprintf(stderr, "行構造体を生成できませんでした\n");
exit(1);
}
return(new);
}
【ReadFile操作】
linebuf に読み込んだ各行の行構造体 L を生成し、現在行 E->current の後ろに挿入して行く。ファイルが空でなければ、読み込んだ先頭行を現在行にする。
void ReadFile(Editor E, char *F)
{
FILE *stream;
Line L, new;
if((stream=fopen(F, "r"))==NULL) {
fprintf(stderr, "!!!!! %s は読めません !!!!!\n", F);
return;
}
for(L=E->current; fgets(linebuf, LINE_SIZE, stream)!=NULL;
L=NEXT(L)) {
new=NewLine(linebuf);
INSERT(new, L);
}
fclose(stream);
if(E->current!=L)
E->current=NEXT(E->current); /* 先頭行を指す */
}
【WriteFile操作】
１行目から最終行のセルを辿りながら、各セルの内容をファイルに書き込む。
void WriteFile(Editor E, char *F)
{
FILE *stream;
Line L;
if((stream=fopen(F, "w"))==NULL) {
fprintf(stderr, "!!!!! %s は書けません !!!!!\n", F);
return;
}
for(L=NEXT(E->top); L!=NULL; L=NEXT(L))
fputs(INFO(L), stream);
fclose(stream);
}
【NextLine操作】
NEXT操作で次のセルへ移動する。次のセルがない場合（NULLの場合）には、最終行であることを表示し、セルの移動を行わない。
【PrevLine操作】
現在の行が０行目でなければ、PREV操作で前のセルへ移動する。現在行が１行目ならば、０行目（<<<<< 先頭行 >>>>> の表示）に移動し、１行目の前への行挿入を可能にする。
【InsertLine操作】
標準入力から読み込んだ新しい行のデータには改行コードがないため、改行コードを追加する。 NewLine操作により、このデータを持つ新しいセルを生成し、INSERT操作で現在行の後ろに挿入する。挿入した行を現在行とする。
void InsertLine(Editor E, char *line)
{
int length;
length=strlen(line);
line[length]='\n'; line[length+1]='\0'; /* 改行コードの挿入 */
E->current=INSERT(NewLine(line), E->current);
}
【DeleteLine操作】
０行目の削除についてはエラーメッセージを出力する。strdup で割り当てた行データを解放し、DELETE操作により現在行を削除するために、PREV操作で前の行に戻る。削除後は、削除された行の次の行を現在行にする。
void DeleteLine(Editor E)
{
Line L;
if(E->current==E->top)
fprintf(stderr, "!!!!! 先頭行は削除できません !!!!!\n");
else {
free(INFO(E->current));
E->current=DELETE(E->current);
L=NEXT(E->current);
if(L!=NULL)
E->current=L;
}
}
【ListLine操作】
現在行の内容を標準出力に出力する。
void ListLine(Editor E)
{
printf("%s", INFO(E->current));
}
【Quit操作】
終了する。本来ならば、データに変更がある場合はユーザに確認する処理が必要である。
void Quit(Editor E)
{
exit(0);
}
【Error関数】
未定義のコマンドが指定された場合に、エラーメッセージを出力する。
void Error(char *message)
{
fprintf(stderr, "!!!!! コマンド %s 解析不能 !!!!!\n", message);
}
【main関数】
CREATE操作でエディタ構造体を生成し、ファイル名が指定されていればその内容を読み込む。標準入力から読み込んだユーザのコマンドの種類に応じてテキストエディタのためのアクセス関数を呼び出す。
char linebuf[LINE_SIZE];
void main(int argc, char **argv)
{
Editor E;
switch(argc) {
case 1: E=CREATE();
break;
case 2: E=CREATE();
ReadFile(E, argv[1]);
break;
default:
fprintf(stderr, "使用法: %s [ファイル名]\n", argv[0]);
exit(1);
}
while(gets(linebuf)!=NULL) {
switch(linebuf[0]) {
case 'r': ReadFile(E, linebuf+1); break;
case 'w': WriteFile(E, linebuf+1); break;
case 'n': NextLine(E); break;
case 'p': PrevLine(E); break;
case 'i': InsertLine(E, linebuf+1); break;
case 'd': DeleteLine(E); break;
case 'l': break;
case 'q': Quit(E); break;
default: Error(linebuf);
}
ListLine(E);
}
}
○時間量
ｎ行のデータを処理している場合に、次行への移動、前行への移動、行挿入、行削除に関して、セルを辿る回数とセルへの代入操作の回数の和を時間量として評価する。
次行への移動は、セルの next フィールドを１回辿るだけである。
Ｔｎｅｘｔ(ｎ)＝１＝Ｏ(１)
前行への移動は、セルの prev フィールドを１回辿るだけである。
Ｔｐｒｅｖ(ｎ)＝１＝Ｏ(１)
行挿入は、現在行の後ろに挿入するので、セルを辿る必要はないが、next/prev フィールドを２つずつ更新する必要がある。
Ｔｉｎｓｅｒｔ(ｎ)＝４＝Ｏ(２)
行削除は、next/prev フィールドを１つずつ更新する。
Ｔｄｅｌｅｔｅ(ｎ)＝２＝Ｏ(１)
問 6.5.1 問 6.3.1〜問 6.3.6 の問題を双方向リストについて解け。