| |
Tencent has just participated in the 2015 online mock exams; the first question is the word count program design four big questions; to remember this day, today I'm going to look through the code; I will use the core data structure is a binary tree ;
Problem
I need to count the words are hard-coded in the program directly; doing so because omit the file input and output brought about confusion; my each article, said only a general topic; I would also facilitate the future review;
Solution
First, we need to define a structure, as shown in the code:
const int LONGEST_WORD = 32; // The longest word size
struct binary_tree {
char str [LONGEST_WORD];
int count;
struct binary_tree * left;
struct binary_tree * right;
};
typedef struct binary_tree node;
Note that we assume that the longest word is defined as a constant, where I think the length of this 32 should be all right; if you want to count the article is a chemical paper, I suggest you increase the number, since the formula is usually very long; and is that our structures; this should be easy to understand; because the C language does not provide the type BOOL I want, write it yourself thus the following code; this definition is useful, it is usually more popular than define;
enum BOOL {
NO,
YES
};
typedef enum BOOL BOOL;
Next, we need to know how to compare the size of the between words;
Therefore, a function called cmp;
Code as follows:
BOOL cmp (char * s, char * t)
{
int i;
for (i = 0; s [i] == t [i]; i ++)
if (s [i] == '\ 0')
return NO;
? Return (s [i] - t [i]) <0 NO: YES;
}
While traversing two strings and returns the value of a process;
This will only return two cases NO / YES, otherwise returns three values (-1, 0, positive number);
In that case, it is not conducive to our future work;
Then, that is, if we return YES (what) (what to do);
If it returns NO should we (how) (what to do);
Therefore, we need to insert a function, the left and right respectively inserted into two different sub-tree data;
void insert (node ** tree, char * val) {
node * temp = NULL;
if (! (* tree)) {
temp = (node *) malloc (sizeof (node));
temp-> left = temp-> right = NULL;
temp-> str = val; // issue code ...
temp-> count = 1;
* Tree = temp;
return;
}
if (cmp (val, (* tree) -> str)) {
insert (& (* tree) -> left, val);
} Else if (cmp (val, (* tree) -> str)) {
insert (& (* tree) -> right, val);
} Else {
(* Tree) -> count ++;
}
}
This code and the aforementioned (C language binary tree) inside the code is almost the same, where there is detailed; here mainly explain the issue code annotated with the line, if this line is not modified, the program will jump collapse; However, I will not intentionally modify it right away and continue to write down; we need a function, the destruction of nodes:
void deltree (node * tree) {
if (tree) {
deltree (tree-> left);
deltree (tree-> right);
free (tree);
}
}
In order to view our results, we need a way to navigate;
Here we chose it in order!
void print_inorder (node * tree) {
if (tree) {
print_inorder (tree-> left);
printf ( "[% s \ t \ t \ t] count: [% d] \ n", tree-> str, tree-> count);
print_inorder (tree-> right);
}
}
We head file stdio.h / stdlib.h after introduction;
The main int main (int argc, char ** arg {
node * root;
node * tmp;
// Int i;
root = NULL;
/ * Inserting nodes into tree * /
insert (& root, "hello");
insert (& root, "hey");
insert (& root, "hello");
insert (& root, "ok");
insert (& root, "hey");
insert (& root, "hey");
insert (& root, "hey");
printf ( "In Order Display \ n");
print_inorder (root); / * Deleting all nodes of tree * /
deltree (root);
}
Sure enough, our issue code in question because the string can not be like the other, such as an int directly with the '=' assignment;
So we need a function cpy:
void mystrcpy (char * s, char * t)
{
while ((* s ++ = * t ++)! = '\ 0')
;
}
All code is as follows:
#include < stdio.h >
#include < stdlib.h >
const int LONGEST_WORD = 32; // The longest word size
struct binary_tree {
char str [LONGEST_WORD];
int count;
struct binary_tree * left;
struct binary_tree * right;
};
typedef struct binary_tree node;
enum BOOL {
NO,
YES
};
typedef enum BOOL BOOL;
BOOL cmp (char * s, char * t)
{
int i;
for (i = 0; s [i] == t [i]; i ++)
if (s [i] == '\ 0')
return NO;
? Return (s [i] - t [i]) <0 NO: YES;
}
void mystrcpy (char * s, char * t)
{
while ((* s ++ = * t ++)! = '\ 0')
;
}
void insert (node ** tree, char * val) {
node * temp = NULL;
if (! (* tree)) {
temp = (node *) malloc (sizeof (node));
temp-> left = temp-> right = NULL;
// Temp-> str = val; // issue code ...
mystrcpy (temp-> str, val);
temp-> count = 1;
* Tree = temp;
return;
}
if (cmp (val, (* tree) -> str)) {
insert (& (* tree) -> left, val);
} Else if (cmp (val, (* tree) -> str)) {
insert (& (* tree) -> right, val);
} Else {
(* Tree) -> count ++;
}
}
void deltree (node * tree) {
if (tree) {
deltree (tree-> left);
deltree (tree-> right);
free (tree);
}
}
void print_inorder (node * tree) {
if (tree) {
print_inorder (tree-> left);
printf ( "[% s \ t \ t \ t] count: [% d] \ n", tree-> str, tree-> count);
print_inorder (tree-> right);
}
}
int main (int argc, char ** argv)
{
node * root;
node * tmp;
// Int i;
root = NULL;
/ * Inserting nodes into tree * /
insert (& root, "hello");
insert (& root, "hey");
insert (& root, "hello");
insert (& root, "ok");
insert (& root, "hey");
insert (& root, "hey");
insert (& root, "hey");
printf ( "In Order Display \ n");
print_inorder (root);
/ * Deleting all nodes of tree * /
deltree (root);
}
Discussion
Then this procedure has been completed it!
There are many that can be optimized, it can also add more features;
For example, to find the number of times a specific character appears;
Or a specific number of lines of characters appearing, etc. can be; |
|
|
|