CMPE 242 • Midterm I • Data Structures and Algorithms

Built-in Arrays

Array Properties

Example 1

Example 2

Introduction

Definition and Decleration

Assignment and Dereference

Be Careful!

Pointer of Pointers - new Keyword

Pointers with Arrays

sizeof() - malloc() - free()

delete Keyword

Pointers as Function Parameters

Pointers of Functions

Pointers of User-Defined Classes

Example 1

Example 2

Static Array vs Dynamic Array

2D Static Arrays

2D Dynamic Arrays

Efficiency of Pointers

Example 3

Introduction

Topic-wide Example: Set Class

Constructors

Copy Constructors

Destructors

this Keyword

Assignment (=) Operator

Add Assignment (+=) Operator

Addition (+) Operator

Addition (+) Operator: with a Foreign Object

Add Assignment (+=) Operator: with a Foreign Object

Equality (==) Operator

Output Stream (<<) Operator

Introduction

New Classes from Old Ones

Access Control Under Inheritance

Access to Private Members of Base Class

Constructors/Destructors Under Inheritance

Some Important Points

Copy Constructors Under Inheritance

Overriding

Multiple Inheritance

Function Overloading

Template Functions - 1

Template Functions - 2

Template Classes - 1

Template Classes - 2

Motivation

Big-O Notation

Big-Omega Notation

Big-Theta Notation

Fundamental Rules

Analyzing Complexity

Example 1

Example 2

Example 3

Recurrences

Example 4

Solving Recurrences

Example 5

Introduction

Singular LinkedList

Doubly LinkedList

Circular LinkedList

Some Background Information

What is a linkedlist?

Reminder: Structs

Constructing Linkedlists

Head and Tail Pointers

Printing a Linkedlist

Adding a Node to the End

Adding a Node in between Two Nodes (Add to a Sorted List)

Finding a Node in the List

Deleting a Node

Deleting the List

What is a Circular Linkedlist?

Constructing the List

Adding a Node to the Beginning/End

Adding a Node in between Two Nodes (Add to a Sorted List)

Counting Number of Elements

Finding a Node in the List

Deleting a Node

Constructing the List

Adding a Node to the Beginning

Adding a Node In Between two Nodes (Add to a Sorted List)

Adding a Node to End of the List

Deleting a Node from the Beginning

Deleting a Node in between Two Nodes (Deleting from a Sorted List)

Deleting a Node from the End

Finding a Node in the List

What is a Stack?

Array Implementation

LinkedList Implementation

What is a Stack?

Stack.h

Implementation

Example 1

Example 2

Example 3

What is a Queue?

Queue.h

Implementation

Example 1

Example 2

Example 3

Tree as a Data Structure

Terminology

How do we implement Trees?

Binary Trees / Binary Search Trees

Example 1

BST.h

Implementation - Constructors/Copying

Implementation - Destructors

Implementation - Find

Implementation - FindMin/FindMax

Implementation - Insert/Remove

Implementation - Printing

Example 2

Example 3

Example 4

Example 5

Example 6

Example 7

Pointers

Pointers

Pointers

Pointers

Pointers

Pointers

Classes - Part 1

Classes - Part 2

Classes - Part 1

Classes - Part 2

Classes - Part 3

Classes

Classes

Classes

Classes

Classes

Inheritance

Inheritance

Inheritance

Complexity Analysis

Complexity Analysis

Complexity Analysis

Complexity Analysis

Complexity Analysis

Complexity Analysis

Complexity Analysis

Linked Lists

Linked Lists

Linked Lists

Linked List

Linked List

Linked List

Linked Lists

Linked Lists

Linked Lists

Stack / Queue

Stack / Queue

Stack / Queue

Stack / Queue

Stack / Queue

Stack / Queue

Linked List/Stack/Queue

Linked List/Stack/Queue

Linked List/Stack/Queue

Trees

Trees

Trees

Trees

Trees

Trees