Java Reference
In-Depth Information
Here are some comments on Program P1.7:
•
For our purposes, we assume that a word begins with a letter and consists of letters only.
If you want to include other characters (such as a hyphen or apostrophe), you need only
change the
getWord
function.
•
MaxWords
denotes the maximum number of distinct words catered for. For testing the
program, we have used
50
for this value. If the number of distinct words in the passage
exceeds
MaxWords
(50, say), any words after the 50
th
will be read but not stored, and a message
to that effect will be printed. However, the count for a word already stored will be incremented
if it is encountered again.
•
main
initializes the frequency counts to
0
and the items in the
String
array to the empty
string. It then processes the words in the passage based on the outline shown at the start of
Section 1.8.
•
getWord
reads the input file and returns the next word found.
All words are converted to lowercase so that, for instance,
•
The
and
the
are counted as the same
word.
•
binarySearch
is written so that if the word is found, its location is returned. If the word is not
found, then the location in which it
should
be inserted is returned. The function
addToList
is given the location in which to insert a new word. Words to the right of, and including, this
location, are shifted one position to make room for the new word.
1.9 Merging Ordered Lists
Merging is the process by which two or more ordered lists are combined into one ordered list. For example, given two
lists of numbers,
A
and
B
, as follows:
A: 21 28 35 40 61 75
B: 16 25 47 54
they can be combined into one ordered list, C:
C: 16 21 25 28 35 40 47 54 61 75
The list
C
contains all the numbers from lists
A
and
B
. How can the merge be performed?
One way to think about it is to imagine that the numbers in the given lists are stored on cards, one per card, and
the cards are placed face up on a table, with the smallest at the top. We can imagine the lists
A
and
B
as follows:
21 16
28 25
35 47
40 54
61
75
We look at the top two cards,
21
and
16
. The smaller,
16
, is removed and placed in
C
. This exposes the number
25
.
The top two cards are now
21
and
25
. The smaller,
21
, is removed and added to
C
, which now contains
16 21
. This
exposes the number
28
.
The top two cards are now
28
and
25
. The smaller,
25
, is removed and added to
C
, which now contains
16 21 25
.
This exposes the number
47
.
The top two cards are now
28
and
47
. The smaller,
28
, is removed and added to
C
, which now contains
16 21 25 28
.
This exposes the number
35
.
Search WWH ::
Custom Search