Transcript contents and introduction to data structure

Lessons:
•
•
•
•
Introduction to Data Structures
Computer Memory
Pointers and Indirection
Linear Data Structures
–
–
–
–
–
–
•
Nonlinear Data Structures
–
–
–
•
•
Ordered List: The Abstract View
Ordered List: The Implementation View
Stacks: The Abstract View
Stacks: The Implementation View
Queues: The Abstract View
Queues: The Implementation View
Multidimensional arrays
Trees
Graphs
Abstract Data Types
Summary
created on 29/10/2008
yahaya.wordpress.com
1
Learning objectives:
• Show how data structures map onto
physical memory.
• Identify linear versus nonlinear data
structures.
• Manipulate data structures with basic
operations.
• Compare different implementations of the
same data structure.
created on 29/10/2008
yahaya.wordpress.com
2
Introduction:
•
The following lessons introduce the topic of data structures by
comparing how data is actually stored in a computer with the
abstract structures that programmers use. To illustrate this
comparison, several basic data structures such as lists, stacks,
and queues are described. Each lesson includes a set of review
questions which test the important concepts from the lesson and
provide practice problems. After reading each lesson, you
should work the review questions before proceeding to the next
lesson. Use the navigation bar at the top of this page to view the
lessons and access the review questions. Each lesson page
has a link on the navigation bar which will take you to the review
questions for that lesson. To begin your study, click at the top
of this page.
•
created on 29/10/2008
yahaya.wordpress.com
3
Introduction:
• Imagine that you are hired by company
XYZ to organize all of their records into a
computer database. The first thing you are
asked to do is create a database of names
with all the company's management and
employees. To start your work, you make
a list of everyone in the company along
with their position.
created on 29/10/2008
yahaya.wordpress.com
4
Introduction:
created on 29/10/2008
Name
Position
Aaron
Manager
Charles
VP
George
Employee
Jack
Employee
Janet
VP
John
President
Kim
Manager
Larry
Manager
Martha
Employee
Patricia
Employee
Rick
Secretary
Sarah
VP
Susan
Manager
Thomas
Employee
Zack
Employee
yahaya.wordpress.com
5
Introduction:
• But this list only shows one view of the company.
You also want your database to represent the
relationships between management and
employees at XYZ. Although your list contains
both name and position, it does not tell you
which managers are responsible for which
workers and so on. After thinking about the
problem for a while, you decide that a tree
diagram is a much better structure for showing
the work relationships at XYZ.
created on 29/10/2008
yahaya.wordpress.com
6
Introduction:
created on 29/10/2008
yahaya.wordpress.com
7
Introduction:
• These two diagrams are examples of different data structures. In
one of the data structures, your data is organized into a list. This is
very useful for keeping the names of the employees in alphabetical
order so that we can locate the employee's record very quickly.
However, this structure is not very useful for showing the
relationships between employees. A tree structure is much better
suited for this purpose.
• In computer science, data structures are an important way of
organizing information in a computer. Just like the diagrams above
illustrate, there are many different data structures that programmers
use to organize data in computers. Some data structures are similar
to the tree diagram because they are good for representing
relationships between data. Other structures are good for ordering
data in a particular way like the list of employees. Each data
structure has unique properties that make it well suited to give a
certain view of the data.
created on 29/10/2008
yahaya.wordpress.com
8
Introduction:
• During these lessons, you will learn how data structures
are created inside a computer. You will find there is quite
a difference between your mental picture of a data
structure and the actual way a computer stores a data
structure in memory. You will also discover that there are
many different ways of creating the same data structure
in a computer. These various approaches are tradeoffs
that programmers must consider when writing software.
Finally, you will see that each data structure has certain
operations that naturally fit with the data structure. Often
these operations are bundled with the data structure and
together they are called a data type. By the end of this
study, you should be able to do the following:
created on 29/10/2008
yahaya.wordpress.com
9
Introduction:
• Show how data structures are represented
in the computer,
• Identify linear and nonlinear data
structures,
• Manipulate data structures with basic
operations, and
• Compare different implementations of the
same data structure
created on 29/10/2008
yahaya.wordpress.com
10