Elementary Data Structure.
2.1 FUNDAMENTAL.
D
D
ata structure is a method of organizing data with a sort of relationship with an intension of
enhancing the qualities of associated algorithms. In this chapter, we review only the non-primitive
data structures. The non-primitive data structures can be broadly classified into two types linear
and non-linear data structures. Under linear data structures Arrays, Stacks and Queues and under nonlinear
data structures graphs and trees are reviewed.
2.2 LINEAR DATA STRUTURE.
A data structure in which every data element has got exactly two neighbors or two adjacent elements
except two elements having exactly one data element is called a linear data structure. Otherwise it is
called a nonlinear data structure.
2.2.1 Array and its representatio.
Array is a finite ordered list of data elements of same type. In order to create an array it is required to
reserve adequate number of memory locations. The allocated memory should be contiguous in nature.
The size of the array is finite and fixed up as a constant. Some of the important operations related to
arrays are,
Creation () g A[n], Array created (reservation of adequate number of memory locations) memory
reserved;
Write (A, i, e) g Updated array with ‘e’ at ith position;
Compare (i, j, Relationl operator) g Boolean;
BSIT 41 Algorithms
Chapter 2 - Elementary Data Structures
Read (A, i) g ‘e’ element at ith position;
Search (A, e) g Boolean;
REPRESENTATION OF A SINGLE DIMENSIONAL ARRA.
1 2 3 4 56
3 7 -8 10 15 5 …… 50 20
1000 1002 1004 1006 1008 1010
Any array is associated with a lower bound l and an upper bound u in general. When the array is
created then it starts at some base address B. Since the computer is byte addressable, each address can
hold a byte. If an integer takes 2 bytes for representation and if B=1000 and if l=1, then
the 1st element is at (1000 + 0)th location
2nd element is at (1000 + 2)th location
3rd element is at (1000 + 4)th location
..
..
..
ith
element is at (1000 + (i-1)*2 )th location
In general, if w is the size of the data element, then ith element is at (B + (i – l) w)th location. i.e., A[i]
= B + (i – l) w.
REPRESENTATION OF A TWO DIMENSIONAL ARRA.
The two dimensional array A[l..u] [l..u] may be interpreted as n = u-l+1 rows and m = u-l+1
11221122
columns i.e., each row consists of u2-l2+1 elements.
l2 l2+1 l2+2 l2+3 l2+4 …. u2
l1
l1+1
l1+2
.
u1
BSIT 41 Algorithms
Although we have an n´m matrix representation the allocations is not in the form of matrix but is
contiguous in nature and will be as shown below. Incase if l1=1, and l2=1 the indices start at [1, 1].
1,1 1,2 1,3 …. 1,m 2,1 2,2 2,3 … 2,m …. ….. n,1 n,2 …. n,m
Given the indices (i, j), the address can be computed using A[i, j] = B + (i-1) m+ (j-1).
In general, if l £ i £u and l £ j £u , then A[i, j] = B + { (i - l ) (u – l +1) +(j - l )}w.
iijjijjj
For higher n-dimensional arrays, the address can be computed as
A( i, i, i, ….i) where l £ i £u, l £ i £u, … l £ i £u
123n111222nnn
A( i, i, i, ….i) = B + { (i - l) (u - l +1)(u-l+1) ….(u- l+1) + (i - l) (u - l +1)(u-l+1) ….
123n112233nn223344
(u- l+1) + (i - l) (u - l +1) (u-l+1) ….(u- l+1)
nn334455nn
+ ……+
(i - l) (u - l +1) + (i- l) }w
n-1n-1nnnn
The algorithm thus designed to compute the row major address is as follows
Algorithm: Address Computation (Row Major)
Input: (1) n, dimension
(2) l1, l2, l3, … ln n lower limits
(3) u1, u2, u3, … un n upper limits
(4) w, word size
(5) i1, i2, i3, …., in values of subscripts
(6) B, the base address
Output: ‘A’ address of the element at (i1, i2, i3, …., in)
Method:
n
A = B + íì
å(ij - lj )Pj ý
ü
w
î j =1 þ
n
where Pj =Õ(uk - lk +1)
k = j +1
Algorithm ends.
Chapter 2 - Elementary Data Structures
2.2.2 Stack.
A stack is an ordered list in which all insertions and deletions are made at one end, called the top. Stack
is a linear data structure which works based on the strategy last-in-first out (LIFO). It is a linear data
structure which is open for operations at only one end (both insertions and deletions are defined at only
one end). One natural example of stack, which arises in computer programming, is the processing of
procedure calls and their terminations. Stacks are generally used to remember things in reverse. It finds
a major use in backtracking approaches.
Some of the functions related to a stack are
Create ( ) g S;
Insertion(S, e) g updated S;
Deletion (S) g S, e;
Isfull(S) g Boolean;
Isempty(S) g Boolean;
Top(S) g e;
Destroy(S)
It has to be noted that with respect to a stack, insertion and deletion operations are, in general, called
PUSH and POP operations respectively. Following are the algorithms for some functions of stack.
Algorithm: Create
Output: S, Stack created
Method:
Declare S[SIZE] //Array of size=SIZE
Declare and Initialize T=0 //Top pointer to remember the number of elements
Algorithm ends
Algorithm: Isempty
Input: S, stack
Output: Boolean
BSIT 41 Algorithms
Method:
If (T==0)
Return (yes)
Else
Return (no)
If end
Algorithm ends
Algorithm: Isfull
Input: S, stack
Output: Boolean
Method:
If (T==SIZE)
Return (yes)
Else
Return (no)
If end
Algorithm ends
Algorithm: Push
Input: (1) S, stack; (2) e, element to be inserted; (3) SIZE, size of the stack;
(4) T, the top pointer
Output: (1) S, updated; (2) T, updated
Method:
If (Isfull(S)) then
Print (‘stack overflow’)
Else
T=T+1;
S[T] =e
If end
Algorithm ends
Chapter 2 - Elementary Data Structures
Algorithm: Pop
Input: (1) S, stack;
Output: (1) S, updated; (2) T, updated (3) ‘e’ element popped
Method:
If (Isempty(S)) then
Print (‘stack is empty’)
Else
e = S[T]
T=T-1;
If end
Algorithm ends
2.2.3 Queue.
A queue is an ordered list in which all insertions take place at one end called the rear end, while all
deletions take place at the other end called the front end. Queue is a linear data structure which works
based on the strategy first-in-first out (FIFO). Unlike stacks, queues also arise quite naturally in the
computer solution of many problems. Perhaps the most common occurrence of a queue in computer
applications is for scheduling of jobs. A minimal set of useful operations on queue includes the following.
Create ( ) g Q;
Insertion (Q, e) g updated Q;
Deletion (Q) g Q, e;
Isfull (Q) g Boolean;
Isempty (Q) g Boolean;
Front (Q) g e;
Back (Q);
Destroy (Q);
Following are the algorithms for some functions of queue.
Algorithm: Create
Output: Q, Queue created
BSIT 41 Algorithms
Method:
Declare Q[SIZE] //Array with size=SIZE
Declare and Initialize F=0, R=0
//Front and Rear pointers to keep track of the front element and the rear element respectively
Algorithm ends
Algorithm: Isempty
Input: Q, Queue
Output: Boolean
Method:
If (F==0)
Return (yes)
Else
Return (no)
If end
Algorithm ends
Algorithm: Isfull
Input: Q, Queue
Output: Boolean
Method:
If (R==SIZE)
Return (yes)
Else
Return (no)
If end
Algorithm ends
Chapter 2 - Elementary Data Structures
Algorithm: Front
Input: Q, Queue
Output: element in the front
Method:
If (Isempty (Q))
Print ‘no front element’
Else
Return (Q[F])
If end
Algorithm ends
Algorithm: Rear
Input: Q, Queue
Output: element in the rear
Method:
If (Isempty (Q))
Print ‘no back element’
Else
Return (Q[R])
If end
Algorithm ends
Algorithm: Insertion
Input: (1) Q, Queue; (2) e, element to be inserted; (3) SIZE, size of the Queue;
(4) F, the front pointer; (5) R, the rear pointer
Output: (1) Q, updated; (2) F, updated; (3) R, updated
BSIT 41 Algorithms
Method:
If (Isfull (Q)) then
Print (‘overflow’)
Else
R=R+1;
Q[R]=e
If (F==0)
F=1;
If end
If end
Algorithm ends
Algorithm: Deletion
Input: (1) Q, Queue; (2) SIZE, size of the Queue; (3) F, the front pointer; (4) R, the rear pointer
Output: (1) Q, updated; (2) F, updated; (3) R, updated; (4) e, element if deleted;
Method:
If (Isempty (Q)) then
Print (‘Queue is empty’)
Else
e = Q[F]
If (F==R)
F=R=0;
Else
F=F+1;
If end
If end
Algorithm ends
Chapter 2 - Elementary Data Structures
However, the linear queue makes less utilization of memory i.e., the ‘return (isfull (Q)) =yes’ does not
necessarily imply that there are n elements in the queue. This can be overcome by the using an alternate
queue called the circular queue.
2.2.4 Circular Queu.
A circular queue uses the same conventions as that of linear queue. Using Front will always point one
position counterclockwise from the first element in the queue. In order to add an element, it will be
necessary to move rear one position clockwise. Similarly, it will be necessary to move front one position
clockwise each time a deletion is made. Nevertheless, the algorithms for create (), Isfull (), Isempty (),
Front () and Rear () are same as that of linear queue. The algorithms for other functions are
Algorithm: Insertion
Input: (1) CQ, Circular Queue; (2) e, element to be inserted; (3) SIZE, size of the Circular Queue;
(4) F, the front pointer; (5) R, the rear pointer
Output: (1) CQ, updated; (2) F, updated; (3) R, updated
Method:
If (Isfull (CQ)) then
Print (‘overflow’)
Else
R=R mod SIZE + 1;
CQ[R] =e
If (Isempty (CQ))
F=1;
If end
If end
Algorithm ends
Algorithm: Deletion
Input: (1) CQ, Circular Queue; (2) SIZE, size of the CQ; (3) F, the front pointer; (4) R, the rear
pointer
Output: (1) CQ, updated; (2) F, updated; (3) R, updated; (4) e, element if deleted;
BSIT 41 Algorithms
17
Method:
If (Isempty (CQ)) then
Print (‘Queue is empty’)
Else
e = CQ[F]
If (F==R)
F=R=0;
Else
F=F mod SIZE +1;
If end
If end
Algorithm ends
2.3 NON-LINEAR DATA STRUCTURE.
A data structure which is not linear data structure is said to be non-linear data structure. That is, a
data structure is said to be non-linear if data elements are allowed to have more than two adjacent
elements. Meaning that, a data element can have any number of relations with other data elements.
.
The number of elements adjacent to a given element is called ‘arity’ or the degree of the
element. i.e., degree = number of relations the element has with others.
.
There is no upper limit placed on this number.
Some of the examples in general are : Friendship among classmates; family structure; University with
every component being a sub-component and the relations among them being non-linear; the nervous
system of the human body, etc.
Few of the specific to Computer Science are: graph, tree.
2.3.1 Introduction to Graph Theor.
A graph G = (V, E) consists of a set of objects V = {v1, v2, …} called vertices, and another set E = {e1,
e2, …} whose elements are called edges. Each edge ek in E is identified with an unordered pair (vi, vj) of
vertices. The vertices vi, vj associated with
Chapter 2 - Elementary Data Structures
Fig. 2.1
edge ek are called the end vertices of ek. The most common representation of graph is by means of a
diagram, in which the vertices are represented as points and each edge as a line segment joining its end
vertices.
In the Fig. 2.1 edge e1 having same vertex as both its end vertices is called a self-loop. There may be
more than one edge associated with a given pair of vertices, for example e4 and e5 in Fig. 2.1. Such
edges are referred to as parallel edges.
A graph that has neither self-loop nor parallel edges are called a simple graph, otherwise it is called
general graph. It should also be noted that, in drawing a graph, it is immaterial whether the lines are
drawn straight or curved, long or short: what is important is the incidence between the edges and vertices.
Because of its inherent simplicity, graph theory has a very wide range of applications in engineering,
physical, social, and biological sciences, linguistics, and in numerous other areas. A graph can be used to
represent almost any physical situation involving discrete objects and a relationship among them.
2.3.1.1 Finite and Infinite Graph.
Although in the definition of a graph neither the vertex set V nor the edge set E need be finite, in most
of the theory and almost all applications these sets are finite. A graph with a finite number of vertices as
well as a finite number of edges is called a finite graph; otherwise, it is an infinite graph.
2.3.1.2 Incidence and Degre.
When a vertex vis an end vertex of some edge e, v and e are said to be incident with (on or to) each
i jij
other. In Fig. 2.1, for example, edges e2, e6, and e7 are incident with vertex v4. Two nonparallel edges are
said to be adjacent if they are incident on a common vertex. For example, e2 and e7 in Fig. 2.1 are
adjacent. Similarly, two vertices are said to be adjacent if they are the end vertices of the same edge. In
Fig. 3.1, v4 and v5 are adjacent, but v1 and v4 are not.
The number of edges incident on a vertex vi, with self-loops counted twice is called the degree, d(vi),
of vertex v. In Fig. 2-1, for example, d(v) = d(v) = d(v) = 3, d(v) = 4, and d(v) = 1. Since each edge
i13425
contributes two degrees, the sum of the degrees of all vertices in G is twice the number of edges in G.
BSIT 41 Algorithms
2.3.1.3 Isolated Vertex, Pendent Vertex and Null Grap.
A vertex having no incident edge is called an isolated vertex. In other words, isolated vertices are
vertices with zero degree. Vertex v4 and v7 in Fig. 2.2, for example, are isolated vertices. A vertex of
degree one is called a pendent vertex or an end vertex. Vertex v3 in Fig. 2.2 is a pendant vertex. Two
adjacent edges are said to be in series if their common vertex is of degree two. In Fig. 2.2, the two edges
incident on v1 are in series.
Fig. 2.2 Graph containing isolated vertices, series edges and a pendant vertex.
Fig. 2.3 Null graph of six vertices
In the definition of a graph G = (V, E), it is possible for the edge set E to be empty. Such a graph,
without any edges, is called a null graph. In other words, every vertex in a null graph is an isolated vertex.
A null graph of six vertices is shown in Fig. 2-3. Although the edge set E may be empty, the vertex set V
must not be empty; otherwise, there is no graph. In other words, by definition, a graph must have at least
one vertex.
2.3.1.4 Walk, Path and Connected Grap.
A “walk” is a sequence of alternating vertices and edges, starting with a vertex and ending with a
vertex with any number of revisiting vertices and retracing of edges. If a walk has the restriction of no
repetition of vertices and no edge is retraced it is called a “path”. If there is a walk to every vertex from
any other vertex of the graph then it is called a “connected” graph.
Chapter 2 - Elementary Data Structures
2.3.2 Matrix Representation of Graph.
Although a pictorial representation of a graph is very convenient for a visual study, other representations
are better for computer processing. A matrix is a convenient and useful way of representing a graph to
a computer. Matrices lend themselves easily to mechanical manipulations. Besides, many known results
of matrix algebra can be readily applied to study the structural properties of graphs from an algebraic
point of view. In many applications of graph theory, such as in electrical network analysis and operation
research, matrices also turn out to be the natural way of expressing the problem.
2.3.2.1 Adjacency matrix Representatio.
Since the edges are the relationship between two vertices, the graph can be represented by a matrix.
Consider a 2D matrix X of size |v| × |v where |v| is the number of vertices in
Fig. 2.4
G. The entries in the matrix are either zero or one. i.e., X
ìí
î
=
if
(, )
v
i
v
belongsto E
j
0 otherwise
Thus the matrix where each column and row corresponds to the vertex in the graph G shown in Fig.
2.4 is
V1 V2 V3 V4 V5 V6
V1
V2
V3
V4
V5
V6
0 1 0 0 1 0
1 0 1 1 1 0
0 1 0 0 0 0
0 1 0 0 1 1 (2)
1 1 0 1 0 0
0 0 0 1 (2) 0 0
This matrix X uniquely represents the graph. It is indeed possible to reconstruct the graph back from
the matrix. The high entry in the matrix says the vertex corresponding to the row and vertex corresponding
BSIT 41 Algorithms
to the column is adjacent. Since, two vertices are adjacent if there is an edge connecting them, and the
matrix represents the same, the above matrix X is called an adjacency matrix.
Adjacency matrix is a symmetric matrix. If the diagonal elements are high then the graph has a self
loop, the respective row index gives the vertex label with self loop. The sum of the ith row elements gives
the degree of the vertex Vi. While calculating the row sum of the adjacency matrix of a non-simple graph,
a weightage 1 has to be given if the diagonal cell is high and additional weightage to every parallel edge.
2.3.2.2 Incidence Matri.
Let G be a graph with n vertices, e edges, and no self-loops. Define an n by e matrix A =[aij], whose
n rows correspond to the n vertices and the e columns correspond to the e edges, as follows:
The matrix element
Aij = 1, if jth edge ej is incident on ith vertex vi, and
= 0, otherwise.
a b c d e f g h
v1 0 0 0 1 0 1 0 0
v2 0 0 0 0 1 1 1 1
v3 0 0 0 0 0 0 0 1
v4 1 1 1 0 1 0 0 0
v5 0 0 1 1 0 0 1 0
v6 1 1 0 0 0 0 0 0
(b)
Fig. 2.5 Incidence matrix of the graph in Fig. 2.4.
Such a matrix A is called the vertex-edge incidence matrix, or simply incidence matrix. Matrix A
for a graph G is sometimes also written as A(G). A graph and its incidence matrix are shown in Fig. 2.4
and Fig. 2.5 respectively. The incidence matrix contains only two elements, 0 and 1. Such a matrix is
called a binary matrix or a (0, 1)-matrix.
The following observations about the incidence matrix A can readily be made:
1. Since every edge is incident on exactly two vertices, each column of A has exactly two1’s.
2. The number of 1’s in each row equals the degree of the corresponding vertex.
3. A row with all 0’s, therefore, represents an isolated vertex.
Chapter 2 - Elementary Data Structures
4. Parallel edges in a graph produce identical columns in its incidence matrix, for example, columns
1 and 2 in Fig. 2.5.
2.3.3 Tree.
The concept of a tree is probably the most important in graph theory, especially for those interested in
applications of graphs.
A tree is a connected graph without any circuits. The graph in Fig 2.6 for instance, is a tree. It follows
immediately from the definition that a tree has to be a simple graph, that is, having neither a self-loop nor
parallel edges (because they both form circuits).
Fig. 2-6. Tree
Trees appear in numerous instances. The genealogy of a family is often represented by means of a
tree. A river with its tributaries and sub-tributaries can also be represented by a tree. The sorting of mail
according to zip code and the sorting of punched cards are done according to a tree (called decision tree
or sorting tree).
2.3.3.1 Some Properties of Tre.
1. There is one and only one path between every pair of vertices in a tree, T.
2. A tree with n vertices has n-1 edges.
3. Any connected graph with n vertices and n-1 edges is a tree.
4. A graph is a tree if and only if it is minimally connected.
Therefore a graph with n vertices is called a tree if
1. G is connected and is circuit less, or
2. G is connected and has n-1 edges, or
3. G is circuit less and has n-1 edges, or
4. There is exactly one path between every pair of vertices in G, or
5. G is a minimally connected graph.