Java Reference
In-Depth Information
(because of the three letters in her name), and the third suitor would be eliminated
from winning her hand and removed from the line. Eve would then continue, count-
ing three more suitors, and eliminate every third suitor. When she reached the end of
the line, she would continue counting from the beginning.
For example, if there were six suitors, the elimination process would proceed
as follows:
123456 Initial list of suitors; start counting from 1.
12456 Suitor 3 eliminated; continue counting from 4.
1245 Suitor 6 eliminated; continue counting from 1.
125 Suitor 4 eliminated; continue counting from 5.
15 Suitor 2 eliminated; continue counting from 5.
1 Suitor 5 eliminated; 1 is the lucky winner.
Write a program that creates a circular linked list of nodes to determine which posi-
tion you should stand in to marry the princess if there are
n
suitors. Your program
should simulate the elimination process by deleting the node that corresponds to
the suitor that is eliminated for each step in the process.
2. Although the
long
data type can store large integers, it cannot store extremely large
values such as an integer with 200 digits. Create a
HugeNumber
class that uses a
linked list of digits to represent integers of arbitrary length. The class should have
a method to add a new most significant digit to the existing number so that longer
and longer numbers can be created. Also add methods to reset the number and to
return the value of the huge integer as a
String
along with appropriate constructor
or accessor methods. Write code to test your class.
Note:
Use of a doubly linked list will make the next problem easier to implement.
3. Add a copy constructor to the
HugeNumber
class described in the previous problem
that makes a deep copy of the input
HugeNumber
. Also create an
add
method that
adds an input
HugeNumber
to the instance's
HugeNumber
value and returns a new
HugeNumber
that is set to the sum of the two values. Write code to test the additions
to your class.
4. Give the definition of a generic class that uses a doubly linked list of data items.
Include a copy constructor, an
equals
method, a
clone
method, a
toString
method, a method to produce an iterator, and any other methods that would
normally be expected. Write a suitable test program.
5. Complete the definition of the binary search tree class
IntTree
in Display 15.39
by adding the following: Make
IntTree
implement the
Cloneable
interface,
including the definition of a
clone
method; add a copy constructor; add an
equals
method; add a method named
sameContents
as described later in this
project; add a
toString
method; and add a method to produce an iterator. Define
equals
so that two trees are equal if (and only if) the two trees have the exact same
shape and have the same numbers in corresponding nodes. The
clone
method and
the copy constructor should each produce a deep copy that is equal to the original