Lab Assignment

Lab #5 Assignment - SIMPLIFIED Look for locations with ** to find revisions from first version

CSE 1320-002

Spring 2011

Due Date: Lab #5 is due absolutely no later than 8:00pm Thursday, May 12th

Extra Credit for early submission as follows:

Turned in before 11:59pm Wednesday, May 11th = 16 extra points

Turned in before 11:59pm Tuesday, May 10th = 24 extra points

Turned in before 11:59pm Monday, May 9th = 32 extra points

(see instructions on website for how to turn this in - “lab submission info”)

Grade value: 10% out of 100% for all grades

Objective: The goal for this lab is to provide an opportunity for practice of C program development and the C programming topics covered in Foster and Foster as covered in class. It is assumed that the student is familiar with and can use all the concepts cover in class and in the related chapters. This assignment is designed to practice those concepts by creating a C program.

Every lab assignment allows students to practice program development, debugging, and testing. All of these skills are crucial to success in Dr. T’s class. The format of this assignment is similar to the assignments that will be required for the rest of the semester so a student who is unsure of their skills can use this assignment to refresh them and to ask the instructor or TA about any concepts they are unsure of.

Topics:

Doubly linked lists

Command line inputs

Bit fields

Enums and Unions

Static variables

Recursion

Multiple files

Function pointers

Searching and Sorting

Program design

Modular programming structure

Error checking

Programming style

Compiling code,

Executing code,

Debugging and testing.

Plan: Dr. T gives an overall problem that students work on all semester. Each lab assignment implements specific concepts. Succeeding assignments will modify and extend previous assignments.

Overview: This semester our theme will be working on a support system for making travel plans. You are going to put together a small database of information to help make travel arrangements. You are going to get information from the user and store that information in a certain way. We’ll call this the data-entry phase of the program. Once all the input data is entered, your program will allow another user to perform various tasks on the data by choosing tasks from a menu. We’ll call this the menu-driven phase of the program. The user can continue to choose tasks from the menu as long as desired and one of the menu choices must be to end the program. The program ends correctly when the user chooses that option.

You are also required to design your program in advance before you begin writing code. You will document your design and turn in the design document at least a week before the lab assignment is due. The goal of the design document is to assist you in developing the actual program.

This assignment has an overview section, a task description section, an implementation requirements section, a grading scale, and a deductions section. If there is additional info needed it will be in a miscellaneous section at the end of this lab assignment. Read ALL of the assignment before you start trying to develop the program.

Be sure to check the DEDUCTIONS section at the end of this assignment to avoid penalties. You may NOT use global variables, the exit command, goto, break (except in a switch), or continue.

Assumptions for the lab #5:

1) A maximum of 20 legs per trip are allowed. Use constants to define the max value. You should use an array to store leg data in the trip struct.

2) Strings will have a maximum length less than 512 characters but will contain blanks and punctuation.

3) There is no maximum number of trips for Lab #5.

Problem: The data in your database will be travel destinations, information about getting to these locations, and other data needed to plan or manage a trip. As part of this assignment you will have to find real data about these destinations to use as test data for your program.

When the user runs your program, they must first enter data either from the keyboard or from a file. The data they are entering will be the travel information that you have researched to use as your test data. The data entry tasks are

• Have the user call the program.

• Introduce the trip database to a new user.

• Create a struct type to hold the data for a trip, including two members that are pointers to this struct type.

• Create a doubly linked list of structs as the user enters the trip data.

After getting all the input data for the destinations from the user (and storing it in a doubly linked list of structs), you will allow the user to do the following in the menu-driven phase:

1) Using the data in the arrays,

A) Search for destination by

** i. Type of travel **NOT REQUIRED: Implement for extra credit

** ii. Continent or area **NOT REQUIRED: Implement for extra credit

iii. Date of trip

** iv. Destination name **NOT REQUIRED: Implement for extra credit

B) Calculate

i. Cost for purchase of tickets for travel

** ii. Length of trip without the travel time **NOT REQUIRED: Implement for extra credit

** iii. Cash value of tickets if not used over **NOT REQUIRED: remove time

C) List all the destinations that meet certain criteria

i. Less than given cost

** ii. Less than a given travel time **NOT REQUIRED: Implement for extra credit

** iii. In the same continental area **NOT REQUIRED: Implement for extra credit

** iv. In the same country **NOT REQUIRED: Implement for extra credit

D) Sort the data by

i. Destination code

ii. Travel date

iii. Name

iv. Number of travelers

v. Area letter code

** 2) Update the data in the arrays–this will take the user to a submenu for doing updates **NOT REQUIRED: Implement for extra credit

3) Add new trips - this will take the user to a submenu to add a new event to the list

4) Delete trips

5) Print all trips forward or backward

6) End the program

Data Entry Phase

