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

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

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)

Example 2 (Part 1)

Example 2 (Part 2)

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)

Example 2 (Part 1)

Example 2 (Part 2)

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)

Example 2 (Part 1)

Example 2 (Part 2)

2D Linkedlists

Hybrid Linkedlists

Constructing the List

Adding a PRIMARY NODE to the End of List

Adding a PRIMARY NODE in Between two Nodes

Adding a SECONDARY NODE to the End of a Row

Adding a SECONDARY NODE in Between two Nodes

Deleting a SECONDARY NODE

Deleting ALL SECONDARY NODES in a Row

Deleting a PRIMARY NODE

Clearing the List

Example 1 (Parts a-b)

Example 1 (Parts c-d)

Example 2 (Part 1)

Example 2 (Part 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 Queue?

Queue Operations

Problem with dequeue

Static Int Queue Implementation

Using StaticIntQueue

Dynamic Int Queue

Dynamic Int Queue Implementation

Using DynIntQueue

Stack vs Queue

Definition of Recursion

An Example: Factorials

Another Example: Fibonacci Numbers

Binary Search Operation

Binary Search Trees (BST)

Insertion in BST

Searching in BST

Displaying a BST

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 Lists 5 - Part 1

Linked Lists 5 - Part 1

Linked Lists 6

Stacks and Queues 1

Stacks and Queues 2

Stacks and Queues 3 - Part 1

Stacks and Queues 3 - Part 2

Stacks and Queues 4