Basic Data Structures

September 29, 2016

CMPE 250 Basic Data Structures September 29, 2016 1 / 37

What are programs made of?

Programs= Data Structures + Algorithms

CMPE 250 Basic Data Structures September 29, 2016 2 / 37

Data Abstraction

Separation of a data type’s logical properties from its implementation.

Logical Properties
What are the possible values?
What operations will be needed?
Implementation
How can this be done in C++?
How can data types be used?

CMPE 250 Basic Data Structures September 29, 2016 3 / 37

Abstract Data Type (ADT)

a data type that does not describe or belong to any specific data, yet
allows the specification of organization and manipulation of data
a data type whose properties (domain and operations) are specified
independently of any particular implementation
a data type that specifies and can share its logical properties without
giving specifics of the implementation code
a way of thinking about data types, often outside the constraints of a
programming language
actual data type is added later in an implementation

CMPE 250 Basic Data Structures September 29, 2016 4 / 37

Four Basic Kinds of ADT Operations

Constructor – creates a new instance (object) of an ADT.

Transformer – changes the state of one or more of the data values of
an instance.
Observer – allows us to observe the state of one or more of the data
values without changing them.
Iterator – allows us to process all the components in a data structure
sequentially.

CMPE 250 Basic Data Structures September 29, 2016 5 / 37

What is a Stack?

Logical level: A stack is an ordered group of homogeneous items

(elements), in which the removal and addition of stack items can take
place only at the top of the stack.
A stack is a LIFO "last in, first out" structure.

CMPE 250 Basic Data Structures September 29, 2016 6 / 37

Stack Operations

MakeEmpty – Sets stack to an empty state.

IsEmpty – Determines whether the stack is currently empty.
IsFull – Determines whether the stack is currently full.
Push (ItemType newItem) – Throws exception if stack is full;
otherwise adds newItem to the top of the stack.
Pop – Throws exception if stack is empty; otherwise removes the item
at the top of the stack.
ItemType Top – Throws exception if stack is empty; otherwise returns
a copy of the top item

CMPE 250 Basic Data Structures September 29, 2016 7 / 37

Class specification for Stack

// File StackType.h

class FullStack // Exception class thrown by

// Push when stack is full
{};
class EmptyStack // Exception class thrown by
// Pop and Top when stack is empty
{};

#include "ItemType.h"

class StackType
{
public:

StackType( );
// Class constructor.
bool IsFull () const;
// Function: Determines whether the stack is full.
// Pre: Stack has been initialized
// Post: Function value = (stack is full)

CMPE 250 Basic Data Structures September 29, 2016 8 / 37

Class specification for Stack (Cont.)

bool IsEmpty() const;

// Function: Determines whether the stack is empty.
// Pre: Stack has been initialized.
// Post: Function value = (stack is empty)
void Push( ItemType newItem );
// Function: Adds newItem to the top of the stack.
// Pre: Stack has been initialized.
// Post: If (stack is full), FullStack exception is thrown;
// otherwise, newItem is at the top of the stack.
void Pop();
// Function: Removes top item from the stack.
// Pre: Stack has been initialized.
// Post: If (stack is empty), EmptyStack exception is thrown;
// otherwise, top element has been removed from stack.
ItemType Top();
// Function: Returns a copy of top item on the stack.
// Pre: Stack has been initialized.
// Post: If (stack is empty), EmptyStack exception is thrown;
// otherwise, returns a copy of top element.
private:
int top;
ItemType items[MAX_ITEMS];
};

CMPE 250 Basic Data Structures September 29, 2016 9 / 37

Stack Implementation

// File: StackType.cpp

#include "StackType.h"
#include <iostream>
StackType::StackType( )
{
top = -1;
}
bool StackType::IsEmpty() const
{
return(top = = -1);
}

bool StackType::IsFull() const

{
return (top = = MAX_ITEMS-1);
}

CMPE 250 Basic Data Structures September 29, 2016 10 / 37

Stack Implementation (Cont.)

void StackType::Push(ItemType newItem)

{
if( IsFull() )
throw FullStack():
top++;
items[top] = newItem;
}

void StackType::Pop()
{
if( IsEmpty() )
throw EmptyStack();
top--;
}

ItemType StackType::Top()
{
if (IsEmpty())
throw EmptyStack();
return items[top];
}

CMPE 250 Basic Data Structures September 29, 2016 11 / 37

Sample Stack Code

char letter = ’V’;

StackType charStack;

charStack.Push(letter);

charStack.Push(’C’);

charStack.Push(’S’);

charStack.Pop();

charStack.Push(’K’);

while (!charStack.IsEmpty())
{
letter = charStack.Top();
charStack.Pop()
}

CMPE 250 Basic Data Structures September 29, 2016 12 / 37

What is a Queue?

Logical (or ADT) level: A queue is an ordered group of homogeneous