Data Description: For lab #5, you will be storing the input data in a doubly linked list of structs for trips. The trip struct will contain a single dimensional array of structs for legs. You will dynamically allocate a new struct for each trip then link them into a list to hold all the trips.

The data elements and descriptions are given below. Following this first list, the data elements are described by type.

1) Destination code - a five digit integer where the digits represent a city or location using the guidelines given at the end of the assignment. You will have to validate the 10000s place and 1000s place of any code entered by the user. For the first destination, the destination code would be read in and error checked. If the value is valid, i.e. it passes error checking, then it is stored in the destination code member of the struct for this trip.

2) Destination name - a string less than 40 characters long that gives the destination name. In lab #5 we are using strings for the name which may have multiple word, i.e. San Antonio is a valid name for this lab.

3) Area letter code - a letter representing the kind of destination. Choices are:

S Small city - population under 50,000

M Medium city - population between 50,000 and 500,000

L Large city - pop. over 500,000

N Natural formation like a mountain, a lake, a cave, a geyser, a fjord, a canyon, etc.

P Designated park or reserve such as a wildlife refuge, a national park, a bioreserve, or a protected marine area

K Man made landmark like the Great Wall of China, the Taj Mahal, or Stonehenge

R State or province or region of a country

C Whole country

U Multiple countries like traveling through Europe

W Ocean voyage

O Any other type of destination - such as visiting the sites of the seven wonders of the world

4) Travel start date as day, month, and year – three separate numbers

5) Travel end date as day, month, and year – three separate numbers

6) Number of legs of travel to reach destination (max of ten legs)

6a) Travel type for a leg (one code letter per leg) Codes are:

A Airplane

R Train and rail travel

B Bus

C Car

F Ferry

S Cruise ship

M Motorcycle

Y Bicycle

T Boat other than a ferry or cruise ship

D Dirigible

O Other

6b) Travel length for a leg (one length in hours and minutes per leg including layover time) - save as a floating point value HH:MM

6c) Cost per leg (one amount per leg) in dollars and cents - save as a floating point value

7) Total time to reach destination (from first departure to final arrival; i.e. the sum of all the travel lengths) in days, hours, and minutes

8) Length of trip from start to end minus travel time in days

9) An enumerated type value for the stage of trip activity as described below. The values will be:

PREP : while doing trip planning,

TRAV : while actually traveling, and

MEM : after the trip is completed

10) A union type variable for recording data for each stage of the trip as described below. The union values are:

10a) The number of days left until the start of the trip used in the PREP stage,

10b) The total expenses for incidentals incurred while traveling used in the TRAV stage, and

10c) The title used to label the trip records, just as photo albums, used in the MEM stage

11) Number of adults traveling (age 18 or older)

12) Number of children ages 2 through 17

13) Number of infants less than age 2

14) Destination country – a string with the name of the country of destination

15) Two pointers to other trip struct types. These variables will “link” in each struct forward and backward.

The format for each piece of data is listed below.

You will create a struct data type to hold a trip. The struct type will hold all the data items for one trip including an array for the data in the legs. The leg data will be another struct type and you will have an array of size 10 of the struct leg type as one member of the struct trip type. The enumerated type and the union type values will be separate types with variables of those types used in the trip struct.

In Lab #5 you will use pointers to keep track of the structs. Structs will be dynamically allocated as needed for each trip that is read in and each new trip will be added in the correct location to the current sorted linked list of trips. This is no maximum number of trips for Lab #5.

Declare the struct types globally and then declare the pointers to the structs inside main. You will create a sorted singly linked list of elements of type struct trip to store any number of trips. The members of the struct trip type are below.

As an example, let's say the user is going to enter data for two trips. The first trip will be to Yellowstone_National_Park (code 13500) and the second trip will be traveling around Germany (45999). For each trip you will be allocating memory for a new struct, asking the user for all the pieces of data listed above and storing this new data into the linked list of structs. The different trips, in this case the first trip and second trip, will be stored in the correct order in the linked list. Each member of the struct will indicate a different piece of data about the trip.

Make sure to declare all your constants before you try to use them. In the information below, I am using the current pointer to be the pointer to the newly allocated struct where the data is being stored.

Destination code - an integer where the digits represent a city or location using the guidelines given at the end of the assignment. You will have to validate the 10000s place and 1000s place of any code entered by the user. For the first destination, the destination code would be read in and error checked. If the value is valid, i.e. it passes error checking, then it is stored in the current dynamically allocated struct in the current->destcode member for this trip.

Destination name - a string less than 40 characters long that gives the destination name. The string will be read in with the getline command into a temporary string. The length of the string should be checked using the strlen command. If the string is less that 40 chars in length then it should be copied to the current->destname member of the struct.

Area letter code - a single character representing the kind of destination. It must match one of the valid series/event codes. If it is valid, it should be stored in the current->area member of the struct.

Travel start day is an integer value. It should be error checked and then a valid day value stored at the current-> trsday member of the struct.

