List.ppt
Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2 MB, 60 trang )
Chapter 8
Lists
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-2
Chapter Objectives
•
Examine list processing and various
ordering techniques
•
Define a list abstract data type
•
Demonstrate how a list can be used to
solve problems
•
Examine various list implementations
•
Compare list implementations
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-3
Lists
•
Lists are linear collections, like stacks and
queues, but are more flexible
•
Adding and removing elements in lists are
not restricted by the collection structure
•
That is, they don't have to operate on one
end or the other
•
We will examine three types of list
collections:
–
ordered lists
–
unordered lists
–
indexed lists
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-4
Ordered Lists
•
The elements in an ordered list are
ordered by some inherent
characteristic of the elements
–
names in alphabetical order
–
scores in ascending order
•
Therefore, the elements themselves
determine where they are stored in the
list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-5
FIGURE 8.1 A conceptual view of
an ordered list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-6
Unordered Lists
•
There is an order to the elements in an
unordered list, but that order is not based on
element characteristics
•
The user of the list determines the order of
the elements
•
A new element can be put on the front or the
rear of the list, or it can be inserted after a
particular element already in the list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-7
FIGURE 8.2 A conceptual view of
an unordered list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-8
Indexed Lists
•
In an indexed list, elements are referenced
by their numeric position in the list
•
Like an unordered list, there is no inherent
relationship among the elements
•
The user can determine the order
•
Every time the list changes, the indexes are
updated
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-9
FIGURE 8.3
A conceptual view of an indexed list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-10
List Operations
•
There are several operations common to all
three list types
•
These include removing elements in various
ways and checking the status of the list
•
The key differences between the list types
involve the way elements are added
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-11
FIGURE 8.4
The common operations on a list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-12
FIGURE 8.5 The operation
particular to an ordered list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-13
FIGURE 8.6 The operations
particular to an unordered list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-14
FIGURE 8.7 The operations
particular to an indexed list
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-15
List Operations
•
As with other collections, we use Java
interfaces to define the collection operations
•
Recall that interfaces can be defined via
inheritance (derived from other interfaces)
•
We define the common list operations in one
interface, then derive three others from it that
define the interfaces of the three list types
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-16
FIGURE 8.8
The various list interfaces
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-17
Listing 8.1
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-18
Listing 8.1 (cont.)
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-19
Listing 8.2
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-20
Listing 8.3
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-21
Listing 8.4
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-22
Listing 8.4 (cont.)
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-23
Tournament Maker
•
Let's use an ordered list to help manage a
bowling tournament
•
Teams are ordered by their number of wins
in the regular season
•
To create the first round match-ups, the
team with the best record is matched against
the team with the worst record
•
The second best team is matched against
the second worst team, etc.
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-24
FIGURE 8.9 Bowling league team
names and number of wins
Copyright © 2005 Pearson
Addison-Wesley. All rights
reserved. 8-25
FIGURE 8.10 Sample tournament layout
for a bowling league tournament
![Moi gioi BAT DONG SAN 01[1].ppt](https://media.store123doc.com/images/document/12/gu/pr/medium_VqscYiF6ld.jpg)