items (elements), in which new elements are added at one end (the
rear), and elements are removed from the other end (the front).
A queue is a FIFO "first in, first out" structure.

CMPE 250 Basic Data Structures September 29, 2016 13 / 37

Queue Operations

MakeEmpty – Sets queue to an empty state.

IsEmpty – Determines whether the queue is currently empty.
IsFull – Determines whether the queue is currently full.
Enqueue (ItemType newItem) – Adds newItem to the rear of the
queue.
Dequeue (ItemType& item) – Removes the item at the front of the
queue and returns it in item.

CMPE 250 Basic Data Structures September 29, 2016 14 / 37

Class specification for Queue

// Header file for Queue ADT.

class FullQueue
{};

class EmptyQueue
{};

struct NodeType;

#include "ItemType.h"

class QueType
{
public:
QueType();
// Class constructor.
// Because there is a default constructor, the precondition
// that the queue has been initialized is omitted.
QueType(int max);
// Parameterized class constructor.
~QueType();
// Class destructor.
void MakeEmpty();
// Function: Initializes the queue to an empty state.
// Post: Queue is empty.

CMPE 250 Basic Data Structures September 29, 2016 15 / 37

Class specification for Queue

bool IsEmpty() const;

// Function: Determines whether the queue is empty.
// Post: Function value = (queue is empty)
bool IsFull() const;
// Function: Determines whether the queue is full.
// Post: Function value = (queue is full)
void Enqueue(ItemType newItem);
// Function: Adds newItem to the rear of the queue.
// Post: If (queue is full) FullQueue exception is thrown
// else newItem is at rear of queue.
void Dequeue(ItemType& item);
// Function: Removes front item from the queue and returns it in item.
// Post: If (queue is empty) EmptyQueue exception is thrown
// and item is undefined
// else front element has been removed from queue and
// item is a copy of removed element.
private:
NodeType* front;
NodeType* rear;
};

struct NodeType {
ItemType info;
NodeType* next;
};

CMPE 250 Basic Data Structures September 29, 2016 16 / 37

Queue Implementation

QueType::QueType() // Class constructor.

// Post: front and rear are set to NULL.
{
front = NULL;
rear = NULL;
}

void QueType::MakeEmpty()
// Post: Queue is empty; all elements have been deallocated.
{
NodeType* tempPtr;

while (front != NULL)

{
tempPtr = front;
front = front->next;
delete tempPtr;
}
rear = NULL;
}

// Class destructor.
QueType::~QueType()
{
MakeEmpty();
}

CMPE 250 Basic Data Structures September 29, 2016 17 / 37

Queue Implementation (Cont.)
bool QueType::IsFull() const
{
NodeType* location;
try
{
location = new NodeType;
delete location;
return false;
}
catch(bad_alloc exception)
{
return true;
}
}

bool QueType::IsEmpty() const

{
return (front == NULL);
}

void QueType::Enqueue(ItemType newItem)

{
if (IsFull())
throw FullQueue();
else
{
NodeType* newNode;

newNode = new NodeType;

newNode->info = newItem;
newNode->next = NULL;
if (rear == NULL)
front = newNode;
else
rear->next = newNode;
rear = newNode;
}
}

CMPE 250 Basic Data Structures September 29, 2016 18 / 37

Queue Implementation (Cont.)

void QueType::Dequeue(ItemType& item)

// Removes front item from the queue and returns it in item.
// Pre: Queue has been initialized and is not empty.
// Post: If (queue is not empty) the front of the queue has been
// removed and a copy returned in item;
// othersiwe a EmptyQueue exception has been thrown.
{
if (IsEmpty())
throw EmptyQueue();
else
{
NodeType* tempPtr;

tempPtr = front;
item = front->info;
front = front->next;
if (front == NULL)
rear = NULL;
delete tempPtr;
}
}

CMPE 250 Basic Data Structures September 29, 2016 19 / 37

Sample Queue Code
/ Test driver
#include <iostream>
#include "QueType.h"
using namespace std;

