Java Reference
In-Depth Information
4.2 One solution to the problem of running out of space for an array-based list
implementation is to replace the array with a larger array whenever the origi-
nal array overflows. A good rule that leads to an implementation that is both
space and time efficient is to double the current size of the array when there
is an overflow. Re-implement the array-based
List
class of Figure 4.2 to
support this array-doubling rule.
4.3 Use singly linked lists to implement integers of unlimited size. Each node of
the list should store one digit of the integer. You should implement addition,
subtraction, multiplication, and exponentiation operations. Limit exponents
to be positive integers. What is the asymptotic running time for each of your
operations, expressed in terms of the number of digits for the two operands
of each function?
4.4 Implement doubly linked lists by storing the sum of the
next
and
prev
pointers in a single pointer variable as described in Example 4.1.
4.5 Implement a city database using unordered lists. Each database record con-
tains the name of the city (a string of arbitrary length) and the coordinates
of the city expressed as integer x and y coordinates. Your database should
allow records to be inserted, deleted by name or coordinate, and searched
by name or coordinate. Another operation that should be supported is to
print all records within a given distance of a specified point. Implement the
database using an array-based list implementation, and then a linked list im-
plementation. Collect running time statistics for each operation in both im-
plementations. What are your conclusions about the relative advantages and
disadvantages of the two implementations? Would storing records on the
list in alphabetical order by city name speed any of the operations? Would
keeping the list in alphabetical order slow any of the operations?
4.6 Modify the code of Figure 4.19 to support storing variable-length strings of
at most 255 characters. The stack array should have type
char
. A string is
represented by a series of characters (one character per stack element), with
the length of the string stored in the stack element immediately above the
string itself, as illustrated by Figure 4.34. The
push
operation would store an
element requiring i storage units in the i positions beginning with the current
value of
top
and store the size in the position i storage units above
top
.
The value of
top
would then be reset above the newly inserted element. The
pop
operation need only look at the size value stored in position
top
1 and
then pop off the appropriate number of units. You may store the string on the
stack in reverse order if you prefer, provided that when it is popped from the
stack, it is returned in its proper order.
4.7 Define an ADT for a bag (see Section 2.1) and create an array-based imple-
mentation for bags. Be sure that your bag ADT does not rely in any way
on knowing or controlling the position of an element. Then, implement the
dictionary ADT of Figure 4.29 using your bag implementation.
