C2A7E1_main-Sample

/ // Leaving the following macro defined enables the binary tree code. Commenting // it out enables the hash table code. Completely remove this macro and all // references to it in the program you produce. // #define TREE

#include #include #include

#define LINE_LEN 256 // size of input buffer #define BUFFMT "%255" // field width for input buffer scan

void *SafeMalloc(size_t size) { void *vp;

if ((vp = malloc(size)) == NULL) { fputs("Out of memory ", stderr); exit(EXIT_FAILURE); } return(vp); }

FILE *OpenFile(const char *fileName) { FILE *fp;

if ((fp = fopen(fileName, "r")) == NULL) { fprintf(stderr, "File \"%s\" didn't open. ", fileName); perror(fileName); exit(EXIT_FAILURE); } return fp; }

#ifdef TREE /*************************************************************************** (Binary Trees) ***************************************************************************/

#define MIN_ARGS 2 // fewest command line arguments #define FILE_ARG_IX 1 // index of file name argument

typedef struct Node NODE; struct Node { char *strng; // points to string this node represents size_t count; // number of occurrences of this string NODE *left, *right; // pointers to left and right children };

// // BuildTree will search the binary tree at pNode for a node representing the // string in str. If found, its string count will be incremented. If not // found, a new node for that string will be created, put in alphabetical order, // and its count set to 1. A pointer to the node for string str is returned. // NODE *BuildTree(NODE *pNode, char *str) { if (pNode == NULL) // string not found { size_t length = strlen(str) + 1; // length of string

pNode = SafeMalloc(sizeof(NODE)); // allocate a node pNode->strng = SafeMalloc(length); memcpy(pNode->strng, str, length); // copy string pNode->count = 1; // 1st occurrence pNode->left = pNode->right = NULL; // no subtrees } else { int result = strcmp(str, pNode->strng); // compare strings

if (result == 0) // new string == current ++pNode->count; // increment occurrence else if (result left = BuildTree(pNode->left, str); // traverse left else // new string > current pNode->right = BuildTree(pNode->right, str); // traverse right } return(pNode); }

// PrintTree recursively prints the binary tree in pNode alphabetically. void PrintTree(const NODE *pNode) { if (pNode != NULL) // if child exists { PrintTree(pNode->left); // traverse left printf("%4zu %s ", pNode->count, pNode->strng); PrintTree(pNode->right); // traverse right } }

// FreeTree recursively frees the binary tree in pNode. void FreeTree(NODE *pNode) { if (pNode != NULL) // if child exists { FreeTree(pNode->left); // traverse left FreeTree(pNode->right); // traverse right free(pNode->strng); // free the string free(pNode); // free the node } }

int main(int argc, char *argv[]) { char buf[LINE_LEN]; // word string buffer char fileName[LINE_LEN]; // file name buffer NODE *root; // pointer to root node FILE *fp;

// Read file name from command line. if (argc

fp = OpenFile(fileName);

// // The following loop will read one string at a time from stdin until EOF is // reached. For each string read the BuildTree function will be called to // update the tree. // for (root = NULL; fscanf(fp, BUFFMT "s", buf) != EOF; root = BuildTree(root, buf)) ; fclose(fp); PrintTree(root); FreeTree(root); return(EXIT_SUCCESS); }

#else /*************************************************************************** (Hashing) ***************************************************************************/

#define MIN_ARGS 3 // fewest command line arguments #define FILE_ARG_IX 1 // index of file name argument #define BINS_ARG_IX 2 // index of bin count argument

typedef struct Node NODE; struct Node // type of each list node { char *strng; // string for this node size_t count; // occurrences of this string NODE *next; // next node in list };

typedef struct // type of table array elements { size_t nodes; // # of list nodes for this bin NODE *firstNode; // 1st node in this bin's list } BIN;

typedef struct // type of hash table descriptor { size_t bins; // bins in hash table BIN *firstBin; // first bin } TABLE;

int HashFunction(const char *key, size_t bins) // get bin value from key { return((int)(strlen(key) % bins)); // value is length % bins }

// CreateTable creates and initializes the hash table and its bins TABLE *CreateTable(size_t bins) { TABLE *hashTable; BIN *bin, *end;

hashTable = SafeMalloc(sizeof(TABLE)); // alloc desc struct hashTable->bins = bins; // how many bins // alloc bins hashTable->firstBin = SafeMalloc(bins * sizeof(BIN)); end = hashTable->firstBin + bins; // end of bins

for (bin = hashTable->firstBin; bin nodes = 0; // no list nodes bin->firstNode = NULL; // no list } return(hashTable); }

// // BuildList searches bin bp of the list for a node representing the string in // str. If found, its string count will be incremented. If not found, a new // node for that string will be created, put at the top of the list, and its // string count set to 1. // void BuildList(BIN *bp, const char *str) { NODE *pNode = bp->firstNode; // first node in list

for (; pNode != NULL; pNode = pNode->next) // visit each node if (!strcmp(pNode->strng, str)) // if strings match... break; // ...quit looking if (pNode == NULL) // no matching node { size_t length = strlen(str) + 1; // characters in string

pNode = SafeMalloc(sizeof(NODE)); // allocate new node pNode->strng = SafeMalloc(length); // storage for string memcpy(pNode->strng, str, length); // store string pNode->count = 1; // set string count pNode->next = bp->firstNode; // insert new node... bp->firstNode = pNode; // ...first in list ++bp->nodes; // update node count } else // found matching node ++pNode->count; // increment string count }

// PrintTable prints the hash table. void PrintTable(const TABLE *hashTable) { BIN *bin, *end;

end = hashTable->firstBin + hashTable->bins; // end of bins for (bin = hashTable->firstBin; bin nodes, (int)(bin - hashTable->firstBin)); // Visit nodes for (node = bin->firstNode; node != NULL; node = node->next) printf("%4zu %s ", node->count, node->strng); } }

// FreeTable frees the hash table. void FreeTable(TABLE *hashTable) { BIN *bin, *end;

end = hashTable->firstBin + hashTable->bins; // end of bins for (bin = hashTable->firstBin; bin firstNode; node != NULL;) // visit nodes { NODE *pNode = node; // save NODE pointer node = node->next; // point to next node free(pNode->strng); // free the string free(pNode); // free the node } } free(hashTable->firstBin); // free all bins free(hashTable); // free table descriptor }

int main(int argc, char *argv[]) { char buf[LINE_LEN]; // word string buffer char fileName[LINE_LEN]; // file name buffer int howManyBins; // bins to create TABLE *hashTable; // pointer to hash table FILE *fp;

// Read file name from command line. if (argc

// Read bin count from command line. if (sscanf(argv[BINS_ARG_IX], "%d", &howManyBins) != 1) { fprintf(stderr, "No bin count specified on command line "); return EXIT_FAILURE; } hashTable = CreateTable((size_t)howManyBins); // allocate table array

// // The following loop will read one string at a time from stdin until EOF is // reached. For each string read the BuildList function will be called to // update the hash table. // while (fscanf(fp, BUFFMT "s", buf) != EOF) // get string from file { // Find appropriate bin. BIN *bin = &hashTable->firstBin[HashFunction(buf, (size_t)howManyBins)]; BuildList(bin, buf); // put string in list } fclose(fp); PrintTable(hashTable); // print all strings FreeTable(hashTable); // free the table return(EXIT_SUCCESS); }

#endif

1. Verify that the "binary tree" portion of the code works by ensuring that macro TREE is defined then compiling and running the program, noting that the desired input file name must be specified on the command line. Instructor-supplied data file TestFile1.txt, which must be placed in the program's "working directory", has been provided for this purpose. 2. Verify that the "hashing" portion of the code works by commenting out the definition of macro TREE then compiling and running the program, noting that in addition to the desired input file name the desired number of bins must be specified after it as an additional command line argument. Test with the same input file as above and a bin count of 10, as well as with any other desired text files and bin counts. 3. Combine, modify, add to, and delete the supplied code in any way you deem necessary so that it will perform the same "hashing" operation as before, but will store the words in ordered binary trees like those in the "binary tree" portion of the code instead of in singly linked lists. Significant credit will be deducted for unused code that is not deleted from your file. To permit automated testing the following things must not be changed: a. The input file name and bin count must still come from the command line. b. The display format (spacing. field width, etc.) must be the same as in the original "hashing" version. c. As in the original "hashing" version, the order of dynamic allocation must remain as follows. There must be no dynamic allocations other than these: 1) Allocate memory for a "Table Descriptor" (just once): 2) Allocate memory for an empty "Hash Table" (just once); 3) If and only if a word is encountered that is not already in the table, allocate memory for a new node first, then memory for its data (the string). 4. As is always the case, do not use external variables in this or any other C exercise land do not use non-const external variables in any C++ exercise). If your code is working properly the display it produces will be identical to that of the original "hashing" version except for the order of the words in each bin, which will now be in the order dictated by the standard library strcmp function. That is, for data file TestFile1.txi and a bin count of 10 the display will start exactly as follows: 6 entries for bin 0 : 1 arguments. 1 constants. expansion) invocation occurrence parameters 6 entries for bin 1: 6 a 1 combination 1 definition, 1 definition. 1 number-sign 1 stringizing