编程辅导 C C++ Java Python MIPS Processing 网络家教 在线辅导

Dictionary DatabaseThis is a fairly large program, and you will only haveto implement part of it. You will be provided with the source code for some basic functions, the structureyou can use to repres

Dictionary Database
This is a fairly large program, and you will only have
to implement part of it. You will be provided with the source code for some basic functions, the structure
you can use to represent the information for each book, and also the code for the top-level keyboard interface
to the program. Your task will be to build the lower level functions that build and manipulate the database.
You will represent the library database as either an array or a tree of structures, one structure per book,
each containing the relevant title, author name and year of publication for the book. The struct Book
structure you will be provided with contains this information, as follows:
#define MAX_TITLE_LENGTH 100
#define MAX_AUTHOR_LENGTH 100
/* Book structure
*/
struct Book
{
/* Book details */
char title[MAX_TITLE_LENGTH+1]; /* title string */
char author[MAX_AUTHOR_LENGTH+1]; /* author name string */
int year; /* year of publication */
/* pointers to left and right branches pointing down to next level in
the binary tree (for if you use a binary tree instead of an array) */
struct Book *prev, *next;
};
So the book title is represented by a string of maximum length MAX TITLE LENGTH (+1 to include the string
termination character), the author name as another string of maximum length MAX AUTHOR LENGTH, and the
year of publication as an integer. If either the title or author name is longer than the specified maximum
length, it should be truncated to the maxmimum length.
Representing a Database with an Array
In your program you will manipulate struct Book structures to build and modify the database. The simplest
way to represent several structures at once is as an array of structures. Let us set the maximum number of
books in our database to a defined constant MAX BOOKS:
/* maximum number of books that can be stored at once in the library
database (relevant only to storage using an array) */
#define MAX_BOOKS 200
Then we can define an array of MAX BOOKS structures, and use an integer to represent the number of books
currently represented in the program, which of course is initialized to zero:
/* array of books */
struct Book book_array[MAX_BOOKS];
2
/* number of books stored */
int no_books = 0;
This array representation may be used to represent our database. However there are some limitations with
using an array to represent a database:
• An array has a fixed size. The array book array of struct Book structures declared above can
obviously not hold details for more than MAX BOOKS books. This is only OK if you know beforehand
the maximum number of books you are likely ever to have, which is not likely.
• An array is inefficient in storing the information, again because of its fixed size. If you guess the
maximum number MAX BOOKS of books, and declare an array of that size, but in fact the program
actually only creates a much smaller database, most of the memory block used for the array is wasted.
• An array is inefficient in implementing important operations, especially if the elements of the array
are maintained in a specific order. Let us assume that our array is stored in alphabetical order of
title, and we wish to insert a new book “Fever Pitch” into the array shown in figure 1. As you can
see, insertion into an ordered array is a very inefficient operation, because every array element (in
this case struct Book structure) beyond the insertion point must shift up one place to make room.
This involves lots of copying data. The same applies to deleting a book, when all the book structures
beyond the deletion point would have to shift back one place.
The binary tree data structure gets around all these problems. It is a dynamic data structure, which expands
and contracts as the database size goes up and down.
However, the tree is also a much more complicated structure to create and work with. Implementing binary
trees involves the use of an advanced C feature called dynamic memory allocation. We shall first introduce
Figure 1: Illustration of the inefficiency of the array representation of an ordered database. Here the database
of books is ordered alphabetically by title name, and a new book “Fever Pitch” is to be inserted in the existing
array (a) of five books. To insert the new book, all the books with titles alphabetically “greater” than “Fever
Pitch” have to shift up one place in the array to make room for it.
3
the concept of dynamic memory allocation and provide a simple example, before discussing how we can use
it to efficiently build a binary tree.
If you do not want to use binary trees, you may use the much simpler array representation, but in this case
your mark will be limited to 90% for this assignment. Another possibility would be to convert your code
to the binary tree representation after you have successfully implemented the array representation. If you
do not want to know about binary trees right now, you may turn immediately to part 1 of the assignment
description on page 8.
Dynamic memory allocation
We must first introduce the mechanism provided in C to create temporary blocks of memory within a
program. The two most important functions that implement dynamic memory allocation in C are malloc()
and free(). malloc() is used to allocate a block of unused computer memory which can then subsequently
be used in the program. It is declared as:–
void *malloc(size_t size);
The size argument specifies how many bytes you want in your block of memory. The memory block is
returned as a generic pointer (void *) type, and can be cast (converted) to whatever C pointer type you
wish. When the program has finished with the memory block, the free() function is used to discard it so
that it may be used again:-
void free(void *ptr);
The void * memory block returned by malloc() should be passed to free() when it is not needed any
more. Here is a simple program using dynamic memory allocation.
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
int main ( int argc, char *argv[] )
{
char *string;
int length = 200;
string = (char *) malloc(length);
strcpy ( string, "This is a string that fits easily into 200 bytes" );
printf ( "String: %s\n", string );
free ( string );
return 0;
}
Firstly the character pointer string is declared. As you should know by now, a pointer can be used to point
to a single object, or it may specify the start of an array. In this case we dynamically create an array of
characters by calling malloc(), and set string to point to the start of it. string can then be used exactly
as if it had been declared as an array of characters, and we show an example, copying another string into it
and printing the copied string. The code for the alternative array version of the program would be
#include <string.h>
#include <stdio.h>
4
int main ( int argc, char *argv[] )
{
char string[200];
strcpy ( string, "This is a string that fits easily into 200 bytes" );
printf ( "String: %s\n", string );
return 0;
}
Comparing the two versions of the program, we note that
1. The version using dynamic memory allocation is more flexible, in that the size of the string allocated
need not be a constant (200 in this case) but can be any integer value, for instance (as here) the value
of an integer variable. The size of the allocated block of memory is determined when the program is
run. In the second version, the array size is fixed.
2. On the other hand, the array version is shorter and simpler. If malloc() is called, you must remember
to add a free() statement at the point where the program has finished using the memory block,
because otherwise the memory will be wasted. The memory taken up by arrays (allocated from the
“stack”) is returned automatically when the program block in which it was declared terminates, in this
simple case the end of the program. Predefined arrays are in this sense easier to use than dynamically
allocated arrays.
Another use of dynamic memory allocation is to create an instance of a structure. So for instance the
program segment
{
struct Book *new;
new = (struct Book *) malloc ( sizeof(struct Book) );
strcpy ( new->title, "Titus Groan" );
strcpy ( new->author, "Mervyn Peake" );
new->year = 1946;
free ( new );
}
creates a memory block the right size to hold a struct Book structure, sets new to point to it, and then fills
the fields of the structure with details of a book. The call to free() discards the memory block so that it
can be used again. Note the -> operator, which allows you to access fields of a structure via a pointer to it.
In fact new->author is equivalent to (*new).author, but a little simpler and more concise.
Without dynamic memory allocation one could write this program segment as
{
struct Book book, *new;
new = &book;
strcpy ( new->title, "Titus Groan" );
strcpy ( new->author, "Mervyn Peake" );
new->year = 1946;
}
5
Again this program segment is exactly equivalent. The book structure is here allocated from the “stack”,
and returned to the stack automatically at the end of the program segment.
NOTE: To use malloc() and free() in your program you must first #include the header file stdlib.h.
Binary Trees
So far the only benefit we have mentioned of dynamic memory allocation is the extra flexibility of being able
to create blocks of memory with size specified as the program runs rather than being fixed beforehand. The
other major benefit becomes clear if we extend the above program segment as follows:–
struct Book *book_tree = NULL;
{
struct Book *new;
/* create the first book */
new = (struct Book *) malloc ( sizeof(struct Book) );
strcpy ( new->title, "Something Happened" );
strcpy ( new->author, "Joseph Heller" );
new->year = 1973;
/* add first book to binary tree */
new->left = new->right = NULL;
book_tree = new;
/* create the second book */
new = (struct Book *) malloc ( sizeof(struct Book) );
strcpy ( new->title, "House of Mirth, The" );
strcpy ( new->author, "Edith Wharton" );
new->year = 1905;
/* add second book to binary tree, to left of "Something Happened" */
new->left = new->right = NULL;
book_tree->left = new;
/* create the third book */
new = (struct Book *) malloc ( sizeof(struct Book) );
strcpy ( new->title, "Suitable Boy, A" );
strcpy ( new->author, "Vikram Seth" );
new->year = 1993;
/* add third book to binary tree, to right of "Something Happened" */
new->left = new->right = NULL;
book_tree->right = new;
/* create the fourth book */
new = (struct Book *) malloc ( sizeof(struct Book) );
strcpy ( new->title, "Plague, The" );
strcpy ( new->author, "Albert Camus" );
new->year = 1946;
6
/* add fourth book to binary tree, to right of "House of Mirth, The" */
new->left = new->right = NULL;
book_tree->left->right = new;
/* create the fifth book */
new = (struct Book *) malloc ( sizeof(struct Book) );
strcpy ( new->title, "Handel’s Operas" );
strcpy ( new->author, "W. Dean and J. M. Knapp" );
new->year = 1987;
/* add fifth book to binary tree, to left of "House of Mirth, The" */
new->left = new->right = NULL;
book_tree->left->left = new;
}
Here we have created five books, and built a simple binary tree book tree to hold them, using the left and
right fields of the struct Book structure to hold the links between the book structures. The binary tree
generated by this simple example is illustrated in figure 2. Note that free() is not called. This means that
the book data stored in the binary tree is maintained outside the program segment in which it is created,
which is not possible with locally declared arrays.
Note the manner in which books are inserted in the tree. Given a new book, we firstly check whether the
new book title is alphabetically greater than or less than that of the top book in the tree. If it is greater,
we follow the right branch, if less the left branch. We repeat this process with the book we find along
the given branch, and continue down the tree, until we either find a book with the same title as the new
book, or a book left or right pointer to NULL. In the latter case we create a structure for the new book
and replace the NULL pointer with a pointer to the new book structure.
If a book is to be deleted from the database, for instance “A Suitable Boy” in the above database, one can
achieve this with the following code:
/* free the memory used for the book structure */
free ( (Book *) book_tree->right );
/* resets the pointer from the top-most node of the tree to NULL */
book_tree->right = NULL;
So free() is applied to the book structures as they become redundant. In general though, deleting books
which point to other books lower in the tree involves a tricky algorithm which you will not have to implement.
Instead there is a simpler alternative method, described in the assignment description below.
This binary tree method of holding book information gets around the previously mentioned problems with
arrays, because
1. The tree can grow and shrink as required. It is only limited by the computer’s memory.
2. It is usually more efficient in terms of using memory, because only the data required at any time is
stored. This usually compensates for the extra pointer fields(s) in the structure used to represent the
branches, which are not required in the array representation.
3. Insertion, deletion and other operations can be implemented efficiently as above. The difference between binary trees and arrays here is that with a binary tree the operation can be implemented as
a “local” operation, with only two or three nodes of the tree involved, whereas with ordered arrays
sometimes the whole of the array must be modified to implement a single operation.
7
Figure 2: A simple binary tree. (a) Initial empty tree pointing to NULL. (b) After the first book is added.
(c) After the second book is added. (d) After the third book is added. (e) & (f) after the fourth and fifth
books. See program segment for code to create this tree.
8
Part 1: Add books and print database (40 %)
Now you should have decided whether to use arrays or binary trees for the assignment (or if you want to
start with arrays and try trees later). So we can now describe the details of the assignment. Firstly, cd
to your eeclabs directory. Then download the database code and examples from SurreyLearn and then
put them into your directory. database1.c, database2.c and database3.c are “template” programs with
some empty functions, which you shall fill in with code as the assignment proceeds. Compile the program
with the command
gcc -ansi -Wall database_main.c database1.c database2.c database3.c -o database
It should compile successfully. Run it using the command:
./database
You will find that none of the menu options do anything, except 5 (Exit), which should work! When
any other menu option is selected, the relevant function (menu add book(), menu get book details(),
menu delete book() or menu print database()) is called, but these functions are empty. Your assignment
is to build this program into a useful database program by filling in these empty functions.
For part 1 of the assignment you need to fill in database1.c. If you want to use arrays, you can ignore (or
even delete) the definitiond of the book tree variable and the get tree depth() function, and remove the
body of the menu print tree() function which are defined in database main.c and database main.h. This
may make the code less cluttered and easier to read.
Similarly, if you’re using the binary tree representation, you can ignore (or delete) the book array and
no books variables in database main.c and database main.h.
Please note that, as with the other assignments, the testing that will be applied to your program involves
redirecting the input (stdin) from a file, then comparing what your program prints on standard output
(stdout) against the correct output specified in the assignment sheet and produced by our reference program.
Your program must conform to the specified output format to be classified as a working program. Therefore
please take note of any instructions regarding output. The use of the standard error (stderr) is however
unrestricted, so any debugging messages, prompts etc. should be fprintf’d to stderr.
In the first part of the assignment, you are to fill in the functions menu add book() and menu print database()
by modifying database1.c. These functions are called when menu options 0 (add new book) and 3 (print
database to screen) respectively are selected by the user.
menu add book() should prompt the user to enter the title, author and publication year of the new book,
in that order, and add the new book to the array/binary tree database. The prompt messages (which you
can choose for yourself) should be printed to standard error (use fprintf(stderr,"...), NOT standard
output (i.e. DO NOT use printf("...). The title and author should be entered as strings, truncated to
MAX TITLE LENGTH and MAX AUTHOR LENGTH characters respectively. The publication year is an integer. If
any part of the description is entered incorrectly (i.e. empty title/author strings are typed, or non-number
year entered), the program should continue to prompt for the relevant detail until a legal version is provided,
before going on to the next part of the book description.
The function menu print database() should print the details of each book in the library database in alphabetical order of title to standard output (i.e. DO use printf() here), with each part being printed
on a line by itself and prefixed by the strings "Title:", "Author:" and "Year:" respectively, and also a
space separating the prefix from the relevant following string/character/integer. There should be a blank
line between each book.
Compile the program with the command
gcc -ansi -Wall database_main.c database1.c database2.c database3.c -o database
9
To test your program, the file input1 can be used as input to the database program, to simulate keyboard
input. Once you have adapted your program as above, and compiled it, run the command
./database < input1 > tmp
The contents of the standard output are sent to the file tmp, which should then contain
Title: Dispossessed, The
Author: Ursula Le Guin
Year: 1974
Title: Don Quixote
Author: Cervantes
Year: 1605
Title: Feersum Endjinn
Author: Iain M. Banks
Year: 1994
Title: Longitude
Author: Dava Sobel
Year: 1996
Title: Structures
Author: J. E. Gordon
Year: 1978
You can check that your output is correct by comparing it against the file output1
diff -s output1 tmp
This will help you ensure that you are following the specification. However we strongly suggest you also
perform other tests to make sure your program is working, particularly to test its behaviour with illegal
inputs.
NOTE 1: You should not change the main() function or place any of your own code into the files database main.c
or database main.h, as you will not submit these files to SurreyLearn. You should use either the global variable book tree to represent your tree, or if using arrays use the global book array and no books variables
defined for you. If you’re using binary trees you should not change the provided get tree depth() or
menu print tree() functions.
Apart from these conditions you are free to implement the program as you wish, so long as it produces
the correct output to stdout for a given keyboard input (from stdin). This applies to all parts of the
assignment.
NOTE 2: Most of the marks will be for correct operation of the program given legal input. The tests and
actions described above for illegal/over-long inputs in menu add book() will gain you a few extra bonus
marks.
Once you are sure the menu add book() and menu print database() functions are working, and have written
comment blocks into the source code for any extra internal functions you have added to the database1.c
program (as described in the rules for assignments on the Web page), re-name your file according to the
following specification and then submit the code to SurreyLearn.
10
NOTE 3: The name of the submitted file MUST be proceeded with your surname and initial followed by
the name of the program. For example, if your surname is “Brown”, and your first name is “Peter”, you
need to name the file as follows:
BROWNP-database1.c
The first part is your surname and initial followed by a hyphen, and then followed by the original filename
(database1.c). If you also have middle names, ignore them in the file name. If your files do not
follow this name specification, 10 percent will be deducted from your final mark.
Part 2: Get/Delete books from the database (35 %)
In the second part of the assignment, you will fill in the functions menu get book details() and menu delete book()
in database2.c. These functions are called when menu options 1 (get details of book) and 2 (delete book
from database) respectively are selected by the user.
menu get book details() should prompt the user to enter the full title of the book to be deleted (as it
appears in the database), and then print the title, author and year of publication of the book in the same
format as for menu print database(). If the title does not match any book in the database, the function
should fprintf an error message to stderr (e.g. “Book not found”) and return.
menu delete book() should prompt the user to enter the full title of the book to be deleted (as it appears
in the database), and delete the named book from the book database. If the title does not match any in
the database, the function should fprintf an error message to stderr (e.g. “Book not found”) and return
with no change to the database.
SPECIAL INSTRUCTIONS FOR TREE USERS
If you are using a tree to represent the database, you can either attempt to delete the book from the
tree, which is very tricky to implement, or retain the book to be deleted in the tree, and simply “mark”
it as deleted. You can mark a book as deleted by, for instance, setting its publication year to a special
value, say 9999, or alternatively setting its author string to empty (as you will see below, you should
not modify the title string). If you choose this simpler option, you will need to modify your code for
menu add book(), menu print database() and menu get book details() to recognise the special year and
take the appropriate action (or inaction). For instance, menu print database() should ignore marked
books, and if you are adding a book into the database that has previously been deleted, you merely need to
“revive” the book by overwriting the author and publication year with the new values. Note that in order
to do the latter, you must have retained the title string so that it can be recognised.
If you want to try and delete a book “properly” from the tree (which will not earn any additional marks),
here are a few hints. If book A is the book being deleted, find the book B that lies “above” book A and
points to it. Set the relevant left/right pointer of B (whichever pointed originally to A) to the left (or right,
if you prefer) pointer of A. Then you have to insert the sub-tree attached to the right (or left) pointer of A
in the correct place in the tree, which is a NULL left or right branch in the position in the sub-tree contained
by book B that maintains the alphabetical order of the tree. Finally free the memory for the deleted book
structure. Deleting the top-most node should be treated as a special case. Good luck if you try this!
END OF SPECIAL INSTRUCTIONS.
Compile the program with the command
gcc -ansi -Wall database_main.c database1.c database2.c database3.c -o database
11
To test your program, the file input2 can be used as input to the database program, to simulate keyboard
input. Once you have adapted your program as above, and compiled it, run the command
./database < input2 > tmp
The contents of the standard output are sent to the file tmp, which should then contain
Title: Something Happened
Author: Joseph Heller
Year: 1973
Title: Frankenstein
Author: Mary Shelley
Year: 1816
Title: House of Mirth, The
Author: Edith Wharton
Year: 1905
Title: Frankenstein
Author: Mary Shelley
Year: 1816
Title: House of Mirth, The
Author: Edith Wharton
Year: 1905
Title: Something Happened
Author: Joseph Heller
Year: 1973
Title: Frankenstein
Author: Mary Shelley
Year: 1816
Title: Something Happened
Author: Joseph Heller
Year: 1973
Title: Frankenstein
Author: Mary Shelley
Year: 1816
You can then check that your output is correct by comparing it against the file output2
diff -s output2 tmp
Again, passing this test is a good start, but it does not necessarily guarantee that your program will work
in every situation. You should still test your code yourself to ensure it is working, particularly with illegal
inputs.
12
Once you are sure the menu delete book() function is working, and have written comment blocks into the
source code for any extra internal functions you have added to the database2.c program (as described in
the rules for assignments on the Web page), re-name your file according to the following specification and
then submit the code to SurreyLearn.
NOTE 1: The name of the submitted file MUST be proceeded with your surname and initial followed by
the name of the program. For example, if your surname is “Brown”, and your first name is “Peter”, you
need to name the file as follows:
BROWNP-database2.c
The first part is your surname and initial followed by a hyphen, and then followed by the original filename
(database2.c). If you also have middle names, ignore them in the file name. If your files do not
follow this name specification, 10 percent will be deducted from your final mark.
Part 3: Read initial book database from file (25 %)
In the third part of the assignment, you will fill in the function read book database() in database3.c.
This function is called when the program is run with a command line argument, which specifies a file of
books with which to initialize the database.
read book database() should read the database in the same format that menu print database() prints
them, except that it should be able to accept books not in alphabetical order. If any illegal title/author
string or publication year appears in the file (i.e. the file is “corrupted”), then the program should exit with
an error message sent to stderr. Otherwise, the file is read, the database is built, and the menu interface
starts as normal, with the pre-loaded book database.
Compile the modified program with the command
gcc -ansi -Wall database_main.c database1.c database2.c database3.c -o database1
To test your program, the file data can be used as input to the database3 program, to simulate keyboard
input. Once you have adapted your program as above, and compiled it, run the command
./database data > tmp
and then select options “3” and “5” in turn to print the database to standard output and exit. The contents
of the standard output are sent to the file tmp, which should then contain
Title: Altered States
Author: Anita Brookner
Year: 1996
Title: Dispossessed, The
Author: Ursula Le Guin
Year: 1974
Title: Don Quixote
Author: Cervantes
Year: 1605
Title: Feersum Endjinn
13
Author: Iain M. Banks
Year: 1994
Title: Fever Pitch
Author: Nick Hornby
Year: 1992
Title: Frankenstein
Author: Mary Shelley
Year: 1816
Title: Handel’s Operas
Author: W. Dean and J. M. Knapp
Year: 1987
Title: House of Mirth, The
Author: Edith Wharton
Year: 1905
Title: Immortality
Author: Milan Kundera
Year: 1991
Title: Longitude
Author: Dava Sobel
Year: 1996
Title: Original Sin
Author: P. D. James
Year: 1994
Title: Plague, The
Author: Albert Camus
Year: 1946
Title: Right Stuff, The
Author: Tom Wolfe
Year: 1979
Title: Something Happened
Author: Joseph Heller
Year: 1973
Title: Structures
Author: J. E. Gordon
Year: 1978
Title: Suitable Boy, A
Author: Vikram Seth
Year: 1993
Title: Time Machine, The
14
Author: H. G. Wells
Year: 1895
You can then check that your output is correct by comparing it against the file output3
diff -s output3 tmp
You should generate other test files in the same way, to make sure your program is working, particularly to
test its behaviour with illegal inputs.
Once you are sure the read book database() function is working, and have written comment blocks into
the source code for any extra internal functions you have added to the database3.c program (as described
in the rules for assignments on the Web page), re-name your file according to the following specification and
then submit the code to SurreyLearn.
NOTE 1: The name of the submitted file MUST be proceeded with your surname and initial followed by
the name of the program. For example, if your surname is “Brown”, and your first name is “Peter”, you
need to name the file as follows:
BROWNP-database3.c
The first part is your surname and initial followed by a hyphen, and then followed by the original filename
(database3.c). If you also have middle names, ignore them in the file name. If your files do not
follow this name specification, 10 percent will be deducted from your final mark.
If you have implemented all the functions correctly, you will have built a database program that can read
an existing database and modify it under interactive keyboard control.