Chapter 4 Implementing
ADTs
in
the Base Language
• 4.1 The Aggregate Type struct
• 4.2 Structure Pointer Operator
• 4.3 AnExamp1e: Stack
• 4.4 Unions
• 4.5 Complex Numbers
• 4.6 Example: A Flush
• 4.7 Bit Fields
• 4.8 An Example: Two-Dimensional Dynamic Arrays
• 4.9 Pragmatics
• Summary
• Exercises
Chapter 4 Implementing
ADTs
in
the Base Language
• This chapter introduces the reader to struct
s t r u c t
as used in the kernel language.
• A large part of the OOP design process
involves thinking up the appropriate ADTs
for a problem. Good ADTs not only model
key features of the problem, but also are
frequently reusable in other code.
4.1 The Aggregate Type struct
• The structure type allows the programmer
to aggregate components into a single
named variable. A structure has
components, called members,
m e m be r s ,
that are
individually named.
• Demo on page 108: poker1.cpp
– In C++, the structure name, or tag name,
t a g n a m e ,
is a
type.
4.1 The Aggregate Type struct
– The declaration struct card can be thought of as
a blueprint; it creates the type card, but no
actual instances are allocated.
card c l , c2;
c ar d c l , c 2;
– Access members
A c e s m e m b e r s
structure-variable
s t r u c t u r e - v a r i a b l e
. member-name
m e m b e r - n a m e
4.1 The Aggregate Type struct
– a unique structure variable identifier, there is no
confusion between two members that have the
same name in different structures.
4.1 The Aggregate Type struct
– In general, a structure is declared with the
keyword s t r u c t followed by an identifier (tag
name), followed by a brace-enclosed list of
member declarations. The tag name is optional
but should be expressive of the ADT concept
being modeled. When the tag name is not
present, the structure declaration is anonymous
a n o n y m o u s
and can be used only to declare variables of that
type immediately, as in:
4.2 Structure Pointer Operator
• We have already seen the use of the member
operator . in accessing members.
• In this section we introduce the structure pointer
operator ->.
• C++ provides the structure pointer operator -> to
access the members of a structure via a pointer.
pointer-to-structure
p o i n t e r - t o - s t r u c t u r e
-> member-name
m e m b e r - n a m e
(
(
*
*
pointer-to-structure)
p o i n t e r - t o - s t r u c t u r e )
. member- name
m e m b e r - n a m e
4.2 Structure Pointer Operator
• Example code
4.3 AnExamp1e: Stack
• The stack
s t ac k
is one of the most useful standard
data structures.
• A
data structure whose chief purpose is to
hold information is called a container.
c on t ai n e r .
• A
A
stack allows as operations push, pop, top,
empty, and full.
• The stack is a typical ADT.
4.3 AnExamp1e: Stack
• Demo on page 111: ch_statc1.h
• Demo on page 114: ch_stac1.cpp
– decleration
– initialization
– opration definition
4.4 Unions
• A union is a derived type whose syntax is
the same as for structures, except that the
keyword union replaces struct. The member
declarations share storage, and their values
will be overlaid.
• Demo on page 115: union.cpp
4.4 Unions
• A
union can be anonymous, as in the
following code.
• Demo on page 115: weekend.cpp
– This allows the individual member identifiers to
be used as variables.
– Note that an anonymous union declared in file
scope must be static .
4.4 Unions
• Let us develop a stack as a union of
different types.
4.4 Unions
4.5 Complex Numbers
• Many scientific computations require
complex numbers. Let us write an ADT for
complex numbers.
• Demo on page 117: complex1.cpp
– Notice how the default argument is a
convenient way to assign a double to a
complex.
– The following code adds a real number and a
complex number.
– can’t use conventional expression notation
4.5 Complex Numbers
4.6 Example: A Flush
• We want to estimate the probability of
being dealt a flush. A flush occurs when at
least five cards are of the same suit. We
simulate shuffling cards by using a random
number generator to shuffle the deck.
• Demo on page 119: poker1.cpp
– structure deceleration and definition
– operation deceleration and definition
4.6 Example: A Flush
4.6 Example: A Flush
4.6 Example: A Flush
4.6 Example: A Flush
4.6 Example: A Flush
• Demo on page 121-124: poker1.cpp
4.7 Bit Fields
• A member that is an integral type can
consist of a specified number of bits. Such a
member is called a bit field
bi t f i e l d
, and the number
of associated bits is called its width
w i dt h
.
4.7 Bit Fields
• The compiler will attempt to pack the bit
fields sequentially within memory.
• It is at liberty to skip to a next byte or word
for purposes of alignment.
• Arrays of bit fields are not allowed
n ot al l ow e d
.
• Also, the address operator &
&
cannot
c an n ot
be
applied to bit fields.
• Demo on page 125: set.cpp
4.7 Bit Fields
• We can overlay word and unsigned within a
union to create a data structure for
manipulating bits:
4.8 An Example: Two-Dimensional
Dynamic Arrays
• The kernel language does not allow general
dynamic
dy n am i c
multidimensional arrays
.
• Scientists, engineers, and others make
heavy use of general two-dimensional
arrays called matrices
m at r i c e s
.
• Demo on page 126: array_2d.cpp
4.8 An Example: Two-Dimensional
Dynamic Arrays
• The pointer base
bas e
is a pointer to a pointer to
double.
• The base pointer contains the starting
address of an array of pointers, and each
pointer is a starting address of a row of
doubles.
4.8 An Example: Two-Dimensional
Dynamic Arrays
4.8 An Example: Two-Dimensional
Dynamic Arrays
• Notice in the following code how
a11ocate() uses new to allocate,
4.8 An Example: Two-Dimensional
Dynamic Arrays
• Demo on page 129: array_2d.cpp
4.9 Pragmatics
• The use of s t r u c t in the kernel language
is in many ways superseded by creating
ADTs using the class construct with private
access for hiding implementation and
member functions for implementing ADT
behavior.
• The material here is transitional and allows
the programmer to understand more
primitive encapsulation techniques that are
still in widespread use.
Summary
• 1. A structure is a declaration using the
keyword struct.
• 2. The structure type allows the programmer
to aggregate components into a single
named variable.
• 3.
A union is a derived type whose syntax is
the same as for structures, except that the
keyword union replaces struct.
• 4. A member that is an integral type can
consist of a specified number of bits.
Summary
• 5. The operator new can be used to create
run-time determined two-dimensional (and
higher) arrays. Functions using new can
work regardless of the row and column size.
ADTs
in
the Base Language
• 4.1 The Aggregate Type struct
• 4.2 Structure Pointer Operator
• 4.3 AnExamp1e: Stack
• 4.4 Unions
• 4.5 Complex Numbers
• 4.6 Example: A Flush
• 4.7 Bit Fields
• 4.8 An Example: Two-Dimensional Dynamic Arrays
• 4.9 Pragmatics
• Summary
• Exercises
Chapter 4 Implementing
ADTs
in
the Base Language
• This chapter introduces the reader to struct
s t r u c t
as used in the kernel language.
• A large part of the OOP design process
involves thinking up the appropriate ADTs
for a problem. Good ADTs not only model
key features of the problem, but also are
frequently reusable in other code.
4.1 The Aggregate Type struct
• The structure type allows the programmer
to aggregate components into a single
named variable. A structure has
components, called members,
m e m be r s ,
that are
individually named.
• Demo on page 108: poker1.cpp
– In C++, the structure name, or tag name,
t a g n a m e ,
is a
type.
4.1 The Aggregate Type struct
– The declaration struct card can be thought of as
a blueprint; it creates the type card, but no
actual instances are allocated.
card c l , c2;
c ar d c l , c 2;
– Access members
A c e s m e m b e r s
structure-variable
s t r u c t u r e - v a r i a b l e
. member-name
m e m b e r - n a m e
4.1 The Aggregate Type struct
– a unique structure variable identifier, there is no
confusion between two members that have the
same name in different structures.
4.1 The Aggregate Type struct
– In general, a structure is declared with the
keyword s t r u c t followed by an identifier (tag
name), followed by a brace-enclosed list of
member declarations. The tag name is optional
but should be expressive of the ADT concept
being modeled. When the tag name is not
present, the structure declaration is anonymous
a n o n y m o u s
and can be used only to declare variables of that
type immediately, as in:
4.2 Structure Pointer Operator
• We have already seen the use of the member
operator . in accessing members.
• In this section we introduce the structure pointer
operator ->.
• C++ provides the structure pointer operator -> to
access the members of a structure via a pointer.
pointer-to-structure
p o i n t e r - t o - s t r u c t u r e
-> member-name
m e m b e r - n a m e
(
(
*
*
pointer-to-structure)
p o i n t e r - t o - s t r u c t u r e )
. member- name
m e m b e r - n a m e
4.2 Structure Pointer Operator
• Example code
4.3 AnExamp1e: Stack
• The stack
s t ac k
is one of the most useful standard
data structures.
• A
data structure whose chief purpose is to
hold information is called a container.
c on t ai n e r .
• A
A
stack allows as operations push, pop, top,
empty, and full.
• The stack is a typical ADT.
4.3 AnExamp1e: Stack
• Demo on page 111: ch_statc1.h
• Demo on page 114: ch_stac1.cpp
– decleration
– initialization
– opration definition
4.4 Unions
• A union is a derived type whose syntax is
the same as for structures, except that the
keyword union replaces struct. The member
declarations share storage, and their values
will be overlaid.
• Demo on page 115: union.cpp
4.4 Unions
• A
union can be anonymous, as in the
following code.
• Demo on page 115: weekend.cpp
– This allows the individual member identifiers to
be used as variables.
– Note that an anonymous union declared in file
scope must be static .
4.4 Unions
• Let us develop a stack as a union of
different types.
4.4 Unions
4.5 Complex Numbers
• Many scientific computations require
complex numbers. Let us write an ADT for
complex numbers.
• Demo on page 117: complex1.cpp
– Notice how the default argument is a
convenient way to assign a double to a
complex.
– The following code adds a real number and a
complex number.
– can’t use conventional expression notation
4.5 Complex Numbers
4.6 Example: A Flush
• We want to estimate the probability of
being dealt a flush. A flush occurs when at
least five cards are of the same suit. We
simulate shuffling cards by using a random
number generator to shuffle the deck.
• Demo on page 119: poker1.cpp
– structure deceleration and definition
– operation deceleration and definition
4.6 Example: A Flush
4.6 Example: A Flush
4.6 Example: A Flush
4.6 Example: A Flush
4.6 Example: A Flush
• Demo on page 121-124: poker1.cpp
4.7 Bit Fields
• A member that is an integral type can
consist of a specified number of bits. Such a
member is called a bit field
bi t f i e l d
, and the number
of associated bits is called its width
w i dt h
.
4.7 Bit Fields
• The compiler will attempt to pack the bit
fields sequentially within memory.
• It is at liberty to skip to a next byte or word
for purposes of alignment.
• Arrays of bit fields are not allowed
n ot al l ow e d
.
• Also, the address operator &
&
cannot
c an n ot
be
applied to bit fields.
• Demo on page 125: set.cpp
4.7 Bit Fields
• We can overlay word and unsigned within a
union to create a data structure for
manipulating bits:
4.8 An Example: Two-Dimensional
Dynamic Arrays
• The kernel language does not allow general
dynamic
dy n am i c
multidimensional arrays
.
• Scientists, engineers, and others make
heavy use of general two-dimensional
arrays called matrices
m at r i c e s
.
• Demo on page 126: array_2d.cpp
4.8 An Example: Two-Dimensional
Dynamic Arrays
• The pointer base
bas e
is a pointer to a pointer to
double.
• The base pointer contains the starting
address of an array of pointers, and each
pointer is a starting address of a row of
doubles.
4.8 An Example: Two-Dimensional
Dynamic Arrays
4.8 An Example: Two-Dimensional
Dynamic Arrays
• Notice in the following code how
a11ocate() uses new to allocate,
4.8 An Example: Two-Dimensional
Dynamic Arrays
• Demo on page 129: array_2d.cpp
4.9 Pragmatics
• The use of s t r u c t in the kernel language
is in many ways superseded by creating
ADTs using the class construct with private
access for hiding implementation and
member functions for implementing ADT
behavior.
• The material here is transitional and allows
the programmer to understand more
primitive encapsulation techniques that are
still in widespread use.
Summary
• 1. A structure is a declaration using the
keyword struct.
• 2. The structure type allows the programmer
to aggregate components into a single
named variable.
• 3.
A union is a derived type whose syntax is
the same as for structures, except that the
keyword union replaces struct.
• 4. A member that is an integral type can
consist of a specified number of bits.
Summary
• 5. The operator new can be used to create
run-time determined two-dimensional (and
higher) arrays. Functions using new can
work regardless of the row and column size.