Lab Assignment #3, CSE 1320-001 Fall 2006
Due Date: See section website for due date
(see instructions on website for how to turn this in)
Topic objectives: Linked lists
Macros
Compilation of multiple files
File input and output
We are continuing to implement our small travel planning assistance system (TPAS) -Travelicita or Orbitty (or whatever name you might prefer) In this lab we will modify the data structures from the previous labs and add more information, we will continue to search, we will do more sophisticated updates and we will still change costs based on how far in advance a ticket is being reserved.
The tasks for this lab, Lab #3, are:
¬ Introduce the system to a new user.
¬ Modify the existing struct type to add additional flight data about any one airline flight and to be able to build a linked list. (This will be all the data from the previous labs as well as additional info)
¬ Dynamically create and populate the linked list with data from an input file.
¬ Create and display a menu of the following choices for the user.
1) Using the data in the list, search for flights by a variety of criteria
2) Calculate costs based on reservation date vs. flight date and one-way vs. round-trip
3) Sort the structs in the linked list
4) Update the data in the linked list – this will take the user to a submenu for doing updates
5) End the program
¬ Output the program results to the screen and to an output file using a macro
Each of these tasks is described in more detail below. There are also a few simplifying assumptions for Lab #3. Many of these simplifications will be eliminated in later labs.
Simplifying assumptions for Lab #3 (same as Lab #2):
a) All flights have a base cost for a one-way ticket and a base cost for a round-trip ticket and then the actual one-way or round-trip cost is calculated with a recursive function based on how far in advance the ticket is reserved.
Task Descriptions:
¬ Introduce the system to a new user.
For this task your system must provide an introduction/welcome screen to the user. The screen should briefly describe what the system will do. You may have the welcome screen stay up for a fixed period of time or you may let the user press a key to continue on with the program. Make sure you tell the user what to do if you want them to press a key. Do NOT have the user enter a planning date.
¬ Modify the struct type to record additional flight data and to be able to create a linked list
For Lab #3 all the data for one flight must be stored in a single struct. You must use the struct type from Lab #2 with modifications to hold this data. The struct data type should be placed above the function prototypes in your code. All variables of this struct type must be declared inside of the functions of the program. The struct must hold the following data in the following form. Note that some elements will now be stored differently than they were previously.
o flight airline – a string that holds the name of the airline. Your string can be stored in a fixed size character array of at least 20 characters OR you may use a character pointer and dynamically allocate memory for the string. Make sure you always store a valid string in the 20 char array even if the original string read from the file is longer. The airline name will always be one word typed without spaces in the file. Functions that use this string should declare a char * variable to manipulate the string with.
o flight number – an integer that gives a specific number for a flight. Together a flight airline and a flight number will designate a particular flight.
o flight departure time – an integer. flight departure time is the departure time for the flight given by the associated airline and flight number. The departure time may be stored as a military time (a 24 hour clock instead of 12 hours AM and 12 hours PM) Ex: 10:00am would be 1000 military time while 10:15pm would be 2215 military time. Time can be stored as part of another struct if desired.
o flight arrival time – an integer with time stored as 12 hour am/pm time or as hours and minutes or as military time. Can be part of another struct if desired.
o flight number of stops – a short int. A direct flight has 0 stops.
o flight layovers – a struct containing the 3 letter airport code of the layover city, a flag representing whether the traveler is physically changing planes or not, a length of time representing how long the layover will be given as a four digit number of hours and minutes hhmm, and a pointer to another flight layover struct. If the original flight has 0 number of stops all the data in this layover struct will be 0s. If the original flight has 1 or more stops there will be a linked list of one or more layover structs, one for each stop.
o flight lowest coach seat – a float or double giving the lowest full-fare round-trip price for any coach seat on the flight.
o flight lowest Business seat – a float or double giving the lowest full-fare round-trip price for any Business class seat on the flight.
o flight lowest First class seat – a float or double giving the lowest full-fare round-trip price for any First class seat on the flight.
o flight date day – an int. Day of the month. Day must be valid for associated month (i.e. the flight canÕt occur on February 31st.) Can be part of another struct if desired.
o flight date month – an int. Numeric value for month with 1 = January, 2 = Feb. through 12 = Dec. 1 – 12 are the only valid values. Can be part of another struct if desired.
o flight date year – an int of four digits (2006 not 06). Numeric value for year. Can be part of another struct if desired.
o flight departure city – a three character string representing the international designation for the desired airport (ex. DFW is Dallas Fort Worth, MAA is the Chennai, India airport)
o flight arrival city – a three character string representing the international designation for the desired airport
o flight seat preference – a single character representing aisle (a), window (w), middle (m), or none (n). Any other character is treated as none.
o flight meal preference– a single character representing vegetarian (v), low-fat (f), low-salt (s), vegan (g), kosher (k), special (p), or regular (r). Any other character is treated as regular.
o flight passenger – a string which will contain the passengers name once a flight is selected.
o flight seat level – an enumerated type of either COACH, BUSINESS, or FIRST – Note that this data will be added to the struct after the user selects a flight.
o flight seat amenities – a union containing three possible values:
if flight seat level is COACH then the union contains a bit field representing preference for special headphones(2), regular headphones (1) or none (0)
if flight seat level is BUSINESS then the union contains a float representing the dollar amount paid to upgrade this seat from coach if that was done or a zero if the seat was purchased directly as business class
if flight seat level is FIRST then the union contains a char representing preference for alcoholic (A) or non-alcoholic (N) beverages.
o flight link – a flight structure pointer to another flight. Should be initialized to NULL.
¬ Dynamically create and populate the linked list with data from a file.
For Lab #3, the flight data will all be stored in one linked list of structs of data as are described above. Declare a set of pointers to navigate through this linked list. Use a pointer to dynamically allocate each new struct for the list as needed.
Given the amount of data to be entered now, the program will read the input from a file called Òlab3input.datÓ. This file will be given to you on the website for you to use for testing. It will be a plain text file.
Each line of the file will have the following data items in the following order each separated by a single space. This file will NOT have a count on the first line Note that these data items correspond exactly in order and in type to the list of data above and that there are some differences from the previous lab. Especially note that some lines will have more data than others based on number of stops.
For data on a flight that has no stops the order of info on the input line is:
airline num deptime arrtime stops lowcoach lowbusi lowfirst day month year depcity arrcity seat meal
For data on a flight that has one [or more] stops the order of info on the input line is:
airline num deptime arrtime stops airport changeflag hhmm [aiport changeflag hhmm] lowcoach lowbusi lowfirst day month year depcity arrcity seat meal
Note that the square brackets are indicating additional information that will be given for each stop. If there is one stop than only one set of stop info will be in the input data. If there are two stops then there will be two sets of data, three stops, three sets of data and so on. There will NOT be any square bracket symbols in the input data. You program must determine whether to read this data and how much to read by the number of stops given.
[CT1]
Note that the airline name could be longer than 20 characters. If you use an array, make sure that the 20 character array is not exceeded, read the airline name from the file into a longer temporary character array (maybe 50 characters). Then use the string functions to copy a maximum of 19 characters to the 20 character array and store an end of string marker if needed in the 20 char array to make a string. If you use a char pointer, allocate sufficient space to hold the actual string in the temp array and copy the temp array value to the newly allocated space.
So as an example, an American Airlines flight number 232 from DFW to Nashville, TN (BNA) nonstop on Oct. 22, 2006 departing at 11:50am and arriving at 1:02pm with a lowest coach price of $25, a lowest Business class cost of $150, and a lowest First class price of $325 might be represented as the following line in the input file:
American 232 1150 1302 0 25 150 325 22 10 2006 DFW BNA a v
A second example - an Delta Airlines flight number 112 from DFW to London, England (LON?) with one stop in NYC on Nov. 14, 2006 departing at 1:20am and arriving London at 11:05pm with a lowest coach price of $200, a lowest Business class cost of $625, and a lowest First class price of $1048 might be represented as the following line in the input file:
Delta 112 120 2305 1 NYC 0 302 200 625 1048 14 11 2006 DFW LON w r
Your program must create a file variable and link it to the file Òlab3input.datÓ and open the file for reading. Then the program must read each line of data from the input file into a newly allocated flight struct and must link this struct into a SORTED list of flight structs. As the data is read in the list must be created in sorted order based alphabetically on the 3 letter international airport code for the departure city. For flights with the same departure city sort by airline. Continue reading flights from the input file until you reach the end of the file. You may test against EOF or use the feof function to do this if desired.
Make sure to check for the validity of
the airline name (a valid string has to be stored in the size array you have declared),
the number of stops (>= 0),
the costs (>=0),
the day, month, and year, and
the city airport codes (must be real 3 letter airport codes).
When the program has read in all the flights from the file, print out all the flight data in an easily readable form, ex. use a table with headings, or columns with headings or rows with labels. Print this data to the screen AND output the same data to a file you create called Òlab3output.datÓ. Create a macro that assists you in writing the same data to both the screen and the file for all output.
¬ Create and display a menu of choices for the user.
Once all the data is read into the linked list your program should give the user a menu with the following choices: (use any number scheme you wish). Note there are fewer searches than in earlier labs.
i- Search for and select a one-way flight by lowest cost or by lowest cost in a certain class
ii- Search for and select a round-trip flight by lowest cost or by lowest cost in a certain class
iii- Search for and select a flight by airline – user gives a preferred airline
iv- Sort all flight data
v- Update flight data
vi- Add a flight to the list
vii- Delete a flight from the list
viii-End the program
All of the search options should call search functions that perform linear search on the linked list of data. When the search is complete your program should print the search result(s). In case of ties, print all results. Then let the user select one of the flights and get data from the user to fill in the passenger name and the flight seat amenities for the chosen class of flight. Once the user has entered the required information, show the user the menu again.
Note that the searches must do string comparisons for airport codes and airlines when those are needed. Below are descriptions of each type of search to perform.
Searches by cost - including one-way lowest cost search, one-way lowest cost search by class, round-trip flight by lowest cost, and round-trip flight by lowest cost .
The cost searches must take three kinds of information into account; the dates, the class, and the type of flight (one-way or round-trip). This search uses the current date and the departure date of the flight to determine how much of a discount is applied to the price based on how far in advance the plans are made. The current date is captured using the built in C time functions, time and localtime, which will be discussed in class. This search also must adjust the costs based on whether the type of flight is one-way or round-trip. This search can optionally restrict the search to a certain class of seats (coach, Business, or First) based on a user input.
Before beginning this search, the program should ask the user if they wish to check all seats or only a certain class of seat. If the user wishes to check only one class of seat, the program should give the user a list of choices (coach, Business, First) and then let the user choose the class to search. If the user chooses a specific class, then only those flights are searched. If the user chooses all seats, then all three classes of tickets are searched for every flight. (Maybe the First class is mysteriously cheaper than coach on some flightÉ)
The planning date discount is calculated recursively as follows. For each month in advance that plans are made the cost of the ticket is discounted by 10% from the previous monthÕs price. The number of months is calculated by comparing the planning date month and year to the flight departure date month and year. Twelve months is the maximum amount of months to discount. If plans are made in the same month as the flight then there is no discount.
As an example, a round-trip coach ticket for December 23, 2006 with a full-fare price of $400 would be discounted by 10% is reserved in November giving a price of $400 – ($400 * .10) = $360. An October reservation would get another 10% on top of the November price for a cost of $360 – ($360 * .10) = $324 and so on.
The planning discount applies the same way to each class ticket.
The other cost adjustment is for one-way flights. The given fares are based on a round-trip which is both to and from the destination. If the user wants to fly only one-way the fare is less than the round-trip fare but not half and is different for each class. For coach class, a one-way ticket is 60% of the cost of the round-trip ticket. For Business class, a one-way ticket is 66.6% of the cost of the round-trip ticket. For First class, a one-way ticket is 75% of the cost of the round-trip ticket. This adjustment is applied AFTER any planning discount is applied.
Searches by airline – This search will probably give ties. Print all the values that match the search.
When you print the search results, make sure to print all of the data for the flight(s) matching the search criteria. Also print the search results to Òlab3output.datÓ along with the data entered by the user for the chosen flight (it should show up in the flight struct for the chosen flight.)
The sort option should take the user to a second screen to allow them to sort all the flight information based on various criteria. Note there is one less sort required. The user should be able to sort the flight data based on
o flight departure city – alphabetically
o flight arrival city - alphabetically
o flight date day
o flight airline
After each sort is performed, print all of the flights in the linked list of structs in the new sorted order to the screen and to the output file.
The update option should take the user to a second screen to allow them to update information in the arrays. This screen should ask for an airline flight number from the user and search for that flight. If multiple flights with that number are found, ask the user for the airline name. Once the correct flight is determined save a pointer to the struct containing the flight and give the user a menu of the following options:
o Change flight departure time
o Change flight arrival time
o Change flight number of stops – Note if this is changed the layover data should also be changed
o Change flight lowest cost seat
o Change flight lowest coach seat
o Change flight lowest Business seat
o Change flight lowest First class seat
o Change flight date day
o Change flight date month
o Change flight date year
o Change flight departure city
o Change flight arrival city
o Change flight seat preference
o Change flight meal preference
o Change flight passenger
o Change flight amenities
o Return to main menu
For any change the user wishes to make, do the same error checking as in the original data entry section. After each change is made, print all of the flight info for the updated flight to the screen and to the output file.
The add a flight option should allow the user to input a new flight struct into the linked list at the front of the list. This module will get input from the user for a new flight (just like was done in the earlier lab), store that data in a newly allocated struct and link that struct at the front of the linked list. This will make the linked list be unsorted which is fine. Print the new list to both the screen and the file. (The user can choose to re-sort the list if desired.)
The delete option will allow the user to choose a flight just as if they were going to do an update. Then that flight is deleted from the linked list. Be sure to verify with the user before deleting. Print the linked list after the deletion is done to both the screen and file.
When the user chooses ÒEnd the programÓ from the main menu, print a concluding message and then gracefully end the program.
In addition to the task functionality your program must be contained in multiple program files. Specifically you must have:
at least one header file for any global #define constants, any macros, the type declarations, and the prototype declarations;
a file containing just your main routine;
and one or more files containing the remainder of your functions.
These files must be linked together with #include statements and must only be compiled once no matter what order the files are seen by the compiler (conditional compilation using #ifdef.)
Further your program must have a debug mode that can be turned on to show all debugging output that was used and can be turned off so that no debugging output is displayed. This will use #ifdef DEBUG.
Input data file:
The input file will be created and posted on the class website for you to use. You may use a subset of this file to test with if desired. Do not change the format of the file.
Implementation requirements:
The program should use the following data structures:
A struct type to contain all the data for one airline flight
An enumerated type and a union type for seat class info and amenities
A linked list of structs for recording flight information
The program should use the following control structures:
Function calls to perform tasks
Macro to assist with output
Conditional compilation and debug mode
File input and output
String functions for copying and comparison
A while, do-while, or for loop to read the input data
If, if-else, or nested ifs to error check numbers and values
Nested ifs or switch to implement the menu options and costs
A recursive function to implement planning discounts
Your program must be implemented in a modular fashion. You must have a main routine and at least one function for input, one function to display the menu, at least one function for searching, at least one function for sorting, and at least one function for updating. You may have more functions than this. Each of your functions must specify any parameters it uses for input in its parameter list.
Your program should have meaningful identifiers and useful comments. It should be consistently indented and should use horizontal and vertical whitespace for readability.
The program should have a program header which gives, at least, your name, the number of the lab assignment, your class and section, the assignment date, the due date, and a description of the program. If multiple files are used, each file should contain a similar header. See your instructorÕs website for SPECIFIC instructions about the program header.
Each programmer-defined function, i.e. each function you write, should have a function header similar to those used in the examples in the textbook. This header should include at least the function name, the purpose of the function, and its inputs and outputs.
The program should perform the following actions in the given order:
Declare and initialize the variables
Print a welcome screen for the user that introduces the system
Get the needed input values
Print the appropriate outputs
Let the user enter additional values until the user indicates that they are finished.
Your program must be run with the real data you collect above as described in the input data section. You must demonstrate ALL of the functions of your program in your output script, i.e. do all the different searches and all the different types of updates.
The program output must be recorded in a script file from OMEGA after the program has been compiled using the gcc compiler. If you do not know how to create a script file, it is your responsibility to ask the TA or OIT how to use this function. Some helpful tips are available on the class website.
The program should NOT use:
any topic not covered in class before the lab DUE date unless approved by the instructor
See the grading scale below for other specific implementation requirements.
Grading scale:
Code: (50 %)
Program header, function headers and comments for all functions (4 points)
Modularity (division of the problem into small tasks, each one assigned to its own function and called from main() or from another function when appropriate--do not code the entire program in main!) and correct function structure as required (3 points)
Style (indentation, consistency, meaningful identifiers, lateral separation of code from line comments, etc.) (3 points)
Correct manipulation of the linked list and structs (12 points)
Correct use of required control structures (3 points)
Correct use of conditional compilation (4 points)
Correct use of debug mode (5 points)
Correct use of a macro (2 points)
Correct use of input file as given on website (6 points)
Proper implementation of input error checking (8 points)
Output: (50%)
User clearly understands what is being requested for input (2 points)
Correct implementation of menus (3 points)
Search (find) tasks perform correctly on linked lists as required (5 points)
Recursive cost function works correctly (2 points)
Sorting tasks perform correctly on linked lists (9 points)
Updates, additions and deletions to linked lists performed correctly (9 points)
Data is correctly printed to screen and to output file. (6 points)
Output gives clear information to explain the values to the user (4 points)
Output contains examples of all program functions (10 points)
Deductions:
Use of global variables will result in an overall grade of 0 (zero)
Use of the exit command will result in an overall grade of 0 (zero)
Use of goto, continue or break (outside a switch) will result in 50 (fifty) point deduction per use
Late submission of softcopy to appropriate TA will result in an overall grade of 0 (zero) without prior instructor approval
Use of C language elements not yet discussed in class by the lab due date will result in potential deduction of points – discuss with instructor before using.