读书笔记《算法》1.3.1

书中例题

Bag背包

背包是一种不支持从中删除元素的集合数据类型——它的目的就是帮助用例收集元素并迭代遍历收集到的元素。迭代的顺序不确定且与用例无关。

以下代码框列出的是常用背包用例。

import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * 简单计算标准输入中的所有double值的平均值和样本标准差.
 * 平均值为它们的和除以N;
 * 样本标准差为每个值和平均值之差的平方之和除以N-1之后的平方根
 * @author Zoye
 *
 */
public class Status {

    public static void main(String[] args) {
        Bag<Double> numbers = new Bag<Double>();
        
        while(!StdIn.isEmpty()) {
            numbers.add(StdIn.readDouble());
        }
        int N = numbers.size();
        
        double sum = 0.0;
        for (Double x : numbers) {
            sum += x;
        }
        double mean = sum/N;
        
        sum = 0.0;
        for (Double x : numbers) {
            sum += (x-mean)*(x-mean);
        }
        double std = Math.sqrt(sum/(N-1));
        
        StdOut.println("mean:"+mean);
        StdOut.println("std:"+std);
        
    }
}

Queue队列

队列是一种先进先出（FIFO）的集合类型。在应用程序中使用队列的主要原因是在用集合保存元素的同时保存它们的相对顺序：使它们入列顺序和出列顺序相同。

例如，以下用例是In类的静态方法readInts()的一种实现。这个方法为用例解决的问题是用例无需预先知道文件的大小即可将文件中的所有整数读入一个数组中。

public static int[] readInts(String name) {
    In in = new In(name);
    Queue<Integer> q = new Queue<Integer>();
    while(!in.isEmpty()) {
        q.enqueue(in.readInt());
    }
    int N = q.size();
    int[] a = new int[N];
    for(int i = 0 ; i < N ; i++ ) {
        a[i] = q.dequeue();
    }
    return a;
}

Stack栈

栈是一种后进先出（LIFO）的集合类型。

以下为其中一典型用例。

/**
 * 把标准输入中的所有证书逆序排列,无需预先知道整数的多少
 * @author Zoye
 *
 */
public class Reverse {

    public static void main(String[] args) {
        Stack<Integer> stack;
        stack = new Stack<Integer>();
        while(!StdIn.isEmpty()){
            stack.push(StdIn.readInt());
        }
        while(!stack.isEmpty()){
            StdOut.println(stack.pop());
        }
        //错误的遍历方式,对于java.util.Stack
        //对于edu.princeton.cs.algs4.Stack则是正确的
//      for (int i : stack) {
//          StdOut.println(i);
//      }
    }
}

算术表达式求值

既是栈用例也是展示泛型的应用的一个典型例子。

表达式由括号、运算符和操作数（数字）组成。我们根据以下4种情况从左到右逐个将这些实体送入栈处理：

将操作数压入操作数栈；
将运算符压入运算符栈；
忽略左括号；
在遇到右括号时，弹出一个运算符，弹出所需数量的运算数，并将运算符和操作数的运算结果压入操作数栈。

以下为该算法的一个实现。

package chapter3;

import edu.princeton.cs.algs4.Stack;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

/**
 * 解释给定字符串所表达的运算并计算得到结果
 * @author Zoye
 *
 */
public class Evaluate {

    public static void main(String[] args) {
        
        //两个栈,一个操作数栈,一个运算符栈
        Stack<String> ops = new Stack<String>();
        Stack<Double> vals = new Stack<Double>();
        //读取字符,如果是运算符就入栈
        while(!StdIn.isEmpty()){
            String s = StdIn.readString();
            if(s.equals("(")) ;
            else if(s.equals("+")) ops.push(s);
            else if(s.equals("-")) ops.push(s);
            else if(s.equals("*")) ops.push(s);
            else if(s.equals("/")) ops.push(s);
            else if(s.equals("sqrt")) ops.push(s);
            else if(s.equals(")")) {
                //如果字符为")",弹出运算符和操作数,计算结果并压入栈
                String op = ops.pop();
                double v = vals.pop();
                if(op.equals("+")) v = vals.pop() + v;
                else if(op.equals("-")) v = vals.pop() - v;
                else if(op.equals("-")) v = vals.pop() - v;
                else if(op.equals("*")) v = vals.pop() * v;
                else if(op.equals("/")) v = vals.pop() / v;
                else if(op.equals("sqrt")) v = Math.sqrt(v);
                vals.push(v);
            } else{
                //如果字符既非运算符也不是括号,将它作为double值压入栈
                vals.push(Double.parseDouble(s));
            }
        }
        StdOut.println(vals.pop());
    }
    
    
}