Data Structures
Module 2
Terminologies
Data Types:
Refer to the different kinds of data that a variable
may hold in a programming languages
Examples:
Integer
Real
Float
Char
String
Data Objects:
Refer to the set of elements
Example: data object integer refers to
D = {0, ±1, ±2, ±3, … }
2 Module 2: Data Structures Saturday, February 15
, 2020
Terminologies cont…
Data Structures:
Describe the set of objects and how they are
related.
Describe the set of operations that can be
applied on the elements of a data object.
Typically this describe the more complex data
types such as arrays, stacks, queues, trees,
graphs and operations of how to manipulate
these.
3 Module 2: Data Structures Saturday, February 15
, 2020
Records
A structure that can have a number of
heterogeneous elements.
4 Module 2: Data Structures Saturday, February 15
, 2020
Records cont…
Field1, field2, field3 … fieldN can be of any
data type (i.e. integer, float, real, record).
To define a variable for the record:
RecordType A;
Assigning a value to a record field:
A.field1 = <value>;
A.field2 = <value>;
To retrieve a value from a record field:
printf(“%d”, A.field1);
printf(“%c”, A.field2);
printf(“%d:4:2”, A.field3);
5 Module 2: Data Structures Saturday, February 15
, 2020
Arrays
Consecutive set of memory locations is a
set of pairs – index and a value finite,
ordered set of homogeneous elements.
Forms:
one-dimensional array
n-dimensional array
6 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
2 data types
Base type of component type
Index type
Declaration
int A[10]; char B[45];
2 basic operations
Extraction
Storing
7 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
If an array is declared to be A[n], then:
n = number of elements
If an array is declared to be A[n][m], then
n*m = number of elements
if given n-dimensional array declaration
A[b][c][d]…[n] = Πb,c, … n
8 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
To determine the ith element of a Single-
dimension array:
A[i] = α + (i) * esize
Where:
α - base or starting address
i – element
esize – element size in bytes
Example: Determine the address of 5th
element of an integer array A with a
starting address of 2000.
9 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
To determine the ith element of a Two
dimension array:
A[i][j] = α + [(i)*(UB2)+(j)] * esize
Where:
UB2 – upper bound of the 2nd dimension
α - base or starting address
esize – element size in bytes
10 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
To determine the ith element of a Three
dimension array:
A[i][j][k]= α +[(i)*(UB2)*(UB3)+(j)*(UB3)+
(k)]*esize
Where:
UB3 – upper bound of the 3rd dimension
UB2 – upper bound of the 2nd dimension
α - base or starting address
esize – element size in bytes
11 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
Exercises:
Given A[10][3][3][6], α =2000, esize=4
bytes:
find the formula to represent an element in
a 4-dimensional array.
find the total number of elements
find the address of A[2][2][0][4]
Given X[8][3][6][2][3], α =3000, esize=3
bytes:
find the total number of elements
find the address of X[0][2][5][1][2]
12 Module 2: Data Structures Saturday, February 15
, 2020
Arrays cont…
Consider the following declaration:
typedef struct{
int A;
char B[10];
float C;
char D;
}rectype;
typedef rectype matrix[121][4][5];
matrix A1;
compute the address of element A1[120][3][3]
given the base address at 2000.
Assume that we do not know the size of RECTYPE
in number of bytes but we know that the address
of A1[20][2][3] is 2160. Give the size of RECTYPE in
bytes. Assume the base address is at 2000.
13 Module 2: Data Structures Saturday, February 15
, 2020
Stacks
Stack - linearly ordered set of elements
having the last-in, first-out (LIFO) discipline
An ordered list in which all insertions and
deletions are made at one end called the
TOP.
14 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Operations are done on top of the stack
only and we have no access to other
elements
Basic operations: push and pop
Representation: sequential or linked
15 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Operations
Insertion of new element onto the stack
(push)
Deletion of the top element from the stack
(pop)
Getting the size of stack
Checking for empty stack
Getting the top element without deleting it
from the stack
16 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Sequential Representation
Makes use of arrays
Stack is empty if top=-1 and full if top=n-1
Deletion from an empty stack causes an
underflow
Insertion onto a full stack causes an overflow
17 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
18 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
19 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
20 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Linked Representation
A linked list of stack nodes could be used to
implement a stack
21 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
22 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
23 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Evaluation of Expressions
Expression is made up of operands,
operators and delimiters.
Operands can be any legal variable names
or constants in programming languages.
Operations are described by operators:
Basic arithmetic operators: + - * /
Unary operators: - +
Relational operators: ==, >, <, >=, <=
24 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Our concern: how the expressions are
evaluated
The compiler accepts expressions and
produce correct result by reworking the
expressions into postfix form. Other forms
include infix and prefix.
Prefix : <Operator> <Operand1> <Operand2>
Postfix : <Operand1> <Operand2>
<Operator>
Infix : <Operand1> <Operator> <Operand2>
25 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Expression: A + B
Prefix : +AB
Postfix: AB+
Expression: (A+B*C)/D
Prefix : /+A*BCD
Postfix: ABC*+D/
26 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Conversion from Infix to Postfix using Stacks
In converting from infix to postfix, the following are the
rules:
1. The order of the operands in both forms is the same
whether or not parentheses are present in the infix
expression.
2. If the infix expression contains no parentheses, then the
order of the operators in the postfix expression is
according to their priority.
3. If the infix expression contains parenthesized sub
expressions, rule 2 applies for such sub expression.
27 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
And the following are the priority numbers:
icp(x) - priority number when token x is an
incoming symbol (incoming priority)
isp(x) - priority number when token x is in the
stack (in-stack priority)
28 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
The Algorithm:
1. Get the next token x.
2. If x is an operand, then output x
3. If x is the ( , then push x onto the stack.
4. If x is the ), then output stack elements until an ( is
encountered. Pop stack once more to delete the (.
If top = 0, the algorithm terminates.
5. If x is an operator, then while icp(x) <
isp(stack(top)), output stack elements; else, if
icp(x) > isp(stack(top)), then push x onto the stack.
6. Go to step 1.
29 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Convert a + ( b * c + d ) - f / g ^ h into its postfix
form using stack:
30 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Convert the following infix expressions to postfix
and prefix:
A+B*C/D
A/B^C+D*E-A*C
(A+B)*D+E/(F+A*D)+C
A+B*D^E^F^G/H^J*K-L
!(A&&!(B<C)||(C>D))||(C<E)
Convert the following prefix expressions to infix:
-+-^ABC*D^EFG
^+-ABC+D-EF
|| || &&ABC!<=EF
31 Module 2: Data Structures Saturday, February 15
, 2020
Stacks cont…
Convert the following postfix expressions to
infix:
AB+CDE-F+*G-/
AB-C+DEF-+^
AB&&C||EF<=!||
Convert the following infix expressions to
postfix using stack:
B+C^(E+F*G^H)/(K-L/M)+N
B+C/D^(E+F*G^H)+Z
A+B-C*D*(E+F-G*H^I^J)+L/M+(N*O/P+
(Q^R^S^T))+U
32 Module 2: Data Structures Saturday, February 15
, 2020
Queues
Queue - linearly ordered set of elements
having the first-in, first-out (FIFO) discipline
Applications: job-scheduling, topological
sorting, graph traversals, etc.
2 basic operations for data manipulation:
insertion at the rear (enqueue) and deletion
at the front (dequeue)
33 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
34 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Sequential Representation
Makes use of one-dimensional array/vector
Deletion from an empty queue causes an underflow
Insertion onto a full queue causes an overflow
Front points to the actual front element of the
queue while rear points to the cell immediately
after the rear element
Queue is empty if front=rear and full if front=0 and
rear=n
Initialization : front = 0; rear = 0
Insertion : Q[rear] = x; rear++;
Deletion : x = Q[front]; front++;
35 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
36 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
37 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
38 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Circular Queue
Cells are considered arranged
in a circle
front points to the actual
element at the front of the
queue
rear points to the cell on the
right of the actual rear
element
Full queue always has one
unused cell
Initialization: front = 0, rear
=0
Empty queue: if front == rear
Full queue: if front == (rear
mod n)+1
39 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
40 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Linked Representation
Queue is empty if front = null
Overflow will happen only when the program
runs out of memory
41 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Application: Topological Sorting
Topological sorting is problem involving
activity networks. It uses both sequential and
link allocation techniques in which the linked
queue is embedded in a sequential vector.
It is a process applied to partially ordered
elements. The input is a set of pairs of partial
ordering and the output is the list of
elements, in which there is no element listed
with its predecessor not yet in the output.
42 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
The Algorithm
Input. A set of number pairs of the form (i,
j) for each relation i ≼ j could represent the
partial ordering of elements. The input
pairs could be in any order.
Output. The algorithm will come up with a
linear sequence of items such that no item
appears in the sequence before its direct
predecessor.
43 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Algorithm Proper. A requirement in topological sorting is
not to output the items with which the predecessors are
not yet in the output. To do this, there is a need to keep
track of the number of predecessors for every item. A
vector could be used for this purpose. Let's call this
vector COUNT. When an item is placed in the output,
the count of every successor of the item is
decremented. If the count of an item is zero, or it
becomes zero as a result of putting in the output all of
its predecessors, that would be the time it is considered
ready for output. To keep track of the successors, a
linked list named SUC, with structure (INFO, LINK), will
be used. INFO contains the label of the direct successor
while LINK points to the next successor, if any.
44 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Example. Given the partial ordering of
seven elements, how can they be arranged
such that no element appears in the
sequence before its direct predecessor?
(0,1),(0,3 ),(0,5),(1,2),(1,5),(2,4),(3,2),(3,4),(5,4),(6,5),
(6,7),(7,1),(7,5)
45 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Solution
46 Module 2: Data Structures Saturday, February 15
, 2020
Queues cont…
Solution cont…
47 Module 2: Data Structures Saturday, February 15
, 2020
The End!!!
