Transcript Document

Chapter 6
Lists Plus
Goals
• Use the C++ template mechanism fr
defining generic data types
• Implement a circular linked list
• Implement a linked list with a header node
or a trailer node or both
• Implement a doubly linked list
• Distinguish between shallow copying and
deep copying
2
Goals
• Overload C++ operators
• Implement a linked list as an array of
records
• Implement dynamic binding with virtual
functions
3
C++ Templates
Generic Data Type
A data type for which the operations are
defined but the types of the items being
manipulated are not
Template
A C++ construct that allows the computer to
generate multiple versions of a class type or a
function by allowing parameterized types
4
Templates implement generic types
C++ Templates
template <class
ItemType>
class StackType
{ ... }
// client code
StackType<int>;
StackType<float>;
StackType<NameType>;
5
Formal parameter
Actual parameters
C++ Templates
Summary
• The formal parameters are in the class
template definition
• The actual parameters are in the client code
• Both formal and actual parameters are
enclosed in angle brackets <...>
• The actual parameter can be any type, builtin or user-defined
6
C++ Templates
What about function templates?
Formal parameter precedes function definition
and follows class name before scope resolution
operator
7
C++ Templates
template<class ItemType>
Formal parameters
void StackType<ItemType>::Push(ItemType
newItem)
{
if (IsFull()) throw FullStack();
else
{
top++;
items[top] = newItem;
}
}
8
Circular Linked Lists
Circular linked list
A list in which each node has a successor;
the “last” element is succeeded by the
“first” element
9
Circular Linked List
Why is it
better
to have
the
external
pointer
point
to the
last
element
?
10
Circular Linked List
Initialization for search
11
Circular Linked List
FindItem
cases
12
Circular Linked List
Insert
an
item
13
Circular Linked List
Delete
an
Item
14
Doubly Linked List
Doubly linked list
A is in which each node is linked to both its
successor and its predecessor
15
Doubly Linked List
Insert
an
item
16
Doubly Linked List
Does
it
matter
in
which
order
we
change
the
pointers
?
17
Doubly Linked List
Delete an item
18
Header and Trailer Nodes
Header Node
A placeholder node at the beginning of a list that
contains a key value smaller than any possible key
Trailer Node
A placeholder node at the end of a list that contains a
key larger than any possible key
19
How do
header/trailer
nodes
simplify
processing
?
Copy Structures
void CopyStack(StackType
oldStack),
20
StackType& copy)
{
StackType tempStack;
ItemType item;
while (!oldStack.IsEmpty())
{
item = oldStack.Top();
oldStack.Pop();
temptStack.Push(item);
}
while (!tempStack.IsEmpty())
{
item = tempStack.Top();
copy.Pop();
}
}
What is
the status
of
oldStack?
copy?
Does the
implementation
structure
matter?
Copy Structures
oldStack is a value parameter; doesn’t that
protect it from change?
Yes, but only in the array-based implementation
private:
int top;
ItemType items[MAX_ITEMS];
top and items are enclosed within the stack
object
21
Copy Structures
In a linked structure, the external pointer is
enclosed within the stack object, but the
linked structure to which it points is not
What
causes
this
problem
?
22
Copy Structures
Shallow copy
An operation that copies one class object to
another without copying pointed-to data
Deep copy
An operation that not only copies one class
object to another but also makes copies of
any pointed-to data
See the difference?
23
Copy Structures
24
Copy Structures
In summary
 A shallow copy shares the pointed to data
with the original class object
 A deep copy stores its own copy of the
pointed to data at different locations than the
data in the original class object
How do we make a deep copy?
25
Copy Structures
MyStack
Private data:
7000
6000
topPtr 7000
20
30
Yes, but how?
26
SomeStack
Private data:
5000
2000
topPtr 5000
20
30
deep copy
Copy Structures
Deep Copy
if anotherStack.topPtr is NULL
Set topPtr to NULL
else
Set topPtr to the address of a newly allocated node
Set Info(topPtr) to Info(anotherStack.topPtr)
Set ptr1 to Next(anotherStack.topPtr)
Set ptr2 to topPtr
while ptr1 is not NULL
Set Next(ptr2) to the address of a newly allocated node
Set ptr2 to next(ptr2)
Set Info(ptr2) to Info(ptr1)
Set ptr1 to Next(ptr1)
Set Next(ptr2) to NULL
27
Copy Structures
Relative
position
of
pointers
at the
beginning
of each
iteration
28
Copy Structures
Copy constructor
A special member function of a class that is
implicitly invoked when passing a parameter by
value, initializing a variable in a declaration,
and returning an object as the value of function
StackType(const StackType&
anotherStack);
Of course, the code should implement a
deep copy!
29
Copy Structures
That about the assignment operator?


The assignment operator does a shallow copy!
We can overload the assignment operator
class StackType
{
public:
...
void operator=(StackType);
private:
...
void StackType::operator=(StackType
anotherStack)
// code for a deep copy
}30
Can
we
overload
other
operators
?
Copy Structrres
Al relational operators can be overloaded
31
bool operator<(ItemType other) const;
// Returns true if self is less than
other
bool operator>(ItemType other) const;
// Returns true if self is greater than
other
bool operator==(ItemType other) const;
// Returns true if self is equal to
other
Of course, you must write the code as for
...
any other function
Array-of-Records Implementation
Array in
static
storage
Array in
dynamic
storage
32
Array-of-Records Implementation
Linked list
in
static
storage
Linked list
in
dynamic
storage
33
Array-of-Records Implementation
Sorted list
34
Array-of-Records Implementation
A sorted
list
of values
and
a list of
free space
35
Array-of-Records Implementation
Two
linked
lists
plus
free
list
36
Array-of-Records Implementation
One
structure
for
each
list
37
Polymorphism
Polymorphism
The ability to determine which of several operations
with the same name to apply to a particular object; a
combination of static and dynamic binding
Binding
The time at which a name or symbol is bound to the
appropriate
static binding: bound at compile time
dynamic binding: bound at run time
38
Polymorphism
NewItemType is derived from ItemType
void PrintResult(ItemType& first, ItemType&
second);
How can this be?
39
Polymorphism
C++ relaxes scope rules to allow dynamic
binding
The type of the actual parameter may be an
object of a derived class of the formal parameter
virtual void PrintResult(ItemType& first,
ItemType& second);
Word virtual in base class (ItemType),
definition forces dynamic binding
Note: Parameters must be reference
40
Circular Doubly Linked List
What are the advantages of this structure?
41
Circular Doubly Linked List
42
C++ Tips
1. Operators :: . sizeof, and ?: may not be
overloaded
2. At least one operand must be a class instance
3. Precedence, operator symbols, or number of
operands cannot be changed
4. Overloading ++ and -- requires prefix form use by
client
5. To overload these operators = ( ) [ ], member
functions must be used
6. An operator can be given multiple meanings if the
data types of operands differ
43