1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | /* * pre存放先序序列， * in存放中序序列， * n为结点个数， * 返回二叉树根指针 */ BTree CreateBT(Type * pre, Type * in, int n) { if(n <= 0) return NULL; BTree bt = new BTNode; Type * p; int k; bt->data = *pre; for(p = in; p < in + n; ++p) if(*pre == *p) break; k = p - in; bt->lchild = CreateBT(pre+1, in, k); bt->rchild = CreateBT(pre+k+1, p+1, n-k-1); return bt; } |
严老太，在您面前小孙孙我实在心智底下啊！一个AVL就把我整的团团转，单向右旋，单向左旋，双向旋转先左后右，双向旋转先右后左，很简单的道理，您就是不肯轻易说出来，在那转啊转的，貌似很神秘的样子！
在构造AVL树的时候，会出现插入某个节点后输不再平衡的情况，这时候只需要找到离插入点最近的、平衡因子不合法的节点，调整以此节点为根的子树(*)，使其平衡因子合法，其实就是使这棵子树(*)的高度与插入节点前相比不发生变化。具体的调整策略因具体情况而异，但原则都是一样的：首先应该明确根节点大于左孩子而小于右孩子，另外，调整后的子树(*)的根是一定会发生变化的，且变化后的子树应该满足平衡条件，即平衡因子为1，0，-1之一。
AVL是一种二叉搜索树(Binary Search Tree)，被称为平衡树(Balanced Binary Tree)，由Adelsonr Velskii 和Landis 提出并以他们的名字命名。
今天看严蔚敏老太太的数据结构，她老人家是这么描述AVL的：AVL，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差(平衡因子：BF)的绝对值不超过1。看着这么个定义很别扭，总觉得对平衡因子的要求比较弱，也可能是我悟性较弱吧，在这句话上我很是下了一番功夫……如果这样来定义的话，可能会让我更容易理解一些：
- 根的左子树和右子树的高度差的最大值为1，空树的高度为0。
- 根的左子树和右子树都是AVL树。
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中的一些字符串操作函数，有几个写的真是漂亮！
char * strstr(const char*, const char*)
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调用，还需要为文件分配存储(磁盘)空间。所有这些操作都是非常费时的，于是操作系统打开文件时，就在内核中相应的文件打开表中添加该文件的文件指针(打开该文件的进程也会有自己的文件表)，结束对文件的访问后，再从相应的文件表中删除文件指针表项。
Using Algebra：
记
为列向量
，假设去掉
之后，剩下来的数可以分为和相等的两等分子集，那么存在行向量
使得
，其中
个位置为0，其余
个元素恰好有
个1和-1。
令矩阵
，其中
的第
，我们证明
令
为同样大小的全1矩阵，那么
除了对角线上都是1之外，其余位置都是偶数，这样矩阵行列式
的表达式中有一个唯一的奇数，这意味着
，从而
，所以
。
故
就是它的唯一解。
一直没弄明白在控制台下如何实现实时更新、无闪烁的时间显示，今天偶然发现回车(CR)和换行(LF)是不同的，在C语言中分别用转义字符’\r’和’\n’表示。回车的语义应该是”光标”移动到当前行的行首，而换行是”光标”移动到下一行，并没有定义一定移动到行首。这样，这里要实现的控制台下实时更新、无闪烁的小时钟就可以用相关的时间函数和回车符来完成：
Linux 为每个进程提供了三个定时器：
- ITIMER_REAL: 给一个指定的时间间隔，按照实际的时间来计数，发出SIGALRM信号；
- ITIMER_VIRTUAL: 当进程执行的时候才计数，发出SIGVTALRM信号；
- ITIMER_PROF: 当进程执行或者是系统为进程调度的时候计数，发出SIGPROF信号。这个和ITIMER_VIRTUAL联合，常用来计算系统内核时间和用户时间。
