F
Foodbank
Hi,
I'm currently teaching myself C data structures in preparation for a
job transition and I've just passed the point in which radix sorting
was covered in my book. I've recently finished a radix sorting program
and was surprised by its speed. Therefore, I'd like help with a radix
tree program in order to compare it with a prior binary tree program
that I finished. The parts I'm having trouble with are collecting
statistics and inserting words into the tree (as commented in the
program below).
The purpose of the program is to scan the string from a text document
and provide various counts, what the deepest level of the tree is, etc.
(you'll see in my variables below, also it performs the same counts as
my previous binary tree exercise). Also, the way the way that the text
document is inputed into the program is on the command line under
Cygwin (UNIX emulator). I am not planning on using fopen in this one,
as I didn't in my previous binary tree program.
Thanks for your help,
James
I'm currently teaching myself C data structures in preparation for a
job transition and I've just passed the point in which radix sorting
was covered in my book. I've recently finished a radix sorting program
and was surprised by its speed. Therefore, I'd like help with a radix
tree program in order to compare it with a prior binary tree program
that I finished. The parts I'm having trouble with are collecting
statistics and inserting words into the tree (as commented in the
program below).
The purpose of the program is to scan the string from a text document
and provide various counts, what the deepest level of the tree is, etc.
(you'll see in my variables below, also it performs the same counts as
my previous binary tree exercise). Also, the way the way that the text
document is inputed into the program is on the command line under
Cygwin (UNIX emulator). I am not planning on using fopen in this one,
as I didn't in my previous binary tree program.
Thanks for your help,
James
Code:
#include <stdio.h>
#include <math.h>
#include <malloc.h>
#include <strings.h>
#define MAXLEN 100 // Maximum length
#define TWID 27 // The tree branching width
#define END (TWID-1) // The code for a non
letter is 26
struct node { // The tree node structure
int count;
struct node *np[TWID];
} root;
// these will be the stats to collect
int nodes_used, total_words, unique_words, most_frequent_count,
deepest_level;
char most_frequent_word[MAXLEN];
char deepest_word[MAXLEN];
// function prototypes
void insert(struct node *, char *);
void treewalk(struct node *);
int get_word(char *);
main(int argc, char *argv[]) {
char word_buff[MAXLEN]; // the reusable word buffer
while(get_word(word_buff))
insert(&root, word_buff);
treewalk(&root);
printf("the root count is %d\n", root.count);
printf("the tree contains %d nodes\n", nodes_used);
printf("there are %d unique words out of %d total words\n",
unique_words, total_words);
printf("most frequent word <%s> appears %d times\n",
most_frequent_word, most_frequent_count);
printf("the deepest word <%s> is at level %d\n",
deepest_word, deepest_level);
}
void insert(struct node *np, char *word) {
char c;
/* ***** CODE TO INSERT A WORD IN THE TREE ***** */
}
char current[MAXLEN]; // keep track of the current word
during recursion
int treewalk_level = -1; // keep track of the recursion depth
void treewalk(struct node *np) {
int i, c;
/* ***** CODE TO WALK THE TREE TO COLLECT THE STATS ***** */
}
#include <ctype.h>
//tells what a string is and ignores numbers
int get_word(char *s) {
int c;
do {
c = getchar();
if(c == EOF)
return(0);
} while(!isalpha(c));
do {
if(isupper(c))
c = tolower(c);
*s++ = c;
c = getchar();
} while(isalpha(c));
*s = 0;
return(1);
}