Transcript Figure 11-14 Traversing a list

Chapter 11
Data
Structures
©Brooks/Cole, 2003
OBJECTIVES
After reading this chapter, the reader should
be able to:
Understand arrays and their usefulness.
Understand records and the difference between an array and
a record.
Understand the concept of a linked list and the difference
between an array and a linked list.
Understand when to use an array and when to use a linked-list.
©Brooks/Cole, 2003
11.1
ARRAYS
©Brooks/Cole, 2003
Figure 11-1
Twenty individual variables
©Brooks/Cole, 2003
Figure 11-2
Processing individual variables
©Brooks/Cole, 2003
Figure 11-3
Arrays with subscripts(下標) and indexes
©Brooks/Cole, 2003
Figure 11-4
Processing an array
©Brooks/Cole, 2003
Array Applications

Frequency arrays
– A frequency array shows the number of
elements with the same value found in a series
of numbers. (Fig. 11.5)

Histograms
– A histogram is a pictorial (圖示的)
representation of a frequency array. (Fig. 11.6)
©Brooks/Cole, 2003
Figure 11-5
Frequency array
©Brooks/Cole, 2003
Figure 11-6
Histogram
©Brooks/Cole, 2003
Figure 11-7- Part I
Two-dimensional array
©Brooks/Cole, 2003
Figure 11-8
Memory layout

“Row-major” storage
©Brooks/Cole, 2003
11.2
RECORDS
©Brooks/Cole, 2003
Records
A record is a collection of related elements,
possibly of different types, having a single
name.
 Each element in a record is called a field.
 A field is the smallest element of named
data that has meaning.
 Fig. 11.9

©Brooks/Cole, 2003
Figure 11-9
Records
©Brooks/Cole, 2003
Note:
The elements in a record can be of
the same or different types. But all
elements in the record must be
related.
©Brooks/Cole, 2003
11.3
LINKED
LISTS
©Brooks/Cole, 2003
Linked lists
A linked list is a ordered collection of data
in which each element contains the
location of the next element.
 Each element contains two parts:

– Data: the data parts holds the useful
information
– Link: the link is use to chain the data together

Example: singly linked list (Fig. 11.10)
©Brooks/Cole, 2003
Figure 11-10
Linked lists

Null pointer: indicate the end of the list
©Brooks/Cole, 2003
Figure 11-11
Node

A node in a linked list is a record that has
at least two fields: one contains the data,
and the other contains the address of the
next node in the sequence
©Brooks/Cole, 2003
Operations on linked lists
Inserting a node
 Deleting a node
 Searching a list
 Retrieving a node
 Traversing a list
 Coping a list … and so on

©Brooks/Cole, 2003
Figure 11-12
Inserting
a node
©Brooks/Cole, 2003
Figure 11-13
Deleting a node
©Brooks/Cole, 2003
Figure 11-14
Traversing a list
©Brooks/Cole, 2003
Key terms











Array
Data structure
Field
Frequency array
Histogram
Link
Linked list
Loop
Memory
Node
Null pointer









One-dimensional array
Pointer
Record
Row-major storage
Search a list
Singly linked list
Subscript
Two-dimensional array
Variable
©Brooks/Cole, 2003