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

This is a discussion on K&R 6-4 : won't read Struct * within the C Programming forums, part of the General Programming Boards category; From K&R's chapter6, #4, I have a Struct tnode "root" full of words, sorted alphabetically, with word-count for each one. ...

  1. #1
    Registered User
    Join Date
    Jan 2011
    Posts
    8

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

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Last edited by quzah; 04-05-2011 at 11:37 PM.
    Hope is the first step on the road to disappointment.

  3. #3
    Registered User
    Join Date
    Mar 2011
    Posts
    21
    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;
    }

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help with Realloc()
    By krazyxazn in forum C Programming
    Replies: 10
    Last Post: 01-27-2010, 10:05 PM
  2. Help me please.
    By yann in forum C Programming
    Replies: 15
    Last Post: 09-29-2009, 10:04 PM
  3. Looking for constructive criticism
    By wd_kendrick in forum C Programming
    Replies: 16
    Last Post: 05-28-2008, 10:42 AM
  4. Looking for a way to store listbox data
    By Welder in forum C Programming
    Replies: 20
    Last Post: 11-02-2007, 12:48 AM
  5. Dikumud
    By maxorator in forum C++ Programming
    Replies: 1
    Last Post: 10-01-2005, 07:39 AM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21