Data Structures

Al-Albayt University
Computer Science Department
Instructor: Eng. Rami Jaradat
[email protected]

Textbook:
Data Structures Using C++, Second Edition, ,D.S. Malik, Cengage Learning 2010

[email protected] 1
 Contents
• Introduction
• Vector (Array-Based List)
• Linked Lists (Pointer-Based List)
• Recursion
• Stacks
• Queues
• Searching and Hashing Algorithms
• Sorting Algorithms
• Binary Search Trees

[email protected] 2
 Introduction

[email protected] 3
 Basic Principles
Object Oriented Programming (OOP)

• Encapsulation:
• the ability to combine data and operations in a single unit (class)

• Inheritance:
• the ability to create new data types from existing data types

• Polymorphism:
• the ability to use the same expression to denote different operations

[email protected] 4
 Data Abstraction
• Abstraction: separating the design details of something from its use.
• concerned only with how to use certain items, rather than with how they work.
• Data Abstraction is the process of separating the logical properties of the
data from its implementation
• Abstract data type (ADT): A data type that separates the logical properties
from the implementation details
• class: is a specification of a collection of data and the operations on the data.
• A class in an ADT
• ADT operations can be used without knowing how are they implemented or how
the data is stored.

[email protected] 5
 Data Structure
• The way of arranging g the data in the computer memory so that it
can accessed and updated efficiently
• A data structure is an implementation of an ADT within a
programming language.
• Examples of data structures: queue, stack, linked list, heap,
dictionary, and tree

[email protected] 6
 Algorithm
• Algorithm is a set of instructions that is applied on data to
accomplish a given task, such searching and sorting algorithms.

[email protected] 7
 Standard Template Library (STL)
• STL components
• Containers: class templates used to manage objects of a given type
• Iterators: class templates used to step through container elements
• Algorithms: manipulate data

[email protected] 8
 Container Types
• Sequence containers: every element has a specific position
• vector, deque, list

• Container adapters: created by limiting functionality in a preexisting

container and providing a different set of functionality
• stack, queue, priority _queue

• Associative containers: Elements are automatically sorted according

to some ordering criteria
• set, map, unordered_set, unorderd_map

[email protected] 9
 Vector
Array b-Based List

[email protected] 10
 vector
• Stores, manages objects in a dynamic array
• Elements accessed randomly
• Time-consuming item insertion: middle, beginning
• Fast item insertion: end
• Using a vector container in a program requires the following statement:
• #include <vector>
• Defining a vector container object
vector<int> intlist;
vector<string> stringList;

[email protected] 11
 Declaring vector objects

[email protected] 12
 Operations to access elements of a vector

[email protected] 13
 Various operations on a vector container

[email protected] 14
 Functions to determine the size of a vector container

[email protected] 15
 Declaring an Iterator to a Vector Container
• Process vector container like an array using array subscripting
operator
• class vector contains typedef iterator which is declared as a
public member
vector<int> v;
vector<int>::iterator it = v.begin();
• ++it: advances iterator it to next element into the container
• *it: returns element at current iterator position

[email protected] 16
 Containers: begin & end Functions
• begin: returns an iterator pointing to the first element into the
container
• end: returns an iterator pointing to the last element into the
container
• Functions have no parameters
• class vector: contains member functions used to find number of
elements currently in the container

[email protected] 17
 #include <iostream>
#include <vector>
using namespace std;
int main (){
int i, Arr[] = {16,2,77,29};
vector<int> A, B(4,100), C(B.begin(),B.end()), D(C), E(Arr, Arr+4);

cout << "contents of vector A:";

for (i=0; i < A.size(); i++)
cout << " " << A[i];

cout << "\ncontents of vector B:";

for (i=0; i < B.size(); i++)
cout << " " << B[i];

cout << "\ncontents of vector C:";

for (i=0; i < C.size(); i++) contents of vector A:
cout << " " << C[i]; contents of vector B: 100 100 100 100
contents of vector C: 100 100 100 100
cout << "\ncontents of vector D:"; contents of vector D: 100 100 100 100
contents of vector E: 16 2 77 29
for (i=0; i < D.size(); i++)
cout << " " << D[i];

cout << "\ncontents of vector E:";

for (i=0; i < E.size(); i++)
cout << " " << E[i];
}

[email protected] 18
 #include <iostream>
#include <vector>
using namespace std;
int main (){
vector<int> v;
cout << "size = " << v.size()<< " cap = " << v.capacity()<< endl;

v.push_back(4); v.push_back(2); v.push_back(1);

for (int i=0;i<v.size();i++)
cout << v[i] << " ";
cout << "\nsize = " << v.size()<< " cap = " << v.capacity()<< endl;

v.push_back(8); v.push_back(10);
for (int i=0;i<v.size();i++)
cout << v[i] << " ";
cout << "\nsize = " << v.size()<< " cap = " << v.capacity()<< endl;
size = 0 cap = 0
v.pop_back(); v.pop_back(); 4 2 1
for (int i=0;i<v.size();i++) size = 3 cap = 4
cout << v[i] << " "; 4 2 1 8 10
cout << "\nsize = " << v.size()<< " cap = " << v.capacity()<< endl; size = 5 cap = 8
4 2 1
} size = 3 cap = 8

[email protected] 19
 #include <iostream>
#include <vector>
using namespace std;

int main() {
vector<string> v;
string name;
=> ali
do{
=> heba Yousef
cout << "=> "; => ahmad
getline(cin,name); => bilal
if (name!="quit") => salma
v.push_back(name); => quit
} while (name!="quit"); ali
heba Yousef
for (int i=0;i<v.size();i++) ahmad
cout << v[i] << endl; bilal
salma
}

[email protected] 20
 Array-based List Implementation
class Vector {
public:
Vector(); The example shows the class
~Vector();
declaration of our own vector class
Vector (const Vector& v);
Vector& operator= (const Vector& v); which can be used as dynamic array
void push_back(float f); of floating points values.
void pop_back();
float& at(int index);
float& operator[](int index);
float& front();
float& back();
int size() const;
int capacity() const;
bool empty() const;
void resize (int num,float elem=0);
void clear();
private:
void resizeCapacity(int num);
float* data;
int Size, Capacity;
};
[email protected] 21
 Vector::Vector():Capacity(4),Size(0){ data = new float[Capacity];}

Vector::~Vector(){ delete[] data; }

Vector::Vector(const MyVector& v): Capacity(v.Capacity), Size(v.Size){

data = new float[Capacity];
for (int i=0; i<Size; i++)
data[i] = v.data[i];
}
As seen from the constructor, this
Vector& Vector::operator=(const Vector& v) { container class is implemented as a
if (this==&v) dynamic array.
return *this;
Destructor, copy constructor and
Capacity = v.Capacity;
assignment operator must be overridden
Size = v.Size;
delete[] data;
data = new float[Capacity];
for (int i=0; i<Size; i++)
data[i] = v.data[i];
return *this;
}

[email protected] 22
 void Vector::resize(int num,float elem){
resizeCapacity(num);
if (Capacity > Size)
for (int i=Size;i<Capacity;i++)
data[i] = elem;
Size = num;
}
void Vector::resizeCapacity(int num){
Capacity = num;
float* newdata = new float[Capacity];
if (Size > Capacity) Size = Capacity;
for (int i=0;i<Size;i++)
newdata[i] = data[i];
delete[] data;
data = newdata;
}
void Vector::clear() { Size = 0; }
int Vector::size() const { return Size; }
int Vector::capacity() const { return Capacity; }
bool Vector::empty() const {
if (Size==0)
return true;
return false;
}
[email protected] 23
 void Vector::push_back(float f) {
if (Size==Capacity)
resizeCapacity(Capacity*2);
data[Size] = f;
Size++;
}

void Vector::pop_back() {
if (Size!=0)
Size--;
}

float& Vector::at(int index) { return data[index]; }

float& Vector::operator[](int index) { return data[index]; }

float& Vector::front() { return data[0]; }

float& MyVector::back() { return data[Size-1]; }

[email protected] 24
 Insert operation:
void Vector::insert(int index, float f){ To insert an item into a particular
if (Size==Capacity) index position, you need to move a
resizeCapacity(Capacity*2); whole block of items one position
for (int i=Size; i > index; i--)
data[i] = data[i-1]; towards the end of the array.
data[index] = f;
Size++;
}

0 1 2 3 4 5 6 7
Size=5
1.1 2.3 7.1 3.6 8.2
Capacity = 8

Move elements to right (from the

v.insert(1,9.3) 1.1 2.3 7.1 3.6 8.2
end to position (index))

Size=6 Write the new value (f) to position

1.1 9.3 2.3 7.1 3.6 8.2
Capacity = 8 (index)

[email protected] 25
 Erase operation:
• to erase an item, you need to move a whole block of items one position towards
the beginning of the array to fill the erased gap
void Vector:: erase(int index){
for (int i=index; i < Size-1; i++)
data[i] = data[i+1];
Size--;
}
0 1 2 3 4 5 6 7
Size=6
1.1 9.3 2.3 7.1 3.6 8.2
Capacity = 8

move elements to left (from

v.insert(2) 1.1 9.3 2.3 7.1 3.6 8.2
position (index+1) to the end)

Size=5 Write the new value (9.3) to

1.1 9.3 7.1 3.6 8.2 8.2
Capacity = 8 position 1
[email protected] 26
 Array-based List : Advantage and Disadvantage

• Array-based list is efficient for :

• random access
• bi-directional sequential access
• inserting / erasing item to the end of the list

• Array-based list is NOT efficient for :

• inserting erasing items far away from the end of the list
• for use of data which the size changes frequently

[email protected] 27
 Linked List
Pointer-Based List

[email protected] 28
 Linked list node

• Every object of type node has two components:

• one to store the data
• one to store the address of the next node (called next)

struct node{
int data; data next
node *next;
}; node

[email protected] 29
 Linked List
Pointer-based Implementation
• A linked list is a collection of components, called nodes, every
node (except the last node) contains the address of the next node
• The address of the first node in the list is stored in a separate
location, called the head

head data next data next data next

Linked List

[email protected] 30
 Statement value
head Address of node 0
head->data 81
head->next Address of node 1
head->next->data 43
head->next->next Address of node 2
head->next->next->data 19
head->next->next->next 0

node 0 node 1 node 2

head 81 43 19

Linked List

[email protected] 31
 node *newnode;
Statement value
newnode = head newnode points to node 0
newnode = head>next newnode points to node 1
newnode = cur newnode points to node 2
newnode = cur->next newnode points to node 3
newnode = tail newnode points to node 4
newnode = tail->next newnode points to NULL

node 0 node 1 node 2 node 3 node 4

head 7 16 56 26 10

