程序代写代做代考 data structure PowerPoint Presentation

PowerPoint Presentation

Array-Based Implementations
Chapter 3
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Contents
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
The Approach
An Array-Based Implementation of the ADT Bag
An Array-Based Implementation of the ADT Bag

The Approach
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Review of an ADT

A collection of data and a set of operations on that data
Specifications indicate what the operations do, not how to implement
Implementing as class provides way to enforce a wall

Prevents access of data structure in any way other than by using the operations.

The Approach
FIGURE 3-1 Violating the wall of ADT operations
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Core Methods
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Methods which do basic tasks

Add
Remove
toVector (for display contents)
Constructors
Add and remove methods designed first

Using Fixed-Size Arrays
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Must store

Data item
Its number in the array
Keep track of

Max size of the array
Number of items currently stored
Where items were removed from array

Array-Based Implementation
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Private data, see header file, Listing 3-1

FIGURE 3-2 An array-based
implementation of the ADT bag
.htm code listing files must be in the same folder as the .ppt files for these links to work

Defining the Core Methods
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Core methods defined

ArrayBag::ArrayBag(): itemCount(0), maxItems(DEFAULT_CAPACITY)add
bool ArrayBag::add( const ItemType& newEntry)
vector ArrayBag:: toVector() const
int ArrayBag::getCurrentSize() const
bool ArrayBag::isEmpty() const

Defining the Core Methods
FIGURE 3-3 Inserting a new entry into an array-based bag

View test program, Listing 3-2 and
Output

Implementing More Methods
int ArrayBag:: getFrequencyOf
( const ItemType& anEntry) const
bool ArrayBag::contains( const ItemType& target) const

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
FIGURE 3-4 The array items after a successful search for the string “Alice”

Implementing More Methods
FIGURE 3-5 (a) A gap in the array items after deleting the entry in items[index] and decrementing itemCount;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Implementing More Methods
FIGURE 3-5 (b) shifting subsequent entries to avoid a gap;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Implementing More Methods
FIGURE 3-5 (c) the array after shifting;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Implementing More Methods
int ArrayBag::getIndexOf
(const ItemType& target) const
bool ArrayBag::remove( const ItemType& anEntry)
void ArrayBag::clear()

Implementing More Methods
FIGURE 3-6 Avoiding a gap in the array
while removing an entry
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Using Recursion in the Implementation
Recursive version of getIndexOf

Using Recursion in the Implementation
Recursive version of getFrequencyOf

Related Posts