Transcript data structure

DATA STRUCTURE
&
ALGORITHMS
(BCS 1223)
NURUL HASLINDA NGAH
SEMESTER 2 2013/2014
What is Data Structure?
• Physically, RAM is a random accessible array of
bits.
• The computer will interpret bits as an address
(pointer)
What is Data Structure?
Digital data must be:
1. Encoded (binary  wave)
2. Arranged (stored in an orderly way in
memory / disk)
3. Accessed (insert new data, remove old data,
find data matching some condition)
4. Processed (algorithms: shortest path, etc)
Data Structuring
• How do we organize information so that we
can find, update, add and delete portions of it
efficiently
Data Structure Example Application
• How does Google quickly find web pages that
contain a search term?
• What’s the fastest way to broadcast a message
to a network of computers?
• How can a subsequence of DNA be quickly
found within the genome?
• How does your operating system track which
memory (disk or RAM) is free?
So, what is Data Structure?
• Its an agreement about:
– How to store a collection of objects in memory
– What operations we can perform for those
operations
– How time and space efficient those algorithms are
Data Organization Principles
• Ordering
– Put keys into some order so that we know
something about where each key is relative to the
other keys
– Phone books are easier to search because they are
alphabetized
Data Organization Principles
• Linking
– Add pointers to each record so that we can find
related records quickly
– E.g. the index in the back of book provides links
from words to the pages on which they appear
Data Organization Principles
• Partitioning
– Divide the records into 2 or more groups, each
group sharing a particular property
– E.g. Multi-volume encyclopedia
– E.g. Folders on your hard drive
Data Structure in Data Design
• Data structure consists of files or tables that
are linked in various ways
– A file or table contains data about people, places or events or
any important data that the business must kept information
about
– Depending on how the system’s file and tables are organized
and linked, an (IS) is called either
– File-oriented system: also called a file processing system, stores
and manages data in one or more separate files.
– Database system: consists of linked data files, also called tables,
that form an overall data structure. Compared to file processing,
a database environment offers greater flexibility and efficiency.
File Processing
– Companies mainly use file processing to handle
large volumes of structured data on a regular basis
– File processing design approach was well suited to
mainframe hardware and batch input
– File processing design is less common today, file
processing can be more efficient and cost less
than a DBMS in certain situations
File Processing Advantages
• Simplicity: the design of file processing is more
simple than designing Database
• Efficiency: file processing cost less and can be
more speed than Database
• Customization: you can customize file processing
more easily and efficiently than Database
because files are related with the application and
it have all the data needed for that application
File Processing Problems
• Data redundancy: occurs when data common to two or more
information systems is stored in several places. Data redundancy
requires more storage space, and maintaining and updating data in
several locations is expensive.
• Data integrity: Refers to the validity of data. Data integrity can be
compromised in a number of ways: human errors when data is
entered, errors that occur when data is transmitted from one
computer to another, software bugs or viruses, hardware
malfunctions, such as disk crashes and natural disasters, such as
fires and floods.
• Rigid data structure: A data structure that is hard to work with and
inflexible. File-processing is rigid when compared to a typical
database management system.
Database
• A Database is a collection of stored
operational data used by the application
systems of some particular enterprise (C.J.
Date)
– Paper “Databases”
• Still contain a large portion of the world’s knowledge
– File-Based Data Processing Systems
• Early batch processing of (primarily) business data
– Database Management Systems (DBMS)
Database
Advantages of Database
•
•
•
•
•
•
•
Scalability
Better support for client/server system
Economy of scale
Flexible data sharing
Controlled redundancy
Better security
Data independence
ADT
• An abstract data type (ADT) is a mathematical model
for a certain class of data structures that have similar
behavior; or for a certain of one or more
programming languages that have similar semantics
• It is defined indirectly, only by the operations that
may be performed on it and by mathematical
constraints on the effect of those operations
ADT
• For example, an abstract stack could be
defined by three operations:
– Push : insert some data item onto the structure
– Pop: extracts an item from stack
– Peek/Top: allows data on top of the structure to
be examined without removal
Advantages of ADT
• Encapsulation – it provides a promise that any
implementation of ADT has certain properties and abilities.
Users does not need any technical knowledge of how the
implementation works to use the ADT
• Localization of change – code that uses an ADT object will not
need to be edited if the implementation of the ADT is
changed.
• Flexibility – different implementation of ADT, having all the
same properties and abilities, are equivalent and may be used
somewhat interchangeably in code that uses the ADT.
Objects & Classes
• One of the benefits of object oriented
programming approach is we can define the
object and class
• A class is used to specify the form of an object
and it combines data representation and
methods for manipulating that data into one
neat package. The data and functions within a
class are called members of the class.
Example of class & object in C++
class Box
{
public: double length; // Length of a box
double breadth; // Breadth of a box
double height; // Height of a box
};
Algorithms
• Algorithm is a well defined computational
procedure that takes some value or a set of
values, as input & produces some value or a
set of values, as output
• A sequence of computational steps that
transform the input into the output
Example of Algorithm
• Adding into stack
procedure add(item : items);
{add item to the global stack stack;
top is the current top of stack
and n is its maximum size}
begin
if top = n then stackfull;
top := top+1;
stack(top) := item;
end: {of add}
Example of Algorithm
• Recursive Algorithms
int power( int num, int exponent )
{
if ( exponent == 1 ) return num;
else
return num * power( num, exponent - 1 );
}
Data Structure Techniques
• Linear Data Structure
–
–
–
–
Array – dynamic, sparse, matrix, etc.
Linked List – unrolled, doubly, Vlist, etc.
Stack & Queue
Associate array – hash, etc.
• Non-linear data structure
– Graph data structure – scene graph, binary tree, heap, etc.
– Tree data structure – search tree, syntax, etc.
End of chapter