Transcript DFS_1_Introduction

Data Structure
•Data Structure:
–Structure:
•Way/Method to store something so that,
–The stored thing can be accessed quickly and efficiently.
•Examples:
–Room of your house:
»To store your belongings.
–Cupboard / Cabinet in your room:
»To store your important accessories such as clothes
etc.
–Hardbound Box files:
»To store your bills etc.
–Class:
»To store students.
–Data:
•Collection of facts and figures.
Data Structure
Marksheet
Whose Data?
Student’s Data
For which Entity?
Entity: Student
Attributes
Row / Record / Tuple
Entity Set
No Name
Gender
English
Maths
Total
1
Sachin
M
50
60
110
2
Sunita
F
50
40
90
3
Virat
M
40
60
100
Domain (Gender) = {M, F}
Domain (English) = {x / x varies from 0 to 100}
Question:
What is the importance of this data to a particular person?
Data Structure
•Data:
–Importance of data to a person depends on the:
•Person who is trying to see/analyze the data.
–Example:
•Importance of TYBCA marksheet data to a TYBBA student?
–Nothing.
•Importance of TYBCA marksheet data to a TYBCA student?
–Wants to know his own record.
–Might want to know his friend’s record.
•Importance of TYBCA marksheet to a BCA faculty?
–Wants to know the result of his subject.
•Importance of TYBCA marksheet to a Director?
–Wants to know the overall result of his college.
–Conclusion:
•Same data can have,
–Different meaning/importance to different people.
–This data / part of data with some meaning is called:
•Information
Data Structure
•Information:
–Information is:
•Processed Data / Meaningful Data which can be used to
take,
•Important decisions.
–Example:
•After seeing the information of his result, a student might
take a decision whether to:
–Continue studies,
–Continue in same college,
–Join some business.
•After seeing the information, a director might take a
decision whether to:
–Change subject faculty,
–Remove that faculty altogether.
Data v/s Information
Information-1
Data
Procedure
to
Process
Data
Information-2
Information-n
•Data & Information:
–There is a major difference between these
2 things.
–However many a times, both the words
‘Data’ & ‘Information’ are used
interchangeably.
Data Structure
•Data Structure:
–Way/Method to store data so that,
•Various processes (Searching, Filtering etc) can
be applied on that data and,
•Information from that stored data can be
accessed quickly and efficiently.
Tell the Structure?
Data: Books
Properly arranged by subject, author etc.
Randomly arranged on top of each other
Tell the Structure?
Data: Light Bills, Phone Bills, Water Bills of different months
In 3 different files
sorted by month etc.
Everything in a
single file.
Everything in a single file with markers.
Data Structure
•Data Structure:
–Way/Method to store data so that,
•Various processes (Searching, Filtering etc) can be applied on
that data and,
•Information from that stored data can be accessed quickly and
efficiently.
OR
–It is a triplet consisting of:
•D: (What is stored?)
–Data that can be stored in the structure.
•F: (Why it is stored?)
–Functions / Operations that can be done on the stored data.
•A: (How is it stored?)
–Axioms (Rules) to be applied when storing the data.
–So,
•Data Structure (DS) = (D, F, A)
Data Structure
•Data Structure:
–We are already aware about,
•The advantages of,
–Storing the same data in a computer than,
–Storing in a physical file / physical world.
•Example:
–Student’s marksheet stored on physical paper compared to
the same marksheet stored in some software (Excel) of
Computer.
–Advantages of storing data in a computer:
•More accessing speed and hence less time consuming.
•More accuracy.
•Changes / Modifications could be easily done.
•No problem of concentration.
–Not tempted and does not use Facebook.
•Will not get tired.
–Does not require food, drinks apart from electricity.
Data Structure
•Data Structure:
–How to store data in a computer?
•Examples:
–Student Marksheet:
»Microsoft Excel
–Letters:
»Microsoft Word
–Music Files:
»In different folders according to Genre.
–3D designs:
»3D Home Architect / AutoCad
–Dates:
»Excel, Database, ?
–Mathematical Equations such as Polynomials:
»?
–Family Tree of a Person:
»?
–Route / Path of a Flight:
»?
Data Structure
•Data Structure Using C:
–How to store data in a computer?
•By instructing the computer,
•By commanding the computer,
•By programming the computer using,
–Any programming language such as:
»C, C++, Java
Data Structure
•Data Structure Using C:
–Examples:
•34:
–int
•99.50:
–float
•‘a’:
–char
•List of roll numbers / List of marks:
–Array
•Family Tree:
–Tree
•Path / Route of a Flight:
–Graph
Data Structure
NonLinear
Linear
int
char
float
V/S
V/S
Array
Created
Built-In
9 7 3 0 5
9
7
3
0
5
Tree
Classification of Data Structures
Data Structures
Primitive
Basic
int
char
Non-Primitive
Classic
Non-Non-Primitive
Complex
Lattice
Petri Nets
float
boolean
Neural Nets
Search Graphs
Semantic Nets
Classification of Data Structures
Non-Primitive / Classic Data Structures
Linear
Array
Linked List
Stack
Non-Linear
Queue
Trees
Graphs
Tables
Sets