Data Structures & Algorithms (CC103-N)

Unit 1: INTRODUCTION

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 sub items- 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.

 Data Structures & Algorithms (CC103-N)

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.

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.
 Data Structures & Algorithms (CC103-N)
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.

Linear Data Structure:

(i) 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
 Data Structures & Algorithms (CC103-N)
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

(ii) 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.
 Data Structures & Algorithms (CC103-N)

(iii) 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.

Non-Linear Data Structure:

(i)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 sub items Street address and Area address, where
Area itself may be a group item having sub items City, State and ZIP code number. This
hierarchical structure is pictured below
 Data Structures & Algorithms (CC103-N)
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.

(ii) 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 & Algorithms (CC103-N)

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 avariable.
Ex: int list[5], *plist[5];

 The array list[5], defines 5 integers and in C array start at index 0, so list[0], list[1],
list[2], list[3], list[4] are the names of five array elements which contains an integer
value.
 The array *plist[5], defines an array of 5 pointers to integers. Where, plist[0], plist[1],
plist[2], plist[3], plist[4] are the five array elements which contains a pointer to an
integer.
 Data Structures & Algorithms (CC103-N)

Implementation:
 When the complier encounters an array declaration, list[5], it allocates five consecutive
memory locations. Each memory is enough large to hold a single integer.
 The address of first element of an array is called Base Address. Ex: For list[5] the
address of list[0] is called the base address.
 If the memory address of list[i] need to compute by the compiler, then the size of the
int would get by sizeof (int), then memory address of list[i] is as follows:

list[i] = α + i * sizeof (int)

Where, α is base address.

Difference between int *list1; & int list2[5];

The variables list1 and list2 are both pointers to an int, but in list2[5] five memory locations
are reserved for holding integers. list2 is a pointer to list2[0] and list2+i is a pointer to list2[i].

Note: In C the offset i do not multiply with the size of the type to get to the appropriate
element of the array. Hence (list2+i) is equal &list2[i] and *(list2+i) is equal to list2[i].

How C treats an array when it is parameter to a function?

 All parameters of a C functions must be declared within the function. As various

parameters are passed to functions, the name of an array can be passed as parameter.
 The range of a one-dimensional array is defined only in the main function since new
storage for an array is not allocated within a function.
 If the size of a one dimensional array is needed, it must be passed into function as a
argument or accessed as a global variable.
 Data Structures & Algorithms (CC103-N)

Example: Array Program

#define MAX_SIZE 100

float sum(float [], int);
float input[MAX_SIZE], answer;
void main(void)
{
int i;
for( i=0; i<MAX_SIZE; i++)
input[i]= i;
answer = sum(input, MAX_SIZE);
printf(“\n The sum is: %f \n”,answer);
}

float sum(float list[], int n)

{
int i;
float tempsum = 0;
for(i=0; i<n; i++)
tempsum = tempsum + list[i];
return tempsum;
}

When sum is invoked, input=&input[0] is copied into a temporary location and associated
with the formal parameter list
A function that prints out both the address of the ith element of the array and the value found
at that address can written as shown in below program.

void print1 (int *ptr, int rows)

{
int i;
printf(“ Address contents \n”);
for(i=0; i<rows; i++)
printf(“% 8u %5d \n”, ptr+i, *(prt+i));
printf(“\n”);
}

Output:
Address Content
12244868 0
12344872 1
12344876 2
12344880 3
12344884 4
 Data Structures & Algorithms (CC103-N)

STRUCTURES
In C, a way to group data that permits the data to vary in type. This mechanism is called the
structure, for short struct.
A structure (a record) is a collection of data items, where each item is identified as to its type
and name.
Syntax: struct
{ data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
} variable_name;

Ex: struct {
char name[10];
int age;
float salary;
} Person;
The above example creates a structure and variable name is Person and that has three fields:
name = a name that is a character array
age = an integer value representing the age of the person
salary = a float value representing the salary of the individual

Assign values to fields

To assign values to the fields, use . (dot) as the structure member operator. This operator is
used to select a particular member of the structure

Ex: strcpy(Person.name,“james”);
Person.age = 10;
Person.salary = 35000;

Type-Defined Structure
The structure definition associated with keyword typedef is called Type-Defined Structure.
Syntax 1: typedef struct
{
data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
}Type_name;
 Data Structures & Algorithms (CC103-N)
Where,
 typedef is the keyword used at the beginning of the definition and by using typedef
user defined data type can be obtained.
 struct is the keyword which tells structure is defined to the complier
 The members are declare with their data_type
 Type_name is not a variable, it is user defined data_type.

Syntax 2: struct struct_name

{
data_type member 1;
data_type member 2;
………………………
………………………
data_type member n;
};
typedef struct struct_name Type_name;

Ex: typedef struct{

char name[10];
int age;
float salary;
}humanBeing;

In above example, humanBeing is the name of the type and it is a user defined data type.

Declarations of structure variables:

humanBeing person1, person2;

This statement declares the variable person1 and person2 are of type humanBeing.

Structure Operation
The various operations can be performed on structures and structure members.

1. Structure Equality Check:

Here, the equality or inequality check of two structure variable of same type or dissimilar type
is not allowed
typedef struct{
char name[10];
int age;
float salary;
}humanBeing;
humanBeing person1, person2;

if (person1 = = person2) is invalid.

 Data Structures & Algorithms (CC103-N)

