Transcript 01._introduction_to_datastructure(Mohsin Raza)

Introduction to Data Structures
1
WORDS OF WISDOM
•
We must understand that life is difficult, if we
know and accept it, it is no longer difficult.

• Do men think that they will be left alone on saying “We
believe” and that they will not be tested? We did test
those before them and Allah will certainly know those who
are true from those who are false”

Al-Quran (29:2-3).
Course Outline
1. Introduction & Overview
2. Preliminaries
3. string Processing
4. Arrays, Records
5. Linked List
6. Stack, Queues
7. Trees
8. Graphs & their applications
9. Sorting and searching
3
Book
“Data Structures”
by Seymour Lipschutz,
4
 Data,
 Data
information , entity, field, record, file
Structure.
 Types of
Data Structure.
 Algorithms.
 Searching
TOPIC TO BE DISCUSS
Elementary Data Organization
•
Data are simply values or sets of values. Data item may be divided into further sub item
called group item.
•
Entity is something that has certain attributes or properties which may be assigned
values.
•
Collection of data are frequently organized into a hierarchy of fields, records and files.
•
Field is single element unit of information or a
column in a table (holds data) For
instance, field is use to store single item. .
•
records is collection of field values of given entity. or is a row of data added to this table.
Record may be variable length or fix length have same data type and same amount of
space for each value.
•
6
File is collection of records.
• What
is Data Structure ?
• Why
7
it is used?

Data Structures
Data may be organized in many different ways; The logical or
mathematical model of a particular organization of data is called a data structure.
Structure should be simple enough that one can effectively process the data when
necessary. Choice of data structure depends on data type, frequency with which
various data operation are applied .
•
Data structure requires 3 basic things.

Space require to store data.

Time require for each basic function.

Programming effort.
Why use Data Structure?
Data structure help us to organize the data in the computer, resulting in more efficient
programs. An efficient program execute faster and helps minimize the use of resources
like memory disk.
8
Data Structures
 Types of Data Structure
1. Linear Data Structure
Example: Arrays, Linked Lists, Stacks, Queues
2. Nonlinear Data Structure
Example: Trees, Graphs
A
Array
A
B
C
D
E F
Tree
B
D
Figure: Linear and nonlinear structures
9
C
E
F
TYPES OF DATA STRUCTURE
•
Stack:- Stack is linear type data structure it is called last in firs out(LIFO). In
this
structure insertion and deletion can take place only at one end called top of the list.
Example is stack of dishes.
•
Queue is linear data structure. It is called first in first out(FIFO) in which deletion take
place only at one end of list the front and insertion take place only other end of queue the
rear of list.
Example people stay in row Waite for bus.

Link List is linear type data structure consisting of group of nodes, which together
represent a sequence. One contain data item and other contain reference.

Tree is non linear data structure. In tree data frequently contain hierarchical relationship
between various data elements. The data structure which reflect this relationship is called
rooted tree graph.
10
Data Structure Operations
1. Traversing: Accessing each record exactly once so that certain items in the
record may be processed.
2. Searching: Finding the location of the record with a given key value.
3. Inserting: Adding a new record to the structure.
4. Deleting: Removing a record from the structure.
5. Sorting: Arranging the records in some logical order.
6. Merging: Combing the records in two different sorted files into a single
sorted file.
11
Algorithms
It is a well-defined set of instructions used to solve a particular problem. Time and
space it uses are two major measure of the efficiency of an algorithm.
Complexity of Algorithm
•
The complexity of an algorithm M is the function f(n) which gives the running time
and/or storage space requirement of the algorithm in terms of the size n of the input
data.
•
Two types of complexity
1. Time Complexity
How long does this sorting program run? It possibly takes a very
long time on large inputs (that is many strings) until the program has completed its
work and gives a sign of life again.
12
CONTINUE
2. Space Complexity
The better the time complexity of an algorithm is, the faster the
algorithm will carry out his work in practice. Apart from time
complexity, its space complexity is also important: This is essentially
the number of memory cells which an algorithm needs. A good
algorithm keeps this number as small as possible, too.
13
Searching Algorithms
•
There are two types of searching.
I.
Linear Searching
II.
Binary Searching
Linear search
Search each record of the file, one at time, until finding the given
Name and hence the corresponding telephone number. It is simple form of
searching but it take more time if there is millions of records.
Binary search
Compare the given name with the name in the middle of list; this tells
which half of the list contain name. in this we need less comparison and we get
14
required data in less time.
Typical Growth Rates
Function
Name
c
Constant
logn
Logarithmic
log2n
Log-squared
n
Linear
nlogn
n2
Quadratic
n3
Cubic
2n
Exponential
15