From 338b2237b3d00745469fb265d77638ec245ca367 Mon Sep 17 00:00:00 2001 From: sinanmohd Date: Mon, 8 May 2023 11:11:45 +0530 Subject: 6.3: using linked list --- 6.3/gnu | 20 ++++++++++++++++++++ 6.3/main.c | 54 ++++++++++++++++++++++++++++++++++++------------------ 6.3/tree.c | 60 +++++++++++++++++++++++++++++++++++++++++++++++------------- 6.3/tree.h | 12 +++++++----- 4 files changed, 110 insertions(+), 36 deletions(-) create mode 100644 6.3/gnu diff --git a/6.3/gnu b/6.3/gnu new file mode 100644 index 0000000..31a03be --- /dev/null +++ b/6.3/gnu @@ -0,0 +1,20 @@ +I'd just like to interject for a moment. What you're refering to as Linux, is +in fact, GNU/Linux, or as I've recently taken to calling it, GNU plus Linux. +Linux is not an operating system unto itself, but rather another free +component of a fully functioning GNU system made useful by the GNU corelibs, +shell utilities and vital system components comprising a full OS as defined +by POSIX. + +Many computer users run a modified version of the GNU system every day, +without realizing it. Through a peculiar turn of events, the version of GNU +which is widely used today is often called Linux, and many of its users are +not aware that it is basically the GNU system, developed by the GNU Project. + +There really is a Linux, and these people are using it, but it is just a part +of the system they use. Linux is the kernel: the program in the system that +allocates the machine's resources to the other programs that you run. The +kernel is an essential part of an operating system, but useless by itself; +it can only function in the context of a complete operating system. Linux is +normally used in combination with the GNU operating system: the whole system +is basically GNU with Linux added, or GNU/Linux. All the so-called Linux +distributions are really distributions of GNU/Linux! diff --git a/6.3/main.c b/6.3/main.c index cd52cec..5c35e24 100644 --- a/6.3/main.c +++ b/6.3/main.c @@ -7,25 +7,20 @@ #define MAXWORD 100 #define ARR_SIZE(X) (sizeof(X)/sizeof(X[0])) -const char *noise[] = { - "the", - "and" -}; - -int isnoise(char *word); +int noiseword(char *w); int main(void) { char word[MAXWORD]; struct tnode *root; - int line = 0; + int linenum = 0; root = NULL; while (getword(word, MAXWORD) != EOF) - if (isalpha(word[0]) && !isnoise(word)) - root = addtree(root, word, line); + if (isalpha(word[0]) && noiseword(word) == -1) + root = addtree(root, word, linenum); else if(word[0] == '\n') - ++line; + ++linenum; tprint(root); tfree(root); @@ -33,13 +28,36 @@ int main(void) return 0; } -int isnoise(char *word) +int noiseword(char *w) { - size_t i; - - for(i = 0; i < ARR_SIZE(noise); ++i) - if (!strcmp(word, noise[i])) - return 1; - - return 0; + const char *noise[] = { + "a", + "an", + "and", + "are", + "in", + "is", + "of", + "or", + "that", + "the", + "this", + "to" + }; + + int cond, mid; + int low = 0; + int high = ARR_SIZE(noise); + + while (low < high) { + mid = (low + high) / 2; + if ((cond = strcmp(w, noise[mid])) < 0) + high = mid; + else if (cond > 0) + low = mid + 1; + else + return mid; + } + + return -1; } diff --git a/6.3/tree.c b/6.3/tree.c index c58da53..a83d294 100644 --- a/6.3/tree.c +++ b/6.3/tree.c @@ -6,55 +6,89 @@ #include "tree.h" struct tnode *talloc(void); +struct linklist *lalloc(void); +void lfree(struct linklist *p); +void addln(struct tnode *p, int linenum); -struct tnode *addtree(struct tnode *p, char *w, int line) +struct tnode *addtree(struct tnode *p, char *w, int linenum) { int cond; if (p == NULL) { p = talloc(); p->word = strdup(w); - p->lc = 0; - p->lines[p->lc++] = line; + p->lines = lalloc(); + p->lines->linenum = linenum; + p->lines->ptr = NULL; p->left = p->right = NULL; } else if (!(cond = strcasecmp(w, p->word))) { - if (p->lc < MAXLINES) - p->lines[p->lc++] = line; - else - error(EXIT_FAILURE, ENOBUFS, "addtree"); + addln(p, linenum); } else if (cond < 0) { - p->left = addtree(p->left, w, line); + p->left = addtree(p->left, w, linenum); } else if (cond > 0) { - p->right = addtree(p->right, w, line); + p->right = addtree(p->right, w, linenum); } return p; } +void addln(struct tnode *p, int linenum) +{ + struct linklist *temp; + + temp = p->lines; + while (temp->ptr != NULL && temp->linenum != linenum) + temp = temp->ptr; + + if (temp->linenum != linenum) { + temp->ptr = lalloc(); + temp->ptr->linenum = linenum; + temp->ptr->ptr = NULL; + } +} + void tprint(struct tnode *p) { - int lc; + struct linklist *temp; if (p != NULL) { tprint(p->left); - printf("---> %s\n", p->word); - for (lc = 0; lc < p->lc; ++lc) - printf((lc == p->lc-1) ? "%d" : "%d, ", p->lines[lc]); + + printf("%10s: ", p->word); + for (temp = p->lines; temp != NULL; temp = temp->ptr) + printf("%4d", temp->linenum); + // printf("%d%s", temp->linenum, + // (temp->ptr == NULL) ? "\n" : ", "); putchar('\n'); tprint(p->right); } } + void tfree(struct tnode *p) { if (p != NULL) { tfree(p->left); tfree(p->right); + lfree(p->lines); free(p->word); free(p); } } +void lfree(struct linklist *p) +{ + if (p != NULL) { + lfree(p->ptr); + free(p); + } +} + struct tnode *talloc(void) { return (struct tnode *) malloc(sizeof(struct tnode)); } + +struct linklist *lalloc(void) +{ + return (struct linklist *) malloc(sizeof(struct linklist)); +} diff --git a/6.3/tree.h b/6.3/tree.h index c6ebc53..0b90913 100644 --- a/6.3/tree.h +++ b/6.3/tree.h @@ -1,18 +1,20 @@ #ifndef TREE_H -#define MAXLINES 1000 - struct tnode { char *word; - int lc; - int lines[MAXLINES]; + struct linklist *lines; struct tnode *left; struct tnode *right; }; +struct linklist { + int linenum; + struct linklist *ptr; +}; + #define TREE_H #endif -struct tnode *addtree(struct tnode *p, char *w, int line); +struct tnode *addtree(struct tnode *p, char *w, int linenum); void tprint(struct tnode *p); void tfree(struct tnode *p); -- cgit v1.2.3