Travel start month is an integer value. It should be error checked and then a valid month value stored in the member trsmo member of the struct.

Travel start year is an integer value greater than 2000 and less than 2050. It should be error checked and then a valid year value stored at the trsyr member of the struct.

Travel end day is an integer value. It should be error checked and then a valid day value stored at current-> treday .

Travel end month is an integer value. It should be error checked and then a valid month value stored in the member current->tremo.

Travel end year is an integer value greater than 2000 and less than 2050. It should be error checked and then a valid year value stored at current->treyr

Number of legs is an integer value. It should be error checked and then a valid day value stored at current->numlegs

There are three pieces data per leg and they should be stored in a struct leg array, e.g. legs

Travel type is one letter per leg per trip. It should be error checked and then a valid type code stored at current->.legs[legnum].travtype

Travel length for a leg is a floating point value in the form HH.MM where HH is the number of hours less than 24 and MM is the minute value. It should be error checked and then a valid length stored at current->legs[legnum].len

Cost per leg is a floating point value. It must represent valid dollars and cents. The cost of a leg can be free. A valid ticket price should be stored in the float array at current->legs[legnum].cost

Total travel days is an integer value. It should be calculated from the sum of the lengths of travel time for all legs and then a valid number of days stored at current->totday. This is only calculating how long it takes to get from the starting point to the destination (one way), not the length of the entire trip. This value should be calculated automatically by your program after the data for all the legs is entered.

Total travel hours is an integer value. Once the total number of days is determined, then the remaining hours should be calculated and a valid number of hours stored at current->tothr. This value should be calculated automatically by your program after the data for all the legs is entered.

Total travel minutes is an integer value. After the total number of days and hours is determined, then the remaining minutes should be calculated and a valid number of minutes stored at current->totmin. This value should be calculated automatically by your program after the data for all the legs is entered.

Trip length is an integer value. It will be calculated, when requested by the user, from the start day to the end day of the trip minus the number of days of travel. This is the length of the entire trip and should be stored in current->triplen

Stage - a variable declared of an enumerated type enum tripstage with three constant values defined: PREP, TRAV, MEM.

Instage - a variable declared of a union type union intrip with three members. The union type has three members:

Days until - an integer count of the number of days until the trip begins. This should be calculated automatically

using the current date and the start of travel during PREP stage.

Spent so far - a floating point value keeping a running total of expenses during the trip in TRAV stage.

Trip title - a string of less than 100 char to use to label data that is saved after the end of the trip during MEM stage. This string CANNOT have any numeric digits in it, only letters and symbols. This will allow string processing.

Adult is a bit field value with a maximum size of 511. It should be error checked and then a valid number of adults stored at current->adult.

Child is a bit field value with a maximum size of 127. It should be error checked and then a valid number stored at current->child .

Infant is a bit field value with a maximum size of 63. It should be error checked and then a valid number stored at current->infant.

Destination country - a string less than 40 characters long that gives the destination country. The string will be read in with the getline command into a temporary string. The length of the string should be checked using the strlen command. If the string is less that 40 chars in length then it should be copied to current->country in the array.

Next trip - a pointer to the trip struct type. This is NOT read in. It is initialized to NULL.

Previous trip - a pointer to the trip struct type. This is NOT read in. It is initialized to NULL.

Input Implementation: For Lab #5 the user must enter at least 4 destinations when doing keyboard input and at least 12 destinations when doing file input. There is no maximum number of trips. If the user is entering data from the keyboard, either with the individual data item method or the line of data method, then the program must prompt the user to find out if the user wishes to enter another trip. The user may enter data until they indicate that they have finished. There is no counted loop.

The struct data type for trips should be defined globally as mentioned previously. The actual trip variables should be dynamically allocated as needed using pointers and linked into a list that is sorted in order by the destination code. The lab must allow the user to enter any number of trips into the database.

For Lab #5, you must implement TWO of the following three methods of input and you are REQUIRED to implement file input. In addition to file input you may implement either the individual data method or the line of data method or both. The three forms of the input are described below. Your program must give them at least two choices of methods: File input (REQUIRED choice), Individual data method, or line of data input method.

For Lab #5, the user must pass in a command line value indicating which type of data entry they want to use. The command line input should be one of the following three strings: "indiv", "line", or "file". If the user enters an input method that you did not implement, ex. you implemented line input but the user enters "indiv", then ask the user how they want to enter data. Otherwise, take the command line input and use that information to go directly to the welcome message and then data input.

Individual data method:

The user will enter data for one trip and then the program must ask the user if they wish to enter another trip. The user will continue to enter trips until they tell the program that the data is complete.

After malloc'ing space to the pointer current you would

