完成数据结构作业，包括Zombie Simulator, Skip List
Set, Deque以及Redix Sort,
量比较大。
Question 1 - Zombie Simulator (recommended readings 1.3, 1.4)
Using the UML below, create a class called Human which represents a human
being whom can walk around a simulated world.
Human
# x,y : double
# dx,dy : double
# size : double
# isAlive : boolean
+ world_width, world_height : int
———————————
# max_speed : double
# sightDistance : int
# generator : Random
# others : List
———————————
+ Human(others:List
+ run(): void
+ getX(): double
+ getY(): double
+ getSize() : double
+ kill() : void
+ draw(g : Graphics) : void
Each Human can run as a separate thread and maintains an x,y position with
periodic movements using dx, dy which change slightly after a number of
iterations. A Human can be instantiated using an initial position and a list
of all other humans in the world. A Human can be drawn using the draw method
and passing a Graphics object around its x,y position and size. There are also
a static public fields which can be set to determine the size of the world in
which humans roam.
Create a Zombie class which extends a Human. Try to work out what Human
fields/methods should be overridden. A Zombie has a sight distance of the
entire panel and will actively seek and search out the nearest human, it will
then alter its dx,dy movements towards the closest human for a fixed period of
time before checking if there is any other targets it could possibly chase. A
Zombie can only move half of the max speed as a human. If a Zombie manages to
catch a human it will bite and kill the human.
Modify the human class so that it tries to move away from the closest zombie
within its sight distance by modifying its dx,dy speed. A Human sight distance
is only of the world size.
Create a GUI called ZombieSimulator with two buttons, starting either a zombie
or a human as a thread. The GUI should periodically redraw all Human and
Zombie objects moving within the world. It should maintain a single thread
safe data structure for all Zombie and Human objects. It should also
periodically check if a human has been killed by a zombie, in which case it
re-instantiates the object as a new Zombie thread. See below for an example
screenshot, where zombies are red squares and humans’ blue circles.
Feel free to add any private/protected helper methods across any of the
classes which you feel would improve the design of your program and play with
any of the formula constants (eg sight distance, max speed, sleep time) to
improve the feel of the simulator.
Question 2 - Skip List Set (recommended readings 2.2)
A skip list data structure is a modification of a singly linked list so that
the add, contains, and remove methods are O(log2 n). Essentially it consists
of a series of singly-linked lists L0, L1, …, Lk, usually visualized one on
top of another with L0 at the bottom. The list L0 holds all the (nonnull)
elements of the collection in order with null at the start and end of the
list. Each list Li+1 holds a subset of the previous list Li and has links from
each element down to the same element in the previous list. These links enable
elements in the collection to be found more efficiently than by just
traversing the list L0. The illustrated skip list holds three elements e0, e1,
e2 in comparable order:
When an element is added to the skip list it is first randomly decided in how
many of the lists it will appear (it is always placed in the list L0, and if
in a list Li it has a 50-50 chance of also being in Li+1 and so on). Then the
correct insertion place is found in the topmost list to which it will be added
(which might result in a new top list being created), and then working
downward it is added to each of the lists below. An element is found by
starting at the top list (referenced by firstNode), following the next links
until either the element is found, the end of the list would be reached, or
else the element would be passed. If not yet found, a down link is followed to
continue the process with the list below. To remove an element the element
should be removed from each list in which it appears (starting with the
topmost list).
Using the UML below as a guide, prepare a class called SkipListSet that
extends AbstractSet (and so implements the Set interface) using a skip list
data structure and the following UML diagram as a guide. Include a suitable
main method which effectively tests your skip list implementation.
A screenshot of an example test is shown below, note that for convenience and
debugging purposes the skip list toString prints all node elements on each
level.
Question 3 - Deque implementations (recommended readings: 3.3)
A deque (pronounced deck) or double-ended queue, is a linear collection that
allows insertion and removal at both ends. The interface above called
DequeADT, available from Blackboard, is an abstract data type which can hold
any generic element E, it also describes operations for a deque.
- It has enqueue and dequeue methods for adding or removing an element from the front and rear of the deque.
- first and last for obtaining the elements (but not removing) at the front and rear of the deque.
- isEmpty for checking whether any elements are in the deque.
- size for returning the number of elements currently in the deque.
- clear for clearing out all elements in deque.
- iterator which can be used to contiguously iterate over the elements in the deque, going from the front to the rear of the deque.
Create two data structure implementations of the Deque, one which uses an
underlying array called ArrayDeque and one which uses an underlying dynamic
doubly-linked structure called DoublyLinkedDeque. Implement the deque data
structures yourself, do not use extra Java Collection classes!
For efficiency first, last, enqueueRear, enqueueFront, dequeueRear,
dequeueFront, clear, size, and isEmpty should all be O(1) operations. Feel
free to add any necessary private helper methods and a suitable toString which
returns a string representation for your deque implementation.
Further enhance your classes to make sure all methods are safe from unexpected
events using appropriate exception handling (example, if user code tries to
remove something from the deque when empty, it should throw an appropriate
exception). Create a test class with a suitable main method which effectively
tests all operations on one or both deque implementations.
See the screenshot below for an example of testing one of the deque
implementations.
Question 4 - Bitwise Radix Sort (recommended readings 3.5, 3.6)
Radix sort is a sorting algorithm that focuses on sorting parts that comprise
the number rather than the whole number directly. Usually it can only be used
on fixed digit or character inputs such as post codes or county codes. Radix
sort focusses on each digit/char at a time and placing it in a desired queue
shared with other parts of the same value. After all elements are queued, it
polls all elements back into an original list. It repeats this process k times
where k is the amount of digits/chars that comprise the element. However, if
we had to sort a single digit element across a larger range of possibilities
(eg Ascii or Unicode values) then a different strategy for radix sort can be
utilised at a bit level, instead focussing on the bits which make up the data
type.
Create a simple static method called bitwiseRadixSort which takes a char[]
of Unicode values and sorts them looking at the individual bits which form
each char data type. Include a main method to test using randomly generated
char values as demonstrated with the screenshot below. Note it may be
beneficial to print out the Unicode number as well as the printed char so that
you know your sort is working.
