HINDUSTHAN INSTITUTE OF TECHNOLOGY

(An Autonomous Institution, Approved by AICTE, New Delhi,Affiliated to Anna University, Chennai,
Accredited with“A”Grade byNAAC)
Valley Campus, Pollachi Main Road, Coimbatore 641 032.

Department of Computer Science and Engineering

20 CS401 DATA STRUCTURES

II YEAR – CSE
 UNIT-I
INTRODUCTION & ARRAYS

DATA STRUCTURES
Data may be organized in many different ways. The logical or mathematical model of a
particular organization of data is called a data structure.

The choice of a particular data model depends on the two considerations

1. It must be rich enough in structure to mirror the actual relationships of the data in the
real world.
2. The structure should be simple enough that one can effectively process the data
whenever necessary.

Basic Terminology: Elementary Data Organization:

Data: Data are simply values or sets of values.

Data items: Data items refers to a single unit of values.

Data items that are divided into sub-items are called Group items. Ex: An Employee Name
may be divided into three subitems- first name, middle name, and last name.

Data items that are not able to divide into sub-items are called Elementary items.
Ex: SSN

Entity: An entity is something that has certain attributes or properties which may be assigned
values. The values may be either numeric or non-numeric.
Ex: Attributes- Names, Age, Sex, SSN
Values- Rohland Gail, 34, F, 134-34-5533

Entities with similar attributes form an entity set. Each attribute of an entity set has a range of
values, the set of all possible values that could be assigned to the particular attribute.
The term “information” is sometimes used for data with given attributes, of, in other words
meaningful or processed data.

Field is a single elementary unit of information representing an attribute of an entity.

Record is the collection of field values of a given entity.

File is the collection of records of the entities in a given entity set.

Each record in a file may contain many field items but the value in a certain field may uniquely
determine the record in the file. Such a field K is called a primary key and the values k1, k2,
….. in such a field are called keys or key values.

Records may also be classified according to length.

A file can have fixed-length records or variable-length records.
 In fixed-length records, all the records contain the same data items with the same amount
of space assigned to each data item.
 In variable-length records file records may contain different lengths.

Example: Student records have variable lengths, since different students take different
numbers of courses. Variable-length records have a minimum and a maximum length.

The above organization of data into fields, records and files may not be complex enough to
maintain and efficiently process certain collections of data. For this reason, data are also
organized into more complex types of structures.

The study of complex data structures includes the following three steps:
1. Logical or mathematical description of the structure
2. Implementation of the structure on a computer
3. Quantitative analysis of the structure, which includes determining the amount of
memory needed to store the structure and the time required to process the structure.

CLASSIFICATION OF DATA STRUCTURES

Data structures are generally classified into

 Primitive data Structures
 Non-primitive data Structures

1. Primitive data Structures: Primitive data structures are the fundamental data types which
are supported by a programming language. Basic data types such as integer, real, character
and Boolean are known as Primitive data Structures. These data types consists of characters
that cannot be divided and hence they also called simple data types.

2. Non- Primitive data Structures: Non-primitive data structures are those data structures
which are created using primitive data structures. Examples of non-primitive data structures
is the processing of complex numbers, linked lists, stacks, trees, and graphs.
Based on the structure and arrangement of data, non-primitive data structures is further
classified into
1. Linear Data Structure
2. Non-linear Data Structure

1. Linear Data Structure:

A data structure is said to be linear if its elements form a sequence or a linear list. There are
basically two ways of representing such linear structure in memory.
1. One way is to have the linear relationships between the elements represented by means
of sequential memory location. These linear structures are called arrays.
2. The other way is to have the linear relationship between the elements represented by
means of pointers or links. These linear structures are called linked lists.

The common examples of linear data structure are Arrays, Queues, Stacks, Linked lists

2. Non-linear Data Structure:

A data structure is said to be non-linear if the data are not arranged in sequence or a linear. The
insertion and deletion of data is not possible in linear fashion. This structure is mainly used to
represent data containing a hierarchical relationship between elements. Trees and graphs are
the examples of non-linear data structure.

Arrays:
The simplest type of data structure is a linear (or one dimensional) array. A list of a finite
number n of similar data referenced respectively by a set of n consecutive numbers, usually 1,
2, 3 . . . . . . . n. if A is chosen the name for the array, then the elements of A are denoted by
subscript notation a1, a2, a3….. an
or
by the parenthesis notation A (1), A (2), A (3).............A (n)
or
by the bracket notation A [1], A [2], A [3].............A [n]

Example 1: A linear array STUDENT consisting of the names of six students is pictured in
below figure. Here STUDENT [1] denotes John Brown, STUDENT [2] denotes Sandra
Gold, and so on.

Linear arrays are called one-dimensional arrays because each element in such an array is
referenced by one subscript. A two-dimensional array is a collection of similar data elements
where each element is referenced by two subscripts.

Example 2: A chain of 28 stores, each store having 4 departments, may list its weekly sales as
in below fig. Such data can be stored in the computer using a two-dimensional array in which
the first subscript denotes the store and the second subscript the department. If SALES is the
name given to the array, then
SALES [1, 1] = 2872, SALES [1, 2] - 805, SALES [1, 3] = 3211,…., SALES [28, 4] = 982

Trees
Data frequently contain a hierarchical relationship between various elements. The data structure
which reflects this relationship is called a rooted tree graph or a tree.
Some of the basic properties of tree are explained by means of examples

Example 1: Record Structure

Although a file may be maintained by means of one or more arrays a record, where one indicates
both the group items and the elementary items, can best be described by means of a tree
structure.
For example, an employee personnel record may contain the following data items:
Social Security Number, Name, Address, Age, Salary, Dependents

However, Name may be a group item with the sub-items Last, First and MI (middle initial).
Also Address may be a group item with the subitems Street address and Area address, where
Area itself may be a group item having subitems City, State and ZIP code number.
This hierarchical structure is pictured below.

Another way of picturing such a tree structure is in terms of levels, as shown below

Some of the data structures are briefly described below.

1. Stack: A stack, also called a fast-in first-out (LIFO) system, is a linear list in which insertions
and deletions can take place only at one end, called the top. This structure is similar in its
operation to a stack of dishes on a spring system as shown in fig.
Note that new 4 dishes are inserted only at the top of the stack and dishes can be deleted only
from the top of the Stack.
2. Queue: A queue, also called a first-in first-out (FIFO) system, is a linear list in which
deletions can take place only at one end of the list, the "from'' of the list, and insertions can take
place only at the other end of the list, the “rear” of the list.
This structure operates in much the same way as a line of people waiting at a bus stop, as
pictured in Fig. the first person in line is the first person to board the bus. Another analogy is
with automobiles waiting to pass through an intersection the first car in line is the first car
through.

3. Graph: Data sometimes contain a relationship between pairs of elements which is not
necessarily hierarchical in nature. For example, suppose an airline flies only between the cities
connected by lines in Fig. The data structure which reflects this type of relationship is called a
graph.
DATA STRUCTURES OPERATIONS
The data appearing in data structures are processed by means of certain operations.
The following four operations play a major role in this text:
1. Traversing: accessing each record/node exactly once so that certain items in the record
may be processed. (This accessing and processing is sometimes called “visiting” the
record.)
2. Searching: Finding the location of the desired node with a given key value, or finding the
locations of all such nodes which satisfy one or more conditions.
3. Inserting: Adding a new node/record to the structure.
4. Deleting: Removing a node/record from the structure.

The following two operations, which are used in special situations:

1. Sorting: Arranging the records in some logical order (e.g., alphabetically according to
some NAME key, or in numerical order according to some NUMBER key, such as social
security number or account number)
2. Merging: Combining the records in two different sorted files into a single sorted file.

ARRAYS
 An Array is defined as, an ordered set of similar data items. All the data items of an
array are stored in consecutive memory locations.
 The data items of an array are of same type and each data items can be accessed using
the same name but different index value.
 An array is a set of pairs, <index, value >, such that each index has a value associated
with it. It can be called as corresponding or a mapping
Ex: <index, value>
< 0 , 25 > list[0]=25
< 1 , 15 > list[1]=15
< 2 , 20 > list[2]=20
< 3 , 17 > list[3]=17
< 4 , 35 > list[4]=35

Here, list is the name of array. By using, list [0] to list [4] the data items in list can be
accessed.

Array in C
Declaration: A one dimensional array in C is declared by adding brackets to the name of a
variable.
Ex: int list[5], *plist[5];
REPRESENTATION OF LINEAR ARRAYS IN MEMORY

Linear Array
A linear array is a list of a finite number ‘n’ of homogeneous data element such that
a. The elements of the array are reference respectively by an index set consisting of n
consecutive numbers.
b. The element of the array are respectively in successive memory locations.

The number n of elements is called the length or size of the array. The length or the numbers
of elements of the array can be obtained from the index set by the formula
When LB = 0,
Length = UB – LB + 1
When LB =
Length = UB
1, Where,

UB is the largest index called the Upper

Bound LB is the smallest index, called the
Lower Bound

Representation of linear arrays in memory

Let LA be a linear array in the memory of the computer. The memory of the
computer is simply a sequence of address location as shown below,

1000
1001
1002
1003
1004

LOC (LA [K]) = address of the element LA [K] of the array LA

The elements of LA are stored in successive memory cells.