a. Ask the user for the destination code (don’t forget explain codes for them.) Read in their number, make sure it is a valid code and then store it in current->destcode As an example of an explanation, you might tell the user "Please enter a destination code. Codes should be five digits with the first digit representing the continent, the second digit indicating what kind of destination it is and the last three digits just being a unique code…" and then you can list the continents and kinds of destinations for them to use. See the Miscellaneous section at the bottom for the destination code info.

b. Ask the user for the area letter code and give them the choices. Check to make sure it is a valid type. Store this valid character in current->area .

c. Ask the user for the month, day, and year for the start of the travel. Make sure it is a valid date, i.e. it is a real date and it is in the future, and then store it in current->trsmo, current->trsday,and current->trsyr.

d. Ask the user for the month, day, and year for the end of the travel. Make sure it is a valid date, i.e. it is a real date and it is in the future and after the start date, and then store it in current.

e. Ask the user how many legs of travel there are from the user's starting location to the desired destination, i.e. two plane legs and a ferry ride would be 3 legs. Store the number of legs in the array at the correct location, current->numleg

f. For each leg,

1. Ask the user for the travel type code letter and give them the choices. Check that they entered a valid code letter and then store it at current->leg[legnum].travtype

2. Ask the user the length of travel time in hours and minutes for that leg entered as a floating point value representing HH.MM . Check that the value is positive and that MM is less than 60. (HH can be any value because it might represent multiple days like on a ship.) Store the time in the floating point array at current->leg[legnum].len.

3. Ask the user for the cost of that leg of travel entered as a floating point value representing US dollars and cents (ex. 450.99). Check that the cost is valid and store in the floating point array at current->leg[legnum].cost.

g. Ask the user which stage the trip is in and have them enter a value to correspond to the correct stage. Use that information to store the correct enumerated value into current->stage.

h. Based on the enumerated value, ask the user for the correct union member value and store in the correct member of the instage union variable. Note that NO value is needed in the PREP stage because this value should be calculated by the program.

i. Ask the user for the number of adults, ages 18 and older, who will be traveling on this trip. Check for validity and save this value in the array current->adult bit field.

j. Ask the user for the number of children, ages 2 through 17, who will be traveling on this trip. Check for validity and save this value in current.

k. Ask the user for the number of infants, under age 2, who will be traveling on this trip. Check for validity and save this value in current.

l. Ask the user for the string name of the destination followed by a comma and one blank and then the name of the destination country. Read all of it into a temporary string. Break the temp string into two tokens at the comma and check the length of the two shorter strings. If each is OK, store them into current.

m. Initialize the next and previous pointers to NULL.

Line of data input method:

Your program may ask the user to enter all the information for one trip on the same line. This data would be an integer for destination code, ints for day, month, and year of start and end along with counts of legs and travelers, chars for area code and travel code, floats for leg cost and length, and a string for the name of the destination and its country. You must tell the user exactly how to enter the line of data.

The data for a single trip will be entered by the user as values on one line as follows {there must be one space only between the values and note the comma between the strings}. Here's an example:

> 11006 L 7 29 2011 8 7 2011 1 C 4.10 57.34 PREP 2 0 0 San Antonio, United States

which represents a trip to San Antonio (code 11006, name San Antonio in country United States) from July 29. 2011 to August 7, 2011 with one leg by car for 4 hours and 10 minutes with a cost of $57.34. Two adults are traveling with no children or infants.

And a second example: [NOTE: this example is longer because the trip has two legs instead of one]

> 13953 P 12 26 2011 1 5 2012 2 A 3.30 249.00 A 2.0 148.00 MEM Cuba Christmas 3 0 2 Sierra Del Rosario, Cuba

which represents a trip to Cuba's Sierra Del Rosario (code 13953, name Sierra Del Rosario in Cuba) from Dec. 26. 2011 to Jan. 5, 2012 with two legs of the trip. The first leg is by airplane for 3 hours and 30 minutes with a cost of $249.00. The second leg is also by plane with a time of 2 hours and a cost of $148. Three adults and two infants are traveling.

Your program will read the first number and store it in the struct array at the correct location, then read and store the character into the corresponding location in the array, then read and store the third number (month) into the array, and so on. Your program should read the numbers, chars, and the string with a minimum number of input commands. When the program reaches the enumerated value, the remainder of the line should be read as a string with getline. The string should then be processed into the word representing the enumerated type, the value for the union, the three bit field values (using atoi), then the destination name. Note that the value for the union may be either a floating point value for expenses or a string without digits for the title. If the title string is to be read, use a string function to read until you find a digit in order to get the title part of the string. Make sure you do not destroy the digit when using the string functions. The digits will be the values of adults, children and infants. These values will need to be separated from the string and then converted to numeric values and saved.

Your program should read in as many lines of input for destinations as the user wishes to enter (there is no maximum).

File input method:

Your program may ask the user to enter all the information for all the trips from a file. The file would have one trip per line. The data for one trip in the file would be exactly the same data you would use for line of data input.