cur tail
[email protected] 32
 struct node{ char item; node* next;};
class linkedList {
public:
linkedList();
~linkedList();
linkedList(const linkedList & list);
linkedList & operator= (const linkedList & list);
void push_front(char ch); The class interface is EXACTLY the
void pop_front();
void push_back(char ch); SAME with the earlier array-based
void pop_back(); linked list class.
char& at(int index);
char& operator[](int index); This is a GOOD example of data
char& front(); abstraction, the interface of a ADT is
char& back(); independent of its implementation
int size() const;
bool empty() const;
void clear();
void display();
void erase(int index);
void insert(int index, char ch);
private:
node* get_Pointer(int nodeNo);
int Size;
node *head, *tail;
};
[email protected] 33
 linkedList::linkedList(): Size(0){ head = tail = NULL; }

linkedList ::~ linkedList(){

while ( !empty() )
pop_front(); }

linkedList & linkedList::operator= (const linkedList & list){

if(this==&list)
return *this;
Size = list.Size;
head = tail = NULL;
node *cur = list.head;
while (cur != NULL) {
push_back( cur->item );
cur = cur->next;
}
return *this;
}

linkedList::linkedList(const linkedList & list){ *this = list; }

int linkedList ::size() const { return Size; }

[email protected] 34
 bool linkedList ::empty() const {
if (head == NULL)
return true;
}
void linkedList ::clear(){
while ( !empty() )
pop_front();
}
void linkedList ::push_front(char ch) {
if ( empty() ) {
head = new node;
head->item = ch;
head->next = NULL;
tail = head;
}
else {
node* slot = new node;
slot->item = ch;
slot->next = head;
head = slot;
}
Size++;
}
[email protected] 35
 void linkedList::push_back(char ch) {
if ( empty() ) {
head = new node;
head->item = ch;
head->next = NULL;
tail = head;
}
else {
node* slot = new node;
slot->item = ch;
slot->next = NULL;
tail->next = slot;
tail = slot;
}
Size++;
}
void linkedList ::display(){
node *cur = head;
while (cur != NULL){
cout << cur->item<<" ";
cur = cur->next;
}
cout<<endl;
} 36
[email protected]
 node* linkedList::get_Pointer(int nodeNo) {
if ( empty() ){cout << "Error : empty list" << endl; exit(1); }
if (nodeNo >= Size){cout << "Error : past the end"<<endl; exit(1); }
node *cur = head;
int i = 0;
while (i < nodeNo) {
cur = cur->next;
i++; }
return cur;
}

char& linkedList::at(int nodeNo) {

node* p = get_Pointer(nodeNo);
return p->item;
}

char& linkedList::operator[](int nodeNo) {

node* p = get_Pointer(nodeNo);
return p->item;
}

[email protected] 37
 void linkedList ::erase(int nodeNo) {
if ( empty() ) {
cout << "Error : empty list" << endl;
exit(1);
}
if (nodeNo==0){
node* oldhead = head;
head = head->next;
delete oldhead;
}
else {
node *prev = get_Pointer(nodeNo-1);
node *cur = prev->next;
prev->next = cur->next;
delete cur;
}
Size--;
}

[email protected] 38
 void linkedList ::insert(int nodeNo, char ch) {
node* slot = new node; slot->item = ch;
if (nodeNo==0){
slot->next = head;
head = slot;
}
else {
node *prev = get_Pointer(nodeNo-1);
node *cur = prev->next;
prev->next = slot;
slot->next = cur;
if (cur == NULL)
tail = slot;
}
Size++;
}
void linkedList::pop_front(){
if ( empty() ) { cout << "Error : pop empty list" << endl; exit(1); }
node* oldhead = head;
head = head->next;
delete oldhead;
Size--;
}
[email protected] 39
 void linkedList::pop_back() {
if ( empty() ) {cout << "Error : pop empty list" << endl; exit(1); }
if ( Size == 1 )
pop_front();
node *prev = get_Pointer(Size-2);
node *cur = prev->next;
delete cur;
prev->next = NULL;
tail = prev;
Size--;
}

char& linkedList::front() {
if ( empty() ){ cout<< "Error : empty list"<< endl; exit(1); }
return head->item;
}

char& linkedList::back() {
if ( empty() ) { cout << "Error : empty list" << endl; exit(1); }
return tail->item;
}
[email protected] 40
 Doubly Linked List
• A doubly linked list is a linked list in which every node contains the
address of the next node and the address of the previous node
• Can be traversed in either direction
• The address of the first node in the list is stored in a separate location,
called the head

head

data data data

Doubly Linked List

[email protected] 41
 Doubly linked list node
• Every object of type node has three components:
• one to store the data
• one to store the address of the next node (called next)
• one to store the address of the previous node (called previous)

struct node{
int data;
node *next;
node *previous; previous data next
};
Doubly Linked List node

[email protected] 42
Erase the node pointed by cur 8 16 47 13 5 NULL

NULL head
cur tail
1. node *prevnode = cur->previous, *nextnode = cur->next;

8 16 47 13 5 NULL

NULL head prevnode cur nextnode tail

2. prevnode->next = nextnode;
nextnode->previous = prevnode; 8 16 47 13 5 NULL

NULL head
prevnode cur nextnode tail

3. delete cur;

8 16 13 5 NULL

NULL head prevnode

[email protected]
nextnode tail 43
insert a node with the value (11) at 8 16 47 13 5 NULL
position pointed by cur
NULL head cur tail

1. node *prevnode = cur->previous;

8 16 47 13 5 NULL

NULL head prevnode cur tail

11
2. node *slot = new node; slot->data = 11;
slot

3. prevnode->next = slot;
slot->previous = prevnode; 8 16 11 47 13 5 NULL

NULL head prevnode slot cur tail

4. slot->next = cur;
cur->previous = slot;
8 16 11 47 13 5 NULL

NULL head prevnode slot cur tail

[email protected] 44
 Advantage of Doubly Linked List

• For node deletion or insertion, the previous node can be directly

obtained based on the current node, without having to search
through the list starting from the head node.
• The iterator became bi-directional as it can now iterate forward as
well as backward to the previous node.

[email protected] 45
 Circular Linked List
• A circular list is a linked list in which the last node points to the first node
• In a circular doubly linked list, the next pointer of the last node points to the first
node and the previous pointer of first node points to the last node.

• There is no head or tail pointer, but we still need a pointer to one of the
nodes to access the list.
• Application : Implementing a queue
cur

8 16 11 47 13 5

[email protected] 46
 RECURSION

[email protected] 47
 Recursion
• A recursive function is a function that calls itself.
• Each recursive function must have at least one base case, as well as the general
(recursive) case
• base case: is the case for which the answer is known (and can be expressed without
recursion)
• Each successive recursive call should bring you closer to the base case
• The main aim of a recursive function is to break down a complex problem to a
solvable problem (the base case).
• A recursive function is designed to terminate when it reaches its base case

[email protected] 48
 Three Question Method of verifying recursive functions

• Base Case Question:

• Is there a non-recursive way out of the function?

• Smaller Caller Question:

• Does each recursive function call involve a smaller case of the original
problem leading to the base case?

• General Case Question:

• Assuming each recursive call works correctly, does the whole function
work correctly?

[email protected] 49
 Why use recursion
• Those examples could have been written without recursion, using
iteration instead. The iterative solution uses a loop, and the recursive
solution uses an if statement.
• However, for certain problems the recursive solution is the most
natural solution. This often occurs when pointer variables are used.

[email protected] 50
 When a function is called...
• A transfer of control occurs from the calling block to the code of the
function. It is necessary that there be a return to the correct place in
the calling block after the function code is executed. This correct place
is called the return address.

• When any function is called, the run-time stack is used. On this stack
is placed an activation record (stack frame) for the function call.

[email protected] 51
 Stack Activation Frames
• The activation record stores the return address for this function call, and also
the parameters, local variables, and the function’s return value, if non-void.

• The activation record for a particular function call is popped off the run-time
stack when the final closing brace in the function code is reached, or when a
return statement is reached in the function code.

• At this time the function’s return value, if non-void, is brought back to the
calling block return address for use there.

[email protected] 52
 General format for many recursive functions

if(some condition for which answer is known)

// base case
solution statement
else
// general case
recursive function call

[email protected] 53
 Infinite Function Calls
• The function prints the letter “A”, then calls itself, but it won’t stop I(infinite loop)
• The program will eventually crash, because each time a function is called,
temporary information is stored on a stack which will eventually overflow and
cause an error
• A recursive function must have some algorithm to control the number of times it
repeats
void message(){
cout << "A\n";
message(); A
} A
A
.
int main(){ message(); } .
.

[email protected] 54
 Control the number of recursive functions calls
• The if statement controls the repetition:
• If n>0: function will print the letter “A” then call itself with the argument n-1
• For example: If the function is called initially with n=3 from the main function:
1. Print “A” then call itself with n=2
2. Print “A” then call itself with n=1
3. Print “A” then call itself with n=0
4. When n=0, the if condition is false, “A” will not be printed and the function will not call itself

void message(int n) {
if(n>0) {
cout << "A\n"; A
message(n-1); A
} A
}
int main(){ message(3); }

[email protected] 55
 1st call of the function
Value of n: 3 This cycle repeats itself until 0
2nd call of the function is passed to the function.
Value of n: 2

3rd call of the function

Value of n: 1

4th call of the function

Value of n: 0

Depth of recursion: 4

[email protected] 56
 void message(int n){
cout << "begin function call with n="<< n <<endl;
if (n>0){
cout << "recursive function\n";
message(n-1);
}
cout << "end function with n=" << n <<endl;
begin function call with n=3
} recursive function
begin function call with n=2
int main() { recursive function
begin function call with n=1
message(3); recursive function
begin function call with n=0
} end function with n=0
end function with n=1
end function with n=2
end function with n=3

[email protected] 57
 Example 4: Counting letters
int Count(char Target, char* String, int Start=0){
if (String[Start] != 0){
if (String[Start] == Target)
return 1 + Count(Target, String, Start+1);
else
return Count(Target, String, Start+1);
}
return 0;
}
int main(){
cout<<Count('a', "happy birthday ahmad");
4
}

[email protected] 58
 Greatest Common Devisor (GCD)
• GCD function uses recursion to find the greatest common devisor (GCD) of two integers.
• To calculate the GCD of two integers x and y, use Euclid’s algorithm:
𝐺𝐶𝐷 𝑥 , 𝑦 = 𝑦 𝑖𝑓 𝑦 𝑑𝑖𝑣𝑖𝑑𝑒𝑠 𝑥
𝐺𝐶𝐷(𝑥 , 𝑦) = 𝐺𝐶𝐷(𝑦 , 𝑟𝑒𝑚𝑎𝑖𝑛𝑑𝑒𝑟 𝑜𝑓 𝑥/𝑦);
• Example: GCD(21,15)= GCD(15,21%15)= GCD(15,6)= GCD(6,r15%6)= GCD(6,3)=3
int GCD(int x , int y){
if(x%y == 0)
return y;
else
return GCD(y , x%y);
}

