21ic电子技术开发论坛 › 已关闭版块 › 恩智浦MCU论坛 › 用二叉树统计单词出现的次数
返回列表 发新帖我要提问

[资料分享与下载] 用二叉树统计单词出现的次数

[复制链接]
1159|7
 楼主| 東南博士 发表于 2015-9-20 14:21 | 显示全部楼层 |阅读模式
ST, root, right, print, return
因为预先不知道出现的单词列表，无法方便地排序并使用折半查找；也不能分别对输入中的每个单词都执行一次线性查找，开销太大-->O(n^n)。
所以考虑使用二叉树的数据结构(O(n*logn))来组织这些单词，实现如下：
  • #include <stdio.h>  
  • #include <stdlib.h>  
  • #include <string.h>  
  • #include <ctype.h>  
  •   
  • #define MAXWORD 100  
  •   
  • /* a binary tree node */  
  • typedef struct tnode_ {  
  •     char *word;  
  •     int count;  
  •     struct tnode_ *left;  
  •     struct tnode_ *right;  
  • } tnode;  
  •   
  • void print_tree(tnode *root);  
  • tnode *add_tree(tnode *root, char *word);  
  • void free_node(tnode *root);  
  •   
  • char *copy_string(char *s) {  
  •     char *p = (char *)malloc(strlen(s)+1);  
  •     if(p != NULL) {  
  •         strcpy(p, s);  
  •     }  
  •   
  •     return p;  
  • }  
  •   
  • tnode *add_tree(tnode *p, char *word) {  
  •     int result;  
  •     if(p == NULL) {  
  •         p = (tnode *)malloc(sizeof(tnode));  
  •         p->word= copy_string(word); // Attention !  
  •         p->count = 1;  
  •         p->left = NULL;  
  •         p->right = NULL;  
  •     }  
  •     else {  
  •         result = strcmp(word, p->word);  
  •         if(result < 0) {  
  •             p->left = add_tree(p->left, word);  
  •         }  
  •         else if(result > 0) {  
  •             p->right = add_tree(p->right, word);  
  •         }  
  •         else {  
  •             p->count++;  
  •         }  
  •     }  
  •   
  •     return p;  
  • }  
  •   
  • void print_tree(tnode *p) {  
  •     if(p) {  
  •         print_tree(p->left);  
  •         printf("%s\t : %4d\n", p->word, p->count);  
  •         print_tree(p->right);  
  •     }  
  • }  
  •   
  • void free_node(tnode *p) {  
  •     if(p) {  
  •         free_node(p->left);  
  •         free_node(p->right);  
  •         free(p->word);  
  •         free(p);  
  •     }  
  • }  
  •   
  • int getword(char *word, int n) {  
  •     int c;  
  •     char *w = word;  
  •   
  •     while(isspace(c = getchar())) {  
  •         ;  
  •     }  
  •     if(c != EOF) {  
  •         *w++ = c;  
  •     }  
  •     if(!isalpha(c)) {  
  •         *w = '\0';  
  •         return c;  
  •     }  
  •     while(n > 0) {  
  •         c = getchar();  
  •         if(isalnum(c)) {  
  •             *w++ = c;  
  •         }  
  •         else {  
  •             break;  
  •         }  
  •         n--;  
  •     }  
  •   
  •     *w = '\0';  
  •     return w[0];  
  • }  
  •   
  • int main() {  
  •     tnode *root = NULL; // 指针一定要初始化为NULL  
  •     char word[MAXWORD];  
  •   
  •     while((getword(word, MAXWORD)) != EOF) {  
  •         if(isalnum(word[0])) {  
  •             root = add_tree(root, word);  
  •         }  
  •     }  
  •   
  •     print_tree(root);  
  •   
  •     free_node(root);  
  •   
  •     return 0;  
  • }  

回复

收藏 举报

相关帖子
cowboy2014 发表于 2015-9-20 20:34 | 显示全部楼层
这个也是C语言的知识，楼主够辛苦的
回复

收藏 举报

FSL_TICS_ZJJ 发表于 2015-9-21 09:54 | 显示全部楼层
感谢楼主资料分享。
资料分享帖就没必要用未结帖形式了。
回复

收藏 举报

 楼主| 東南博士 发表于 2015-9-25 14:39 | 显示全部楼层
是吧！好的。
另外，飞思卡尔的有没有一些关于射频方面的资料？
回复

收藏 举报