You must create a data file that contains at least 12 lines of trip data and you must read the data from tje file. To do this requires creating file variables, opening the file and linking it to the file variable, and then reading the data from the file variable using fscanf and getline in the same way that a line of data would be read from the screen. If the user chooses file input, then your program must first get the name of the input data file to use. This can be done in two ways:

1) You may tell the user to name the file a specified name, i.e. "You input data file must be named lab4data.txt in order for the program to use it. The file must be stored in the same directory as the program. Press any key when your file is ready to be read. " You would then accept a key press from the user, set up the file pointer for the file, and then begin reading from the file one line at a time. As one line of data is read, it should be error checked before the next line is read. You would loop until you reach the end of the file.

2) If you wish to give the user more flexibility, you can let the user type in a string with the name of the file in it and then use the string as the file name to set up the file pointer. You would read in the name string using getline in the same way you read in the destination name.

For either approach your program needs a FILE * pointer which is connected to the file with fopen. Ex: Using the 2^nd method above:

int filenm = 100; // not needed for 1^st method

char *filename; // not needed for 1^st method

FILE *infile;

printf("Please enter the complete name of your data file: "); // use different message for 1^st method above

getline(&filename, &filenm, stdin); // not needed for 1^st method

if (filename != NULL) // not needed for 1^st method

infile = fopen(filename, "r"); // infile = fopen("lab4data.txt","r"); for 1^st method

Linking structs:

For this lab the user may enter any number of trips. The user should NOT give a count of how many trips they are entering. [Note for development: start with a small number of trips then increase when program is working well ].

The user will enter data for one trip struct, error check the data, and then that struct will be added to the linked list. After that struct is added to the list, then the user can enter data for another struct. This process is the same even if the data is read from a file. The steps for entering the data and building the linked list are:

Determine if there is more trip data to be entered and if so, your program should

1) allocate a new struct,

2) read and store input into that struct in one of the three following ways:

Individual data method,

line of data input method, or

file of lines input method

3) link the struct into the trip list using both the previous and next links in to order sorted by destination code from smallest to largest.

Loop back to the top to get the next trip

The list must be BUILT in sorted order by destination code. If you build an unsorted list and then sort it into destination code order this will deduct points.

Input verification:

When the user has entered as many trips as desired or all trips are read from the file, then print out all the input trip data in an easily readable form, ex. use a table with headings, or columns with headings or rows with labels. It is strongly suggested that this printing be written as a separate function that can be called at any time in the program to print the current contents of the array. It is also suggested that a small function be written which will print the name of a destination given the destination code as input. The function could have a switch or a bunch of if statements in it.

Menu-driven Phase

Task Description:

Once all the data is read into the arrays your program should give the user a main menu with the following choices: (use any number scheme you wish)

** A) Search for destination by type of travel **NOT REQUIRED: You may implement with doubly linked list for extra credit

B) Search for destination by date of trip

** C) Search for destination by area or continent **NOT REQUIRED: You may implement with doubly linked list for extra credit

** D) Search for destination by destination name **NOT REQUIRED: You may implement with doubly linked list for extra credit

E) Calculate cost for purchase of tickets for travel

** F) Calculate length of the trip without travel time **NOT REQUIRED: You may implement with doubly linked list for extra credit

** G) Find all the destinations in the same continent **NOT REQUIRED: You may implement with doubly linked list for extra credit

** H) Find all the trips that are shorter than a given travel time (from start to destination) **NOT REQUIRED: Implement for extra credit

I) Find all the trips that cost less than a given amount

** J) Find all the destinations in the same country **NOT REQUIRED: You may implement with doubly linked list for extra credit

K) Sort the data by destination code

L) Sort the data by trip start date

M) Sort the data by destination name

N) Sort by total number of travelers

O) Sort by area letter code

** P) Update the data in the arrays–this will take the user to a submenu for doing updates **NOT REQUIRED: You may implement with doubly linked list for extra credit

Q) Add new trips - this will take the user to a submenu to add a new trip to the list

R) Delete trips

S) Print trips forward (beginning to end of list)

T) Print trips backwards (end to beginning)

U) End the program

The search functions should let the user enter a travel type or date or continent or name and then look through the list to find the first destination that matches that code/date/name. Print a sentence stating that matching code/date/name was or was not found and if found, also print the code and the name of the destination. For the Lab #5 your program should return the LAST destination that is found as a match.

The calculate-cost function will ask the user for a particular destination code from those in the database (print the table of trips) and will then calculate and print the total cost of the tickets for all the travelers listed for that trip. You may save the trip costs in a floating point array of costs if desired. The cost of any trip is calculated as follows:

The sum of the cost of all the legs is the half-trip cost.

The total trip cost for one adult is two times the half-trip cost.

The total trip cost for one child is equal to the half-trip cost.

The total cost for one infant is half of the half-trip cost.