The computer does not keep track of the address of every element of LA, but needs
to keep track only the address of the first element of LA denoted by,
Base (LA)
and called the base address of LA.
Using the base address of LA, the computer calculates the address of any element of LA by
the formula
LOC (LA[K]) = Base(LA) + w(K – lower bound)

Where, w is the number of words per memory cell for the array LA.

DYNAMICALLY ALLOCATED ARRAYS

One Dimensional Array

While writing computer programs, if finds ourselves in a situation where we cannot determine
how large an array to use, then a good solution to this problem is to defer this decision to run
time and allocate the array when we have a good estimate of the required array size.

Example:
int i, n, *list;
printf(“Enter the number of numbers to generate:”);
scanf(“%d”, &n);
if(n<1)
{
fprintf (stderr, “Improper value of n \n”);
exit(EXIT_FAILURE);
}
malloc (list, n*sizeof(int));

The programs fails only when n<1 or insufficient memory to hold the list of numbers that are
to be sorted.

Two Dimensional Arrays

C uses array-of-arrays representation to represent a multidimensional array. The two
dimensional arrays is represented as a one-dimensional array in which each element is itself a
one-dimensional array.

Example: int x[3][5];

Array-of-arrays representation
C find element x[i][j] by first accessing the pointer in x[i].
Where x[i] = α+ i* sizeof(int), which give the address of the zeroth element of row i of the
array.
Then adding j*sizeof(int) to this pointer ( x[i] ) , the address of the [j]th element of row i is
determined.
x[i] = α+ i* sizeof(int)
x[j] = α+ j* sizeof(int)
x[i][j] = x[i]+ i* sizeof(int)

Creation of Two-Dimensional Array Dynamically

int **myArray;
myArray = make2dArray(5,10); myArray[2]
[4]=6;

int ** make2dArray(int rows, int cols)

{ /* create a two dimensional rows X cols array */
int **x, i;
malloc(x, rows * sizeof (*x)); /*get memory for row pointers*/ for
(i= 0;i<rows; i++) /* get memory for each row */
malloc(x[i], cols * sizeof(**x));
return x;
}

The second line allocates memory for a 5 by 10 two-dimensional array of integers and the
third line assigns the value 6 to the [2][4] element of this array.

ARRAY OPERATIONS

1. Traversing
 Let A be a collection of data elements stored in the memory of the computer. Suppose
if the contents of the each elements of array A needs to be printed or to count the
numbers of elements of A with a given property can be accomplished by Traversing.
 Traversing is a accessing and processing each element in the array exactly once.

Algorithm 1: (Traversing a Linear Array)

Hear LA is a linear array with the lower bound LB and upper bound UB. This algorithm
traverses LA applying an operation PROCESS to each element of LA using while loop.
1. set K:= LB
2. Repeat step 3 and 4 while K ≤ UB
3. Apply PROCESS to LA [K]
4. Set K:= K + 1 [End of step 2 loop]
5. Exit
6.
Algorithm 2: (Traversing a Linear Array)

Hear LA is a linear array with the lower bound LB and upper bound UB. This algorithm
traverses LA applying an operation PROCESS to each element of LA using repeat – for loop.

1. Repeat for K = LB to UB
Apply PROCESS to LA [K]
[End of loop]
2. Exit.

Example:
Consider the array AUTO which records the number of automobiles sold each year from 1932
through 1984.

To find the number NUM of years during which more than 300 automobiles were sold,
involves traversing AUTO.
1. [Initialization step.] Set NUM := 0
2. Repeat for K = 1932 to 1984:
If AUTO [K] > 300, then: Set NUM: = NUM + 1.
[End of loop.]
3. Return.

2. Inserting
 Let A be a collection of data elements stored in the memory of the computer.
Inserting refers to the operation of adding another element to the collection A.
 Inserting an element at the “end” of the linear array can be easily done provided the
memory space allocated for the array is large enough to accommodate the additional
element.
 Inserting an element in the middle of the array, then on average, half of the elements
must be moved downwards to new locations to accommodate the new element and keep
the order of the other elements.

