Jupyter at Bryn Mawr College |
|||
Public notebooks: /services/public/dblank / CS206 Data Structures / 2016-Spring / Notebooks |
[Lab 3, CS206: Data Structures, Bryn Mawr College. In the following cell, give a hash title and by-line. Then you can remove this cell. This lab is due in one week.]
YOUR ANSWER HERE
Consider our old friend Node:
class Node {
double data;
Node next;
Node(double data) {
this.data = data;
}
}
Node node = new Node(23.334);
node.data
Now, let's consider a slightly different LinkedList, a SortedLinkedList. This one has an insert method rather than an append method:
class SortedLinkedList {
Node head;
public void insert(Node node) {
if (head == null) {
head = node;
} else if (node.data < head.data) {
// insert here
// NEED SOME CODE
} else { // find where to insert it:
Node current = head;
while (current.next != null) {
if (current.data < node.data) {
// insert it!
// NEED SOME CODE
return;
}
}
// You got here and didn't insert!
// insert it here
// NEED SOME CODE
}
}
}
The idea is that when you insert a Node, it will put it in sorted order. In the next cell, define the method insert, and test it out to show that it works:
# YOUR CODE HERE
raise NotImplementedError()
Redefine the SortedLinkedList
in the next cell, this time adding the method public boolean find(double value)
that will look through the list and return true
if the item is in the list, and false
if it is not. When it finds it (or gives up), it should also print out how many comparisons it took. Test your function many times to see how it works.
# YOUR CODE HERE
raise NotImplementedError()
Consider these Data Structures together that make a Binary Tree
:
class Node {
String data;
Node left;
Node right;
}
class BinaryTree {
Node head;
}
We want to add an public void insert(Node node)
method to BinaryTree like our SortedLinkedList, but we want to BinaryTree to remain sorted such that:
Note that this is a recursive constraint, and is true for all BinaryTrees. Put the String in the first place that it will fit.
class BinaryTree {
Node head;
public void insert(Node node) {
/// NEED CODE HERE
}
}
In the following cell, define a BinaryTree
with an public void insert(Node node)
method. Test it out thoroughly to make sure it works.
# YOUR CODE HERE
raise NotImplementedError()
In the next cell, redefine BinaryTree
to include the method public boolean find(String value)
to search through and see if that value is in the tree. Return true
or false
appropriately. In addition, it should print out how many comparisons it took to determine the answer.
# YOUR CODE HERE
raise NotImplementedError()
[In the following cell, give a thorough reflection of what you found and learned in this lab. Then you can remove this cell.]
YOUR ANSWER HERE