プログラミング学習

データ構造の続きを説明します。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 ‘}’があれば Pop Popの時にStackがEmptyであれば、エラーで ”}”が多すぎる すべての行が読み終わったときに、Stackに ‘{‘が残っていればエラー ”{“が多すぎる StackがEmptyであれば、Balanced Python Program #Use Stack.append, Stack.pop import csv import os def 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) # main with 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;&gt; 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 &gt; 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;&gt;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; 著者：松尾正信株式会社京都テキストラボ代表取締役

プログラミング学習 Day 12：Software Test-Coverage

プログラミング学習 Day 11：Agile Scrum

プログラミング学習 Day 10：プロジェクト管理手法：Agile (アジャイル）

プログラミング学習 Day 9：Software test, pytest

プログラミング学習 Day 8：ソフトウエアのテスト技法

プログラミング学習 Day 7：Database Semantics

プログラミング学習 Day 6：DataBase, Relational Data Model

プログラミング学習 Day 5：Programming-File

プログラミング学習 Day 4：データ型、オブジェクト・Class

プログラミング学習 DAY 3 : Stack, Queue, etc