Subject: Data Structure Course: Third Lecturer: 1: Dr. Bzar Khidir Hussan 2019-2020

Download as ppt, pdf, or txt
Download as ppt, pdf, or txt
You are on page 1of 18

Subject: Data structure

Course: Third
Lecturer: 1

Dr. Bzar khidir Hussan


2019-2020
Outline
Data:
Structure:
Data Structure:
Why study data structures?
CLASSIFICATION OF DATA STRUCTURE
Characteristics of a Data Structure
Type of Data structure:
Categories of Data Structure:
1.Linear Data Structure:
2.2. Non-linear Data Structure:
Data Structures Operations:
How to Choose the Right Graphic Structure :
Data:
Data are simply collection of facts and figures. Data are values or set of
values. A data item refers to a single unit of values.
values
Data items that are divided into sub items are group items;
items those that
are not are called elementary items.
items
For example, a student’s name may be divided into three sub items
[first name, middle name and last name]
but the ID of a student would normally be treated as a single item.

In the above example ( ID, Age, Gender, First, Middle, Last, Street, Area )
are elementary data items,
items whereas (Name, Address ) are group data items
Data:
Factual information (as measurements or
statistics) used as a basis for reasoning,
discussion, or calculation.

Structure:
Arrangement or relationship of elements as
particles, parts, or organs in a substance,
body, or system.

Data Structure:
Refers to the study of data and how to
represent data objects within a program;( the
implementation of structured relationships).
Why study data structures?
The major advantages of data structures are:
Programs are comprised of two things:
Data
 Algorithms.
The algorithms describe the way the data is to be transformed

The reason for learning about data structures is because


adding structure to our data can make the algorithms much
Simpler
Easier to maintain
Often faster.
Also, it tells how data can be stored and accessed in its
elementary level
CLASSIFICATION OF DATA STRUCTURE
Data structures are broadly divided into two :
1. Primitive data structures : These are the basic data
structures and are directly operated upon by the machine
instructions, which is in a primitive level. They are integers,
floating point numbers, characters, string constants, pointers
etc. These primitive data structures are the basis for the
discussion of more sophisticated (non-primitive) data
structures in this book.
 
2. Non-primitive data structures : It is a more sophisticated
data structure emphasizing on structuring of a group of
homogeneous (same type) or heterogeneous (different type)
data items. Array, list, files, linked list, trees and graphs fall
in this category.
Characteristics of a Data Structure

Correctness − Data structure implementation


should implement its interface correctly.
 Time Complexity − Running time or the execution
time of operations of data structure must be as
small as possible.
Space Complexity − Memory usage of a data
structure operation should be as little as possible
:Type of Data structure

Physical structure:   Means the material or space that


stores or represents the data in the memory you deal
.with in a single matrix of reservoir locations

Logical structure: It is the programming format or


method in which the programmer handles that data

Categories of Data Structure:

The data structure can be classified in to major types:


Linear Data Structure
Non-linear Data Structure
1. Linear Data Structure:
A data structure is said to be linear if its elements form
any sequence. There are basically two ways of
representing such linear structure in memory.

a)One way is to have the linear relationships between the


elements represented by means of sequential memory
location.
location These linear structures are called arrays.

b) The other way is to have the linear relationship


between the elements represented by means of pointers
or links.
links

These linear structures are called linked lists.


The common examples of linear data structure are
Arrays
Queues
2. Non-linear Data Structure:
This structure is mainly used to represent data
containing a hierarchical relationship between
elements. e.g. graphs, family trees and table of
contents.
Arrays:
The simplest type of data structure is a linear (or one
dimensional) array. A list of a finite number n of
similar data referenced respectively by a set of n
consecutive numbers, usually 1, 2, 3 . . . . . . . n. if
we choose the name A for the array, then the
elements of A are denoted by subscript notation
A 1, A 2, A 3 . . . . A n
or by the parenthesis notation
A (1), A (2), A (3) . . . . . . A (n)
or by the bracket notation
A [1], A [2], A [3] . . . . . . A [n]
Example:
A linear array A[8] consisting of numbers is pictured
in following figure.
Stack:

It is an ordered group of homogeneous items of


elements. Elements are added to and removed from the
top of the stack (the most recently added items are at
the top of the stack). The last element to be added is the
first to be removed (LIFO:Last In, First Out).

Queue:

A queue, also called FIFO system, is a linear list in which


deletions can take place only at one end of the list, the
Font of the list and insertion can take place only at the
other end Rear.
Linked List:
A linked list, or one way list is a linear collection
of data elements, called nodes, where the
linear order is given by means of pointers.
pointers Each
node is divided into two parts:
The first part contains the information of
the element/node
The second part contains the address of the
next node (link /next pointer field) in the
list.
There is a special pointer Start/List contains
the address of first node in the list. If this
special pointer contains null, means that List is
empty.
Tree:
Data frequently contain a hierarchical
relationship between various elements.
The data structure which reflects this relationship
is called a rooted tree graph or, simply, a tree.
Graph:
Data sometimes contains a relationship between pairs of
elements which is not necessarily hierarchical in nature,
e.g. an airline flights only between the cities connected by
lines. This data structure is called Graph.
Data Structures Operations:

The following four operations play a major role in this


text:

Traversing: accessing each record/node exactly once


so that certain items in the record may be processed.
(This accessing and processing is sometimes called
“visiting” the record.)
Searching: Finding the location of the desired node
with a given key value, or finding the locations of all
such nodes which satisfy one or more conditions.
 Inserting: Adding a new node/record to the
structure.

 Deleting: Removing a node/record from the structure.


How to Choose the Right Graphic Structure
:
- Data size
- Speed ​and method of data usage
- The dynamic nature of data as modified and
modified periodically.
- Required storage capacity.
- Time to retrieve any information.
- Programming method.

You might also like