Introduction
Program = Data structure + Algorithm
Data Structure :
Static ≡ 𝐴𝑟𝑟𝑎𝑦𝑠
Dynamic ≡ Pointers Memory ≡ Location - Memory Address
Data Structure
Static Data Structures :
Disadvantages of Static arrays :
o can be a waste of memory
o Can't add excess elements
Advantages :
Can iterate through array
Dynamic Data Structures :
Memory management is one of the main tasks of the operating system
Pseudocode : Through this course we will work with pseudocode
new(P1) //create a new location pointed by P1
C code :
int* P1;
*P1 = 30;
Q = P1;
*Q = 70
Free(P1)
Disadvantages of dynamic data structures :
You can't declare large numbers of variables easily
You can't get previous and next element
Solutions to the previous problems :
Linked List
Double linked list
Circular Double Linked List
Stack
Queue
Tree
Graph
Linked Lists
Initialize(list)
//create new empty linked list
list = Null
__________________
Add(list, x)
new(P)
P->data = x
P->Next = list
List = P
Searching Linked Lists :
Fig 3.1
Search(list, x, found)
P = list
While(P!=NULL) and (P->data != x)
P = P->Next
If(P==NULL)
Found = False
Else
Found = True
Deleting from Linked List:
Fig 3.2
Delete(list, x, Done)
q=p=list
While((p!=NULL) and (p->data != x))
q=p
p=P->Next
If(p==null)
Done = False
Else
Done = True
q->Next = p->Next
If(list==p)
List=list->Next
Free(p)
Double Linked List and Circular Double Linked List
Fig 3.3
Circular linked list is better than double
If you want to get last node you just move backwards from First node
Search Circular Double Linked List :
Search(CDList, x, found)
found = false
If(CDList != NULL)
P = CDlist
Do
If(P->Data == x)
found = true
Else
P = P->Next
While((P!= CDList) and (found ==false))
Stack
Fig 5.1
Input order : 20, 10, 50, 30
Output order : 30, 50, 10, 20
Last in first out(LIFO)
Uses of stack :
1. ALU(Arithmetic and Logic Unit)
2. Expression Evaluation
By converting infix notation to postfix notation, then putting the operands and operators on stack
Example : (a+b) / (c-d)
Postfix notation : ab+cd-/
3. Recursion
Fig 5.2 : Growing of Stack
Operations on Stack :
Initialize(S)
// create new empty stack S
S = NULL
Push(S, x)
New P
P->data = x
p->next = S
S=P
Fig 5.3 Push Operation
Pop(S, x, Empty)
If(S==NULL)
Empty = True
Else
{
Empty = False
X = S->data
P=S
S = S->Next
Free(P)
}
Fig 5.4 : Pop Operation
Implementing a search operation on a stack using the Stack interface :
Search(S, y, found)
Intialize(T)
Pop(S, x, Empty)
While(Empty==False and x!=y )
{
Push(T, x)
Pop(S,x, Empty)
}
If(Empty==True)
Found=Flase
Else
{
Found = True
Push(S, x)
}
//putting back the elements that were popped :
Pop(T,x, Empty)
While(Empty==False)
{
Push(S,x)
Pop(T,x, Empty)
}
Stack Serch(Modified by Fady) :
Search(Stack, y, found)
Intialize(TempStack)
Pop(Stack, x, Empty)
While(Empty==False and x!=y )
{
Push(TempStack, x)
Pop(Stack,x, Empty)
}
found = !Empty
If(!Empty)
Push(Stack, x)
//putting back the elements that were popped :
Pop(TempStack,x, Empty)
While(Empty==False)
{
Push(Stack,x)
Pop(TempStack ,x , Empty)
}
Queue
Input : 20, 50, 10, 30
Output : 20, 50, 10, 30
First In - First Out(FIFO)
Uses of Queue :
CPU Scheduling
Queue Simulation
o Flow Rate
o Waiting Time
o Average Waiting Time
o Queue Length
Queuing Theory
Operation Research
Multi Queue - Multi Server
Operations on Queue :
Initialize(Q)
H = T = NULL
Add(Q, X)
New(P)
P->data = X
P->Next = NULL
If(T==NULL)
H=T=P
Else
T->Next = P
T=P
Remove(Q, X, Empty)
If(H==NULL)
Empty = True
Else
Empty = False
X = H->data
P=H
H = H->Next
If(H==NULL)
T = NULL
Free(P)
Search(Q, Y, found)
Initialize(T) //Temporary Queue
Found = false
Remove(Q, X, Empty)
While(Empty==False)
{
If((X==Y)
Found = True
Add(T, X)
Remove(Q, X, Empty)
}
Remove(T, X, Empty)
While(Empty==False)
{
Add(Q, X)
Remove(T, X, Empty)
}
Trees
The previous binary tree can be redrawn simplified :
Binary Search Trees :
By adding the following Elements in order :
50, 10, 70, 15, 30, 55, 60, 90, 12, 100, 95, 25, 28, 50
The resulting binary search tree is :
Balanced Binary Trees :
A binary tree is balanced when the difference in height between it's left and right subtrees is not more than 1
Diff( height(left) - height(right) ) = ±1
Example of balanced binary search trees :
AVL Tree(Adelson-Velskii and Landis' tree, named after the inventors)
It is a self-balancing binary search tree
Tree Algorithms :
Search(Root, x, found)
{
P = Root
While((P!=NULL) and (P->data!=x))
{
If (x>P->data)
P = P->right;
else
p=p->left;
}
If(p==NULL)
Found=false;
Else
Found = true;
}
Add(root, x)
{
New(q);
q->data = x;
q->left = q->right = NULL;
If(root==NULL)
Root = q;
Else
{
P1=P2 = Root
While(P1!=NULL)
{
P2 = P1;
If (x>P1->data)
P1 = P1->right;
else
p1=p1->left;
}
If(x>p2->data)
P2->right = q;
Else
P2->left = q;
}
}
Tree Traversal :
Preorder(Root) Inorder(root) Postorder(root)
If(root!=NULL) If(root!=NULL) If(root!=NULL)
{ { {
Print(root->data) Inorder(root->left) Postorder(root->left)
Preorder(root->left) Print(root->data) Postorder(root->right)
Preorder(root->right) Inorder(root->right) Print(root->data)
} }
}
50, 10, 15, 12, 30, 25, 28, 50, 70, 10, 12, 15, 25, 28, 30, 50, 55, 60, 12, 28, 25, 50, 30, 15, 10, 60, 55, 95, 100, 70,
55, 70 50
60, 90, 100, 95 90, 95, 100
Advantages of search trees :
Search O(𝑙𝑜𝑔2 𝑛)
For example : finding an element a binary search tree of 1000,000 nodes can be done in no more than
𝑙𝑜𝑔2 1000000 = 20 steps !
Traversal like problems :
Example :
sum of all the elements of the tree
Count the nodes of the tree
Using Binary Trees to convert mathematical infix expression to postfix expression :
Consider the following mathematical expression :
𝑎+𝑏
𝑐 −𝑑
It's postfix Equivalent is :
𝑎𝑏 + 𝑐𝑑 −/
Can be obtained by using postorder traversal of the following tree :
Graphs
Note : in graph node label cannot be repeated
Graph Concepts :
Node
Node Label
1
a b
2 3
c d
Branch
(Edge)
4 5
Directed Graph
Undirected(Bidirectional) Graph
0
12
20
1 2
50
Weight
3 30
13
80
4 6
90
Complete Graph
5
Weighted Graph
Representation of Graphs :
The graph can be represented using :
Adjacency Matrix
Adjacency List
Sparse Matrix : In very large graphs it is inefficient to represent the whole matrix
It is more efficient to use sparse matrix instead
Note that Undirected(Bidirectional) graph is represented by a symmetric matrix
Notice that matrix Representation of Directed Graph is not symmetric
Note : In an undirected graph, half of the matrix is enough to represent the graph
Traversal of Graphs :
Consider the following graph :
Breadth First Search(BFS) : 1 → 2 → 3 → 5 → 4
Depth First Search(DFS) : 1 → 2 → 5 → 3 → 4
