Software Engineering using C++.pdf

(668 KB) Pobierz
Department of Computing Science
Faculty of Computing & Engineering
Software Engineering
using C++
Lecture Notes
Prepared by Terry Chapman
September 1999
Table of Contents
Table of Contents
BASIC C++ .....................................................................................................................1
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
1.
2.
3.
4.
5.
6.
7.
8.
9.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
A First C++ Program.......................................................................................................................... 1
Data Types.......................................................................................................................................... 1
String Constants.................................................................................................................................. 2
Variables and Constants ..................................................................................................................... 3
Arithmetic Operators .......................................................................................................................... 4
Type conversions................................................................................................................................ 5
Assignment operator........................................................................................................................... 5
The compound assignment operators ................................................................................................. 5
The increment & decrement operators ............................................................................................... 5
Iostream library .................................................................................................................................. 6
Command line redirection .................................................................................................................. 6
Streams ............................................................................................................................................... 6
Output manipulators ........................................................................................................................... 7
Relational operators and expressions.................................................................................................. 8
FALSE and TRUE.............................................................................................................................. 8
Logical operators and expressions...................................................................................................... 9
Short-circuit evaluation ...................................................................................................................... 9
The while statement.......................................................................................................................... 10
The if statement ................................................................................................................................ 11
Style for logical expressions............................................................................................................. 12
The
ctype
library............................................................................................................................... 12
Introduction ...................................................................................................................................... 13
Input and output in functions............................................................................................................ 15
Multi-function programs................................................................................................................... 15
Stepwise Refinement (or Top-down design) .................................................................................... 16
Automatic variables.......................................................................................................................... 17
Function values................................................................................................................................. 17
Function arguments .......................................................................................................................... 17
Function argument agreement & conversion.................................................................................... 18
Overloaded function names .............................................................................................................. 18
Reference Arguments ....................................................................................................................... 19
Function comments .......................................................................................................................... 19
Summary .......................................................................................................................................... 19
The type cast operator ...................................................................................................................... 21
The comma operator......................................................................................................................... 21
The conditional operator................................................................................................................... 21
The
for
statement.............................................................................................................................. 22
The
do
statement............................................................................................................................... 23
Nested loops ..................................................................................................................................... 23
The
break
statement ......................................................................................................................... 24
The
continue
statement..................................................................................................................... 24
The
switch
statement ........................................................................................................................ 24
Introduction ...................................................................................................................................... 27
Reference Type................................................................................................................................. 27
Pointers v References ....................................................................................................................... 28
Enumeration Types........................................................................................................................... 29
The typedef statement....................................................................................................................... 29
Reference arguments to functions .................................................................................................... 29
Pointer arguments to functions ......................................................................................................... 30
Default arguments ............................................................................................................................ 32
Inline functions................................................................................................................................. 32
Mathematical functions .................................................................................................................... 33
i
FUNCTIONS .................................................................................................................13
FLOW OF CONTROL ...................................................................................................21
POINTERS, REFERENCES AND FUNCTIONS............................................................27
Table of Contents
ARRAYS .......................................................................................................................35
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1.
2.
3.
4.
5.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
ii
Introduction.......................................................................................................................................35
Defining and referencing arrays........................................................................................................35
Array initialisation ............................................................................................................................37
Multi-dimensional arrays ..................................................................................................................38
Arrays as function arguments ...........................................................................................................38
Pointers and arrays............................................................................................................................39
Character strings and variable pointers .............................................................................................40
Character string input/output ............................................................................................................40
Arrays of pointers and pointers to pointers .......................................................................................41
Command line arguments .................................................................................................................42
Initialising pointer arrays ..................................................................................................................43
Review ..............................................................................................................................................43
Summary...........................................................................................................................................44
An array application - Stack of char .................................................................................................45
Introduction.......................................................................................................................................47
The steps to produce an executable...................................................................................................48
Types, storage class and scope..........................................................................................................48
Local duration ...................................................................................................................................49
Declaration versus definition ............................................................................................................50
Static duration ...................................................................................................................................51
Storage class static ............................................................................................................................52
Static local variables .........................................................................................................................52
Static global variables .......................................................................................................................52
The C++ pre-processor .....................................................................................................................53
Conditional compilation....................................................................................................................53
Conditional file inclusion..................................................................................................................54
Data Types ........................................................................................................................................55
Abstract Data Types..........................................................................................................................55
Classification ....................................................................................................................................55
Categories of Collection ...................................................................................................................56
Stacks................................................................................................................................................56
Abstract Data Type? .........................................................................................................................59
Queues ..............................................................................................................................................59
Lists...................................................................................................................................................61
Structs ...............................................................................................................................................61
Unions...............................................................................................................................................62
Structures ..........................................................................................................................................63
Comparison between structs and arrays ............................................................................................64
Storage Management ........................................................................................................................65
Dynamic Data Structures - Linked Lists ...........................................................................................68
Other dynamic structures ..................................................................................................................72
Introduction.......................................................................................................................................73
Components of Sorting .....................................................................................................................73
Sorting Files......................................................................................................................................73
Why sort?..........................................................................................................................................75
Does it pay to sort? ...........................................................................................................................75
What is the best sort? ........................................................................................................................75
Sorting efficiency..............................................................................................................................75
Simple Array Sort - Exchange (Bubble) ...........................................................................................76
Insertion Sort.....................................................................................................................................77
Simple Sort performance ..................................................................................................................78
Conclusions.......................................................................................................................................78
Complex sorts ...................................................................................................................................78
PROGRAM FILES ........................................................................................................47
DATA STRUCTURES ...................................................................................................55
DYNAMIC DATA STRUCTURES..................................................................................63
SORTING......................................................................................................................73
Table of Contents
13.
14.
15.
16.
17.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
1.
2.
3.
4.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
1.
2.
3.
4.
5.
6.
7.
8.
1.
2.
3.
QuickSort.......................................................................................................................................... 79
Efficiency of Quicksort .................................................................................................................... 80
C++ code for function Quicksort ( see Wirth )................................................................................. 81
Comparison of complex sorting algorithms...................................................................................... 81
Further Reading ................................................................................................................................ 81
The context for testing - Verification and Validation....................................................................... 83
The objectives of testing................................................................................................................... 83
Testing & Debugging ....................................................................................................................... 84
Two different testing strategies ........................................................................................................ 84
Categories of Testing........................................................................................................................ 86
Test Planning.................................................................................................................................... 86
How much testing? ........................................................................................................................... 87
Test Data v Test Cases ..................................................................................................................... 87
Black box v White box testing ......................................................................................................... 87
Black box testing .............................................................................................................................. 88
White box testing - Introduction....................................................................................................... 91
White box testing.............................................................................................................................. 92
Automated Testing ........................................................................................................................... 96
Representing Abstract Structure ....................................................................................................... 99
Implementing Data Structures ........................................................................................................ 100
Metrics............................................................................................................................................ 100
Mathematical Notations.................................................................................................................. 101
Applications.................................................................................................................................... 105
Implementation............................................................................................................................... 105
Variations ....................................................................................................................................... 105
Example Declaration ...................................................................................................................... 105
Expression Trees ............................................................................................................................ 106
Tree Traversal................................................................................................................................. 106
Parse Trees ..................................................................................................................................... 107
Binary Search Trees ....................................................................................................................... 107
Importance of Balance.................................................................................................................... 108
Other types of tree .......................................................................................................................... 108
Applications.................................................................................................................................... 111
Operations ...................................................................................................................................... 111
Efficiency ....................................................................................................................................... 111
Problem .......................................................................................................................................... 111
Hashing........................................................................................................................................... 111
Collision Resolution ....................................................................................................................... 112
Hash Table example ....................................................................................................................... 112
Perfect Hashing Functions.............................................................................................................. 113
The ctype library............................................................................................................................. 115
The maths library............................................................................................................................ 116
The standard library........................................................................................................................ 117
TESTING ......................................................................................................................83
DATA STRUCTURE METRICS ....................................................................................99
TREES ........................................................................................................................ 105
HASH TABLES........................................................................................................... 111
LIBRARIES................................................................................................................. 115
BIBLIOGRAPHY......................................................................................................... 119
iii
Basic C++
Basic C++
1.
A First C++ Program
// first.cpp
// My first C++ program
// A. Student
// 27/09/99
#include<iostream>
int main( void )
{
cout << “Hello World” << endl;
return 0;
}
The lines starting with // are comments. These are for human consumption - the compiler
ignores them. They cause all text on the current line to the right of the symbol to be a
comment. An alternative form of comment is the pair:-
/* this is a comment */
These do not need repeating on every line and therefore a number of lines can be enclosed
within one pair.
Since the program is going to display output, it is necessary to make available the
input/output library
iostream.
This is done by issuing a compiler directive that the text of
the file
iostream.h
should be included in the compilation. The compiler knows where to
find this file. The word
cout
represents the output stream and the symbol
<<
causes what
follows it to be placed on the standard output stream. By default, the standard output
stream is displayed on the terminal.
Every C++ program must have one, and only one function
main.
This is where program
execution always commences. This, and all other functions have a return type, in this case
int,
and an argument list, in this case empty - indicated by
void
and a body that is delimited
by open and close braces { }.
The first line of function
main
outputs the message “Hello World” to the terminal followed
by a new line. The program then terminates, returning the value 0 to the operating system.
By convention, a return value of 0 indicates success. This program deals only with two
values - a constant
string
1
literal containing the words “Hello World” and an integer
constant
0.
It does not require the use of any variables. Most programs require the use of
variables, i.e. storage locations in memory that contain values during program execution.
Variables may be of different types.
2.
Data Types
There are a number of basic data types built in to all programming languages. A data type
consists of a name and a specification of :-
!
!
the range of values that a variable of that type can hold - its
domain.
This range is
often limited due to the amount of storage that is used by such items.
the operations that may be carried out on values of that type
In C++, the most common data type is
int
- whole numbers that may be positive or
negative -
natural numbers.
The amount of storage allocated to variables of type
int
is
1
A sequence of characters
1

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin