Data Structures
Introduction
Lec-1
22-Sep-18 1
DATA STRUCTURES
Very important subject
Have already studied Introduction to programming using C
and C++ and used some data structures
Focus was on how to carry out programming with the use of
C and C++ languages besides the resolution of different
problems.
22-Sep-18 2
DATA STRUCTURES
In this course, we will continue problem solving and see that
the organization of data in some cases is of immense
importance.
Therefore, the data will be stored in a special way so that the
required result should be calculated as fast as possible.
22-Sep-18 3
GOALS OF THIS COURSE
Cover well-known data structures such as
Arrays
Linked lists
Stacks
Queues
Tree
Graphs.
Implementation
22-Sep-18 4
GRADING POLICY
Mid Term 20
Final Term 50
Practical / LAB Assignments 20
Quizzes 10
Total 100
Note= 75% Attendance is compulsory for Exams 22-Sep-18
5
REFERENCE MATERIALS:
1. Data Structure by Seymour Lipschutz (Schaum’s Series)
2. Data Structures and Algorithm Analysis, Mark Allen
Weiss, Florida International University, Addison-Wesley
(latest Edition)
3. Data Structures: Abstraction and Design Using Java,
Koffman and Wolfgang, Wiley; 2nd Edition (or latest
Edition), 2010
4. Data Structures and Algorithms in C++, Adam Drozdek,
Course Technology; 4th Edition, 2012.
22-Sep-18
5. Data Structures in C++ by Aikman Series
6
6. Data Structure by Reingold & lipschutz
NEED FOR DATA STRUCTURES
Data structures organize data more efficient programs.
More powerful computers more complex applications.
More complex applications demand more calculations.
22-Sep-18 7
ORGANIZING DATA
Data should be arranged in a way that it is easily accessible.
The choice of data structure and algorithm can make the
difference between a program running in a few seconds or
many days (Time Complexity).
22-Sep-18 8
EFFICIENCY
A Program / solution is said to be efficient if it solves the
problem within its resource constraints.
Space
Time
The cost of a solution is the amount of resources that the
solution consumes.
22-Sep-18 9
EFFICIENCY
This means that we have to write programs considering the
resources to achieve some solution as soon as possible.
The cost of a solution is the amount of resources (Memory /
Running Time) that the solution consumes.
22-Sep-18 10
SELECTING A DATA STRUCTURE
Select a data structure as follows:
1. Analyze the problem to determine the resource constraints a
solution must meet.
2. Determine the basic operations that must be supported.
3. Select the data structure that best meets these requirements.
22-Sep-18 11
DATA STRUCTURE PHILOSOPHY
Each data structure has costs/Disadvantages and benefits.
In different situations, different data structures will be suitable.
22-Sep-18 12
PHYSICAL DATA REPRESENTATION
22-Sep-18 13
PHYSICAL DATA REPRESENTATION
Data are simply values or set of values
A data item refers to a single unit of values
Data items group items / elementary items
22-Sep-18 14
PHYSICAL DATA REPRESENTATION
An entity is something that has certain attributes or properties
which may be assigned values
Field is a single elementary unit of information representing a
property of an entity
Record is the collection of field values of a given entity
22-Sep-18 15
PHYSICAL DATA REPRESENTATION
File is the collection of records
Each record in a field may contain many field items, but the
value in a certain field may uniquely determine the record in the
file primary key
22-Sep-18 16
FILE ORGANIZATIONS
22-Sep-18 17
FILE ORGANIZATIONS
The structure of a file (especially a data file), defined in
terms of its components and how they are mapped onto
backing store(secodary memory ).
basic factor which determines the organization of a file
is the nature of operations that are to be performed on the
files.
22-Sep-18 18
FILE ORGANIZATIONS
The possible operations performed can be:
– Retrieval
– Processing
– Selection
– Updation
– Deletion
22-Sep-18 19
FILE ORGANIZATIONS
Organization of files depend upon:
– File storage access method
– Number of records, record size, block size and hence
size of the file
– Length of records either fixed or variable
22-Sep-18 20
FILE ORGANIZATIONS
Organization of files depend upon:
– Frequency of operations to be performed
– Response time required to complete an operation
– Security provisions for data handling
22-Sep-18 21
FILE ORGANIZATIONS
Keeping in view these points, there are three commonly
used file organizations.
1. Sequential Files
2. Index Sequential Files
3. Direct or Random Access Files
22-Sep-18 22
SEQUENTIAL FILES
Records are stored one after the other on a storage
device based on the value of the search key of each
record.
Processing same order
All secondary storage devices support sequential file
organization.
Access time varies according to location Why?
22-Sep-18 23
SEQUENTIAL FILES
To arrive at a certain location means to pass through all
the precedence locations.
More time taken in sorting and merging them
The next figure shows a record of a sequential file.
22-Sep-18 24
SEQUENTIAL FILES
22-Sep-18 25
SEQUENTIAL FILES
Storage devices on which we can store in this manner are
Before > Punched Cards
Now > Magnetic Disks, Magnetic Tapes
Advantages ?
Disadvantages ?
22-Sep-18 26
DISADVANTAGES OF SEQUENTIAL
FILE ORGANIZATION
• To access a specific file, we need to access all the previous
files.
• Process is slow in huge files.
• Files are stored one after another, there is gap between the
file to insert new.
• Difficult to delete the record, all the records will be
rearranged.
DIRECT/RANDOM ACCESS
FILES
Each has unique address location>separate field or extracted
through hashing
22-Sep-18 29
DIRECT FILE ORGANIZATION:
It overcomes the problem of sequential method
Records stored at random places
Each record accessed directly irrespective of its location
Access desired record randomly or directly.
Individual address is allocated to each record of the file.
Using fields key value we can access the desired record without
access the previous record.
Online ticket reservation is an example.
DFO can be created on magnetic Disks but not in magnetic tapes.
DIRECT/RANDOM ACCESS
FILES
Advantages ?
No need of separate transaction file
Fast retrieval of records
Disadvantages ?
Possibility of less efficient use of storage space
Collision
22-Sep-18 31
INDEX SEQUENTIAL FILES
Have qualities of both sequential and direct methods
Records stored in sorted order by record key as sequential
method
An index also maintained for direct accessing as direct
method
The index consists of record keys and their corresponding
addresses
22-Sep-18 32
INDEX SEQUENTIAL FILES
The index is searched and the key is located which then
provides the address for access
Thus as file is sequential but can be updated randomly
Devices > Magnetic Disks, Magnetic Drums
22-Sep-18 33
22-Sep-18 34
INDEX SEQUENTIAL FILES
Advantages ?
When activity ratio less efficiently use of sequential
method
When activity ratio more efficiently use of direct
method
Disadvantages ?
Extra storage required
Access of a record slower than the direct files
22-Sep-18 35
ASSIGNMENT # 1
Solve questions of Schaum’s Series book in your own words
1.1
1.2
1.3
1.4
22-Sep-18 36
