• The study of data structures is an essential subject of

every undergraduate and graduate programs related to

computer science.
• A thorough understanding of the basics of this subject is
inevitable for efficient programming.
1.1. AN INTRODUCTION TO DATA
STRUCTUREs
• The structural representation of logical relationships between elements of data.
• In other words, a data structure is a way of organizing data items by
considering its relationship to each other.
• Data structure mainly specifies the structured organization of data, by
providing accessing methods with correct degree of associativity.
• Data structure affects the design of both the structural and functional aspects
of a program.
• Algorithm + Data Structure = Program
• Data structures are the building blocks of a program; here the selection of a
particular data structure will help the programmer to design more efficient
programs as the complexity and volume of the problems solved by the
computer is steadily increasing day by day.
• The programmers must strive hard to solve these problems. If the problem is
analyzed and divided into sub problems, the task will be much easier i.e.,
divide, conquer and combine.
1.12. CLASSIFICATION OF DATA
STRUCTURE
• Data structures are broadly divided into two :
• 1. Primitive data structures : These are the basic data
structures and are directly operated upon by the machine
instructions, which is in a primitive level.
• They are integers, floating point numbers, characters, string
constants, pointers etc.
• 2. Non-primitive data structures : It is a more
sophisticated data structure emphasizing on structuring of
a group of homogeneous (same type) or
heterogeneous(different type) data items.
• Array, list, files, linked list, trees and graphs fall inthis category.
13. ARRAYS

• Arrays are most frequently used in programming. Mathematical

problems like matrix, algebra and etc can be easily handled by arrays.
• An array is a collection of homogeneous data elements described by a
single name.
• Each element of an array is referenced by a subscripted variable or
value, called subscript or index enclosed in parenthesis.
• If an element of an array is referenced by single subscript, then the
array is known as one dimensional array or linear array and if two
subscripts are required to reference an element, the array is known as
two dimensional array and so on.
• Analogously the arrays whose elements are referenced by two or
more subscripts are called multi dimensional arrays.
1.13.1. ONE DIMENSIONAL ARRAY
• One-dimensional array (or linear array) is a set of ‘n’ finite
numbers of homogenous data elements such as :
• The elements of the array are referenced respectively by an index
set consisting of ‘n’ consecutive numbers.
• The elements of the array are stored respectively in successive
memory locations.
• ‘n’ number of elements is called the length or size of an
array. The elements of an array ‘A’ may be denoted in C as
• A[0], A[1], A[2], ...... A[n –1].
• The number ‘n’ in A[n] is called a subscript or an index and
A[n] is called a subscripted variable. If ‘n’ is 10, then the
array elements A[0], A[1]......A[9] are stored in sequential
memory locations as follows :
• A[0] A[1] A[2] ...... A[9]
Reading and writing array
• In C, array can always be read or written through loop.
To read a one-dimensional array, it requires one loop for
reading and writing the array, for example:
• For reading an array of ‘n’ elements
for (i = 0; i < n; i ++)
scanf (“%d”,&a[i]);
• For writing an array
for (i = 0; i < n; i ++)
printf (“%d”, &a[i]);
 MULTI DIMENSIONAL ARRAY

• If we are reading or writing two-

dimensional array, two loops are required.
Similarly
• the array of ‘n’ dimensions would require
‘n’ loops. The structure of the two
dimensional array is illustrated in the
following figure :
• int A[10][10];
3. SPARSE ARRAYS
• Sparse array is an important application of arrays. A sparse array is
an array where:
• nearly all of the elements have the same value (usually zero) and
this value is a constant.
• One-dimensional sparse array is called sparse vector and two-
dimensional sparse arrays are called sparse matrix.
• The main objective of using arrays is to
• minimize the memory space requirement
• improve the execution speed of a program.
• This can be achieved by allocating memory space for only non-zero
elements.
• For example a sparse array can be viewed as
SPARSE ARRAYS

Store only non-zero elements in the above sparse

matrix because storing all the elements of the sparse
array will be consisting of memory sparse.
The non-zero elements are stored in an array of the
form.
A[0......n][1......3]
Where ‘n’ is the number of non-zero elements in the
array.
In the above Fig. 1.5 ‘n = 7’.
The space array given in Fig. 1.5 may be represented in
the array A[0......7][1.....3].
SPARSE ARRAYS representation
• The element A[0][1] and A[0][2] contain the number of rows
and columns of the
• sparse array. A[0][3] contains the total number of nonzero
elements in the sparse array.
• A[1][1] contains the number of the row where the first
nonzero element is present in the
• sparse array. A[1][2] contains the number of the column of
the corresponding nonzero element.
• A[1][3] contains the value of the nonzero element. In the Fig.
1.4, the first nonzero element can be found at 1st row in 3rd
column.
14. VECTORS
• A vector is a one-dimensional ordered collection of numbers.
Normally, a number of contiguous memory locations are sequentially
allocated to the vector. A vector size is fixed and, therefore, requires
a fixed number of memory locations. A vector can be a column
• vector which represents a ‘n’ by 1 ordered collections, or a row
vector which represents a 1 by ‘n’ ordered collections.
• The column vector appears symbolically as follows :

