DATA STRUCTURES LAB

BCSCCS308 /BITCIT308 /BICCIC 308

List of Exercises
1. Stack operations using arrays

2. Queue operations using arrays

3. Operations on SLL

4. Infix to Postfix conversion

5. Operations on DLL

6. Operations on Circular DLL

7. Operations on BST

8. General Tree to Binary Tree conversion

9. Operations on B-tree

10. Operations on Trie Structure

11. Heap and Merge Sort

12. Searching Techniques

13. BFS and DFS

14. Finding Minimum Weight Spanning Tree

Ex. No: 01 Stack Operations

1. Push:
Algorithm PUSH(S[0…N-1], TOP, X)
If TOP>=N-1 Then
Write(„STACK OVERFLOW‟)
Return
End If
TOP = TOP + 1
S[TOP] = X
Return
End PUSH

2. Pop

Function POP(S[0…N-1], TOP)

If TOP = -1 Then
Write(„STACK UNDERFLOW ON POP‟)
Return
End If
X = S[TOP]
TOP = TOP-1
Return(X)
End POP

3. Peek

Function PEEK(S[0…N-1], TOP)

If TOP= -1 Then
Write („STACK EMPTY‟)
Return
End If
Return(S[TOP])
End PEEK

4. Display
Algorithm DISPLAY(S[0…N-1], TOP)
If TOP = -1 Then
Write(„STACK IS EMPTY‟)
Return
End If
I = TOP
 Loop (I >= 0)
Write S[I]
I=I-1
End loop
Return
End DISPLAY

Pre Lab: Implementation knowledge on Arrays and Functions.

Ex. No: 02 Queue Operations

1. Enqueue

Procedure ENQUEUE(Q[0…N-1], F,R,N,Y)

If R>=N-1 Then
Write(„OVERFLOW‟)
Return
R=R+1
Q[R] = Y
If F = -1 Then
F=0
Return
End ENQUEUE

2. Dequeue

Function DEQUEUE(Q[0…N-1],F,R)
If F=-1 Then
Write(„UNDERFLOW‟)
Return(0);
Y = Q[F]
If F = R Then
F = R = -1
Else
F=F+1
Return(Y)
End DEQUEUE

3. Search

Function SEARCH(Q[0…N-1], F,R, X)

If F= -1 Then
 Write(„QUEUE IS EMPTY. No Such Element‟)
