This assignment is meant for you to practice different data structures and their applications. A lot of the design decisions have been done for you, but you might notice that the instructions for A2 are less complete than A1. You will need to take care of small details by yourself. Finally, we will not be grading your work on efficiency; however, if a method takes more than 1 second to complete,it is equivalent to failing.
This assignment contains 3 parts. You need to download the files provided and complete the following 13 files:
Part I Part II Part III
MyList.java Position.java Region.java
MyLinkedList.java TargetQueue.java Caterpillar.java
MyDoublyLinkedList.java Direction.java State.java
MyStack.java ActionQueue.java World.java
- Except for the MyDoublyLinkedList.java, where a starting file is provided, you have to create all the above classes from scratch.
- Please make sure that all the files you submit are part of a package called assignment2.
- You are NOT allowed to import any other class/interface except NoSuchElementException and Iterator, which have already been imported for you in MyDoublyLinkedList.java. You are also not allowed to use ANY field of type array. Any failure to comply with these rules will give you an automatic 0.
- You are always allowed to add private methods/fields whenever you think this can improve your implementation. You are also allowed to override the toString method if this can help you during the debugging process.
- Two extra files, CaterpillarGame.java and CaterpillarDrawer.java, are provided for visualizing the results of Part III. Do not use them unless your Part III is completed and passes all tests from the minitester.
- Do NOT start testing your code only after you are done writing the entire assignment. It will be extremely hard to debug your program otherwise. If you need help debugging, feel free to reach out to the teaching staff. When doing so, make sure to mention what is the bug you are trying to fix, what have you tried to do to fix it, and where have you isolated the error to be.
- Late assignments will be accepted up to 2 days late and will be penalized by 10 points per late day. Note that submitting one minute late is the same as submitting 23 hours late. We will deduct points for any student who has to resubmit after the due date (i.e. late) irrespective of the reason, be it the wrong file submitted, the wrong file format submitted or any other reason. We will not accept any submission after the 2 days grace period.
- Don’t worry if you realize that you made a mistake after you submitted: you can submit multiple times but only the latest submission will be evaluated. We encourage you to submit a first version a few days before the deadline (computer crashes do happen and Ed Lessons may be overloaded during rush hours).
- Do not submit any other files, especially .class files and the tester files. Any failure to comply with these rules will give you an automatic 0.
- Whenever you submit your files to Ed, you will see the results of some exposed tests. If you do not see the results, your assignment is not submitted correctly. If your assignment is not submitted correctly, you will get an automatic 0. If your submission does not compile on ED, you will get an automatic 0.
- The assignment shall be graded automatically on ED. Requests to evaluate the assignment manually shall not be entertained, and it might result in your final marks being lower than the results from the auto-tests. Please make sure that you follow the instruction closely or your code may fail to pass the automatic tests.
- The exposed tests on ED are a mini version of the tests we will be using to grade your work.
If your code fails those tests, it means that there is a mistake somewhere. Even if your code passes those tests, it may still contain some errors. Please note that these tests are only a subset of what we will be running on your submissions, we will test your code on a more challenging set of examples. Passing the exposed tests assures you that your submission will not receive a grade lower than 40/100. We highly encourage you to test your code thoroughly before submitting your final version.
- Next week, a mini-tester will also be posted. The mini-tester contains tests that are equivalent to those exposed on Ed. We encourage you to modify and expand it. You are welcome to share your tester code with other students on Ed. Try to identify tricky cases. Do not hand in your tester code.
- Failure to comply with any of these rules will be penalized. If anything is unclear, it is up to you to clarify it by asking either directly a TA during office hours, or on the discussion board on Ed.
PART – I: Data Structures (35 points)
For the first part, you will write several classes to implement different data structures.
[5 points] Write an interface MyList<E> with a generic element type E. The MyList<E> interface extends the Iterable<E> interface. The MyList<E> interface has the following public methods:
- A getSize method that returns an int indicating the number of elements in the list.
- A isEmpty method that returns a boolean indicating whether the list is empty.
- An add method that appends the specified element to the end of this list and does not return anything.
- A clear method that removes all of the elements from this list and does not return anything.
- A remove method that removes the last element from the list and returns it.
[5 points] Write an abstract class MyLinkedList<E> with a generic type E and implements MyList<E>.
The MyLinkedList<E> class has the following protected field:
- A int indicating the size of the list.
The class must also implement the public methods getSize and isEmpty as specified by the documentation of the interface MyList<E>.
[15 points] Complete the MyDoublyLinkedList<E> class (provided) as a doubly linked-list of generic type E. Inside the file provided you can find:
- A private class called DLLIterator and a method iterator returning a DLLIterator object. This DLLIterator class implements the Iterator<E> interface (from java.util.Iterator) which allows the user to iterate over the list. DO NOT modify anything from the
DLLIterator class or the iterator method; otherwise, your program will fail the testers.
- A private class called DNode. The DNode class contains three private fields:
– An E named element indicating the element stored in the node
– A DNode named next indicating the next node in the list
– A DNode named prev indicating the previous node in the list
- The MyDoublyLinkedList<E> class has the following private fields:
– A DNode named head indicating the head of the list
– A DNode named tail indicating the tail of the list
It is up to you to do the following:
- Make sure the class MyDoublyLinkedList<E> extends the MyLinkedList<E> class.
- Implement the public methods add, remove, and clear as specified in the documentation of the interface MyList<E>.
- Add the following public methods to the MyDoublyLinkedList<E> class:
– An addFirst and an addLast method which takes input as an object of the generic type E and adds the element as the first/last element of the list. These methods do not return anything.
– A removeFirst and a removeLast method which removes the first/last node from the list and returns the element. The method should throw a NoSuchElementException if the list is empty.
– A peekFirst and a peekLast method which returns the first/last element without removing it from the list. The method should throw a NoSuchElementException if the list is empty.
– An equals method that takes an Object as an input; the method returns true if all elements in the list are considered to be equal and false otherwise.
You are free to add any additional private methods and/or fields to either MyDoublyLinkedList<E> or DNode if you think this can help you with the implementation. Please note that, as specified in the general instructions, you are NOT allowed to add any field of type array.
[5 points] Write a class MyStack<E>.
The MyStack<E> class has the following private fields:
- A MyDoublyLinkedList<E> to store the elements of the stack.
The class must also have the following public methods:
- A constructor that takes no inputs and creates an empty stack.
- A push method that takes an input of type E and adds the input to the top of the stack.
- A pop method that removes the top of the stack and returns it. The method should throw a NoSuchElementException if the stack is empty.
- A peek method that returns the element at the top of the stack without removing it.
The method should throw a NoSuchElementException if the stack is empty.
- A isEmpty method that returns true if the stack is empty and false otherwise.
- A clear method that clears the stack (i.e. removes all the elements from the stack).
- A getSize method that returns the number of elements in the stack.
[5 points] Write a class MyQueue<E>.
The MyQueue<E> class has the following private fields:
- A MyDoublyLinkedList<E> to store the elements of the queue.
The class must also have the following public methods:
- A constructor that takes no inputs and creates an empty queue.
- A enqueue method that takes an input of type E and adds it to the back of the queue.
- A dequeue method that removes the first element from the front of the queue and returns
- The method should throw a NoSuchElementException if the queue is empty.
- An isEmpty method that returns true if the queue is empty and false otherwise.
- A clear method that clears the queue (i.e. removes all the elements from the queue).
- An equals method that takes as input an Object and returns true if the input is another queue with equal elements, and false otherwise.
PART – II: Information Parsing with Stacks (35 points)
In PART-II, you will decode and parse strings that contain compressed information.
[7 points] Write a Position class as a representation of a point (x,y) on a 2D map as the figure below. The origin (0,0) is located at the top-left corner of the map.
The Position class has the following private fields:
- An int indicating the x-coordinate on the map
- An int indicating the y-coordinate on the map
The Position class must also have the following public methods:
- A constructor that takes two int as inputs indicating the x- and y-coordinates on a map,in this order. The constructor uses the inputs to initialize the corresponding fields.
- A constructor that takes a Position as input and initializes the fields with the corresponding input. This type of constructors are called copy constructors. They are used to create duplicates of existing instances of the class.
- A reset method that takes two int as inputs indicating the x- and y-coordinates on a map. The method uses the inputs to resets the corresponding fields.
- A reset method that takes Position as input and resets the corresponding fields using the values of those of the input object.
- A static method called getDistance that takes two Position objects as input and returns the absolute distance between them in terms of the x- and y- coordinates. For example, the distance between two Position objects (2,3) and (3,5) is 3 (i.e. |2-3|+ |3-5|).
- A getX and a getY method that return the values of the corresponding fields.
- A moveWest method that decrements the x-coordinate by 1.
- A moveEast method that increments the x-coordinate by 1.
- A moveNorth method that decrements the y-coordinate by 1.
- A moveSouth method that increments the y-coordinate by 1.
- An equals method which takes as input an Object and returns true if the input matches this in type, x-coordinate, and y-coordinate. Otherwise, the method returns false.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx