I've decided to just go ahead and post all the code I've written since I'm getting no where on my own. I've re-written these functions multiple times now and I either end up making things worse or getting right back to where I was when I started.
Here's my driver program...
Code:
#define CRTDBG_MAP_ALLOC
#include <stdio.h> /* printf, NULL */
#include <string.h> /* strcmp, strlen */
#include <crtdbg.h>
#include "Words.h"
int CompareLengths(const char *word1, const char *word2)
{
return (int)(strlen(word1) - strlen(word2));
}
void SimpleWordTest1(void)
{
unsigned i;
unsigned count;
WordNode *node;
char *word, *oldword, *newword;
WordNode *words1 = NULL;
char *text[] = {"two", "two", "three", "two", "four",
"an", "computer", "fiver", "two", "four"};
printf("\n***** SimpleWordTest1 *****\n");
for (i = 0; i < sizeof(text) / sizeof(*text); i++)
add_word(&words1, text[i]);
print_words(words1);
add_word(&words1, "red");
add_word(&words1, "green");
add_word(&words1, "blue");
print_words(words1);
word = "computer";
node = find_word(words1, word);
if (node)
printf("Found the word: '%s'\n", node->word);
else
printf("Did not find the word: '%s'\n", word);
word = "DigiPen";
node = find_word(words1, word);
if (node)
printf("Found the word: '%s'\n", node->word);
else
printf("Did not find the word: '%s'\n", word);
oldword = "two";
newword = "2";
printf("Replacing %s with %s:\n", oldword, newword);
replace_words(words1, oldword, newword);
print_words(words1);
word = "2";
count = count_matching_words(words1, word);
printf("The word '%s' appears %u time(s) in the list.\n", word, count);
printf("Deleting all occurrences of the word '%s':\n", word);
delete_word(&words1, word);
print_words(words1);
word = "digipen";
printf("Deleting all occurrences of the word '%s':\n", word);
delete_word(&words1, word);
print_words(words1);
printf("Printing words in reverse:\n");
print_words_reverse(words1);
free_words(words1);
}
void SimpleWordTest2(void)
{
unsigned i;
WordNode *words1 = NULL;
WordNode *words2 = NULL;
char *text[] = {"computer", "languages", "three", "four",
"an", "DigiPen", "123", "Quotas"};
printf("\n***** SimpleWordTest2 *****\n");
for (i = 0; i < sizeof(text) / sizeof(*text); i++)
{
insert_word(&words1, text[i], strcmp);
insert_word(&words2, text[i], CompareLengths);
}
printf("Ordered lexicographically:\n");
print_words(words1);
printf("Ordered by length:\n");
print_words(words2);
free_words(words1);
free_words(words2);
}
void SimpleLineTest1(void)
{
unsigned count;
WordNode *words1 = NULL;
WordNode *words2 = NULL;
WordNode *words3 = NULL;
LineNode *lines = NULL;
LineNode *ltemp;
char *word, *oldword, *newword;
// char *text[] = {"digipen", "two", "three", "two", "four",
// "an", "computer", "fiver", "two", "four"};
char *text[] = {"two", "two", "three", "two", "four",
"an", "computer", "fiver", "two", "two"};
unsigned i;
printf("\n***** SimpleLineTest1 *****\n");
for (i = 0; i < sizeof(text) / sizeof(*text); i++)
{
add_word(&words1, text[i]);
insert_word(&words2, text[i], strcmp);
insert_word(&words3, text[i], CompareLengths);
}
add_word(&words1, "red");
add_word(&words2, "green");
add_word(&words3, "blue");
print_words(words1);
print_words(words2);
print_words(words3);
add_line(&lines, words1);
add_line(&lines, words2);
add_line(&lines, words3);
print_lines(lines);
word = "blue";
ltemp = find_line(lines, word);
if (ltemp)
{
printf("Found '%s' in this line:\n", word);
print_words(ltemp->words);
}
else
printf("Could not find '%s' in any line.\n", word);
word = "yellow";
ltemp = find_line(lines, word);
if (ltemp)
{
printf("Found '%s' in this line:\n", word);
print_words(ltemp->words);
}
else
printf("Could not find '%s' in any line.\n", word);
oldword = "two";
newword = "technology";
printf("Replacing %s with %s\n", oldword, newword);
replace_words2(lines, oldword, newword);
print_lines(lines);
word = "technology";
count = count_matching_words2(lines, word);
printf("The word '%s' occurs %u time(s) in the list\n", word, count);
word = "DigiPen";
count = count_matching_words2(lines, word);
printf("The word '%s' occurs %u time(s) in the list\n", word, count);
printf("\nDeleting words\n");
delete_word2(lines, "technology");
delete_word2(lines, "digipen");
delete_word2(lines, "blue");
print_lines(lines);
printf("\nDeleting words\n");
delete_word2(lines, "computer");
delete_word2(lines, "three");
delete_word2(lines, "four");
delete_word2(lines, "fiver");
delete_word2(lines, "an");
print_lines(lines);
printf("\nDeleting words\n");
delete_word2(lines, "red");
print_lines(lines);
free_lines(lines);
}
int main(void)
{
SimpleWordTest1();
//SimpleWordTest2();
//SimpleLineTest1();
_CrtSetReportMode(_CRT_WARN,_CRTDBG_MODE_WNDW);
_CrtDumpMemoryLeaks();
return 0;
}
and my words.c
Code:
#include <stdio.h> /* printf, NULL */
#include <malloc.h> /* malloc(), free() */
#include <string.h> /* strlen(), strcpy(), strcmp() */
#include "Words.h"
#define ERROR -1
void print_words(WordNode *list)
{
/* Loop until we hit the end. If the user passes in a NULL pointer, */
/* this code will handle it correctly. */
while (list)
{
printf("%s ", list->word);
list = list->next;
}
printf("\n");
}
void print_lines(LineNode *list)
{
unsigned count = 0;
/* Loop until we hit the end. If the user passes in a NULL pointer, */
/* this code will handle it correctly. */
while (list)
{
count++;
printf("Line %2u: ", count); /* Format each line with a number */
print_words(list->words); /* Prints the actual words */
list = list->next;
}
}
void print_words_reverse(WordNode *list)
{
/* if list passed in is not NULL print words in reverse */
if(list != NULL)
{
/* Loop until we hit the end so that we start printing from last node */
while(list->next)
list = list->next;
/* prints out the words in reverse order until hitting a NULL pointer. */
while(list)
{
printf("%s ", list->word);
list = list->prev;
}
}
printf("\n");
}
int add_word(WordNode **words, const char *word)
{
/* Initilizing the new node */
struct WordNode *pNode;
/* Allocating a new node */
pNode = (struct WordNode *) malloc(sizeof(struct WordNode));
/* If malloc failed return an error */
if(pNode == NULL)
return ERROR;
/* malloc the size of the word we're putting in */
pNode->word = (char *)malloc(strlen(word) + 1);
/* if malloc failed on strlen */
if(pNode->word == NULL)
{
/* free created node */
free(pNode);
return ERROR;
}
strcpy(pNode->word, word); /* copy the word to the node */
pNode->next = NULL; /* Initialize next and prev (none yet) */
pNode->prev = NULL;
/* If the list is NULL (empty), this is the first
node we are adding to the list. */
if ((*words) == NULL)
(*words) = pNode;
else
{
/* Find the end of the list */
struct WordNode *temp = (*words);
while (temp->next)
temp = temp->next;
temp->next = pNode; /* Put new node at the end */
pNode->prev = temp; /* point pNode at the previous */
}
return 0;
}
void delete_word(WordNode **words, const char *word)
{
/* finding if any occurances of the word exist */
WordNode *temp = find_word(*words, word);
/* while occurances are found */
while(temp)
{
/* create temporary nodes*/
WordNode *prev = temp->prev;
WordNode *next = temp->next;
/* if node is the first there will be no previous node */
if(prev != NULL)
prev->next = next; /* pointing previous node at new next node */
else
(*words) = next; /* if word occured in first node making
words now point to new first node*/
/* if word occured in last node there will be no next */
if(next != NULL)
next->prev = prev; /* pointing next node at new previous node */
/* getting rid of node with occurance of word*/
free(temp->word);
free(temp);
/* if there is no next node exit the function*/
if(next != NULL)
temp = find_word(*words, word);
else
return;
}
}
unsigned count_matching_words(WordNode *words, const char *word)
{
WordNode *temp = find_word(words, word);
unsigned count = 0;
/* while finding an occurance of the word */
while(temp)
{
count++; /* increase count */
temp = find_word(temp->next, word); /* find next occurance starting from next node*/
}
return count;
}
WordNode *find_word(WordNode *words, const char *word)
{
WordNode *temp = words;
/* while there are words left to check loop */
while(temp)
{
/* if word is one we're looking for return the pointer to the node */
if(strcmp(temp->word, word) == 0)
return temp;
/* otherwise go to the next word */
temp = temp->next;
}
temp = words;
/* if word not found return a NULL pointer */
return NULL;
}
int replace_words(WordNode *words, const char *oldword, const char *newword)
{
int rVal = 0;
WordNode *temp = find_word(words, oldword);
/* while find_words finds occurances of oldword */
while(temp)
{
/* setting up temporary nodes */
WordNode *prev = temp->prev;
WordNode *next = temp->next;
/* setting the previous nodes next pointer to NULL so that we can
add a word after it with the add_word function */
if(prev)
prev->next = NULL;
rVal = add_word(&prev, newword);
/* if add_word was unable to allocate enough memory return in a fail state */
if(rVal != 0)
{
prev->next = temp;
return ERROR;
}
/* disconnecting temp from main list */
temp->next = NULL;
temp->prev = NULL;
/* deleting the old node */
delete_word(&temp, oldword);
/* connecting new nodes together */
if(prev->next)
{
prev->next->next = next;
next->prev = prev->next;
}
else /* if prev will start the list */
{
prev->next = next;
next->prev = prev;
words = prev;
}
/* seeing if any more occurances of oldword exist */
temp = find_word(words, oldword);
} /* end while(temp) */
return 0;
}
void free_words(WordNode *words)
{
while(words)
{
delete_word(&words, words->word);
}
}
int insert_word(WordNode **words, const char *word, CompFn comp)
{
struct WordNode *pNode = (struct WordNode *) malloc(sizeof(struct WordNode));
/* if error in malloc() */
if( pNode == NULL )
return ERROR;
/* initilize pointers and allocate memory for word */
pNode->next = pNode->prev = NULL;
pNode->word = (char *)malloc(strlen(word) + 1);
/* if malloc() failed return that there was an error */
if(pNode->word == NULL)
{
free(pNode);
return ERROR;
}
/* copy the word over to pNode */
strcpy(pNode->word, word);
/* if the list does not exist yet pNode will become the first member */
if(!(*words))
*words = pNode;
else
{
WordNode *temp = (*words), *prev;
/* while we're not at the end of the list and we haven't found where
pNode is supposed to go */
while(temp && comp(temp->word, pNode->word) < 0)
{
prev = temp;
temp = temp->next;
}
/* if pNode should be the new start of the list */
if(temp == (*words))
(*words) = pNode;
else
{
prev->next = pNode;
pNode->prev = prev;
}
pNode->next = temp;
/* if pNode was not placed at the end of the list */
if(temp)
temp->prev = pNode;
}
return 0;
}
int add_line(LineNode **lines, WordNode *words)
{
LineNode *pNode, *temp = *lines;
/* Allocating a new LineNode structure */
pNode = (struct LineNode *) malloc(sizeof(struct LineNode));
if(!pNode)
return ERROR;
/* initilizing the new LineNode structure */
pNode->words = words;
pNode->next = NULL;
/* if no LineNodes are present pNode becomes the first node */
if(!(*lines))
{
(*lines) = pNode;
}
else
{
/* while we're not at the last LineNode */
while(temp->next)
{
temp = temp->next;
}
temp->next = pNode;
}
return 0;
}
LineNode *find_line(LineNode *lines, const char *word)
{
LineNode *temp = lines;
/* while there's still lines to check */
while(temp)
{
/* if word found in given line return the line it was found in */
if(find_word(temp->words, word))
return temp;
temp = temp->next;
}
return NULL;
}
int replace_words2(LineNode *lines, const char *oldword, const char *newword)
{
LineNode *temp = lines;
while(temp)
{
/* if replace_words returns an error return an error to the original
caller */
if(replace_words(temp->words, oldword, newword) == ERROR)
return ERROR;
temp = temp->next;
}
return 0;
}
unsigned count_matching_words2(LineNode *lines, const char *word)
{
unsigned count = 0;
LineNode *temp = lines;
/* while there's still more lines to check */
while(temp)
{
/* increase count with the ammount of new words found */
count += count_matching_words(temp->words, word);
temp = temp->next;
}
return count;
}
void delete_word2(LineNode *lines, const char *word)
{
LineNode *temp = lines;
while(temp)
{
delete_word(&temp->words, word);
temp = temp->next;
}
}
void free_lines(LineNode *lines)
{
while(lines)
{
LineNode *temp = lines->next;
free_words(lines->words);
free(lines);
lines = temp;
}
}
and my words.h
Code:
/*---------------------------------------------------------------------------*/
#ifndef WORDS_H
#define WORDS_H
/*---------------------------------------------------------------------------*/
struct WordNode
{
char *word;
struct WordNode *next;
struct WordNode *prev;
};
struct LineNode
{
struct WordNode *words;
struct LineNode *next;
};
typedef struct WordNode WordNode;
typedef struct LineNode LineNode;
typedef int (*CompFn)(const char *, const char *);
void print_words(WordNode *list);
void print_lines(LineNode *list);
void print_words_reverse(WordNode *list);
/* Word related functions */
int add_word(WordNode **words, const char *word);
void delete_word(WordNode **words, const char *word);
unsigned count_matching_words(WordNode *words, const char *word);
WordNode *find_word(WordNode *words, const char *word);
int replace_words(WordNode *words, const char *oldword, const char *newword);
void free_words(WordNode *words);
int insert_word(WordNode **words, const char *word, CompFn comp);
/* Line related functions */
int add_line(LineNode **lines, WordNode *words);
void delete_word2(LineNode *lines, const char *word);
unsigned count_matching_words2(LineNode *lines, const char *word);
LineNode *find_line(LineNode *lines, const char *word);
int replace_words2(LineNode *lines, const char *oldword, const char *newword);
void free_lines(LineNode *lines);
#endif
Sorry to post so much code but I've been working on this one problem with my code since yesterday morning and I'm sure I'm going to find more once I fix this one.
Thanks again for any insight anyone can bring.
-Peter