Lab Assignment # 3, CSE 1320 Section 001, Fall 2005

 

Due Date:     Section 001 – Nov 9th , 1:00pm

(see instructions on website for how to turn this in)

 

Topic objectives:       Structs

                                                Enumerated types

                                                Unions

                                                Bit fields

                                        Arrays of structs

                                        Sorting with recursion

                                        File input

 

Our spice rack program is working well for our novice cooks so we are going to improve the structure internally and add some more functionality for the user.  The internal changes will be to convert our representation from separate arrays for the name pointers and the spice costs and amounts to one array of structures where a structure holds all the data for a single spice. There will also be structs for the spice blends.  The external changes will be to allow the user to save more data about each spice and each spice blend and to sort the spices and blends in new ways. 

 

The internal changes start with new data structures.  There will be a new data structure for the spices and a new structure for the blends.  The data structure for the spices will hold all of the existing spice information and the new information as given below.  The spice structure should contain:

                        Pointer to the spice name (which will still be dynamically allocated)

                        Quantity of the spice in units    (same data type as previously)

                        Total cost of the quantity of spice    (same data type as previously)

                        Cost for one unit of spice    (same data type as previously)

                        An enumerated type indicating whether the spice is stored as ounces or milligrams

                        A union giving the conversion factors (based on enumerated type value) for either:

                                Ounces to cups

                                Milligrams to grams

A short int t representing the total number of blends this spice is part of  (utility)

A bit field of 6 bits which will indicate which blends this spice is part of by setting one bit for each blend (the blend numbers corresponding to the bits will be part of the blend info)

 

You will declare an array of 20 of these spice structs.  Your program will then read in the input data for the structs from a text file called spicein.dat .  There will be between 10 and 20 spices in the file with the number of spices in the file given on the first line of the file.  The format of this file is given below by listing the Line number and then the data that will be on that line:

 

                Line 1:       number of spices  numspice  in the file

                Line 2:       name of a spice (can be one or more words)

                Line 3:       number of units of the spice

                Line 4:       number giving total cost for the amount of spice on the previous line

                Line 5:       a single lowercase char – either ‘o’ for ounces or ‘m’ for milligrams

                Lines 6 - 9:       same data as Lines 2 - 5 for the next spice

                Lines 10  …     repeat sets of spice data lines for numspice  spices

               

Notice that your program must calculate the cost per unit for the spice.  The value for the utility t and the bit field value will be determined by your program using the blend information.  There will be a sample spice data file on the website for you to use as one set of input and as a guideline to creating other input files.

 

The second struct in your program will be a struct to hold the blend information.  The data structure for the blends will hold all of the existing blend information (basically the list of names and the list of amounts will be inside the new struct) and the new information as given below.  The blend structure should contain:

 

                        Pointer to the blend name (which will still be dynamically allocated)

                        A unique base-2 blend number (to be used in the bit field of the spices)

                        An integer representing the number of spices used in this blend <= 10

                        An array of ten pointers to the spice names needed for this blend

                        An ten element array of units needed of each spice for the blend

                        A cost for one mixture of this blend

                       

Your program will declare an array of six of these structs.  The blend  data will be read in from a file named blendin.dat .  Your file should have the information for 6 blends in it.  The file data will be in the following order:

                                               

                Line 1:       name of a blend (can be one or more words)

                Line 2:       blend number (which should be a power of 2 , i.e. 1, 2, 4, 8, 16, 32)

                Line 3:       integer b giving the number of spices in the blend (b must be <= 10)

                Line 4:       name of the first spice in the blend (can be one or more words)

                Line 5:       number of units of the spice needed for the blend

                Line 6:       name of the second spice in the blend (can be one or more words)

                Line 7:       number of units of the spice needed for the blend

                Lines 8 – (2*b+3):       names and units of remaining spices in the blend for b spices

 

                Lines (2*b+4) …:        same data as Lines 1 – (2*b+3) for the next blend

                Lines …                        repeat until all data is entered for 6 blends

 

There will be a sample blend data file on the website for you to use as one set of input and as a guideline to creating other input files.

 