Algorithm:
INSERT (LA, N, K, ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K ≤ N. This
algorithm inserts an element ITEM into the Kth position in LA.

1. [Initialize counter] set J:= N

2. Repeat step 3 and 4 while J ≥ K
3. [Move Jth element downward] Set LA [J+1] := LA[J]
4. [Decrease counter] set J:= J – 1
[End of step 2 loop]
5. [Insert element] set LA[K]:= ITEM
6. [Reset N] set N:= N+1
7. Exit
3. Deleting
 Deleting refers to the operation of removing one element to the collection A.
 Deleting an element at the “end” of the linear array can be easily done with difficulties.
 If element at the middle of the array needs to be deleted, then each subsequent
elements be moved one location upward to fill up the array.

Algorithm
DELETE (LA, N, K, ITEM)
Here LA is a linear array with N elements and K is a positive integer such that K ≤ N. this
algorithm deletes the Kth element from LA

1. Set ITEM:= LA[K]

2. Repeat for J = K to N – 1
[Move J + 1 element upward] set LA[J]:= LA[J+1]
[End of loop]
3. [Reset the number N of elements in LA] set N:= N – 1
4. Exit
Example: Inserting and Deleting
Suppose NAME is an 8-element linear array, and suppose five names are in the array, as in Fig.
(a). Observe that the names are listed alphabetically, and suppose we want to keep the array
names alphabetical at all times. Suppose Ford is added to the array. Then Johnson, Smith and
Wagner must each be moved downward one location, as in Fig.(b). Next suppose Taylor is
added to the array; then Wagner must be moved, as in Fig.(c). Last, suppose Davis is removed
from the array. Then the five names Ford, Johnson, Smith, Taylor and Wagner must each be
moved upward one location, as in Fig.(d).
5. Searching
 Let DATA be a collection of data elements in memory, and suppose a specific ITEM of
information is given. Searching refers to the operation of finding the location LOC of
ITEM in DATA, or printing some message that ITEM does not appear there.
 The search is said to be successful if ITEM does appear in DATA and unsuccessful
otherwise.

Linear Search
Suppose DATA is a linear array with n elements. Given no other information about DATA,
The way to search for a given ITEM in DATA is to compare ITEM with each element of DATA
one by one. That is, first test whether DATA [l] = ITEM, and then test whether DATA[2] =
ITEM, and so on. This method, which traverses DATA sequentially to locate ITEM, is called
linear search or sequential search.
Algorithm: (Linear Search) LINEAR (DATA, N, ITEM, LOC)
Here DATA is a linear array with N elements, and ITEM is a given item of information. This
algorithm finds the location LOC of ITEM in DATA, or sets LOC: = 0 if the search is
unsuccessful.
1. [Insert ITEM at the end of DATA.] Set DATA [N + 1]: = ITEM.
2. [Initialize counter.] Set LOC: = l.
3. [Search for ITEM.]
Repeat while DATA [LOC] ≠ ITEM:
Set LOC:= LOC + 1.
[End of loop.]
4. [Successful?] If LOC = N + 1, then: Set LOC:= 0
5. Exit.

Complexity of the Linear Search Algorithm

Worst Case: The worst case occurs when one must search through the entire array DATA,
i.e., when ITEM does not appear in DATA. In this case, the algorithm requires comparisons.
f(n) = n + 1
Thus, in the worst case, the running time is proportional to n.

Average Case: The average number of comparisons required to find the location of ITEM is

(𝑛+1)
approximately equal to half the number of elements in the array.

2
f(n)=

Binary Search
Suppose DATA is an array which is sorted in increasing numerical order or, equivalently,
alphabetically. Then there is an extremely efficient searching algorithm, called binary search,
which can be used to find the location LOC of a given ITEM of information in DATA.
Algorithm: (Binary Search) BINARY (DATA, LB, UB, ITEM, LOC)
Here DATA is a sorted array with lower bound LB and upper bound UB, and ITEM is a
given item of information. The variables BEG, END and MID denote, the beginning, end and
middle locations of a segment of elements of DATA.
 This algorithm finds the location LOC of ITEM in DATA or sets LOC = NULL.

1. [Initialize segment variables.]

Set BEG: = LB, END = UB and MID = INT((BEG + END)/2).
2. Repeat Steps 3 and 4 while BEG ≤ END and DATA [MID] ≠ ITEM.
3. If ITEM < DATA [MID], then: Set
END = MID - 1.
Else:
Set BEG = MID + 1.
[End of If structure.]
4. Set MID = INT((BEG + END)/2). [End of
Step 2 loop.]
5. If DATA[MID] = ITEM, then:
Set LOC = MID.
Else:
Set LOC = NULL.
[End of If structure.]
6. Exit.
Remark: Whenever ITEM does

Complexity of the Binary Search Algorithm

The complexity is measured by the number f(n) of comparisons to locate ITEM in DATA
where DATA contains n elements. Observe that each comparison reduces the sample size in
half. Hence we require at most f(n) comparisons to locate ITEM where

2f(n) > n or equivalently f(n) = [log2 n] + 1

That is, the running time for the worst case is approximately equal to log2 n. One can also
show that the running time for the average case is approximately equal to the running time for
the worst case.

Text Book:

Mark Allen Weiss, “Data Structures and Algorithm Analysis in C”, 2nd Edition, Pearson
Education,1997.