Transcript PPT - The School of Electrical Engineering and Computer Science

Cpt S 122 – Data Structures
Course Review
FINAL
Nirmalya Roy
School of Electrical Engineering and Computer Science
Washington State University
Final


When: Wednesday (12/12) 1:00 pm -3:00 pm
Where: In Class

Closed book, Closed notes
Comprehensive

Material for preparation:




Lecture Slides
Quizzes, Labs and Programming assignments
Deitel & Deitel book (Read and re-read Chapter 15 to 22
and Chapter 24 and the last 5 weeks lecture notes from
course webpage)
Course Overview (First 5 weeks)

Functions (Chapter 5)



Pointers (Chapter 7)




Function Call Stack and Stack Frames
Pass-by-value and Pass-by-reference
Pointer Operators
Passing Arguments to Functions by Reference
const qualifiers with Pointers
Characters and Strings (Chapter 8)

Fundamentals of Strings and Characters
Course Overview

Data Structures (Chapter 12)



Self Referential Structures
Dynamic Memory Allocation
Linked Lists, Stacks and Queues



insert, delete, isEmpty, print
Binary Trees, Binary Search Trees
Tree Traversals

preOrder, inOrder, postOrder
Course Overview (Second 5 weeks)

C++ as a better C; Introducing Object Technology
(Chapter 15)




Introduction to Classes, Objects & Strings (Chapter 16)



Inline Function
Function Overloading and Function Templates
Pass-by-value and Pass-by-reference
Data members, Members functions, set and get functions
Constructors
Classes: A Deeper Look, Part I (Chapter 17)


Separating interface from implementation
Destructors
Course Overview

Classes: A Deeper Look, Part 2 (Chapter 18)





const Objects and const Member functions
Composition: Objects as members of class
friend function and friend class
this pointer
Operator Overloading; Class String (Chapter 19)



Implementation of operator overloading
Dynamic memory management using new operator
Explicit constructor
Course Overview

Object Oriented Programming: Inheritance (Chapter 20)



Base Classes & Derived Classes
public, protected, and private Inheritance
Object Oriented Programming: Polymorphism (Chap. 21)



Abstract Classes & pure virtual Functions
virtual Functions & Dynamic Binding
Polymorphism & RunTime Type Information (RTTI)


downcasting, dynamic_cast
virtual Destructors
Course Overview

Templates (Chapter 22)




Function Template
Class Templates
STL Containers: example of container class template such
as stack
Exception Handling (Chapter 24)



Use of try, catch and throw to
detect, handle and indicate exceptions, respectively.
Exception handling with constructors & destructors
Processing new failures
Course Overview (Last 5 weeks)

Templatized Linked List


Templatized Stack


push, pop, top, isStackEmpty, printStack
Templatized Queue


insert, delete, isEmpty, printList
enqueue, dequeue, isQueueEmpty, printQueue
Templatized Tree

insertNode, preOrder, inOrder, postOrder
Course Overview (Last 5 weeks)

Sorting algorithms and Runtime analysis



Standard Template Library


Bubble sort, Selection sort, Insertion sort, Shell sort, Merge
sort, Quick sort
Enumeration of sorting algorithms in practice
Containers, Iterators, Algorithms
Abstract Data Types


vector, list, stack, queue
Runtime complexity
Function Overloading

C++ enables several functions of the same name to be
defined, as long as they have different signatures.


The C++ compiler selects the proper function to call


examining the number, types and order of the arguments in the
call.
Overloaded functions are distinguished by their signatures.


This is called function overloading.
A signature is a combination of a function’s name and its
parameter types (in order).
Function overloading is used to create several functions of
the same name

perform similar tasks, but on different data types.
Function Templates


Overloaded functions normally perform similar or identical
operations on different types of data.
If the operations are identical for each type, they can be
expressed more compactly and conveniently using function
templates.
Inheritance



With object-oriented programming, we focus on the
commonalities among objects in the system rather
than on the special cases.
We distinguish between the is-a relationship and the
has-a relationship.
The is-a relationship represents inheritance.

In an is-a relationship,


an object of a derived class can be treated as an object of its
base class.
By contrast, the has-a relationship represents
composition.
Dynamic Memory Management



Use the new operator to dynamically allocate (i.e.,
reserve) the exact amount of memory required to hold
an object or array at execution time.
Once memory is allocated in the free store, you can
access it via the pointer that operator new returns.
To destroy a dynamically allocated object, use the
delete operator as follows:


delete ptr;
To deallocate a dynamically allocated array, use the
statement

delete [] ptr;
Polymorphism
Polymorphism
late binding, or
dynamic binding,
virtual function
early binding, or static
binding, or static linking
Compile time
Polymorphism
Function
Overloading
Operator
Overloading
Runtime
Polymorphism
Virtual
Functions
Abstract Classes and pure virtual Functions

A class is made abstract by declaring one or more of its virtual
functions to be “pure.”
 A pure virtual function is specified by placing “= 0” in its
declaration, as in
virtual void draw() const = 0;

Abstract classes are classes from which you never intend to
instantiate any objects.

Classes that can be used to instantiate objects are called concrete
classes.
Exception Handling

What is exception handling?




Exception Specifications


Example: Handling an attempt to divide by zero
Use try, catch and throw to detect, handle and indicate
exceptions, respectively.
Rethrowing an exception
Processing unexpected and uncaught exceptions
Processing new failures


Dynamic memory allocation
Use unique_ptr to prevent memory leak
Exception Handling (cont.)


try blocks enable exception handling.
 The try block encloses statements that might cause
exceptions and statements that should be skipped if an
exception occurs.
Exceptions are processed by catch handlers (also called
exception handlers), which catch and handle exceptions.
 At least one catch handler must immediately follow each try
block.
Last 5 Weeks





