首页 / 算法 / 《算法》第一章部分程序 part 2
《算法》第一章部分程序 part 2
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《算法》第一章部分程序 part 2，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含7183字，纯文字阅读大概需要11分钟。
内容图文
? 书中第一章部分程序，加上自己补充的代码，包括简单的计时器，链表背包迭代器，表达式计算相关
● 简单的计时器，分别记录墙上时间和 CPU 时间。
1 package package01;
2
3 import java.lang.management.ThreadMXBean;
4 import java.lang.management.ManagementFactory;
5
6 public class class01
7 {
8 private final ThreadMXBean threadTimer; // CPU 计时器
9 private final long startWall; // 墙上时间
10 private final long startCPU; // CPU 时间
11
12 public class01() // 构造函数即开始计时
13 {
14 startWall = System.currentTimeMillis();
15 threadTimer = ManagementFactory.getThreadMXBean();
16 startCPU = threadTimer.getCurrentThreadCpuTime();
17 }
18
19 public void elapsedTime() // 停止计时并输出结果
20 {
21 long finishWall = System.currentTimeMillis();
22 long finishCPU = threadTimer.getCurrentThreadCpuTime();
23 System.out.printf("Wall time: %d ms, CPU time:%d ns\n", finishWall - startWall, finishCPU - startCPU);
24 }
25
26 public static void main(String[] args)
27 {
28 class01 clock = new class01();
29
30 double sum = 0.0;
31 for (int i = 1; i <= 100000000; i++)
32 sum += Math.pow(i, 0.5);
33
34 clock.elapsedTime();
35 }
36 }
● 在链表背包数据结构的基础上实现迭代器
1 package package01;
2
3 import edu.princeton.cs.algs4.StdIn;
4 import edu.princeton.cs.algs4.StdOut;
5 import java.util.Iterator;
6 import java.util.NoSuchElementException;
7
8 public class class01<Item> implements Iterable<Item>
9 {
10 private Node<Item> first; // 头节点
11 private int n; // 物品数
12
13 private static class Node<Item> // 链表结构
14 {
15 private Item item;
16 private Node<Item> next;
17 }
18
19 public class01()
20 {
21 first = null;
22 n = 0;
23 }
24
25 public boolean isEmpty()
26 {
27 return first == null;
28 }
29
30 public int size()
31 {
32 return n;
33 }
34
35 public void add(Item item)
36 {
37 Node<Item> oldfirst = first;
38 first = new Node<Item>();
39 first.item = item;
40 first.next = oldfirst;
41 n++;
42 }
43
44 public Iterator<Item> iterator() // 实现迭代器
45 {
46 return new ListIterator<Item>(first);
47 }
48
49 private class ListIterator<Item> implements Iterator<Item> // 迭代器的基本结构
50 {
51 private Node<Item> current;
52 public ListIterator(Node<Item> first)
53 {
54 current = first;
55 }
56
57 public boolean hasNext()
58 {
59 return current != null;
60 }
61 public void remove() // 不含 remove() 方法
62 {
63 throw new UnsupportedOperationException();
64 }
65
66 public Item next()
67 {
68 if (!hasNext())
69 throw new NoSuchElementException();
70 Item item = current.item;
71 current = current.next;
72 return item;
73 }
74 }
75
76 public static void main(String[] args)
77 {
78 class01<String> bag = new class01<String>();
79 while (!StdIn.isEmpty())
80 {
81 String item = StdIn.readString();
82 bag.add(item);
83 }
84
85 StdOut.println("size of bag = " + bag.size());
86 for (String s : bag) {
87 StdOut.println(s);
88 }
89 }
90 }
■ 输入输出要点，在这里使用了 algs4 的 StdIn，需要给出多行的程序输入（用 "<" 重定向的不用考虑这部分）。在命令行中执行 java XXX 后逐行输入，用回车键隔开，全部输入完后回车到新的一行，按 Ctrl + z 结束输入程序自动向下运行；而在 IntelliJ中，点击执行后逐行输入，用回车键隔开，全部输入完后回车到新的一行，按 Ctrl + d 结束输入程序自动向下运行
● 表达式计算相关
1 package package01;
2
3 import edu.princeton.cs.algs4.Stack;
4 import edu.princeton.cs.algs4.StdIn;
5
6 public class class01
7 {
8 public static double evaluate(String args) // Dijkstra 双栈中缀表达式计算
9 {
10 Stack<String> ops = new Stack<String>(); // 算符栈
11 Stack<Double> vals = new Stack<Double>(); // 操作数栈
12
13 for (int i = 0; i<args.length(); i++)
14 {
15 String s = args.charAt(i) + "";
16
17 if (s.equals("(") || s.equals(" ")) // 跳过左括号和空格
18 ;
19 else if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) // 运算符，压栈
20 ops.push(s);
21 else if (s.equals(")")) // 右括号，吐栈并计算
22 {
23 String op = ops.pop();
24 double v = vals.pop();
25
26 if (op.equals("+"))
27 v = vals.pop() + v;
28 else if (op.equals("-"))
29 v = vals.pop() - v;
30 else if (op.equals("*"))
31 v = vals.pop()*v;
32 else if (op.equals("/"))
33 v = vals.pop() / v;
34 else if (op.equals("sqrt"))
35 v = Math.sqrt(v);
36
37 vals.push(v); // 数字压栈，缺点是只能读取一位数字
38 }
39 else vals.push(Double.parseDouble(s)); // 计算结果压栈
40 }
41 return vals.pop();
42 }
43
44 public static String correctBracket(String[] args) // P102, Ex1.3.9，将中缀表达式缺失的左括号补全
45 {
46 Stack<String> ops = new Stack<String>();
47 Stack<String> vals = new Stack<String>();
48
49 for (; !StdIn.isEmpty();)
50 {
51 String s = StdIn.readString();
52
53 if (s.equals("(") || s.equals(" ")) // 左括号，不作任何操作
54 ;
55 if (s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/") || s.equals("sqrt")) // 运算符，压栈
56 ops.push(s);
57 else if (s.equals(")")) // 右括号，吐栈
58 {
59 String op = ops.pop();
60 String v = vals.pop();
61 if (op.equals("+") || op.equals("-") || op.equals("*") || op.equals("/"))
62 v = String.format("( %s %s %s )", vals.pop(), op, v);
63 else if (op.equals("sqrt"))
64 v = String.format("( %s ( %s ) )", op, v);
65
66 vals.push(v);
67 }
68 else vals.push(s);
69 //else vals.push(((Double)Double.parseDouble(s)).toString()); // 输出浮点数的情况
70 }
71 return vals.pop();
72 }
73
74 public static void main(String[] args)// 测试输入：1 + 2 ) * 3 - 4 ) * 5 - 6 ) ) )
75 {
76 String output1 = correctBracket(args);
77 double output2 = evaluate(output1);
78 System.out.printf("%s\n%f\n", output1, output2);
79 }
80 }
内容总结
以上是互联网集市为您收集整理的《算法》第一章部分程序 part 2全部内容，希望文章能够帮你解决《算法》第一章部分程序 part 2所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】