Leysið dæmi 1.3.27 í bókinni.
Write a method max() that takes a reference to the first node in a linked list as argument and returns the value of the maximum key in the list. Assume that all keys are positive integers, and return 0 if the list is empty.
public class MaxList
{
static class Node
{
int value;
Node next;
};
public static int max(Node first)
{
if (first == null)
return 0;
int m = first.value;
Node p = first.next;
while (p != null)
{
if (p.value > m)
m = p.value;
p = p.next;
}
return m;
}
public static void main(String[] args)
{
Node h1 = new Node();
Node h2 = new Node();
Node h3 = new Node();
Node h4 = new Node();
h1.value = 40;
h1.next = h2;
h2.value = 20;
h2.next = h3;
h3.value = 30;
h3.next = h4;
h4.value = 10;
h4.next = null;
if (max(null) == 0)
System.out.println("Test 1: Passed");
else
System.out.println("Test 1: Failed");
if (max(h1) == 40)
System.out.println("Test 2: Passed");
else
System.out.println("Test 2: Failed");
if (max(h2) == 30)
System.out.println("Test 3: Passed");
else
System.out.println("Test 3: Failed");
if (max(h3) == 30)
System.out.println("Test 4: Passed");
else
System.out.println("Test 4: Failed");
if (max(h4) == 10)
System.out.println("Test 5: Passed");
else
System.out.println("Test 5: Failed");
}
}
Leysið dæmi 1.3.29 í bókinni.
Write a Queue implementation that uses a circular linked list, which is the same as a linked list except that no links are null and the value of last.next is first whenever the list is not empty. Keep only one Node instance variable (last).
Klárið að útfæra beinagrindina samkvæmt þeirri gagnaskipan sem er lýst efst í klasanum.
public class Queue<T>
{
// Biðröðin inniheldur n gildi.
// Gildin eru í hringlista þar sem last bendir
// á aftasta hlekk, aftasti hlekkur bendir
// fremsta hlekk, sem bendir aftur á næstfremsta
// og svo koll af kolli. Ef biðröðin er tóm þá
// er last == null (og n==0 einnig, að sjálfsögðu).
private Node last;
private int n;
private class Node
{
private T value;
private Node next;
}
// Notkun: q = new Queue<T>();
// Fyrir: Ekkert
// Eftir: q er ný tóm biðröð gilda af tagi T
public Queue()
{
last = null;
n = 0;
}
// Notkun: b = q.isEmpty();
// Fyrir: Ekkert
// Eftir: b er satt þþaa. q er tóm
public boolean isEmpty()
{
return last == null;
}
// Notkun: n = q.size();
// Fyrir: Ekkert
// Eftir: n er fjöldi gilda í q
public int size()
{
return n;
}
// Notkun: x = q.peek();
// Fyrir: q er ekki tóm
// Eftir: x er stakið sem er fremst í q
public T peek()
{
return last.next.value;
}
// Notkun: q.enqueue(x);
// Fyrir: Ekkert
// Eftir: Búið er að bæta x aftast í q
public void enqueue(T value)
{
Node p = new Node();
p.value = value;
if (last == null)
p.next = p;
else
{
p.next = last.next;
last.next = p;
}
last = p;
n++;
}
// Notkun: x = q.dequeue();
// Fyrir: q er ekki tóm
// Eftir: Búið er að fjarlægja fremsta
// gildið úr q og það er x.
public T dequeue()
{
T value = last.next.value;
if (last.next == last)
last = null;
else
last.next = last.next.next;
n--;
return value;
}
public static void main(String[] args)
{
Queue<String> q = new Queue<String>();
q.enqueue("A");
q.enqueue("B");
q.enqueue("C");
q.enqueue("D");
q.enqueue("E");
String[] exp = {"A", "B", "C", "D", "E"};
if (q.size() != 5)
{
System.out.printf("Test 1: Failed, expected queue to have 5 values\n");
return;
}
System.out.println("Test 1: Passed");
for (int i = 0; i < exp.length; i++)
{
if (q.isEmpty())
{
System.out.println("Test 2: Failed, queue empty too soon");
return;
}
String s = q.dequeue();
System.out.println(s);
if (!exp[i].equals(s))
{
System.out.printf("Test 2: Failed, expected %s got %s\n", exp[i], s);
return;
}
}
System.out.println("Test 2: Passed");
if (!q.isEmpty())
{
System.out.printf("Test 3: Failed, expected queue to be empty\n");
return;
}
System.out.println("Test 3: Passed");
if (q.size() != 0)
{
System.out.printf("Test 4: Failed, expected queue to be empty\n");
return;
}
System.out.println("Test 4: Passed");
}
}
Leysið fyrri hlutann af dæmi 1.3.33 í bókinni. Þið eigið að útfæra Deque með tvítengdum lista, en þið megið sleppa að útfæra Deque með fylki.
Deque. A double-ended queue or deque (pronounced "deck") is like a stack or a queue but supports adding and removing items at both ends. A deque stores a collection of items and supports the API described in the code below.
Klárið að útfæra beinagrindina samkvæmt þeirri gagnaskipan sem er lýst efst í klasanum.
import java.util.Iterator;
public class Deque<T> implements Iterable<T>
{
// Ef biðröðin er tóm þá er first==last==null og n==0.
// Annars bendir first á hlekk (Node) sem inniheldur fremsta
// gildið og last bendir á hlekk sem inniheldur aftasta
// gildið og milli þeirra eru hin gildin, tengd saman
// á hefðbundinn hátt fyrir tvítengda lista. Fremsti
// hnúturinn hefur prev==null og aftasti hefur next==null,
// eins og venjan er með lista sem ekki eru tengdir í hring.
// Breytan n inniheldur ávallt fjölda gilda í listanum.
private Node first;
private Node last;
private int n;
private class Node
{
private T value;
private Node prev;
private Node next;
}
// Notkun: q = new Deque<T>();
// Fyrir: Ekkert
// Eftir: q er ný tóm tveggja enda biðröð gilda af tagi T
public Deque()
{
first = null;
last = null;
n = 0;
}
// Notkun: b = q.isEmpty();
// Fyrir: Ekkert
// Eftir: b er satt þþaa. q er tóm
public boolean isEmpty()
{
return first == null;
}
// Notkun: n = q.size();
// Fyrir: Ekkert
// Eftir: n er fjöldi gilda í q
public int size()
{
return n;
}
// Notkun: q.pushLeft(x);
// Fyrir: Ekkert
// Eftir: Búið er að bæta x fremst í q
public void pushLeft(T value)
{
Node p = new Node();
p.value = value;
p.prev = null;
p.next = first;
if (first == null)
last = p;
else
first.prev = p;
first = p;
n++;
}
// Notkun: q.pushRight(x);
// Fyrir: Ekkert
// Eftir: Búið er að bæta x aftast í q
public void pushRight(T value)
{
Node p = new Node();
p.value = value;
p.prev = last;
p.next = null;
if (last == null)
first = p;
else
last.next = p;
last = p;
n++;
}
// Notkun: x = q.popLeft();
// Fyrir: q er ekki tóm
// Eftir: Búið er að fjarlægja fremsta
// gildið úr q og það er x.
public T popLeft()
{
T value = first.value;
first = first.next;
if (first != null)
first.prev = null;
else
last = null;
n--;
return value;
}
// Notkun: x = q.popRight();
// Fyrir: q er ekki tóm
// Eftir: Búið er að fjarlægja aftasta
// gildið úr q og það er x.
public T popRight()
{
T value = last.value;
last = last.prev;
if (last != null)
last.next = null;
else
first = last = null;
n--;
return value;
}
// Notkun: it = q.iterator();
// Fyrir: Ekkert
// Eftir: it er nýr flakkari sem er staðsettur
// fremst í biðröðinni. Flakkarinn
// mun ferðast í röð frá fremsta til
// aftasta gildis í biðröðinni.
public Iterator<T> iterator()
{
return new ListIterator();
}
private class ListIterator implements Iterator<T>
{
private Node current;
public ListIterator()
{
current = first;
}
public boolean hasNext()
{
return current != null;
}
public T next()
{
T value = current.value;
current = current.next;
return value;
}
public void remove() {}
}
public static void main(String[] args)
{
Deque<String> dq = new Deque<String>();
dq.pushLeft("C");
dq.pushLeft("B");
dq.pushRight("D");
dq.pushRight("E");
dq.pushLeft("A");
String[] exp = {"A", "B", "C", "D", "E"};
System.out.println("Test 1: ");
Iterator<String> it = dq.iterator();
for (int i = 0; i < exp.length; i++)
{
if (!it.hasNext())
{
System.out.println("Test 1: Failed, iterator ends too soon");
return;
}
String s = it.next();
System.out.println(s);
if (!exp[i].equals(s))
{
System.out.printf("Test 1: Failed, expected %s got %s\n", exp[i], s);
return;
}
}
System.out.println("Test 1: Passed");
System.out.println();
System.out.println("Test 2: ");
if (dq.size() != 5)
{
System.out.printf("Test 2: Failed (count), expected dq to have 5 values\n");
return;
}
for (int i = 0; i < exp.length; i++)
{
if (dq.isEmpty())
{
System.out.println("Test 2: Failed, deque empty too soon");
return;
}
String s = dq.popLeft();
System.out.println(s);
if (!exp[i].equals(s))
{
System.out.printf("Test 2: Failed, expected %s got %s\n", exp[i], s);
return;
}
}
if (!dq.isEmpty())
{
System.out.printf("Test 2: Failed (isEmpty), expected dq to be empty\n");
return;
}
if (dq.size() != 0)
{
System.out.printf("Test 2: Failed (count), expected dq to be empty\n");
return;
}
System.out.println("Test 2: Passed");
System.out.println();
dq.pushRight("C");
dq.pushLeft("D");
dq.pushRight("B");
dq.pushRight("A");
dq.pushLeft("E");
System.out.println("Test 3: ");
if (dq.size() != 5)
{
System.out.printf("Test 3: Failed (count), expected dq to have 5 values\n");
return;
}
for (int i = 0; i < exp.length; i++)
{
if (dq.isEmpty())
{
System.out.println("Test 3: Failed, deque empty too soon");
return;
}
String s = dq.popRight();
System.out.println(s);
if (!exp[i].equals(s))
{
System.out.printf("Test 3: Failed, expected %s got %s\n", exp[i], s);
return;
}
}
if (!dq.isEmpty())
{
System.out.printf("Test 3: Failed (isEmpty), expected dq to be empty\n");
return;
}
if (dq.size() != 0)
{
System.out.printf("Test 3: Failed (count), expected dq to be empty\n");
return;
}
System.out.println("Test 3: Passed");
}
}
Leysið dæmi 1.3.39 í bókinni.
Ring Buffer. A ring buffer, or circular queue, is a FIFO data structure of a fixed size N. It is useful for transferring data between asynchronous processes or for storing log files. When the buffer is empty, the consumer waits until data is deposited; when the buffer is full, the producer waits to deposit data.
Klárið að útfæra beinagrindina hér fyrir neðan.
import java.util.Iterator;
public class RingBuffer<T> implements Iterable<T>
{
private T[] f; // queue elements
private int N = 0; // number of elements on queue
private int first = 0; // index of first element of queue
private int last = 0; // index of next available slot
// Notkun: q = new RingBuffer<T>(capacity);
// Fyrir: capacity > 0
// Eftir: q er ný tóm hringbiðröð af stærð capacity
// fyrir gildi af tagi T
@SuppressWarnings({"unchecked"})
public RingBuffer(int capacity)
{
f = (T[]) new Object[capacity];
}
// Notkun: b = q.isEmpty();
// Fyrir: Ekkert
// Eftir: b er satt þþaa. q er tóm
public boolean isEmpty()
{
return N == 0;
}
// Notkun: n = q.size();
// Fyrir: Ekkert
// Eftir: n er fjöldi gilda í q
public int size()
{
return N;
}
// Notkun: q.enqueue(x);
// Fyrir: Ekkert
// Eftir: Búið er að bæta x aftast í q
public void enqueue(T item)
{
if (N == f.length) { throw new RuntimeException("Ring buffer overflow"); }
f[last] = item;
last = (last + 1) % f.length;
N++;
}
// Notkun: x = q.dequeue();
// Fyrir: q er ekki tóm
// Eftir: Búið er að fjarlægja fremsta
// gildið úr q og það er x.
public T dequeue()
{
if (isEmpty()) { throw new RuntimeException("Ring buffer underflow"); }
T item = f[first];
f[first] = null;
first = (first + 1) % f.length;
N--;
return item;
}
public Iterator<T> iterator()
{
return new RingBufferIterator();
}
private class RingBufferIterator implements Iterator<T>
{
private int i = 0;
public boolean hasNext()
{
return i < N;
}
public T next()
{
T item = f[(i + first) % f.length];
i++;
return item;
}
public void remove() {}
}
public static void main(String[] args)
{
RingBuffer<String> ring = new RingBuffer<String>(20);
ring.enqueue("A");
ring.enqueue("B");
ring.enqueue("C");
ring.enqueue("D");
ring.enqueue("E");
String[] exp = {"A", "B", "C", "D", "E"};
if (ring.size() != 5)
{
System.out.printf("Test 1: Failed, expected ring to have 5 values\n");
return;
}
System.out.println("Test 1: Passed");
for (int i = 0; i < exp.length; i++)
{
if (ring.isEmpty())
{
System.out.println("Test 2: Failed, ring empty too soon");
return;
}
String s = ring.dequeue();
System.out.println(s);
if (!exp[i].equals(s))
{
System.out.printf("Test 2: Failed, expected %s got %s\n", exp[i], s);
return;
}
}
System.out.println("Test 2: Passed");
if (!ring.isEmpty())
{
System.out.printf("Test 3: Failed, expected ring to be empty\n");
return;
}
System.out.println("Test 3: Passed");
if (ring.size() != 0)
{
System.out.printf("Test 4: Failed, expected ring to be empty\n");
return;
}
System.out.println("Test 4: Passed");
}
}