新南威尔士大学COMP9024 19T3——Sydney Transport Planner——课业解析

欢迎使用51辅导,51作业君孵化低价透明的学长辅导平台,服务保持优质,平均费用压低50%以上! 51fudao.top

新南威尔士大学COMP9024 19T3——Sydney Transport Planner——课业解析

题意: 

C编写myTrain.c程序,兼顾到达时间和用户喜好的情况,找到最佳的火车 

解析:

 程序首先提示用户输入站点数量和名字(站点名字无拼写错;名字不超过31个字符;名字不可重复);之后程序提示用户输入当天火车的数量及时刻表(2辆车对应两个时刻表,0935表示09:35出发,时刻后是输入到达的站点;时刻数字在0000~2359之间;所有列车在2359前到达终点站;站点名字必须是上一步用户输入中的);允许用户输入起点、终点站和要求到达时间,查询合适的列车并显示该列车的对应时刻表,若检测到用户输入“done”,则退出程序,形如: 第二阶段要求找到起点站最晚出发的、在规定时间前到达站点的列车,如果没有则显示No connection found.;第三阶段要求找到最早到达目标站点的火车。 

涉及知识点: 

C 图与算法、时间复杂度分析 

更多可加微信讨论 

微信号ITCSdaixie 

pdf

COMP9024 19T3 Assignment
Sydney Transport Planner
Data Structures and
Algorithms
Change Log
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.
Version 1: Released on 30 October 2019
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 marks for complexity analysis
1 mark for style
———————
Total: 12 marks
Due 11:00:00am on Tuesday 19 November (week 10)
Late 2 marks (16.67%) off the ceiling per day late
(e.g. if you are 25 hours late, your maximum possible mark is 8)
Aim
Your task is to write a program myTrain.c for finding an optimal train connection that takes into
account a given arrival time and user preferences.
Input
Station names
Your program should start by prompting the user to input a positive number n followed by n lines,
each containing the name of a train station. An example is:
prompt$ ./myTrain
Enter the number of stations: 3
Central
Parramatta
Chatswood
You may assume that:
• The input is syntactically correct.
• Station names require no more than 31 characters.
• No station name will be input more than once.
Hint:
To read a single line with a station name you may use:
scanf("%s", station); // station is a character array (= string variable)
Trains
Next, your program should ask the user for the number m of trains running during a day, followed
by m schedules. Each schedule requires the number of stops, k≥2, followed by k*2 lines of the
form:
hhmm
station-name
meaning that passengers can get on or off the train at that time (hh – hour, mm – minute) at that
station. An example is:
Enter the number of trains: 2
Enter the number of stops: 3
0935
Parramatta
1002
Central
1030
Chatswood
Enter the number of stops: 2
1010
Central
1025
Chatswood
You may assume that:
• The input is syntactically correct: 4 digits followed by a single space followed by the name of
a station.
• All times are valid and range from 0000 to 2359.
• There are no overnight trains: Each train will reach its final stop before midnight.
• Only valid station names that have been input before will be used.
Queries
After reading the network, your program should prompt the user to search for a connection:
From: Parramatta
To: Chatswood
Arrive by: 1230
Again you may assume that the input is correct: Only stations that have been entered before are
used and a valid time is given.
If the user inputs "done," then your program should terminate:
From: done
Thank you for using myTrain.
prompt$
Stage 1 (3 marks)
For stage 1, you should demonstrate that you can read the input and generate a suitable data
structure.
For this stage, all test cases will only use queries (From, To, ArriveBy) for which
• there is only one train between From and To ; and
• this train is guaranteed to arrive on, or before, the requested time, ArriveBy .
Hence, all you need to do for this stage is find and output this train connection, including all stops
along the way and the arrival/departure times. Here is an example to show the desired behaviour
of your program for a stage 1 test:
prompt$ ./myTrain
Enter the number of stations: 7
Burwood
Central
Chatswood
Hornsby
Parramatta
Redfern
Wynyard
Enter the number of trains: 2
Enter the number of stops: 5
0935
Parramatta
0950
Burwood
1005
Redfern
1012
Central
1017
Wynyard
Enter the number of stops: 2
1459
Chatswood
1530
Hornsby
From: Chatswood
To: Hornsby
Arrive by: 1700
1459 Chatswood
1530 Hornsby
From: Burwood
To: Central
Arrive by: 1015
0950 Burwood
1005 Redfern
1012 Central
From: done
Thank you for using myTrain.
prompt$
Stage 2 (5 marks)
For stage 2, you should extend your program for stage 1 such that it always finds, and outputs, a
connection between From and To that
• arrives on, or before, the requested time ArriveBy ; and
• departs as late as possible.
You should assume that:
• Changing trains takes no time: Passengers arriving at a station can get onto any other train
that leaves that station at the same time or later.
• In all test scenarios there will be at most one connection that satisfies all requirements.
If there is no connection, the output should be:
No connection found.
Here is an example to show the desired behaviour and output of your program for a stage 2 test:
prompt$ ./myTrain
Enter the number of stations: 5
Parramatta
Burwood
Ashfield
Central
Chatswood
Enter the number of trains: 2
Enter the number of stops: 4
0935
Parramatta
0945
Burwood
1002
Central
1030
Chatswood
Enter the number of stops: 3
0940
Parramatta
0950
Ashfield
1000
Central
From: Parramatta
To: Chatswood
Arrive by: 1030
0940 Parramatta
0950 Ashfield
1000 Central
Change at Central
1002 Central
1030 Chatswood
From: Parramatta
To: Central
Arrive by: 0959
No connection found.
From: done
Thank you for using myTrain.
Stage 3 (2 marks)
For stage 2, you should extend your program for stage 2 such that:
If there are two or more connections with the same latest departure time, choose the
one with the earliest arrival time.
Here is an example to show the desired behaviour and output of your program for a stage 3 test:
prompt$ ./myTrain
Enter the number of stations: 3
Central
Parramatta
Chatswood
Enter the number of trains: 2
Enter the number of stops: 3
0935
Parramatta
1002
Central
1030
Chatswood
Enter the number of stops: 2
1010
Central
1025
Chatswood
From: Parramatta
To: Chatswood
Arrive by: 1030
0935 Parramatta
1002 Central
Change at Central
1010 Central
1025 Chatswood
From: done
Thank you for using myTrain.
Complexity Analysis (1 mark)
Your program should include a time complexity analysis for the worst-case asymptotic running
time of your program, in Big-Oh notation, depending on the size of the input:
1. the number of stations, n
2. the number of trains, m
3. the maximum number k of stops on a train line.
Hints
If you find any of the following ADTs from the lectures useful, then you can, and indeed are
encouraged to, use them with your program:
• linked list ADT : list.h, list.c
• stack ADT : stack.h, stack.c
• queue ADT : queue.h, queue.c
• graph ADT : Graph.h, Graph.c
• weighted graph ADT : WGraph.h, WGraph.c
You are free to modify any of the five ADTs for the purpose of the assignment (but without
changing the file names). If your program is using one or more of these ADTs, you should submit
both the header and implementation file, even if you have not changed them.
Your main program file myTrain.c should start with a comment: /* … */ that contains the time
complexity of your program in Big-Oh notation, together with a short explanation.
Testing
We have created a script that can automatically test your program. To run this test you can
execute the dryrun program that corresponds to this assignment. It expects to find, in the current
directory, the program myTrain.c and any of the admissible ADTs
(Graph,WGraph,stack,queue,list) that your program is using, even if you use them
unchanged. You can use dryrun as follows:
prompt$ 9024 dryrun myTrain
Please note: Passing dryrun does not guarantee that your program is correct. You should
thoroughly test your program with your own test cases.
Submit
For this project you will need to submit a file named myTrain.c and, optionally, any of the ADTs
named Graph,WGraph,stack,queue,list that your program is using, even if you have not
changed them. You can either submit through WebCMS3 or use a command line. For example, if
your program uses the Graph ADT and the queue ADT, then you should submit:
prompt$ give cs9024 assn myTrain.c Graph.h Graph.c queue.h queue.c
Do not forget to add the time complexity to your main source code file myTrain.c.
You can submit as many times as you like — later submissions will overwrite earlier ones. You can
check that your submission has been received on WebCMS3 or by using the following command:
prompt$ 9024 classrun -check assn
Marking
This project will be marked on functionality in the first instance, so it is very important that the
output of your program be exactly correct as shown in the examples above. Submissions which
score very low on the automarking will be looked at by a human and may receive a few marks,
provided the code is well-structured and commented.
Programs that generate compilation errors will receive a very low mark, no matter what other
virtues they may have. In general, a program that attempts a substantial part of the job and does
that part correctly will receive more marks than one attempting to do the entire job but with many
errors.
Style considerations include:
• Readability
• Structured programming
• Good commenting
Plagiarism
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism
detection software will be used to compare all submissions pairwise (including submissions for
similar projects in previous years, if applicable) and serious penalties will be applied, particularly in
the case of repeat offences.
• Do not copy ideas or code from others
• Do not use a publicly accessible repository or allow anyone to see your code, not
even after the deadline
Please refer to the on-line sources to help you understand what plagiarism is and how it is dealt
with at UNSW:
• Plagiarism and Academic Integrity
• UNSW Plagiarism Policy Statement
• UNSW Plagiarism Procedure
Help
See FAQ for some additional hints.
Finally …
Have fun! Michael  

51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468