查找单词序列在文章中出现的次数

[期望]

对于测试
char *substrs[3] = {"ffff", "cindy", "Bill"};
char *str = "Hellocindy, BillGatesBill---cindy-ffffffxxx23424cindycindy";
找到的结果应该是：

"ffff" => 3,
"cindy" => 4,
"Bill" => 2

[抱怨]

c语言没有基础数据结构hash用来方便地表示上面这种结果，像perl,python都有，用起来很方便，C++通过STL的hash_map也能干这个活。

搜了一下，网上有把c++的STL移植到c上的，其中一个叫做libcstl,它的github地址是这里,有兴趣的同学可以看一下。不过作为技术练习，可以试着自己思考/动手来用c实现hash(hash_map)。

[思路]
如果用脚本语言来做，简直太简单了。
我C语言的思路是这样的：
对每一个子字符串，第一次从文章开头开始找，第二次从文章开头+1的位置开始找，......,若这一次找到的位置和上一次不一致，则认为子串又出现了一次。查找完一个子串后，分配填充找到的信息，链到链表中。然后开始下一个子串的查找。
查找使用的是strstr()函数，应该有更好的做法。
#include <string.h>

char *strstr(const char *haystack, const char *needle);

简单实现了一下，目前把所有功能都写在了一个函数里，更好的做法是把链表节点的创建、填充、插入、删除，查找子串出现次数等功能独立出来，结构会更清晰。

欢迎大家提出更好的做法。

[代码]

  1 #include <stdio.h>
  2 #include <assert.h>
  3 #include <stdlib.h>
  4 #include <string.h>
  5 
  6 struct info {
  7     char *str;
  8     int count;
  9     struct info *next;
 10 };
 11 
 12 typedef struct info * HEAD;
 13 typedef struct info * INFO;
 14 
 15 INFO get_substr_info(const char *str, char **substrs, int num);
 16 void get_substr_info_test();
 17 
 18 int main()
 19 {
 20     get_substr_info_test();
 21     return 0;
 22 }
 23 
 24 void get_substr_info_test()
 25 {
 26     char *substrs[3] = {"ffff", "cindy", "Bill"};
 27     char *str = "Hellocindy, BillGatesBill---cindy-ffffffxxx23424cindycindy";
 28     INFO rtn = get_substr_info(str, substrs, 3);
 29     while(rtn != NULL && rtn->next != NULL) {
 30         INFO ptr = rtn->next;
 31         printf("name=>%s,count=>%d
", ptr->str, ptr->count);
 32         rtn = rtn->next;
 33         free(ptr->str);
 34         free(ptr);
 35     }
 36 }
 37 
 38 INFO get_substr_info(const char *str, char **substrs, int num)
 39 {
 40     assert(str!=NULL && substrs != NULL);
 41     char *substr = NULL;
 42     char *tmpstr;
 43     int i = 0;
 44     char *lastpos = NULL;
 45     HEAD head = NULL;
 46     INFO info = NULL;
 47     INFO ptr = NULL;
 48     int count[num];
 49     int len;
 50 
 51     head = malloc(sizeof(struct info));
 52     head->next = NULL;
 53     ptr = head;
 54 
 55     while(i<num) {
 56         substr = substrs[i];
 57         len = strlen(substr);
 58 
 59         lastpos = tmpstr = str;
 60         count[i] = 0;
 61         while(*tmpstr != '') {
 62             char *rtn;
 63             if (tmpstr == str ) {
 64                 if ((rtn=strstr(tmpstr, substr)) != NULL) {
 65                     count[i]++;
 66                     lastpos = rtn;
 67                     //printf("  found %s %d times
", substr, count[i]);
 68                 }
 69             } else {
 70                 if (((rtn=strstr(tmpstr, substr)) != NULL) 
 71                 && rtn != lastpos) {
 72                     count[i]++;
 73                     lastpos = rtn;
 74                     //printf("  found %s %d times
", substr, count[i]);
 75                 }
 76             }
 77             tmpstr++;
 78         }
 79 
 80         //
 81         info = malloc(sizeof(struct info));
 82         memset(info, 0, sizeof(struct info));
 83         info->str = malloc(len+1);
 84         memcpy(info->str, substr, len);
 85         info->str[len] = '';
 86         info->count = count[i];
 87         info->next = NULL;
 88 
 89         //
 90         while(ptr->next != NULL) {
 91             ptr = ptr->next;
 92         }
 93         ptr->next = info;
 94         ptr = info;
 95 
 96         i++;
 97     }
 98 
 99     return head;
100 }

View Code