《编程珠玑》第15章
编程珠玑第15章是讲关于字符串的一系列问题和基本常见的算法的。
在最近的编程过程当中经常要和字符串打交道，最近在做的是Web服务器。
可昨天在折腾一个github的GUI软件的时候，不小心把已经写好的代码都删除了，这是我们都不想看到的。T。T|||
那个github的GUI软件叫GitKraken，界面很酷炫，网上有说这个软件有BUG的，目前没碰到。因为对git的要求不高，基本是提交日常书写的代码和日常的练习项目，所以一个GUI就足够了。
有关字符串的算法
先上变成主机里面的几个代码，这些代码都是伪代码，类似于C/C++；
#include <iostream>
#include <set>
using namespace std;
int main(void)
{
set<string> S;
set <string> :: iterator j;
string t;
while(cin >> t)
S.insert(t);
for(j = S.begin();j != S.end();++j){
cout << *j << " ";
}
cout << endl;
return 0;
}
这段代码是循环读取输入的单词，并且以此将其插入到集合S中。并以此将S中的单词输出来。
关于这个while循环来讲，我们通过EOF来退出循环。在Linux中，我们一般使用Ctrl+D来实现EOF。
关于SET，很有意思的事情是，单词在其中是按字典序排序的，STL库还是得多用啊，不试不知道。
#include <iostream>
#include <map>
using namespace std;
int main(void)
{
map<string,int> M;
map<string,int> :: iterator j;
string t;
while(cin >> t)
M[t]++;
for(j = M.begin();j != M.end();++j){
cout << j -> first << " ";
cout << j -> second;
}
cout << endl;
return 0;
}
//这部分代码利用map容器实现对每个单词出现的个数进行计数。
//因为map的迭代器是一个pair类型，存在键值对。
因为map容器本身是将数据建立起映射关系，底层实现是基于红黑树RB-TREE。
自己造的轮子才滚得爽T~T
编程珠玑第十五章page177提到为了减少map处理时间，可以自己建立散列表。即hash表。
总所周知，hash表存在hash冲突，因为说不定两个不同的单词可能会散列到同一个位置。这个时候，我们将我们的每一个节点设计成链表节点，这样，在同一个散列位置，可以通过链表将散列到同一位置的数据连接起来。
stringHanlde_v1/string1.cpp(代码戳我的Github！)
在书中的总结是自己定制的散列表比C++STL的映射快一个数量级。我不会做测试，所以。。。。。有谁会做的写在评论里啊。 ￣O￣)ノ
以上的代码实现的总的来说就是对单词的统计，比如说你有一本书的文件，你可以通过读取文件来进行对文中的字符的统计。当然，我们一般认为两个空格之间为一个单词，而且这只限于英文。中文的单词判定自我认为首先需要一个不断更新的词库作为基础才可以。
书中小结
平衡搜索树将字符串看作不可分割的对象进行操作，STL的set和map中大部分实现都使用这种结构。平衡搜索树中的元素始终处于有序状态，从而很容易执行寻找前驱节点或者顺序输出元素之类的操作。
散列则需要深入字符串的内部，计算散列函数并将关键字分散到一个较大的表中。
散列方法的平均速度很快，但是缺乏平衡树提供的最欢情况性能保证，也不能支持其他涉及顺序的操作。
这也很容易通过实现代码来体会。
一天都是满课，在课上老师讲的听不懂，嘈杂的教室也看不下去，今天跌跌撞撞认真的看完了一部分书，并且能够总结整理下来，这是一种认知转换为实践的过程，还是不错的。有机会逛一下我的github@starboom。啥也没有，正在种地。
英俊的尔康.JPG
网友评论