LECTURE WEEK 1 Course overview

ACTIVITY
Route Maps
Library Books
Phone book
Attendance record of employees
Students exam copies
Files and folders
Friends watsapp group
AIM

The prime aim of data structure includes to study how data is organized in a
computer, how it is manipulated, how it is retrieved, and how it can be
utilized, resulting in more efficient programs.
ABSTRACT DATA TYPES
(ADTS)
ADT’s are like user defined data types which defines operations on data using
functions without specifying implementation details.
The definition of ADT only mentions what operations are to be performed but not
how these operations will be implemented. It is called “abstract” because it gives an
implementation-independent view.
 DATA STRUCTURE?
•ADT is the logical picture of the data and the operations to manipulate the component
elements of the data. Data structure is the actual representation of the data during the
implementation and the algorithms to manipulate the data elements.

•In computer science, a data structure is a particular way of storing and organizing data
in a computer so that it can be used efficiently.

•Data may be organized in many different ways, the logical or mathematical model of
a particular organization of data in memory or on disk is called Data Structure.

Algorithms are used for manipulation of data.

 space for each data item it stores

Traversing
Accessing each record exactly once so that certain items in the record may be processed.(This
accessing or processing is sometimes called 'visiting" the records.)

Searching
Finding the location of the record with a given key value, or finding the locations of all
records, which satisfy one or more conditions.

Inserting
Adding new records to the structure.

Deleting
Removing a record from the structure.
TYPES OF DATA STRUCTURES
Linear Data Structure Non- Linear Data Structure
data structure is said to be linear A non-linear structure is mainly used
if its elements form a sequence, to represent data containing a
or in other words a linear list. hierarchical relationship between
elements.
Array
Tree
Stack
Graph
Queue
Linked List
ALGORITHM? WHY ANALYSIS
OF ALGORITHM?

GOAL???
 CHARACTERISTIC OF
DATA STRUCTURE
Data Structure Advantages Disadvantages

Arrays Quick insertion, very fast access if index Slow search, Slow deletion, Fixed
is known size
Ordered Array Quicker search than unsorted array. Slow insertion and deletion, Fixed
size
Stack Provides last-in first-out access Slow access to other items
Queue Provides first-in first-out access Slow access to other items
Linked List Quick insertion and quick deletion Slow search
Binary Trees Quick search, insertion and deletion if tree Deletion algorithm is complex.
remains balance
Hash Table Very fast access if key known, Fast Slow deletion, access slow if key
insertion. not known, inefficient memory
usage
Heap Fast insertion ,deletion. Access to largest Slow access to other items
item
Graph Models real world situation Some algorithms are slow and
REVISION
POINTERS
Pointers are variables which hold addresses of other variables.
STRUCTURES

Books
STRUCTURES
A structure contains a number of data types grouped together.
These data types may or may not be of the same type.

struct book
{
char name ;
float price ;
int pages ;
};
struct book b1, b2, b3 ;
CALL BY VALUE & CALL BY
REFERENCE
main( )
{ int a = 10, b = 20 ;
swapv ( a , b ) ;
cout<< “ \n a = “ << a << “b =“<< b ;
}
swapv ( int x, int y )
{
int t ;

t = x ;
x = y ;
y = t ;
cout<< “ \n x =“ << x << “y = “ << y ;
}
 CALL BY REFERENCE
main( )
{ int a = 10, b = 20 ;
swapv ( &a , &b ) ;
cout<< “ \n a = “ << a << “b =“<< b ;
}
swapv ( int *x, int *y )
{
int t ;

t = *x ;
*x = *y ;
*y = t ;
}
WHY ARRAYS?
1. Construct 100 variables to store percentage marks obtained by 100 different
students, i.e. each variable containing one student’s marks.
2. Construct one variable (called array ) capable of storing or holding all the
hundred values.
Which option u choose??
WHAT IS ARRAY???
An array is a compound data type which allows a collection of data of the same type
to be grouped into a single object
Array is a set of data elements stored under the same name.
As with any data type to understand how to use an array one must know how such a
structure can be declared how data may be stored and accessed in the structure and
what operations may be performed using this new type
ARRAY DECLARATION
Let’s store marks of 5 students.
Basic Syntax:
 Datatype variable_name[size_of _array];
 Example:
int marks[5];

Declaration+ Initialization:
int marks[5]={78,26,31,54,76};
More on Initialization
 ARRAY ELEMENTS IN
MEMORY
What happens in memory
when we make this
int marks[4] ; declaration?
int marks[4]={12,34,15,29}

16 bytes get immediately reserved in

INDEX VALUE: 0 1 2 3
 SAMPLE PROGRAM
int main( )
{
int numbers[5];
cout << "Enter 5 numbers: ";
for (int i = 0; i < 5; ++i)
{
cin >> numbers[i];
}
return 0;
}
 ACTIVITY
Write a program that takes the marks out of 50 as input and find the following
Number of students that score above average.
Find the lowest marks.
Find the highest marks.
ACTIVITY 2
Write a program that implements the array BILLS which records bill amount for
each year from 2000 through 2020

Find the number NUM of years during where bill amount is more than 3000.
Print each year and the bill amount for that year.
END LECTURE 1