Sign In
Create Account
Follow Us on Twitter
Subscribe on Youtube
2
#include <stdio.h>
#include <ctype.h>
#include <stdlib.h>
#include <string.h>
typedef struct LinkedLineList
{
LinkedLineList *next;
int line;
}LinkedLineList;
typedef struct AVLWordNode
{
char *word;
int height;
LinkedLineList *firstline;
struct AVLWordNode *left;
struct AVLWordNode *right;
}AVLWordNode;
LinkedLineList *addLine(int line)
{
LinkedLineList *newLine = malloc(sizeof *newLine);
if(newLine != NULL)
{
newLine->line = line;
newLine->next = NULL;
}
return new;
}
AVLWordTree *addNode(AVLWordTree **node, char *word, int line)
{
AVLWordTree *wordloc = NULL;
LinkedLineList *newline = NULL;
AVLWordTree *temp = NULL;
int diff = 0;
if(node != NULL && word != NULL)
{
if(NULL == *node)
{
*node = malloc(sizeof **node);
if(NULL != *node)
{
(*node)->left = NULL;
(*node)->right = NULL;
(*node)->word = dupstr(word);
if((*node)->word != NULL)
{
(*node)->firstline = addLine(line);
if((*node)->firstline != NULL)
{
wordloc = *node;
}
}
}
}
else
{
diff = caseInsensitiveCmp((*node)->word, word);
if(0 == diff)
{
newline = addLine(line);
if(newline != NULL)
{
wordloc = *node;
newline->next = (*node)->firstline;
(*node)->firstline = newline;
}
}
else if(0 < diff)
{
temp = *node;
wordloc = addNode(&temp->left, word, line);
}
else
{
temp = *node;
wordloc = addNode(&temp->right, word, line);
}
}
}
if(wordloc == NULL)
{
delWord(node);
}
return wordloc;
}
/* This is the issue */
/* need rightrotate, leftrotate, doubleleft and right, balance */
int getHeight(AVLWordTree *node)
{
int lChild = (node->left) ? node->left->height + 1 : 0;
int rChild = (node->right) ? node->right->height + 1 : 0;
return(lChild >= rChild) ? lChild : rChild);
}
void delWord(AVLWordTree **node)
{
AVLWordTree *temp = NULL;
if(node != NULL)
{
if(*node != '\0')
{
if{(*node)->right != NULL)
{
temp = *node;
delWord(&temp->right);
}
if((*node)->left != NULL)
{
temp = *node;
delWord(&temp->left);
}
if((*node)->word != NULL)
{
free((*node)->word);
}
if((*node)->firstline != NULL)
{
delList((*node)->firstline;
}
free(*node);
*node = NULL;
}
}
}
void delList(LinkedLineList *listnode)
{
if(listnode != NULL)
{
delList(listnode->next);
free(listnode);
}
}
void printList(LinkedLineList *list)
{
if(list != NULL)
{
printList(list->next);
printf("%d ", list->line);
}
}
void printTree(AVLWordNode *node)
{
if(node != NULL)
{
printtree(node->left);
printf("%s: ", node->word);
printlist(node->firstline);
printf("\n");
printtree(node->right);
}
}
char *char_in_string(char *s, int c)
{
char *p = NULL;
if(s != NULL)
{
if(c != '\0')
{
while(*s != '\0' && *s != c)
{
++s;
}
if(*s == c)
{
p = s;
}
}
}
return p;
}
char *tokenize(char **s, char *eliminate)
{
char *p = NULL;
char *q = NULL;
if(s != NULL && *s != '\0' && eliminate != NULL)
{
while(NULL != char_in_string(eliminate, **s))
{
++*s;
}
if(**s != '\0')
{
q = *s + 1;
p = *s;
while(*q != '\0' && NULL == char_in_string(eliminate, *q))
{
++q;
}
*s = q + (*q != '\0');
*q = '\0';
}
}
return p;
}
int caseInsensitiveCmp(const char *s, const char *t)
{
int diff = 0;
char cs = 0;
char ct = 0;
while(diff == 0 && *s != '\0' && *t != '\0')
{
cs = tolower((unsigned char)*s);
ct = tolower((unsigned char)*t);
if(cs < ct)
{
diff = -1;
}
else if(cs > ct)
{
diff = 1;
}
++s;
++t;
}
if(diff == 0 && *s != *t)
{
if(*s == '\0')
{
diff = -1;
}
else
{
diff = 1;
}
}
return diff;
}
char *duplicateStr(char *s)
{
char *p = NULL;
if(s != NULL)
{
p = malloc(strlen(s) + 1);
if(p)
{
strcpy(p, s);
}
}
return p;
}
char *getLine(char *s, int n, FILE *fp)
{
int c = 0;
int done = 0;
char *p = s;
while(!done && --n > 0 && (c = getc(fp)) != EOF)
{
if((*p++ = c) == '\n')
{
done = 1;
}
}
*p = '\0';
if(EOF == c && p == s)
{
p = NULL;
}
else
{
p = s;
}
return p;
}
#define MAXLINE 8192
int main(void)
{
static char buffer[MAXLINE] = {0};
char *s = NULL;
char *word = NULL;
int line = 0;
int giveup = 0;
AVLWordTree *tree = NULL;
char *eliminate = " \t\n\r\a\f\v!\"%^&*()_=+{}[]\\|/,.<>:;#~?1234567890";
while(!giveup && getLine(buffer, sizeof buffer, stdin) != NULL)
{
++line;
s = buffer;
while(!giveup && (word = tokenize(&s, eliminate)) != NULL)
{
if(NULL == addWord(&tree, word, line))
{
printf("Error adding data into memory. Giving up.\n");
giveup = 1;
}
}
}
if(!giveup)
{
printTree(tree);
}
delWord(&tree);
return 0;
}
And maybe even condense it a little.
Thanks
Edited by mr mike, 26 March 2011 - 11:35 AM.
cleanup
Back to top