[email protected] 59
 Power

int Power ( int x, int n) {

if ( n == 0 ) // base case
return 1;
else // general case
return ( x * Power ( x , n-1 ) ) ;
}

[email protected] 60
 Recursive Factorial
• Base case is when 𝑛 = 0 and 𝑛 = 1, where 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(0) = 1 and 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(1) = 1
• General case: the value of 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑛) can be written as:
𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑛) = 𝑛 × (𝑛 − 1) ×. . .× 1 or 𝑛 × 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(𝑛 − 1)
• Each recursive call 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙 (𝑛 − 1) gets closer to the base case of 𝐹𝑎𝑐𝑡𝑜𝑟𝑖𝑎𝑙(1).

int Factorial (int number) {

if((number == 1) || (number == 0)) // base case
return 1;
else // general case
return number*Factorial(number-1);
}

[email protected] 61
 Reversing input characters

void reverse(){
char ch;
cin.get(ch);
if (ch != '\n'){
reverse();
cout.put(ch);
}
}
enter a text:hello world
int main(){ dlrow olleh
cout<<"enter a text:";
reverse();
}

[email protected] 62
 Sum the contents of an int array

int sum(int y[], int lastindex){

if (lastindex < 0)
return 0;
else
return y[lastindex] + sum(y, lastindex-1);
}

[email protected] 63
 Direct and Indirect Recursion
• The previous functions called themselves directly. This is called direct
recursion.
• Indirect recursion is also possible, e.g. when function A calls function B
which calls function A.
• Alternatively, function A could call function B, that calls function C that
calls function A.

[email protected] 64
 The Towers of Hanoi
• According to legend, the monks in a remote mountain monastery knew how to
predict when the world would end. They had a set of 3 diamond needles. Stacked
on the first diamond needle were 64 gold disks of decreasing size.
• The legend said that when all 64 disks has been transferred to the destination
needle, the stars would be extinguished, and the world would end.
• This task requires 264-1 moves! the

[email protected] 65
 Rules of moving the Disks
1. Only one disk can be moved at a time
2. A larger disk can not be placed on top of a smaller disk
3. Only one auxiliary needle can be used for the intermediate storage of
disks.

1
2
3

Source Auxiliary Destination

[email protected] 66
 Recursive Solution
• The problem with n disks can be broken down into a smaller sub-problems, to
each of which that same general solving procedure applies, as follows:
• Base case:
• Move 0 disks (do nothing)
• General Case:
1. Move n−1 disks from the source to auxiliary, this leaves the disk n as a top
disk on the source.
2. Move disk n from the source to the destination
3. Move the n−1 disks from auxiliary to destination

[email protected] 67
void hanoi(int n, char source, char destination, char auxiliary){
static int i=1; n=4
if(n==0)
1 move disk 1 from A To B
return; 2 move disk 2 from A To C
hanoi(n-1, source, auxiliary, destination); 3 move disk 1 from B To C
cout<<i++<<"\tmove disk "<<n<<" from " 4 move disk 3 from A To B
<<source<<" To "<<destination<<endl; 5 move disk 1 from C To A
6 move disk 2 from C To B
hanoi(n-1, auxiliary, destination, source);
7 move disk 1 from A To B
} 8 move disk 4 from A To C
int main(){ 9 move disk 1 from B To C
char A='A', B='B',C='C'; 10 move disk 2 from B To A
int n; 11 move disk 1 from C To A
12 move disk 3 from B To C
cin>>n;
13 move disk 1 from A To B
hanoi(n,A,C,B); 14 move disk 2 from A To C
} 15 move disk 1 from B To C
n=1 n=3
1 move disk 1 from A To C 1 move disk 1 from A To C
2 move disk 2 from A To B
n=2 3 move disk 1 from C To B
4 move disk 3 from A To C
1 move disk 1 from A To B 5 move disk 1 from B To A
2 move disk 2 from A To C 6 move disk 2 from B To C
3 move disk 1 from B To C 7 move disk 1 from A To C

[email protected] 68
 A B C A B C A B C
START STEP1 STEP2

A B C A B C A B C
STEP3 STEP4 STEP5

A B C A B C
STEP6 STEP7 69
[email protected]
 hanoi
(3,A,C,B)

hanoi
(2,A,B,C) hanoi
Step 4
(2,B,C,A)
move disk 3
from A To C

hanoi hanoi
(1,A,C,B) Step 2 hanoi hanoi
(1,C,B,A) Step 6
(1,B,A,C) (1,A,C,B)
move disk 2
from A To B move disk 2
from B To C

hanoi hanoi hanoi hanoi

Step 1 hanoi hanoi Step 5 hanoi
(0,A,B,C) (0,B,C,A) (0,C,A,B) Step 3 hanoi
(0,A,B,C) (0,B,C,A) (0,C,A,B) Step 7
(0,A,B,C) (0,B,C,A)
move disk 1 move disk 1
from A To C move disk 1
from C To B move disk 1
from B To A
from A To C

[email protected] 70
 1. move disk 1 from A To C
2. move disk 2 from A To B
3. move disk 1 from C To B
4. move disk 3 from A To C
5. move disk 1 from B To A
6. move disk 2 from B To C
7. move disk 1 from A To C
8. move disk 4 from A To B
9. move disk 1 from C To B
10. move disk 2 from C To A
11. move disk 1 from B To A
12. move disk 3 from C To B
1 13. move disk 1 from A To C
2 14. move disk 2 from A To B
3 15. move disk 1 from C To B
16. move disk 5 from A To C
4 17. move disk 1 from B To A
5 18. move disk 2 from B To C
19. move disk 1 from A To C
20. move disk 3 from B To A
Source Auxiliary Destination 21. move disk 1 from C To B
A B C 22. move disk 2 from C To A
23. move disk 1 from B To A
24. move disk 4 from B To C
25. move disk 1 from A To C
26. move disk 2 from A To B
27. move disk 1 from C To B
28. move disk 3 from A To C
29. move disk 1 from B To A
30. move disk 2 from B To C
[email protected] 31. move disk 1 from A To C 71
 Stacks

[email protected] 72
 Stacks
• A stack is a list in where the addition and deletion of elements occur
only at one end, called the top of the stack
• Last In First Out (LIFO) data structure
• Used to implement function calls

[email protected] 73
 Various Types of Stacks
• For example, in a cafeteria, the second tray in a stack of trays can be removed only if
the first tray has been removed.
• Similarly, to get to your favorite computer science book, which is underneath your
math and history books, you must first remove the math and history books. After
removing these two books, the computer science book becomes the top book (the
top element of the stack).

[email protected] 74
 Last In First Out (LIFO) data structure
• A stack has the property that the last item placed on the stack will be
the first item removed. This property is commonly referred to as last
in, first out, or simply LIFO.

[email protected] 75
 Empty Stack
• Initially, all of the boxes are on the floor and the stack is empty.

[email protected] 76
 Stack Operations
a. First, we push box A onto the stack
b. We then push box B onto the stack
c. Next, we push box C onto the stack
d. Next, we retrieve the top element of the stack
e. We then push box D onto the stack
f. Next, we pop the stack

[email protected] 77
 ADT Stack Operations
• Create an empty stack.
• Destroy a stack.
• Determine whether a stack is empty.
• Add a new item to the stack.
• Remove from the stack the item that was added most recently.
• Retrieve from the stack the item that was added most recently.

[email protected] 78
 Array-Based Implementation of the Stack
• stackTop can range from 0 to maxStackSize
• If stackTop = 0, then the stack is empty
• If stackTop ≠ 0, then stackTop-1 is the index of the top
element of the stack the
• stackTop is the index to write a new element
• maxStackSize is the capacity of the stack

• Setting stackTop to 0 will initialize the stack

[email protected] 79
 Push operation

[email protected] 80
 Pop operation

[email protected] 81
 An Array-Based Implementation of the ADT Stack
class Stack{
public:
Stack();
bool isEmpty() const;
void push(int item);
void pop();
void pop(int& top);
void getTop(int& top) const;
void display();
private:
int items[MAX_STACK];
int stackTop;
};

[email protected] 82
 Stack::Stack(): stackTop(0){ } When a stack is empty, stackTop = 0

bool Stack ::isEmpty() const{ return (stackTop==0); }

void Stack::push(int item){

if (stackTop >= MAX_STACK)
cout << "Stack is full" ;
else{ When an item is pushed to a stack, top will
items[stackTop] = item; increase by 1.
++stackTop;
}
}
void Stack ::pop(){
if (isEmpty())
cout <<"Stack is empty";
else
--stackTop;
}
[email protected] 83
 void Stack ::pop(int & top){
if (isEmpty()) cout <<"Stack is empty";
else {
--stackTop;
top = items[stackTop];
cout << top; }
}
void Stack ::getTop(int& top) const {
if (isEmpty()) cout <<"stack is empty" ;
else top = items[stackTop-1];
cout << top;
}
void Stack ::display() {
cout << "Items in the stack : ";
cout <<"[";
for (int i=0; i<stackTtop; i++)
cout << " " << items[i];
cout<<" ]";
}

[email protected] 84
 # include <iostream>
using namespace std;
const int MAX_STACK = 10;
int main() {
int p, item;
Stack aStack;
cin >> item;
aStack.push(item);
cin >> item;
aStack.push(item);
cin >> item;
aStack.push(item);
aStack.display(); 2
aStack.pop(); 3
aStack.pop(); 5
Items in the stack : [ 2 3 5 ]
cout << endl;
Items in the stack : [ 2 ]
aStack.display();
Press any key to continue …
}

[email protected] 85
 A Pointer-Based Implementation of the ADT Stack
class Stack {
public:
Stack();
Stack(const Stack& aStack);
Stack& operator=(const Stack&);
~Stack();
bool isEmpty() const;
void push(int item);
void pop();
void pop(int& stackTop);
void getTop(int & stackTop) const;
void display();
private:
struct node { int item; node *next; };
node *topPtr;
};

[email protected] 86
 Push operation

Stack before push operation create newNode newNode->next = stackTop StackTop = newNode

[email protected] 87
 Pop operation

Stack before push operation Temp = stackTop delete temp

stackTop = stackTop->next;

[email protected] 88
 Stack::Stack(): topPtr(NULL) { }

