#include "stdafx.h" #include <stdlib.h> 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 */ }; #include <stdio.h> #include <ctype.h> #include <string.h> #define MAXWORD 100 struct tnode *addtree(struct tnode *, char *); void treeprint(struct tnode *); int getword(char *, int); /* word frequency count */ int main() { struct tnode *root; char word[MAXWORD]; root = NULL; while (getword(word, MAXWORD) != EOF) if (isalpha(word[0])) root = addtree(root, word); treeprint(root); system("pause"); 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 */ 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; } /* treeprint: in-order print of tree p */ void treeprint(struct tnode *p) { if (p != NULL) { treeprint(p->left); printf("M %s/n", p->count, p->word); treeprint(p->right); } } /* 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) /* push character back on input */ { if (bufp >= BUFSIZE) printf("ungetch: too many characters/n"); else buf[bufp++] = c; }
改进版: 以下程序对输入单词按字典顺序排序 但是只排前6（默认6，具体可由命令行参数给出）位字符一样的单词
#include "stdafx.h" #include <stdlib.h> struct tnode { /* the tree node: */ char *word; /* points to the text */ int match; /* match found */ struct tnode *left; /* left child */ struct tnode *right; /* right child */ }; #include <stdio.h> #include <ctype.h> #include <string.h> #define MAXWORD 100 #define YES 1 #define NO 0 struct tnode *addtree(struct tnode *, char *, int, int*); void treeprint(struct tnode *); int getword(char *, int); /* print in alphabetic order each group of variable names*/ /* identical in the first num characters (default 6)*/ int main(int argc, char *argv[]) { struct tnode *root; char word[MAXWORD]; int found = NO; /* YES if match was found*/ int num; /* number of the first ident, chars*/ num = (--argc && (*++argv)[0] == '-') ? atoi(argv[0]+1):6; root = NULL; while (getword(word, MAXWORD) != EOF){ if (isalpha(word[0]) && strlen(word) >= num) root = addtree(root, word, num, &found); found = NO; } treeprint(root); system("pause"); return 0; } struct tnode *talloc(void); int compare(char *, struct tnode *, int, int *); char *strdup(char *); /* addtree: add a node with w, at or below p */ struct tnode *addtree(struct tnode *p, char *w, int num, int * found) { int cond; if (p == NULL) { /* a new word has arrived */ p = talloc(); /* make a new node */ p->word = strdup(w); p->match = *found; p->left = p->right = NULL; } else if ((cond = compare(w, p, num,found)) < 0) p->left = addtree(p->left,w,num,found); else if (cond > 0) /* less than into left subtree */ p->right = addtree(p->right, w, num, found); return p; } /* compare; compare words and update p->match*/ int compare(char *s,struct tnode *p, int num, int *found) { int i; char *t = p->word; for(i = 0; *s == *t; i++,s++,t++) if(*s =='/0') return 0; if (i >= num) { *found = YES; p->match = YES; } return *s -*t; } /* treeprint: in-order print of tree p */ void treeprint(struct tnode *p) { if (p != NULL) { treeprint(p->left); if(p->match) printf("%s/n", p->word); treeprint(p->right); } } /* 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) /* push character back on input */ { if (bufp >= BUFSIZE) printf("ungetch: too many characters/n"); else buf[bufp++] = c; }
