《算法》第四版答案（三）习题1.3
2017-10-19 本文已影响0人
HilaryLi
本章节为习题1.3.12-1.3.16的答案
-
1.3.12
答案
在作者的Stack程序中添加如下方法：
public static <T> Stack<T> copy(Stack<T> s)
{
Iterator<T> it = s.iterator();
Stack<T> result = new Stack<T>();
Stack<T> temp = new Stack<T>();
while (it.hasNext()) {
temp.push(it.next());
}
it = temp.iterator();
while (it.hasNext()) {
result.push(it.next());
}
return result;
}
测试代码：
public class ex1_3_12 {
public static void main(String[] args) {
Stack<String> s1 = new Stack<String>();
s1.push("first");
s1.push("second");
s1.push("third");
Stack<String> s2 = Stack.copy(s1);
while (!s2.isEmpty()) {
System.out.println(s2.pop());
}
}
}
-
1.3.13
答案
b c d
-
1.3.14
答案
import java.util.Iterator;
import java.util.NoSuchElementException;
public class ResizingArrayQueue<Item> implements Iterable<Item> {
private Item[] q; // queue elements
private int n; // number of elements on queue
private int first; // index of first element of queue
private int last; // index of next available slot
/**
* Initializes an empty queue.
*/
public ResizingArrayQueue() {
q = (Item[]) new Object[2];
n = 0;
first = 0;
last = 0;
}
/**
* Is this queue empty?
* @return true if this queue is empty; false otherwise
*/
public boolean isEmpty() {
return n == 0;
}
/**
* Returns the number of items in this queue.
* @return the number of items in this queue
*/
public int size() {
return n;
}
// resize the underlying array
private void resize(int capacity) {
assert capacity >= n;
Item[] temp = (Item[]) new Object[capacity];
for (int i = 0; i < n; i++) {
temp[i] = q[(first + i) % q.length];
}
q = temp;
first = 0;
last = n;
}
/**
* Adds the item to this queue.
* @param item the item to add
*/
public void enqueue(Item item) {
// double size of array if necessary and recopy to front of array
if (n == q.length) resize(2*q.length); // double size of array if necessary
q[last++] = item; // add item
if (last == q.length) last = 0; // wrap-around
n++;
}
/**
* Removes and returns the item on this queue that was least recently added.
* @return the item on this queue that was least recently added
* @throws java.util.NoSuchElementException if this queue is empty
*/
public Item dequeue() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
Item item = q[first];
q[first] = null; // to avoid loitering
n--;
first++;
if (first == q.length) first = 0; // wrap-around
// shrink size of array if necessary
if (n > 0 && n == q.length/4) resize(q.length/2);
return item;
}
/**
* Returns the item least recently added to this queue.
* @return the item least recently added to this queue
* @throws java.util.NoSuchElementException if this queue is empty
*/
public Item peek() {
if (isEmpty()) throw new NoSuchElementException("Queue underflow");
return q[first];
}
/**
* Returns an iterator that iterates over the items in this queue in FIFO order.
* @return an iterator that iterates over the items in this queue in FIFO order
*/
public Iterator<Item> iterator() {
return new ArrayIterator();
}
// an iterator, doesn't implement remove() since it's optional
private class ArrayIterator implements Iterator<Item> {
private int i = 0;
public boolean hasNext() { return i < n; }
public void remove() { throw new UnsupportedOperationException(); }
public Item next() {
if (!hasNext()) throw new NoSuchElementException();
Item item = q[(i + first) % q.length];
i++;
return item;
}
}
/**
* Unit tests the {@code ResizingArrayQueue} data type.
*
* @param args the command-line arguments
*/
public static void main(String[] args) {
ResizingArrayQueue<String> queue = new ResizingArrayQueue<String>();
while (!StdIn.isEmpty()) {
String item = StdIn.readString();
if (!item.equals("-")) queue.enqueue(item);
else if (!queue.isEmpty()) StdOut.print(queue.dequeue() + " ");
}
StdOut.println("(" + queue.size() + " left on queue)");
}
}
-
1.3.15
答案
import java.util.Iterator;
import edu.princeton.cs.algs4.StdIn;
/**
* ClassName : Queue <br>
* Function : TODO ADD FUNCTION. <br>
* date : Sep 28, 2016 10:21:54 AM <br>
*
* @version
*/
public class Queue<Item> implements Iterable<Item>
{
private Node first;
private Node last;
private int n;
private class Node
{
Item item;
Node next;
}
public boolean isEmpty()
{
return first == null;
}
public int size()
{
return n;
}
public void enqueue(Item item)
{
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty())
{
first = last;
}
else
{
oldlast.next = last;
}
n++;
}
public Item dequeue()
{
Item item = first.item;
first = first.next;
if (isEmpty())
{
last = null;
}
n--;
return item;
}
@Override
public Iterator<Item> iterator()
{
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item>
{
private Node current = first;
@Override
public boolean hasNext()
{
return current != null;
}
@Override
public Item next()
{
Item item = current.item;
current = current.next;
return item;
}
}
public static void main(String[] args)
{
Queue<String> q = new Queue<String>();
while (!StdIn.isEmpty())
{
String item = StdIn.readString();
if (!item.equals("-"))
{
q.enqueue(item);
}
else if (!q.isEmpty())
{
System.out.print(q.dequeue() + " ");
}
}
System.out.println("(" + q.size() + " left on queue)");
}
}
测试:
public class E10315
{
public static void main(String[] args)
{
int k = Integer.parseInt(args[0]);
Scanner scanner = new Scanner(System.in);
Queue<String> q = new Queue<String>();
while (scanner.hasNext()) {
q.enqueue(scanner.next());
}
scanner.close();
int size = q.size();
for (int i = 0; i < size - k; i++) {
// System.out.print(q.dequeue() + " ");
q.dequeue();
}
System.out.println(q.dequeue());
}
}
-
1.3.16
答案
public class Date
{
private final int month;
private final int day;
private final int year;
public Date(int m, int d, int y)
{
month = m;
day = d;
year = y;
}
public Date(String date)
{
String[] s = date.split("\\/");
if (s.length != 3) {
throw new IllegalArgumentException("Arguments illegal: " + date);
}
month = Integer.parseInt(s[0]);
day = Integer.parseInt(s[1]);
year = Integer.parseInt(s[2]);
}
public int month()
{
return month;
}
public int day()
{
return day;
}
public int year()
{
return year;
}
public String toString()
{
return month() + "/" + day() + "/" + year();
}
public boolean equals(Object x)
{
if (this == x) return true;
if (x == null) return false;
if (this.getClass() != x.getClass()) return false;
Date that = (Date)x;
if (this.day != that.day) return false;
if (this.month != that.month) return false;
if (this.year != that.year) return false;
return true;
}
public static Date[] readDates(String s)
{
String[] dates = s.split(" ");
int n = dates.length;
Queue<Date> q = new Queue<Date>();
for (int i = 0; i < n; i++) {
q.enqueue(new Date(dates[i]));
}
Date[] result = new Date[n];
for (int i = 0; i < n; i++) {
result[i] = q.dequeue();
}
return result;
}
}
测试：
public class E10316
{
public static void main(String[] args)
{
String s = "11/30/2009 1/12/2012";
Date[] dates = Date.readDates(s);
for (int i = 0; i < dates.length; i++) {
System.out.println(dates[i]);
}
}
}
