data程序讲解、java编程调试、java程序辅导
- 首页 >> Matlab编程 The guide describes what you need to do for the minimum, core, completion,
and challenge
The data:
stops.txt stores the stops . In the file, the first line is the title. From
the second line, each line represents a stop, including its ID, name, latitude
and longitude. The entries are separated by tab.
trips.txt stores the trips of the transport network. Each trip is a sequence
of stops. In the file, the first line is the title. From the second line,
each line represents a trip. The first entry is the trip ID. Then, the sequence
of stops in this trip is represented by the second to the last entry of the
line. The entries are separated by tab as well. In each trip, there is a
directed edge from each stop in the sequence to its successive stop.
The program should read the data from the data files into an appropriate set
of data structures, and then draw the graph. The program should also have
the proper functionalities when the user presses the buttons, clicks on the
map to select a stop, and type something into the search box. The details
of the functionalities are given in the next section.
GUI is provided in the model code called GUI.java. This contains an area for
drawing the graph, a loading button, some navigation buttons, a search box,
and a text output area. It is an abstract class; the behaviour of how to draw
the drawing area, load the data, and what happens when you press the
navigation buttons, click the screen, or enter something in the search box
are left unimplemented. You will need to extend the GUI class and implement
these using your data structures. For an example of how to do this,
SquaresExample.java repurposes the GUI class to make an unrelated little game.
The program will need a collection of Stop objects, a collection of Trip
objects, and a collection of Connection objects. You will need to access stops
both by their IDs and by their names. The first can be accomplished with a
Hash Map. The second should use a Trie structure, since it needs to be able
to access all the roads whose names start with a specified prefix. The Stops
and Connections form a graph, with the Stops as the nodes, and the Connections
as the edges. The graph is directed (each trip is directed), is a multi-graph
(there can be more than one connection between two stops belonging to
different trips), but has no ‘looped’ connections that start and end at
the same stop. You need to choose an appropriate data structure for this graph
recommend using Stop objects and Connection objects, where the Stop objects
include a list of all the incoming and outgoing Connections. The Stop objects
also need to store their location, both for drawing them and for finding the
stop the user clicks on. The Connection objects need to store the Stops at
each end, and the Trip they belong to. You should decide whether to use the
IDs in the data structure or to simply connect Stop and Connection objects
directly to each other.
Solving the problem in stages
Minimum – Parsing, data structures, and drawing.
• Construct classes to represent Stops, Trips, and Connections between two
stops. The class should have methods to read the data from the files and
construct the objects. Hint: Use the Location class to represent positions
of the Stops. The class includes methods for converting from
latitude/longitude to x/y coordinates in kilometers.
• Make methods to read the data files, parse them, and create data structures.
When using the GUI class, these methods should run when the onLoad method
is called. This method is passed a File object for each of the stop and trip
files. Hint: When reading the Trips, you need to add each of the Connections
in the trip to the appropriate Stop objects. Hint: Loading the data is best
done with a BufferedReader.
• Draw the graph by filling in the redraw method left abstract in the GUI
class. This method should call a draw method on the Connection and Stop, which
should use the passed Graphics object. It will make the zooming easier if
these methods also take an origin and scale factor as parameters, so they
can calculate where on the graphics object they should be drawn.
Core – Using the graph structure and other functionality.
• Allow the user to navigate the map, i.e. implement panning and zooming
with the buttons. Whenever these buttons are pressed, the onMove method (left
abstract in GUI) is called, and is passed an enum representing which button
was pushed; this is where should write the movement logic.
• Make the program respond to the mouse so that the user can select a stop
with the mouse, and the program will then highlight it, and print out the
name of the stop and the id of all the trips going through the stop. This
can be done by implementing the onClick method left abstract by the GUI class,
which is called whenever the mouse is clicked. This method is passed a
MouseEvent object, which contains, among other things, the coordinates of
click within the graphics area. The simplest method will do a linear search
through the collection of stops to find the closest one to the mouse position.
(Use the methods in Location to convert between pixel based positions on the
screen and the locations in the Stops.)
• Implement the behaviour of the search box in the top right, which should
allow a user to select a Stop by entering its name. This can be done with
the onSearch method, which is called whenever the user presses ‘enter’ in
the search box. When they complete their entry, the program should highlight
the stop with name (exactly) matching their input, and highlight all the trips
going through that stop. Hint: Remember that there may be multiple Trip
objects going through the stop, and each Trip object may have multiple
Connections in it. Hint: The search box, and its contents, can be accessed
with the getSearchBox method in GUI.
• The text output area at the bottom of the window should be used to show
information about stops and trips, and can be accessed via the
getTextOutputArea method in GUI.
Completion – Making a trie and improving search.
• To make the program more usable, we want the search function to highlight
all the stops whose name is prefixed by the search input, and not just an
exact match. A linear search is not an efficient way of doing this, and using
some hashing scheme wouldn’t work either, as we need to do prefix-matching
(unless the hashing scheme was very cleverly designed). A better way is to
construct a trie data structure to store all the Stop objects, indexed by
their name. This data structure will need methods to add a new stop, and to
retrieve all stops matching a given prefix.
• Improve the search using a trie. Highlight all stops that start with the
prefix typed into the search box. For example, there are 4 stop names starting
with “VRD”. If the user’s search query exactly matches a stop name, it
should only highlight and show exact matches. Print out the name of the
matched stops in the text output area. Also, highlight all the trips going
through the match stops. Hint: The UPDATE_ON_EVERY_CHARACTER variable in the
GUI class can be set to true to make the onSearch method be called each time
the user types a character in the search box, and not just when they press
enter.
Challenge – Quad-trees and UI improvements.
• A linear search through the stops to find the closest one is also inefficient,
but searching for inexact matches for 2D positions doesn’t work with hashing
or binary search. (This problem is a standard problem in computer graphics.)
The right structure to use for searching for the closest 2D point is called
a quad-tree .Implement a quad-tree index of all the nodes and use it to search
for the closest node to the mouse location.
• The user interface in the GUI class is functional, but could be improved
further; find a way to significantly improve it. Two ideas are: – Implement
navigation with the mouse and scroll wheel. – Add a drop-down suggestions
box to the search box, which the user can select completions from.
and challenge
The data:
stops.txt stores the stops . In the file, the first line is the title. From
the second line, each line represents a stop, including its ID, name, latitude
and longitude. The entries are separated by tab.
trips.txt stores the trips of the transport network. Each trip is a sequence
of stops. In the file, the first line is the title. From the second line,
each line represents a trip. The first entry is the trip ID. Then, the sequence
of stops in this trip is represented by the second to the last entry of the
line. The entries are separated by tab as well. In each trip, there is a
directed edge from each stop in the sequence to its successive stop.
The program should read the data from the data files into an appropriate set
of data structures, and then draw the graph. The program should also have
the proper functionalities when the user presses the buttons, clicks on the
map to select a stop, and type something into the search box. The details
of the functionalities are given in the next section.
GUI is provided in the model code called GUI.java. This contains an area for
drawing the graph, a loading button, some navigation buttons, a search box,
and a text output area. It is an abstract class; the behaviour of how to draw
the drawing area, load the data, and what happens when you press the
navigation buttons, click the screen, or enter something in the search box
are left unimplemented. You will need to extend the GUI class and implement
these using your data structures. For an example of how to do this,
SquaresExample.java repurposes the GUI class to make an unrelated little game.
The program will need a collection of Stop objects, a collection of Trip
objects, and a collection of Connection objects. You will need to access stops
both by their IDs and by their names. The first can be accomplished with a
Hash Map. The second should use a Trie structure, since it needs to be able
to access all the roads whose names start with a specified prefix. The Stops
and Connections form a graph, with the Stops as the nodes, and the Connections
as the edges. The graph is directed (each trip is directed), is a multi-graph
(there can be more than one connection between two stops belonging to
different trips), but has no ‘looped’ connections that start and end at
the same stop. You need to choose an appropriate data structure for this graph
recommend using Stop objects and Connection objects, where the Stop objects
include a list of all the incoming and outgoing Connections. The Stop objects
also need to store their location, both for drawing them and for finding the
stop the user clicks on. The Connection objects need to store the Stops at
each end, and the Trip they belong to. You should decide whether to use the
IDs in the data structure or to simply connect Stop and Connection objects
directly to each other.
Solving the problem in stages
Minimum – Parsing, data structures, and drawing.
• Construct classes to represent Stops, Trips, and Connections between two
stops. The class should have methods to read the data from the files and
construct the objects. Hint: Use the Location class to represent positions
of the Stops. The class includes methods for converting from
latitude/longitude to x/y coordinates in kilometers.
• Make methods to read the data files, parse them, and create data structures.
When using the GUI class, these methods should run when the onLoad method
is called. This method is passed a File object for each of the stop and trip
files. Hint: When reading the Trips, you need to add each of the Connections
in the trip to the appropriate Stop objects. Hint: Loading the data is best
done with a BufferedReader.
• Draw the graph by filling in the redraw method left abstract in the GUI
class. This method should call a draw method on the Connection and Stop, which
should use the passed Graphics object. It will make the zooming easier if
these methods also take an origin and scale factor as parameters, so they
can calculate where on the graphics object they should be drawn.
Core – Using the graph structure and other functionality.
• Allow the user to navigate the map, i.e. implement panning and zooming
with the buttons. Whenever these buttons are pressed, the onMove method (left
abstract in GUI) is called, and is passed an enum representing which button
was pushed; this is where should write the movement logic.
• Make the program respond to the mouse so that the user can select a stop
with the mouse, and the program will then highlight it, and print out the
name of the stop and the id of all the trips going through the stop. This
can be done by implementing the onClick method left abstract by the GUI class,
which is called whenever the mouse is clicked. This method is passed a
MouseEvent object, which contains, among other things, the coordinates of
click within the graphics area. The simplest method will do a linear search
through the collection of stops to find the closest one to the mouse position.
(Use the methods in Location to convert between pixel based positions on the
screen and the locations in the Stops.)
• Implement the behaviour of the search box in the top right, which should
allow a user to select a Stop by entering its name. This can be done with
the onSearch method, which is called whenever the user presses ‘enter’ in
the search box. When they complete their entry, the program should highlight
the stop with name (exactly) matching their input, and highlight all the trips
going through that stop. Hint: Remember that there may be multiple Trip
objects going through the stop, and each Trip object may have multiple
Connections in it. Hint: The search box, and its contents, can be accessed
with the getSearchBox method in GUI.
• The text output area at the bottom of the window should be used to show
information about stops and trips, and can be accessed via the
getTextOutputArea method in GUI.
Completion – Making a trie and improving search.
• To make the program more usable, we want the search function to highlight
all the stops whose name is prefixed by the search input, and not just an
exact match. A linear search is not an efficient way of doing this, and using
some hashing scheme wouldn’t work either, as we need to do prefix-matching
(unless the hashing scheme was very cleverly designed). A better way is to
construct a trie data structure to store all the Stop objects, indexed by
their name. This data structure will need methods to add a new stop, and to
retrieve all stops matching a given prefix.
• Improve the search using a trie. Highlight all stops that start with the
prefix typed into the search box. For example, there are 4 stop names starting
with “VRD”. If the user’s search query exactly matches a stop name, it
should only highlight and show exact matches. Print out the name of the
matched stops in the text output area. Also, highlight all the trips going
through the match stops. Hint: The UPDATE_ON_EVERY_CHARACTER variable in the
GUI class can be set to true to make the onSearch method be called each time
the user types a character in the search box, and not just when they press
enter.
Challenge – Quad-trees and UI improvements.
• A linear search through the stops to find the closest one is also inefficient,
but searching for inexact matches for 2D positions doesn’t work with hashing
or binary search. (This problem is a standard problem in computer graphics.)
The right structure to use for searching for the closest 2D point is called
a quad-tree .Implement a quad-tree index of all the nodes and use it to search
for the closest node to the mouse location.
• The user interface in the GUI class is functional, but could be improved
further; find a way to significantly improve it. Two ideas are: – Implement
navigation with the mouse and scroll wheel. – Add a drop-down suggestions
box to the search box, which the user can select completions from.