diff options
| -rw-r--r-- | ch6/6-03_line_location.c | 190 |
1 files changed, 190 insertions, 0 deletions
diff --git a/ch6/6-03_line_location.c b/ch6/6-03_line_location.c new file mode 100644 index 0000000..9a22c81 --- /dev/null +++ b/ch6/6-03_line_location.c @@ -0,0 +1,190 @@ +#include <stdio.h> +#include <string.h> +#include <ctype.h> +#include <stdlib.h> + +/* The C Programming Language: 2nd Edition + * + * Exercise 6-3: Write a cross-referencer that prints a list of all words in a + * document, and, for each word, a list of the line numbers on which it occurs. + * Remove noise words like "the", "and", and so on. + * + * Notes: The trick to this is to pare down a few functions from 6-2, then add + * a separate struct to be part of the tnode struct. I opted for a linked list + * of line numbers and some recursion. getline could have been used, and might + * have been slightly simpler, but this gets the job done. There's certainly + * some room for better word detection, and the tlist structure could probably + * be something that's not O(n), but this is Category-0 so who cares? :) + */ + +#define BUFSIZE 1000 +#define MAXWORD 100 +#define DEF_PRE_LEN 4 + +struct tlist { + struct tlist *next; + int num; +}; + +struct tnode { + char *word; + struct tlist *lines; + struct tnode *left; + struct tnode *right; +}; + +char buf[BUFSIZE]; +int bufp = 0; +int minlen; +int line_nr = 1; + +int getch(void); +void ungetch(int); +int getword(char *, int); +struct tnode *addtree(struct tnode *, char *, int); +void addlist(struct tlist *, int); +void treeprint(struct tnode *); +void listprint(struct tlist *); +struct tnode *talloc(void); +struct tlist *lalloc(void); +char *mystrdup(char *); + +int main(int argc, char *argv[]) { + switch (argc) { + case 1: + minlen = DEF_PRE_LEN; + break; + case 2: + minlen = strtol(argv[1], NULL, 10); + break; + default: + printf("Too many arguments.\n"); + return 1; + } + struct tnode *root; + char word[MAXWORD]; + root = NULL; + while (getword(word, MAXWORD) != EOF) { + /* Only add the words we need to the tree */ + if (isalpha(word[0]) && strlen(word) > minlen) { + root = addtree(root, word, line_nr); + } + } + if (root == NULL) { + printf("No words at that length or greater were found.\n"); + return 1; + } else { + treeprint(root); + return 0; + } +} + +int getword(char *word, int lim) { + int c; + char *w = word; + while (isspace(c = getch())) { + if (c == '\n') { + line_nr++; + } + } + if (c == EOF) { + return EOF; + } + if (c != EOF) { + *w++ = c; + } + for ( ; --lim > 0; w++) { + if (!isalpha(*w = getch())) { + ungetch(*w); + break; + } + } + *w = '\0'; + return word[0]; +} + +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; + } +} + +struct tnode *addtree(struct tnode *p, char *w, int pos) { + int cond; + if (p != NULL) { + if ((cond = strcmp(w, p->word)) == 0) { + addlist(p->lines, pos); + } else if (cond < 0) { + p->left = addtree(p->left, w, pos); + } else if (cond > 0) { + p->right = addtree(p->right, w, pos); + } + } else { + p = talloc(); + p->lines = lalloc(); + p->word = mystrdup(w); + /* Add to the list of lines */ + (p->lines)->num = pos; + (p->lines)->next = NULL; + p->left = p->right = NULL; + } + return p; +} + +void addlist(struct tlist *l, int pos) { + /* Follow the list until we reach the end */ + while (l->next != NULL) { + l = l->next; + } + /* Don't add a line number if the numbers match! */ + if (l->num == pos) { + return; + } + /* This won't happen unless l->next is NULL, meaning we've reached the end of the list. */ + struct tlist *newline = lalloc(); + newline->num = pos; + newline->next = NULL; + /* Let's add to it now */ + l->next = newline; +} + +void treeprint(struct tnode *p) { + if (p != NULL) { + treeprint(p->left); + printf("%-20s ", p->word); + listprint(p->lines); + treeprint(p->right); + } +} + +void listprint(struct tlist *list) { + printf("%3d ", list->num); + if (list->next != NULL) { + listprint(list->next); + } else { + printf("\n"); + } +} + +struct tnode *talloc(void) { + return (struct tnode *) malloc(sizeof(struct tnode)); +} + +struct tlist *lalloc(void) { + return (struct tlist *) malloc(sizeof(struct tlist)); +} + +char *mystrdup(char *s) { + char *p; + p = (char *) malloc(strlen(s)+1); + if (p != NULL) { + strcpy(p , s); + } + return p; +} |