The valid function is shown below

#define FALSE 0
#define TRUE 1
if (humansEqual(person1,person2))
printf("The two human beings are the same\n");
else
printf("The two human beings are not the same\n");

int humansEqual(humanBeing person1, humanBeing person2)

{ /* return TRUE if person1 and person2 are the same human being otherwise
return FALSE */
if (strcmp(person1.name, person2.name))
return FALSE;
if (person1.age != person2.age)
return FALSE;
if (person1.salary != person2.salary)
return FALSE;
return TRUE;
}
Program: Function to check equality of structures

2. Assignment operation on Structure variables:

person1 = person2
The above statement means that the value of every field of the structure of person 2 is
assigned as the value of the corresponding field of person 1, but this is invalid statement.

Valid Statements is given below:

strcpy(person1.name, person2.name);
person1.age = person2.age;
person1.salary = person2.salary;

Structure within a structure:

There is possibility to embed a structure within a structure. There are 2 ways to embed
structure.

1. The structures are defined separately and a variable of structure type is declared inside the
definition of another structure. The accessing of the variable of a structure type that are nested
inside another structure in the same way as accessing other member of that structure
 Data Structures & Algorithms (CC103-N)

Example: The following example shows two structures, where both the structure are defined
separately.
typedef struct {
int month;
int day;
int year;
}date;

typedef struct {
char name[10];
int age;
float salary;
date dob;
} humanBeing;
humanBeing person1;

A person born on February 11, 1944, would have the values for the date struct set as:
person1.dob.month = 2;
person1.dob.day = 11;
person1.dob.year = 1944;

2. The complete definition of a structure is placed inside the definition of another structure.
Example:
typedef struct {
char name[10];
int age;
float salary;
struct {
int month;
int day;
int year;
} date;
} humanBeing;
 Data Structures & Algorithms (CC103-N)
ARRAY OPERATIONS

1. Traversing
 Let A be a collection of data elements stored in the memory of the computer. Suppose
if the contents of 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. [Initialize Counter] set K:= LB
2. Repeat step 3 and 4 while K ≤ UB
3. [Visit element] Apply PROCESS to LA [K]
4. [Increase counter] Set K:= K + 1
[End of step 2 loop]
5. Exit

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.
 Data Structures & Algorithms (CC103-N)
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
 Data Structures & Algorithms (CC103-N)
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).

MULTIDIMENSIONAL ARRAY

Two-Dimensional Arrays

A two-dimensional m x n array A is a collection of m . n data elements such that each element

is specified by a pair of integers (such as J, K), called subscripts, with the property that
1 ≤ J ≤ m and 1 ≤ K ≤ n

The element of A with first subscript j and second subscript k will be denoted by
AJ,K or A[J, K]

Two-dimensional arrays are called matrices in mathematics and tables in business

applications.
There is a standard way of drawing a two-dimensional m x n array A where the elements of A
form a rectangular array with m rows and n columns and where the element A[J, K] appears
in row J and column K.
 Data Structures & Algorithms (CC103-N)

Representation of Two-Dimensional Arrays in Memory

Let A be a two-dimensional m x n array. Although A is pictured as a rectangular array of
elements with m rows and n columns, the array will be represented in memory by a block of
m . n sequential memory locations.
The programming language will store the array A either (1) column by column, is called
column-major order, or (2) row by row, in row-major order.
 Data Structures & Algorithms (CC103-N)

The computer uses the formula to find the address of LA[K] in time independent of K.
LOC (LA[K]) = Base(LA) + w(K - 1)

The computer keeps track of Base(A)-the address of the first element A[1, 1] of A-and
computes the address LOC(A[J, K]) of A[J, K] using the formula

(Column-major order) LOC(A[J, K]) = Base(A) + w[M(K - 1) + (J - 1)]

(Row-major order) LOC(A[J, K]) = Base(A) + w[N(J - 1) + (K - 1)]

General Multidimensional Arrays

An n-dimensional m1 X m2 X ... X mn array B is a collection of m1, m2 ... mn data elements in
which each element is specified by a list of n integers-such as K1 K2 ... , Kn called subscripts,
with the property that
1 ≤ K1 ≤ m1 , 1 ≤ K2 ≤ m2 ….. 1 ≤ Kn ≤ mn

The element of B with subscripts K1 K2 ... , Kn will be denoted by B[K1 K2 ... , Kn]
The programming language will store the array B either in row-major order or in column-
major order.

Let C be such an n-dimensional array. The index set for each dimension of C consists of the
consecutive integers from the lower bound to the upper bound of the dimension. The length Li
of dimension i of C is the number of elements in the index set, and Li can be calculated, as
Li = upper bound - lower bound + 1

For a given subscript Ki, the effective index Ei of Li is the number of indices preceding Ki in
the index set, and Ei can be calculated from
Ei = Ki - lower bound

Then the address LOC(C[K1 K2 ... , Kn] of an arbitrary element of C can be obtained from the
formula
Base(C) + w[((( ... (ENLN-1 ] + E N-1])LN-2) + ... + E3))L2 + E2)L1 + E1]
or from the formula
Base(C) + w[( ... ((E1L2 + E2)L3 + E3)L4 + ... + EN-1 )LN + EN]

according to whether C is stored in column-major or row-major order.

Data Structures & Algorithms (CC103-N)