Lab 8
Lab assignment: Structs for the storage and retrieval of data
This week in lab we'd like you to familiarize yourself with the structure of structs. We've given you some sample code which uses some struct objects, and we'd like you to implement some algorithms over them. When you get used to them, it's like defining your own data types, but the syntax can be weird so here's your time to practice and ask questions. This assignment is similar to writing a frontend for a really basic database. We're not even worrying about adding and removing elements yet, though if you wanted to practice dynamic allocation in the context of structs go right ahead. The "functions" you should implement for this lab are
1. Print out the database
2. Sort the data by a given criterion
3. Find a particular item from the database
Note that you need not actually use methods or functions to implement this functionality.
In the code you're given the declaration for an array of structs, as well as the instantiation of elements of that array using data I produced from some database. Also, you are given the structure of the code, which prints out the database, calls a sort function on the data, and then searches through the data for a particular value.
This week's lab will be in C, though it is okay if you use C++ style input and output. Structs are primarily a C construct, whereas classes with functions appear only in C++. Your book uses C++ structs, which are as powerful as C++ classes, so the syntax and functionality is different from C structs.
A sample run of the program will look like the following. (User input is shown in bold, though in your program it will not be bold.)
For one point:
Data:
Adams, Suma 768454006 37.000000
Alex, Cris 680378908 5.000000
Alvino, Jason 721777193 69.000000
Amrhein, Maria 798094980 1.000000
... // I'm not going to list all 75 lines here.
Vinot, Hill 684654477 73.000000
Warner, Jill 658026216 61.000000
Williams, Michael 785019931 78.000000
For two points:
Which field would you like to sort by?
1. First Name
2. Last Name
3. UIN
4. Grade
3
Sowles, Charles 650993131 83.000000
Villalobos, Patricia 651055147 7.000000
Kinney, Brian 653179869 52.000000
Nash, Christopher 653856107 27.000000
... // Again, I don't think you need all this data in a lab prompt.
Verhoeven, Andrew 791215097 75.000000
Goehring, Brian 794717105 78.000000
Amrhein, Maria 798094980 1.000000
And for extra credit:
if user choice was 2
Which last name would you like to look up? Siebert
At index 64
Siebert, Sabrina 706562581 7.000000
if user choice was 3
Which UIN would you like to look up? 709418024
At index 28
Minielly, Gary 709418024 23.000000
if user choice was 4
Which grade would you like to look up? 57
At index 47
Flagg, Megan 756141672 57.000000
and an example where the object could not be found (happens to be sorted by first name (user choice 1))
Which first name would you like to look up? Sean
No Student was found with the first name Sean.
Use only structs from C, the syntax is different for C++ (largely how you treat it as a type). This means you will have to use typedef notation when defining your struct to make it work with the sample code. You may use any of the library functions for C string operations. Wherever possible, you should use the builtin and library C functions instead of looping through the characters yourself.
Stage 1 (1 point):
Print out all of the struct objects in the format "LastName, FirstName UIN Grade". Use tabs as appropriate to line up the columns. If the spacing doesn't match my example, that's fine, I'm not too concerned with the actual formatting of the output. Similarly for grade, I used a double but all of the data is integers so if you want to use an int that's fine too. The data is already given to you in an array of structs, so just set up a loop to access and print out the data. Reserve 20 characters for the char[]s for first name and last name. As a starting point you should use the sample file called Lab8.c provided at the bottom of this page. The file given demonstrates how to instantiate structs, and provides the data in an array of structures, but does not include the struct definitions or their usage, and will not compile without the struct definitions. You may use either struct notation, I used the typedef one because I think it's more sane. Note that if you want to use C++ style input and output you will need to change the import statements and change the file to a .cpp.
Stage 2 (1 point):
Sort the array of struct objects by either FirstName, LastName, UIN, or Grade, depending on user input. After sorting the array, print out the array again. You can apply any sorting technique you wish, and keep in mind that you can perform assignment of structs, which will automatically assign each of the fields. In general you should be careful about char[]s though, as they might be pointing to the same location after an assignment, instead of actually reserving the space. This depends on how the struct is constructed, with a pointer or actually with the full memory allocated in the struct. In this case, if you declare a fixed size for the character arrays in your struct, assignment should work correctly with no issues.
Stage 3 (Extra Credit) (1 point):
Ask the user for an element matching the one sorted by, and then perform a binary search of your array to find that structure and print out the index of that element in the newly sorted array, and the line for that structure. If you can't find the object in the array, then print out that the object could not be found. Look at the sample input for an example of what I mean by this, and if you're still confused ask Sean.
Notes:
Keep in mind that this is a team effort so you should agree with your partner on what you are going to do before you start typing. The partner who is typing is the "driver" and the partner watching is the "navigator." Be sure to switch roles every 10 to 15 minutes, to foster a deep understanding of the code for both partners. The navigator should be watching for syntax errors and verifying the correctness of the code you're writing.
It will speed things up for you if you keep a window open for editing and have a separate window open for compiling and running your program. Remember that windows are resizeable!
Submission:
1. You should work with a partner for this (and all the remaining) lab(s). Only one of you need to submit the program to Blackboard, though you should be certain that both of your names be present in a comment at the top of the .c or .cpp source file.
1.5 If you work alone, include just your name in the comment at the top so that I know you worked alone, and not have to guess.
2. You should turn in to Blackboard by the END OF THE LAB (8:50 for the 8-9 lab session, 9:50 for the 9-10 lab session). I know it's tempting to keep working on it, but other classes come in, and it's not fair to the students who are limited to that particular time span if you go over. Which isn't to say that you can't work on it later, to check your solution against the one I post for your own understanding. But what you submit for a grade should be before the next hour begins.
3. If you wish, you may submit your lab by 11 am on Thursday for a 1 point penalty. If you can't finish up the second point by the end of lab, you can still earn the score by completing all three steps and submitting your code by the day after.