• A row vector appears symbolically as follows :

• A = (A1, A2, A3, ...... An)
• Vectors can contain either real or complex numbers. When they
contain real numbers, they are sometime called real vectors.
• When they contain complex numbers, they are called complex
vectors.
.15. LISTS

As we have discussed, an array is an ordered set, which consist of a

fixed number of elements.
• No deletion or insertion operations are performed on arrays.
• Another main disadvantage is its fixed length; we cannot add elements to the array.

Lists overcome all the above limitations.

A list is an ordered set consisting of a varying number of elements to

which insertion and deletion can be made.

A list represented by displaying the relationship between the adjacent

elements is said to be a linear list. Any other list is said to be non linear.
List can be implemented by using pointers. Each element is referred to
as nodes; therefore a list can be defined as a collection of nodes as
shown below :
FILES AND RECORDS
• A file is typically a large list that is stored in the external memory (e.g., a magnetic
• disk) of a computer.
• A record is a collection of information (or data items) about a particular entity. More
• specifically, a record is a collection of related data items, each of which is called a
filed or
• attribute and a file is a collection of similar records.
• Although a record is a collection of data items, it differs from a linear array in the
• following ways:
• (a) A record may be a collection of non-homogeneous data; i.e., the data items in a
• record may have different data types.
• (b) The data items in a record are indexed by attribute names, so there may not be
a
• natural ordering of its elements
 17. CHARACTERISTICS OF STRINGS

• In computer terminology the term

‘string’ refers to a sequence of
characters.
• A finite set of sequence (alphabets,
digits or special characters) of zero
or more characters is called a string.
• The number of characters in a string
is called the length of the string.
• If the length of the string is zero
then it is called the empty string
or null string.
• .
STRING REPRESENTATION

• Strings are stored or represented in memory by using following

three types of structures :
• • Fixed length structures
• • Variable length structures with fixed maximum
• • Linear structures

• FIXED LENGTH REPRESENTATION. In fixed length storage each

line is viewed as a
• record, where all records have the same length. That is each
record accommodates maximum of same number of characters
Fiexed length representation
The main
advantage of 1. To access data from any given record easily.
representing the
string in the 2. It is easy to update the data in any given record.
above way is :

1. Entire record will be read even if most of the storage

consists of inessential blank space. Time is wasted in reading
The main these blank spaces.
disadvantages
are : 2. The length of certain records will be more than the fixed
length. That is certain records may require more memory
space than available.
Variable Length Representation
• In variable length representation, strings are stored in a
fixed length storage medium. This is done in two ways.
• One can use a marker, (any special characters) such as two-
dollar sign ($$), to signal the end of the string.
• Listing the length of the string at the first place is another way
of representing strings in this method.
Linked List Representations
• In linked list representations each characters in a string
are sequentially arranged in memory cells, called nodes,
where each node contain
• An item and link, which points to the next node in the
list (i.e., link contain the address of the next node)
17.2. SUB STRING

• Group of consecutive elements or characters in a string

(or sentence) is called substring.
• This group of consecutive elements may not have any
special meaning. To access a sub string from the given
string we need following information :
• (a) Name of the string
• (b) Position of the first character of the sub string in the given
string
• (c) The length of the sub string
• Finding whether the sub string is available in a string by
matching its characters is called pattern matching.
3. RELEASING THE USED SPACE
• Dynamic memory allocation allocates block(s) of memory
when it is required and deallocates or releases when it is not in
use.
• It is important and is our responsibility to release the memory
block for future use when it is not in use, using free() function.
• The free() function is used to deallocate the previously
allocated memory using malloc() or calloc() function.
• The syntax of this function is free(ptr);
• ‘ptr’ is a pointer to a memory block which has already been
allocated by malloc() or calloc() functions.
• Trying to release an invalid pointer may create problems and
cause system crash.
.2. DYNAMIC MEMORY ALLOCATION
IN C+
• Although C++ supports all the functions (i.e., malloc, calloc, realloc
and free) used in C, it also defines two unary operators new and
delete that performs the task of allocating and freeing the memory
in a better and easier way.
• An object (or variable) can be created by using new, and destroyed
by using delete, as and when required.
• A data object created inside a block with new, will remain in
existence until it is explicitly destroyed by using delete. Thus, the
lifetime of an object is directly under our control and is unrelated to
the block structure of the program.
• The new operator can be used to create objects of any type. It takes
the following general form:
• Pointer_Variable = new data_type;
• Here, Pointer_Variable is a pointer of type data_type.
• The new operator allocates sufficient memory to hold a data object of type
data_type and returns the address of the object.
• The data_type may be any valid data type. The Pointer_Variable holds the
address of the memory space allocated. For example:
• int *Var1 = new int;
• float *Var2 = new float;
• Where Var1 is a pointer of type int and Var2 is a pointer of type float.
• When a data object is no longer needed, it is destroyed to release the memory
space for reuse.
• The general form of its use is:
• delete Pointer_Variable
• The Pointer_Variable is the pointer that points to a data object created with new.
• delete Var1;
• delete Var2