CMP 2003 • Midterm • Data Structures and Algorithms (C++)

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

Example 3

Static Array vs Dynamic Array

2D Static Arrays

2D Dynamic Arrays

Efficiency of Pointers

Example 1

Example 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

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

Example 1 (Parts a-c)

Example 1 (Parts d-e)

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

Example 1 (Parts a-c)

Example 1 (Parts d-e)

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

Example 1 (Parts a-c)

Example 1 (Parts d-e)

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

Linked List (Part 1)

Linked List (Part 2)

Circular Linked List (Part 1)

Circular Linked List (Part 2)

Doubly Linked List (Part 1)

Doubly Linked List (Part 2)

Our First Data Structure

Code for Amateurs

Linkedlist.h

ListNode

ListItr

List

Example 1

Example 2

Example 3

What is Recursion?

Factorials and Fibonacci Numbers

Binary Search using Recursion

Example 1

Example 2

What is a Stack?

Stack Operations

Static Int Stack Implementation

Using StaticIntStack

Dynamic Int Stack

Dynamic Int Stack Implementation

Using DynIntStack

What is a Stack?

Stack.h

Implementation

Example 1

Example 2

Example 3

What is a Queue?

Queue Operations

Problem with dequeue

Static Int Queue Implementation

Using StaticIntQueue

Dynamic Int Queue

Dynamic Int Queue Implementation

Using DynIntQueue

Stack vs Queue

What is a Queue?

Queue.h

Implementation

Example 1

Example 2

Example 3

Complexity Analysis 1

Complexity Analysis 2

Complexity Analysis 3

Complexity Analysis 4

Complexity Analysis 5

Linked Lists 1 - Part 1

Linked Lists 1 - Part 2

Linked Lists 2 - Part 1

Linked Lists 2 - Part 2

Linked Lists 3 - Part 1

Linked Lists 3 - Part 2

Linked Lists 4

Linked List 5

Linked List 6

Linked List 7

Linked List 8

Recursion 1

Recursion 2

Recursion 3

Stacks and Queues 1

Stacks and Queues 2

Stacks and Queues 3 - Part 1

Stacks and Queues 3 - Part 2

Stacks and Queues 4

Stacks and Queues 5

Stacks and Queues 6

Stacks and Queues 7

Question 1

Question 2

Question 3