From K&R's chapter6, #4, I have a Struct tnode "root" full of words, sorted alphabetically, with word-count for each one. The task was to print the list of words, but sorted by decreasing word count. I attempted reading all the nodes from the struct into an array, then was going to sort the array, but couldn't get it to work.
Now I am trying to use the (first) struct 'root', to create a new structure 'root3'. This new struct is comparing the Count of each word, so it builds the structure naturally by decreasing-word-count. Then the original 'treeprint' function can print it. It compiles ok (with a warning about *treeread not always returning a value), but then after input does nothing and eventually times out.
I highlighted where it is getting stuck in an infinite loop.
Can anyone catch what the problem is?
Code:
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#define MAXWORD 100
struct tnode *addtree(struct tnode *, char *);
struct tnode *addtree2(struct tnode *, struct tnode *);
void treeprint(struct tnode *);
struct tnode *treeread(struct tnode *);
int getword(char *, int);
struct tnode { /*the tree node:*/
char *word; /*points to the text*/
int count; /*number of occurrences*/
struct tnode *left; /*left child*/
struct tnode *right; /*right child*/
};
/*word frequency count*/
main (int argc, char *argv[]) {
struct tnode *root=NULL, *root2=NULL, *root3=NULL;
char word[MAXWORD];
int i;
while (getword(word,MAXWORD) != '>') {
if (isalpha(word[0]))
root = addtree(root,word);
}
while ((root2=treeread(root))!= NULL) {
if (isalpha(word[0]))
root3 = addtree2(root3,root2);
}
treeprint(root3);
return 0;
}
struct tnode *talloc(void);
char *strdup(char *);
/* addtree: add a node with w, at or below p */
struct tnode *addtree(struct tnode *p, char *w) {
int cond;
if (p==NULL) { /*a new word has arrived; make a new node */
p=talloc();
p->word=strdup(w);/*string duplicate*/
p->count=1;
p->left = p->right = NULL;
} else if ((cond = strcmp(w, p->word))==0)
p->count++; /*repeated word*/
else if (cond<0) /*less than, into left subtree*/
p->left=addtree(p->left,w);
else
p->right=addtree(p->right,w);
return p;
}
/* addtree2: add a node with w, at or below p; comparing word-count */
struct tnode *addtree2(struct tnode *p, struct tnode *w) { printf("hello");
if (p==NULL) { /*a new word has arrived; make a new node */
p=talloc();
p->word=w->word;
p->count=1;
p->left = p->right = NULL;
} else if (w->count <= p->count) /*less than or =, into left subtree*/
p->left=addtree2(p->left,w);
else
p->right=addtree2(p->right,w);
return p;
}
/*treeprint: alphabetical order print of tree p*/
void treeprint(struct tnode *p) {
if (p!=NULL) {
treeprint(p->left);
printf("%4d %s\n", p->count,p->word);
treeprint(p->right);
}
}
struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/ if (p!=NULL) {
treeread(p->left);
treeread(p->right);
return p;
}
}
/*talloc: make a tnode*/
struct tnode *talloc(void) {
return (struct tnode *) malloc(sizeof(struct tnode));
}
char *strdup(char *s) { /*make a duplicate of s*/
char *p;
p=(char *) malloc(strlen(s)+1); /*+1 for '\0'*/
if (p != NULL)
strcpy(p,s);
return p;
}
/*getword: get next word or character from input*/
int getword(char *word, int lim) {
int c,getch(void);
void ungetch(int);
char *w=word;
while (isspace(c=getch()))
;
if (c!=EOF)
*w++=c;
if (!isalpha(c)){
*w='\0';
return c;
}
for (;--lim>0;w++) {
if (!isalnum(*w=getch())) {
ungetch(*w);
break;
}
}
*w = '\0';
return word[0];
}
#define BUFSIZE 100
char buf[BUFSIZE]; /*buffer for ungetch*/
int bufp=0; /*next free position in buf*/
int getch(void) /*get a (possibly pushed-back) character */
{
return (bufp>0) ? buf[--bufp] : getchar();
}
void ungetch(int c)
{
if (bufp>=BUFSIZE)
printf("ungetch:too many characters\n");
else
buf[bufp++]=c;
}