My開発メモ

Pascalでリストを使う(Free Pascal)

『アルゴリズムとデータ構造』は「聖書」

Youtubeで “ゆるコンピュータ科学ラジオ”というのに今はまってて、その中で
『アルゴリズムとデータ構造 / 岩波講座ソフトウェア科学3』という本の
紹介があったので、その本を図書館で借りてきた。
(この本のことを「聖書」と呼んでいた)

この本では、最初に”アルゴリズムと計算量”についての話があり、次に”データ構造”についての話があった。

サンプルとして掲載されているコードは Pascal で、プログラムの内容をわかりやすく
説明するのに Pascal が向いているということなんだろう。

ただ、この本に書かれているコードをそのまま入力しても動作しない。
あくまで、処理の内容を説明するためのものである。

しかし、せっかくだし、実際に動かしてみることにした。

Ubuntuに Pascal処理系をインストールすることについては、

このとおりにやった。

リストをプログラムする

今回、記述したのは、同書 p30 の「リスト」である。
まず、僕の書いたコード全体を掲載する。

mylist.pas

program mylist;

type
   list = ^cell;
   cell = record
             element : string;
             next    : list;
          end;
var
   listhead : list;
   p        : list;

procedure init;
var
   list2th : list;
   list3th : list;
   list4th : list;
begin
   new(listhead);
   listhead^.element := 'first';
   listhead^.next := nil;

   new(list2th);
   list2th^.element := '2th';
   list2th^.next := nil;
   listhead^.next := list2th;

   new(list3th);
   list3th^.element := '3th';
   list3th^.next := nil;
   list2th^.next := list3th;

   new (list4th);
   list4th^.element := '4th';
   list4th^.next := nil;
   list3th^.next := list4th;
   
end;

begin
   init;
   p := listhead;
   while p <> nil do
      begin
         writeln(p^.element);
         p := p^.next;
      end;
end.

コードの説明

プログラム名

program mylist;

Pascalでは最初にプログラム名を書くみたい。
実際のファイル名と同じでなくてもコンパイルはできるけれど、同じにしている人が大多数みたい。

リスト定義部

type
   list = ^cell;
   cell = record
             element : string;
             next    : list;
          end;

リストの定義部。
string型のelement と list型のnext を内容とする レコード型を定義し、
それに cell という名前を与えている。
そして、その cellへのポインタ として、listを定義している。
ポインタというのは、この場合、cellが格納されたメモリ上のアドレスと僕は理解している。
しかし、この段階では定義しているだけなので、実際にメモリ上に確保されているわけではない。

変数定義部

var
   listhead : list;
   p        : list;

変数の定義部。
ここでの変数はグローバル変数。
一番下の begin…end.部で使用する変数を定義する。

初期化処理

procedure init;
var
   list2th : list;
   list3th : list;
   list4th : list;
begin
   new(listhead);
   listhead^.element := 'first';
   listhead^.next := nil;

   new(list2th);
   list2th^.element := '2th';
   list2th^.next := nil;
   listhead^.next := list2th;

   new(list3th);
   list3th^.element := '3th';
   list3th^.next := nil;
   list2th^.next := list3th;

   new (list4th);
   list4th^.element := '4th';
   list4th^.next := nil;
   list3th^.next := list4th;
end;

procedure というは、戻り値のない関数みたいなもので、”手続き”と呼ばれている。
ここで、procedure init; と書いたが、コンパイルエラーは出なかった。
procedure init(); と書いてもコンパイルできた。

次に、この手続き部で使用するローカル変数を定義している。
後述のコードのように簡潔に記述できるが、ここでは、わかりやすさを重視して、
あえて冗長に書いてみた。

begin部が実際の処理である。

new(listhead);

listheadはこのリストの最初のセルである。これをメモリ上に確保する。
つまり実体化する。
そして、その中の element部分に ‘first’という文字列をセットする。
この時、メモリ上に確保された listheadというセルを参照するには、

listhead^

と書かねばならない。

もし、listhead だけなら、コンパイルできない。

次の next部分は、次のセルへのポインタを指定するのだが、現在のセルは先頭セルで、
次のセルはまだできていないから、nil を代入しておく。

次に、2つめのセル list2th を作成する。

new(list2th);

として、メモリ上に確保する。
そして、emement部に、このセルを表す’2th’を代入する。
また、next部にも、nil を代入しておく。

で、この2つめのセルができたので、このセルへのポインタを
1つめのセル listhead の next部に代入しておく。
こうすることで、listhead^.next とすることで、このセルを呼び出せる。

以下、同様にして、list3th、list4th を作っておく。
list4th は最後尾なので、list4th^.next は nil のままである。

メイン処理部

begin
   init;
   p := listhead;
   while p <> nil do
      begin
         writeln(p^.element);
         p := p^.next;
      end;
end.

メイン処理部である。

まず、init; として、init手続きを実行する。

次に、変数p に listhead つまり、リストの先頭セル へのポインタを代入する。
この 変数p が while部の中で、リストの各セルを次々と代入することになる。

while は p が nil でない限り、以下を繰り返す。
pセル の element(文字列)を表示する。
p^.next が指す次のセルへのポインタを p に代入することにより、
p を 次のセルとする。

以上で、『アルゴリズムとデータ構造』p30 のコードが書けた。

実行例

$ fpc mylist
Free Pascal Compiler version 3.2.2+dfsg-9ubuntu1 [2022/04/11] for x86_64
Copyright (c) 1993-2021 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling mylist.pas
Linking mylist
50 lines compiled, 0.1 sec

$ ./mylist
first
2th
3th
4th

ちゃんと動いた。

付録・簡潔なコード

procedure init の箇所の簡潔なコードは、以下である。

procedure init;
var
   now  : list;
   prev : list;
   i    : integer;
   s    : string;
begin
   new(listhead);
   listhead^.element := 'first';
   listhead^.next := nil;
   prev := listhead;
   i := 1;
   while i < 10 do begin
      new(now);
      str(i, s);
      now^.element := 'ele' + s;
      now^.next := nil;
      prev^.next := now;
      prev := now;
      i := i + 1;
   end;
end;

実行例

$ ./mylist
first
ele1
ele2
ele3
ele4
ele5
ele6
ele7
ele8
ele9