Program Design (プログラム設計）

5. Control-flow design representations
制御の流れの設計表現
The structure chart（構造図）
The Jackson Structure Diagram（Jackson構造図）
The flowchart（フローチャート）
The Nassi-Shneiderman diagram（ NassiShneiderman図）
The Production Rule Notation (PRN)（生産規則
記号）
The Java-based pseudocode（Javaの擬似コード）
5.1 The structure chart（構造図）
The structure chart is a tree-like structure diagram that supports the
top-down design. The structure chart uses the following three
components：（構造図は、木のような形で、 top-down 設計を支え
る。構造図は、次の三つの分品を使う）
The box is used to represent a function or procedure.（箱は機能
又は操作を表す）
The arc between a high level procedure and a low level procedure
denotes a procedure invocation.（弧は操作の呼び出すを表す）
The side-arrows represent data flows in terms of parameterpassing. The side-arrows are optional to use, depending on how
detailed information about the system needs to be shown on the
chart.（側面の矢印はデータの流れを現す）
The graphical representation
A
a6
a1
a4
B
C
a3
a2
B1
B2
D
a5
a8
C1
a7
D1
D2
Procedure A invokes B, C, and D（操作Aは操作B,C,Dを呼び出す）;
procedure B invokes B1 and B2;procedure C invokes C1; and
procedure D invokes D1 and D2.
Example of a structure chart without side-arrows
（側面の矢印を持っていない構造図）
Personal Expenses
Management System
Take Input
Command
Input Item Data
Register Items
Display Single Item
Register Item
Output
Confirmation
Message
Display All Items
Obtain All Items
Data
Calculate Total
Make Item Table
Example of a structure chart with side-arrows
（側面の矢印を持っている構造図）
Personal Expenses
Management System
total-amount
command
Take Input
Command
Input Item Data
Register Items
Display Single Item
Register Item
Output
Confirmation
Message
Display All Items
Calculate Total
items-table
all-items-list
Obtain All Items
Data
Make Item Table
Important points about the structure
chart（構造図についての重要点）
The structure chart usually supports top-down design, but it does
not necessarily mean it cannot support bottom-up design.（構造図
は一般にtop-down設計を支えるが、 bottom-up設計を支えない訳
ない）
The decomposition of a high level procedure is a collection of
lower level procedures that are invoked by the high level process
during its execution.（高いレベルの操作を分解した結果は、呼び
出される低いレベルの操作の集合である）
There is no indication of the order of invoking low level procedures
by a high level procedure.（構造図は低いレベルの操作を呼び出
す順番を示していない）
It is usually difficult to draw many side-arrows, and therefore very
inconvenient in modeling complex invocations of low level
procedures. （側面の矢印が多くと、構造図は複雑になってしまう。
そのため、複雑な設計には、側面の矢印を持つ構造図の構築は
難しい）
5.2 The Jackson Structure
Diagram（Jackson構造図）
The Jackson Structure Diagram is a notation used in
JSP (Jackson Structured Programming), which
was invented by Michael Jackson. （Jackson構造
図は、Michael Jacksonに発明され、JSPに使わ
れる表現である）
This diagram is similar to the structure chart, but has
additional expressive power: it also describes the
sequence, selection, and iteration of procedure
invocations. （Jackson構造図は、構造図に似ている
が、もっとアルゴリズムらしい表現である）
The basic forms of Jackson Structure Diagram:
（基本表現：）
Task1
Task2
Task3
Task4
Sequence
This diagram denotes that Task1 is implemented by the sequence
construct written in Structured English:
Task2;
Task3;
Task4;
（この図は、Task1の機能が、Task2、Task3,Task4の順次的な実行と
して定義することを表す）
Task1
Task2
Task3
Selection
This diagram represents that Task1 is implemented by the choice
construct given in Structured English:
if C
/*C is added during the translation */
then Task2
else Task3
end-if
（この図は、Task1の機能が、Task2とTask3から構成された選択構造
として定義することを表す）
Task1
Task2
*
Iteration
This diagram describes that Task1 is implemented by the iteration
construct in Structured English:
while C do
/*C is added during the translation*/
Task2;
Update control variable;
end-while
（この図は、Task1がTask2から構成された反復構造として定義するこ
とを表す。）
Example
Register
Items
Register
One Item
Register
Item Name
Register
As Food
Register
Item Price
Register
As Others
*
Register
Item Shop
Register
Item Date
5.3 The Flowchart （
The flowchart is a graphical notation that describes
control flows among functions, possibly under
certain conditions.
The flowchart is more suitable for detailed design,
since rather detailed information of an algorithm is
usually provided, such as conditions and the order
of executions of functions.
However, the Hierarchical Flowchart can also be
used for abstract design.
The basic components of the
flowchart
condition
(a) Diamond
Task
(b) Rectangle
(c) arrow
Diamond denotes a condition; rectangle denotes a
function; and arrow represents a control flow.
The basic forms of the flowchart
yes
task1
task2
Sequence
no
yes
C
task1
task2
Choice
no
C
task1
Iteration
C
v1
Task1
v2
v8
Task2
Task8
Multiple selection
Example
total = 0;
foodTotal = 0;
clothTotal = 0;
othersTotal = 0;
no
End of expenses-file?
Output foodTotal;
Output clothTotal;
Output othersTotal;
Output total
Read item
yes
no
is-Food(item)?
foodTotal += item.price
yes
yes
is-Cloth(item)?
clothTotal += item.price
Make the next item ready
no
othersTotal += item.price
Hierarchical flowcharts
Hierarchical flowcharts are built by decomposing
high level functions into lower level flowcharts.
Let us first look at an abstract description of a
hierarchical flowcharts, and then look at a specific
example.
yes
c1
no
1
no
c2
yes
2
3
(a) the top level flowchart
1.1
3.1
no
c3
yes
c4
no
yes
3.2
1.2
3.3
1
Obtain all items purchased
at the given shop from the
expenses-file
2
Calculate the total cost of
these items
(a) the top level flowchart
End of
expenses-file?
yes
yes
no
no
1.1
Get the
next item
item.shop =
the given shop?
End of the
item list?
2.1
Get next item
from the list
no
2.2
total +=
item.price
yes
1.2
Put the item on
the item list
(c) the decomposition of task 2
(b) the decomposition of
task 1
5.4 The Nassi-Shneiderman diagram
(N-S diagram)
（N-S図）
The N-S diagram is similar to the flowchart, but doesn’t use arrows. （ NS図は、フローチャートに似ているが、制御の流れを表現する矢印を
使わない）
The motivations of inventing N-S diagram:（N-S図を開発した
動機）
Enforce the use of only single-entry and single-exit constructs to
ensure that designed programs are all structured programs.（一つの入
り口と出口を持つプログラム構造のみを使わせることにより、構造
化プログラムを作成することを保証する）
Use graphical notation with less space than the flowchart. （少ない紙
面を占める図を使うことにより、設計の紙面を節約する）
5.4.1 The basic components of
the N-S diagram
if condition
Task1
if condition
T
F
Task2
Task1
No
task
T
F
Task1
Task2
Task3
Sequence
case of
value1
e
value2
Task1
if-then choice
Task2
if-then-else choice
while condition
value3
Task3
Mulitiple selection
Task1
Iteration (while-do)
Example（事例）
total = 0;
foodTotal = 0;
clothTotal = 0;
othersTotal = 0;
while not end of expenses-file
Read item
is-Food(item)
T
F
is-Cloth(item)
T
foodTotal += item.price
F
clothTotal +=
item.price
othersTotal +=
item.price
Make the next item ready
Output total;
Output foodTotal;
Output clothTotal;
Output othersTotal
5.5 The Production Rule Notation
(PRN)
（生産規則記号PRN）
PRN is a textual notation for program design, with the following
features:（PRNは、次の特徴を持つテキスト言語である）
It offers an effective mechanism for defining operations in a topdown manner. （トップドン設計を支え、操作を定義する有効な仕組
みを提供している）
It is suitable for both abstract and detailed design.（PRNは、抽象設
計と詳細設計に使用できる）
It uses much less space than the graphical notations, such as the
Structure chart, Jackson Structure Diagram, Flowchart, and N-S
Diagram.（図の言語と比べて、設計紙面を大幅に節約する）
It can be easily transformed into code (program written in a specific
programming language).（コードへ変換しやすい）
5.5.1 The representation of an
operation（操作の表現）
The fundamental concept in PRN is operation. An
operation has the following possible forms:（PRNの基本要
素は、「操作」という。操作は次の四つの形式を取れる）
<OP>
/*operation without input and output（入力とし出力がな
い操作）*/
[I1, I2, …, In]<OP> /*input-only operation （入力のみを持つ操
作）*/
<OP>[O1, O2, …, Om] /*output-only operation（出力のみを持つ
操作）*/
[I1, I2, …, In]<OP>[O1, O2, …, Om]
/*operation with both input and output（入力と出力を持つ操
作*/
Example(事例）
(1) <Check Errors>
(2) [item-name]<Find All Items>[items-list]
(3) [book-title, price]<Input>
(4) <Display Totals>[foodTotal, clothTotal,
othersTotal>
5.5.2 The definition of operation
(操作の定義）
An operation OP is defined in the form:（操作を次の形で定
義する）
OP ---> Statement end-op
The Statement has two types: basic and compound
statements（二つの種類のStatementがある。基本
と複合Statementである）
The basic statements
（基本Statements)
Operation /*this means to call or invoke an
operation （操作の呼び出し）*/
Example:
[item-name]<Find All Items>[items-list]
<V := E> /*assignment statement（代入文）*/
<Read>[O1, O2, …, Om] /*read from outside the
program system. （プログラムインタ
フェースから読み込む）*/
[I1, I2, …, In]<Write> /*Write to the output
device （出力デバイスへ書き込む）*/
The compound statements（複合文）
S1 ; S2 /*Sequence of statements*/
S1 |C /* if-then statement: if condition C is true, statement S1 is
executed. Otherwise, S1 is not executed.*/
S1 |C S2 /* if-then-else statement: if C is true, S1
is executed; otherwise, S2 is executed. */
case expression of
v1: S1;
v2: S2;
…
vn: Sn
end-case
{S1}C /*while-do statement: while C is true, S1 is repeatedly
executed until C becomes false. */
begin S1 end /*block statement: equivalent to the compound
statement S1. */
Example of operation definition
（操作の定義の事例）
[expenses-file, shop-name]<Calculate the total cost
of all items purchased at the given shop>[total]
--->
[expenses-file, shop-name]<Obtain all
items purchased at the given shop from the
expenses-file>[items-list];
[items-list]<Calculate the total cost>[total]
[expenses-file, shop-name]<Obtain all
items purchased at the given shop from the
expenses-file>[items-list] --->
{[expenses-file]<Get the next item>[item];
[item]<Put the item on items-list>[items-list]
|item.shop = shop-name
}not end of expenses-file
[items-list]<Calculate the total cost>[total] --->
{ [items-list]<Get next item from the list>[item];
[item]<total := total + item.price>[total]
}not end of items-list
Advantages of PRN
（PRNのいいところ）
The name of an operation can be as long as
necessary. Thus, one can choose freely the name
that describes the function of the operation best.
（長い操作名を使える）
The order of defining operations is consistent
with the way of developing design ideas.（操作定
義の順番が重要でない）
PRN has a good readability, due to both the clear
syntax and the way to define operations.（PRN設
計書は読みやすい）
PRN can be easily translated into a
programming language, e.g., C, Java.（PRN
設計からプログラムへの変換を行いやす
い）
PRN takes less space than the graphical
notations, such as the Structure chart,
Jackson Structure Diagram, Flowchart, and
N-S Diagram.（PRN設計書は、図言語より
小さい紙面を占める）
5.6 Java-based pseudocode
（Java擬似コード）
Pseudocode is similar to a program code, but allows the use of natural
language (e.g., English) for abstraction of functions. These
functions are usually complex at the time and they need further
decomposition, to be performed at later stage.（擬似コードは、プロ
グラムコードに似ているが、ある部分を自然言語で表現する）
Java-based pseudocode is similar to program code written in Java;
that is, the pseudocode structure is similar to that of a Java program,
but natural language descriptions are allowed to abstract complex
functions.（Java擬似コードとは、Java言語の構文に基くある部分
の機能を自然言語で表現したプログラムのようなものである）
Pseudocode is suitable for detailed design.（擬似コードは詳細な設計
に適切である）
The difference between Structured
English and Pseudocode
（構造化英語と擬似コードの違い）
In Structured English we emphasize the use of
English, but expect to improve its structure by
using programming language constructs, such as
sequence, choice, and iteration. While in
pseudocode we emphasize the use of
programming language, but to expect to improve
its readability by using proper English for abstract
description of functions.
Example（擬似コードの事例）
A pseudocode for computing the average of 10 integers:
int a[] = new int[10];
int total = 0, count = 0;
double average = 0;
Input 10 integers to array a;
Obtain the total of the integers in array a;
average = (double) total / a.length;
Decomposition（分解）
Obtain the total of the integers in array a:
while (count < a.length)
{
total += a[count];
count++;
}
Advantages of pseudocode
（擬似コードの長所 )
It is easy to learn, if one knows the specific programming
language well.（勉強しやすい）
It is natural and effective for detailed designs.（詳細な設
計に対して、有効及び自然的な表現である）
It is easy to be translated into program code.（プログラム
コードへの変換をしやすい）
Disadvantage of pseudocode
（擬似コードの短所）
Pseudocode is usually language-specific, therefore,
it is not suitable for high level design.（擬似コード
は、一般にプログラミング言語に依存するので、抽
象設計には、適切でない。
Exercise 5
1. Use Structured English to describe the following
Jackson Structure Diagram.（次のJackson Structure
DiagramをStructured Englishで表現しなさい）
Register
Items
Register
One Item
Register
Item Name
Register
As Food
Register
Item Price
Register
As Others
*
Register
Item Shop
Register
Item Date
2. Give a flowchart describing the following Jackson
Structure Diagram. （フローチャートで次のJackson
Structure 図を表現しなさい）
Register
Items
Register
One Item
Register
Item Name
Register
As Food
Register
Item Price
Register
As Others
*
Register
Item Shop
Register
Item Date
3. Give a N-S diagram for the flowchart resulted
from problem 2.（課題２で作成されたフロー
チャートをN-S図で表現しなさい）
4. Give a Java-based pseudocode for the following
PRN operation definitions:（次のPRN設計書を
Java擬似コードで表現しなさい）
[expenses-file, shop-name]<Calculate the total cost
of all items purchased at the given shop>[total]
--->
[expenses-file, shop-name]<Obtain all
items purchased at the given shop from the
expenses-file>[items-list];
[items-list]<Calculate the total cost>[total]
[expenses-file, shop-name]<Obtain all
items purchased at the given shop from the
expenses-file>[items-list] --->
{[expenses-file]<Get the next item>[item];
[item]<Put the item on items-list>[items-list]
|item.shop = shop-name
}not end of expenses-file
[items-list]<Calculate the total cost>[total] --->
{ [items-list]<Get next item from the list>[item];
[item]<total := total + item.price>[total]
}end of items-list
5. Give a Jackson Structure Diagram describing the
following PRN operation definitions:（次のPRN操作の定
義をJackson Structure図で表現しなさい）
[x1, x2]<A>[y1, y2, y3]
---> [x1]<B1>[z1]; [z1]<B2>[y1];
[x2]<B3>[y2] | x2 > 0 [x2]<B4>[y3]
[x1]<B1>[z1]
---> <z1 := x1 + 5>
[z1]<B2>[y1]
---> <y1 := 0>;
{<y1 := y1 + z1>; <z1 := z1 – 1>}z1 > 0
Hint: there is no need to consider the detailed conditions in
the generated Jackson Structured Diagram.

Download Report