ソフトウエア開発の流れ
•2
機能設計
構成設計
詳細設計
論理試験
耐性試験
外部仕様（プログラムの入力と出力の取り決
め）
内部データ構造や関数呼び出し方法などに関
する取り決め
ソースプログラムの記述
正しい入力データから正しい結果が得られる
かテスト
関数単位からテストをおこなう
異常な入力データに対して，異常を検出でき
るかテスト
異常終了することはないかテスト
・・・
・・・
・・・
・・・
・・・
機能設計
•外部仕様（プログラムの入力と出力の取り決め）
•3
プログラム
入力
データファイル，
外部から与える動作
など
出力
「what」を定める （「how」とは段階を分ける）
データファイル，
外部に出すメッセージ
など
機能設計の例
入力
•4
出力
下記に定める「名簿ファイル」を入力とする
1. テキストファイル形式
2. 氏名，生年月日，住所，電話番号が並び，半角の空白文字
で区切られる．
•氏名，住所，電話番号は最大で１００バイトとする．
•生年月日は，西暦年，月，日が「/」で区切られている
3. ファイル名は z:\Address.txt
・「名簿ファイル」の中身を，氏名でソートして表示
1. 氏名の順序は，c の文字列比較関数 strcmp() での順序
に従う
金子邦彦 1200/01/01 福岡市東区箱崎３丁目 392-123-8234
○○×× 1300/12/31 福岡市東区貝塚団地 492-252-7188
●●■■ 0800/05/31 福岡市東区香椎浜１丁目 592-824-7144
例
構成設計
•プログラムの内部仕様を定める
•外部仕様を実現するのに最も適した手段を定める
•5
ファイル
プログラムのメモリ空間
fgets
で読み込み 氏名をキーとする
２分探索木を構成
in-order で辿り
ながら表示
内部仕様の概要の例
#include "stdio.h"
#include <math.h>
#include <string.h>
#pragma warning(disable:4996)
struct Person {
char name[100];
int birth_year;
int birth_month;
int birth_day;
char address[100];
char phone[100];
};
struct BTNode
{BTNode *left;
BTNode *right;
Person person;
};
void print_person_data( struct BTNode *root )
{if ( root->left != NULL ) {
print_person_data( root->left );
}
printf( "%s, \t%d/%d/%d, \t%s, \t%s\n", root->person.name, root->person.birth_year, root->person.birth_month, root->person.birth_day, root->person.address, root->person.phone );
if ( root->right != NULL ) {
print_person_data( root->right );
}
}
struct BTNode *new_person_node(Person *p, struct BTNode *y, struct BTNode *z)
{struct BTNode *w = new BTNode();
strcpy_s( w->person.name, p->name);
w->person.birth_year = p->birth_year;
w->person.birth_month = p->birth_month;
w->person.birth_day = p->birth_day;
strcpy_s( w->person.address, p->address );
strcpy_s( w->person.phone, p->phone );
w->left = y;
w->right = z;
return w;
}
struct BTNode *insert_person_node(struct BTNode *node, Person *p)
{if ( node == NULL ) {
return new_person_node(p, NULL, NULL);
}
else if ( strcmp( p->name, node->person.name ) < 0 ) {
node->left = insert_person_node(node->left, p);
return node;
}
else if ( strcmp( p->name, node->person.name ) > 0) {
node->right = insert_person_node(node->right, p);
return node;
}
else {
return node;
}
}
BTNode* read_file_and_create_tree( char* file_name )
{FILE *in_file;
char line[sizeof(Person)];
Person p;
BTNode *root;
in_file = fopen(file_name, "r");
if ( in_file == NULL ) {
return 0;
}
root = NULL;
while( fgets( line, sizeof(Person), in_file ) != NULL ) {
sscanf_s( line, "%s %d/%d/%d %s %s", &(p.name), &(p.birth_year), &(p.birth_month), &(p.birth_day), &(p.address), &(p.phone) );
if ( root == NULL ) {
root = new_person_node( &p, NULL, NULL );
}
else {
insert_person_node( root, &p );
}
}
fclose(in_file);
return root;
}
int main()
{BTNode *root;
int ch;
root = read_file_and_create_tree( "z:\\Address.txt" );
print_person_data( root );
printf( "Enter キーを1,2回押してください. プログラムを終了します\n");
ch = getchar();
ch = getchar();
return 0;
}•6
print_person_data 関数
new_person_node 関数
insert_person_node 関数
read_file_and_create_tree 関数
構造体 Person の定義（説明は後述）
構造体 BTNode の定義（説明は後述）
•7
実行結果の例
構造体の例
•8
name
birth_year
birth_mont
h
birth_day
address
phone
例題１の
構造体 Person
これで
１つの
データ
char の配列（100バイト）
char の配列（100バイト）
char の配列（100バイト）
int
int
int
二分探索木の各ノードを
C言語の構造体で表現
•9
struct BTNode
{
BTNode *left;
BTNode *right;
Person person;
};
left right
person
left right
person
left right
person
１個の
構造体
「Person person」 の部分は，格納
すべきデータに応じて変わる
Person
構造体を
中に
含む
•10
BTNode* read_file_and_create_tree( char* file_name )
{FILE *in_file;
char line[sizeof(Person)];
Person p;
BTNode *root;
in_file = fopen(file_name, "r");
if ( in_file == NULL ) {
return 0;
}
root = NULL;
while( fgets( line, sizeof(Person), in_file ) != NULL ) {
sscanf_s( line, "%s %d/%d/%d %s %s", &(p.name), &(p.birth_year),
&(p.birth_month), &(p.birth_day), &(p.address), &(p.phone) );
if ( root == NULL ) {
root = new_person_node( &p, NULL, NULL );
}
else {
insert_person_node( root, &p );
}
}
fclose(in_file);
return root;
}
ファイル
プログラムのメモリ空間
fgets
で読み込み 氏名をキーとする
二分探索木を構成
ファイルオープンに失敗した
ときのみ実行される部分
ファイルオープンに失敗したら，
プログラムが終わる
挿入を行う関数
•11
struct BTNode *insert_person_node(struct BTNode *node, Person *p)
{
if ( node == NULL ) {
return new_person_node(p, NULL, NULL);
}
else if ( strcmp( p->name, node->person.name ) < 0 ) {
node->left = insert_person_node(node->left, p);
return node;
}
else if ( strcmp( p->name, node->person.name ) > 0) {
node->right = insert_person_node(node->right, p);
return node;
}
else {
return node;
}
}
p->name ・・・ 挿入データの name フィールド
node->person.name ・・・ 探索中の部分木の根
にある name フィールド
strcmp で「辞書順」での比較
通りがけ順 (in-order traversal)
•左の子節点以下を処理 （左部分木を辿る）
•親節点について処理 （根を辿る）
•右の子節点以下を処理 （右部分木を辿る）
•12
A
BC
DEF G
D, B, E, A, F, C, G
の順に処理を行う
①左部分木を辿る
②根を辿る
③右部分木を辿る
表示を行う関数（in-order での表示）
•13
void print_person_data( struct BTNode *root )
{
if ( root->left != NULL ) {
print_person_data( root->left );
}
printf( "%s, \t%d/%d/%d, \t%s, \t%s\n", root-
>person.name, root->person.birth_year, root-
>person.birth_month, root->person.birth_day, root-
>person.address, root->person.phone );
if ( root->right != NULL ) {
print_person_data( root->right );
}
}
左部分木
右部分木
根
