eriol
- 浏览: 407918 次
- 性别:
- 来自: 上海
-
最新评论
-
handong1587：
代码有一处错.query函数最后一行return的应该是:re ...
RMQ -
yuandong0828：
简洁的特别透彻细致，多谢，
虚函数、虚指针和虚表 -
adam_zs：
谢谢分享！
括号匹配问题 -
hongloumengyanzxw：
good[b][/b]
dup和dup2函数 -
chriszeng87：
最后第二种情况右下角的那个点是不是可以看作相交点的?上面的那种 ...
判断两个链表是否相交
文章列表
关于虚函数的背景知识
用virtual关键字申明的函数叫做虚函数，虚函数肯定是类的成员函数。
存在虚函数的类都有一个一维的虚函数表叫做虚表。类的对象有一个指向虚表开始的虚指针。虚表是和类对应的，虚表指针是和对象 ...
C++中的虚函数的作用主要是实现了多态的机制。关于多态，简而言之就是用父类型别的指针指向其子类的实例，然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”，这是一种泛型技术。所谓泛型技术，说白了就是试图使用不变的代码来实现可变的算法。比如：模板技术，RTTI技术，虚函数技术，要么是试图做到在编译时决定，要么试图做到运行时决定。
虚函数表
对C++了解的人都应该知道虚函数（Virtual Function）是通过一张虚函数表（Virtual Table）来实现的。简称为V-Table。 在这个表中，主要是一个类的虚函数的地址表，这张表解决了继承、覆 ...
函数指针
在程序运行中，函数代码是程序的算法指令部分，它们和数组一样也占用存储空间，都有相应的地址。可以使用指针变量指向数组的首地址，也可以使用指针变量指向函数代码的首地址，指向函数代码首地址的指针变量称为函数指针。
1. 函数指针定义
函数类型 (*指针变量名) (形参列表);
“函数类型”说明函数的返回类型，由于“()”的优先级高于“*”，所以指针变量名外的括号必不可少，后面的“形参列表”表示指针变量指向的函数所带的参数列表。
例如：
int (*f)(int x);
double (*ptr)(double x);
...
关于字节序(大端法、小端法)的定义
《UNXI网络编程》定义：术语“小端”和“大端”表示多字节值的哪一端(小端或大端)存储在该值的起始地址。小端存在起始地址，即是小端字节序；大端存在起始地址，即是大端字节序。
也可以说：
小端法(Little-Endian)就是低位字节排放在内存的低地址端即该值的起始地址，高位字节排放在内存的高地址端。
大端法(Big-Endian)就是高位字节排放在内存的低地址端即该值的起始地址，低位字节排放在内存的高地址端。
举个简单的例子，对于整形0x12345678。它在大端法和小端法的系统内中，分别以如下所示的方式存放。
...
memset
用来对一段内存空间全部设置为某个字符，一般用在对定义的字符串进行初始化为''或'\0'。
函数原型：void *memset(void *s, int c, size_t n);
例如：
char a[100];
memset(a, '\0', sizeof(a));
memset也可以方便的清空一个结构类型的变量或数组。
struct sample_struct
{
char csName[16];
int iSeq;
int iType;
};
struct samp ...
首先看一个例子：
假设有3篇文章，file1, file2, file3，文件内容如下：
file1 (单词1，单词2，单词3，单词4....)
file2 (单词a，单词b，单词c，单词d....)
file3 (单词1，单词a，单词3，单词d....)
那么建立的倒排索引就是这个样子：
单词1 (file1,file3)
单词2 (file1)
单词3 (file1,file3)
单词a (file2, file3)
....
倒排索引的概念很简单：就是将文件中的单词作为关键字，然后建立单词与文件的 ...
C++的static有两种用法：面向过程程序设计中的static和面向对象程序设计中的static。前者应用于普通变量和函数，不涉及类；后者主要说明static在类中的作用。
一、面向过程设计中的static
1、静态全局变量
在全局变量前，加上关键字static，该变量就被定义成为一个静态全局变量。我们先举一个静态全局变量的例子，如下：
//Example 1
#include <iostream.h>
void fn();
static int n; //定义静态全局变量
void main()
{
n=2 ...
五大内存分区
在C++中，内存分成5个区，他们分别是堆、栈、自由存储区、全局/静态存储区和常量存储区。
栈：就是那些由编译器在需要的时候分配，在不需要的时候自动清除的变量的存储区。 里面的变量通常是局部变量、函数参数等。
堆：就是那些由new分配的内存块，他们的释放编译器不去管，由我们的应用程序去控制，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收。
自由存储区：就是那些由malloc等分配的内存块，他和堆是十分相似的，不过它是用free来结束自己的生命的。
全局/静态存储区：全局变量和静态变量被分配到同一块内存中，在以前 ...
括号匹配问题：
import java.util.Stack;
public class SymbolMatch {
public boolean check(String str) {
Stack<Character> s = new Stack<Character>();
boolean match = true;
for (int i = 0; i < str.length() && match; i++) {
try {
switch (str.charAt(i)) {
...
C++在类的构造函数中，可以两种方式初始化成员数据：
在构造函数的实现中，初始类的成员数据。
还可以定义初始化成员列表 (Initializer list) 来初始化成员数据。
那么我们在什么情况下该使用初始化成员列表呢？
需要初始化的数据成员是对象。
需要初始化的类成员是const对象或者引用对象。
解决没有默认构造函数的类成员对象的生成。
在继承里面，只有初始化列表可以构造父类的private成员。
1. 需要初始化的数据成员是对象。
#include <stdio.h>
class point
{
protecte ...
Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，例如，英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。
Trie的核心思想是用空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。当然，如果系统中存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存，这也是trie树的一个缺点。
Trie树的性质
Trie树的基本性质可以归纳为：
根节点不包含字符，除根节点意外每个节点只包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节 ...
LRU表示Least Recently Used，即最近最少被使用的页面替换算法。其理论基础是局部性原理，也就是说最近被访问的对象将在不久以后再次被访问。
对于LRU算法，可以使用一个链表和hashmap来实现。链表中的节点表示缓存的页面，链表中的第一个元素就是要被替换的元素，所以替换的复杂度是O(1)。同时，还维护一个hashmap来建立访问对象和缓存页面的映射关系。
当需要访问某个对象时，先从hashmap中查看该对象是否在缓存中，如果在，则将该缓存页面从链表中取出并插入到链表尾部，并访问对象。否则，从链表头取出一个缓存页面，将要访问的对象写入该缓存并插入到链表尾部，并且在h ...
Lock-free 算法的基础是 CAS (Compareand-Swap) 原子操作。当某个地址的原始值等于某个比较值时，把值改成新值，无论有否修改，返回这个地址的原始值。目前的cpu 支持最多64位的CAS。并且指针 p 必须对齐。
注：原子操作指一个cpu时钟周期内就可以完成的操作，不会被其他线程干扰。
一般的 CAS 使用方式是：
假设有指针 p, 它指向一个 32 位或者64位数，复制p 的内容（*p）到比较量 cmp （原子操作）。
基于这个比较量计算一个新值 xchg （非原子操作）。
调用 CAS 比较当前 *p 和 cmp, 如果相等把 ...
常量指针：即指向常量的指针。其定义为：
const int* p;
它表示p是一个指向const int的指针，也就是说p指向的对象的内容不能改变，但是p可以指向其他的对象。所以，在这里不需要对p进行初始化，因为p可以指向任何东西（p不是一个const），但它所指的东西是不能被改变的。
指针常量：即指针是const类型的。其定义为：
int d = 1;
int* const p = &d;
它表示p是一个指向int的const指针，也就是说p不能再指向其他的对象，这个指针是const的。因此，编译器要求在定义p时给它一个初始值，这个值在指 ...
链表逆序，即将原先的链表 a->b->c->d， 变为 d->c->b->a。需要使用三个指针来进行操作。
public int* reverse(int* head) {
int* front = head;
int* back = null;
int* temp;
while (front != null) {
temp = font - > next;
font -> next = back;
back = font;
font = temp;
}
return bac ...