This is a program in C that is like a previous assignment we did in Java, but now we have to do it in the C language. It involves the use of an ADT system to run this program assignment properly.

Specifically I want a C code of Dictionary.c and DictionaryTest.c. The interface of Dictionary.c embodies the Dictionary.h file (provided below and the exact function and variable names MUST be used otherwise points will be lost). The function of DictionaryTest is for the programmer to periodically test the functions from Dictionary.c while working on it. DictionaryClient.c is just used to run the Dictionary.c file (remains unchanged along with Dictionary.h).

I want this tested and verified. Thank you for your time.

The goal of this assignment is to learn how to implement ADTs in C. We will discuss the typedef and struct commands, header files, information hiding, constructors and destructors, and memory management. You will write a program in C that recreates the Dictionary ADT from pa3 Creating New Data Types in C The struct keyword is used to create a new aggregate data type called a structure or just struct, which is the closest thing C has to Java's class construct. Structs contain data fields, but no methods, unlike Java classes. A struct can also be thought of as a generalization of an array. An array is a contiguous set of memory areas all storing the same type of data, whereas a struct may be composed of different types of data. The general form of a struct declaration is struct structure_tagi // data field declarations Note the semicolon after the closing brace. For example struct person int age; int height; char first [201; char last [20] The above code does not allocate any memory however, and in fact does even not create a complete type called person. The term person is only a tag which can be used with the keyword struct to declare variables of the new type struct person fred; After this declaration fred is a local variable of type struct person, i.e. a symbolic name for an area of stack memory storing a person structure. By comparison, a Java reference variable is a pointer to heap memory. As we shall see, it is possible and desirable to declare C structures from heap memory as well. The variable fred contains four components, which can be accessed via the component selection (dot ".") operator: fred.age27 fred.height70; strcpy (fred.first, "Fredrick"); strcpy (fred.last, "Flintstone") See the man pages or google to learn more about strcpy) in the library string.h. The struct command is most often used in conjunction with typedef, which establishes an alias for an existing data type. The general form of a typedef statement is: typedef existing_type new_type: For instance typedef int feet; defines feet to be an alias for int. We can then declare variables of type feet by doing feet x = 32; Using typedef together with struct allows us to declare variables of the structure type without having to include struct in the declaration. The general form of this combined typedef struct statement is: typedef struct structure_tag /* data field declarations new_type; The structure_tag is only necessary when one of the data fields is itself of the new type, and can otherwise be omitted. Often the tag is included simply as a matter of convention. Also by convention structure_tag and new_ type are the same identifier, since there is no reason for them to differ. Going back to the person example above we have typedef struct personf int age; int height; char first[20 char last [20] person; We can now declare person fred; and assign values to the data fields of fred as before. It is important to remember that the typedef statement itself allocates no memory, only the declaration does. To allocate a person structure from heap memory, we do person* pFredmalloc (sizeof (person)) The variable pFred points to a person structure on the heap. Note that pFred itself is a symbolic name for an area of stack memory storing the address of a block of heap memory storing a person structure. This is essentially the situation one has in Java when declaring a reference variable of some class type. To access the components of the person structure pointed to by pFred, we must first dereference (i.e. follow) the pointer using the indirection (value-at) operator*. Unfortunately the expression pFred.first is not valid since the component selection (dot". ") operator has higher precedence than value-at*. We could insert parentheses to get (*pFred) .first, but this leads to some unwieldy expressions. Fortunately C provides a single operator combining the value-at and dot operators called the indirect component selection (arrow ->) operaton Note this operator is represented by two characters with no separating space. To assign values to the components of the person pointed to by pFred, do pFred->age27 pFred->height 70; strcpy (pFred->first, "Fredrick"); strcpy (pFred->last, "Flintstone" We illustrate with the following C implementation of an IntegerStack based on a linked list. This example has been abridged to save space. The unabridged version is posted on the webpage // IntegerStack.h // Header file for the IntegerStack ADT #ifnde f INTEGER STACK H INCLUDE #define INTEGER STACK H INCLUDE // Stack // Exported reference type typedef struct Stackobj* Stack; // newStack () // constructor for the Stack type Stack newStack (void) // freeStack () // destructor for the Stack type void freeStack (Stack* ps) // prototypes of ADT operations deleted to save space, see webpage // printStack // prints a text representation of S to the file pointed to by out // pre: none void printStack (FILE out, Stack S) endif This file contains some preprocessor commands for conditional compilation that we have not yet seen, namely # ifndef and #endi f. If the C compiler encounters multiple definitions of the same type, or multiple prototypes of any function, it is considered a syntax error. Therefore when a program contains several files, each of which may # include the same header file, it is necessary to place the content of the header file within a conditionally compiled block (sometimes called an "include guard"), so that the prototypes etc. are seen by the compiler only once. The general form of such a block is #Ifndef MACRO NAME #define MACRO NAME statements #endif If MACRO-NAME-s undefined then the statements between #ifndef and #endif are compiled. Otherwise these statements are skipped. The first operation in the block is to #de fine MACRO NAME-Notice that the macro is not defined to be anything, it just needs to be defined. It is customary to choose_MACRO_NAME in such a way that it is unlikely to conflict with any "legitimate" macros. Therefore the name usually begins and ends with an unde score The next item in IntegerStack.h is the typedef command defining Stack to be a pointer to struct Stackobj. The definition of struct Stackobj, which contains the data fields for the IntegerStack ADT, will be placed in the implementation file. Next are prototypes for the constructor newStack ) and destructor freeStack, followed by prototypes of ADT operations (skipped in this document, but given on the class webpage) Finally a prototype is included for a function printStack) corresponding roughly to the toString method in java. An abridged version of the implementation file follows. // IntegerStack. Implementation file for IntegerStack ADT # include # include include # include # include "IntegerStack.h" // private types // Nodeobj typedef struct NodeObj int item; struct Nodeobj* next NodeObj // Node typedef NodeObj* Node // newNode () // constructor of the Node type Node newNode(int x) Node N malloc (sizeof (NodeObj)) assert (N ' =NULL) ; N->item = x; N-nextNULL return (N) // freeNode ) // destructor for the Node type void freeNode (Node pN) ( if ( pN !=NULL && free (pN) pNNULL *pN !=NULL ) { // Stackob typedef struct Stackobj( Node top; int numItems; ) StackObj: // public functions // newStack () // constructor for the Stack type Stack newStack (void) Stack S malloc ( sizeof (Stackobj) ) ; assert (S!-NULL) s->top NULL ; s->num!tems 0; return S; // freeStack () // destructor for the Stack type void freeStack (Stack* ps)[ if ( ps !=NULL if( !isEmpty (*ps)popAll (ps) free (pS); psNULL && *pS!=NULL ) { // definitions of ADT operations deleted to save space, see webpage // printStack // prints a text representation of S to the file pointed to by out // pre: none void printStack (FILE out, Stack s) Node N if ( s-NULL ) { fprintf (stderr, "Stack Error: calling printStack) on NULL Stack referencen") exit (EXIT FAILURE) for (N=S->top; N!=NULL; fprintf (out, "In") N=N->next) fprintf(out, "%d ", N->tem); This implementation file defines several private types, namely NodeObj, Node and Stackobj. Type Node is a pointer to NodeObj, which is the basic building block for a linked list. Type StackObj encapsulates the data fields for a stack. Recall that type Stack was defined in the header file to be a pointer to the structure struct StackObj. Type Stack is the reference through which the client interacts with ADT operations. Memory Management Each of the structure types defined in the above example have their own constructor that allocates heap memory and initializes data fields, as well as a destructor that balances calls to malloc ) and calloc ) in the constructor with corresponding calls to free) Observe that the arguments to freeNode ) and freeStackare not the reference types Node and Stack, but are instead pointers to these types. The reason for this added level of indirection is that the destructor must alter, not just the object a reference points to, but also the reference itself by setting it to NULL. Why must the destructor do this? Recall that maintaining a pointer to a free block on the heap is a serious memory error in C. The responsibility for setting such pointers safely to NULL should lie with the ADT module, not the with client module. To accomplish this, reference types are themselves passed by reference to their destructor As in Java, all ADT operations should check their own preconditions and exit with a useful error massage when one is violated. This message should state the module and function in which the error occurred, and exactly which precondition was violated. The purpose of this message is to provide diagnostic assistance to the designer of the client module. In C however there is one more item to check. Every ADT operation should verify that its reference argument is not NULL. This check should come before the checks of other preconditions since any attempt to dereference a NULL handle will result in a segmentation fault. The reason this was not necessary in Java was because calling an instance method on a null reference variable causes a NullPointerException to be thrown, which provides some automatic error tracking to the client programmer Naming Conventions Suppose you are designing an ADT in C called Blah. Then the header file will be called Blah.h and should define a reference type Blah that points to a structure type BlahObj typedef struct BlahObj* Blah; The header file should also contain prototypes for ADT operations. The implementation file will be called Blah.c and should contain the statement typedef struct BlahObji // data fields for the Blah ADT Blahobj; together with constructors and destructors for the Blahobj structure. File Blah.c will also contain definitions of all public functions (i.e. those with prototypes in Blah.h) as well as definitions of private types and functions. The general form for the constructor and destructor (respectively) are Blah newBlah (arg_list) Blah B malloc (sizeof (Blahobj)); assert ( B!= NULL ); // initialize the fields of the Blah structure return B; and void freeBlah (Blah pB) if ( pB!=NULL // free all heap memory associated with pB free (pB) pB NULL && *pB!=NULL) { Again note that the destructor passes its B1 ah argument by reference, so it can set this pointer to NULL. Given a Blah variable B, a call to freeBlah ) would look like freeBlah (&B) The general form for an ADT operation is return type some op (Blah B, other parameters) if ( B-NULL ) { fprintf (stderr, "Blah Error: some_op o called on NULL Blah referenceIn") exit (EXITFAILURE) // check other preconditions // do whatever some_op ) is supposed to do Most ADTs should also contain aprintBlah ) function that prints a text representation of a Blah object to a file stream. This function is roughly equivalent to the toString ) function in Java. void printBlah (FILE out, Blah B) I if ( B-NULL ) { fprintf (stderr, "Blah Error: printBlah ) called on NULL Blah referenceln") exit (EXITFAILURE) // calls to fprintf (out, text_representation_of_B) What to Turn In Study the unabridged version of the IntegerStack ADT on the webpage. It is recommended that you use it as a starting point for your Dictionary ADT in C. The Dictionary in this assignment is largely the same that in pa3, so re-familiarize yourself with the specifications for that assignment. As before the elements of the Dictionary will be pairs of strings called key and value respectively. Recall however that strings in C are represented by a null O'terminated char array, rather than a built in data type as in Java. The C standard library string.h provides functions for operating on these primitive strings. See documentation for string.h at https://www-s.acm.illinois.edu/webmonke k/c guide/ to learn about these functions, paying special attention to strcmp(), strcpy(), and strlen(). following comprehensive reference is also helpful The anu but also very long (over a thousand pages), so you must search the function names. Function strcmp () is of particular importance in this assignment since it provides a simple way to tell if two strings are equal. Specifically, the expression strcmp (strl, str2) 0 returns true (1) if the char array pointed to by strl is the same sequence as that pointed to by str2, and false (0) otherwise. Use this fact when writing the private function findKey The Node type for the underlying linked list should contain two data fields, each of type char*, representing the two strings key and value. The ADT operations are identical to those in , except of course that certain return types and formal parameters are now char rather than String. One other difference is that you must write a destructor for the Dictionary ADT, where none was necessary in pa3. You will also write a function called printDictionary ( replacing the Java toString ) method. Its output should be formatted to look exactly like that of toString) from pa3. The interface for the Dictionary ADT is embodied in the file Dictionary.h posted on the webpage. A test client called DictionaryClient.c is also included. Submit both of these files unaltered with your project. The webpage also contains a Makefile for the Stack ADT. Alter this Makefile to make the executable DictionaryClient from the source DictionaryClient.c. (This can be done by defining the variable ADT_NAME to be Dictionary instead of IntegerStack.) Compare the output of DictionaryClient with the file DictionaryClientOut. Note that this test client and its output are provided as a convenience to you and should not be deemed to certify your Dictionary.c as error free. For that you will need to construct your own tests in a file called DictionaryTest.c which you will also submit. Note that the Makefile provided includes clean and check utilities which you should leave in place. Do make clean to delete old binaries and make check to check your Dictionary.c for memory leaks. 8 Submit the files: README Makefile Dictionary.c DictionaryTest.c Dictionary.h DictionaryClient.c written by you provided but altered by you written by you written by you provided provided to the assignment name lab5. As always start early and ask for help if anything is not completely clear. // Dictionary.h // Header file for the Dictionary ADT #ifndef DICTIONARY H INCLUDE #define DICTIONARYHINCLUDE - - - /1 Dictionary // Exported reference type typedef struct Dictionaryobj* Dictionary // newDictionary) Iconstructor for the Dictionary type Dictionary newDictionary (void); // freeDictionary() // destructor for the Dictionary type void freeDictionary (Dictionary* pD); // isEmpty() // returns 1 (true) if S is empty, 0 (false) otherwise /7 pre: none int isEmpty(Dictionary D) // size( // returns the number of (key, value) pairs in D // pre: none int size(Dictionary D) /1 lookup() /I returns the value v such that (k, v) is in D, or returns NULL if no // such value v exists /7 pre: none char* lookup(Dictionary D, char* k); insert) // inserts new (key,value) pair into D // pre: lookup (D, k) NULL void insert (Dictionary D, char* k, char* v); // delete() // deletes pair with the key k // pre: lookup (D, k)!-NULL void delete(Dictionary D, char* k); // makeEmpty) // re-sets D to the empty state. // pre: none void makeEmpty (Dictionary D) // printDictionary() // pre: none // prints a text representation of D to the file pointed to by out void printDictionary (FILE* out, Dictionary D) #endif // DictionaryClient.c // Test client for the Dictionary ADT #include #include #includestring . h> #1nclude "Dictionary" h" #define MAX LEN 180 int main(int argc, char*argv]) Dictionary AnewDictionary() char* k; char* v; char* word1 "one", "two", "three", "four", "five", "six", "seven" char* word2 "foo", "bar", "blah", "galumph", "happy","sad", "blue"; int i; for(1-0 ; i) operaton Note this operator is represented by two characters with no separating space. To assign values to the components of the person pointed to by pFred, do pFred->age27 pFred->height 70; strcpy (pFred->first, "Fredrick"); strcpy (pFred->last, "Flintstone" We illustrate with the following C implementation of an IntegerStack based on a linked list. This example has been abridged to save space. The unabridged version is posted on the webpage // IntegerStack.h // Header file for the IntegerStack ADT #ifnde f INTEGER STACK H INCLUDE #define INTEGER STACK H INCLUDE // Stack // Exported reference type typedef struct Stackobj* Stack; // newStack () // constructor for the Stack type Stack newStack (void) // freeStack () // destructor for the Stack type void freeStack (Stack* ps) // prototypes of ADT operations deleted to save space, see webpage // printStack // prints a text representation of S to the file pointed to by out // pre: none void printStack (FILE out, Stack S) endif This file contains some preprocessor commands for conditional compilation that we have not yet seen, namely # ifndef and #endi f. If the C compiler encounters multiple definitions of the same type, or multiple prototypes of any function, it is considered a syntax error. Therefore when a program contains several files, each of which may # include the same header file, it is necessary to place the content of the header file within a conditionally compiled block (sometimes called an "include guard"), so that the prototypes etc. are seen by the compiler only once. The general form of such a block is #Ifndef MACRO NAME #define MACRO NAME statements #endif If MACRO-NAME-s undefined then the statements between #ifndef and #endif are compiled. Otherwise these statements are skipped. The first operation in the block is to #de fine MACRO NAME-Notice that the macro is not defined to be anything, it just needs to be defined. It is customary to choose_MACRO_NAME in such a way that it is unlikely to conflict with any "legitimate" macros. Therefore the name usually begins and ends with an unde score The next item in IntegerStack.h is the typedef command defining Stack to be a pointer to struct Stackobj. The definition of struct Stackobj, which contains the data fields for the IntegerStack ADT, will be placed in the implementation file. Next are prototypes for the constructor newStack ) and destructor freeStack, followed by prototypes of ADT operations (skipped in this document, but given on the class webpage) Finally a prototype is included for a function printStack) corresponding roughly to the toString method in java. An abridged version of the implementation file follows. // IntegerStack. Implementation file for IntegerStack ADT # include # include include # include # include "IntegerStack.h" // private types // Nodeobj typedef struct NodeObj int item; struct Nodeobj* next NodeObj // Node typedef NodeObj* Node // newNode () // constructor of the Node type Node newNode(int x) Node N malloc (sizeof (NodeObj)) assert (N ' =NULL) ; N->item = x; N-nextNULL return (N) // freeNode ) // destructor for the Node type void freeNode (Node pN) ( if ( pN !=NULL && free (pN) pNNULL *pN !=NULL ) { // Stackob typedef struct Stackobj( Node top; int numItems; ) StackObj: // public functions // newStack () // constructor for the Stack type Stack newStack (void) Stack S malloc ( sizeof (Stackobj) ) ; assert (S!-NULL) s->top NULL ; s->num!tems 0; return S; // freeStack () // destructor for the Stack type void freeStack (Stack* ps)[ if ( ps !=NULL if( !isEmpty (*ps)popAll (ps) free (pS); psNULL && *pS!=NULL ) { // definitions of ADT operations deleted to save space, see webpage // printStack // prints a text representation of S to the file pointed to by out // pre: none void printStack (FILE out, Stack s) Node N if ( s-NULL ) { fprintf (stderr, "Stack Error: calling printStack) on NULL Stack referencen") exit (EXIT FAILURE) for (N=S->top; N!=NULL; fprintf (out, "In") N=N->next) fprintf(out, "%d ", N->tem); This implementation file defines several private types, namely NodeObj, Node and Stackobj. Type Node is a pointer to NodeObj, which is the basic building block for a linked list. Type StackObj encapsulates the data fields for a stack. Recall that type Stack was defined in the header file to be a pointer to the structure struct StackObj. Type Stack is the reference through which the client interacts with ADT operations. Memory Management Each of the structure types defined in the above example have their own constructor that allocates heap memory and initializes data fields, as well as a destructor that balances calls to malloc ) and calloc ) in the constructor with corresponding calls to free) Observe that the arguments to freeNode ) and freeStackare not the reference types Node and Stack, but are instead pointers to these types. The reason for this added level of indirection is that the destructor must alter, not just the object a reference points to, but also the reference itself by setting it to NULL. Why must the destructor do this? Recall that maintaining a pointer to a free block on the heap is a serious memory error in C. The responsibility for setting such pointers safely to NULL should lie with the ADT module, not the with client module. To accomplish this, reference types are themselves passed by reference to their destructor As in Java, all ADT operations should check their own preconditions and exit with a useful error massage when one is violated. This message should state the module and function in which the error occurred, and exactly which precondition was violated. The purpose of this message is to provide diagnostic assistance to the designer of the client module. In C however there is one more item to check. Every ADT operation should verify that its reference argument is not NULL. This check should come before the checks of other preconditions since any attempt to dereference a NULL handle will result in a segmentation fault. The reason this was not necessary in Java was because calling an instance method on a null reference variable causes a NullPointerException to be thrown, which provides some automatic error tracking to the client programmer Naming Conventions Suppose you are designing an ADT in C called Blah. Then the header file will be called Blah.h and should define a reference type Blah that points to a structure type BlahObj typedef struct BlahObj* Blah; The header file should also contain prototypes for ADT operations. The implementation file will be called Blah.c and should contain the statement typedef struct BlahObji // data fields for the Blah ADT Blahobj; together with constructors and destructors for the Blahobj structure. File Blah.c will also contain definitions of all public functions (i.e. those with prototypes in Blah.h) as well as definitions of private types and functions. The general form for the constructor and destructor (respectively) are Blah newBlah (arg_list) Blah B malloc (sizeof (Blahobj)); assert ( B!= NULL ); // initialize the fields of the Blah structure return B; and void freeBlah (Blah pB) if ( pB!=NULL // free all heap memory associated with pB free (pB) pB NULL && *pB!=NULL) { Again note that the destructor passes its B1 ah argument by reference, so it can set this pointer to NULL. Given a Blah variable B, a call to freeBlah ) would look like freeBlah (&B) The general form for an ADT operation is return type some op (Blah B, other parameters) if ( B-NULL ) { fprintf (stderr, "Blah Error: some_op o called on NULL Blah referenceIn") exit (EXITFAILURE) // check other preconditions // do whatever some_op ) is supposed to do Most ADTs should also contain aprintBlah ) function that prints a text representation of a Blah object to a file stream. This function is roughly equivalent to the toString ) function in Java. void printBlah (FILE out, Blah B) I if ( B-NULL ) { fprintf (stderr, "Blah Error: printBlah ) called on NULL Blah referenceln") exit (EXITFAILURE) // calls to fprintf (out, text_representation_of_B) What to Turn In Study the unabridged version of the IntegerStack ADT on the webpage. It is recommended that you use it as a starting point for your Dictionary ADT in C. The Dictionary in this assignment is largely the same that in pa3, so re-familiarize yourself with the specifications for that assignment. As before the elements of the Dictionary will be pairs of strings called key and value respectively. Recall however that strings in C are represented by a null O'terminated char array, rather than a built in data type as in Java. The C standard library string.h provides functions for operating on these primitive strings. See documentation for string.h at https://www-s.acm.illinois.edu/webmonke k/c guide/ to learn about these functions, paying special attention to strcmp(), strcpy(), and strlen(). following comprehensive reference is also helpful The anu but also very long (over a thousand pages), so you must search the function names. Function strcmp () is of particular importance in this assignment since it provides a simple way to tell if two strings are equal. Specifically, the expression strcmp (strl, str2) 0 returns true (1) if the char array pointed to by strl is the same sequence as that pointed to by str2, and false (0) otherwise. Use this fact when writing the private function findKey The Node type for the underlying linked list should contain two data fields, each of type char*, representing the two strings key and value. The ADT operations are identical to those in , except of course that certain return types and formal parameters are now char rather than String. One other difference is that you must write a destructor for the Dictionary ADT, where none was necessary in pa3. You will also write a function called printDictionary ( replacing the Java toString ) method. Its output should be formatted to look exactly like that of toString) from pa3. The interface for the Dictionary ADT is embodied in the file Dictionary.h posted on the webpage. A test client called DictionaryClient.c is also included. Submit both of these files unaltered with your project. The webpage also contains a Makefile for the Stack ADT. Alter this Makefile to make the executable DictionaryClient from the source DictionaryClient.c. (This can be done by defining the variable ADT_NAME to be Dictionary instead of IntegerStack.) Compare the output of DictionaryClient with the file DictionaryClientOut. Note that this test client and its output are provided as a convenience to you and should not be deemed to certify your Dictionary.c as error free. For that you will need to construct your own tests in a file called DictionaryTest.c which you will also submit. Note that the Makefile provided includes clean and check utilities which you should leave in place. Do make clean to delete old binaries and make check to check your Dictionary.c for memory leaks. 8 Submit the files: README Makefile Dictionary.c DictionaryTest.c Dictionary.h DictionaryClient.c written by you provided but altered by you written by you written by you provided provided to the assignment name lab5. As always start early and ask for help if anything is not completely clear. // Dictionary.h // Header file for the Dictionary ADT #ifndef DICTIONARY H INCLUDE #define DICTIONARYHINCLUDE - - - /1 Dictionary // Exported reference type typedef struct Dictionaryobj* Dictionary // newDictionary) Iconstructor for the Dictionary type Dictionary newDictionary (void); // freeDictionary() // destructor for the Dictionary type void freeDictionary (Dictionary* pD); // isEmpty() // returns 1 (true) if S is empty, 0 (false) otherwise /7 pre: none int isEmpty(Dictionary D) // size( // returns the number of (key, value) pairs in D // pre: none int size(Dictionary D) /1 lookup() /I returns the value v such that (k, v) is in D, or returns NULL if no // such value v exists /7 pre: none char* lookup(Dictionary D, char* k); insert) // inserts new (key,value) pair into D // pre: lookup (D, k) NULL void insert (Dictionary D, char* k, char* v); // delete() // deletes pair with the key k // pre: lookup (D, k)!-NULL void delete(Dictionary D, char* k); // makeEmpty) // re-sets D to the empty state. // pre: none void makeEmpty (Dictionary D) // printDictionary() // pre: none // prints a text representation of D to the file pointed to by out void printDictionary (FILE* out, Dictionary D) #endif // DictionaryClient.c // Test client for the Dictionary ADT #include #include #includestring . h> #1nclude "Dictionary" h" #define MAX LEN 180 int main(int argc, char*argv]) Dictionary AnewDictionary() char* k; char* v; char* word1 "one", "two", "three", "four", "five", "six", "seven" char* word2 "foo", "bar", "blah", "galumph", "happy","sad", "blue"; int i; for(1-0 ; i