0.Course Introduction
Goals of this Course
- Reinforce the concept that costs and benefits exist for every data
structure.
- Learn the commonly used data structures.
- These form a programmer’s basic data structure “toolkit”.
- 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.
Costs and Benefits
- Each data structure has costs and benefits.
- Rarely is one data structure better than another in all situations.
- Any data structure requires:
- space for each data item it stores,
- time to perform each basic operation,
- programming effort.
- Only after a careful analysis of problem characteristics can we
know the best data structure for a task.
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: 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: 32/64 bit integers, overflow.
Logical vs. Physical Form (2)
Data Type
ADT
Type
Operations
Data Items
Logical Form
Data Structure
Storage Space
Subroutines
Data Items
Physical Form