The total cost of a trip for all travelers is the number of adults times the adult cost plus number of children times the child trip cost plus number of infants times the infant cost.

**NOT REQUIRED: Implement for extra credit ** The calculate-length-of-trip function will find the total number of days of the trip excluding the travel time. The calculation is to take the start day of the trip and count the number of days until the end of the trip (remember to include the start and end day in the count) then subtract two times the number of days of travel time. For purposes of this calculation, you can ignore the total hours and minutes of travel time.

>**NOT REQUIRED: Implement for extra credit ** The find-all-on-continent function should ask the user to choose the desired continent from a list then go through every destination and print the complete information for all destinations that are on that continent. You will have to use the destination code to determine this.

>**NOT REQUIRED: Implement for extra credit ** The find-all-shorter-trips function should ask the user for a number of days, hours and minutes and then go through every destination and print the complete information for all destinations that have a total travel time shorter than the given travel time. This is the time to go from the start to the destination, not the total length of the trip.

If the user chooses the find-all-less-than-cost function, your program should ask the user to enter a trip cost for one adult. Once the user has entered this value then call a recursive function that goes through every destination and prints the complete information for all destinations that have that have a single adult cost equal to or less than that cost.

>**NOT REQUIRED: Implement for extra credit ** The find-all-in-country function should ask the user to enter the desired country then go through every destination and print the complete information for all destinations that are in that country. You will have to use the country name string to determine this.

Sort functions in Lab #5:

For Lab #5 you will only have one bubble sort function. In order to sort by different criteria, i.e. code, date, name, travelers or area code, you will write criteria test functions and pass these functions into the sort function using a function pointer. There should be five of the criteria test functions as follows:

Test-destination-code should test destination codes to allow the program to sort from smallest to largest.

Test-date should test based on the date of the start of the trip from earliest to latest. Make sure you work out the algorithm for comparing two dates before you try to write the comparison tests. You’ll have to use the day, month, and year values to do this.

Test-destination-name should test based on the destination names alphabetically.

Test-travelers should add up all the travelers (adults + children + infants) for a trip and compare that to sort the list from largest group of travelers to smallest.

Test-area-code should test the area letter codes to sort alphabetically.

The sort function should also keep a static variable that increments every time the sort function is called. This value should be printed at the end of each sort with some sort of message like "You have sorted the list X number of times."

>**NOT REQUIRED: Implement for extra credit ** The update option should take the user to a second screen to allow them to update information in the arrays. This screen should print the destinations in the database for them to choose from, ask for a destination code from the user, and search for that destination. Once the correct destination is determined save a pointer to that struct and give the user a menu of the following options:

o Change trip start or end month, day, or year

o Change the number of travelers

o Change the area letter code

o Change the name

o Increase the number of legs

o Add all the data for a new leg

o Change the leg cost

o Change the leg type

o Change the leg length

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 destination info at [index]. [Hint: If you write your data entry section with little functions for each input check then you can reuse them all here.]

Add new trips to the list:

The add trips option should take the user to a second screen to allow them to add information about a new trip into the linked list. The user should be allowed to choose whether to enter the new trip by individual items or by the line of data method (if both of these are implemented) but NOT by file input. The process to add an trip should be just like the process for taking in the trips initially. The list should be sorted by destination code before the new element is added and the new trip should be put into the list in sorted order. After the new trip is added, print the list.

Delete trips from the list

The delete option should take the user to a second screen to allow them to indicate the information to delete in the linked lists. This screen should ask for an destination code from the user and search for that trip. Once the correct trip is determined, the program should verify again with the user that this is the trip they wish to delete. If the user answers yes, the trip should be deleted from the list by changing the pointers of the other list elements and then freeing the space of the deleted trip. After the trip is deleted, print the list.

Print trips

Print trips forward should print starting at the begin element and printing until the end of list is reached.

Print backwards should start with the element farthest from the beginning and print backward to the begin element.

When the user chooses "End the program" from the main menu, print a concluding message and then gracefully end the program.

Implementation Requirements:

WRITE A DESIGN DOCUMENT FIRST. The design must include

a) all the functions you expect to write,

b) brief (one line) descriptions of each function,

c) some indication of which function calls what other functions,

d) a brief description or pseudo code of the main data structure, and

e) an indication of which functions will be in which .c file.

The design document may be written as lines of text or as diagrams (such as a diagram that start with the main function at the top and all others below it) or as some combination of those, but it must include the information listed for a), b), and c) above. Each function should accomplish one main purpose and each function at a lower level should have a more specific purpose than the function that calls it. Be sure to include all the functions that are described in this lab assignment. This design documentation will be turned in for the lab and a design will be required to be turned in for Lab 1 and all later labs. See the website for the DESIGN DOCUMENT due date. It is usually ONE WEEK PRIOR to the lab due date.