int main()
{

ifstream inFile; // file containing operations

ofstream outFile; // file containing output
string inFileName; // input file external name
string outFileName; // output file external name
string outputLabel;
string command; // operation to be executed

ItemType item;
QueType queue;
int numCommands;

// Prompt for file names, read file names, and prepare files
cout << "Enter name of input command file; press return." << endl;
cin >> inFileName;
inFile.open(inFileName.c_str());

cout << "Enter name of output file; press return." << endl;
cin >> outFileName;
outFile.open(outFileName.c_str());

cout << "Enter name of test run; press return." << endl;
cin >> outputLabel;
outFile << outputLabel << endl;

inFile >> command;

CMPE 250 Basic Data Structures September 29, 2016 20 / 37

Sample Queue Code
numCommands = 0;
while (command != "Quit")
{
try
{
if (command == "Enqueue")
{
inFile >> item;
queue.Enqueue(item);
outFile << item << " is enqueued." << endl;
}
else if (command == "Dequeue")
{
queue.Dequeue(item);
outFile<< item << " is dequeued. " << endl;
}
else if (command == "IsEmpty")
if (queue.IsEmpty())
outFile << "Queue is empty." << endl;
else
outFile << "Queue is not empty." << endl;

else if (command == "IsFull")

if (queue.IsFull())
outFile << "Queue is full." << endl;
else outFile << "Queue is not full." << endl;
}
catch (FullQueue)
{
outFile << "FullQueue exception thrown." << endl;
}

catch (EmptyQueue)
{
outFile << "EmtpyQueue exception thrown." << endl;
}
numCommands++;
cout << " Command number " << numCommands << " completed."
<< endl;
inFile >> command;

};

cout << "Testing completed." << endl;

inFile.close();
outFile.close();
return 0;
}

CMPE 250 Basic Data Structures September 29, 2016 21 / 37

Tree

A tree is a finite set of one or more nodes such that:

There is a specially designated node called the root.
The remaining nodes are partitioned into n ≥ 0 disjoint sets T1 , ..., Tn ,
where each of these sets is a tree.
We call T1 , ..., Tn the subtrees of the root.

CMPE 250 Basic Data Structures September 29, 2016 22 / 37

Terminology

The degree of a node is the number of subtrees of the node

The node with degree 0 is a leaf or terminal node.
A node that has subtrees is the parent of the roots of the subtrees.
The roots of these subtrees are the children of the node.
Children of the same parent are siblings.
The ancestors of a node are all the nodes along the path from the
root to the node.

CMPE 250 Basic Data Structures September 29, 2016 23 / 37

Tree Notation

Root

Leaf Node

Node Leaf

Leaf Leaf Leaf

CMPE 250 Basic Data Structures September 29, 2016 24 / 37

Binary Tree

A binary tree is a structure in which:

Each node can have at most two children, and in which a unique path
exists from the root to every other node.
The two children of a node are called the left child and the right child,if
they exist.

CMPE 250 Basic Data Structures September 29, 2016 25 / 37

Binary Tree Example

B C

D E

F G

CMPE 250 Basic Data Structures September 29, 2016 26 / 37

Linked Representation

typedef struct node *tree_pointer;

typedef struct node {
int info;
tree_pointer left_child, right_child;
};

CMPE 250 Basic Data Structures September 29, 2016 27 / 37

Binary Search Tree

A special kind of binary tree in which:

Each node contains a distinct data value,
The key values in the tree can be compared using "greater than" and
"less than", and
The key value of each node in the tree is less than every key value in
its right subtree, and greater than every key value in its left subtree

CMPE 250 Basic Data Structures September 29, 2016 28 / 37

Binary Search Tree Example

50

40 70

60 80

55 65

CMPE 250 Basic Data Structures September 29, 2016 29 / 37

Insertion into a Binary Search Tree

void Insert(TreeNode*& tree, ItemType item)

{
if (tree == NULL)
{// Insertion place found.
tree = new TreeNode;
tree->right = NULL;
tree->left = NULL;
tree->info = item;
}
else if (item < tree->info)
Insert(tree->left, item);
else
Insert(tree->right, item);
}

CMPE 250 Basic Data Structures September 29, 2016 30 / 37

Binary Search Tree Insertion Example

CMPE 250 Basic Data Structures September 29, 2016 31 / 37

Deleting a Leaf Node

CMPE 250 Basic Data Structures September 29, 2016 32 / 37

Deleting a Node with One Child

CMPE 250 Basic Data Structures September 29, 2016 33 / 37

Deleting a Node with Two Children

CMPE 250 Basic Data Structures September 29, 2016 34 / 37

Delete

void Delete(TreeNode*& tree, ItemType item)

{
if (item < tree->info)
Delete(tree->left, item);
else if (item > tree->info)
Delete(tree->right, item);
else
DeleteNode(tree); // Node found
}

CMPE 250 Basic Data Structures September 29, 2016 35 / 37

DeleteNode

void DeleteNode(TreeNode*& tree)

{
ItemType data;
TreeNode* tempPtr;
tempPtr = tree;
if (tree->left == NULL) {
tree = tree->right;
delete tempPtr; }
else if (tree->right == NULL){
tree = tree->left;
delete tempPtr;}
else
{
GetPredecessor(tree->left, data);
tree->info = data;
Delete(tree->left, data);
}
}

CMPE 250 Basic Data Structures September 29, 2016 36 / 37

Get Predecessor

void GetPredecessor(TreeNode* tree, ItemType& data)

{
while (tree->right != NULL)
tree = tree->right;
data = tree->info;
}

CMPE 250 Basic Data Structures September 29, 2016 37 / 37