The Need for Data Structures
Data structures organize data
? more efficient programs.
More powerful computers ? more complex
applications.
More complex applications demand more
calculations.
Complex computing tasks are unlike our
everyday experience.
Organizing Data
Any organization for a collection of records
can be searched,processed in any order,
or modified.
The choice of data structure and algorithm
can make the difference between a
program running in a few seconds or many
days.
Efficiency
A solution is said to be efficient if it solves
the problem within its resource constraints.
– Space
– Time
? The cost of a solution is the amount of
resources that the solution consumes.
有效率的
资源限制
Selecting a Data Structure
Select a data structure as follows:
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.
Some Questions to Ask
? Are all data inserted into the data structure
at the beginning,or are insertions
interspersed with other operations?
? Can data be deleted?
? Are all data processed in some well-
defined order,or is random access
allowed?
Data Structure Philosophy
Each data structure has costs and benefits.
Rarely is one data structure better than
another in all situations.
A data structure requires:
– space for each data item it stores,
– time to perform each basic operation,
– programming effort.
原则、方法
Goals of this Course
1,Reinforce the concept that costs and
benefits exist for every data structure.
2,Learn the commonly used data structures.
– These form a programmer's basic data
structure ``toolkit.'‘
3,Understand how to measure the cost of a
data structure or program.
– These techniques also allow you to judge the
merits of new data structures that you or
others might invent.
Abstract Data Types
Abstract Data Type (ADT),a definition for a
data type in terms of a set of values and a
set of operations on that data type.
Each ADT operation is defined by its inputs
and outputs.
Encapsulation,Hide implementation details.
Data Structure
? A data structure is the physical
implementation of an ADT.
– Each operation associated with the ADT is
implemented by one or more subroutines in
the implementation.
? Data structure usually refers to an
organization for data in main memory.
? File structure is an organization for data on
peripheral storage,such as a disk drive.
Logical vs,Physical Form
Data items have both a logical and a
physical form.
Logical form,definition of the data item
within an ADT.
– Ex,Integers in mathematical sense,+,-
Physical form,implementation of the data
item within a data structure.
– Ex,16/32 bit integers,overflow.
Data Type
ADT:
Type
Operations
Data Items,
Logical Form
Data Items:
Physical Form
Data Structure:
Storage Space
Subroutines
Problems
? Problem,a task to be performed.
–Best thought of as inputs and matching
outputs.
–Problem definition should include
constraints on the resources that may
be consumed by any acceptable
solution.
? Problems ? mathematical functions
–A function is a matching between inputs
(the domain) and outputs (the range).
–An input to a function may be single
number,or a collection of information.
–The values making up an input are
called the parameters of the function.
–A particular input must always result in
the same output every time the function
is computed.
Algorithms and Programs
Algorithm,a method or a process followed to
solve a problem.
– A recipe.
An algorithm takes the input to a problem
(function) and transforms it to the output.
– A mapping of input to output.
A problem can have many algorithms.
Algorithm Properties
An algorithm possesses the following
properties:
– It must be correct.
– It must be composed of a series of concrete steps.
– There can be no ambiguity as to which step will be
performed next.
– It must be composed of a finite number of steps.
– It must terminate.
A computer program is an instance,or
concrete representation,for an algorithm
in some programming language.
-finiteness,Algorithm must complete after a finite
number of instructions have been executed.
-absence of ambiguity,Each step must be clearly
defined,having only one interpretation.
-definition of sequence,Each step must have a
unique defined preceding & succeeding step,
The first step (start step) & last step (halt step)
must be clearly noted,
-input/output,Number and types of required inputs
and results must be specified.
-feasibility,It must be possible to perform each
instruction,
Data structures organize data
? more efficient programs.
More powerful computers ? more complex
applications.
More complex applications demand more
calculations.
Complex computing tasks are unlike our
everyday experience.
Organizing Data
Any organization for a collection of records
can be searched,processed in any order,
or modified.
The choice of data structure and algorithm
can make the difference between a
program running in a few seconds or many
days.
Efficiency
A solution is said to be efficient if it solves
the problem within its resource constraints.
– Space
– Time
? The cost of a solution is the amount of
resources that the solution consumes.
有效率的
资源限制
Selecting a Data Structure
Select a data structure as follows:
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.
Some Questions to Ask
? Are all data inserted into the data structure
at the beginning,or are insertions
interspersed with other operations?
? Can data be deleted?
? Are all data processed in some well-
defined order,or is random access
allowed?
Data Structure Philosophy
Each data structure has costs and benefits.
Rarely is one data structure better than
another in all situations.
A data structure requires:
– space for each data item it stores,
– time to perform each basic operation,
– programming effort.
原则、方法
Goals of this Course
1,Reinforce the concept that costs and
benefits exist for every data structure.
2,Learn the commonly used data structures.
– These form a programmer's basic data
structure ``toolkit.'‘
3,Understand how to measure the cost of a
data structure or program.
– These techniques also allow you to judge the
merits of new data structures that you or
others might invent.
Abstract Data Types
Abstract Data Type (ADT),a definition for a
data type in terms of a set of values and a
set of operations on that data type.
Each ADT operation is defined by its inputs
and outputs.
Encapsulation,Hide implementation details.
Data Structure
? A data structure is the physical
implementation of an ADT.
– Each operation associated with the ADT is
implemented by one or more subroutines in
the implementation.
? Data structure usually refers to an
organization for data in main memory.
? File structure is an organization for data on
peripheral storage,such as a disk drive.
Logical vs,Physical Form
Data items have both a logical and a
physical form.
Logical form,definition of the data item
within an ADT.
– Ex,Integers in mathematical sense,+,-
Physical form,implementation of the data
item within a data structure.
– Ex,16/32 bit integers,overflow.
Data Type
ADT:
Type
Operations
Data Items,
Logical Form
Data Items:
Physical Form
Data Structure:
Storage Space
Subroutines
Problems
? Problem,a task to be performed.
–Best thought of as inputs and matching
outputs.
–Problem definition should include
constraints on the resources that may
be consumed by any acceptable
solution.
? Problems ? mathematical functions
–A function is a matching between inputs
(the domain) and outputs (the range).
–An input to a function may be single
number,or a collection of information.
–The values making up an input are
called the parameters of the function.
–A particular input must always result in
the same output every time the function
is computed.
Algorithms and Programs
Algorithm,a method or a process followed to
solve a problem.
– A recipe.
An algorithm takes the input to a problem
(function) and transforms it to the output.
– A mapping of input to output.
A problem can have many algorithms.
Algorithm Properties
An algorithm possesses the following
properties:
– It must be correct.
– It must be composed of a series of concrete steps.
– There can be no ambiguity as to which step will be
performed next.
– It must be composed of a finite number of steps.
– It must terminate.
A computer program is an instance,or
concrete representation,for an algorithm
in some programming language.
-finiteness,Algorithm must complete after a finite
number of instructions have been executed.
-absence of ambiguity,Each step must be clearly
defined,having only one interpretation.
-definition of sequence,Each step must have a
unique defined preceding & succeeding step,
The first step (start step) & last step (halt step)
must be clearly noted,
-input/output,Number and types of required inputs
and results must be specified.
-feasibility,It must be possible to perform each
instruction,