A Lab #5 Design Document must be turned in in order for your Lab #5 assignment to be graded.

Multiple .c file implementation:

Your Lab #5 program must be split into at least two physical files, i.e. .c files. The first .c file should use the standard file naming convention and should contain all the struct, enum, and union definitions, all the constants, the function prototypes, and the main routine. The second file should contain some or all of the remaining functions in the program and should be named with an 'a' following the name of the main file. I.e. if the main file is Lab5abc1234.c then the second file would be Lab5abc1234a.c. If there were a third file it would be Lab5abc1234b.c etc. You should NOT use #include to combine these files; you should used gcc with all the file names to compile them together.

The program should use the following data structures:

A user defined struct data type (can use more than one struct type) which contains member elements to hold

all the required information for one trip and two pointers. Make sure you have added and modified the data

types as defined.

Doubly linked list in sorted order

Enum type

Union type

Command line parameters

Single-dimensional struct array for leg data inside the trip struct

Files for data input

Global CONSTANTS for specific and/or maximum values given in this assignment. Constants can be done with

#define or with the const declaration. Examples:

#define EVENTMAX 10

const int EVENTMAX = 10;

The program should use the following control structures:

Function calls to perform tasks

A while or for loop to read the input data

Dynamic memory allocation for structs

If, if-else, nested ifs, or switches to error check and implement the menu options

The program should NOT use:

global variables

exit

break (except in a switch)

continue

any topic not covered in class before the lab DUE date unless approved by the instructor

Programming practices:

Comment your code! Use headers as described below, use line comments and use block comments. Line and block comments should explain the meaning of the code. As an example compare the following examples of code with comments:

Example 1:

/* Find A by multiplying L times W */

A = L * W; // A is the product

Example 2:

/* Find the area of the rectangle by multiplying length times width of the sides */

A = L * W; // A is area, L is length of one side, W is length of perpendicular side attached to L

While Example 1 has comments, the comments do not tell us anything extra about the code. The code itself tell us that A is the product of L*W. In Example 2, the comments are meaningful and explain the goal of the code and the meaning of the variables. Make your comments like Example 2 not Example 1.

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 be implemented as a set of functions with a main routine and at least one function for menu operations, two for getting input, one for printing, and all of the functions listed for the user choices. You may use many more functions than this but you must use at least this many. The purpose of functions is to divide the problem into small tasks, each one assigned to its own function and then to call the functions from main() or from another function when appropriate. Do not code the entire program in main!

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 from the keyboard or file

Print the appropriate outputs

Let the user make additional choices until the user indicates that they are finished.

Output requirements:

The program must be run and the output recorded in a script file from OMEGA using the gcc compiler. No Exceptions! If you do not know how to create a script file, it is your responsibility to ask the TA, look for help on the class website, or ask OIT how to use this function.

You must come up with information to use as test data for at least 12 destinations and trips. You may only have one trip that is a single leg - all other trips must have multiple legs. Please use real data for trips and costs. Feel free to use travel websites to "plan" the trip data for this lab. See the Miscellaneous section below for other useful info.

Testing:

This program must be run with two different sets of test data for the input data. You must create two different data sets and run your program with both of them. I will give you a small amount of sample data at the end of this lab for you to use as a model. You may run your program two times within a single execution or you may execute the program two different times so that you have a total of two different data sets. The sample data sets that you create must meet the guidelines given in the problem definition. Your test runs should demonstrate all the choices that are available in your program.

NOTE ABOUT ERRORS:

Programs turned in for credit MUST compile and run WITHOUT any compilation errors or runtime errors using the gcc compiler on omega. No other compiler may be used for the compilation for credit. No other operating system may be used for the compilation and/or execution for credit.

Compilation errors and warnings occur while the program is being developed and they prevent the program from compiling correctly. Programs compile correctly when running

>gcc myprogram.c // or >gcc Labmy.c Labmya.c Labmyb.c

gives no error or warning messages.

Programs may be turned in for credit when they are partially complete but all completed functions must run without any errors. A program completes without runtime errors if it ends only when the user selects for the program to end and it correctly prints the exit message. Partially complete programs that compile and run correctly for all implemented menu choices will receive partial credit.

Any other type of ending is a runtime error or a "crash". A program has a runtime error if it compiles and runs but then crashes in any situation, i.e. if there is any set of choices the user can make that will make the program crash. It is your responsibility to test all possible choices in your program to make sure that none of them cause a runtime error. The goal of creating input test data and running your program with it should be to test all of the various choices in your program to make sure all of them terminate correctly.

Labs which have errors in them and do not terminate normally will receive an overall grade of 0 (zero)

Grading Scale:

Code: (52%) (up to 5% more extra credit)

Program style:

Program header and function headers for all functions (2 points)

Comments (line comments and block comments) (3 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!) (2 points)

Style (indentation, consistency, meaningful identifiers, lateral separation of code from line comments, etc.) (2 points)