Stack::Stack(const Stack& aStack) {

if (aStack.topPtr == NULL)
topPtr = NULL; // original list is empty
else { // copy first node
topPtr = new node;
topPtr->item = aStack.topPtr->item;
// copy rest of the list
node *newPtr = topPtr; // new list pointer
for (node *origPtr=aStack.topPtr->next; origPtr!=NULL; origPtr=origPtr->next) {
newPtr->next = new node;
newPtr = newPtr->next;
newPtr->item = origPtr->item;
}
newPtr->next = NULL;
}
}

[email protected] 89
 Stack& Stack::operator=(const Stack& aStack) {
if (aStack.topPtr == NULL)
topPtr = NULL; //original list is empty
else { // copy first node
topPtr = new node;
topPtr->item = aStack.topPtr->item;
// copy rest of the list
node *newPtr = topPtr; // new list pointer
for (node *origPtr=aStack.topPtr->next; origPtr!=NULL; origPtr=origPtr->next) {
newPtr ->next = new node;
newPtr = newPtr->next;
newPtr ->item = origPtr->item;
}
newPtr ->next = NULL;
}
return *this;
}

Stack ::~Stack(){
while (!isEmpty())
pop();
}
[email protected] 90
 bool Stack::isEmpty() const { return topPtr == NULL; }

void Stack::push(int item) {

node *newPtr = new node; // create a new node
newPtr->item = item;
newPtr->next = topPtr;
topPtr = newPtr;
cout << "\n One item is pushed !!!!";
}

void Stack::pop() {
if (isEmpty())
cout << "Stack empty on pop";
else { // stack is not empty; delete top
node *temp = topPtr;
topPtr = topPtr->next;
// return deleted node to system
delete temp;
}
cout << "\n One item is popped !!!!";
}
[email protected] 91
 void Stack::pop(int & stackTop){
if(isEmpty()) cout << "Stack empty on pop";
else { stackTop = topPtr->item;
node *temp = topPtr;
topPtr = topPtr->next;
delete temp; }
}

void Stack::getTop(int & stackTop) const {

if(isEmpty()) cout << "stack empty on getTop";
else stackTop = topPtr->item;
cout << "\nTop Element of the stack is " << stackTop << endl;
}

void Stack::display() {
node *curPtr = topPtr;
cout << "\nItems in the stack : [";
while (curPtr != NULL) {
cout << " " << curPtr->item;
curPtr = curPtr->next;
}
cout<<" ]\n";
}
[email protected] 92
 int main(){
int p;
int item;
Stack aStack; Enter an item to be pushed : 3
cout << "Enter an item: "; cin >> item; aStack.push(item); One item is pushed !!!!
Enter an item to be pushed : 4
cout << "Enter an item: "; cin >> item; aStack.push(item); One item is pushed !!!!
cout << "Enter an item: "; cin >> item; aStack.push(item); Enter an item to be pushed : 1
aStack.display(); One item is pushed !!!!
Items in the stack : [ 1 4 3 ]
aStack.pop(); One item is popped !!!!
aStack.display(); Items in the stack : [ 4 3 ]
aStack.getTop(p); Top Element of the stack is 4
Enter an item to be pushed : 6
cout << "Enter an item:"; cin >> item; aStack.push(item); One item is pushed !!!!
aStack.display(); Items in the stack : [ 6 4 3 ]
aStack.getTop(p); Top Element of the stack is 6
Make another copy of the stack
cout << "\n Make another copy of the stack" << endl; Items in the stack : [ 6 4 3 ]
Stack newItem(aStack); // a call to copy constructor Make second copy of the stack
newItem.display(); Items in the stack : [ 6 4 3 ]
Press any key to continue . . .
cout << "\n Make second copy of the stack" << endl;
Stack secondItem;
secondItem = newItem; // a call to operator=(
secondItem.display();
}

[email protected] 93
 The copy constructor
• One final insecurity that can arise with linked structures occurs when the C++
compiler calls for a copy of an object.
• Objects need to be copied when an argument is passed to a function by value.
• In C++, the default copy operation copies each data member of a class. the
default copy operation on a linked Stack leads to a sharing of data between
objects.
• In other words, the default copy operation on a linked Stack has reference semantics. This
allows a malicious client to declare and run a function whose sole purpose is to destroy linked
Stack objects

[email protected] 94
 The Standard Template Library Class stack
#include <iostream>
#include <stack>
using namespace std;
int main() {
stack <string> s;
s.push("Ali"); stack size() = 4
stack top() = tala
s.push("heba");
stack top() = Ahmad
s.push("Ahmad"); stack top() = heba
s.push("tala"); stack top() = Ali
cout << "stack size() = " << s.size() << "\n"; stack size() = 0
while (!s.empty()){
cout << "stack top() = " << s.top() << "\n";
s.pop();
}
cout << "stack size() = " << s.size() << "\n";
}

[email protected] 95
 Stack Applications
• Infix to postfix convertor
• Postfix expression calculator
• Bracket matching

[email protected] 96
 Infix to postfix convertor
1. Scan the input string (infix notation) from left to right
2. If the symbol scanned is an operand, then append it to the postfix string.
3. If the next symbol is an operator:
A. Pop and append to the postfix string every operator on the stack that is above the
most recently scanned left parenthesis and has precedence higher than or is a
right-associative operator of equal precedence to that of the new operator
symbol.
B. Push the new operator onto the stack.

[email protected] 97
 Infix to postfix convertor
4. If the symbol scanned is a left parenthesis, then always push onto the stack.
5. If the symbol scanned is a right parenthesis, then, all operators down to the
most recently scanned left parenthesis must be popped and appended to the
postfix string. Furthermore, this pair of parentheses must be discarded.
6. When the infix string is completely scanned, all the remaining operators should
be popped and appended to the postfix string.

[email protected] 98
 Infix expression: (𝐴 + 𝐵 ∗ (𝐶 − 𝐷))/𝐸
