严老太，在您面前小孙孙我实在心智底下啊！一个AVL就把我整的团团转，单向右旋，单向左旋，双向旋转先左后右，双向旋转先右后左，很简单的道理，您就是不肯轻易说出来，在那转啊转的，貌似很神秘的样子！
在构造AVL树的时候，会出现插入某个节点后输不再平衡的情况，这时候只需要找到离插入点最近的、平衡因子不合法的节点，调整以此节点为根的子树(*)，使其平衡因子合法，其实就是使这棵子树(*)的高度与插入节点前相比不发生变化。具体的调整策略因具体情况而异，但原则都是一样的：首先应该明确根节点大于左孩子而小于右孩子，另外，调整后的子树(*)的根是一定会发生变化的，且变化后的子树应该满足平衡条件，即平衡因子为1，0，-1之一。
AVL是一种二叉搜索树(Binary Search Tree)，被称为平衡树(Balanced Binary Tree)，由Adelsonr Velskii 和Landis 提出并以他们的名字命名。
今天看严蔚敏老太太的数据结构，她老人家是这么描述AVL的：AVL，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差(平衡因子：BF)的绝对值不超过1。看着这么个定义很别扭，总觉得对平衡因子的要求比较弱，也可能是我悟性较弱吧，在这句话上我很是下了一番功夫……如果这样来定义的话，可能会让我更容易理解一些：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | class Match { public: Match(): repos(NULL){} Match(const string& main, const string& mod) :repos(new int[mod.size()]), m_main(main), m_mod(mod) {} ~Match() { delete [] repos; } //~ kmp搜索，默认从主串0位置处开始， //~ 匹配成功返回匹配开始的索引，否则返回-1 int strkmp(size_t pos = 0); //~ 重设主串与模式串 void reset(const string& main, const string& mod); private: int * repos; string m_main; //~ 主串 string m_mod; //~ 模式串 //~ 生成重定位的索引值 void gen_rps(); }; |
其实，我最初写的不是这样子滴，对比上面的程序，看看下面这个哪里会出问题？
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | string multiply(const string &l, const string &r) { size_t lenl = l.size(); size_t lenr = r.size(); string result(lenl+lenr, '\0'); for(size_t i = 0; i < lenl; ++i) for(size_t j = 0; j < lenr; ++j) { result[i + j + 1] += ctoi(l[i]) * ctoi(r[j]); } for(size_t i = lenl + lenr-1 ; i > 0; --i) { result[i - 1] += (unsigned char)result[i] / 10; result[i] = (unsigned char)result[i] % 10 + '0'; } if(result[0] == 0) result.erase(0, 1); else result[0] += '0'; return result; } |
看了Linux内核代码linux/string.h中的一些字符串操作函数，有几个写的真是漂亮！
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /** * strstr - Find the first substring in a %NUL terminated string * @s1: The string to be searched * @s2: The string to search for */ char *strstr(const char *s1, const char *s2) { int l1, l2; l2 = strlen(s2); if (!l2) return (char *)s1; l1 = strlen(s1); while (l1 >= l2) { l1--; if (!memcmp(s1, s2, l2)) return (char *)s1; s1++; } return NULL; } |
C/C++中，为了读或写一个文件，我们需要首先需要调用open来打开相应的文件，完成对该文件的访问(read, write)后，再调用close将之关闭。那么为什么不再read和write内部完成打开和关闭文件的操作呢？这是因为打开一个文件时操作系统需要根据文件名，在文件系统中查找文件的位置、检验文件的属性(读、写、执行、追加等)进而验证本次操作是否有相应的权限，对于write调用，还需要为文件分配存储(磁盘)空间。所有这些操作都是非常费时的，于是操作系统打开文件时，就在内核中相应的文件打开表中添加该文件的文件指针(打开该文件的进程也会有自己的文件表)，结束对文件的访问后，再从相应的文件表中删除文件指针表项。
记
为列向量
，假设去掉
之后，剩下来的数可以分为和相等的两等分子集，那么存在行向量
使得
，其中
个位置为0，其余
个元素恰好有
个1和-1。
令矩阵
，其中
的第
，我们证明
令
为同样大小的全1矩阵，那么
除了对角线上都是1之外，其余位置都是偶数，这样矩阵行列式
的表达式中有一个唯一的奇数，这意味着
，从而
，所以
。
故
就是它的唯一解。
一直没弄明白在控制台下如何实现实时更新、无闪烁的时间显示，今天偶然发现回车(CR)和换行(LF)是不同的，在C语言中分别用转义字符’\r’和’\n’表示。回车的语义应该是”光标”移动到当前行的行首，而换行是”光标”移动到下一行，并没有定义一定移动到行首。这样，这里要实现的控制台下实时更新、无闪烁的小时钟就可以用相关的时间函数和回车符来完成：
Linux 为每个进程提供了三个定时器：
如果两个或多个进程永久等待某个事件而该事件只能由这些等待进程的某一个引起，那么死锁就会发生。死锁的发生需要满足四个必要条件：
