6
Data structure design
（データ構造の設計）
Data structure is one of the most important aspects
of a program:
Program = Data Structure + Algorithm
In a Structure Chart there is no definition of data-items involved. For
example, what do those arguments mean?（次の構造図で使われた
引数は、定義されていない）
A
a6
a1
a4
B
C
a3
a2
B1
B2
D
a5
a8
C1
a7
D1
D2
In a Jackson Structure Diagram there is no definition of data-items
involved.（次の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
In a flowchart there is no
definition of data-items.
E.g., expenses-file.
no
total = 0;
foodTotal = 0;
clothTotal = 0;
othersTotal = 0;
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
Data structures involved in design should be
defined in the form of being easily transformed into
corresponding data structures in programming
languages.（設計書に使われたデータ項目は、プロ
グラミング言語で実装しやすい形で定義すること
が必要である）
Design of data structures include the following
aspects:（データ構造の定義には、次のことを定義
すべきだ）
Define types and variables.（型と変数の定義）
Determine how the variables are used (e.g., are they
global or local? do they hold internal or external
data?)（変数の使い方を決まる）
6.1 Defining types and variables
First, we need to understand the following points about
programs:
Programs process directly variables denoting useful data.
A variable has the features:
It corresponds to a memory unit.
It has a name.
It has a value.
Every variable must be declared with a type, indicating
the range of the values the variable can take (e.g., x: T).
A type is a set of values together with a set of operations:
Type = set of values + set of operations
where the set of operations can be a single operation or
empty.（型は値の集合と操作の集合）
Examples of types:（型の事例）
int = {…, -1, 0, 1, …} + {+, -, *, /, …}
values
operations
real = {…, -1.5, -1.0, 0, 1.0, 1.5, …} + {+, -, *, /, …}
values
operations
WeekDays = {MONDAY, TUESDAY, WEDNESDAY,
THURSDAY, FRIDAY} +
{}
values
operations
A notation for type definitions
The design of data structures in the design phase should
focus on the issues:
The values of elementary data items.
The member data items and their values of composite data
items.
The structure of organizing data items.
By following this principle, a notation for defining types is
introduced next. This notation is part of the Structured
Object-Oriented Formal Language (SOFL), which can be
used for both abstract and detailed design.
Basic types (built-in types)
nat0: {0, 1, 2, …}
nat: {1, 2, 3, …}
int: {…, -1, 0, 1, …}
real: {…, -1.5, -1.0, 0, 1.0, 1.5, …}
string: {s | s is a sequence of characters}
enumeration: {A1, A2, …, An} (e.g., {DOG, CAT,
COW, HORSE})
subset of nat0: e.g., 1..8 (= {1, 2, …, 8})
9..100 (= {9, 10, …, 100})
and so on.
The form of defining a type
A = Texp
where Texp is a type expression.
For example,
Name = string
declares that every name in type Name is a string
of characters.
Composite type
In general, a composite type A is defined as
follows:
A = composed of
f1: Type-1
f2: Type-2
…
fn: Type-n
end
where f1, f2, …, fn are called fields of type A.
Example
Item = composed of
name: Name
price: real
shop: Name
date: Date
end;
/* Item is a composite type */
Date = composed of
day: 1..31
month: 1..12;
year: nat0
end
/* Date is another composite type */
Sequence types
A sequence type is an abstract representation of the
concrete data types available in programming
languages, such as array, vector, linked list, and file.
Two forms of sequence type definitions:
(1) A = seq of Type-1
(2) A1 = seq[n] of Type-1
(1) states that A is a set of sequences, each consisting of a
list of data items in type Type-1. (2) states that A1 is a
set of sequences, each consisting of a list of at most n
data items in Type-1. That is, every sequence in type
A1 has at most n data items.
Examples
Item-List = seq of Item; /* illustration:
Item-List = {
[ ], [a], [a1, a2], [b1, b2, b3], …, [c1, c2,
…, cn]
}
/*
Item = composed of
name: Name
price: real
shop: Name
date: Date
end;
/* Item is a composite type defined
before*/
Class = seq[60] of Student;
/* illustration:
Class = {
[ ], [s1], [s1, s2], …, [s1, s2, …, s60]
}
*/
where Student is supposed to have been defined
before.
Variable declarations
The form of a variable declaration:
a, b, c: Type-1; /*Which has no difference in
semantics from the variable
declaration: Type-1 a, b, c; */
or
a: Type-1;
b: Type-2;
c: Type-3;
Examples of variable declarations
(1) a: nat0; /* a = 0, a = 1, a = 2, or a = 10 … */
(2) a: nat; /* a = 1, a = 2, or a = 10, … */
(3) a: int; /*a = -1, a = 0, or a = 1, … */
(4) a: string; /*a = “Hosei”, a = “University, … */
(5) a: WeekDays; /*a = MONDAY, a =
TUESDAY, … */
(6) a: Item; /*field select: a.f, where f is a field of a.
for example, a.name, a.price, a.shop, a.date */
(7) a: Item-List; /*a = [b1, b2, …, bn], … where
b1, b2, …, bn are variables of
composite type Item.
Simple operations: application: a(i), where i is
the index of sequence a.
for example, a(1) = b1, a(2) = b2, a(n) = ?
length: len(a),
for example, len(a) = n. */
6.2 Determining how the variables are
used
（変数の使い方が決まる）
When we declare variables with types, we must try
to understand how they will be potentially used in
the program.
Two aspects are important:（二つのポイントが重要
である）
Global and local variables?
Representation of internal or external data?
6.2.1 Global and local variables
Description 1: a global variable in a module (e.g., a
single Java class) is a variable that can be
accessed directly by different operations (e.g.,
methods in a single Java class).
Description 2: a local variable is a variable that can
only be accessed by a single operation; and after
the termination of an execution of the operation
this variable will no longer exist (e.g., variables
declared inside a method of a Java class).
An abstract example
module A
a: int;
b: int;
c: string;
end-module;
operation P1(x: int)
tem: int;
begin
tem := a;
a := x + b;
b := a;
…
end-op;
operation P2(y: string)
begin
if c = y
then
b := a * b;
else
b := a + b
end-op;
A specific example in Java
//Scope.java
import java.awt.Graphics;
import java.applet.Applet;
public class Scope extends Applet {
int x = 1; //instance variable, global variable
public void paint(Graphics g)
{
int x = 5; //local variable, with the same name as the global variable.
System.out.println(“the initial value of x in paint” + x);
a();
b();
System.out.println(“the final value of x in paint” + x); //the same as the initial x.
}
void a() {
int y = 0;
//local variable
y = x;
//the initial value of x is held in y, x is used as a global variable
++x;
x = x * x;
System.out.println(“the initial value of x in a” + y);
System.out.println(“the final value of x in a” + x);
}
void b() {
System.out.println(“the initial value of global variable x in b” + x);
x *= 10; //x is used as a global variable
System.out.println(“the final value of x in b” + x);
}
}
6.2.2 Variables representing internal
and external data
(内部変数と外部変数）
Usually, files are used to hold external data and all other data structures
are used to hold internal data, such as array, vector, and linked list.
External data are the data independent of the program system. This kind
of data is expected to be kept for future use, either by the same
program or by other programs. For example, files are usually used to
hold such kinds of data.
Internal data means the data that exist only during executions of the
program system. This kind of data is usually used by the program
before its termination, and will disappear after the termination of the
program.
How to distinguish variables
representing external data and internal
data
（内部変数と外部変数の区別）
Definition A variable representing external data is
called external variable, and a variable representing
internal data is called internal variable.
A way to distinguish external and internal variables is
to mark external variables with a special symbol #.
Specifically speaking, suppose f1 is expected to hold
external data, its declaration takes the form:
#f1: Type-1
where Type-1 is usually a sequence type.
Example:
#item-list: Item-List
where Item-List is defined as:
Item-List = seq of Item
© Copyright 2024 ExpyDoc
