Summary University{CSE} detailed notes for best exam performance

DATA STRUCTURES
Data is collection of raw facts that have to be processed.
Information is processed data.
Data structure is a specialized format for organizing and storing data.


Classification of data structures
Data structures are classified into 2 types
1. Primitive Data Structures - These are data structures that are directly operated upon
by machine-level instructions.
Eg - integer, real(float), character, pointers
2. Non-primitive Data Structures - These are data structures that are derived from
Primitive data structures. The emphasis is on grouping of elements. They are further
classified into 3 types
a. Arrays – They are collection of homogeneous elements (elements of same type)
under the same name. The different types of arrays Are One-Dimensional Arrays,
Two-Dimensional Arrays And Multi-Dimensional Arrays.
b. Lists - They are collection of homogeneous elements. They are further classified
into 2 types
i. Linear Data Structure - They are collection of homogeneous elements which
have linear (adjacency) relationship.
Eg. Stacks , Queues, Linked List
ii. Non-Linear Data Structure - They are collection of homogeneous elements
where an element is connected to several other elements.
Eg. Trees , Graphs
c. Files - They are collection of heterogeneous elements (elements of different
types)


Operations on Primitive Data Structures
1. Create Operation – It is used to create a new data structure by reserving memory
space.
Eg. int a;
2. Destroy Operation – It is used to destroy or remove the data structure by de-
allocating the memory that was allocated.
Eg. In C++, delete operator, destructor function are used for this purpose.
3. Select Operation – It is used to access the data within the data structure.
4. Update Operation – It is used to modify or change the data within the data
structure.
Eg. Assignment operator (=) int a=25;




10

,Operations on Non-Primitive Data Structures(Arrays/Lists/Linear/Non-Linear)
1. Traversal Operation – It is the process of accessing each element exactly once to
perform some operation.
2. Searching Operation – It is the process of finding the location of an element in the
given collection of elements.
3. Sorting Operation – It is the process of arranging the elements in either ascending
or descending order.
4. Insertion Operation – It is the process of adding a new element into the given
collection of elements.
5. Deletion Operation – It is the process of removing an existing element from the
given collection of elements.
6. Merging Operation – It is the process of combining the elements of two data
structures to form a single data structure.


ARRAYS


Types of Arrays
1. One-Dimensional Array – It is an array with only one row or one column. / It is an
array ordered in one-dimension. Each element of the array is accessed using one
subscript/index.
2. Two-Dimensional Array – It is an array ordered in two dimensions. Each element of
the array is accessed using two subscripts.
3. Multi-Dimensional Array – It is an array ordered in N dimensions where N>1. Each
element of the array is accessed using N subscripts.


One-Dimensional Array


Declaration Syntax
datatype arrayname[size];
Here datatype specifies the type of the elements stored in the array.
size specifies the number of elements that can be stored in the array.
Eg. int a[20];


Total Size (In Bytes)
Total size = size of the array * size of the datatype
Eg. int a[25];
Total size of array a = 25 * 2 = 50 bytes [ size of int datatype is 2 bytes]




11

, Length of the Array
L = UB – LB + 1
Here, UB – Upper Bound – Index of the last element in the array
LB – Lower Bound – Index of the first element in the array
L – Length – No. of elements in the array


Eg. If UB = 23 and LB = 8. How many elements are there in the array?
L = 23 – 8 + 1 = 16 elements


Memory Representation of 1-Dimensional Array
Elements of 1-D array are stored in consecutive memory locations.
Eg. Consider an array A with 5 integer numbers. Memory representation of array A is as
shown below.


Element 35 67 98 12 21


Address 1000 1002 1004 1006 1008


Address of any element of an array can be calculated using the formula
LOC(A[P]) = BASE(A) + W(P - LB)
Here, P is the position of the array element whose address is being calculated
W is the size of the datatype of elements stored in the array.
LB is the position of the first element in the array.
BASE(A) is the base address of the array. [Base address is the address of
the first element in the array.


Eg. Consider an array A with 55 float numbers if the base address is 7352. Find the
address of A[24]
LOC (A[24]) = BASE(A) + W(P-LB)
= 7352 + 4(24-0)
= 7352 + 96
= 7448




12