Given the blend data, you must use this input to add information to the spice structures.  Your program should go through each blend and check each spice to see if it is part of that blend.  If the spice (ex: oregano)  is part of a given blend (Ex Italian blend which is blend number 1 ), then in the oregano structure, the bit field should be modified so that the bit corresponding to blend number 1 is turned on (this will use the blend numbers as bit masks for each blend).  After the first blend is recorded this way, then continue with the next blend.  When this is complete, the bit field of each spice will correspond to all the blends that the spice is part of.  After all the blends are recorded in the spices, the program must check each bit field and calculate an integer t which tells how many blends the spice is part of  by counting the number of bits turned on in the field.  Ex:  If oregano is part of Italian blend 1, and Cajun blend 4, then oregano’s bit field will look like 000101  and the integer t for this spice would be 2 since oregano is part of two different blends shown by two bits turned on in the bit field.  The value of t will be called the utility of the spice.

 

 

Given the new data structures most of the rest of the task is to modify your existing functions to work with the new data structures.  You should modify the printing function, the name sort, the cost/quantity sort and the associated swap function, whether a seasoning blend can be made and how many mixtures, creating a shopping list for missing spices, and calculating the cost of one mixture of a blend. 

 

You should present the choices of actions to the user as a menu which will allow them to sort in the various ways, print, and check a seasoning blend.  If you used a menu in the last lab just expand it with the new option given below.

 

You must also add one new function.  You must allow the user to sort the spices based on the utility of the spice as measured by how many blends it is part of.  This sort should be performed using the recursive merge sort algorithm.  If two spices are in the same number of blends, then the order in the utility sorted list of those two spices doesn’t matter.   This sort should be an option to the user in the same menu as the existing name sort and cost/quantity sort.

 

 

 

Implementation requirements:

 

 

The program should use the following data structures:

Array of 20 structs for spices as defined above

Array of 6 structs for blends as defined above

The program should NOT use the following data structures:

Linked list

 

 

The program should use the following control structures:

Function calls to perform tasks

Loops to perform testing for the spice utility in blends

Selection statements as needed

Recursion in a merge sort algorithm for numeric utility values

The program should NOT use the following control structures:

breaks outside of switch structures

continues

gotos

exits

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

 

The program should be implemented as a set of functions as in the previous labs with new functions added for calculating the utility values and for performing the merge sort.  You should use at least 8 functions.  You may use more functions than this but you must use at least this many.

 

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 value from the keyboard

Perform appropriate calculations and print the appropriate outputs

Let the user enter additional values until the user indicates that they are finished.

 

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. 

 

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.

 

This program must be run with three different sets of data for the spice rack contents and one data set for the spice blends.  The first data set (dataset 1) will be given as a file on the website. You must also create two additional data files and run your program with them as well.  A file containing half the required blend data will also be posted on the website.  You must add seasoning blends up to a total of 6 blends.  You may run the program three times within a single execution or you may execute the program three different times so that you have a total of three different data sets. The sample datasets that you create must meet the guidelines given in the problem definition.

 

The program output must be recorded in a script file from OMEGA 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.  

 

 

Grading scale:

Code:     (75%)

                Headers, Style, Modularity (8 points)

Program header and function headers for all functions   

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

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!)  Follows the function structure requirements given

Correct definitions of spice and blend structs  (14 points total)

        Data for name, cost, quantity, and utility (6 points)

        Enumerated type member (2)

        Union type member (2)

        Bit field member (4)

Correct definition of enumerated type (4 points)

Correct definition of union type (4 points)

Correct manipulation of the arrays of structs (8 points)

                Correct use of file input (8 points)

Correct manipulation of bit field to represent blend membership (6 points)

Correct calculation of utility (6 points)

Correct implementation of recursive merge sorting for utility values (10 points)

Correct use of required control structures (4 points)

Proper implementation of input error checking for quantities and costs (3 points)

Output:          (25%)

                User clearly understands program options throughout program execution (3 points)

                Sorted output is correctly printed (3 points)

                Modification of existing functionality with new data structures is done correctly (8 pts)

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

                Output contains all the sample data and two additional data sets  (6 points)

 

 

Deductions:

                Use of global variables will result in an overall grade of 0 (zero)

                        NOTE: Types are allowed at be defined globally

                Use of the goto or exit commands will result in an overall grade of 0 (zero)

                Use of linked lists will result in a 30 point deduction

                Use of continue will result in a 20 point deduction

                Use of a break outside of a switch statement will result in a 20 point deduction

                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.