Symbol Stack Postfix expression
( (
A ( A
+ (+ A
B (+ AB
* (+* AB
( (+*( AB
C (+*( ABC
- (+*(- ABC
D (+*(- ABCD
) (+* ABCD-
) ABCD-*+
/ / ABCD-*+ Postfix expression: 𝐴𝐵𝐶𝐷 −∗ +𝐸/
E / ABCD-*+E
ABCD-*+E/
[email protected] 99
 Symbol Stack Postfix expression
A A
+ + A
( +( A
B +( AB
* +(* AB
C +(* ABC
- +(- ABC*
Infix expression: ( +(-( ABC* Postfix expression:
A+(B*C–(D/E^F)*G)*H D +(-( ABC*D
ABC*DEF^/G*-H*+
/ +(-(/ ABC*
E +(-(/ ABC*DE
^ +(-(/^ ABC*DE
F +(-(/^ ABC*DEF
) +(- ABC*DEF^/
* +(-* ABC*DEF^/
G +(-* ABC*DEF^/G
) + ABC*DEF^/G*-
* +* ABC*DEF^/G*-
H +* ABC*DEF^/G*-H
[email protected] ABC*DEF^/G*-H*+ 100
 Postfix expression calculator
1. Scan the expression from left to right:
A. If it is an operand, push it onto the stack
B. If it is an operator
I. pop from stack the last two operands and perform the operation (+-*/ …)
II. push back the result onto the stack

[email protected] 101
 Bracket matching
• Read the program file character by character, for every character:
• if an opening bracket (, [, { is encountered, push it into the stack.
• When a closing bracket ), ], } is encountered, pop out the top of the element.
• check if the top of the stack matches the current closing bracket.
• If it is a match, then continue
• else, report the problem.

[email protected] 102
 Queues

[email protected] 103
 Queues
• Definition: A queue is a set of elements of the same type in which the
elements are added at one end, called the back or rear, and deleted
from the other end, called the front or first
• First In First Out (FIFO) data structure
• Elements are processed in the order they were added

[email protected] 104
 A bank line at time (a) 0; (b) 12; (c) 20; (d) 38

For example, bank customers

waiting are processed in the
order they arrived in

[email protected] 105
 ADT Queue Operations
1.Create an empty queue.
2.Destroy a queue.
3.Determine whether a queue is empty.
4.Add a new item to the queue.
5.Remove from the queue the item that was added earliest.
6.Retrieve from the queue the item that was added earliest.

[email protected] 106
 Array-Based Implementation of queue
• An array can be used to implement a queue for applications in which a fixed-sized
queue does not present a problem
• front and back are the indices of the front and back items, respectively
• Initially, front is 0 and back is -1:
• To insert a new item into the queue, increment back and place the item in items[back].

• To delete an item, you simply increment front.

• The queue is empty whenever front is greater than back.

• The queue is full when back equals MAX_QUEUE -1.

[email protected] 107
 Array-Based Implementation of queue
• rightward drift: after a sequence of additions and removals as shown in figures
below, the items in the queue will drift toward the end of the array, and back could
equal MAX_QUEUE – 1 even when the queue contains only a few items.

• One possible solution to this problem is to shift array elements to the left, either
after each deletion or whenever back equals MAX_QUEUE – 1.
• This solution guarantees that the queue can always contain up to MAX_QUEUE
items.

[email protected] 108
 Array-Based Implementation
• A better solution is possible by viewing the array as circular
• Queue indices front and back are advanced by moving them clockwise around the
array

[email protected] 109
 Array-Based Implementation
• The figures illustrate the effect of a sequence of three queue operations on front,
back, and the array.
• When either front or back advances past MAX_QUEUE – 1, it wraps around to 0.
• This wraparound eliminates the problem of rightward drift, which occurred in the
previous implementation, because here the circular array has no end.
• The only difficulty with this scheme involves detecting the queue-empty and
queue-full conditions.

[email protected] 110
 Array-Based Implementation
• If front is one slot ahead of back, then:
• The queue is empty (figure a)
• Or the queue is full queue (figure b)

Figure (a) Figure (b)

front passes back when the queue becomes empty back catches up to front when the queue becomes full

[email protected] 111
 Array-Based Implementation
• Obviously, you need a way to distinguish between the two situations.
• One such way is to keep a count of the number of items in the queue.
• Before inserting into the queue, you check to see if the count is equal to
MAX_QUEUE: if it is, the queue is full.
• Before deleting an item from the queue, you check to see if the count is zero, if it
is, the queue is empty.

[email protected] 112
 Array-Based Implementation
• Initially, front=0, back=MAX_QUEUE – 1, and count=0.
• using modulo arithmetic when incrementing front and back. For example, to insert a
new item into the queue:
back = (back+1) % MAX_QUEUE;
items[back] = newItem;
++count;
• If back is equal to MAX_QUEUE -1 before the insertion of newItem, then the first
statement, back=(back+1)%MAX_QUEUE, would have the effect of wrapping back
around to location 0.
• Similarly, you can delete the item at the front of the queue by using the statements
front=(front+1)%MAX_QUEUE;
--count;
[email protected] 113
 Array-Based Implementation of queue
class Queue {
public:
Queue(); // default constructor
bool isEmpty() const;
void push(QueueItemType newItem);
void pop(); Declaration
void pop(QueueItemType& queueFront); of class
void getFront(QueueItemType& queueFront) const; Queue
void display() const;

private:
QueueItemType items[MAX_QUEUE];
int front;
int back;
int count;
};

[email protected] 114
 Queue ::Queue() : front(0), back(MAX_QUEUE-1), count(0) { }

bool Queue ::isEmpty() const {

return (count==0);
}

void Queue ::push(QueueItemType newItem){

if(count == MAX_QUEUE)
cout << "queue full on push";

else { // queue is not full, insert item

back = (back+1) % MAX_QUEUE;
items[back] = newItem;
++count;
}

[email protected] 115
 void Queue ::pop() {
if (isEmpty())
cout << "empty queue, cannot pop" ;
else { // queue is not empty; remove front
front = (front+1) % MAX_QUEUE;
--count;
}
}
void Queue ::pop(QueueItemType& queueFront){
if (isEmpty())
cout << "empty queue, cannot pop\n" ;
else { // queue is not empty; retrieve and remove front
queueFront = items[front];
front = (front+1) % MAX_QUEUE;
--count;
cout << "Front element of the queue is "<< queueFront << endl;
}
}

[email protected] 116
 void Queue ::getFront(QueueItemType& queueFront) const {
if (isEmpty())
cout << "empty queue, cannot getFront" ;
else { // queue is not empty; retrieve front
queueFront = items[front];
cout << "Front element of the queue is “;
cout << queueFront << endl;
}
}
void Queue ::display() const {
cout << "Items in the queue : [";
i = front - 1;
do {
i = (i+1)% MAX_QUEUE;
cout << items[i] << "\t";
} while (i != back)
cout << " ]\n";
}

[email protected] 117
 #include <iostream>
const int MAX_QUEUE = 5;
typedef int QueueItemType;
using namespace std;

int main() {
int a;
Queue Q;
Q.push(15);
Q.push(20);
Q.push(25);
Q.push(33); Items in the queue : [ 15 20 25 33 ]
Q.display(); Front element of the queue is 15
Q.getFront(a);
Items in the queue : [ 25 33 ]
Q.pop();
Front element of the queue is 25
Q.pop();
Items in the queue : [ 33 ]
Q.display();
Q.pop(a);
Q.display();
}

[email protected] 118
 Pointer-Based Implementation
• A pointer-based queue can be implemented using:

• Linear linked list that can be

implemented with two external
pointers, front and back.

• Circular linked list that can be

implemented with a single external
pointer to the back.

[email protected] 119
 Pointer-Based Implementation
• Insertion at the back and deletion from the front are straightforward.
• The figure shows the insertion of an item to a nonempty queue.

Inserting an item into a nonempty queue

[email protected] 120
 A Pointer-Based Implementation
• Deletion from the front of the queue is simpler than insertion at the back.
• The figure shows the removal of the front item of a queue that contains more than
one item

Deleting an item from a queue of more than one item

[email protected] 121
 A Pointer-Based Implementation of queue
class Queue {
public:
Queue();
Queue(const Queue& Q);
~Queue();
bool isEmpty() const;
void push(QueueItemType newItem);
void pop();
void pop(QueueItemType& queueFront);
void getFront(QueueItemType& queueFront) const;
void display();
private:
struct node { QueueItemType item; node *next; };
node *front;
node *back;
};

[email protected] 122
 Queue::Queue() : back(NULL), front(NULL) { }

Queue::Queue(const Queue& Q){

front = back = NULL;
node *cur = Q.front;
while (cur != NULL) { push( cur->item ); cur = cur->next; }
}

Queue Queue::operator=(const Queue& Q){

while(!isEmpty())
pop();
front = back = NULL;
node *cur = Q.front;
while (cur != NULL) { push( cur->item ); cur = cur->next; }
return *this;
}

Queue::~Queue() { while (!isEmpty()) pop(); }

bool Queue::isEmpty() const { return bool(back == NULL); }

[email protected] 123
void Queue::push(QueueItemType newItem) {
if (isEmpty()) {
front = new node;
front->item = newItem;
front->next = NULL;
back=front; }
else { // create a new node
node* newPtr = new node;
newPtr ->item = newItem;
newPtr ->next = NULL;
back ->next = newPtr;
back = newPtr; }
}
void Queue::pop() {
if (isEmpty()) cout << "empty queue, cannot pop" ;
else { // queue is not empty; remove front
node *tempPtr = front;
if (front == back) { // special case, one node in queue
front = NULL;
back = NULL; }
else { front = front->next; }
tempPtr ->next = NULL;
delete tempPtr;
}
} // end pop
[email protected] 124
 void Queue::pop(QueueItemType& queueFront){
if ( isEmpty() ) cout << "empty queue, cannot pop\n" ;
else { // queue is not empty; retrieve and remove front
queueFront = front ->item;
pop(); // delete front
cout << "Front element of the queue is " << queueFront << endl; }
} // end pop

void Queue ::getFront(QueueItemType& queueFront) const {

if (isEmpty()) cout << "empty queue, cannot getFront" ;
else { // queue is not empty; retrieve front
queueFront = front ->item;
cout << "Front element of the queue is " << queueFront << endl; }
}

void Queue ::display() {

node *curPtr = front;
cout << "Items in the queue : [ ";
while (curPtr != NULL) {
cout << curPtr ->item<<" " ;
curPtr = curPtr ->next; }
cout << "]\n";
}
[email protected] 125
 int main(){
int x;
Queue Q;
Q.push(3);
Q.push(5);
Q.push(7); Items in the queue : [ 3 5 7 9 ]
Q.push(9); Front element of the queue is 3
Items in the queue : [ 7 9 ]
Q.display();
Front element of the queue is 7
Q.getFront(x); Items in the queue : [ 9 ]
Q.pop(); Press any key to continue . . .
Q.pop();
Q.display();
Q.pop(x);
Q.display();
}

[email protected] 126
 STL Class queue
template <class T>
class queue {
public:
queue(); // default constructor
queue(const queue&); // copy constructor
~queue(); // destructor
queue& operator=(const queue&); // assignment operator
int size() const; // returns number of elements
bool empty() const; // returns true if is empty
T& front(); // returns the element in front
T& back(); // returns the element in back
void push(const T&); // inserts given element at back
void pop(); // removes element from front
};

[email protected] 127
 #include<iostream>
#include<queue>
using namespace std;
int main(){
queue<string> q;
q.push("Ali");
q.push("Ashraf");
q.push("Heba");
q.push("Yasmeem");
q.push("Noor");
cout << "Size of queue is : " << q.size() << endl;
cout << "Front element of the queue is "; Size of queue is : 5
cout << q.front()<<endl; Front element of the queue is Ali
cout << "Back element of the queue is "; Back element of the queue is Noor
cout << q.back()<<endl; Elements in the queue :
cout << "Elements in the queue :\n"; Ali
while (!q.empty()) { Ashraf
cout << q.front() << endl; Heba
q.pop(); Yasmeen
Noor
}
}
[email protected] 128
 Queue Applications: Reading a String of Characters

• When you enter characters at a keyboard, the system must retain them in
the order in which you typed them. It could use a queue for this purpose, as
the following pseudo code indicates:
• read a string of characters from a single line of input into a queue
Q.createQueue()
While (not end of line){
Read a new character
Q.push(ch)
}

[email protected] 129
 Queue Applications: Reading a String of Characters

• Once the characters are in a queue, the system can process them, as necessary.
• For example: If you had typed an integer without any mistakes, but possibly
preceded or followed by blanks, the queue would contain digits and possibly
blanks.
• If the digits are 2, 4, and 7, the system could convert them into the decimal value
247 by computing: 10 × (10 × 2 + 4) + 7

[email protected] 130
 Queue Applications: Reading a String of Characters
// convert digits in a queue into a decimal integer n
// get first digit, ignoring any leading blanks

int read(queue<char> q){

int n=0,y;
char x;
while(!q.empty()){
while(q.front()==' ') // ignore any leading blanks
q.pop();
if(!q.empty()){
x = q.front();
y = int(x)-48; //covert char to int
n = 10*n + y;
q.pop();
}
}
return n;
}
[email protected] 131
 Queue Applications: Recognizing Palindromes
• A palindrome is a string that reads the same from left to right as it does from right to left.
• A queue and a stack can be used to o determine whether a string is a palindrome as
follows:
1. Push each character in the string into both a queue and a stack.
2. pop a character from the queue and from the stack
3. Compare both characters, if they are not equal, return false and finish
4. Repeat this process until stack or queue becomes empty
5. return true

[email protected] 132
 #include<iostream>
#include<queue>
#include<stack>
using namespace std;

bool isPal(string str){

queue<char> q; stack<char> s; int i=0;
while(str[i]!= '\0'){ q.push(str[i]); s.push(str[i]); i++; }
while(!q.empty() && !s.empty()){
if(q.front() != s.top())
return false;
q.pop();
s.pop();
}
return true;
}

int main(){
if(isPal("abcba")) cout<<"is a palindrome"<<endl;
else cout<<"is no a palindrome"<<endl;
}
[email protected] 133
 PRIORITY QUEUES
• In certain situations, the First In First Out rule needs to be relaxed:
• For example, In a hospital, patients are usually seen in the order they arrive, however, if a
patient arrives with life threatening symptoms, they are treated first. These patients take
priority over the patients who can wait to be seen
• A priority queue data structure can be used in such cases:
• customers or jobs with higher priority are pushed to the front of the queue.
• One way to implement a priority queue is to use an ordinary linked list, which
keeps the items in order from the highest to lowest priority.

[email protected] 134
 STL Priority Queue
template <class T>
class priority_queue { These are the same functions as
public: for the queue class template. The
priority_queue(); only significant difference is that
priority_queue(const priority_queue&); the priority_queue class requires
the template parameter T to be
~priority_queue();
an ordinal type (i.e., a type for
priority_queue& operator=(const priority_queue&);
which the comparison operators
int size() const; // returns number of elements
are defined) so that the pop() and
bool empty() const; // returns true iff this is empty top() functions remove and return
const T& top() const; // returns the front element the highest priority element
void push(const T&); // inserts given element at back instead of the first element.
void pop(); // removes element from front
private:
// . . . .
};

[email protected] 135
 #include<iostream>
#include<queue>
using namespace std;
void print(priority_queue<int>); // prints a copy of given queue
int main(){
priority_queue<int> pq; print(pq);
pq.push(44); print(pq);
pq.push(66); print(pq);
pq.push(22); print(pq);
pq.push(55); print(pq);
pq.push(33); print(pq);
}
size=0
size=1,top=44:(44)
void print(priority_queue<int> q){ size=2,top=66:(66,44)
cout << "size=" << q.size(); size=3,top=66:(66,44,22)
if (q.size()>0){ size=4,top=66:(66,55,44,22)
cout << ",top=" << q.top() << ":(" << q.top(); size=5,top=66:(66,55,44,33,22)
q.pop();
while (!q.empty()){ cout << "," << q.top();q.pop(); }
cout << ")";
}
cout << "\n";
} 136
[email protected]
 PRIORITY QUEUES
• The print() function suggests that the elements are stored in the priority queue in
descending order
• But that is probably not true. The function uses the priority_queue ::pop()
function to access the elements, and that member function is required to remove
the elements in order of their priority.
• But there is no obligation on the priority_queue itself to store the elements in any
particular order.
• Indeed, most implementations keep the elements only partially ordered.

[email protected] 137
 Searching and Hashing
Algorithms

[email protected] 138
 Searching Algorithm
• The most important operation performed on a list is the search Algorithm
• Using the search algorithm, you can do the following:
• Determine whether a particular item is in the list.
• If the data is specially organized (for example, sorted), find the location in the list where a new
item can be inserted.
• Find the location of an item to be deleted.
• The performance of the search algorithm is crucial:
• If the search is slow, it takes a large amount of computer time to accomplish the task, whereas,
if the search is fast, you can accomplish the task quickly.

[email protected] 139
 Sequential Search (Linear search)
• The sequential search works the same for both array-based and linked lists
• does not require the list elements to be in any particular order
• always starts at the first element in the list and continues until either the item is
found in the list or the entire list is searched.

[email protected] 140
 Sequential Search (Linear search)
• Search the list below for a student bool found = false;
mark given his ID number using for (i=0; i<A.size(); i++)
sequential search if (A[i].ID == id){
cout << a[i].Mark;
found = true
break;
A[0] A[1] A[2] A[3] }
ID 86 78 91 33 if (found !=true)
Mark 74 63 17 20 cout << "Not in the List";

[email protected] 141
 Sequential Search
• Best Case: found at first location
• number of comparisons = 1 𝑂(1)

• Worst Case: found at the last element

• number of comparisons = n 𝑂(𝑛)
1+2+3+⋯+𝑛 𝑛(𝑛+1) 𝑛+1
• Average Case: = =
𝑛 2𝑛 2

[email protected] 142
 Sequential Search
• Advantages:
• Useful for limited sized data sets
• Does not require data to be structured in any way
• Useful when the data set to be searched is constantly changing
• Disadvantages :
• Time consuming for large lists

[email protected] 143
 Binary Search
• Binary search algorithm uses the divide-and-conquer technique to
search the list.
• The search item is compared with the middle element of the list, then:
• If the search item is found, the search terminates.
• If the search item is less than the middle element of the list, search to the first
half of the list
• otherwise, we search the second half of the list
• Binary Search can be written using iteration or recursion.

[email protected] 144
 Binary Search: Non-Recursive Algorithm
bool BinarySearch(int data[], int target, int from, int to){
bool found =0;
int mid;
while ( (found == 0) && (from <= to) ){
mid = (to + from)/2;
if (target == data[mid])
found = 1;
else if(target< data[mid])
to = mid - 1;
else
from = mid + 1;
}
if (found){
cout<<"\nPosition ="<<mid;
return true; }
else {
cout<<"\nTarget not found";
return false;
}
}
[email protected] 145
 Binary Search: Recursive Algorithm
bool BinarySearch(int data[], int target, int from, int to){
int mid ;
if (from > to) base case
return false ; (not found)
else {
mid = (from + to)/2;
base case
if (data[mid] == target)
(found at mid)
return true ;
else
if (target < data[mid]) search lower half
return BinarySearch(data, target, from, mid-1 );
else search upper half
return BinarySearch(data, target, mid + 1, to );
}
}

[email protected] 146
 int data[15]={0,2,4,6,8,10,12,14,16,18,20,22,24,26,28} First Call (from=0, to=14)
bool found = BinarySearch(data, 25, 0, 14 ); • (0+14)/2 = 7
• 25 is greater than 14 (data[7])
• Search upper half

Second Call(from=8, to=14)

Index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
• (8+14)/2 = 11
data 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 • 25 is greater than 22 (data[11])
• Search upper half

16 18 20 22 24 26 28
Third call(from=12, to=14)
• (12+14)/2 = 13
24 26 28 • 25 is smaller than 26(data[13])
• Search lower half

24 Fourth call(from=12, to=12)

• (12+12)/2 = 12
• 25 is greater than 24 (data[12])
• Search upper half

Fifth Call(from=13, to=12)

• 13 is greater than 12
• Return false
[email protected] 147
 Comparison-Based Search Algorithms
• Bothe sequential and binary search algorithms perform the search by comparing
the target with the list elements.
• For this reason, these algorithms are called comparison-based search algorithms
• The fewer comparisons the better the algorithm.
• A comparison tree is used to obtain the worst-case number of comparisons:
• Each comparison is represented by a node in the tree.
• Edges represent the possible outcomes.
• The binary search algorithm is the optimal worst-case algorithm for solving search
problems by the comparison method.
• Worst case complexity is 𝑂( log2(𝑛) ) comparisons.

[email protected] 148
 Comparison tree for Search Algorithms
• Comparison tree for sequential search of • Comparison tree for binary search of 7
7 elements (worst case = 7 comparisons) elements (worst case = 3 comparisons)
=
1 =
≠ = 4
2 ≠
= < >
3 ≠
= = =
4 ≠ 2 6
= < > < >
= = =
=
5 ≠ 1 3 7
= 5
6 ≠
=
7

[email protected] 149
 Hashing
• The optimal comparison-based search algorithm is the binary search, 𝑂( log2(𝑛) ), where
𝑛 is the size of the list
• A search algorithm that is of order less than log2(𝑛) , it cannot be comparison based.
• Hashing is such a search algorithm
• In hashing, the data is organized with the help of a table, called the hash table (HT) which
is stored in an array.
• To determine whether a particular item with a key is in the table, we apply a function h,
called the hash function, to the key that is compute h(X).
• h(X) gives the address of the item in the hash table.
• Because the address of an item is computed with the help of a function, it follows that the
items are stored in no particular order.

[email protected] 150
 Hashing
• For example, if the data of all students in tiny college with their ID numbers were
stored in an array, then to look for any student we simply go to the location of the
student ID and retrieve.
• The ID is the KEY which is the value used for searching
• The search time will be constant O(1)
• If the student ID is 10 digits long, then we need to use a hash function to convert
that large number into a smaller number to match an array index.
• Hash Function is used to convert the key into a hash table index.
• The Keys may be integers, characters or some kind of data

[email protected] 151
 Hashing
• How to choose a hash function
• Easy to compute.
• Minimize the number of collisions.
• How to organize the data with the help of the hash table
• The data is either stored within the hash table, that is, in an array.
• Or the data is stored in linked lists and the hash table is an array of pointers to those
linked lists.

[email protected] 152
 Methods of Hashing: Identity
• Creating an array and storing the keys in those elements with the same
index
• Hash function: index = key
• Disadvantage:
• For this to be a viable proposition memory would have to be limitless (and
wastable).
• In practice you cannot afford such extravagance.

[email protected] 153
 Methods of Hashing: Truncation
• With truncation part of the key is ignored and the remainder used directly.
• For example:
suppose there were just 6 keys: 12302, 12303, 12305, 12307, 12308, 12309
hash function: index = last digit of key (or index = key mod 12300 )
• The above hash function would not work for the keys: 2134, 4134, 5134, 7134, 9134
• Here you would require a hash function that removes the last 3 digits. This is why it is
necessary for you to know something about the distribution of actual keys before
deciding a hash function.

[email protected] 154
 Methods of Hashing: Folding
• The key is partitioned, and the parts are combined in some way (maybe by adding
or multiplying them) to obtain the index.
• Suppose we have 1000 records with 8-digit keys then, the 8 digit key such as
62538194, 62538195 may be partitioned into: 625, 381, 94, 625, 381, 95
• The groups now added: 1100, 1101 and the result truncated: 100, 101
• Since, all the information in the key is used in generating the index, folding often
achieves a better spread than truncation just by itself.

[email protected] 155
 Methods of Hashing: Modular Arithmetic
• The key is converted into an integer, the integer is then divided by the size of the
index range and the remainder is taken as the index position of the record.
• index = key % size
• Example: suppose we have a 5-digit integer as a key and there are 1000 records,
the hash function would then be: index = KEY % size e.g., 12345 % 1000
• If we are very lucky, our keys might be such that there is only 1 key that maps to
each index. we might still have the situation where two keys map to the same
index (e.g. 23456, 43456), this is called a COLLISION.

[email protected] 156
 #define MAX 20
int HASH(int);
int main (){
int table[MAX],index, i, target;
for(i=1; i<=MAX; i++)
table[i-1]=10*i;
cout<<"Enter Target: ";
cin>>target;
index = HASH(target);
if (index!=-1){
if (table[index] == target) cout<<"Found at"<<"table[“<<index<<"]";
else cout <<"Target Not found";
}
else cout <<"Target Not found";
}

int HASH(int key){

int index = key/10-1;
if (index<MAX) Enter Target: 20
return index; Found at table[1]
else
return -1; Enter Target: 15
} Target not found
[email protected] 157
 Collision
• Collision is when the hashing Function gives out the same index for
two keys
• For example: 123%10 = 3, index will be 3 and 223 % 10, index will be
again 3
• We cannot store two values in the same location.

[email protected] 158
 Resolving Collision
• Resolving collisions by REPLACEMENT
• Resolving collisions by OPEN ADDRESSING
• Linear probing
• Quadratic probing
• Resolving collisions by CHAINING

[email protected] 159
 Resolving collisions by replacement:
• Simply replace the old KEY with the new KEY when there is a
collision
• The Old Key is simply lost or it is combined with the new Key.
• Example: 121 122 221 124 125 126 224 index = key % 10
0 1 2 3 4 5 6 7 8 9
121
221 122 124
224 125 126

• Very Rarely used

• Used only when the data are sets.
• Using UNION Operation old data is combined with the new data.

[email protected] 160
 Resolving collisions by Open addressing:
• Collision is resolved by putting the new Key in some other empty location in the
table:
• Two methods are used to locate the empty location:
1. Linear Probing: Start at the point where the collision occurred and do a
sequential search through the table for an empty location. Circular Probing is
an improvement in which after reaching the end start probing from the first
2. Quadratic Probing: If there is a collision at the address h, this method probes
the table at locations:
(h+i2) % hash_tables_ize for i = 1,2,3…

[email protected] 161
 Example: Linear Probing
Keys = 6 key 12 15 21 36 84 96
Hash Table Size = 7
Index 5 1 0 1 0 5
Hash Function = key mod 7

0 1 2 3 4 5 6

21 15 36 84 12 96

[email protected] 162
 Example: Quadratic Probing
Keys = 10
key 12 15 21 36 84 96 24 51 54 94
Hash Table Size = 15
Index 12 0 6 6 9 6 9 6 9 4
Hash Function = key mod 15

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

15 51 54 94 21 36 84 96 12 24

[email protected] 163
 Resolving collisions by Chaining
• Implemented using Linked List
• Whenever a collision occurs a new node is created, and the new value is stored
and linked to the old value.
key 12 15 21 36 84 96
Index 5 1 0 1 0 5

0 1 2 3 4 5 6

21 15 NULL NULL NULL 12 NULL

84 36 96

NULL NULL
[email protected] 164
 • Using modulo-division method and linear probing to store the following keys in an array
of 19 elements: 224562, 137456, 214562, 140145, 214576, 162145, 144467, 199645,
234534
224562 % 19 = 1
137456 % 19 =10
214562 % 19 =14
140145 % 19 =1 ( 2)
214576 % 19 =9
162145 % 19 =18
144467 % 19 =10 ( 11)
199645 % 19 =12
234534 % 19 =17

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
224562 214576 214576 137456 144467 199645 214562 234534 162145

[email protected] 165
 Sorting Algorithms

[email protected] 166
 Sorting
• Sorting is the process through which data are arranged according to their values.
• If data is not ordered in some way, we will spend an incredible amount of time
trying to find the correct information.
• What is sorting?
• There are many algorithms for sorting, some simple but perhaps inefficient others
complicated but efficient.

[email protected] 167
 Sorting Algorithms
• Selection Sort
• Insertion Sort
• Bubble Sort
• Quick Sort

[email protected] 168
 Selection Sort
• An array-based list is sorted by selecting elements in the list, one at a time, and
moving them to their proper positions.
• The first time we locate the smallest item in the entire list, the second time we
locate the smallest item in the list starting from the second element in the list, and
so on.
1. From position 0, find the smallest and then swap it with the element in position 0.
2. From position 1, find the smallest and swap it with the element in position 1.
3. Now from 2 do the same until you have reached the end of the list

for positions i=0 to max-1

find smallest item from position i
swap with position i

[email protected] 169
 0 1 2 3 4 5
1. Starting from index 0, find the 40 20 50 45 10
smallest element 5

0 1 2 3 4 5
2. Swap the smallest element
5 20 50 45 40 10
with the first element.
Sorted Side Unsorted Side
Repeat starting from index 1 0 1 2 3 4 5
3. Find the smallest element in the 5 10 50 45 40 20
unsorted side and swap with the Sorted Side Unsorted Side
first element in the unsorted side
0 1 2 3 4 5
4. Repeat the process and stop when the
5 10 20 45 40 50
unsorted side has just one item
Sorted Side Unsorted Side
0 1 2 3 4 5
5 10 20 40 45 50

Sorted Side Unsorted Side 170

[email protected]
 const int size=10;
//swaps x with y
void swap(int &x, int &y){
void selectionSort(int A[size]){
int temp=x;
int k;
x=y;
for (int i=0; i<size; i++){
y=temp;
k=Min(A,i);
}
swap(A[k],A[i]);
}
} //returns the index of the min value in
the array starting from the given position
int main() { int Min(int A[], int pos){
int A[size],k; int i, m=A[pos], index=pos;
for (int i=0; i<size; i++) for (i=pos+1; i<size; i++)
cin>>A[i]; if (A[i]<m){
m=A[i];
selectionSort(A); index=i;
}
cout<<"Sorted elements:"<< endl; return index;
for (int i=0;i<size;i++) }
cout<<A[i]<<" ";
}
[email protected] 171
 Selection Sort-Example
67 33 21 84 49 50 75

21 33 67 84 49 50 75

21 33 67 84 49 50 75

21 33 49 84 67 50 75

21 33 49 50 67 84 75

21 33 49 50 67 84 75

21 33 49 50 67 75 84
[email protected] 172
 Insertion Sorting Algorithm
• Insertion Sort views the array as having a sorted side and an unsorted side
• Sorts the list by moving each element to its proper place
• This is the way that most people sort playing cards
• Elements are Picked one by one and put into the Proper Place
• The sorted side starts with just the first element, which is not necessarily the
smallest element.

[email protected] 173
 const int size=10;
void insertionSort(int A[size]){
int temp, j;
for(int i=1; i<size; i++){
temp=A[i];
j=i;
while( j>0 && temp < A[j-1] ){
A[j]=A[j-1]; // shift one position to right
j--;
}
A[j]=temp; // place in proper position
}
}
int main(){
int A[size];
for(int i=0; i<size; i++)
cin>>A[i];

insertionSort(A);

cout<<"The elements after Sort:"<<endl;

for(int i=0; i<size; i++)
cout<<A[i]<<" ";
}
[email protected] 174
 33 84 67 21 49 33 84 84 21
temp 49

Sorted list Unsorted list copy 67 33 67 84 21 49

33 67 84 84 49

33 84 21 33 67 67 84 49
67 49
copy temp 33 33 67 84 49
Sorted list Unsorted list 21
21 33 67 84 49

21 33 67 84 84
21 33 67 84 49 67
21 33 67 84
copy
temp
Sorted list Unsorted list 21 33 49 67 84
49

21 33 49 67 84

[email protected] Sorted list 175

 Bubble Sort
• Works by comparing neighbours in the array and swapping them if necessary to
put the smaller of the pair first.
• On each pass through the array one element 'bubbles' up into place (Largest
Element sinks down)

[email protected] 176
 const int size=10;
void swap(int &x, int &y){ int temp=x; x=y; y=temp; }

void bubbleSort(int A[size]){

for(int i=0; i<size; i++)
for(int j=0; j<size-1; j++)
if( A[j] > A[j+1] )
swap( A[j],A[j+1] );
}

int main(){
int A[size];
for(int i=0; i<size; i++)
cin>>A[i];

bubbleSort(A);

cout<<"The elements after Sort:"<<endl;

for(int i=0; i<size; i++)
cout<<A[i]<<" ";
}

[email protected] 177
 Bubble Sort-Example 67 33 21 84 49 50 75

67 33 21 84 49 50 75 Swap 67 with 33 33 21 67 49 50 75 84 Swap 33 with 21

33 67 21 84 49 50 75 Swap 67 with 21 21 33 67 49 50 75 84 No Swap

33 21 67 84 49 50 75 No Swap 21 33 67 49 50 75 84 Swap 67 with 49

33 21 67 84 49 50 75 Swap 84 with 49 21 33 49 67 50 75 84 Swap 67 with 50

33 21 67 49 84 50 75 Swap 84 with 50 21 33 49 50 67 75 84 No Swap

33 21 67 49 50 84 75 Swap 84 with 75 21 33 49 50 67 75 84 End of second pass

33 21 67 49 50 75 84 End of first pass

Continue for size -1 passes

[email protected] 178
 DIVIDE and CONQUER
• Divide and Conquer: the Problem is divided into similar subproblems
until the problem is small enough to be handled.
• Used in merge and quick sort

[email protected] 179
 Quick Sort
• The list is partitioned into two sublists (lowerSublist and upperSublist), and the two
sublists are then sorted (using quicksort) and combined into one list in such a way
so that the combined list is sorted
• To partition the list into two sublists, first choose the pivot.
• The pivot is an element used to divide the list into two sublists.
• the elements in the lowerSublist are smaller than the pivot
• and the elements in the upperSublist are greater than the pivot.
• There are several ways to determine the pivot:
• the pivot is chosen such that the lowerSublist and upperSublist are of nearly equal size
• In the next example, the pivot is chosen as the middle element

[email protected] 180
 Quick Sort
• Once a pivot value has been selected, the algorithm swaps the other values
in the list until all the elements in lowerSublist are less than the pivot, and all
the elements in upperSublist are greater than the pivot.
• Once this is done, the algorithm repeats the on lowerSublist and then on
upperSublist.
• The recursion stops when there is only one element in a sublist. At that
point the original list is completely sorted.

[email protected] 181
 General Algorithm
if the list has 0 or 1 elements return
else do the following
pick an element in the list to use as pivot
split the remaining elements into two sub lists
lowerSublist = elements < pivot
upperSublist = elements > pivot
return the list rearranged as
Quicksort(lowerSublist),pivot, Quicksort(upperSublist)

pivot

lowerSublist upperSublist

[email protected] 182
 Partition Algorithm
1. Determine the pivot, and swap the pivot with the first element of the list.
Suppose that the index pivotIndex points to the last element smaller than the pivot. The index
pivotIndex is initialized to the first element of the list.
2. Repeat for the remaining elements in the list (starting at the second element) If
the current element is smaller than the pivot
a. Increment pivotIndex.
b. Swap the current element with the array element pointed to by pivotIndex
3. Swap the first element, that is, the pivot, with the array element pointed to by
pivotIndex.

[email protected] 183
 void swap(int &x, int &y) int partition(int list[], int start, int end){
{ int temp=x; x=y; y=temp; } int pivot, pivotIndex;

// pivot is chosen as the middle element

void quickSort(int list[], int start, int end){ int mid=(start+end)/2;
int pivotPoint;
if(start<end){ // put the pivot in the first position
// partition the list. swap(list[start], list[mid]);
pivotPoint = partition(list, start, end);
// Sort the lower sublist. pivotIndex=start;
quickSort(list, start, pivotPoint-1); pivot=list[start];
// Sort the upper sublist.
quickSort(list, pivotPoint+1, end); for (int i=start+1; i<=end; i++)
} /*increment pivotIndex when an element less than
} // End quicksort pivot is found. the pivotIndex is the position
of the pivot in the final sorted list*/
if (list[i] < pivot){
int main(){ pivotIndex++;
int A[10] = {5,11,66,3,4,0,9,17,88,6}; swap(list[pivotIndex], list[i]);
}
quickSort(A,0,9);
swap(list[start], list[pivotIndex]);
for(int i=0;i<10; i++) return pivotIndex;
cout<<A[i]<<" ";
} } // End partition

[email protected] 184
 0 1 2 3 4 5 6 7 8
45 82 25 94 50 60 78 32 92 pivot=50, Swap(45,50), pivotIndex=0 List[pivotIndex]
List[i]
50 82 25 94 45 60 78 32 92 i=1: Compare 82 with 50, do nothing
50 82 25 94 45 60 78 32 92 i=2: Compare 25 with 50, pivotIndex=1, swap(82,25)

50 25 82 94 45 60 78 32 92 i=3: Compare 94 with 50, do nothing

50 25 82 94 45 60 78 32 92 i=4: Compare 45 with 50, pivotIndex=2, swap(82,45)

50 25 45 94 82 60 78 32 92 i=5: Compare 60 with 50, do nothing
50 25 45 94 82 60 78 32 92 i=6: Compare 78 with 50, do nothing

50 25 45 94 82 60 78 32 92 i=7: Compare 32 with 50, pivotIndex=3, swap(94,32)

50 25 45 32 82 60 78 94 92 i=8: Compare 92 with 50, do nothing

i=9: end loop
32 25 45 50 82 60 78 94 92 Swap (50,32), return pivotIndex (3), end partition
The pivot (50) is in the proper position

Repeat for lowerSublist Repeat for upperSublist

0 1 2 4 5 6 7 8
32 25 45 82 60 78 94 92
[email protected] 185
 0 1 2 3 4 5 6 7 8

32 25 45 50 82 60 78 94 92
0 1 2 4 5 6 7 8
32 25 45 82 60 78 94 92
25 32 45 78 60 82 94 92

25 32 45 78 60 82 94 92
78 60 82 94 92
25 32 45
78 60 82 94 92
1 2
Start >= end
60 78 82 94 92
stop 6 7 8
32 45
Start >= end Start >= end 82 94 92
Stop
stop 94 82 92
6 7 94 82 92
Start >= end Start >= end 92 82
stop 92 82 94
stop
82 92

Start >= end Start >= end

Start >= end
stop stop
[email protected]
stop 186
 Time Complexity of Quick Sort
• Average case complexity is 𝑂(𝑛 log 𝑛)
• Worst case is 𝑂(𝑛2)
• For this particular example Partition function will be called 6 times
• 1st call it will loop 8 times
• 2nd call it will loop 2 times
• 3rd call it will loop 1 times
• 4th call it will loop 4 times
• 5th call it will loop 2 times
• 6th call it will loop 1 times

[email protected] 187
 Binary Trees

[email protected] 188
 Tree
• A Tree consists of a finite set of elements, called nodes and a finite set of
directed lines called branches, that connect the nodes
• A list is:
• Efficient for searching (ordered list()
• Inefficient for insertion and deletion of elements (require Data movements)
• Linked List
• Efficient for insertion and deletion of elements
• Inefficient for searching
• A tree combines the advantages of an ordered array and a linked list
• Efficient for searching, insertion and deletion of elements

[email protected] 189
 Basic Concepts
• Binary Tree: tree in which a node can have 0 , 1, or 2 Subtrees
• Indegree: number of branches directed toward the node
• Outdegree: number of branches directed outward from a node
• Root: a node that has an indegree of zero
• Level: distance of a node from the root (node G is at level 3)
• Height: level of the leaf in the longest path from the root + 1
• Ancestor: any node in the path from root to the node
• Descendant: all nodes in the path from that node to leaf node

[email protected] 190
 Basic Concepts
• A is the root node
• Height of the tree = 4
• B is the left child of A and C is the right child of A
• A is called the parent of B and C
• B is the root node for LT
• C is the root node for RT

Left subtree (LT) Right subtree (RT)

[email protected] 191
 Properties of Binary Tree
• A tree is said to be balanced if the height of the left subtree and the height of the right
subtree differ by not more than 1, and each subtree is also balanced
ℎ 𝐿 𝑇 − ℎ 𝑅𝑇 ≤ 1

• Full Binary Tree : A Binary Tree of height h with no missing nodes:

• all leaves are at level h
• and all other nodes each having two children

• Complete Binary Tree: A binary tree of height h that is full to

level h-1 and has level h filled in from left to right

[email protected] 192
 A
A

A B E
B

One node binary tree C

n=1 C D F G

• Balanced binary tree

E • Full binary tree
• n=7
• Height = 3
F
Unbalanced Binary tree
n=7
Height = 7
G

[email protected] 193
 Binary Tree Node
• Every object of type node has three components:
• Data
• Pointer to the left child
• Pointer to the right child

struct node{
int data; data
node *left; left right
node *right;
};

[email protected] 194
 Binary Tree Traversal
• Preorder traversal
• Inorder traversal
• Postorder traversal

[email protected] 195
 Preorder (VLR)
• Preorder traversal
• Visit the node
• Traverse the left subtree
• Traverse the right subtree

void preOrder(node* n){

if (n != NULL){
cout<< n->data <<endl;
preOrder(n->left);
preOrder(n-> right);
}
}

[email protected] 196
 Inorder (LVR)
• Inorder traversal
• Traverse the left subtree
• Visit the node
• Traverse the right subtree

void InOrder(node* n) {
if (n != NULL){
InOrder(n->left);
cout<<n->data<<endl;
InOrder(n->right);
}
}

[email protected] 197
 Postorder (LRV)
• Postorder traversal
• Traverse the left subtree
• Traverse the right subtree
• Visit the node

void postOrder(node* n) {
if (n != NULL){
postOrder(n->leftc);
postOrder(n->right);
cout<<n->data<<endl;
}
}

[email protected] 198
 9
Preorder Traversal (VLR)
9 7 6 1 5 3 2 4 8 12 10 11 14 13 7 12

Inorder Traversal (LVR) 6 8 10 14

1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 11 13
Postorder Traversal (LRV) 5
2 4 3 5 1 6 8 7 11 10 13 14 12 9
3

2 4

[email protected] 199
 Binary Search Tree

• A data structure that is efficient for searching, insertion

and deletion
• A binary search tree has the following properties:
• Data in each node is larger than any data in its left subtree
• Data in each node is smaller than any data in its right subtree
• Each subtree is itself a binary search tree
• Inorder traversal produces an ordered list

[email protected] 200
 Binary Search Tree Algorithms
• Find smallest value
• Find largest value
• Searching
• Inserting a Node
• Deleting a Node

[email protected] 201
 Finding the smallest value
• Start at the root and keep moving left until a node that has no left child is
reached
• the minimum value is in the last left node in the left sub-tree of the root.

int Minimum(node* root){

node *s = root;
while (s->left != NULL)
s = s->left;
return s->data;
}

[email protected] 202
 Finding the largest value
• Start at the root and keep moving right until a node that has no right child is
reached
• the maximum value is in the last right node in the right sub-tree of the root.

int Maximum(node* root) {

node *s = root;
while (s->right != NULL)
s = s->right;
return s->data;
}

[email protected] 203
 Searching
• The search algorithm visits at most one node in each level of the
binary search tree
• the algorithm runs in 𝑂(ℎ) time, where ℎ is the height of the tree.
• If the tree is balanced, then ℎ = log 𝑛

[email protected] 204
 Search for the value 90
1. Compare 90 with 50, since 90 is greater than 50 then go right
2. Compare 90 with 85, since 90 is greater than 85 then go right
3. Compare 90 with 100, since 90 is less than 100 then go left
4. Compare 90 with 95, since 90 is less than 95 then go left
5. Compare 90 with 90, item found

[email protected] 205
 void search(int val, node* root){
node *s = root; //start search at root
int flag=1;
while ( (s->data != val) && (flag) ){ //examine current data
if(val < s->data)
s = s->left; //go to left child
else
s = s->right; //go to right child
if(s == NULL)
flag=0; // item not found, finish searching
}
if (flag)
cout<<"found!";
else
cout<<"not found";
}

[email protected] 206
 Insertion
• A new node is always inserted as a leaf
• The operation of inserting a new node proceeds in the same sequence as the
search operation, until it encounters a "NULL", where the new node is inserted
and connected to the previous node

[email protected] 207
 Insert the value 55
1. Compare 55 with 50, since 55 is greater than 50 then go right
2. Compare 55 with 85, since 55 is smaller than 85 then go left
3. Compare 55 with 65, since 55 is less than 65 then go left
4. A NULL is reached, then insert 55 to the left of 65

[email protected] 208
 void insert(int val, node* root) {
node *n,*parent,*s;
n = new node; n->data = val; n->left = NULL; n->right = NULL; //create a new node;
s = root; //start search at root
int flag=1;
while(flag){ //tree traversal
parent = s; // parent points to the parent of the node to be inserted

if(val < s->data){ //go to left child

s = s->left;
if(s == NULL){ //if null, insert new node to the left of parent, then end
parent->left = n;
flag=0; }
}

else { //go to right child

s = s->right;
if(s == NULL){ //if null, insert new node to the right of parent, then end
parent->right = n;
flag=0; }
}
} //end of while
} //end of function
[email protected] 209
 Deleting a Node
• Three cases:
1. Delete a leaf node (node that has no children)
2. Deleting a node that has only one child
3. Deleting a node that has two children

[email protected] 210
 Deleting a leaf node
• Make the parent of the node to be deleted point to null, then delete the node

Deleting node 98

[email protected] 211
 Deleting a node with only one child
1. Make the parent of the node (to be deleted) point to its child
2. then delete the node
• The child along with its subtrees takes the place of the deleted node

Deleting node 90

[email protected] 212
 Deleting a node that has two children
1. Find the inorder successor of the node (most left node in the in right subtree)
• The inorder successor is the smallest value in the right subtree
2. Replace the value of the node to be deleted with the value of the inorder successor.
3. Delete the inorder successor (it may be a leaf node, or it may have only a right child)

Deleting node 85

[email protected] 213
void delete (node *root, int key) {
node *current=root, *parent=NULL;

while((current->data != key) && (current != NULL)) {

parent=current;
if ( key < current->data ) current = current->left;
else current = current->right;
} // current points to node to be deleted and parent point to its parent

// if current is equal to NULL then node does not exist

if (current == NULL){ cout<<"element doesn't exist"<<endl; return; }

if ((current->left == NULL) || (current->right == NULL)) { //leaf node or node has only one child
if (parent->left->data == key) { // current is on the left of parent
if (current->right != NULL)
parent->left = current->right;
else
parent->left = current->left; parent
} else { // current is on the right of parent
if (current->right != NULL) current
parent->right = current->right;
else
parent->right = current->left;
}
delete current;
}
[email protected] 214
 if ((current->left != NULL) && (current->right != NULL)){ //node has two Childs
// find the inorder successor of the node and its parent node
node *successor = current->right, *pn;
while(successor->left != NULL) {
pn = successor;
successor = successor->left;
} // successor points to most left node (smallest node) in the right subtree
// pn points to successor parent
parent
//replace data of the node to be deleted with data the successor
current->data = successor->data; current

//delete successor given that it is on the left of pn and

// it doesn't have a left subtree
if (successor->right == NULL)
pn->left = NULL;
else
pn->left = successor->right;
delete successor;
}
}

[email protected] 215