CS 245 Homework 5

Due Date

4:00 pm Monday Feb 2

Assignment Name

wordcount

File Names

wordcount.c

Below are implementations of a chained hashtable (symbol table) and a binary search tree using the random insertion method.

Write a program that reads a text file from stdin, splits it up into words, and prints a frequency table for the words, ordered first by frequency in decreasing order and then alphabetically for words with the same frequency. It will use a hash table to accumulate the counts and a binary search tree to print the words in the proper order.

Modify the symbol table to store a count for the words, so value field will be an int rather than void *. You won't need the lookup function if store just increments the count when the word is already in the table. The traverse function will need a visit function that stores the word and count in the binary search tree.

Modify the binary search tree implementation to store words and counts in the nodes. You will need to do the comparison of nodes by first comparing the count and then the word if the counts are equal.

I have also included functions that split a text file into words. You may use that code to split words in your program.

Remove any code that is not needed and include all functions in wordcount.c.

symtab.h

#ifndef SYMTAB_H
#define SYMTAB_H

typedef struct symtab symtab;

symtab *symtab_new();
void symtab_store(symtab *table, char *key, void *value);
void *symtab_lookup(symtab *table, char *key);
void symtab_traverse(symtab *table, void (*visit)(char *, void *));

#endif

symtab.c

#include <stdlib.h>
#include "symtab.h"

#define SYMTAB_SIZE 1009

static unsigned int hash(char *s) {
  int h = 0;
  while (*s != '\0') {
    h += *s++ * 117;
  }
  return h;
}

typedef struct node {
  void *key;
  void *value;
  struct node *next;
} node;

struct symtab {
  int size;
  node **chains;
};

symtab *symtab_new() {
  symtab *st = malloc(sizeof(symtab));
  st->size = SYMTAB_SIZE;
  st->chains = malloc(SYMTAB_SIZE * sizeof(node *));
  return st;
}

void symtab_store(symtab *st, char * key, void *value) {
  unsigned int h = hash(key) % st->size;
  node *n = st->chains[h];
  while (n != NULL) {
    if (n->key == key) {
      n->value = value;
      return;
    }
    else {
      n = n->next;
    }
  }
  n = malloc(sizeof(node));
  n->key = key;
  n->value = value;
  n->next = st->chains[h];
  st->chains[h] = n;
}

void *symtab_lookup(symtab *st, char * key) {
  unsigned int h = hash(key) % st->size;
  node *n = st->chains[h];
  while (n != NULL) {
    if (n->key == key) {
      return n->value;
    }
    else n = n->next;
  }
  return NULL;
}

void symtab_traverse(symtab *st, void (*visit)(char * key, void *value)) {
  for (int i = 0; i < st->size; i++) {
    node *n = st->chains[i];
    while (n != NULL) {
      visit(n->key, n->value);
      n = n->next;
    }
  }
}

bst7.c

#include <stdio.h>
#include <stdlib.h>

// Binary Search Tree with Random Insertion

typedef struct node {
  int value;
  struct node *left;
  struct node *right;
  int count;
} node;

typedef struct bst {
  node *root;
} bst;


bst *bst_new() {
  bst *tree = malloc(sizeof(bst));
  tree->root = NULL;
  return tree;
}

int get_count(node *n) {
  if (n == NULL) return 0;
  else return n->count;
}

void fix_count(node *n) {
  if (n != NULL) {
    n->count = 1 + get_count(n->left) + get_count(n->right);
  }
}

node *rotate_right(node *n) {
  node *temp = n->left;
  n->left = temp->right;
  temp->right = n;
  fix_count(n);
  fix_count(temp);
  return temp;
}

node *rotate_left(node *n) {
  node *temp = n->right;
  n->right = temp->left;
  temp->left = n;
  fix_count(n);
  fix_count(temp);
  return temp;
} 

node *insert_top(node *n, int value) {
  if (n == NULL) {
    node *new = malloc(sizeof(node));
    new->value = value;
    new->left = NULL;
    new->right = NULL;
    new->count = 1;
    return new;
  }
  else {
    if (value < n->value) {
      n->left = insert_top(n->left, value);
      return rotate_right(n);
    }
    else if (value > n->value) {
      n->right = insert_top(n->right, value);
      return rotate_left(n);
    }
    else if (drand48() < 0.5) {
      n->left = insert_top(n->left, value);
      return rotate_right(n);
    }
    else {
      n->right = insert_top(n->right, value);
      return rotate_left(n);
    }
  }
}