Return 0 //Unsuccessful Search
End If
I=F
Loop (I <= R)
If (Q[I] = X Then
Return I-F+1 //Successful Search
Else
I=I+1
End loop
Return 0 //Unsuccessful Search
End SEARCH

4. Display
Algorithm DISPLAY(Q[0…N-1], F,R)
If F= -1 Then
Write(„QUEUE IS EMPTY‟)
Return
End If
I=F
Loop (I <= R)
Write Q[I]
I=I+1
End loop
Return
End DISPLAY

Pre Lab: Implementation knowledge on Arrays and Functions.

Ex. No: 03 SLL Operations

1. Insert at Beginning
Algorithm insBeg(ref sList, val dataIn)
Allocate(newNode)
newNode->data = dataIn
newNode->link = sList
sList = newNode
End insBeg
2. Insert at End
Algorithm insEnd(ref sList, val dataIn)
If (sList null) then
Allocate(newNode)
newNode->data = dataIn
newNode->link = null
sList = newNode
Else
temp = sList
loop(temp->link is not null)
temp = temp->link
End loop
allocate(newNode)
newNode->data = dataIn
newNode->link = null
temp->link = newNode
End if
End insEnd

3. Insert after Specified Location

Alogrithm insAfter(ref sList, val Loc, val dataIn)
Temp = sList
I=1
Loop(I < Loc)
Temp = temp->link
If(temp=null) then
Write(„Invalid Location‟)
Return
End if
I= I+1
End loop
Allocate(newNode)
newNode->data = dataIn
newNode->link = temp->link
temp->link = newNode
return
End insAfter

4. Delete Node
Algorithm delNode(ref sList, val dataOut)
If sList->link = null AND sList->data = dataOut
sList = null
 end if
Temp = sList
Loop(temp not null)
If temp->data = dataOut then
If temp = sList then
sList = temp->link
else
P->link = temp->link
End if
Release(temp)
Return
Else
P = temp
Temp = temp->link
End if
End loop
Write(„Data not found‟)
Return
End delNode

5. Retrieve Data
Function getData(ref sList, val Loc)
Temp = sList
Cnt = 1
Loop(temp not null)
If Cnt = Loc then
Return(temp->data)
End if
Temp = temp->link
Cnt = Cnt + 1
End loop
Write(„Invalid Location‟)
Return(0)
End getData

6. Count Node
Function cntNode(ref sList)
Temp = sList
Cnt = 0
Loop(temp not null)
Temp = temp->link
Cnt = Cnt + 1
End loop
 Return(Cnt)
End getData

Ex. No: 04 Infix to Postfix Conversion

Priority for Operators:
Priority 3: ^
Priority 2: * and /
Priority 1: + and –
Priority 0: (

Algorithm:

Algorithm inToPostFix(val Exp)

Stack = createStack
Set postfix to null string
Looper = 1
Loop(Looper <= sizeof Exp)
Token = Exp[Looper]
If Token is open parenthesis then
pushStack(Stack, Token)
Else If Token is close parenthesis then
popStack(Stack, Token)
loop(Token not open paranthesis)
concatenate Token to postFix
popStack(Stack, Token)
End loop
Else If Token is Operator then
stack Top(Stack, topToken)
loop( not emptyStack(Stack) AND
Priority(token) <= Priority(topToken) )
popStack (Stack, tokenOut)
concatenate tokenOut to postFix
stackTop (Stack, topToken)
End loop
PushStack (Stack, Token)
Else
Concatenate Token to postfix
End if
Looper = Looper + 1
End loop
Loop (not emptyStack(Stack))
popStack (Stack, Token)
concatenate Token to postFix
 End loop
DestroyStack (Stack)
Return postFix
End inToPostFix

Ex. No: 05 Operations on DLL

1. Insert at Beginning
Algorithm insBeg(ref sList, val dataIn)
Allocate(newNode)
newNode->data = dataIn
newNode->pLink = null
newNode->sLink = sList
sList->pLink = newNode
sList = newNode
End insBeg

2. Insert at End
Algorithm insEnd(ref sList, val dataIn)
If (sList null) then
Allocate(newNode)
newNode->data = dataIn
newNode->pLink = null
newNode->sLink = null
sList = newNode
Else
temp = sList
loop(temp->sLink is not null)
temp = temp->sLink
end loop
allocate(newNode)
newNode->data = dataIn
newNode->sLink = null
newNode->pLink = temp
temp->sLink = newNode
End if
End insEnd

3. Insert after Specified Location

Alogrithm insAfter(ref sList, val Loc, val dataIn)
Temp = sList
 I=1
Loop(I < Loc)
Temp = temp->sLink
If(temp=null) then
Write(„Invalid Location‟)
Return
End if
I= I+1
End loop
Allocate(newNode)
newNode->data = dataIn
newNode->pLink = temp
newNode->sLink = temp->sLink
temp->sLink->pLink = newNode
temp->sLink = newNode
return
End insAfter

4. Delete Node
Algorithm delNode(ref sList, val dataOut)
If sList->sLink = null AND sList->data = dataOut
sList = null
end if

Temp = sList
Loop(temp not null)
If temp->data = dataOut then
If temp = sList then
sList = temp->sLink
sList->pLink = null
else
if temp->sLink = null then
temp->pLink->sLink = null
else
temp->pLink->sLink = temp->sLink
temp->sLink->plink = temp->pLink
end if
end if
release(temp)
return
end if
temp = temp->sLink
End loop
Write(„Data not found‟)
Return
 End delNode

5. Retrieve Data
Function getData(ref sList, val Loc)
Temp = sList
Cnt = 1
Loop(temp not null)
If Cnt = Loc then
Return(temp->data)
End if
Temp = temp->sLink
Cnt = Cnt + 1
End loop
Write(„Invalid Location‟)
Return(0)
End getData

6. Count Node
Function cntNode(ref sList)
Temp = sList
Cnt = 0
Loop(temp not null)
Temp = temp->sLink
Cnt = Cnt + 1
End loop
Return(Cnt)
End getData

Ex. No: 06 Operations on CDLL

1. Insert at Beginning
Algorithm insBeg(ref sList, val dataIn)
Allocate(newNode)
newNode->data = dataIn
newNode->pLink = sList->pLink
newNode->sLink = sList
sList->pLink->sLink = newNode
sList->pLink = newNode
 sList = newNode
End insBeg

2. Insert at End
Algorithm insEnd(ref sList, val dataIn)
If (sList null) then
Allocate(newNode)
newNode->data = dataIn
newNode->pLink = newNode
newNode->sLink = newNode
sList = newNode
else
temp = sList->pLink
allocate(newNode)
newNode->data = dataIn
newNode->pLink = temp
newNode->sLink = sList
sList->pLink = newNode
temp->sLink = newNode
end if
End insEnd

3. Insert after Specified Location

Alogrithm insAfter(ref sList, val Loc, val dataIn)
Temp = sList
I=1
Loop(I < Loc)
Temp = temp->sLink
If(temp=sList) then
Write(„Invalid Location‟)
Return
End if
I= I+1
End loop
Allocate(newNode)
newNode->data = dataIn
newNode->pLink = temp
newNode->sLink = temp->sLink
temp->sLink->pLink = newNode
temp->sLink = newNode
return
End insAfter
4. Delete Node

Algorithm delNode(ref sList, val dataOut)

If sList->sLink = sList AND sList->data = dataOut
sList = null
end if

Temp = sList
Loop(temp not null)
If temp->data = dataOut then
If temp = sList then
sList = temp->sLink
sList->pLink = temp->pLink
temp->pLink->sLink = sList
else
temp->pLink->sLink = temp->sLink
temp->sLink->pLink = temp->pLink
end if
release(temp)
return
end if
temp = temp->sLink
if temp=sList then
break loop
end if
End loop
Write(„Data not found‟)
Return
End delNode

5. Retrieve Data

Function getData(ref sList, val Loc)

Temp = sList
Cnt = 1
Loop(temp not null)
If Cnt = Loc then
Return(temp->data)
End if
Temp = temp->sLink
If temp = sList then
Break loop
End if
Cnt = Cnt + 1
 End loop
Write(„Invalid Location‟)
Return(0)
End getData

6. Count Node

Function cntNode(ref sList)

Temp = sList
Cnt = 0
Loop(temp not null)
Temp = temp->sLink
Cnt = Cnt + 1
If temp = sList then
Break loop
End if
End loop
Return(Cnt)
End getData

Ex. No: 07 BST Operations

1. Insertion
Algorithm insertBST(ref Root, val newNode)
If Root is null
Root = newNode
Else
pWalk = Root
loop(pWalk not null)
parent = pWalk
If newNode->key < pWalk->key then
pWalk = pWalk->left
Else
pWalk = pWalk->right
End if
End loop
If newNode->key < parent->key)
parent->left = newNode
Else
parent->right = newNode
End if
End if
 Return
End insertBST

2. Deletion
Algorithm deleteBST(ref Root, val dltKey)
If Root = null then
Return false
If dltKey < Root->data.key then
Return deleteBST(Root->left, dltKey)
Else If dltKey > Root->data.key then
Return deleteBST(Root->right,dltKey)
Else
If Root->left = null then
dltPtr = Root
Root = Root->right
Release(dltPtr)
Return true
Else If Root->right = null then
dltPtr = Root
Root = Root->left
Release(dltPtr)
Return true
Else
DltPtr = Root->left
loop(dltPtr->right not null)
DltPtr = dltPtr->right
End loop
Root->data = dltPtr->data
Return deleteBST(Root->left, dltPtr->data.key)
End if
End if
End deleteBST

3. Traversal
Algorithm preOrder (val Root)
If Root=null then
Process(Root)
preOrder(Root->leftSubtree)
preOrder(Root->rightSubtree)
End if
Return
End preOrder
Algorithm inOrder (val Root)
If Root=null then
inOrder(Root->leftSubtree)
Process(Root)
inOrder(Root->rightSubtree)
End if
Return
End inOrder

Algorithm postOrder (val Root)

If Root=null then
postOrder(Root->leftSubtree)
postOrder(Root->rightSubtree)
Process(Root)
End if
Return
End postOrder

Ex. No: 08 General Tree to Binary

The input to the algorithm should be given in the preorder traversal of the general
tree. It consists of the level number of the node (LEVEL) and data stored in the node
(NAME). After conversion, HEAD‟s left subtree points to root node of the converted
binary tree. The algorithm uses Stack S to store Level Number and Location of the node.
The local variable PRED has two fields PRED_LEVEL and PRED_LOC. Display
Preorder, Inorder and Postorder traversal of the converted binary tree as output.

Algorithm CONVERT

1. HEAD = newNode
HEADleftSubTree = null
HEADrightSunTree = HEAD
TOP=0
PUSH(S[1..N],TOP,LEV,LOC)
2. Loop thru step 7 while there exists input
3. Read LEVEL and NAME
4. Allocate(newNode)
newNodeleftSubTree = newNoderightSubTree = null
newNodedata = NAME
 5. PRED = PEEK(S[1..N], TOP)
6. If LEVEL > PRED_LEVEL Then
PRED_LOCleftSubTree = newNode
Else
Loop (PRED_LEVEL > LEVEL)
POP(S[1..N],TOP)
PRED = PEEK(S[1..N], TOP)
End loop
If PRED_LEVEL < LEVEL Then
Write („Error in input‟. Mixed Level Numbers‟)
Return
End if
PRED_LOCrightSubTree = newNode
POP(S[1..N], TOP)
7. PUSH(S[1..N], TOP, LEVEL, newNode)
8. Return

Given the following general tree:

B C D

K H I J E F

G
The input for the above general tree should be given as follows:
1, A
2, B
3, K
2, C
3, H
3, I
3, J
2, D
3, E
3, F
4, G

The following is the converted binary tree:

HEAD

K C

H D

I E

J F

G
Ex. No: 09 B-Tree Operations
Algorithm BTreeInsert(tree,data)

1. if(tree = null)
2. create new node
3. set left subtree of node to null
4. move data to first entry in new node
5. set subtree of first entry to null
6. set tree root to address of new node
7. set number of entries to 1
8. end if
9. insertNode(tree, data, upEntry)
10. if(tree higher)
11. create new node
12. move upEntry to first entry in new node
13. set left subtree of node to tree
14. set tree root to new node
15. set number of entries to 1
16. end if
17. Return

Algorithm BTreeDelete(tree,dltKey)

1. if(tree empty)
2. return false
3. end if
4. delete(tree, dltKey,success)
5. if(success)
6. if(tree number of entries zero)
7. set tree to left subtree
8. end if
9. end if
10. return success
Ex. No: 10 Trie Structure Operations
Structure of node:

DATA LINK [1] LINK [2] LINK [3] …. LINK [n]

1. Insertion

Algorithm Insert(Head, Word)

1. Temp = Head
2. I = 1
3. N = Length(Word)
4. Loop (I <=N)
5. idx = Index corresponding to Word[I]
6. If Temp->Link [idx] not Null Then
7. Temp = TempLink[idx]
8. Else
9. Allocate(newNode)
10. newNodeData = “-“
11. Initialize all Link fields of newNode to Null
12. TempLink[idx] = newNode
13. Temp = newNode
14. EndIf
15. I=I+1
16. End Loop
17. TempData = Word
18. Return

2. Deletion

Algorithm Delete(Head, Word)

1. Prev = Null
2. Temp = Head
3. I = 1
4. N = Length(Word)
5. Loop (I <=N)
6. idx = Index corresponding to Word[I]
7. If Temp->Link [idx] not Null Then
8. Prev = Temp
9. Temp = TempLink[idx]
10. Else
11. Write “Word is not available in the dictionary”
 12. Return
13. EndIf
14. I=I+1
15. End Loop
16. If Temp not Null then
17. TempData = “-“
18. If all Link fields of Temp are Null Then
19. PrevLink[idx] = Null
20. EndIf
21. Else
22. Write “Word is not available in the dictionary”
23. Return
24. EndIf
25. Return

3. Searching

Algorithm Search(Head, Word)

1. Temp = Head
2. I = 1
3. N = Length(Word)
4. Loop (I <=N)
5. idx = Index corresponding to Word[I]
6. If Temp->Link [idx] not Null Then
7. Prev = Temp
8. Temp = TempLink[idx]
9. Else
10. Write “Word is not available in the dictionary”
11. Return
12. EndIf
13. I=I+1
14. End Loop
15. If TempData is not “-“
16. Write “Word is present in the dictionary”
17. Return Word
18. Else
19. Write “Word is not available in the dictionary”
20. EndIf
21. Return

4. Display

Algorithm Display(Node)

1. If Node not Null

 2. If NodeData is not “-“
3. Write NodeData
4. EndIf
5. I=1
6. Loop (I<= n) //n is the number of Link fields
7. Display(Node->Link [I])
8. I=I+1
9. End Loop
10. EndIf
11. Return

Ex. No: 11 Sorting Techniques

1. Heap Sort
Procedure Heapify(ref K, val N)
Heapsize[K] = N
I=N/2
Loop(I >= 1)
Call Adjust(K,I)
I=I-1
End loop
Return
End Heapify

Procedure Adjust(ref K, val I)

Left = 2*I
Right = 2*I+1
If Left<=Heapsize[K] AND K[Left]>K[I] then
Largest = Left
Else
Largest = I
End if
If Right<=Heapsize[K] AND K[Largest]<K[Right] then
Largest = Right
End if
If Largest <> I then
Swap K[I] and K[Largest]
Call Adjust(K,largest)
End if
Return
End Adjust

Procedure HeapSort(ref K, val N)

Call Heapify(K,N)
 Q=N
Loop(Q>=2)
Swap K[1] and K[Q]
Heapsize[K] = Heapsize[K] – 1
Q=Q-1
Call Adjust(K,1)
End loop
Return
End HeapSort

2. Merge Sort
Procedure MergeSort(ref K, val low, val high)
If low<high then
Mid = (low+high) / 2
Call MergeSort(K, low, mid)
Call MergeSort(K, mid+1, high)
Call Merge(K, low, mid, high)
End if
Return
End MergeSort

Procedure Merge(ref K, val low, val mid, val high)

I = low
J = mid + 1
H = low
Loop(I<=mid AND J<=high)
If K[I]<=K[J] then
Temp[H] = K[I]
I=I+1
Else
Temp[H] = K[J]
J=J+1
End if
H=H+1
End loop
If I>mid then
Loop(J<=high)
Temp[H] = K[J]
J=J+1
H=H+1
End loop
Else
Loop(I<=mid)
Temp[H] = K[I]
I=I+1
 H=H+1
End loop
End if
I = low
Loop(I<=high)
K[I] = Temp[I]
End loop
Return
End Merge

Ex. No: 12 Searching Techniques

1. Linear Search
Function LinearSearch(val K, val N, val X)
I=1
Loop(I<=N)
If K[I]=X then
Return(I)
End if
I = I+1
End loop
Return(0)
End LinearSearch

2. Binary Search

2.1 Binary Search Iterative

Function BinarySearch_I(val K, val N, val X)
Low = 1
High = N
Loop(Low<=High)
Mid = (Low + High) / 2
If X<K[Mid] then
High = Mid – 1
Else
If X >K[Mid] then
Low = Mid + 1
Else
Return(Mid)
End if
End if
End loop
 Return(0)
End BinarySearch_I

2.2. Binary Search Recursive

Function BinarySearch_R(val K, val P, val Q, val X)
If P > Q then
Loc = 0
Else
Mid = (P + Q) / 2
If X < K[Mid] then
Loc = BinarySearch_R(K, P, Mid-1, X)
Else
If X > K[Mid] then
Loc = BinarySearch_R(K, Mid+1, Q, X)
Else
Loc = Mid
End if
End if
End if
Return(Loc)
End BinarySearch_R

3. Hash Search
Division method for h( k )
h(k) = k mod m
Example:
If m = 20 and k = 91
h(91) = 91 mod 20 = 11

Algorithm Insert(Table, key)

1. h = key mod m
2. Allocate(newNode)
3. newNodeData = key
4. newNodeLink = Table[h]
5. Table[h] = newNode
6. Return

Algorithm Search(Table, key)

1. h = key mod m
2. If Table[h] is Null
3. Write “Element is not present in the Table”
4. Return
5. Else
6. Temp = Table[h]
7. loc = 1
8. Loop Temp is not Null
9. If TempData = key Then
10. Write “Element is present at position”, loc, “in list”, h
11. Return (loc)
12. Else
13. loc = loc + 1
14. Temp = TempLink
15. EndIf
16. End Loop
17. Write “Element is not present in the Table”
18. Return (0)

Algorithm Display(Table)

1. h = 0
2. Loop h <=size(Table)
3. Temp = Table[h]
4. Loop Temp is not Null
5. Write TempData
6. Temp = TempLink
7. End Loop
8. h = h+1
9. End Loop
10. Return

Ex. No: 13 BFS & DFS

Represent the graph using adjacency list or adjacency matrix

Algorithm breadthFirst(graph)

1. If(empty graph)
2. return
3. End if
4. createQueue(queue)
5. loop(through all vertices)
6. set vertex to not processed
7. end loop
8. loop(through all vertices)
9. if(vertex not processed)
 10. if(vertex not in queue)
11. enqueue(queue,walkPtr)
12. set vertex to enqueued
13. end if
14. loop(not emptyQueue(queue))
15. set vertex to dequeue(queue)
16. process(vertex)
17. set vertex to processed
18. loop(through adjacency list)
19. if (destination not enqueued or processed)
20. enqueue(queue,destination)
21. set destination to enqueued
22. end if
23. get next destination
24. end loop
25. end loop
26. end if
27. get next vertex
28. end loop
29. destroyQueue(queue)
30. Return

Depth-First Traversal
Algorithm depthFirst(graph)

1. if(empty graph)
2. return
3. EndIf
4. set walkPtr to graph first
5. loop (through all vertices)
6. set processed to 0
7. End loop
8. createStack(stack)
9. Loop(through vertex list)
10. If(vertex not processed and not in stack)
11. pushStack(stack,walkPtr)
12. set walkPtr processed to 1
13. End if
14. Loop(not emptyStack(stack))
 15. set vertex to popStack(stack)
16. process(vertex)
17. set vertex to processed
18. Loop(through arc list)
19. If(arc destination not in stack)
20. pushStack(stack,destination)
21. set destination to in stack
22. End if
23. get next destination
24. End loop
25. End loop
26. get next vertex
27. End loop
28. destroyStack(stack)
29. Return

Ex. No: 14 Minimum Weight Spanning Tree

Represent the graph as adjacency list or adjacency matrix. w(u,v) represents the weight
of the edge (u,v)

Algorithm Prim(G, w, r)

1. Loop for all v in G

2. d[v] = ∞
3. Parent[v] = nil
4. End loop
5. d[r] = 0
6. Q  V[G] // Q is a priority queue
7. Loop Q is not empty
8. u = Remove the node with lowest d value from the priority queue Q
9. Loop for each v adjacent to u
10. If v is in Q and w(u,v) < d[v] Then
11. Parent[v] = u
12. d[v] = w(u,v)
13. End if
14. End loop
15. End loop
16. Return

Additional Exercises
 Operations on circular Queue.
 Evaluation of postfix expression using stack.
 Operations on circular singly linked list.
 Ternary Search
 MST using Kruskal‟s algorithm
 Operations on AVL Tree.