Elysian Shadows

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);
   }