プログラミング　Python　PASCAL – 京都テキストラボ情報＆教育サイト

データ構造の続きを説明します。HLPのプログラミングを正確に、バグが少なくなるようにいろんなデータ構造が発案されています。以下はその中でも代表的なものを紹介します。 ■Stack（スタック） スタックというデータ構造を考えてみましょう。満員電車で、扉のしまる寸前に飛び込んだ人は、次の駅で扉が開いたときには真っ先に外に出なければなりません。最後に入れたものを最初に出す、（LIFO）という構造をスタックと呼びます。PASCALのシンタックスで、ブロックの始まりと終わりの記号としてbegin endを使いますが、endを忘れていたりすることがよくあります。PHPですと、カッコ ｛ ｝でくくる必要があります。一行のみのデータを読み込んで、カッコ｛ ｝のバランスをチェックするプログラムを作ります。日常語によるロジックの説明は下記の通り。画面入力より1行のデータを読み込む。読み込んだ文字列を最初から順番に取り出す。もし、取り出した文字が’{‘ があれば、スタックに’{‘をPushもし、’}‘ があれば、スタックをPopして文字を取り出すスタックが空であれば、エラー(no Balanced)最後に スタックが空ではなく、残っていればエラー（no Balanced)以下のプログラムはPOPとPUSHとIsBalancedに分けて、それぞれをコンパクトにしています。program Kakko_1;{$mode objfpc}{$H+}uses SysUtils;type TCharStack = array of Char;procedure Push(var st: TCharStack; c: Char);begin SetLength(st, Length(st) + 1); st[High(st)] := c;end;function Pop(var st: TCharStack): Char;begin if Length(st) = 0 then Exit(#0); Result := st[High(st)]; SetLength(st, Length(st) - 1);end;function IsBalanced(const s: string): Boolean;var st: TCharStack; i: Integer; c, t: Char;begin st := nil; for i := 1 to Length(s) do begin c := s[i]; if (c = '{') then Push(st, c) else if (c = '}') then begin t := Pop(st); if (t = #0) then Exit(False); end; end;//スタックが空であれば、結果がTrue Result := Length(st) = 0;end;var line: string;begin Write('Input> '); if Eof then Exit; ReadLn(line); if IsBalanced(line) then WriteLn('Balanced') else WriteLn('Not balanced');end.これを、Pythonでコードを書いてみます。List構造を使った簡単なプログラムです。こちらは複数行にまたがったカッコのペアのバランスをチェックします。まず、StackのPopとPushを表現する関数を作ります。次に、CSVファイルを各行ごとに読み込んでSpaceで区切られるStringをListに入れる。そのListから、要素を順番に取り出して、’{‘ があれば、Push‘}’があれば PopPopの時にStackがEmptyであれば、エラーで ”}”が多すぎるすべての行が読み終わったときに、Stackに ‘{‘が残っていればエラー ”{“が多すぎるStackがEmptyであれば、BalancedPython Program#Use Stack.append, Stack.popimport csvimport osdef stack_push(stack,item): stack.append(item) print ("after pushstack",stack)def stack_pop(stack): if (len(stack)==0): print ("empty") print ("error:less }") else: x=stack.pop(len(stack)-1) print ("popped ",x)# mainwith open('stackdata.csv',encoding='utf-8') as h: reader = csv.reader(h,delimiter=' ') st = [row for row in reader]gstack=[]for i in range(len(st)): line=st[i] for k in range(len(line)): if (line[k]=='{'): stack_push(gstack,'{') elif (line[k]=='}'): x=stack_pop(gstack) else: print ("no")print("finally ",gstack)if (len(gstack)==0): print ("balanced")else: print ("Error:Unbalanced more }") ■QUEUE（キュー） 次は、キュー（Queue）というデータ構造を考えます。これは、スタックと違って、順番に入ったものは順番に出ていく。FIFOです。レストランで順番を待っているとき、呼ばれるのがこのFIFOです。QUEUEの中に、予約の入っている人の名前を入れる。席が空いたときは順番に名前を呼び出す。プログラムの設計では、データ構造として、ノードには、名前を入れるValueと次のノードへのポインタを入れている。QUEUEはオブジェクトを使って指定する。頭と尾のポインタとカウントを持つ。手続き（Procedure)として３つ、初期値設定、キューに入れる、キューを開放する。関数（Function）として次の３つ。キューから取り出す、キューが空かどうかの判定、キューの中にある数。program junbanmachi;{$mode objfpc}{$H+}uses SysUtils;type PNode = ^TNode; TNode = record Value: string; Next: PNode; end; TLinkedQueue = object private head, tail: PNode; cnt: Integer; public procedure Init; procedure Enqueue(const s: string); function Dequeue: string; function IsEmpty: Boolean; function Count: Integer; end;procedure TLinkedQueue.Init;begin head := nil; tail := nil; cnt := 0;end;procedure TLinkedQueue.Enqueue(const s: string);var p: PNode;begin New(p); p^.Value := s; p^.Next := nil; if tail = nil then begin head := p; tail := p; end else begin tail^.Next := p; tail := p; end; Inc(cnt);end;procedure TLinkedQueue.Done;var p: PNode;begin while head &lt;> nil do begin p := head; head := head^.Next; Dispose(p); end; tail := nil; cnt := 0;end;function TLinkedQueue.Dequeue: string;var p: PNode;begin if head = nil then raise Exception.Create('Dequeue from empty queue'); p := head; Result := p^.Value; head := head^.Next; if head = nil then tail := nil; Dispose(p); Dec(cnt); if head = nil then tail := nil;end;function TLinkedQueue.IsEmpty: Boolean;begin Result := head = nil;end;function TLinkedQueue.Count: Integer;begin Result := cnt;end;// テスト部分 キューに3名の名前を入れますvar q: TLinkedQueue; s: string;begin q.Init; try q.Enqueue('masa'); q.Enqueue('ogawa'); q.Enqueue('yoshida'); WriteLn('Count=', q.Count);//キューから順番に取り出す while not q.IsEmpty do begin s := q.Dequeue; WriteLn('Dequeued: ', s); end; finally q.Done; end;end. ■LinkList（単方向リスト） 次は、単方向のリンクリストです。type PNode = ^TNode; TNode = record Value: Integer; Next: PNode; end;procedure AddFront(var head: PNode; v: Integer);var p: PNode;begin New(p); p^.Value := v; p^.Next := head; head := p;end;双方向のLinkListを使って、次に、バイナリツリーを実装します。 ■バイナリツリー バイナリーツリーの構造は階層構造を表現するときによく使われます。データーベースのIndexを作成したり、データを検索するときにツリーをトラバースすることで、検索時間を縮小できます。右のリンクと左のリンクをノードに持ちます。ツリーもノードに、右、左のノードへのリンクを入れます。下のプログラムでは、ノードに整数を入れます。ツリーを左からたどると数字の小から大の順に並んだ列が得られます。これを使うと、数字列のソートが可能になります。program BST;{$mode objfpc}{$H+}uses SysUtils;type PBNode = ^TBNode; TBNode = record Key: Integer; Left, Right: PBNode; end;procedure InsertNode(var root: PBNode; k: Integer);begin if root = nil then begin New(root); root^.Key := k; root^.Left := nil; root^.Right := nil; Exit; end; if k &lt; root^.Key then InsertNode(root^.Left, k) else if k > root^.Key then InsertNode(root^.Right, k); // duplicates: ignoreend;procedure PrintInOrder(root: PBNode);begin if root = nil then Exit; PrintInOrder(root^.Left); Write(root^.Key, ' '); PrintInOrder(root^.Right);end;//Main サンプルの数字列をBSTに入れるvar root: PBNode; keys: array[0..9] of Integer = (400,10,30,500,600,2,5,8,9,10); i: Integer;begin root := nil; // insert keys into Tree for i := 0 to High(keys) do InsertNode(root, keys[i]); Write('InOrder: '); PrintInOrder(root); WriteLn; end. ■応用問題１ バイナリーツリーを使った例として、最小の数字を出す関数は以下のようになります。 左端にあるツリーの終端ノードに入っている数字です。 function BSTMin(root: PBNode): Integer;begin if root=nil then raise Exception.Create('empty'); while root^.Left&lt;>nil do root:=root^.Left; Result := root^.Key;end; ■応用問題２ 与えられた数字がツリーの中にあるかどうかを判定する関数です。function BSTContains(root: PBNode; k: Integer): Boolean;begin if root=nil then Exit(False); if k=root^.Key then Exit(True); if k&lt;root^.Key then Result := BSTContains(root^.Left,k) else Result := BSTContains(root^.Right,k);end; 小見出しを3つ以上入れると、自動で目次が作成されます。この投稿のスラッグはprogramming3としてあります。次回からもprogramming#の形にするとわかりやすくてよいと思います。カテゴリーはComputer Science、プログラミング学習を選んでください。（この投稿では選択済み） 著者：松尾正信株式会社京都テキストラボ代表取締役

プログラミング学習 DAY 3