Homework 6
Arrays of Pointers, Access Tables
Due: Tuesday, December 11, 2012 at 5pm
Outcomes
After successfully completing this assignment, you will
be able to...
- Work with arrays of pointers
- Use an access table to access an array in an order different from the
array's physical ordering
Before Starting
Review Chapters 6, 7, and 8 in Deitel & Deitel.
Access Tables
In this assignment we'll use multiple arrays (access tables) to refer to
a single array of information. For example, consider an array of student
records at WPI, where each record consists of a student's name and ID number.
You can imagine the Registrar wanting, at different
times, to obtain a list of students ordered alphabetically by name, or
a list of students ordered by increasing ID number. What we would like to
do is come up with a scheme in which the data in the array remains in place,
but we have a way of visiting the elements in the array in the desired order.
What we'll do for each type of ordering is keep an array of subscripts
that correspond to the elements ordered the way we want. For example, given this data in the original array:
| array element |
name |
ID |
| [0] |
HAMEL, GLYNIS
|
39602 |
| [1] |
WARD, MATT |
4412 |
| [2] |
HEINEMAN, GEORGE
|
6074 |
| [3] |
WILLS, CRAIG
|
5570 |
| [4] |
FISLER, KATHI
|
3964 |
We would construct this array to provide access to the data in alphabetical
order:
| array element |
subscript |
| [0] |
4
|
| [1] |
0 |
| [2] |
2
|
| [3] |
1
|
| [4] |
3
|
The meaning is this: you will find the name closest to the beginning of the
alphabet (FISLER, KATHI) at subscript 4 in the original array. The next one
in order is at subscript 0 (HAMEL, GLYNIS), and so on. Similarly, to order the
original data by increasing ID number, we would construct an array consisting of these
values:
| array element |
subscript |
| [0] |
4
|
| [1] |
1 |
| [2] |
3
|
| [3] |
2
|
| [4] |
0
|
By using access tables in this way, we can avoid keeping multiple copies of
the original data, which would be wasteful of storage space. And if a change
needs to be made to one of the student records, we only have to
make the change in one place; we're spared the problem of making sure that
multiple copies of the data are updated in exactly the same way.
The Assignment
In this assignment, we'll create an alphabetical access table for names of students
enrolled in a course. However, instead of storing subscripts in the
access table, we'll store pointers (to the name strings).
Here are the declarations you should use for the array that holds the names
and the array that holds pointers to the names:
#define MAXSTUDENTS 20
#define MAXSTRING 30
char students[MAXSTUDENTS][MAXSTRING]; // the original list of names
char *alphabetic[MAXSTUDENTS]; // array of pointers to the names
Student names are entered into the students array. After all the names are entered, a sorting routine will be called, and both the
original list and the
alphabetized list will be displayed. The original list should not be modified by the sorting function. Here is a sample execution:
How many students are enrolled? 5
Enter the names of the students on separate lines:
JENKINS, JOHN
WANG, JIN
SULLIVAN, DANIEL
FISHER, KATHERINE
BELOIT, KIMBERLY
Original Order Alphabetical Order
------------------ -------------------
JENKINS, JOHN BELOIT, KIMBERLY
WANG, JIN FISHER, KATHERINE
SULLIVAN, DANIEL JENKINS, JOHN
FISHER, KATHERINE SULLIVAN, DANIEL
BELOIT, KIMBERLY WANG, JIN
Assumptions and Restrictions
- Make sure the students' names are stored as strings (null-terminated
array of char).
- Initialize the
alphabetic array to contain the addresses
of each string in the students array. Then call a sorting
function to sort the pointers in the alphabetic array corresponding
to the alphabetical ordering of the strings in the students array.
- You may choose any sorting function to do the sorting. In Homework 4 you
were provided with code for
bubblesort to sort an array of numbers, and the textbook also contains
code for bubble sort (Figure 6.15). The online Appendix E (available through
www.pearsonhighered.com/deitel/) contains code for
selection sort and insertion sort. Whichever sorting algorithm you choose,
make sure you take the time to understand it thoroughly before you
modify it for this assignment. Your modifications will involve comparing
strings instead of integers (you'll want to use the C function
strcmp to compare strings alphabetically). The array you will be passing to the
sorting function will be the alphabetic array (not the
students array). Your sorting function should be in a separate
.c file.
- Uppercase and lowercase letters have different ASCII codes. According
to the
strcmp function, the string "Alcott" comes before the
string "adams" (because the ASCII code for 'A' is smaller than the ASCII
code for 'a'). To keep you from having to deal with this problem, you may enter the students' names in
all capital letters (or in all lower-case letters). (Of course, if you would
like to write your solution so that it does alphabetize mixed upper/lower case
strings correctly, you are welcome to do so.)
Deliverables
Here is what you should submit for the assignment:
- A README.txt file decribing the files, functions, and data
structures of your program, including instructions on how to build
your program
- All .c and .h files needed to build your program, and your makefile, compressed into one .zip file.
Submit your files using web-based turnin.
Grading
This assignment is worth 35 points:
- Successful compilation without warnings using your makefile - 5 points
- README file as described - 5 points
- Program comprises multiple files (separate file(s) for sorting) - 5 points
- Program documentation, including pre- and post-conditions for all functions - 5 points
- Both arrays initialized as specified in the assignment - 5 points
- Sorting function modified to sort
alphabetic array - 5 points
- Correct execution - 5 points
Programs submitted after 5pm on December 11 will be tagged as late,
and will be subject to the late homework
policy.