K&R 6-4 : won't read Struct *

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

Code:

struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/	if (p!=NULL) {
		treeread(p->left);
		treeread(p->right);
		return p;
	}
}

You are ignoring the return values of treeread. Shouldn't you be doing something useful with them?

Code:

This isn't code, it's an illustration:
n1 = { (left) n2, (right) n2 }
n2 = { (left) NULL, (right) NULL }
n3 = { (left) NULL, (right) NULL }

You have one node (n1) that has two branches (n2 and n3), each of which have no branches.

Your code does:

Code:

treeread( n1 )
    n1 != null
        treeread( n2 )
            n2 != null
                treeread( null )
                    null == null, return ... what? 
                treeread( null )
                    null == null, return ... what? 
            return n2
        ignore n2 being returned
        treeread( n3 )
            n3 != null
                treeread( null )
                    null == null, return ... what? 
                ignore whatever happens to be returned
                treeread( null )
                    null == null, return ... what?
                ignore whatever happens to be returned
            return n3
        ignore n3 being returned
        return n1

Some of the time you reach the end of the function and don't return anything (your function SHOULD be returning something all the time, so listen to your compiler). Then some of the times you actually do something, but you just return the starting node in those cases.

In any event, you aren't really doing anything with this function at all.


Quzah.

Code:

struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/	if (p!=NULL) {
		treeread(p->left);
		treeread(p->right);
		return p;
	}
}

I'm surprised your compiler didn't warn you that it is possible to reach the end of this function without returning anything. I don't think that's your problem, but maybe move the return p outside of the if block...

Code:

struct tnode *treeread(struct tnode *p) {/*here it gets stuck in loop*/	
        if (p) {
		treeread(p->left);
		treeread(p->right);
	}
	return p;
}