Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP9024
Assignment
We may make minor changes to the spec to address/clarify some outstanding
issues. These may require minimal changes in your design/code, if at all.
Students are strongly encouraged to check the change log regularly.
Objectives
The assignment aims to give you more independent, self-directed practice with
advanced data structures, especially graphs
graph algorithms
asymptotic runtime analysis
Admin
Marks 3 marks for stage 1
(correctness)
5 marks for stage 2
(correctness)
2 marks for stage 3
(correctness)
1 mark for complexity
analysis
1 mark for style
———————
Total: 12 marks
Due
5:00:00pm on Monday
13 November (week 10)
Late 5% penalty per day late
(e.g. if you are 25 hours
late, your mark will be
reduced by 10%)
Aim
The objective is to write a program tripView.c that generates an optimal trip on (a
part of) Sydney's railway network based on user preferences.
Input
Railway stations
The first input to your program consists of an integer n > 0, indicating the number of
railway stations on the network, followed by n*2 lines of the form:
railway-station
transfer-time
where the first line is the name of a station and the second line denotes the time – in
minutes – it takes to transfer to a different train at that station.
Here is an example: ./tripView
Size of network: 3HarrisPark
1
TownHall
3
NorthSydney
2
You may assume that:
The input is syntactically correct.
The maximum length (strlen()) of the name of a railway station is 16 and
will not use any spaces.
The transfer time will be a positive integer.
No name will be input more than once.
Hint:
To read a single line with a station name you should use:
scanf("%s", name);
where name is a string, i.e. an array of chars.
Timetables
The next input to your program is an integer m > 0, indicating the number of trains on
any day, followed by m timetables. Each timetable starts with the number s > 1 of
stops followed by s*2 lines of the form:
station
hhmm
meaning that you can get on or off the train at that station at the given time (hh – hour,
mm – minute).
Here is an example:
Number of timetables: 2
Number of stops: 3HarrisPark
0945
TownHall
1020
NorthSydney
1035
Number of stops: 2TownHall
1024
NorthSydney
1033
You may assume that:
The input is syntactically correct.
All times are given as 4 digits and are valid, ranging from 0000 to 2359.
Only train stations that have been input earlier as part of the network will be
used.
The stops are input in the correct temporal order.
Each stop will be visited at most once in a single timetable.
All trains reach their final stop before midnight.
Trip View
The final input to your program are user queries:
From: HarrisPark
To: NorthSydney
Arrive at or before: 1200
As before, you may assume that the input is correct: Two different valid railway
stations followed by a valid time in the form of 4 digits.
Your program should terminate when the user enters "done" when prompted
with From:
From: done
Bye
Stage 1 (3 marks)
Stage 1 requires you to generate a suitable data structure from the input.
Test cases for this stage will only use queries FromStation, ToStation,
ArrivalTime such that:
there exists one, and only one, train that travels
from FromStation to ToStation ;
this train arrives on, or before, the given ArrivalTime ; and
this train is the desired output for the query.
Therefore, at this stage all you need to do is find and output the connection between
the two train stations, including all the stops along the way and the arrival/departure
times.