ACM中使用java

目录java输出重定向 (2)java输入重定向 (2)java中使用控制台输入 (2)java输入输出重定向 (3)Java中输入多组数据时的技巧 (3)Java中对象无重复排序 (4)单链表 (7)循环链表 (9)栈 (11)队列 (13)二叉排序树 (15)最小生成树（普里姆算法） (18)深度优先搜索和广度优先搜索 (21)最短路径求解—Dijkstra算法 (26)1、java输出重定向import java.io.FileOutputStream;import java.io.PrintStream;public class Main {public static void main(String args[]) throws Exception { PrintStream out = new PrintStream(newFileOutputStream("pc2.estdout"));System.setOut(out);System.out.println("Hello World!");out.close();}}2、java输入重定向import java.io.BufferedInputStream;import java.io.FileInputStream;import java.util.Scanner;public class Test08 {public static void main(String[] args) throws Exception { // 输入重定向BufferedInputStream in = new BufferedInputStream(new FileInputStream("std.in"));System.setIn(in);Scanner stdin = new Scanner(System.in);int a = stdin.nextInt();int b = stdin.nextInt();System.out.print(a + b);}}3、java中使用控制台输入import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner input = new Scanner(System.in);String str1 = input.nextLine();System.out.println(str1);}}4、java输入输出重定向import java.io.BufferedInputStream;import java.io.FileInputStream;import java.io.FileOutputStream;import java.io.PrintStream;import java.util.Scanner;public class Main {public static void main(String[] args) throws Exception { // 输入重定向BufferedInputStream in = new BufferedInputStream(new FileInputStream("std.in"));System.setIn(in);Scanner stdin = new Scanner(System.in);int a = stdin.nextInt();int b = stdin.nextInt();// 输出重定向PrintStream out = new PrintStream(new FileOutputStream("estdout.pc2"));System.setOut(out);System.out.print(a + b);out.close(); // 关闭重定向}}Java中输入多组数据时的技巧public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt(); // 表示有m组数据Activity[] act = null;Activity[][] t = new Activity[m][];for (int i = 0; i < m; i++) {int n = sc.nextInt(); // 表示有n个活动act = new Activity[n];for (int k = 0; k < n; k++) {act[k] = new Activity();}for (int j = 0; j < n; j++) {act[j].setTime(sc.nextInt(), sc.nextInt());}t[i] = act;}for (int i = 0; i < m; i++) {sort(t[i]);delete(t[i]);System.out.println(count(t[i]));}}Java中对象无重复排序import java.util.ArrayList;import java.util.Arrays;import parator;import java.util.HashSet;import java.util.Scanner;public class Per {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt(); // 代表m组测试数据for (int i = 0; i < m; i++) {int n = sc.nextInt(); // 代表n个长方形Rect[] s = new Rect[n];for (int j = 0; j < n; j++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();int height = b > c ? b : c;int width = b < c ? b : c;s[j] = new Rect(a, height, width);}HashSet set = new HashSet();ArrayList list = new ArrayList();for (int j = 0; j < s.length; j++) {if (set.add(s[j]))list.add(s[j]);}Object[] arr = list.toArray();Arrays.sort(arr, new MyComparator());for (Object j : arr)System.out.println(j);}}public static class MyComparator implements Comparator {@Overridepublic int compare(Object o1, Object o2) {Rect rc1 = (Rect) o1;Rect rc2 = (Rect) o2;if (rc1.id > rc2.id) {return 1;} else if (rc1.id < rc2.id) {return -1;} else {if (rc1.height > rc2.height) {return 1;} else if (rc1.height < rc2.height) {return -1;} else {if (rc1.width > rc2.width) {return 1;} else if (rc1.width < rc2.width) {return -1;} elsereturn 0;}}}}public static class Rect {int height;int id;int width;public Rect(int i, int hei, int wid) {height = hei;id = i;width = wid;}public String toString() {return id + " " + height + " " + width;}public boolean equals(Object o) {Rect t = (Rect) o;return t.height == height && t.id == id && t.width == width;}public int hashCode() {return 3 * height + 4 * id + 5 * width;}}}Java中的常用数据结构1.单链表public class Main {public static void main(String[] args){LinkList l = new LinkList();l.add("A");l.add("B");l.add("C");l.add("D");l.add("E");printList(l.head);System.out.println();LinkNode t = l.search("E");System.out.println(t.data);l.delete("E");LinkNode t1 = l.search("E");System.out.println(t1.data);}public static void printList(LinkNode tmp){System.out.print(tmp.data+" ");if(tmp.next!=null){printList(tmp.next);}}}//定义节点类class LinkNode{Object data = null; //保存节点内容LinkNode next = null; //保存节点的下一个节点public LinkNode(Object data){this(data,null);}public LinkNode(Object data,LinkNode tmp){ this.data = data;this.next = tmp;}}//定义链表类，对节点进行封装class LinkList{LinkNode head = null; //定义头结点LinkNode p = null; //p节点用来保存节点移动后的当前位置//向链表中增加成员public void add(Object data){LinkNode tmp = new LinkNode(data);if(head==null){head = tmp;p = tmp;p.next = null;}else{p.next = tmp;p = tmp;p.next = null;}}//查找链表中的某节点public LinkNode search(Object data){p = head;boolean i = false; //用于判断节点是否找到while(p!=null){if(p.data==data){i = true;break;}p = p.next;}if(i==false){return (new LinkNode("不存在"));}else{return p;}}//删除链表中某节点public void delete(Object data){if(search(data).data=="不存在"){System.out.println("找不到该节点，删除失败！");}else{LinkNode tmp;tmp = search(data); //找到要删除的节点tmpif(tmp.next!=null){LinkNode ch; //通过将要删除的节点（即tmp）的下一个节点的内容传给tmp，ch = tmp.next; //然后再将tmp的下一个节点从链表中移走达到删除tmp的目的tmp.data = ch.data;tmp.next = ch.next;}else{ //如果要删除的是最后一个结点，则将节点的内容修改，search(data).data = "不存在"; //相当于删除了该节点}}}}2.循环链表public class Main {public static void main(String[] args){LinkList l = new LinkList();l.setLen(30);l.createLink();l.setK(1);l.setM(9);l.play();}}class Node{int data;Node next;public Node(int data){this.data = data;}}class LinkList{Node head = null; //定义头节点Node p = null; //定义p保存当前节点的位置int len = 0; //保存链表的长度int k = 0; //保存从第几人开始报数int m = 0; //保存报到第几个数public void setLen(int len){this.len = len; //设置链表长度}public void setK(int k){this.k = k; //设置从第几人开始报数}public void setM(int m){this.m = m; //设置报到第几个数}public void createLink(){for(int i=1;i<=len;i++){Node ch = new Node(i); //生成一个新节点if(i==1){head = ch; //将第一个新节点设为头节点p = ch; //p保存移动后的当前位置的节点}else if(i==len){p.next = ch;p = ch;p.next= head; //将最后一个节点的下一个节点设为头节点，形成循环链表}else{p.next = ch;p = ch;}}}public void show(Node node){System.out.print(node.data+" ");}public void play(){char[] a = new char[30];for(int i=0;i<a.length;i++){a[i] = '@';}p = head;//找到第k个人for(int i=1;i<k;i++){p = p.next;}while(this.len!=15){for(int i=1;i<m;i++){p = p.next;}//show(p); //打印读到m的人a[p.data-1] = '+';//删除第m个人Node tmp = p.next;p.data = tmp.data;p.next = tmp.next;this.len--;};for(int i=0;i<a.length;i++){System.out.print(a[i]);}}}3.栈public class Main {public static void main(String[] args){StackLi sl = new StackLi();sl.push("A");sl.push("B");sl.push("C");sl.push("D");sl.push("E");print(sl.getTopStack()); //从栈顶开始向下输出元素sl.pop();sl.pop();sl.pop();sl.pop();print(sl.getTopStack());print(sl.getTopStack()); //输出栈顶元素}public static void print(ListNode node){if(node==null){System.out.println("桟是空的，没有元素可以输出!"); }else{System.out.print(node.element+" ");if(node.next!=null){print(node.next);}else{System.out.println(); //桟中全部元素输出后换行 }}}}//定义异常类class Underflow extends Throwable{private String info;public Underflow(){System.out.println("桟已空，无法出桟！");}}//定义链表节点类class ListNode{Object element;ListNode next;public ListNode(Object c){this(c,null);}public ListNode(Object c,ListNode node){this.element = c;this.next = node;}}//定义桟类class StackLi{private ListNode topOffStack;public StackLi(){topOffStack = null;}//取得栈顶public ListNode getTopStack(){return topOffStack;}//判断是否桟满public boolean isFull(){return false;}//判断是否桟空public boolean isEmpty(){return topOffStack == null;}//清空桟public void makeEmpty(){topOffStack = null;}//进栈public void push(Object x){topOffStack = new ListNode(x,topOffStack); }//出桟public void pop(){if (isEmpty()){new Underflow();}else{topOffStack = topOffStack.next;}}//出桟并取得栈顶内容public Object topAndPop(){if(isEmpty()){return null;}Object topItem = topOffStack.element;topOffStack = topOffStack.next;return topItem;}}4.队列public class Main {public static void main(String[] args){QueueAr qa = new QueueAr();qa.enqueue("A"); //依次入队qa.enqueue("B");qa.enqueue("C");qa.enqueue("D");qa.enqueue("E");qa.dequeue(); //出队print(qa.getFront()); //打印队列中所有成员qa.enqueue("F");print(qa.getFront());qa.makeEmpty(); //清空队列print(qa.getFront());}public static void print(ListNode node){if(node==null){System.out.println("队列是空的，没有元素可以输出!"); }else{System.out.print(node.element+" ");if(node.next!=null){print(node.next);}else{System.out.println(); //队列中全部元素输出后换行 }}}}//定义链表节点类class ListNode{Object element;ListNode next;public ListNode(Object c){this(c,null);}public ListNode(Object c,ListNode node){ this.element = c;this.next = node;}}//定义队列class QueueAr{private ListNode front;private ListNode back;public QueueAr(){back = null;front = null;}//判断队列是否为空public boolean isEmpty(){return front == null;}//判断队列是否满，此处队列永远不会满public boolean isFull(){return false;}//清空队列public void makeEmpty(){front = null;back = null;}//去的队列头public ListNode getFront(){return front;}//入队public void enqueue(Object x){ListNode ch = new ListNode(x);if(isEmpty()){back = ch;front = back;}else{back.next = ch;back = ch;}}//出队public void dequeue(){if(isEmpty()==true){System.out.println("队列已空，无法出队！");}else{front = front.next;}}}5.二叉排序树public class TreeDemo02 {public static void main(String[] args) {BinarySearchTree btr = new BinarySearchTree();btr.insert(6);btr.insert(2);btr.insert(1);btr.insert(3);btr.insert(4);btr.insert(8);System.out.println(btr.find(4));System.out.println(btr.findMin());System.out.println(btr.findMax());btr.printTree();}}// 定义树节点class BinaryNode {Comparable element; // 保存节点内容BinaryNode left; // 保存节点的左孩子BinaryNode right; // 保存节点的右孩子// 定义构造函数，初始化成员BinaryNode(Comparable theElement) {this(theElement, null, null);}BinaryNode(Comparable theElement, BinaryNode lt, BinaryNode rt) { element = theElement;left = lt;right = rt;}}// 定义二叉查找树，将树节点封装成树并进行各种操作class BinarySearchTree {private BinaryNode root;public BinarySearchTree() {root = null;}// 判断树是否为空public boolean isEmpty() {return root == null;}// 查找树中是否存在某节点public Comparable find(Comparable x) { return find2(x, root).element;}// 查找树中最小的节点public Comparable findMin() {return findMin2(root).element;}// 查找树中最大的节点public Comparable findMax() {return findMax2(root).element;}// 向树中插入某节点public void insert(Comparable x) {root = insert2(x, root);}// 删除树中某节点public void remove(Comparable x) {root = remove2(x, root);}// 遍历二叉树public void printTree() {if (isEmpty()) {System.out.println("Empty Tree!");} else {printTree2(root);System.out.println();}}// 查找的具体操作,该操作对外是透明的,后面的操作同理private BinaryNode find2(Comparable x, BinaryNode t) {// 如果不存在，就新添加一个辅助树节点，并将其内容设为不存在if (t == null) {BinaryNode s = new BinaryNode("不存在该元素！");return s;}if (pareTo(t.element) < 0) { // 如果查找的元素比当前根节点小，则继续再该节点的左子树中查找，直至根节点为空return find2(x, t.left);} else if (pareTo(t.element) > 0) { // 如果查找的元素比当前根节点大，则继续再该节点的右子树中查找，直至根节点为空return find2(x, t.right);} elsereturn t; // 如果查找的节点内容和当前根节点的内容相等，则返回当前根节点}// 找最小节点的具体过程private BinaryNode findMin2(BinaryNode t) {if (t == null) {return null;} else if (t.left == null) {return t;}return findMin2(t.left);}// 找最大节点的具体过程private BinaryNode findMax2(BinaryNode t) {if (t != null) {while (t.right != null) {t = t.right;}}return t;}// 构造二叉查找树的具体过程private BinaryNode insert2(Comparable x, BinaryNode t) {if (t == null) { // 若树是空的，则构造一棵新的树，t为树的根t = new BinaryNode(x, null, null);} else if (pareTo(t.element) < 0) { // 如果要插入的元素小于当前节点，则插入在该节点的左边t.left = insert2(x, t.left);} else if (pareTo(t.element) > 0) { // 如果要插入的元素大于当前节点，则插入在该节点的又边t.right = insert2(x, t.right);} else; // 否则什么也不做return t;}// 删除节点的具体操作过程private BinaryNode remove2(Comparable x, BinaryNode t) {if (t == null) {return t;}if (pareTo(t.element) < 0) {t.left = remove2(x, t.left);} else if (pareTo(t.element) > 0) {t.right = remove2(x, t.right);} else if (t.left != null && t.right != null) {t.element = findMin2(t.right).element;t.right = remove2(x, t.right);} else {t = (t.left != null) ? t.left : t.right;}return t;}// 遍历二叉树的具体过程private void printTree2(BinaryNode t) {if (t != null) {printTree2(t.left);System.out.print(t.element + " ");printTree2(t.right);}}}6、最小生成树（普里姆算法）import java.util.Scanner;public class PrimDemo {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();// 图的顶点数int m = sc.nextInt(); // 图的边数if (n == 0 && m == 0)break;int[][] map = new int[n][n]; //存放边的权值for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {map[i][j] = Integer.MAX_VALUE; //起点i，终点为j的边的权植。