Quality and correctness of code (simplicity, readability, testability, etc.) (3 points)

Correct definition and use of the struct type including all correct data members (4 points)

Correct definition and use of enum and union types and variables (3 points)

Correct definition and use of external struct pointers (1 point)

Correct manipulation of the doubly linked list (6 points)

Correct use or recursion in find-all function (3 points)

Correct use of required control structures (4 points)

Correct development of sort criteria functions and use of function pointer (4 points)

Correct use of multiple files for the C program (3 points)

Correct implementation of files and file variables for input (3 points)

Correct function structure as required (3 points)

Correct use of static variable (2 points)

Proper implementation of data input and input error checking (4 points)

**EXTRA CREDIT: Correct implementation of non-required functions - 1 point per function up to max of 5 points (up to 5 points)

Output: (48%)

User clearly understands what is being requested for input (3 points)

File input works correctly (2 points)

Input data for modified and new data members of struct read correctly (4 pts)

Initial sorted linked list created correctly from input data (3 points)

Sort tasks perform correctly on linked list using function pointer parameter (5 points)

Sort criteria functions work correctly (3 pts)

Sort task count works correctly (1 pt)

Search tasks perform correctly (3 points)

Find-all tasks perform correctly including recursive function (3 points)

Calculate tasks perform correctly (3 points)

Update tasks including leg data perform correctly (2 points)

Add and delete tasks perform correctly with double links (4 points)

Both print tasks perform correctly (3 points)

Input verification shows valid values and list of inputs correctly saved and printed (2 points)

Output gives clear information to explain the values to the user (4 points)

Output contains file data output and keyboard entry output (3 points)

Grading Deductions:

Use of global variables will result in an overall grade of 0 (zero) [-100 deduction]

Use of the exit, break (outside a switch), or continue command will result in an overall grade of 0 (zero) [-100 deduction]

Labs which cannot be compiled or do compile with warnings will receive an overall grade of 0 (zero) [-100 deduction]

Labs which have errors in them and do not terminate normally will receive an overall grade of 0 (zero) [-100 deduction]

** Note: if extra credit functions have errors, they will be treated like any other error and result in a grade of 0

Missing design document will result in an overall grade of 0 (zero) [-100 deduction]

Late submission of softcopy of code and/or script file to appropriate TA will result in an overall grade of 0 (zero) UNLESS

student has obtained prior instructor approval [-100 deduction]

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.

Policy on lab grade review: Students who make arrangements, within 7 days of receiving the lab grade, to talk to the lab grader (usually the TA) AND who actually go talk to the grader within 3 weeks of receiving their grade, will receive the following grade changes:

If the amount of deductions is worth more than the total number of earned points, then after talking to the TA, the student will receive a final score on the lab of 50% of the earned points. Ex: the lab earned 72 points but had a 100 deduction (-100) resulting in a grade of 0. After the talk with the TA, the lab grade will be changed from 0 to 36 (50% of 72).

If the amount of the deductions is not greater than the total score, then after talking to the TA, the student will receive a final score on the lab which is the earned points minus 50% of the original deduction. Ex: Lab scored 72 but had 60 points deduction for a resulting grade of 12. After talk with TA, the grade will be 42 (72 - 50% of 60).

Miscellaneous:

Destination code structure: The code will be a 5-digit number. The leftmost digit (10,000s place) will indicate the continent as follows:

1 North America

2 South America

3 Asia

4 Europe

5 Africa

6 Australia

7 Antarctica

Following the continent value will be a value in the 1000s place that indicates if the destination is a city, a land form of some kind, or other types of locations. The codes for that digit will be:

1 City (any size)

2 Natural formation like a mountain, a lake, a cave, a geyser, a fjord, a canyon, etc.

3 Designated park or reserve such as a wildlife refuge, a national park, a bioreserve, or a protected marine area

4 Man made landmark like the Great Wall of China, the Taj Mahal, or Stonehenge

5 State or province or region (for example if traveling around Saskatchewan)

0 Any other type of destination - such as visiting the sites of the seven wonders of the world

Therefore, a destination code for Washington, DC, USA might be 11100 for North America, city, and then code 100 for DC. Likewise Arlington, TX might be 11001 where Arlington is 001. The Taj Mahal could use a 3 digit code like 123 and its destination code would be 34123.

Sample data:

11006 L 7 29 2011 8 7 2011 1 C 4.10 57.34 PREP 2 0 0 San Antonio, United States

13953 P 12 26 2011 1 5 2012 2 A 3.30 249.00 A 2.0 148.00 MEM Cuba Christmas 3 0 2 Sierra Del Rosario, Cuba

62444 N 12 28 2010 1 11 2011 3 A 4.2 219.00 A 16.30 1599.00 A 3.5 199.00 TRAV 435.50 3 0 0 Wellington, New Zealand