node *insert_random(node *n, int value) {
  if (n == NULL) {
    node *new = malloc(sizeof(node));
    new->value = value;
    new->left = NULL;
    new->right = NULL;
    new->count = 1;
    return new;
  }
  else if (drand48() < 1.0 / (n->count + 1)) {
    return insert_top(n, value);
  }
  else if (value < n->value) {
    n->left = insert_random(n->left, value);
    n->count++;
    return n;
  }
  else if (value > n->value) {
    n->right = insert_random(n->right, value);
    n->count++;
    return n;
  }
  else if (drand48() < 0.5) {
    n->left = insert_random(n->left, value);
    n->count++;
    return n;
  }
  else {
    n->right = insert_random(n->right, value);
    n->count++;
    return n;
  }
}

void insert(bst *tree, int value) {
  tree->root = insert_random(tree->root, value);
}

void print_h(node *n) {
  if (n != NULL) {
    print_h(n->left);
    printf("%d\n", n->value);
    print_h(n->right);
  }
}

void print(bst *tree) {
  print_h(tree->root);
}

int height_h(node *n) {
  if (n == NULL) return -1;
  else {
    int lheight = height_h(n->left);
    int rheight = height_h(n->right);
    if (lheight < rheight) return rheight + 1;
    else return lheight + 1;
  }
}

int height(bst *tree) {
  return height_h(tree->root);
}

typedef struct dc {
  int total_depth;
  int count;
} dc;

dc total_depth_and_count(node *n) {
  if (n->left == NULL && n->right == NULL) return (dc) { 0, 1 };
  else if (n->left == NULL) {
    dc result = total_depth_and_count(n->right);
    return (dc) { result.total_depth + result.count, result.count + 1};
  }
  else if (n->right == NULL) {
    dc result = total_depth_and_count(n->left);
    return (dc) { result.total_depth + result.count, result.count + 1};
  }
  else {
    dc left_result = total_depth_and_count(n->left);
    dc right_result = total_depth_and_count(n->right);
    return (dc) {
      left_result.total_depth + left_result.count +
      right_result.total_depth + right_result.count,
      left_result.count + right_result.count + 1
    };
  }
}

double average_depth(bst *tree) {
  dc result =  total_depth_and_count(tree->root);
  return result.total_depth / (double) result.count;
}

void display_h(node *n, int indent) {
  if (n != NULL) {
    printf("%*d\n", indent, n->value);
    display_h(n->left, indent + 4);
    display_h(n->right, indent + 4);
  }
  else {
    printf("%*s\n", indent, "*");
  }
}

void display(bst *tree) {
  display_h(tree->root, 0);
}

void to_array_h(node *n, int *a, int *i) {
  if (n != NULL) {
    to_array_h(n->left, a, i);
    a[*i] = n->value;
    (*i)++;
    to_array_h(n->right, a, i);
  }
}
  

int *to_array(bst *tree) {
  int n = get_count(tree->root);
  if (n == 0) return NULL;
  else {
    int *a = malloc(n * sizeof(int));
    int i = 0;
    to_array_h(tree->root, a, &i);
    return a;
  }
}

Functions for reading words

void skip() {
  while (true) {
    int c = getchar();
    if (c == EOF) return;
    else if (isalpha(c)) {
      ungetc(c, stdin);
      return;
    }
  }
}

char *getword() {
  skip();
  char word[MAXWORD + 1];
  int len = 0;
  while (true) {
    int c = tolower(getchar());
    if (len > MAXWORD) {
      fprintf(stderr, "Maximum word length exceeded\n");
      exit(1);
    }
    if (c == EOF) {
      if (len == 0) return NULL;
      else {
        word[len] = '\0';
        return strdup(word);
      }
    }
    else if (isalpha(c) || c == '\'') {
      word[len] = c;
      len++;
    }
    else {
      if (len == 0) return NULL;
      else {
        word[len] = '\0';
        return strdup(word);
      }
    }
  }
}