Transcript data structure

CS 350
Data Structures
Chaminade University of Honolulu
1
Introduction






Why Data Structures?
What Is Data Structure?
Program Efficiency
Example: Banking Application
Example: City Database
Abstract Data Type
2
Why Data Structures?



Main function of computers is to perform
calculations—fast, and efficiently.
Complex jobs require intensive calculations
How do you make computers work efficiently?



Hardware
Software
Software solution


Algorithms
Algorithms depend on data structures
3
What Is a Data Structure?


In a general sense, any data
representation is a data structure.
E.g., integer, string
Specifically, data structure is an
organization for a collection of data items.

You choose appropriate data structure for
efficient processing of data.
4
Data Structure and Algorithm


Different data structures can be used for
processing data—searching, sorting,
modifying, etc.
But the choice of data structure, and
accompanying algorithm can make the
difference between a fast program (sec,
min) and a long program (hrs, days).
5
Program Efficiency

A program is said to be efficient if it solves a
problem without wasting computing
resources of:



Space
Time
The cost of a (program) solution is the
amount of resources that the solution
consumes.
6
Example: Banking Application

Typical Operations




Open accounts (far less often than access)
Close accounts (far less often than access)
Access account to Add money
Access account to Withdraw money
7
Banking Application (cont.)


Teller and ATM transactions are
expected to take short time (minutes).
Opening or closing an account can take
longer time (perhaps up to an hour).
8
Banking Application (cont.)

Kind of data structure for this
application:
 Must be highly efficient for search
of account


May be less
account
efficient for deletion of
May be moderately efficient for
insertion of account
9
Banking Application (cont.)

Hash Table
Meets these requirements
 Allow for extremely fast records search.
 Also supports efficient insertion of new
records.
 Deletions can also be supported efficiently.
(But too many deletions lead to
performance degradation–requiring the
hash table to be reorganized.)

10
Example: City Database



Database system for city information
Search by particular value--e.g., ZIP
code, street name, building name-(exact match)
Search by range of values--e.g.,
population, income level—(range query)
11
City Database (cont.)

The database must answer queries quickly


For an exact-match query, fast operation
(seconds)
For a range queries, the entire operation may be
allowed to take longer (minutes)
12
City Database (cont.)

The hash table is inappropriate because it

The B+ tree supports large databases for:
cannot perform efficient range queries




Insertion
Deletion
Range queries
If the database is created once and then
never changed, simple linear lists may be
more appropriate.
13
Selecting a Data Structure
Selection Criteria for a Data Structure
1.
Analyze the problem to determine the
resource constraints a solution must meet.
2.
Determine the basic operations that must be
supported. Quantify the resource constraints
for each operation.
3.
Select the data structure that best meets
these requirements.
14
Data Structure Philosophy
Each problem has constraints on available space
and time.
Only after a careful analysis of problem
characteristics can we know the best data
structure for the task.
Bank example:



Start account: a few minutes
Transactions: a few seconds
Close account: overnight
15
Goals of this Course

Reinforce the concept that costs and benefits
exist for every data structure


Learn commonly used data structures


Choice of data structure is important for complex
processing
Programmer's basic data structure “toolkit”
Understand how to measure the cost of a data
structure or program.

Algorithm analysis
16
Abstract Data Type

Abstract Data Type (ADT):
specification for a data type solely in terms
of


a set of values
a set of operations on that data type
17
Abstract Data Type (cont.)

Humans handle complexity in hierarchy of
abstraction


E.g., dogruns, barks, eats
dogruns with legs
barks with lungs, mouth
eats with mouth, stomac
E.g., listinsert item, remove item, search
listdata in array
insert item into array
remove item by overwriting
use binary search algorith
18
Abstract Data Type (cont.)


ADT provides a set of (high-level)
operations as an interface to the
outside world
Data Structure and algorithm provides
the (low-level) implementation of the
abstract operations
19
Abstract Data Type (cont)


Information Hiding
Principle of hiding the design and
implementation details of data structure
Encapsulation
Way to achieve information hidng. Often
used synonymously with information
hiding itself.
20
ADT and Data Structure

Data Structure





the physical implementation of an ADT.
Each operation in the ADT is implemented by one or
more subroutines in the implementation.
In a OO language, an ADT and its
implementation together make up a class.
Data Structure: usually refers to an organization
for data in main memory.
File Structure: an organization for data on
external storage, such as a disk drive.
21
Data Type
ADT:
Type
Operations
Data Items:
Logical Form
Data Structure:
Storage Space
Subroutines
Data Items:
Physical Form
22
Programs


A computer program is a concrete
representation of an algorithm in some
programming language.
Naturally, there are many programs
that are instances of the same
algorithms, since any modern
programming language can be used to
implement any algorithm.
23
To Summarize:



A problem is a function or a mapping of
inputs to outputs.
An algorithm is a recipe for solving a
problem whose steps are concrete and
ambiguous.
A program is an instantiation of an
algorithm in a computer programming
language.
24
Your Turn

Imagine that you are a shipping clerk for a large
company. You have just been handed about
1000 invoices, each of which is a single sheet of
paper with a unique large number in the upper
right corner. The invoices must be sorted by this
number, in order from lowest to highest. Write
down as many different approaches to sorting
the invoices as you can think of.
You can recruit your friend to help you.
25