.Oh and don't use anagram.c it doesn't free mem.
anagram.c (Note the readWord is not my implementation I picked up that little trick from a mate)
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <assert.h>
// Max length of string used to store a word (including the final '\0')
#define MAX_STRING_LENGTH 24
#include "tree.h"
// your structs and typedefs here ...
static int readWord(FILE *input, char *word, int wordBufferSize);
static void sortLetters(char *letters);
int main (int argc, char *argv[]) {
FILE *inputStream;
char *filename;
char data[MAX_STRING_LENGTH];
char sortedData[MAX_STRING_LENGTH];
tree myTree = NULL;
// did they supply the name of a file to read input from?
if (argc >= 2) {
// open it for reading
filename = argv[1];
inputStream = fopen (filename, "r");
// check it exists and was opened ok
assert (inputStream != NULL);
} else {
// otherwise just read from standard input
inputStream = stdin;
}
//////////////////////////
while (readWord(inputStream, data, MAX_STRING_LENGTH) != 0) {
strncpy(sortedData, data, MAX_STRING_LENGTH);
sortLetters(sortedData);
myTree = insertTree(myTree, sortedData, data);
}
printTree(myTree);
///////////////////////////////
fclose(inputStream);
return EXIT_SUCCESS;
}
// Reads up to wordBufferSize-1 letters from stream into word, skipping
// over any leading whitespace. Letters are stored in lowercase.
// A '\0' is added after the last character.
// Function returns the length of the string placed in word. 0 means EOF
// was reached before any letters were read.
int readWord (FILE *input, char *word, int wordBufferSize) {
assert (input != NULL);
assert (wordBufferSize > 0);
int lettersStored;
int character;
// first skip over any leading non-letters (eg whitespace)
character = fgetc (input);
while (!isalpha (character) && (character!=EOF)) {
character = fgetc (input);
}
// now scan in the word,
// note: character currently contains the first letter or EOF
// abort on long words (since storing their leading characters
// as a fragment would be incorrect)
lettersStored = 0;
while (isalpha (character) && (character!=EOF)) {
// before storing character check it fits into buffer,
// after leaving room for terminating '/0' (hence the -1)
assert (lettersStored < (wordBufferSize-1));
word[lettersStored] = tolower (character);
lettersStored++;
character = fgetc (input);
}
// to follow string convention append a terminating '/0'
assert(lettersStored < wordBufferSize);
word[lettersStored] = '\0';
return lettersStored;
}
// Sorts the letters in a string in place.
// uses another sort algorithm, called "insertion sort"
void sortLetters (char *letters) {
int gapPosition;
char valueToInsert;
int length = strlen (letters);
int numberSorted = 1;
// sort letters into place one at a time. starting with the leftmost
while (numberSorted < length) {
valueToInsert = letters[numberSorted];
gapPosition = numberSorted;
// create a gap at the end of the sorted part and shift it left
// until it is in the correct spot for the value we wish to insert
while ((valueToInsert < letters[gapPosition-1]) &&
(gapPosition > 0)) {
// shift the gap one to the left
letters[gapPosition] = letters[gapPosition-1];
gapPosition--;
}
// write the value into the gap, which now in the correct place
letters[gapPosition] = valueToInsert;
numberSorted++;
}
}
Code: Select all
// tree.h
// Author: Ben Wright
// Date: 10th June 2009
// Description: A Simple Tree...
#define MAX_LENGTH 24
#define TRUE 1
#define FALSE 0
typedef struct tree *tree;
// Functions
void printTree(tree root);
tree createTree(void);
void destroyTree(tree toBeDestroyed);
tree insertTree(tree tree, char sortedData[MAX_LENGTH], char originalData[MAX_LENGTH]);
Code: Select all
// tree.h
// Author: Ben Wright
// Date: 10th June 2009
// Description: A Simple Tree...
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include "tree.h"
struct tree {
tree left;
tree middle;
tree right;
char sortedData[MAX_LENGTH];
char originalData[MAX_LENGTH];
};
tree createTree(void) {
tree tree;
tree = malloc(sizeof(struct tree));
assert(tree != NULL); // make sure we haven't run out of memory
tree->left = NULL;
tree->middle = NULL;
tree->right = NULL;
return tree;
}
void destroyTree(tree toBeDestroyed) {
free(toBeDestroyed);
}
tree insertTree(tree myTree, char sortedData[MAX_LENGTH], char originalData[MAX_LENGTH]) {
tree returningNode = myTree;
if (returningNode == NULL) {
returningNode = createTree();
strncpy(returningNode->sortedData, sortedData, MAX_LENGTH);
strncpy(returningNode->originalData, originalData, MAX_LENGTH);
} else if (strncmp(returningNode->sortedData, sortedData, MAX_LENGTH) > 0) {
returningNode->left = insertTree(returningNode->left, sortedData, originalData);
} else if (strncmp(returningNode->sortedData, sortedData, MAX_LENGTH) < 0) {
returningNode->right = insertTree(returningNode->right, sortedData, originalData);
} else {
returningNode->middle = insertTree(returningNode->middle, sortedData, originalData);
}
return returningNode;
}
void printTree(tree root) {
if (root != NULL) {
printTree(root->left);
if (root->middle != NULL) {
// found an anagram
tree nextNode = root;
while (nextNode != NULL) {
printf("%s ", nextNode->originalData);
nextNode = nextNode->middle;
}
printf("\n");
}
printTree(root->right);
}