Home PC Games Linux Windows Database Network Programming Server Mobile  
           
  Home \ Programming \ C language binary tree counts words     - 5 fast Node.js application performance tips (Programming)

- Ceph distributed storage system is installed on a CentOS 7.1 (Server)

- Lazarus for Raspbian installation (Linux)

- To share some very useful Vim command (Linux)

- Eclipse remove all comments and code spaces (Linux)

- Java precision four operations (Programming)

- Customize the 404 error page Nginx (Server)

- Basic Tutorial: Linux novice should know 26 commands (Linux)

- namespace mechanism Linux kernel analysis (Linux)

- Guide: Trickle restrict application bandwidth usage (Linux)

- RHEL 7.1 compile and install Ganglia 3.7.1 (Server)

- Shuffle Process Arrangement in MapReduce (Server)

- How do you turn on and off IPv6 address on Fedora (Linux)

- Android use canvas board painting (Programming)

- Distributed Hadoop1.2.1 cluster installation (Server)

- Linux system with a firewall to prevent the DOS attack (Linux)

- To explore the caching mechanism for Android ListView (Programming)

- Vi syntax highlighting settings (Linux)

- How do I upgrade from Ubuntu 15.04 to Ubuntu 15.10 (Linux)

- MariaDB phpMyAdmin installation and configuration issues to resolve under CentOS7 (Database)

 
         
  C language binary tree counts words
     
  Add Date : 2018-11-21      
         
         
         
  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;
     
         
         
         
  More:      
 
- Elementary OS Freya global menu (Linux)
- Ubuntu installation under Scrapy (Linux)
- Linux System shutdown procedures (Linux)
- Ubuntu 12.04 installation instructions under GAMIT10.40 (Linux)
- Linux Troubleshooting: How to save the status of the SSH session is closed (Linux)
- Debian SSD ext4 4K aligned (Linux)
- VNC connection VMware vSphere ESXi 5.5 (Linux)
- Ubuntu amend resolv.conf restart failure problem (Linux)
- Java in several ways of using MongoDB (Programming)
- Using Linux command line and execute PHP code (Programming)
- Go performed using iOS and Android programming (Programming)
- Depth Java Singleton (Programming)
- How to make GRub instead of the default Ubuntu software center (Linux)
- Command line tool Tmux (Linux)
- Build Docker based MongoDB replication cluster environment (Database)
- Lazarus IDE Start Basics Tutorial (Linux)
- Linux raw socket (Programming)
- Ubuntu system process is bound CPU core (Linux)
- The several technical presentation Raid under Linux (Linux)
- Linux virtual machine settings network, hostname ssh access (Linux)
     
           
     
  CopyRight 2002-2022 newfreesoft.com, All Rights Reserved.