Lab Assignment # 3, CSE 1320 Sections 001 and 501, Fall 2004

Due Date: Section 501 – Nov 9^th, 5:30 pm

Section 001 –Nov 10^th, 1:00 pm.

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

Topic objectives: Recursion

Structs, enum and unions

Static variables

File input with scanf

(Plus all the stuff you’ve already done)

We’re back to work on your bookstore, Plus or Minus Perfect Books (or ‘±Perfect’ for short). Now that you’ve compared publisher/distributors and selected one, you are ready to put together your inventory list - a complete list of the titles and quantities of books you wish to order. You will be reading in a set of information for each book from a file and storing the book information into an array of structs. This is the basis for your inventory database for ±Perfect. You will then be sorting this array in multiple ways based on the order in which the publisher/distributor wants the book requests sorted.

The first step is to design a data structure to hold all the information required about a book for your inventory database. The information will include all the data used before with some additional detail as well as some further pieces of info for each book. Your inventory list will be an array of these structs that is dynamically allocated based on the number of books in the input file. The number of books in the file will be the very first number given on the first line of the file. The input file of book data will be a text file named “bookinput.txt”. Your program will read the first line of the file to find out the number of books, will dynamically allocat an array of structs to hold the book data and then will read in the information for all the books from the file.

The data to be stored in the struct for each book will be

title

author’s last name,

author’s first name,

author’s middle initial,

wholesale price,

retail price,

quantity,

ISBN number as a long int (it is basically a 10 digit numeric tag),

year this book was published,

year this book was first published,

an enumerated type value of P, S, H, C or D indicating whether the book is paperback (P), softcover (S), hardcover (H), cassette (C), or CD (D), and

a union giving one of the following:

a number of pages for paperback, softcover, or hardcover books,

a number of tapes for cassette books, or

a time in hours and minutes of the length of the book reading for CD books. (This will be a floating point value with the whole number part representing the hours and the fractional part representing the minutes (just humor me))

Format for the given data will be 4 lines as follows in the input file (there is one blank between each data item on lines 3 and 4 for each book):

Number_of_books <first line of the file>

Title (a string on a single line of the file; 1^st line of book data)

Last_name, First_name, I (2^nd line; with commas; no dot after the initial – if the author has no middle initial then there will be no comma after the first_name (test for this!) and a blank should be stored in the middle initial field in the struct)

Wholesale Retail Quantity ISBN (3^rd line; NO commas between numbers)

Publication_year First_pub_year E Number (4^th line; 4-digit years, E is single letter for enum type and number is appropriate union value for given enumerated type)

Title_for_next_book etc.

Last_name for next book … See sample data file given for format example.

The steps for getting the book data are:

1) read the number of books numbooks from the first line of the file

2) dynamically allocate storage for numbooks structs using a pointer to the beginning of these records

3) use a loop to read in the four lines of data for numbooks books from the file and store the data into one of the structs in the book inventory array of structs

a. read the book title from one whole line of the file

b.read the next line and break it into a last name, a first name and a middle initial if there is one

c. read in four numbers from the next line for wholesale, retail, quantity and ISBN

d.from the fourth line of book data read in two years, then a single character then the appropriate number

After all the book data has been read in, the program should print out all the book inventory information in some moderately easy-to-read format (like give the data labels and print blank lines between the data for different books or make a table or something)

After the book inventory has been printed the program must allow the user to choose one of the following options:

1) Print a list of book titles only in the current order

2) Print a list of authors (first_name middle_initial last_name) only in the current order

3) Sort the list by ISBN number and print the titles and ISBN numbers after the list is sorted.

4) Sort the list by book title and print the list of titles and author’s last names after the list is sorted. (Don’t worry about the rules for “The” and “A”)

5) End the program

The user must be allowed to continue choosing from these five options until they select option 5.

For option 3, your program should use a recursive quicksort algorithm to sort with based on the ISBN number values. The main part of the quicksort algorithm in C is given at the end of this assignment (the function is called sort) along with a description and some pseudocode. You may use this function in your program and modify it as necessary. Do NOT use the qsort function discussed in the book. You MUST write your own swap function to be called by the quicksort function.

For option 4, your program should use a bubblesort algorithm to sort with based on comparisons of the title strings using the string functions in C. You must write your own bubblesort algorithm based on the discussion of the algorithm in class. You must also write a swap function for the bubblesort. In the bubblesort function you must also keep track of how many times swap is called. If bubblesort has been called before, then the current call should compare the previous number of swaps (in the last time bubblesort was called) to the number of swaps made this time and print this comparison before bubblesort returns to the calling program. If this is the first call to bubblesort then just print the number of swaps made.

After this is done, print a concluding message and then end the program.

Implementation requirements:

The program should use the following data structures:

At least one struct type and dynamically allocated array of structs as described above

An enumerated type for the book format

A union for the values associated with the book format

A static variable to count calls to the bubblesort swap

The struct type may be declared globally but the struct pointers and variables must be declared locally

The enum and union types may be declared globally but the variable must be declared locally

The program should use the following control structures:

Recursion (in the quicksort)

Other control structures already discussed as needed

The program should NOT use the following control structures:

breaks outside of switch structures

continues

gotos

exits

The program should also use the following:

File input for the book data

The program should have a main function and at least four (4) subfunctions but no more than twelve (12) subfunctions. Each function should focus on one particular task.

This program must be run with at least three different sets of data in the input file. The first data set (data set 1) should use the values given in the file that is linked to this lab assignment. You must also create at least two additional data sets (with at least 5 unique books each) and run your program with them as well. [Create three different files of input data and then for each run, copy one of them to the appropriate file name in order to use it in the program.]

You must execute the program three different times. The sample data sets that you create must meet the guidelines given in the problem definition. Each execution of the program should demonstrate options 1 – 5. At least one execution of the program must demonstrate option 4 being used at least twice not consecutively (in order to demonstrate the static swap count).

General implementation requirements for all assignments:

The program should perform the roughly 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 info or choices 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.

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: (81%)

Headers, Style, Modularity (12 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!)

Correct declaration of struct type to contain all required data (6 points)

Correct declaration of pointer to struct to use for dynamic allocation (3 points)

Correct allocation of memory for array of structs (6 points)

Correct declaration of FILE variables (4 points)

Appropriate opening and closing of specified file (6 points)

Effective data input from file and storage into array of structs (10 points total)

Tokenizing of names (3 points)

Checking for middle initial value(2 point)

Correct choice of data type based on enum flag (2 points)

Correct use of quicksort (5 points)

[if unique quicksort is written it must be recursive]

Correct swap function implementation (7 points)

Correct implementation of bubblesort (10 points)

Correct use of static counter for swap calls in bubblesort (5 points)

Correct string comparison (4 points)

Correct function structure as required (3 points)

Proper implementation of user control (3 points)

Output: (16%)

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

Output contains all the sample data and at least two additional data sets (10 points)

Deductions:

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

Use of qsort from textbook will result in a 30 point deduction

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

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

Late submission of softcopy to appropriate TA will result in an overall grade of 0 (zero)

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.

Quicksort

Source : http://en.wikipedia.org/wiki/Quicksort#Performance_and_algorithm_details

Because of its good average performance and simple implementation, Quicksort is one of the most popular sorting algorithms in use. It is an unstable sort in that it doesn't preserve any ordering that is already between elements of the same value. Quicksort's worst-case performance is Θ(n²); much worse than some other sorting algorithms such as heapsort or merge sort. However, if pivots are chosen randomly, most bad choices of pivots are unlikely; the worst-case has only probability 1/n! of occurring.

The Quicksort algorithm uses a recursive divide and conquer strategy to sort a list. The steps are:

• Pick a pivot element from the list.
• Reorder the list so that all elements less than the pivot precede all elements greater than the pivot. This means that the pivot is in its final place; the algorithm puts at least one element in its final place on each pass over the list. This step is commonly referred to as "partitioning".
• Recursively sort the sub-list of elements less than the pivot and the sub-list of elements greater than the pivot. If one of the sub-lists is empty or contains one element, it can be ignored.

In pseudocode, the complete algorithm in its simplest form is:

The following is wikicode, a proposed pseudocode:

 function partition(a, left, right, pivotIndex)
 pivotValue := a[pivotIndex]
 swap(a[pivotIndex], a[right]) // Move pivot to end
 storeIndex := left
 for i from left to right-1
 if a[i] <= pivotValue
 swap(a[storeIndex], a[i])
 storeIndex := storeIndex + 1
 swap(a[right], a[storeIndex]) // Move pivot to its final place
 return storeIndex
 
 function quicksort(a, left, right)
 if right > left
  select a pivot value a[pivotIndex]
 pivotNewIndex := partition(a, left, right, pivotIndex)
 quicksort(a, left, pivotNewIndex-1)
 quicksort(a, pivotNewIndex+1, right)
 
 
Implementation in C for integer arrays:
 
void sort(int array[], int begin, int end) {
 if (end > begin) {
 int pivot = array[begin];
 int l = begin + 1;
 int r = end;
 while(l < r) {
 if (array[l] <= pivot) {
 l++;
 } else {
 r--;
 swap(array[l], array[r]); 
 }
 }
 l--;
 swap(array[begin], array[l]);
 sort(array, begin, l);
 sort(array, r, end);
 }
}

Bubblesort implementation and algorithm information can be found at the link below

Source : http://en.wikipedia.org/wiki/Bubble_sort