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

PowerPoint Presentation

Link Based Implementations
Chapter 4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

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
Preliminaries
A Link-Based Implementation of the ADT Bag
Using Recursion in Link-Based Implementations
Testing Multiple ADT Implementations
Comparing Array-Based and Link-Based Implementations

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Preliminaries
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Components that can be linked

FIGURE 4-1 A node

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Preliminaries
FIGURE 4-2 Several nodes linked together
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Preliminaries
FIGURE 4-3 A head pointer to the first
of several linked nodes
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Preliminaries
FIGURE 4-4 A lost node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

The Class Node
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
View Node header file, Listing 4-1
Note implementation of class Node,
Listing 4-2

.htm code listing files must be in the same folder as the .ppt files for these links to work

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Link-Based Implementation of ADT Bag
View header file, Listing 4-3

Note methods to be implemented

FIGURE 4-5 A link-based implementation
of the ADT bag
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Link-Based Implementation of ADT Bag

FIGURE 4-6 Inserting at the beginning of a linked chain
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

FIGURE 4-7 The effect of the assignment
curPtr = curPtr->getNext()
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Link-Based Implementation of ADT Bag

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

FIGURE 4-8 (a) A linked chain and its shallow copy;
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013
Link-Based Implementation of ADT Bag

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Testing Multiple ADT Implementations
Note program which tests core methods,
Listing 4-4

FIGURE 4-8 (b) a linked chain and its deep copy
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Testing Multiple ADT Implementations
Sample output 1 of test program
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Testing Multiple ADT Implementations
Sample output 2 of test program
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Comparing Array-Based
and Link-Based Implementations
Arrays easy to use, but have fixed size
Increasing size of dynamically allocated array can waste storage, time
Array based implementation good for small bag
Linked chains do not have fixed size

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Comparing Array-Based
and Link-Based Implementations
Item after an array item is implied

Item in a chain of linked nodes points explicitly to next item
Array based implementation requires less memory
Array items accessed directly, equal access time

Must traverse linked chain for ith item – access time varies
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

End
Chapter 4
Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013

Data Structures and Problem Solving with C++: Walls and Mirrors, Carrano and Henry, © 2013