Java语言程序设计（梁勇）第21-30章全部完整习题答案

import java.util.ArrayList; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Stack; import javafx.application.Application; import javafx.geometry.Point2D; import javafx.geometry.Pos; import javafx.scene.Scene; import javafx.scene.control.Button; import javafx.scene.image.ImageView; import javafx.scene.layout.BorderPane; import javafx.scene.layout.HBox; import javafx.scene.layout.Pane; import javafx.scene.shape.Line; import javafx.stage.Stage; /** Use the old Graph.java, AbstractGraph.java, UnweightedGraph.java. Need to replace it in the future.*/ public class Exercise28_18 extends Application { private Model model = new Model(); private static final int SIZE = 8; private int startX = 0; private int startY = 0; private ArrayList<Point2D> moveHistory = null; @Override // Override the start method in the Application class public void start(Stage primaryStage) { BorderPane pane = new BorderPane(); ChessBoard board = new ChessBoard(); pane.setCenter(board); Button btPath = new Button("Path"); Button btCycle = new Button("Cycle"); HBox hBox = new HBox(5); hBox.getChildren().addAll(btPath, btCycle); hBox.setAlignment(Pos.CENTER); pane.setBottom(hBox); // Create a scene and place it in the stage Scene scene = new Scene(pane, 250, 250); primaryStage.setTitle("Exercise28_18"); // Set the stage title primaryStage.setScene(scene); // Place the scene in the stage primaryStage.show(); // Display the stage board.repaint(); btPath.setOnAction(e -> { resetMoveHistory(); List<Integer> list = model.findHamiltonianPath(startX, startY); for (int i = 0; i < list.size(); i++) { addMoveHistory(list.get(i) / 8, list.get(i) % 8); } board.repaint(); }); btCycle.setOnAction(e -> { resetMoveHistory(); List<Integer> list = model.findHamiltonianCycle(startX, startY); for (int i = 0; i < list.size(); i++) { addMoveHistory(list.get(i) / 8, list.get(i) % 8); } board.repaint(); }); scene.widthProperty().addListener(ov -> board.repaint()); scene.heightProperty().addListener(ov -> board.repaint()); } public void resetMoveHistory() { moveHistory = new ArrayList(63); } public void addMoveHistory(int x, int y) { moveHistory.add(new Point2D(x, y)); } public void removeLastMoveHistory() { moveHistory.remove(moveHistory.size() - 1); } private class ChessBoard extends Pane { ImageView knightImageView = new ImageView("image/knight.jpg"); ChessBoard() { this.setOnMouseClicked(e -> { startX = (int) (e.getX() / (getWidth() / SIZE)); startY = (int) (e.getY() / (getHeight() / SIZE)); resetMoveHistory(); repaint(); }); } protected void repaint() { // Clear previous drawing this.getChildren().clear(); // Add the Knight image this.getChildren().add(knightImageView); knightImageView.setX(startX * getWidth() / SIZE); knightImageView.setY(startY * getHeight() / SIZE); knightImageView.setFitWidth(getWidth() / SIZE); knightImageView.setFitHeight(getHeight() / SIZE); // Draw the lines for (int i = 1; i <= SIZE; i++) { this.getChildren().add( new Line(0, i * getHeight() / SIZE, getWidth(), i * getHeight() / SIZE)); this.getChildren().add( new Line(i * getWidth() / SIZE, 0, i * getWidth() / SIZE, getHeight())); } // Draw the moves if (moveHistory != null) { for (int i = 1; i < moveHistory.size(); i++) { Point2D p1 = moveHistory.get(i - 1); Point2D p2 = moveHistory.get(i); this.getChildren().add( new Line(p1.getX() * (getWidth() / SIZE) + getWidth() / SIZE / 2, p1.getY() * (getHeight() / SIZE) + (getHeight() / SIZE / 2), p2.getX() * (getWidth() / SIZE) + getWidth() / SIZE / 2, p2.getY() * (getHeight() / SIZE) + getHeight() / SIZE / 2)); } } } } /** * The main method is only needed for the IDE with limited * JavaFX support. Not needed for running from the command line. */ public static void main(String[] args) { launch(args); } /** * Edge inner class inside the AbstractGraph class */ public static class Edge { public int u; // Starting vertex of the edge public int v; // Ending vertex of the edge /** * Construct an edge for (u, v) */ public Edge(int u, int v) { this.u = u; this.v = v; } } public interface Graph { /** * Return the number of vertices in the graph */ public int getSize(); /** * Return the vertices in the graph */ public Object[] getVertices(); /** * Return the object for the specified vertex index */ public Object getVertex(int index); /** * Return the index for the specified vertex object */ public int getIndex(Object v); /** * Return the neighbors of vertex v */ public java.util.List getNeighbors(int v); /** * Return the degree for a specified vertex */ public int getDegree(int v); /** * Return the adjacency matrix */ public int[][] getAdjacencyMatrix(); /** * Print the adjacency matrix */ public void printAdjacencyMatrix(); /** * Print the edges */ public void printEdges(); /** * Obtain a depth-first search tree */ public AbstractGraph.Tree dfs(int v); /** * Obtain a breadth-first search tree */ public AbstractGraph.Tree bfs(int v); /** * Obtain a depth-first search tree */ public List<Integer> getHamiltonianPath(int v); /** * Obtain a depth-first search tree */ public List<Integer> getHamiltonianCycle(int v); /** Return a Hamiltonian cycle * Return null if the graph does not contain a Hamiltonian cycle */ public List<Integer> getHamiltonianCycle(); } public abstract class AbstractGraph implements Graph { protected Object[] vertices; // Store vertices protected LinkedList<Integer>[] neighbors; // Adjacency lists /** * Construct a graph from edges and vertices stored in arrays */ protected AbstractGraph(int[][] edges, Object[] vertices) { this.vertices = vertices; createAdjacencyLists(edges, vertices.length); } /** * Construct a graph from edges and vertices stored in ArrayList */ protected AbstractGraph(List<Edge> edges, List<Object> vertices) { this.vertices = vertices.toArray(); createAdjacencyLists(edges, vertices.size()); } /** * Construct a graph from edges and vertices in ArrayList */ protected AbstractGraph(List<Edge> edges, int numberOfVertices) { vertices = new Integer[numberOfVertices]; // Create vertices for (int i = 0; i < numberOfVertices; i++) { vertices[i] = new Integer(i); // vertices is {0, 1, 2, ...} } createAdjacencyLists(edges, numberOfVertices); } /** * Construct a graph from edges in array */ protected AbstractGraph(int[][] edges, int numberOfVertices) { vertices = new Integer[numberOfVertices]; // Create vertices for (int i = 0; i < numberOfVertices; i++) { vertices[i] = new Integer(i); // vertices is {0, 1, 2, ...} } createAdjacencyLists(edges, numberOfVertices); } /** * Create adjacency lists for each vertex */ @SuppressWarnings("unchecked") private void createAdjacencyLists(