Templated Classes
Sorting and Algorithm Analysis
Standard Template Library (STL)
Abstract Data Type
Runtime Complexity
ListNode Template Class
List Class Template
List Class Constructor
List Class Destructor
insertAtFront() & Runtime
insertAtBack() & Runtime
removeFromFront() & Runtime
removeFromBack() & Runtime
isEmpty() & Runtime
Templated Linked List Problem

Please write a insertNode() method for the class List.
This method should insert data in the list in order.



First create a new node with the provided value.
Make sure to check if the list is empty and if so set the pointers
appropriately to insert the new node into the empty list.
Otherwise traverse the list by advancing a current pointer,
compare the new Node’s value with the existing ListNode’s
data to find the correct position and then set the pointers
appropriately to insert the new node considering the following
3 cases



insertAtFront
insertInBetween
insertAtBack
Templated Stack

Option 1: Implement a stack class primarily by reusing a
list class.


private inheritance of the list class.
Option 2: Implement an identically performing stack
class through composition

a list object as a private member of a stack class.
List Class is Given
Templated Stack derived from class List
runtime of push, pop, isStackEmpty,
printStack??
Templated Stack (cont.)
Queue Class Template
runtime of enqueue, dequeue,
isQueueEmpty, printQueue??
Queue Class Template
Trees


Linked lists, stacks and queues are linear data structures.
A tree is a nonlinear, two-dimensional data structure.


arrays arrange data linearly, binary trees can be envisioned as
storing data in two dimensions
Tree nodes contain two or more links.

trees whose nodes all contain two links (none, one or both of
which may be null).
TreeNode Class Template
ListNode Member Function
TreeNode Class Template (cont.)
Tree Class Template (cont.)
Tree Class Template (cont.)
Tree Class Template (cont.)
Tree Class Template preorder Traversal

preOrder traversal is: root, left, right
Tree Class Template inOrder Traversal

inOrder traversal is: left, root, right
Tree Class Template postOrder Traversal

postOrder traversal is: left, right, root
Other Binary Tree Operations

The level order traversal of a binary tree visits the nodes
of the tree row-by-row starting at the root node level.



On each level of the tree, the nodes are visited from left to right.
The level order traversal is not a recursive algorithm.
Implement the level order binary tree traversal using a
common data structure we have discussed in the class.

Write the pseudo code of this algorithm.
Level Order Binary Tree Traversal


Use the Queue data structure to control the output of
the level order binary tree traversal.
Algorithm


Insert/enqueue the root node in the queue
While there are nodes left in the queue,




Get/dequeue the node in the queue
Print the node’s value
If the pointer to the left child of the node is not null
 Insert/enqueue the left child node in the queue
If the pointer to the right child of the node is not null
 Insert/enqueue the right child node in the queue
Problem in Tress

Given the preOrder, inOrder or postOrder traversals
of a binary tree, draw the binary tree.



preOrder: 27 13 6 17 42 33 48
inOrder: 6 13 17 27 33 42 48
postOrder: 6 17 13 33 48 42 27
Problem in Trees

Draw the a binary search tree after inserting the
following sequence of values using the
insertNode() method from the tree class:

50, 25, 12, 6, 13, 33, 75, 67, 68, 88
Sorting Algorithms






Bubble sort
Insertion sort
Selection sort
Shell sort
Merge sort
Quick sort
Worst case Runtime O(?)
Worst case Runtime O(?)
Worst case Runtime O(?)
Worst case Runtime O(?)
Worst case Runtime O(?)
Worst case Runtime O(?)
Which one is best at least theoretically?
Which one is best in practice and Why?
Comparison of Sorting Algorithms
Bubble Sort
(N2)
(N2)
(N)
Selection Sort
(N2)
(N2)
(N2)
Best Case
is quadratic
Enumeration of Sorting Algorithms

Try the insertion sort, selection sort, shell sort, merge
sort and quick sort, algorithm on the following list of
integers for example:

{7, 3, 9, 5, 4, 8, 0, 1}
Standard Template Library (STL)
Containers
Iterators
Algorithms
Abstract Data Types (ADTs)

ADT is a set of objects together with a set of operations

Abstract





implementation of operations is not specified in ADT definition
E.g., List
Operations on a list: Insert, delete, search, sort
C++ class are perfect for ADTs
Can change ADT implementation details without
breaking code that uses the ADT
Lists Using STL

Two popular implementation of the List ADT

The vector provides a growable array implementation of
the List ADT



The list provides a doubly linked list implementation of
the List ADT



Advantage: it is indexable in constant time
Disadvantage: insertion and deletion are computationally
expensive
Advantage: insertion and deletion are cheap provided that the
position of the changes are known
Disadvantage: list is not easily indexable
Vector and list are class templates

Can be instantiated with different type of items
Lists Using STL (cont’d)

vector<Object>



Array-based implementation
findKth – O(1)
insert and remove – O(N)


list<Object>



Doubly-linked list with sentinel nodes
findKth – O(N)
insert and remove – O(1)


Unless change at end of vector
If position of change is known
Both require O(N) for search
Course Evaluations

Please take a few minutes to complete the online
course evaluations available at
https://skylight.wsu.edu/student/

Thank you for taking CptS 122.
Tentative Final Structure

Part I: Conceptual Questions (45pts)


Part II: Programming Questions (35pts)



Multiple Choice, Fill-in-the-blank, and True/False
 Go though the self-review exercises at the end of each
chapter
Write Templated C++ code for Linked List, Stack, Queue and
Tree
Retake Quiz 1 to Quiz 6
Part III: Enumerative and Pseudo code Questions (20pts)


Workout all the sorting algorithm on an example input set
 Remember the time complexity
Practice preOrder, inOrder, postOrder & level-order traversal
algorithm
Good Luck !