Contents

Page
1. Data Structures
1.1 What is the data structure?  2
1.2 Basic data structure  3
1.2.1 Basic data type  3
1.2.2 Structured type  4
1.2.3 Abstract data type  6
1.3 Problem-oriented data structure  7
1.3.1 List structure  7
1.3.2 Stack  9
1.3.3 Queue  10
1.3.4 Tree structure  11
1.3.5 Hash  16
Exercises  18
2. Algorithms 34
Introduction  23
2.1 Basics of algorithms  23
2.1.1 What is an algorithm?  23
2.1.2 Algorithm and the data structure  24
2.2 Various algorithms  28
2.2.1 Search algorithm  28
2.2.2 Sort algorithm  32
2.2.3 Recursive algorithm  47
2.2.4 Character string processing  49
2.2.5 File processing  53
2.2.6 Drawing figures  61
2.2.7 Graph  65
2.2.8 Numeric calculation  69
2.2.9 Collation algorithm  76
2.2.10 Approximate and probability algorithms  79
2.3 Evaluation of algorithms  84
2.3.1 Evaluation by computational complexity  84
2.3.2 Evaluation by validity  85
2.3.3 Evaluation by representation  85
2.4 How to design algorithms  86
Exercises  87
3. Internal Design
Introduction  92
3.1 What is internal design?  92
3.1.1 Purpose of internal design and points to note  92
3.1.2 Internal design procedure  93
3.2 Functional partitioning and structuring  96
3.2.1 Units of functional partitioning and structuring  96
3.2.2 Procedures of functional partitioning and structuring  97
3.2.3 Structured design method  102
3.3 Physical data design  105
3.3.1 Physical data design procedure  105
3.3.2 Physical data organization  109
3.4 Detailed input-output design  112
3.4.1 Detailed input data design  112
3.4.2 Screen design  115
3.4.3 Detailed output data design  124
3.5 Creation and reuse of parts  127
3.5.1 Concept of creation and reuse of parts  127
3.5.2 Use of software packages  127
3.6 Creating internal design documents  128
3.6.1 Organization of internal design documents  128
3.6.2 Points to note when creating internal design documents  130
3.6.3 Design review  130
Exercises  132
4. Program Design
Introduction  134
4.1 Purpose and tasks of program design  134
4.1.1 Purpose of program design  134
4.1.2 Program design tasks  136
4.2 Structured design of programs  138
4.2.1 Structured design procedure  138
4.2.2 Typical module partitioning techniques  141
4.2.3 Criteria for module partitioning  149
4.2.4 Program partitioning  160
4.3 Creating module and test specifications  161
4.3.1 Creating module specifications  161
4.3.2 Creating test specifications  162
4.4 Creating program design documents  164
4.4.1 Creating program design documents and the contents  164
4.4.2 Points to note when creating program design documents  166
4.4.3 Design review  166
Exercises  167
5. Program Implementation
Introduction  170
5.1 Programming  170
5.1.1 Programming paradigm  170
5.1.2 Programming style  171
5.1.3 Use of language processors  172
5.1.4 Programming environment  172
5.2 Test  174
5.2.1 Overview of tests  174
5.2.2 Unit tests  174
5.2.3 Integration tests  175
5.2.4 System tests  179
5.2.5 Other tests  180
5.2.6 Testing plan and tasks  181
Exercises  185
Answers to Exercises  187
Answers for No.3 Chapter1 (Data Structures)  187
Answers for No.3 Chapter2 (Algorithms)  194
Answers for No.3 Chapter3 (Internal Design)  204
Answers for No.3 Chapter4 (Program Design)  208
Answers for No.3 Chapter5 (Program Implementation)  214
Index  218
FE No.3 INTERNAL DESIGN AND PROGRAMMING 208