芙蓉洞 发表于 2015-9-26 21:53 | 显示全部楼层
复制
  1. #include <stdio.h>  
    

  2. #include <stdlib.h>  
    

  3. #include <string.h>  
    

  4. #include <ctype.h>  
    

  5.   
    

  6. #define MAXWORD 100  
    

  7.   
    

  8. /* a binary tree node */  
    

  9. typedef struct tnode_ {  
    

  10.     char *word;  
    

  11.     int count;  
    

  12.     struct tnode_ *left;  
    

  13.     struct tnode_ *right;  
    

  14. } tnode;  
    

  15.   
    

  16. void print_tree(tnode *root);  
    

  17. tnode *add_tree(tnode *root, char *word);  
    

  18. void free_node(tnode *root);  
    

  19.   
    

  20. char *copy_string(char *s) {  
    

  21.     char *p = (char *)malloc(strlen(s)+1);  
    

  22.     if(p != NULL) {  
    

  23.         strcpy(p, s);  
    

  24.     }  
    

  25.   
    

  26.     return p;  
    

  27. }  
    

  28.   
    

  29. tnode *add_tree(tnode *p, char *word) {  
    

  30.     int result;  
    

  31.     if(p == NULL) {  
    

  32.         p = (tnode *)malloc(sizeof(tnode));  
    

  33.         p->word= copy_string(word); // Attention !  
    

  34.         p->count = 1;  
    

  35.         p->left = NULL;  
    

  36.         p->right = NULL;  
    

  37.     }  
    

  38.     else {  
    

  39.         result = strcmp(word, p->word);  
    

  40.         if(result < 0) {  
    

  41.             p->left = add_tree(p->left, word);  
    

  42.         }  
    

  43.         else if(result > 0) {  
    

  44.             p->right = add_tree(p->right, word);  
    

  45.         }  
    

  46.         else {  
    

  47.             p->count++;  
    

  48.         }  
    

  49.     }  
    

  50.   
    

  51.     return p;  
    

  52. }  
    

  53.   
    

  54. void print_tree(tnode *p) {  
    

  55.     if(p) {  
    

  56.         print_tree(p->left);  
    

  57.         printf("%s\t : %4d\n", p->word, p->count);  
    

  58.         print_tree(p->right);  
    

  59.     }  
    

  60. }  
    

  61.   
    

  62. void free_node(tnode *p) {  
    

  63.     if(p) {  
    

  64.         free_node(p->left);  
    

  65.         free_node(p->right);  
    

  66.         free(p->word);  
    

  67.         free(p);  
    

  68.     }  
    

  69. }  
    

  70.   
    

  71. int getword(char *word, int n) {  
    

  72.     int c;  
    

  73.     char *w = word;  
    

  74.   
    

  75.     while(isspace(c = getchar())) {  
    

  76.         ;  
    

  77.     }  
    

  78.     if(c != EOF) {  
    

  79.         *w++ = c;  
    

  80.     }  
    

  81.     if(!isalpha(c)) {  
    

  82.         *w = '\0';  
    

  83.         return c;  
    

  84.     }  
    

  85.     while(n > 0) {  
    

  86.         c = getchar();  
    

  87.         if(isalnum(c)) {  
    

  88.             *w++ = c;  
    

  89.         }  
    

  90.         else {  
    

  91.             break;  
    

  92.         }  
    

  93.         n--;  
    

  94.     }  
    

  95.   
    

  96.     *w = '\0';  
    

  97.     return w[0];  
    

  98. }  
    

  99.   
    

  100. int main() {  
    

  101.     tnode *root = NULL; // 指针一定要初始化为NULL  
    

  102.     char word[MAXWORD];  
    

  103.   
    

  104.     while((getword(word, MAXWORD)) != EOF) {  
    

  105.         if(isalnum(word[0])) {  
    

  106.             root = add_tree(root, word);  
    

  107.         }  
    

  108.     }  
    

  109.   
    

  110.     print_tree(root);  
    

  111.   
    

  112.     free_node(root);  
    

  113.   
    

  114.     return 0;  
    

  115. }  
回复

收藏 举报

Mancherstun 发表于 2015-9-27 14:36 | 显示全部楼层
二叉树是不是倒立的树形啊？
回复

收藏 举报

 楼主| 東南博士 发表于 2015-9-28 21:44 | 显示全部楼层
都差不多的！
回复

收藏 举报

lovecat2015 发表于 2015-9-29 09:04 | 显示全部楼层
最近看ucos 的源码也提到了二叉树
回复

收藏 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 注册

本版积分规则

東南博士

385

主题

6103

帖子

35

粉丝
快速回复 在线客服 返回列表 返回顶部