Transcript ppt

Object Oriented Programming
COP3330 / CGS5409



Vectors
Linked Lists
Stacks


C++ has some built-in methods of storing
compound data in useful ways, like arrays
and structs.
Collectively known as Abstract Data Types, as
they describe the nature of what is stored,
along with the expected operations for
accessing the data, without specifying the
details of implementation



C++ classes allow a nice mechanism for
implementing such data types
Provides an interface (the public section) for
the necessary operations
The actual implementation details are internal
and hidden.


Data structure that stores items of the same
type, and is based on storage in an array
By encapsulating an array into a class (a
vector class), we can
◦ Use dynamic allocation to allow the internal array to
be flexible in size
◦ Handle boundary issues of the array (error checking
for out-of-bounds indices).


Advantages: Random access - i.e. quick
locating of data if the index is known.
Disadvantages: Inserts and Deletes are
typically slow, since they may require shifting
many elements to consecutive array slots



Collections of data items linked together with
pointers, lined up "in a row".
Typically a list of data of the same type, like
an array, but storage is arranged differently.
Made up of a collection of "nodes", which are
created from a self-referential class (or
struct).




Self-referential class: a class whose member data
contains at least one pointer that points to an
object of the same class type.
Each node contains a piece of data, and a pointer
to the next node.
Nodes can be anywhere in memory (not restricted
to consecutive slots, like in an array).
Nodes generally allocated dynamically, so a
linked list can grow to any size, theoretically
(within the boundaries of the program's
memory).




An alternative to array-based storage.
Advantages: Inserts and Deletes are typically fast.
Require only creation of a new node, and changing of
a few pointers.
Disadvantage: No random access. Possible to build
indexing into a linked list class, but locating an
element requires walking through the list.
Notice that the advantages of the array (vector) are
generally the disadvantages of the linked list, and
vice versa



First In Last Out (FILO)
Insertions and removals can occur from "top"
position only
Analogy - a stack of cafeteria trays. New
trays are always placed on top. Trays also
picked up from the top.

A stack class will have two primary
operations:

push -- adds an item onto the top of the
stack

pop -- removes the top item from the stack

Typical application areas include compilers,
operating systems, handling of program
memory (nested function calls)



First In First Out (FIFO)
Insertions at the "end" of the queue, and
removals from the "front" of the queue.
Analogy - waiting in line for a ride at an
amusement park. Get in line at the end. First
come, first serve.




A queue class will have two primary operations:
enqueue -- adds an item into the queue (i.e. at
the back of the line)
dequeue -- removes an item from the queue (i.e.
from the front of the line).
Typical application areas include print job
scheduling, operating systems (process
scheduling).


Some abstract types, like Stacks and Queues,
can be implemented with a vector or with a
linked list.
A stack can use a linked list as its underlying
storage mechanism, for instance, but would
limit the access to the list to just the "push"
and "pop" concepts (insert and remove from
one end).


A non-linear collection of data items, also
linked together with pointers (like a linked
list).
Made up of self-referential nodes. In this
case, each node may contain 2 or more
pointers to other nodes.

Typical example: a binary tree

Each node contains a data element, and two
pointers, each of which points to another node.


Very useful for fast searching and sorting of data,
assuming the data is to be kept in some kind of
order.
Binary search - finds a path through the tree,
starting at the "root", and each chosen path (left
or right node) eliminates half of the stored
values.



Creates a template doubly linked list of List()
type, composed of Listnode() type nodes.
Listnode.h -- Template ListNode class
definition.
List.h -- Template List class definition.
#ifndef LISTNODE_H
#define LISTNODE_H
template< typename T > class List;
template< typename T >
class ListNode
{
friend class List< T >; // make List a friend
public:
ListNode( const T & ); // constructor
T getData() const; // return data in node
private:
T data; // data
ListNode< T > *nextPtr; // next node in list
};
// constructor
template< typename T >
ListNode< T >::ListNode( const T &info ): data( info ),
nextPtr( 0 )
{ } // end ListNode constructor
// return copy of data in node
template< typename T >
T ListNode< T >::getData() const
{
return data;
} // end function getData
#endif
#ifndef LIST_H
#define LIST_H
#include <iostream>
#include "Listnode.h" // ListNode class definition
template< typename T >
class List
{
public:
List(); // constructor
~List(); // destructor
void insertAtFront( const T & );
void insertAtBack( const T & );
bool removeFromFront( T & );
bool removeFromBack( T & );
bool isEmpty() const;
void print() const;
private:
ListNode< T > *firstPtr; // pointer to first node
ListNode< T > *lastPtr; // pointer to last node
ListNode< T > *getNewNode( const T & );
};
// default constructor
template< typename T >
List< T >::List() : firstPtr( 0 ), lastPtr( 0 )
{ } // end List constructor
// destructor
template< typename T >
List< T >::~List()
{
if ( !isEmpty() ) // List is not empty
{
cout << "Destroying nodes ...\n";
ListNode< T > *currentPtr = firstPtr;
ListNode< T > *tempPtr;
while ( currentPtr != 0 ) // delete remaining nodes
{
tempPtr = currentPtr;
cout << tempPtr->data << '\n';
currentPtr = currentPtr->nextPtr;
delete tempPtr;
} // end while
} // end if
cout << "All nodes destroyed\n\n";
} // end List destructor
/ insert node at front of list
template< typename T >
void List< T >::insertAtFront( const T &value )
{
ListNode< T > *newPtr = getNewNode( value ); // new node
if ( isEmpty() ) // List is empty
firstPtr = lastPtr = newPtr; // new list has only one node
else // List is not empty
{
newPtr->nextPtr = firstPtr; // point new node to previous 1st node
firstPtr = newPtr; // aim firstPtr at new node
} // end else
} // end function insertAtFront
// insert node at back of list
template< typename T >
void List< T >::insertAtBack( const T &value )
{
ListNode< T > *newPtr = getNewNode( value ); // new node
if ( isEmpty() ) // List is empty
firstPtr = lastPtr = newPtr; // new list has only one node
else // List is not empty
{
lastPtr->nextPtr = newPtr; // update previous last node
lastPtr = newPtr; // new last node
} // end else
} // end function insertAtBack
// delete node from front of list
template< typename T >
bool List< T >::removeFromFront( T &value )
{
if ( isEmpty() ) // List is empty
return false; // delete unsuccessful
else
{
ListNode< T > *tempPtr = firstPtr; // hold tempPtr to delete
if ( firstPtr == lastPtr )
firstPtr = lastPtr = 0; // no nodes remain after removal
else
firstPtr = firstPtr->nextPtr; // point to previous 2nd node
value = tempPtr->data; // return data being removed
delete tempPtr; // reclaim previous front node
return true; // delete successful
} // end else
} // end function removeFromFront
// delete node from back of list
template< typename T >
bool List< T >::removeFromBack( T &value ) {
if ( isEmpty() ) // List is empty
return false; // delete unsuccessful
else {
ListNode< T > *tempPtr = lastPtr; // hold tempPtr to delete
if ( firstPtr == lastPtr ) // List has one element
firstPtr = lastPtr = 0; // no nodes remain after removal
else
{
ListNode< T > *currentPtr = firstPtr;
while ( currentPtr->nextPtr != lastPtr ) // locate second-to-last element
currentPtr = currentPtr->nextPtr; // move to next node
lastPtr = currentPtr; // remove last node
currentPtr->nextPtr = 0; // this is now the last node
} // end else
value = tempPtr->data; // return value from old last node
delete tempPtr; // reclaim former last node
return true; // delete successful
} // end else
} // end function removeFromBack
// is List empty?
template< typename T >
bool List< T >::isEmpty() const
{
return firstPtr == 0;
} // end function isEmpty
// return pointer to newly allocated node
template< typename T >
ListNode< T > *List< T >::getNewNode(
const T &value )
{
return new ListNode< T >( value );
} // end function getNewNode
// display contents of List
template< typename T >
void List< T >::print() const {
if ( isEmpty() ) { // List is empty
cout << "The list is empty\n\n";
return;
} // end if
ListNode< T > *currentPtr = firstPtr;
cout << "The list is: ";
while ( currentPtr != 0 ) { // get element dat
cout << currentPtr->data << ' ';
currentPtr = currentPtr->nextPtr;
} // end while
cout << "\n\n";
} // end function print
#endif