### 数据结构代写 | Data Structures and Algorithms: Assignment 2

数据结构伪代码代写

Data Structures and Algorithms: Assignment 2 Due: 23 September 2019, 11:59pm

50 Marks Possible – worth 10% of final grade

Question 1) One of the issues with a standard list is that if the index of an item is unknown and we want to check if an item is in the list or not using a contains or indexof methods, the complexity of these operations are O(n). A self-organizing list tries to improve on this by moving more frequently accessed items to the beginning of the list. A self-organizing list keeps an access counter for each item in the list, whenever a target item is checked to see if it is in the list its counter is incremented. Once found, the self-organizing list then repeatedly checks whether that target item has a higher or equal access counter to its neighbour heading towards the front of the list, if the target item does it bubbles (swaps) position with its neighbour. It may do this several times, potentially even bubbling all the way to the front of the list. Note: the access counter is not incremented when a standard get operation is used, or with an iterator.

Example: If the elements A, B, C, D, E were added in this order then the list and access counter would show:

[A(1), B(1), C(1), D(1), E(1)]

If now a program was to check if “C” was in the list using the contains method, it would increment its access counter. Now because the access counter of C is now 2, it would first bubble with B then bubble with A before returning true. The list would now show:

[C(2), A(1), B(1), D(1), E(1)]

If now the element B was checked using indexOf, its access counter would increase to 2 and it would bubble with A, then bubble with C (as access counter would equal C, but preference is given to the last target element), it then would return index 0 (its new position). The list would now show:

[B(2), C(2), A(1), D(1), E(1)]

If now element B was checked again using indexOf, its access counter would increase to 3 but because it is at the front it would not move and its index of 0 would be returned. If now we remove element C from the list the elements to the left must shift along. If the code then checks to see if A was in the list it would increase its access counter to 2, but would not bubble along as B’s access counter is 3. The list would now show:

[B(3), A(2), D(1), E(1)]

Create two separate self-organizing list classes of any generic type E, both implementing the java.util.List<E> interface. One of these classes should provide an implementation of a self-organizing list using an underlying array, the other an implementation using a doubly linked structure of nodes. You must create these classes from scratch (You cannot use or extend ArrayList or LinkedList). Think of how to best handle the access counter and bubbling. You will also need to provide suitable implementations of Iterator and ListIterator. However, these must be read only versions and only support navigation.

Because a self-organizing list is charge of positioning elements, any methods which would normally allow user code to insert new elements at specific indices should not be allowed. For convenience create a toString method that prints out the elements in the list with the access counter inside circle

brackets and all inside square brackets (like the above examples). Think of any problems that could arise when the list is incorrectly used by other programs, handle the appropriate exceptions where needed. Make sure you thoroughly test your code is working as expected using simple examples before proceeding. (30 marks)

Question 2) Create a class called DocumentReader with a simple main method which instantiates a self-organizing list using one of the implementations above, designed to hold unique strings for word frequency analysis. The class reads a text file using streams, extracting each word individually. It should check to see if that word is not already contained in the self-organizing list, before adding it as a new word. Make sure your program recognizes both upper and lower case versions of the same word. After the document is read, print out the list – it should show the number of occurrences for each word with the most commonly accessed words at the front of the list. (5 marks)

Question 3) An expression tree is a binary tree representing mathematical expressions built from postfix notation and converting to infix notation. Each internal node in the tree can be an operator (mathematical operations), whereas leaf nodes are operands (numbers or values). An operator can calculate an expression from the output of its left child and right child. A boolean expression tree is a expression tree for boolean logic, comprised of operands {true (T) or false (F)} as well as operators {OR (|), AND (&), NOT(!), XOR(^)}.

Eg: The posfix notation input TF& would produce the expression tree:

This would evaluate to the infix notation (T & F) = false.

Eg: The postfix notation of TF|F&T!F|!^ as input would produce the expression tree:

This would evaluate to the infix notation: (((T|F)&F)^!(!T|F)) = true

Using the UML below create the abstract class BoolExpNode and concrete subclasses BoolOperatorNode and BoolOperandNode. The super class keeps an expression symbol as a char as well as links to its left and right subtrees. The constructors accept a symbol used to represent the operand (T,F) or operator (!&^|), throwing an appropriate exception if the symbol is invalid. The toString simply prints out the symbol as a String. The subclasses must override the abstract method evaluate which for an operand will simply return true or false depending on the symbol. However, for an operator node it must evaluate the correct boolean expression by evaluating the left subtree and right subtree depending on the symbol (care should be taken for the unary operator NOT).

<<abstract>> BoolExpNode

#symbol : char

+leftChild : BoolExpNode +rightChild : BoolExpNode

+ BoolExpNode(symbol : char)

+ evaluate() : boolean

+ toString() : String

BoolOperatorNode

+ BoolOperatorNode (symbol : char) + evaluate() : boolean

Obtain the partially complete class BETreeGUI from Blackboard. The class can display a boolean expression tree, drawing the tree from the root node (if not null) down. It has an input text field to enter a post fix expression with associated buttons. One button is used to build the tree, the other to evaluate the tree, outputting the infix notation formula and the resulting boolean output.

Finish the method buildExpressionTree which builds an expression tree comprised of operator and operand nodes by reading symbols from the postfix input expression given as user input to the text field. The following pseudo code may be very useful:

Create Stack S, Create parent Node P, set numberNodes = 0; for(symbol in expression)

if symbol is an operand

push(operand) onto S, increment numberNodes

if symbol is operator

return P.

set P as new Operator

pop two Nodes (or only one if unary operator) and set as P.left and P.right push(P) onto s, increment numberNodes

BoolOperandNode

+ BoolOperandNode(symbol : char) + evaluate() : boolean

Finish the recursive method toInfixString which can be used to recursively convert a binary expression tree into infix notation using brackets: The following pseudo code may be useful.

toInfixSring(Node current) create empty string S

if (current null) return “”

if (current symbol is binary operator) append “(“ to S

append toInfixString (left subtree) to S append current symbol to S

append toInfixString (left subtree) to S

if (current symbol is binary operator) append “)” to S

return S

Finally append the resulting boolean output by evaluating the tree and append to the infix notation. Once working your GUI should look like something like this once tree is built and the evaluate to infix button pressed:

Make any necessary modifications to handle any unexpected user input such as invalid symbols and incorrect postfix formula. (15 marks)

## 发表评论