程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> 關於C語言 >> C語言實現二叉樹-利用二叉樹統計單詞數目

C語言實現二叉樹-利用二叉樹統計單詞數目

編輯:關於C語言

C語言實現二叉樹-利用二叉樹統計單詞數目


Problem   我需要統計的單詞是在程序直接硬編碼的;   這樣做得原因是省略了文件輸入輸出所帶來的困惑;   我的每篇文章,一般只說一個主題;   這樣也方便我日後復習;       Solution   首先,我們需要定義一個結構體,如下代碼所示:    
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;

 

注意到,我們假設最長的單詞定義為一個常量,在這裡我覺得目前32這個長度應該可以啦;   如果要統計的文章是化學論文,建議你再加大數字,因為化學式通常都很長;   然後是,我們的結構體;這應該很容易理解的;   由於C語言沒有提供我想要的BOOL類型,因此自己動手寫啦下面的代碼;   這個定義非常有用,通常它比define更加值得推薦;   enum BOOL {     NO,     YES };     typedef enum BOOL BOOL; 接下來,我們需要知道單詞之間是如何比較大小的;   因此,需要一個函數叫做cmp;   代碼實現如下:    
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;
}

 

  同時遍歷兩個字符串,然後對返回值進行一個處理;   這樣只會返回兩種情況NO/YES,不然的話會返回三種值(-1,0,正數);   那樣的話,不利於我們往後的工作;   接下來呢,就是如果返回YES我們該(如何) (做什麼);   如果返回NO我們又該(如何)(做什麼);   因此,我們需要一個insert函數,把數據的兩種不同分別插入左右子樹;    
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++;
    }
} 
 

 

  這段代碼和前面提到的(C語言實現二叉樹)裡面的代碼幾乎一樣的,哪裡有詳細介紹;   這裡主要講解一下注釋有issue code的那行,如果這行不修改,程序將會蹦潰;   但是,我會故意不馬上修改它,繼續往下寫;   我們需要一個函數,銷毀節點:    
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);
    }
} 

 

    我們把頭文件stdio.h/stdlib.h引入後;   把主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);
}

 

    gcc編譯運行得到如下結果:       果然,我們的issue code有問題,原因是字符串不能像其他的,例如int類型一樣直接用‘=’號賦值;   所以我們需要一個cpy函數:   void mystrcpy(char *s, char *t) {     while ((*s++ = *t++) != '\0')         ; } 所有代碼如下:    
#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   那麼這個程序已經完成啦!   還有很多可以優化的,也可以增加更多的功能;   例如,查找特定字符出現的次數;   或者特定字符所出現的行數,等等都可以;   我們會在日後慢慢完善;    

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved