Self-referential structure, example from K and R #include <stdio.h> #include <ctype.h> #include <string.h> #include <stdlib.h> #include <unistd.h> #define MAXWORD 100 #define BUFSIZE 100 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 */ }; struct tnode *addtree(struct tnode *, char *); struct tnode *talloc(void); void treeprint(struct tnode *); void ungetch(int); int getword(char *, int); int getch(void); char buf[BUFSIZE]; /* buffer for ungetch */ int bufp = 0; /* next free position in buf */ int main(void) { /* word frequency count */ struct tnode *root; char word[MAXWORD]; root = NULL; while(getword(word, MAXWORD) != EOF) if(isalpha(word[0])) root = addtree(root, word); treeprint(root); exit(0); } /* 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]; } /* 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 */ p = talloc(); /* make a new node */ p->word = strdup(w); 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 /* greater than into right subtree */ p->right = addtree(p->right, w); return p; } /* talloc: make a tnode */ struct tnode *talloc(void) { return(struct tnode *)malloc(sizeof(struct tnode)); } /* treeprint: in-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); } } int getch(void) { return (bufp > 0) ? buf[--bufp] : getchar(); } void ungetch(int c) { if(bufp >= BUFSIZE) printf("ungetch: too many characters\n"); else buf[bufp++] = c; }
No comments: