编码与字符

字符(集):中

字节:对应的二进制流byte

字符串(编码):字符与字节的映射关系:ANSI(多字节)字符串,Unicode (宽字节)字符串,(ANSI:0.一个字符可能是多个字节存储,1.不通国家字符集不一样,会有相同的字节映射,2.同一字符,不通编码规范 也可能对应不同的字符。)(Unicode :0.不同国家的字符集,不会有冲突的字节映射,是唯一的1.不同编码规范,最终可能对应不同的字符(为了省字节会添加一些识别信息,但去掉这些识别信息最终的值是一样的))

编码规范:同一编码的不通实现方式:UTF-8:可变长,节省Unicode 编码字符的空间。

编码转换:

把 UNICODE 字符串通过 ANSI 编码转化为“字节串”时,根据各自编码的规定,一个 UNICODE 字符可能转化成一个字节或多个字节。
反之,将字节串转化成字符串时,也可能多个字节转化成一个字符。比如,[0xD6, 0xD0] 这两个字节,通过 GB2312 转化为字符串时,将得到 [0x4E2D] 一个字符,即 ‘中’ 字。
“ANSI 编码”的特点:
1. 这些“ANSI 编码标准”都只能处理各自语言范围之内的 UNICODE 字符。
2. “UNICODE 字符”与“转换出来的字节”之间的关系是人为规定的。

比较懒,转一篇文章吧。

今天中午,我突然想搞清楚Unicode和UTF-8之间的关系,于是就开始在网上查资料。

结果,这个问题比我想象的复杂,从午饭后一直看到晚上9点,才算初步搞清楚。

下面就是我的笔记,主要用来整理自己的思路。但是,我尽量试图写得通俗易懂,希望能对其他朋友有用。毕竟,字符编码是计算机技术的基石,想要熟练使用计算机,就必须懂得一点字符编码的知识。

1. ASCII码

我们知道,在计算机内部,所有的信息最终都表示为一个二进制的字符串。每一个二进制位(bit)有0和1两种状态,因此八个二进制位就可以组合出256种状态,这被称为一个字节(byte)。也就是说,一个字节一共可以用来表示256种不同的状态,每一个状态对应一个符号,就是256个符号,从0000000到11111111。

上个世纪60年代,美国制定了一套字符编码,对英语字符与二进制位之间的关系,做了统一规定。这被称为ASCII码,一直沿用至今。

ASCII码一共规定了128个字符的编码,比如空格”SPACE”是32(二进制00100000),大写的字母A是65(二进制01000001)。这128个符号(包括32个不能打印出来的控制符号),只占用了一个字节的后面7位,最前面的1位统一规定为0。

2、非ASCII编码

英语用128个符号编码就够了,但是用来表示其他语言,128个符号是不够的。比如,在法语中,字母上方有注音符号,它就无法用ASCII码表示。于是,一些欧洲国家就决定,利用字节中闲置的最高位编入新的符号。比如,法语中的é的编码为130(二进制10000010)。这样一来,这些欧洲国家使用的编码体系,可以表示最多256个符号。

但是,这里又出现了新的问题。不同的国家有不同的字母,因此,哪怕它们都使用256个符号的编码方式,代表的字母却不一样。比如,130在法语编码中代表了é,在希伯来语编码中却代表了字母Gimel (ג),在俄语编码中又会代表另一个符号。但是不管怎样,所有这些编码方式中,0–127表示的符号是一样的,不一样的只是128–255的这一段。

至于亚洲国家的文字,使用的符号就更多了,汉字就多达10万左右。一个字节只能表示256种符号,肯定是不够的,就必须使用多个字节表达一个符号。比如,简体中文常见的编码方式是GB2312,使用两个字节表示一个汉字,所以理论上最多可以表示256×256=65536个符号。

中文编码的问题需要专文讨论,这篇笔记不涉及。这里只指出,虽然都是用多个字节表示一个符号,但是GB类的汉字编码与后文的Unicode和UTF-8是毫无关系的。

3.Unicode

正如上一节所说,世界上存在着多种编码方式,同一个二进制数字可以被解释成不同的符号。因此,要想打开一个文本文件,就必须知道它的编码方式,否则用错误的编码方式解读,就会出现乱码。为什么电子邮件常常出现乱码?就是因为发信人和收信人使用的编码方式不一样。

可以想象,如果有一种编码,将世界上所有的符号都纳入其中。每一个符号都给予一个独一无二的编码,那么乱码问题就会消失。这就是Unicode,就像它的名字都表示的,这是一种所有符号的编码。

Unicode当然是一个很大的集合,现在的规模可以容纳100多万个符号。每个符号的编码都不一样,比如,U+0639表示阿拉伯字母Ain,U+0041表示英语的大写字母A,U+4E25表示汉字”严”。具体的符号对应表,可以查询unicode.org,或者专门的汉字对应表

4. Unicode的问题

需要注意的是,Unicode只是一个符号集,它只规定了符号的二进制代码,却没有规定这个二进制代码应该如何存储。

比如,汉字”严”的unicode是十六进制数4E25,转换成二进制数足足有15位(100111000100101),也就是说这个符号的表示至少需要2个字节。表示其他更大的符号,可能需要3个字节或者4个字节,甚至更多。

这里就有两个严重的问题,第一个问题是,如何才能区别Unicode和ASCII?计算机怎么知道三个字节表示一个符号,而不是分别表示三个符号呢?第二个问题是,我们已经知道,英文字母只用一个字节表示就够了,如果Unicode统一规定,每个符号用三个或四个字节表示,那么每个英文字母前都必然有二到三个字节是0,这对于存储来说是极大的浪费,文本文件的大小会因此大出二三倍,这是无法接受的。

它们造成的结果是:1)出现了Unicode的多种存储方式,也就是说有许多种不同的二进制格式,可以用来表示Unicode。2)Unicode在很长一段时间内无法推广,直到互联网的出现。

5.UTF-8

互联网的普及,强烈要求出现一种统一的编码方式。UTF-8就是在互联网上使用最广的一种Unicode的实现方式。其他实现方式还包括UTF-16(字符用两个字节或四个字节表示)和UTF-32(字符用四个字节表示),不过在互联网上基本不用。重复一遍,这里的关系是,UTF-8是Unicode的实现方式之一。

UTF-8最大的一个特点,就是它是一种变长的编码方式。它可以使用1~4个字节表示一个符号,根据不同的符号而变化字节长度。

UTF-8的编码规则很简单,只有二条:

1)对于单字节的符号,字节的第一位设为0,后面7位为这个符号的unicode码。因此对于英语字母,UTF-8编码和ASCII码是相同的。

2)对于n字节的符号(n>1),第一个字节的前n位都设为1,第n+1位设为0,后面字节的前两位一律设为10。剩下的没有提及的二进制位,全部为这个符号的unicode码。

下表总结了编码规则,字母x表示可用编码的位。

Unicode符号范围 | UTF-8编码方式
(十六进制) | (二进制)
——————–+———————————————
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

跟据上表,解读UTF-8编码非常简单。如果一个字节的第一位是0,则这个字节单独就是一个字符;如果第一位是1,则连续有多少个1,就表示当前字符占用多少个字节。

下面,还是以汉字”严”为例,演示如何实现UTF-8编码。

已知”严”的unicode是4E25(100111000100101),根据上表,可以发现4E25处在第三行的范围内(0000 0800-0000 FFFF),因此”严”的UTF-8编码需要三个字节,即格式是”1110xxxx 10xxxxxx 10xxxxxx”。然后,从”严”的最后一个二进制位开始,依次从后向前填入格式中的x,多出的位补0。这样就得到了,”严”的UTF-8编码是”11100100 10111000 10100101″,转换成十六进制就是E4B8A5。

6. Unicode与UTF-8之间的转换

通过上一节的例子,可以看到”严”的Unicode码是4E25,UTF-8编码是E4B8A5,两者是不一样的。它们之间的转换可以通过程序实现。

在Windows平台下,有一个最简单的转化方法,就是使用内置的记事本小程序Notepad.exe。打开文件后,点击”文件”菜单中的”另存为”命令,会跳出一个对话框,在最底部有一个”编码”的下拉条。

bg2007102801.jpg

里面有四个选项:ANSI,Unicode,Unicode big endian 和 UTF-8。

1)ANSI是默认的编码方式。对于英文文件是ASCII编码,对于简体中文文件是GB2312编码(只针对Windows简体中文版,如果是繁体中文版会采用Big5码)。

2)Unicode编码指的是UCS-2编码方式,即直接用两个字节存入字符的Unicode码。这个选项用的little endian格式。

3)Unicode big endian编码与上一个选项相对应。我在下一节会解释little endian和big endian的涵义。

4)UTF-8编码,也就是上一节谈到的编码方法。

选择完”编码方式”后,点击”保存”按钮,文件的编码方式就立刻转换好了。

7. Little endian和Big endian

上一节已经提到,Unicode码可以采用UCS-2格式直接存储。以汉字”严”为例,Unicode码是4E25,需要用两个字节存储,一个字节是4E,另一个字节是25。存储的时候,4E在前,25在后,就是Big endian方式;25在前,4E在后,就是Little endian方式。

这两个古怪的名称来自英国作家斯威夫特的《格列佛游记》。在该书中,小人国里爆发了内战,战争起因是人们争论,吃鸡蛋时究竟是从大头(Big-Endian)敲开还是从小头(Little-Endian)敲开。为了这件事情,前后爆发了六次战争,一个皇帝送了命,另一个皇帝丢了王位。

因此,第一个字节在前,就是”大头方式”(Big endian),第二个字节在前就是”小头方式”(Little endian)。

那么很自然的,就会出现一个问题:计算机怎么知道某一个文件到底采用哪一种方式编码?

Unicode规范中定义,每一个文件的最前面分别加入一个表示编码顺序的字符,这个字符的名字叫做”零宽度非换行空格”(ZERO WIDTH NO-BREAK SPACE),用FEFF表示。这正好是两个字节,而且FF比FE大1。

如果一个文本文件的头两个字节是FE FF,就表示该文件采用大头方式;如果头两个字节是FF FE,就表示该文件采用小头方式。

8. 实例

下面,举一个实例。

打开”记事本”程序Notepad.exe,新建一个文本文件,内容就是一个”严”字,依次采用ANSI,Unicode,Unicode big endian 和 UTF-8编码方式保存。

然后,用文本编辑软件UltraEdit中的”十六进制功能”,观察该文件的内部编码方式。

1)ANSI:文件的编码就是两个字节”D1 CF”,这正是”严”的GB2312编码,这也暗示GB2312是采用大头方式存储的。

2)Unicode:编码是四个字节”FF FE 25 4E”,其中”FF FE”表明是小头方式存储,真正的编码是4E25。

3)Unicode big endian:编码是四个字节”FE FF 4E 25″,其中”FE FF”表明是大头方式存储。

4)UTF-8:编码是六个字节”EF BB BF E4 B8 A5″,前三个字节”EF BB BF”表示这是UTF-8编码,后三个”E4B8A5″就是”严”的具体编码,它的存储顺序与编码顺序是一致的。

9. 延伸阅读

* The Absolute Minimum Every Software Developer Absolutely, Positively Must Know About Unicode and Character Sets(关于字符集的最基本知识)

* 谈谈Unicode编码

* RFC3629:UTF-8, a transformation format of ISO 10646(如果实现UTF-8的规定)

(完)

计算机原理(七)-进程内存管理分段

我们知道,进程都有独立的虚拟内存空间,跟物理内存一样,因为物理内存大小有限定,存在被覆盖的风险,所以现代CPU一般通过虚拟内存通过MMU进行页表的映射管理。而进程内的空间也一样,因为编译程序的时候,进程内也需要生成各个虚拟地址表,而每个表的大小不固定,可能就会覆盖其他表的地址,而这时,采用的解决方案是早期A-16位内存采用的分段方式,防止被覆盖。

分段原因

在编译过程中会建立许多的表,来确定代码和变量的虚拟地址:

  • 被保存起来供打印清单的源程序正文;
  • 符号表,包含变量的名字和属性;
  • 包含所有用到的整形和浮点型数据的表;
  • 语法分析树,包括程序语法分析的结果;
  • 编译器内部过程调用的堆栈。

前面4张表会随着编译的进行不断增大,而堆栈的数据也会变化,现在的问题就是,每一张表的大小都不确定,那么如何指定每一张表在虚拟内存空间的地址呢?

 

分段作用

分页实际是一个纯粹逻辑上的概念,因为实际的程序和内存并没有被真正的分为了不同的页面。而分段则不同,他是一个逻辑实体。一个段中可以是变量,源代码或者堆栈。一般来说每个段中不会包含不同类型的内容。而分段主要有以下几个作用:

  1. 解决编译问题: 前面提到过在编译时地址覆盖的问题,可以通过分段来解决,从而简化编译程序。
  2. 重新编译: 因为不同类型的数据在不同的段中,但其中一个段进行修改后,就不需要所有的段都重新进行编译。
  3. 内存共享: 对内存分段,可以很容易把其中的代码段或数据段共享给其他程序,分页中因为数据代码混合在一个页面中,所以不便于共享。
  4. 安全性: 将内存分为不同的段之后,因为不同段的内容类型不同,所以他们能进行的操作也不同,比如代码段的内容被加载后就不应该允许写的操作,因为这样会改变程序的行为。而在分页系统中,因为一个页不是一个逻辑实体,代码和数据可能混合在一起,无法进行安全上的控制。
  5. 动态链接: 动态链接是指在作业运行之前,并不把几个目标程序段链接起来。要运行时,先将主程序所对应的目标程序装入内存并启动运行,当运行过程中又需要调用某段时,才将该段(目标程序)调入内存并进行链接。可见,动态链接也要求以段作为管理的单位。
  6. 保持兼容性

所以在现在的x86的体系结构中分段内存管理是必选的,而分页管理则是可选的。

计算机原理-X86 CPU和内存管理(六)

这里主要简单介绍下32位处理器的内存访问,内存管理以及应用程序的内存布局。而32位CPU主要就是从intel 的80386架构CUP开始的,这也是我们最开始熟悉的CPU。而CPU最直接的作用就是 取指令、指令译码、执行指令、访存取数和结果写回。说白了就是对指令进行操作。而前面的可执行程序在CPU看来就是编译好的指令集合及数据集合。

其总图可以抽象为如下:

image

我们分别看看CPU及内存的一些操作细节:

一.32CPU
CPU架构

从80386开始,地址线变为了32位,和CPU寄存器以及运算单元位数一样,最大寻址范围增加到4G。另外80386处理器都可以支持虚拟存储器,支持多任务。 而之后的CPU,主要的改进就在于:

  1. CPU内部集成DMA,计数器,定时器等;
  2. 制造工艺的提示,更多的晶体管,更快的速度
  3. 加入更多的指令集,如MMX,SSE,SSE2等
  4. 集成L1,L2,L3高速缓存,减少外部总线的访问
  5. 超线程,多核心提高CPU效率
CPU内存访问方式

80386引入多任务后,内存管理方式有如下方式:

  1. 地址空间:这个是对物理内存的一个抽象,就好像进程是对CPU的一个抽象。一个进程可用于寻址的一套地址的集合,每个进程都有自己的地址空间,相互独立,这就解决了安全问题。
  2. 交换:把程序全部加载到内存,当进程处于空闲时,把他移除内存,存放到硬盘上,然后载入其他程序。这样使得每个进程可以使用更多的内存。
  3. 虚拟内存:利用到计算机系统的局部性和存储分层,我们可以只加载一部分需要使用的代码和数据到内存,当访问的内容不在内存时,和已经使用完的部分进行交换,这样就能在小内存的机器上运行大的程序了。对于程序来说这是透明的,看起来自己好像使用了全部内存。而多个应用完全可以使用相同的虚拟地址。
  4.  

    由于上面内存管理方式,产生了如下的内存访问方式:

虚拟寻址

CPU在内部增加了一个MMU(Memory Management Unit)单元来管理内存地址的转换。除了可以转换地址,还能提供内存访问控制。如操作系统固定使用一段内存地址,当进程请求访问这一段地址时,MMU可以拒绝访问以保证系统的稳定性。而MMU的翻译过程则需要操作系统的支持。所以可见硬件和软件在计算机发展过程中是密不可分的。

CPU寄存器

通用寄存器 ,指令指针寄存器。。。

二.虚拟内存

他就是现在保护模式下的内存获得方式,它的基本思想是:

  • 每个进程都有自己的地址空间;
  • 每个地址空间被分为多个块,每个块称为页,每个页有连续的地址空间;
  • 这些页被映射到物理内存,但不是所有也都在内存中程序才能运行;
  • 当使用的页不在物理内存中时,由操作系统负责载入相应的页;//运行时映射

虚拟地址(线性地址),虚拟地址就是同上CPU的MMU将虚拟地址映射为物理地址,然后送到总线,进行内存访问。这里最关键的就是虚拟地址的映射。

内存分页

对于虚拟内存来说,是对物理内存的抽象,整个虚拟内存空间被划分成了多个大小固定的页(page),每个页连续的虚拟地址,组合成了一个完整的虚拟地址空间。同样,操作系统也会把物理内存划分为多个大小固定的块,我们称为页框(page frame),它只是操作系统为了方便管理在逻辑上的划分的一个数据结构,并不存放实际内存数据,但是我们可以简单的认为它就是内存。这样一个虚拟内存的page就可以和一个物理内存的page frame对应起来,产生映射关系。

关于一个虚拟页的大小,现在的操作系统中一般是512B-64K(准确的说是地址范围大小,而非容纳数据的大小)。但是内存页的大小会对系统性能产生影响,内存页设得太小,内存页会很多,管理内存页的数组会比较大,耗内存。内存页设大了,因为一个进程拥有的内存是内存页大小的整数倍,会导致碎片,即申请了很多内存,真正用到的只有一点。目前Windows和Linux上默认的内存页面大小都是4K。

从上图我们也可以看出,虚拟内存的页和物理内存的页框并不一定是一一对应的,虚拟内存的大小和系统的寻址能力相关,也就是地址线的位数,而物理内存的页框数取决于实际的内存大小。所以可能只有一部分页有对应的页框,而当访问的数据不在物理内存中时就会出现缺页,这个时候操作系统会负责调入新的页,也就是建立新的映射。这样就不需要一次把程序全部加载到内存。

存储分页

加载应用程序到内存时,因为和虚拟地址有关,我们需要把应用程序文件和虚拟内存关联起来,在Linux中称为存储器映射,同时提供了一个mmap的系统调用来实现次功能。文件被分成页面大小的片,每一片包含一个虚拟页面的内容,因为页面调度程序是按需求调度,所以在这些虚拟页面并没有实际的进入内存,而是在CPU发出访问请求时,会创建一个虚拟页并加载到内存。我们在启动一个进程时,加载器为我们完成了文件映射的功能,所以此时我们的执行文件又可以称为映像文件。实际上加载器并不真正负责从磁盘加载数据到内存,因为和虚拟内存建立了映射关系,所以这个操作是虚拟内存自动进行的。 正是有了存储器映射的存在,使得我们可以很方便的将程序和数据加载到内存中。

MMU映射方式

如何将虚拟页映射到物理页中,MMU通过页表映射,页表是实时在内存中的,而虚拟页是运行时通过页表映射到实际的物理内存页上的。

页表分级

为了解决页表占用内存过多的问题,引入了分级页表

页表缓冲区

虚拟地址转换时,一次内存访问查找页表的过程。我们知道内存速度比CPU慢很多,每次从内存取数据都要访问2次内存,会使得系统性能下降。为了解决这个问题,在MMU中包含了一个关于PTE的缓冲区TLB(Translation Lookaside Buffer ),TLB是一个寄存器,所以它运行的速度和CPU速度相同。每次在去页表中查找之前,可以先在TLB中进行查找,如果命中则直接拿到物理页地址,如果不命中则再次访问内存。

进程调度和虚拟内存

我们知道在系统中,每个进程都有自己独立的虚拟空间,于是每个进程都有一张属于自己的内页表。 而我们翻译地址时,从cr3中取出页表目录的首地址。对于不同的进程,他们都使用同一个寄存器。于是在CPU调度进程的时候,虚拟的地址空间也需要切换。于是对于普通用户程序需要做下面几件事情:

  1. 保存当前进程的页表目录地址,也就是保存cr3中存放的地址到进程上下文中
  2. 清空TLB中缓存的数据
  3. 调度新的进程到CPU,并设置cr3寄存器的值为页表目录的首地址

但是内存中除了用户程序之外还存在操作系统自身占用的内存。我们可以简单的把操作系统看成一个超大的进程,他和其他普通进程一样需要使用虚拟内存,需要使用到页表。当然作为内核程序,它必须是有一些特权的,下一篇我们将会介绍虚拟内存的布局。而对于内核而言不是存在进程调度的。因为所有的内核进程都是共享内核的虚拟地址空间,而我们一般都称之为内核线程,而非进程。 当然对于Linux而言,没有线程的概念,线程和进程唯一不同就是是否共享虚拟地址空间。一般来说内核代码是常驻在内存的,那么内核会不会缺页呢?

STL容器解析

C++ STL 之所以得到广泛的赞誉,也被很多人使用,不只是提供了像vector, string, list等方便的容器,更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组,list封装了链表,map和set封装了二叉树(红黑树)等,在封装这些数据结构的时候,STL按照程序员的使用习惯,以成员函数方式提供的常用操作,如:插入、排序、删除、查找等。让用户在STL使用过程中,并不会感到陌生。

一.使用原则

当对象很大时,建立指针的容器而不是对象的容器

1 STL基于拷贝的方式的来工作,任何需要放入STL中的元素,都会被复制。

2 只涉及到指针拷贝操作, 没有额外类的构造函数和赋值构造函数的调用;

3.对象是指针的话,容器销毁前需要自行销毁指针所指向的对象;否则就造成了内存泄漏;

4.对象是指针的话, 使用排序等算法时,需要构造基于对象的比较函数,如果使用默认的比较函数,其结果是基于指针大小的比较,而不是对象的比较;

二.使用场景

deque的使用场景:比如排队购票系统,对排队者的存储可以采用deque,支持头端的快速移除,尾端的快速添加。如果采用vector,则头端移除时,会移动大量的数据,速度慢。
vector与deque的比较:
一:vector.at()比deque.at()效率高,比如vector.at(0)是固定的,deque的开始位置却是不固定的。
二:如果有大量释放操作的话,vector花的时间更少,这跟二者的内部实现有关。
三:deque支持头部的快速插入与快速移除,这是deque的优点。
list的使用场景:比如公交车乘客的存储,随时可能有乘客下车,支持频繁的不确实位置元素的移除插入。
set的使用场景:比如对手机游戏的个人得分记录的存储,存储要求从高分到低分的顺序排列。
map的使用场景:比如按ID号存储十万个用户,想要快速要通过ID查找对应的用户。二叉树的查找效率,这时就体现出来了。如果是vector容器,最坏的情况下可能要遍历完整个容器才能找到该用户。

数据结构与算法(五)查询

很多时候,我们会比较在意查询的时间,因为这是用户最常使用的功能,并且是实时的需求,非常影响用户体验,以下是各种数据结构查询的效率,我们可以看到平衡二叉树等查找效率比较高,其实这是将时间前移了,因为平衡二叉树本身就是有序的,相当于已经对数据进行了一个排序,我们可以看到插入构造这个树的时间LOG(N)。

image

一.无序数据基础查找

像单链表这种无序队列,插入的时候很快的,直接加到末尾就可以,但是其查找确实耗时,使用了直接查找法。

所以为了加速查找的速度,需要将数据预先进行排序,一般就是生成的 时候就进行排序,比如数据库表加索引,构造二叉树,哈希表存储数据,这样在这些有序数据基础上进行数据查找就快多了,虽然在构造的时候会消耗时间,甚至让总时间都增加了,但是,有什么关系呢。

二.有序数据查找

无序数据查找效率比较慢,所以一般查找前都会排序,分担一部分的压力。

折半查找法

适用场景:针对已排序序列,并且只适用于顺序存储结构的序列,这样才能O(1)找到其中间值。但是这样一来,其插入,删除会变得比较低效,鱼熊不可兼得。

B树(二叉查找树)算法

其查找效率与树的深度有关。

HASH查找

算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

算法流程:

1)用给定的哈希函数构造哈希表;

2)根据选择的冲突处理方法解决地址冲突;

常见的解决冲突的方法:拉链法和线性探测法。 详细的介绍可以参见:  哈希表 。

3)在哈希表的基础上执行哈希查找。

这也是用空间换时间的例子之一。所以哈希表是查询效率的极致了。但是要解决好健冲突问题,比如拉链法,相当于将有共同哈希值的数据存储到一个链上,哈希值索引指向这个链,如果链COUNT>1,则再在链上顺序查找,这也有分治法的应用效果,基本上std::map 这种 kv存储结构就是哈希表的应用。这还可以衍生出进行大数据外排查找Top K问题。

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

拉链法实现的哈希表应该也算是一个分块查找,索引查找的实现方式

分块查找(索引查找)

分块查找又称索引顺序查找,它是顺序查找的一种改进方法。

算法思想: 将n个数据元素”按块有序”划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须”按块有序”;即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……

这种也适合使用并行进行查找。

算法流程:

step1 先选取各块中的最大关键字构成一个索引表;

step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。

数据结构与算法(四)排序

根据待排序数据量能否被全部装载到内存中进行排序分为:内部排序外部排序。当然我们都希望直接在内存中进行排序,因为IO的延迟非常的大,但对于大数据集来说,内存是远远不够的,这时候就涉及到外排序,外排序通过读/写外存的次数来衡量其效率。基本上上学的时候学的都是内部排序,同时万不得已,都尽量使用内部排序,或者转化为内部排序。其实也就是说,我们要以空间换时间,以稳定性换时间,所以如何选择排序方法要综合场景来进行

一.基本排序

http://ibinguo.net/wp-content/uploads/2016/12/image_thumb8.png

image

冒泡排序->快速排序->归并排序

冒泡排序是最基本的排序算法,遍历所有数据,一次遍历查出最大值。所以如果要查询某个最大值也可以使用下冒泡。但是这个速度不敢恭维,所以有了变种快速排序,当然是以牺牲部分空间及稳定性为条件的。

快速排序快排是基础单线程排序中效率最好的了。以分治的思想进行排序,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列

 

插入排序->希尔排序->并归排序

插入排序:遍历剩余所有数据,遍历待排序数据,将数据插入到一个已排序好的队列中,该已排序好的队列慢慢增大。

插入排序是每次将一个数据插入待排序序列,即步长为1希尔排序也可称为分组插入方法,则是步长>1,每个分组内使用插入排序或者二分插入排序。

并归排序:

归并排序是将两个或两个以上的有序子表合并成一个新的有序表。初始时,把含有n个结点的待排序序列看作由n个长度都为1的有序子表组成,将它们依次两两归并得到长度为2的若干有序子表,再对它们两两合并。直到得到长度为n的有序表,排序结束。
归并操作的工作原理如下:

  1、申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

  2、设定两个指针,最初位置分别为两个已经排序序列的起始位置

  3、比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

  4、重复步骤3直到某一指针达到序列尾

堆排序

堆实际上是一棵完全二叉树,利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单。

二.适用场景

综合上述,得到的各种情况下的最优排序分别是:

(1)序列完全有序,或者序列只有尾部部分无序,且无序数据都是比较大的值时, 【直接插入排序】最佳(哪怕数据量巨大,这种情形下也比其他任何算法快)

(2)数据基本有序,只有少量的无序数据零散分布在序列中时,【希尔排序】最佳

(3)数据基本逆序,或者完全逆序时,  【希尔排序】最佳(哪怕是数据量巨大,希尔排序处理逆序数列,始终是最好的,当然三数取中优化的快速排序也工作良好)

(4)数据包含大量重复值,【希尔排序】最佳(来自实验测试,直接插入排序也表现得很好)

(5)数据量比较大或者巨大,单线程排序,且较小几率出现基本有序和基本逆序时,【快速排序】最佳

(6)数据量巨大,单线程排序,且需要保证最坏情形下也工作良好,【堆排序】最佳

(7)数据量巨大,可多线程排序,不在乎空间复杂度时,【归并排序】最佳

 

三.

数据结构与算法(三)树

这一节我们专门来看看树吧,因为这个的应用也是非常广泛。基本的就是二叉查找树,因为二叉查找树可能会出现跛脚的情况,一边长,一边短,所以就出现了平衡二叉树,根据其实现又有AVL树,红黑树。

1.二叉树查找树

定义

对于任何一个结点X

若它的左子树非空,则左子树上所有结点的值均小于等于X的值;             

若它的右子树非空,则右子树上所有结点的值均大于等于X的值;

遍历:

前序遍历:根节点->左子树->右子树

中序遍历:左子树->根节点->右子树

后序遍历:左子树->右子树->根节点

例如:求下面树的三种遍历


前序遍历:abdefgc

中序遍历:debgfac

后序遍历:edgfbca

按中序遍历二叉查找树,所得到的中序遍历序列是一个递增(或递减)的有序序列。

我们来说二叉查找树当然是和查找操作有关系,查找的时间复杂度是和高度H成正比的:log(h)。也可以这么说,二叉查找树基本操作的时间都是和树的高度H是成正比的。这些基本操作包括查找插入和删除,前驱后继等。遍历不在这里讲,以后会专门写有关遍历的文章,BFS,DFS,无栈非递归等。

查找

我们先来看一下查找:给定一个树的树根指针x和关键字k,返回指向关键字的指针,否则返回NIL。 TREE-SEARCH(x,k)伪代码

在递归查找的过程中遇到的结点即构成了一条由树根下降的路径,故TREE-SEARCH的时间复杂度是O(H)。

再来一个非递归版本的ITERATIVE-TREE-SEARCH,这个比递归的要快一些。


最大值和最小值

那么如何去找最大值和最小值呢?最大值肯定是二叉树的最右结点啦,从根结点开始沿着right指针一路走到right指针为空。而最小值肯定在最左结点,从根结点沿着left指针一路走到left指针为空。(此时说的二叉树是按中序遍历是从小到大)

	时间复杂度都是O(H),因为寻找的过程就是根结点一路下降的过程。

前驱和后继

找到最大值和最小值还不够,有时候我们需要寻找前驱和后继。如何寻找呢?我们这里来讲述一下中序遍历的的前驱和后继寻找。后序遍历和前序遍历的前驱后继的寻找和这是一样的道理。
后继
先说后继,对于一个结点X来说,后继无非是有3种情况: 1  X有右孩子,那么X的后继就是右孩子的最左结点。 2  X无右孩子,而且X是其父母的左孩子,那么X后继就是其父母结点(可能NIL)。 3  X无右孩子,而且X是其父母的右孩子,那么X的后继就是X的某个祖先(这个最低祖先的左孩子也是X的祖先),此时让父母成为新的X,寻找不断找X是其父母的左孩子的结点,如果此时出现一个X结点是其父母左孩子,那个父母就是X的后继。这个意思也就是说把第三种情况变成第二种情况。如果这个时候找不到则得到的是NIL结点。因为最大值是没有后继的,其他的肯定都有。 对于第一种情况很简单

对于第二种情况,更简单了,可能父母是NIL,即X结点是根结点。

对于第三种情况,找不到的话就是NIL。最大值没有后继。

伪代码

前驱
	再来看一下前驱,前驱和后继是对称的。如果你仔细看,你会发现刚才寻找后继2 、3 情况的过程是X一直向上查找X是否是其父母的左孩子,而此时X的前驱的分类是和他对称的,是一直向上寻找看X是否是其父母的右孩子,那么其父母就是其前驱。
	1  X有左孩子,那么X的前驱就是左孩子的最右结点。
	2  X无左孩子,而且X是其父母的右孩子,那么X前驱就是其父母结点(可能NIL)。
	3  X无左孩子,而且X是其父母的左孩子,那么X的前驱就是X的某个祖先(这个最低祖先的右孩子也是X的祖先),此时让父母成为新的X,寻找不断找X是其父母的右孩子的结点,如果此时出现一个X结点是其父母右孩子,那个父母就是X的前驱。这个意思也就是说把第三种情况变成第二种情况。如果这个时候找不到则得到的是NIL结点。最小值没有前驱。
对应第一种情况

对应于第二种情况,父母可能是NIL。

对应于第三种情况,找不到是NIL。最小值没有前驱。

伪代码
TREE-PREDECESSOR(x)
1 if left[x]≠NIL
2    then return TREE-MAXIMUM(left[x])
3 y←p[x]
4 while y≠NIL and x=left[y]
5      do  x←y
6          y←p[y]
7 return y
	时间复杂度都是O(H),就是一条自结点向上的路径罢了。
	综上所述 对于一颗高度为H的二叉查询树来说,静态操作SEARCH,MINIMUN,MAXIMUM,SUCCESSOR,PREDECESSOR等用时都是O(H)。
	对于一颗二叉树,要的不仅仅是静态操作,还需要动态操作。因为必然会有插入和删除操作,而且还要保持二叉排序树的性质。

插入

先来看如何插入结点Z,插入很简单的。先把结点Z的左右孩子left[z] 、right[z]和父母p[z]初始化,然后从根结点开始一直向下寻找Z的父母,找到之后就把孩子Z插入,如果是空树,直接把Z当成根结点。 在伪代码中,X初始化为根结点,Y始终是其父母,最后把Z插入。

TREE-INSERT的时间复杂度是O(H)。

删除

插入结点很简单,那么如何删除结点呢?删除结点之后还要保持中序遍历是一个相对位置不变的序列。对于删除一个结点Z,其实是要分类的。 1 如果Z没有孩子,直接删除,仅仅修改其父结点P[Z]的孩子为NIL即可。 2 如果Z仅仅只有一个孩子,那么删除Z之前要把Z的孩子赋值给其父母P[Z]的孩子(左|右)。这样一个拉链直接去删除Z了。 3 如果Z有两个孩子,这样就有点麻烦了。因为删除Z之后还有两个孩子,如果不好好处理会破坏二叉树的性质,我们删除Z一定要保持中序遍历的相对位置序列不变。这样有两种方法,因为只有保持性质即可,两种方法得来的二叉树不一定是一样的,但是都是正确的二叉树。 我们来看一下第三种情况的两种方法:假设删除的结点是P,而且中序遍历的序列是{....CL ,C....  QL,Q,SL,S,P,PR,F}删除P之后的中序遍历序列应该是{....CL ,C....  QL,Q,SL,S,PR,F}。S是P的前驱,PR是P的后继。

这就是未删除P之前的二叉树原型。
方法一
第一种方法是,先把P的前驱S的左孩子SL(S肯定无右孩子,左孩子可能是NIL)变成S父母Q的右孩子,删除S。然后把S的值全部给P,这就让P前驱S取代了P的位置,这样序列相对位置没有发生变化。

	可是真的是这样吗?这是老严数据结构书上的截图,算导上给的是找后继结点,然后和上边说的一样,就是把刚才的前驱换成后继。
	可是我想说的是这里忽略了一种情况,那就是如果前驱是其左孩子了怎么办?根据之前分析的前驱分类,在这里要删除的结点P肯定有两个孩子,那么对于前驱来说就只有两种情况,如果P前驱是左孩子的最右结点,刚才的分析没有一点问题,可是如果P前驱是其左孩子,也就是说左子树根结点没有右子树。那么按刚才的分析 就是说不通了。前驱S是P的左孩子,你还要把S的左孩子变成S的父母(P)的右孩子吗?那之前P的右孩子岂不是丢了??!!
	所以这个时候你要判断一点就是P前驱是否是P的左孩子,就是在找前驱的时候保留一个指针指向前驱的父母,最后判断是否和P相等,如果相等就把P左孩子的左孩子变成P的左孩子,然后P的左孩子(此时也是前驱)覆盖P。如果不相等,就按刚才说的做。
	算导给的,和这是一样的,只不过是对称找后继,如果后继是其右孩子也是尴尬。也可以和刚才一样,留个指针判断。
	我们要分类判断,如果判断得到P的前驱是其左孩子的话,那么直接将前驱取代P就好了,其他什么都不用做。或者像算导上说的找后继,后继是其右孩子的话就让后继取代他。也就是说如果一个结点的前驱或者后继是其孩子的话,直接让其孩子取代他就好了,很简单的,其他什么都不用做。
	不能想当然的以为前驱一定是左孩子的左右结点,后继一定是右孩子的最左结点。这样就算是前驱不是其左孩子,只要后继是其右孩子,就让右孩子取代他,两个孩子满足一个就可以减少很多的处理,优化算法,而且此时不必留指针再判断了。如何判断呢?如果P的左孩子没有右子树,那前驱就是左孩子。如果他的右孩子没有左子树,那后继就是其右孩子。
伪代码
TREE-DELETE(T,z)
1 if left[z]=NIL or right[z]=NIL
2    then if left[z]=NIL
3            then  p[right[z]]=p[z]
4                  left[p[z]]=right[z]
5         else if right[z]=NIL
6            then p[left[z]]=p[z]
7                 left[p[z]]=left[z]
8 else if  right[left[z]]=NIL
9  then key[z]=key[left[z]]
10              p[left[left[z]]]=z
11              left[z]=left[left[z]]
12 else if left[right[z]]=NIL
13         then p[right[right[z]]]=z
14              right[z]=right[right[z]]
15 else
16      then y=left[z]
17           while right[y]≠NIL
18                 y=right[y]
19           p[left[y]]=p[y]
20           right[p[y]]=left[y]
21           key[z]=key[y]
	这是一种分类的做法,老严给的版本是找后继判断,算导给的是找前驱判断,我这里给他综合了一下,更加的优化。不过算导版本虽然没有分类,但是有各种判断,代码很紧凑。虽然我感觉没我的好,不过还是在这里贴一下。

方法二
	接下来我们看第二种方法,这种方法的好处是不像刚才那么有BUG,不过好像大多数书上举的例子都是第一种,汗。难道第一种比第二种的简单?我们看一下吧
	先令P的右孩子PR成为其前驱S的右孩子,然后将P的左孩子C成为P父母F的左孩子,删除P。这样就不用管C是不是其前驱了。C就是其前驱也是把PR给C的右孩子,序列的相对位置是不会发生变化的。

来看一下伪代码
TREE-DELETE(T,z)
1 if  left[z]=NIL or right[z]=NIL
2     then if left[z]=NIL
3             then  p[right[z]]=p[z]
4                   left[p[z]]=right[z]
5          else if right[z]=NIL
6                  then p[left[z]]=p[z]
7                       left[p[z]]=left[z]
8  else  9       y=TREE-PREDECESSOR(z)
10      p[right[z]]=y
11      right[y]=right[z]
12      p[left[z]]=p[z]
13      left[p[z]]=left[z]	代码很简洁,我反倒觉得这个简单,还不麻烦。这两种方法都很简单的,一时想不起,就拿笔画一颗二叉树,很快就明白了。一定要动手画一下。时间复杂度很明显是O(H)。	上边所说的二叉树的大部分操作的时间复杂度都是O(H),H是树的高度。大家一听高度想当然以为就是lgN,其实非也。一个好的二叉树高度可能是O(lgN),即便是如此,可是经过了很多的插入和删除,高度就会发生变化。就像是一开始只有一个结点的二叉树,最后变成了一个高度为N-1的链。这虽然还是树,可是已经不是我们需要的了,时间复杂度太大了(O(N)).
	可是我们怎么才能保证一个树的高度是lg级的呢?随机。一个N个关键字随机的构造的二叉树的高度是lgN。可是经过删除和再次插入的洗礼,高度也不会一直是lgN。所以我们二叉树期望高度是O(lgN),平均时间复杂度是良好的,不过还是不可避免的是会出现最坏情况。这个时候我们就不能仅仅依靠随机了。

平衡二叉树

不过我们不会任由这种最坏情况的发生,我们可以对二叉树做一些平衡的处理,接下来就介绍一下平衡二叉树,这个在最坏情况的时间复杂度都是lg级。 平衡二叉树是为了避免刚才的最坏情况产生的,平衡是指所有的叶子的高度趋于平衡,更广义的是指在平衡二叉树上所有可能查找的均摊复杂度偏低。几乎所有平衡树的操作都基于树的旋转操作,通过旋转操作可以使得树趋于平衡。AVL树,红黑树,伸展树,Treap树等都是平衡二叉树。

AVL树

AVL树仅仅只是平衡二叉树的一种而已,具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵AVL树。若二叉树上结点的平衡因子定义为该结点的左子树的高度减去右子树的高度。那么AVL树的平衡因子就只能是0,-1,1。如果有一个结点的平衡因子的绝对值大于1 ,那么这个二叉树就不是AVL树。如果由于插入和删除结点导致AVL树不平衡,那么就从这个结点开始进行一次或多次的左右旋转和高度的调整,最后使二叉树变得平衡。 老严那本书上讲的平衡二叉树仅仅只是AVL算法的一种平衡二叉树而已,不代表全部的。注意平衡二叉树一种平衡树,而AVL算法只不过是调整树的高度保持平衡的算法而已,不是平衡二叉树的全部。平衡二叉树有很多种,这里我把一些以前的AVL笔记中中的旋转K过来看一下吧。

红黑树

这里我们主要是说一个特殊的平衡二叉树,那就是红黑树RB-TREE。RB-TREE的好处在于检索很快,主要用于关联式容器。Set map multiset  multimap的底层实现都是RB-TREE,这些关联容器存入的时候都是自动排序,查询的时候都是很快。不过代价就是RB-TREE树的插入和删除带来的麻烦很多,不过还好的是 它可以在O(log n)时间内做查找,插入和删除。 红黑树在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。每一个结点有5个域:color key  left  right  p。如果某个结点没有孩子或没有父结点,则把相应的结点设为NIL,颜色BLACK。 红黑树是每个结点都带有颜色属性的二叉查找树,颜色为红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求(性质): 性质1. 每个结点只能是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子结点都是黑色(叶子是NIL结点)。 性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) 性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。

	在很多树数据结构的表示中,一个结点有可能只有一个子结点,而叶子结点包含数据。这种表示红黑树是可能的,但是这会改变一些属性并使算法复杂。为此,我们使用 NIL来表示叶子结点。如上图所示,它不包含数据而只充当树在此结束的指示。这些结点在绘图中经常被省略,导致了这些树好像同上述原则相矛盾,而实际上不是这样。与此有关的结论是所有结点都有两个子结点,尽管其中的一个或两个可能是空叶子NIL。有点时候为了节省内存把所有的NIL连在一起当成一个NIL[T]哨兵,代表所有的叶子NIL和父母结点是NIL的结点。
	结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。
	要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个相连的红色结点就足够了。最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点。还有注意的是叶子节点都是NIL,它不包含数据而只充当树在此结束的指示。所以根据属性5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长。
	我们定义黑高度BH(X)为从结点X出发(不包括X)到叶子结点的任意一条路径上,黑色结点的个数。这样我们就会得到一个结论:一颗有N个结点(不包括NIL叶子)的红黑二叉树的高度至多是2lg(N+1)。
	简单证明一下:由于以X为根的RB-TREE至少包含2^BH(X)-1个结点。因为对于高度为0的RB树,结点数目是0,对于一个结点高度大于0的RB树,左右孩子的颜色可能是红,也可能是黑,所以孩子的黑高度BH有可能和父母一样,也有可能比父母少1。所以孩子的结点数目加上父母结点X就和X为根的RB树的结点数目是一样的,也就是说2^(BH(X)-1)-1+2^(BH(X)-1)-1+1=2^BH(X)-1,所以假设成功。此时呢,假设N个结点的RB树高度是H,则黑高度至少是H/2,所以呢,2^BH-1=2^(H/2)-1<=N,H<=2lg(N+1),得证。
	所以对于红黑树的所有动态和静态的操作都可以在O(lgN)时间内实现。
旋转
可是经过了删除和插入,红黑树的性质会发生变化,所以需要一些旋转操作和结点颜色的改变来维持性质。这里我们先来看一下旋转的知识。旋转分左旋和右旋。

	当在某个结点x上做左旋操作时,我们假设它的右孩子y不是NIL,x可以为RB树内任意右孩子而不是的结点。旋以x到y之间的链为“支轴”逆时针旋转,它使y成为该子树新的根,而y的左孩子b则成为x的右孩子。而右旋和左旋是对称的。Y的右孩子X也不是NIL,这时候以y到x之间的链为“支轴”逆顺时针旋转,使x成为新的子树的根,x的右孩子变成y的左孩子。因为左右对称,这里我们只给出左旋的伪代码。假设X的右孩子不等于NIL,而且根的父母结点是NIL。

	时间复杂度都是O(1),旋转的时候只有指针在变化,而其他的所有域都不会改变。至于RB树颜色的变化是和旋转无关的。还要明确一点的就是旋转不改变中序遍历的相对顺序
插入
现在就先说插入吧,因为插入毕竟比删除简单一些。在一个有N个RB树中插入一个结点可以在O(lgN)时间内完成。 插入一个结点肯定是要赋予颜色的,我们是给他红色,还是给他黑色呢? 5大性质: 性质1. 每个结点只能是红色或黑色。 性质2. 根结点是黑色。 性质3. 所有叶子结点都是黑色(叶子是NIL结点)。 性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点) 性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。 根据5大性质我们知道,如果把插入的结点赋予黑色,则会违反性质5,导致黑高度发生变化,这个是很麻烦的。待会删除的时候你就会明白。而如果赋予红色,则只会违反性质2和4,如果是性质2,说明插入的是根结点,直接把根结点变成黑色就好。如果违反性质4,说明插入结点的父节点是红色的,此时可以通过旋转和结点颜色的改变搞定,这个不是很麻烦。我们只讨论违反性质的情况,不违反的就不说了。我们来看一下。 RB-TREE的插入和之前的二叉查找树的插入代码有些不同,所有的NIL结点换成哨兵NIL[T],插入的结点初始化left和right都是哨兵NIL[T],颜色直接赋予红色。然后专门写一个调整算法RB-INSERT-FIXUP。这里我们只看调整算法,之前的插入我们已经讲过了,不明白看前面章节。 我们假设父节点是P,叔叔结点是U,祖父结点是G,插入结点是N。同时假设Z的父节点P是祖父G的左孩子,这和是右孩子是对称的,我们只讨论P是G左孩子的情况。 如何调整呢?我们要寻找一些辅助,父节点P肯定是要参与的,因为要看他是不是红色,红色的话就调整,不是红色的话直接给根结点变黑色(不判断都行),不管其他的。而且可以肯定是祖父节点G肯定是存在的,而且是黑色(NIL或者其他,因为插入之前肯定满足RB树的性质)。如果父结点P是红色,那么我们如何调整?因为除了根结点是黑色之外,其他的都不晓得,我们也不能随意的调整。
情况一
	我们不能贸然调整把插入结点N变成黑色,不过如果父结点的兄弟结点,也是插入结点N的叔叔结点U,他如果是红色的话。

	此时我们可以把U和P都变成黑色,但是此时以祖父的父节点G为根的子树的黑高度变化了,也即是+1了。这就违反了性质5,唉,千万不敢违反性质5,超级麻烦。所以我们做一个变通,可以把祖父结点G变成红色,此时的违反性质的可能性就落到了G身上,这时就把G当成插入结点N,继续进入调整算法开始调整。
	也就是说我们可以把这个插入结点N和父节点P的连续红色的违反情况向上移动,就是把违反性质的结点向上调整,这样直到最后变成根结点是红色的,根结点父节点是NIL[T]黑色,此时直接把根结点变成黑色即可,很nice。

	此时的G就变成了新的插入结点了,继续调整,最多到根结点。情况一:如果父节点P和叔父节点U二者都是红色,则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质5)。
	可是如果叔叔结点U是黑色呢?这就不能按刚才说的调整了,我们要换一个策略了。此时我们要分情况,插入结点N是父节点P的左孩子还是右孩子,这是不一样的。
情况三
如果N是P的左孩子

	此时我们直接把父节点P变成黑色,然后以G--P为轴顺时针旋转(右旋),P变成了根,但是G变成了P的右孩子,这个时候两边的黑高度就发生了变化,右边的+1了,此时我们可以把G变成红色,这样两边就均衡了啊。而且
此时算法直接就结束了,因为性质都保持住了。

情况二
可是如果N是P的右孩子呢?

	这样看起来很不好搞啊,旋转变色,都达不到要求,都是无用的。我们可以把这个N右孩子变成刚才说的左孩子吗?看起来是不可以。不过我们可以发现的是父母和孩子结点的变换是可以通过旋转来做的,也就是说通过一次旋转,孩子可以变成父母,父母也可以变成孩子,而新的孩子和之前的孩子的左右是相反的。而此时N和P都是红色,我们通过一次的左旋,可以把P变成N的左孩子,也就是相当于P变成插入结点是红色,N变成父节点是红色,叔叔结点U是黑色,则和刚才说的是一样的。

	也即是变成了刚才那种情况。所以我们把这种情况称为第二种,刚才说的是第三种。因为第二种到第三种是直接过度的,不是互斥的情况。虽然我们忘了一种情况,那就是叔叔不存在,但是这并不影响我们刚才分析的结果。
情况二:如果父节点P是红色而叔父节点U是黑色或不存在,并且插入节点N是其父节点P的右孩子。我们以P-N为轴进行一次左旋调换插入节点N和其父节点P的角色(不是颜色)

情况三::如果父节点P是红色而叔父节点U是黑色或不存在,并且插入节点N是其父节点P的左孩子。我们可以把P重绘为黑色,并重绘G为红色。然后以P-G为轴以进行一次左旋调换节点P和节点G的角色。
	情况一要进入继续调整,最坏的情况是向上调整到根。情况二直接进入情况三。情况三调整完了之后调整算法就结束了。
	上伪代码,这个伪代码和刚才分析的是一样的,如此同时还是只有半边代码,就是只有父节点P是祖父结点G的左孩子的情况。不过在伪代码里,插入结点是z,y是其叔叔。
INSERT伪代码

RB-INSERT-FIXUP伪代码

给一个例子看看,很好的例子,囊括了三种情况。
这是情况一的情况

情况一调整结果变成了情况二了。

情况二调整结果变成了情况三了。

情况三调整完了就结束了。

	很明显我们的RB-INSERT的1-16行的时间代价是(lgN),而对于RB-INSERT-FIXUP中,只有情况一才会发生循环,即便是循环到根,也不过用时O(lgN),所以总的时间花费就是O(lgN)。而且这个RB-INSERT-FIXUP过程的旋转不超过2次,也就是情况二和情况三各旋转一次O(1),旋转过后算法就结束了。
删除
接下来我们来看看如何删除RB-TREE的结点。
	对于一个有N个结点的RB-TREE来说,删除一个结点要花费的时间就是O(lgN)。与插入相比,只不过是更加的复杂罢了。我们来分析一下。删除一个二叉树的结点我们说过了,这里不再说,之说删除结点之后如何保持红黑树的5大性质。
5大性质:
	性质1. 每个结点只能是红色或黑色。
	性质2. 根结点是黑色。
	性质3. 所有叶子结点都是黑色(叶子是NIL结点)。
	性质4. 每个红色结点的两个孩子结点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色结点)
	性质5. 从任一结点到其每个叶子的所有简单路径都包含相同数目的黑色结点。
	如果删除的结点的颜色是一个红色,我们压根就不需要调整,因为这并不违反任何一个性质。因为各结点黑高度没有变化,不存在相邻的红色结点,删除的也不是根结点。如果树的结点只有一个,那么删除了也不需要调整。如果树的结点不是一个而且删除的结点是黑色的,那么就有可能违反性质4,因为可能有两个相邻的红色结点。删除了根结点,造成新的根结点是红色可能违反了性质2。而且删除黑色的结点会违反性质5,导致黑高度不一致。
	我们如何调整呢?假设删除了结点Y,肯定有占用他位置的结点是X,X可能是他的前驱或后继,X也可能是Y的孩子,或者是哨兵NIL[T]结点。如果X结点本身是红色,也就是说有可能违反性质4和5,那我们直接赋予它黑色就解决了。如果红色结点X变成了根违反性质1,也直接赋予黑色就OK。现在的问题是如果X结点是黑色而且不是根结点,违反了性质5,黑高问题就不好解决了。这里我们主要说如何解决这一个情况,前两个情况很easy,不需细说了。
	之前说过如果违反了性质5,会很麻烦,这会你就知道了。违反了性质5,我就很拙计了。当然这也不是解决不了的。那如何保持性质5呢?我们总不能期望他不违反性质5吧。这里我们用一个技巧,就是假设删除的结点Y把它的黑色性质X结点了,也就是说X结点多了一重黑色,就是黑+黑,这样的话黑高度就一致了,性质5就满足了。
	当然这只是假设,我们假想的,不过这有助于我们解决问题。这个黑+黑结点是X结点,他的颜色属性还是黑色,只不过用一个指针指向他,他便多了一层黑色。不断调整的过程,会出现新的X结点,这时候指针指向的结点不一定会是原来的X了,不过还是会多一层黑色。而且在不断旋转的过程会出现旋转前后两边子树黑高发生变化的情况,此时如果N这边的子树黑高+1了,那N头上的多于黑色就没有了,舍弃。这就是我们的最终目的。
	这也就是调整的麻烦之处,接下来我们看看他如何麻烦。当然这还是要分类的。这里我们只考虑结点X是其父节点左孩子的情况,对称的情况不再讲。
	我们假设占用被删除结点的位置的结点是N,N的兄弟结点是S,N的父亲结点是P,S的左孩子是SL,S是右孩子是SR。要明确一点的是S不是NIL[T],因为如果是NIL[T],那两边的黑高现在就不一样,即便是没删除之前,RB-TREE也不会出现这种情况的。
情况一
如果兄弟结点S是红色,那么S的父亲结点P和S的孩子SL和SR都必然是黑色,此时N也是黑色的。

	此时如何调整?指针指向的是N,N是黑+黑。此时父亲结点P变红色,S变黑色,然后以P-S为轴左旋。此时指针指向的还是N,看起来好象是没什么变化,其实是变了,父亲结点P变成了红色,兄弟结点变成SL还是黑色。不要着急,这只是第一步而已嘛。

情况一:如果兄弟结点S是红色的(隐含的意思P,SL,SR都是黑色),那么我们就交换父节点P和兄弟结点S的颜色,即P变红色,S变黑色,然后以P-S为轴左旋。	如果兄弟结点是红色的话,只可能有这一种情况,因为父节点和孩子结点的颜色都是定好的黑色。接下来看兄弟结点是黑色的情况,这样他的孩子结点和父亲结点的颜色可就不唯一了,这可以分好几种情况的。
情况二
如果N的兄弟结点S是黑色的,而且两个孩子结点都是黑色的。N还是被指针指向,黑+黑。(P的颜色不晓得)

	如何调整?此时我们并不知道P的颜色,我们也不需要去判断。我们假设N和S都脱掉一层的黑色(两边路径上的黑色结点数还是相同),那N变成了正儿八经的黑色了,指针也不指向他了,而S脱掉黑色就只能变成了红色。而此时经过P的路径在这边少了一个黑色,黑高-1,所以我们要用指针指向他,给他多一层的黑色,这样经过P的路径在这边的黑色就不变了,这样多好。

	此时指针指向的是P(新的N)多了一层黑色,黑+黑或者是红+黑。有变化吗?当然了,看起来好像回到了情况一(兄弟S是红色),其实不是。因为新的N是P,这样指针指向的结点不断的向上移动,至多变成了根结点,那敢情好,直接赋予黑色,OK搞定。
情况二:如果兄弟结点S是黑色的,而且S的两个孩子也都是黑色的。直接把N变成黑色,S变成红色,用指针指向P,P多了一层黑色。
情况三
如果N的兄弟结点S是黑色,不过S的左孩子SL是红色的,右孩子SR是黑色的。

	那么如何调整?此时把SL和S的颜色交换,即SL变成黑色,S变成红色,然后以S-SL为轴右旋。此时N的兄弟变成了SL,而SL的右孩子变成了红色。

情况三:如果N的兄弟结点S是黑色,而且S的左孩子SL是红色的,右孩子SR是黑色的。此时把SL变成黑色,S变成红色,然后以S-SL为轴右旋。
情况四
此时N的兄弟S的右孩子就变成了红色,而左孩子不晓得。这种情况就是我们要说的情况四,情况三直接过渡到情况四,相互不排斥,其实是在一个分类里面。

	这样的话就是直接交换P和S的颜色,P变成黑色,而S变成P的颜色(不定),S的右孩子SR也变成黑色。然后以P-S为轴左旋。此时只有S的颜色不定,可是此时S的孩子都是黑色,S是什么色都无所谓了。此时算法就结束了,调整完毕。

算法为什么就结束了呢?因为调整的前后左边的子树的黑高+1了,所以此时N的多一层黑色就没用了,要舍弃。就是说我们解决了黑高的问题,性质5保持住了。
情况四:如果N的兄弟结点S是黑色,而且S的右孩子SR是红色的。那么交换P和S的结点颜色,即S变成P的颜色(不定),P变成黑色,SR变成黑色,然后以P-S为轴左旋。
	OK,大功告成一半,接下来上伪代码。伪代码中Y是要删除的结点,X是替代Y的结点,W是X的兄弟。调整算法是RB-DELETE-FIXUP。
RB-DELETE(T,x)
........
if color[y]=black
   then RB-DELETE-FIXUP(T,x)

     RB-DELETE-FIXUP的时间复杂度是O(lgN),因为只有情况二需要循环,循环次数最多是O(lgN)。情况 1 、3、 4最多需要旋转3次和一些颜色的改变而已。所以RB-DELETE-FIXUP过程要花费O(lgN)的时间,至多需要3次旋转。总的来说红黑树是很不错的,很快,所以很多容器的底层都用RB树。
	OK,这样红黑树就差不多说完了,以后有新的理解还会继续更新。

数据结构与算法(二)概述

数据结构与算法都比较严谨,找了一篇通俗的介绍篇。

http://www.matrix67.com/blog/archives/90

《数据结构与算法分析》

4月7日买起来看,前几天才看完。这可以说明很多问题,比如,学习很紧张,没有时间;书本身很好,很有看头;看书看得很细心,很有耐心。
    打算大致写一下书里的内容。
    Data Structures and Algorithm Analysis in C, Second Edition,机械工业出版社。封面很丑,一个黑底版,上面有些大理石花纹,正中间生硬的摆一个原版封面,同样丑。一共12章,近400页。
    400多页是很多的。我们必须要“把厚书读薄”,厚的变薄的,薄的变一页,一页变一行,一行变成一个字。因此,我要在有限的字数内把整本书说完。

    算法分析,就是复杂度的问题。复杂度只算“最要命的”,比如,执行n^2的算法前来个快排根本不拖速度,n^2多的都豁出去了不在乎区区一个nlogn。书里对复杂度进行了严格的定义,包括O()、o()、Θ()、Ω()四种符号。简单地说,O(n^2)就是顶破天了搞个n^2次;o(n^2)就是天花板不到n^2,比n^2矮一点(比如希尔排序就是o(n^2),因为它再倒霉也达不到n^2);Ω(n^2)就是说某个算法随便怎么至少都要耗费n^2,比如所有基于比较的排序都是Ω(nlogn);Θ(n^2)就是说它即是O(n^2)又是Ω(n^2),被天花板和水泥地夹在中间了,动不了了,就是它了。这里面有一个经典的例子,就是最大子序列(找数列中连续一段数之和最大)的四种算法,复杂度分别为O(n^3)、O(n^2)、O(nlogn)和O (n)。这书一个特色在于,对每种数据结构都有严格的算法复杂度证明,这往往是看上去最头痛的部分。

    表、栈和队列是三个基本的数据结构。说穿了表就是把数据找起来排排坐吃果果,找什么东西都来把整个队伍找一遍。栈就是一个桶,后放进去的先拿出来,它下面本来有的东西要等它出来之后才能出来,就好像你看到了一个丑人不可能今天的中饭还没吐出来就先把早饭吐出来了。栈是拿来模拟多个过程的调用的(比如递归),实际点的用途就是表达式计算队列好比堵车,先进去的先出来。先进队先买票,不能插队。常拿来实现广搜

    树,是一种植物,有很多枝枝丫丫。不同的是这里的树是倒着的,树枝朝下长。最上面叫根,尖尖的地方叫树叶,生出树叶的是他爸,他爸生的是他儿子。不管是根是树叶还是儿子还是儿子他爸都叫节点。我们常常把数据储存在节点上,并且以后还要不断地插入、改变和删除数据。
    二叉树就是每个分叉的地方最多分两个岔,而且还分得清左右。二叉查找树就是说把数据存在节点上,而且左边的都比他爸小,右边的都比他爸大,以后要找哪个数就可以只找其中的一边,一半一半地扔掉。在二叉查找树里也可以插入一个数,删掉一个数(只有一个儿子好办,有两个就把右边的最小的一个拿来替代这个),找最小的数(一直往左走),找最大的数(一直往右走),但是容易搞着搞着的树就变畸形了,比如说左边猛起长右边萎缩导致以后往左边走要走很久。我们就需要一种方法来让树左右差不多一样多而且左边的值仍然比右边的小。事实上这种方法已经找到了,而且不只一种方法,而是一卡车的方法,比如AVL、Splay、红黑树、Treap等。几种方法都靠一个叫“旋转”的技巧,就是把几个节点怎么个一转,左边的就跑到右边去了一点。看下面这个图你就明白了。

         ①                   ②
        /        旋转       / 
      ②   ZZ    ——>    XX  ①
     /                        / 
    XX  YY                    YY  ZZ

这样一来左边就少了,如果左边的XX本来很多的话就可以往上提一层从而平衡。同样地,右边多了反过来做就是了。这只是最简单的“单旋转”,事实上还有很多其它的较复杂的旋转方法。Splay树就是把刚才访问过的节点转啊转啊转啊转转到最顶上去,Treap就是每个节点附加一个随机的数,随时通过旋转保持儿子的这些随机数比他爸大,其余的有点复杂。这些方法都能使二叉查找树相对地平衡一些,防止畸变导致的时间浪费。
    B-树和二叉查找树有两个不同,一个是节点不存数据,数据全在树叶子上,二个是它不一定是二叉。数据仍然左边小右边大方便查找。每个节点最多的儿子数有限制,最多三叉的叫2-3树,最多四叉的叫2-3-4树。因为只有树叶上有数据,所以可以递归地用分裂的方法处理新插入后出现的分叉比规定的最多的儿子个数时还多的情况。比如,2-3树中如果哪里分了四个岔,就把它重新分成两个两个的岔。我们还规定,除了根以外,每个节点最少的儿子数是规定的最多儿子数的一半,除不尽取上整。容易想到,删除的话可以把插入时的分裂反过来做,什么时候只剩一个儿子了就和旁边的合并起来。

    Hash表又叫散列表,一般用于判断有没有重复。比如我想找我们班有没有两个一天生的,我们不必每两个人都来比较一次,而是准备一个年历,让人一个一个上去在他的生日那天那里画一个圈,如果谁要画圈时发现那里已经有一个圈了,就找到了一对。这个很简单,不说了。

堆,就是一陀一陀的东西。头重脚轻不算堆,要上面小下面大才算一个堆。堆是一棵二叉树,满足下面的始终比上面的大。它和二叉查找树比较起来既有好的又有不好的:好的就是要想知道数据里的最小值时根本就不用找了,直接就是最顶上的那个了;不好的就是堆除了这个以外基本上不能做别的事了。除了最顶上的那个以外,你几乎没办法控制其余的部分。当然,插入和删除数据这种基本操作还是可以做的。插入就是把数据暂时先放在最下面的某个位置,然后通过与它上面一个进行比较、交换不断往上冒直到已经到了自己的位置不能再向上为止。删除反起来,通过不断交换往下沉一直沉到底。因为是往下走,所以要考虑到一个把左边的放上来还是把右边的放上来的问题。当然,为了保证堆上小下大的性质,应该把小的一边换上来。刚才说过,由于你只能“看”到最顶上的东西,不知道中间部分是什么样,我们通常只删除最小的(最上面的)那个节点。其实堆还有一个最大的好处:容易写代码。因为我们可以有意让数据把树“排得满满的”,满到它是一行一行挨着排下来的。这叫做“完全二叉树”。我们可以给完全二叉树编个号,从上到下从左到右挨着数下来。根是1,找左儿子就乘2,找右儿子就乘2加1,找它爸就 div 2。以后叫谁就是谁,很方便。这样整个树就可以用一个数组实现了。由于堆基本上只用来找最小,因此如果某个问题要求很复杂的话,最好还是用成二叉查找树;当然,如果问题只要求插入、删除和找最小三种操作,你应该毫不犹豫地选择堆,毕竟找最小时堆方便得多,写起又简单。什么时候出现这种问题呢?比如说,我的女友排起队的,我每次要选一个最纯洁的,就是受那些的影响最小的人。每当我遇见了一个新的美女,我就把她放在这个队伍里合适的位置供我以后娱乐。这时,我只关心每次插入、取最小和删最小。这个队伍就可以用一个堆来优化。因此,堆还有一个形象的名字叫优先队列。如果谁问题目要求不找最小找最大怎么办,那人肯定是个傻子,把堆变通一下,上大下小不就完了吗?
    研究堆麻烦的地方就是堆的合并。如何把两个堆合并成一个堆?这个解决了很有用,至少上面的这些操作跟着全部统一了:插入就是与一个单节点的堆合并,删除根就是把根不要了,把根的左右两边(显然还是堆)合并起来。一个简单的办法就是递归地不断把根大的堆往根小的堆的右边合并,把新得到的堆替换原来的右儿子。注意递归过程中哪个根大哪个根小是不停在改变的。这样下来的结果就是典型的“右倾错误”,而且破坏了完全二叉树的完美。为此,我们想要随时保证堆的最右边尽量少。于是,干脆不要完全二叉树了,不过是多写几行代码嘛。这个不存在像二叉查找树那样“某一边越做越多”的退化问题,因为对于一个堆来说,反正我只管最顶上的东西,下面平不平衡无所谓,只要不挡我合并的道就行。于是,我们想到人为下一个能让堆尽量往左边斜的规定。这个规定就是,对于左右两个儿子来说,左边那个离它下面最近的两个儿子不全(有可能一个都没有)的节点的距离比右边那个的远。这规定看着麻烦,其实还真有效,最右边的路径的长比想像中的变得短得多。这就叫左式堆(左偏树)。这下合并倒是方便了,但合并着合并着要不了多少次右边又多了。解决的办法就是想办法随时保持左式堆的性质。办法很简单,你合并不是递归的吗?每次递归一层后再看看左右两边儿子离它下面没有两个儿子的节点哪个远,如果右边变远了就把左边右边调一下。由于我们已经没有用数组实现这玩意了,因此链表搞起很简单。这个对调左右的方法给了我们一个启发:哪里还要管什么到没有两个儿子的节点的距离嘛,既然我每次都在往右合并,我为什么不每次合并之后都把它对调到左边去呢?这种想法是可行的,事实上它还有一个另外的名字,叫斜堆。
    二项堆更强,它也是堆,也能合并,不过它已经超越了堆的境界了:它不是一个堆,而是满屋子的堆。也就是说,找最小值不能再一下子找到了,而是要把二项堆中的每个堆的顶部都看一下。二项堆的合并也很强,直接把根大的堆放在根小的堆的下面。这意味着二项堆的每个堆都可能不是二叉树了。这增加了编程的难度,不过可以用一个叫做“左儿子右兄弟”的技巧来解决问题。这个技巧,说穿了就是仍然用二叉树来表示多叉树:把树画好,然后规定节点的左儿子是下一层的最左边那个,右儿子就是它右边那个。就是说,左儿子才是真正的儿子,右儿子不过是一起生出来的。为了让二项堆好看些,让堆的个数和大小保持在一个能快速操作的数目和比例内,二项堆作出了一个明智的规定:每个堆的大小(总的节点个数)只能是1、2、4、8、16…中的一个,且每种大小的堆只能有一个。若干个互不相同的2的幂足以表示任意一个正整数,因此这个规定可以保证不管多大的二项堆都能表示出来。保持这个性质很简单,遇到两个大小相等的堆就合并起来成为一个大一号的堆。由于总是两个大小相等的堆在合并,因此二项堆中的每一个堆都有一个奇妙的样子,看看本文结束后下面附的一个大小为16的堆的示意图,再看一下,再看一下,你就能体会到了。图下面有一个用“左儿子右兄弟”法表示的同样的树,其中,往下走的线是左儿子,往右走的线是右儿子。
    最后简单说一下Fibonacci堆。保持一个跟着变的数组记录现在某个节点在堆中的位置,我们还是可以对堆里的数据进行一些操作的,至少像删除、改变数值等操作是完全可以的。但这个也需要耗费一些时间。Fibonacci堆相当开放,比二项堆更开放,它可以不花任何时间减少(只能是减少)某个节点的值。它是这样想的:你二项堆都可以养一屋子的堆,我为什么不行呢?于是,它懒得把减小了的节点一点一点地浮上去,而是直接就把它作为根拿出来当成一个新的堆。每次我要查最小值时我就再像二项堆一样(但不要求堆的大小了)一个个合并起来还原成一个堆。当然,这样的做法是有适用范围的,就是前面说的数值只能是减少。在什么时候需要一个数值只减少不增加的堆结构呢?莫过于Dijkstra一类的图论算法了。所以说,这些图论算法用Fibonacci堆优化可以进一步提速。
有一个女人的男人很幸福。事实上,这是片面的。应该说,有不止一个女人的男人更幸福。但是,这样会坏了我的人品,而且被女的知道了也不好。两个耍得好的女人话很多,秘密在女人中传得很快。于是,我打算不同时和两个耍得好的女的耍朋友。后来我意识到,这样也不行。女人太无敌了,即使A与B耍得好,B与C耍得好,A和C的消息也是互通的。哪怕只有一个朋友关系也能把两群人联系在一起。我不得不改变策略,使得我的女朋友之间没有任何渠道传递信息。也就是说,在上面的A、B、C三个人中,虽然A和C没有直接的联系,但我也不能同时和A、C耍。不久后,我想知道,某两个女人是否可以通过某条“朋友链”传递信息。这就是所谓的等价关系——基本上算是判断一个无向图的连通性。就像很多个集合,每次选两个并成一个,而且我们随时想知道某两个元素经过前面的合并后是否在同一个集合内。怎么办呢?后来有一天,我发现那些小女生喜欢玩些认亲戚的游戏,什么谁是谁妈,谁是谁姐,谁是谁女儿之类的(不知道为什么这些疯女人喜欢搞这些)。我突然恍然大悟,我的问题可以用树结构来完成。亲戚的亲戚还是亲戚,但有一点总相同:所有亲戚的始祖总是一样的。始祖一样的都是一伙的。因此,把两个集合并在一起,只要让其中一个集合的根成为另一个集合中的某个元素的一个儿子就行了,这种家谱关系的改变将使前面的集合中所有的元素拥有和后面那个集合一样的鼻祖,而这将成为这些元素的“标志”。这个想法的灵感是来自女人世界的,因此女人还是有一定的作用。     这就叫并查集,又叫不相交集。它可以合并两个集合并且查询两个元素是否在同一集合。我们有一个很有效的剪枝:递归时顺便把路上经过的祖祖辈辈全部变成根的儿子。这样的程序只用2行来解决。function find_set(x:integer):integer;   begin   if x<>p[x] then p[x]:=find_set(p[x]);   exit(p[x]);end;
    p[x]表示元素x的父亲的位置。一开始,p[x]都等于x自己,表示自己一个人是一个集合。函数find_set(x)将返回x所在集合(一棵树)的根。     并查集还有些其它的剪枝和一些很复杂的效率分析问题,这里不多说了。
    写到这里,《数据结构与算法分析》中的几个大块内容算是说清楚了。由于本文的叙述调整了原书各章节的顺序且至此还没有涉及书里的一些小问题,因此这里想把遗漏下的一些小东西提一下。     有一些树结构可能要求同时满足多个要求。比如一个简单的问题:如果要求构造一个堆使得既能查找最小元素又能查找最大元素怎么办?这时,我们可以用一个特殊的方法来实现:树的单数层满足一种性质,树的双数层满足另一种性质。我们用一个叫做最小-最大堆的东西来实现前面说的问题。这个堆的双数层的数据小于它爸大于它爸的爸,单数层的数据反过来,大于它爸小于它爸的爸。用类似的方法,我们还可以设计一个二叉查找树,使得它能够支持含有2种不同类型元素的数据。在单数层按其中一种操作,在双数层按另一种操作,这样可以方便的查找同时位于两个不同类元素的指定区间内的数据。这种二叉查找树叫做2-d树。扩展2-d 树,我们可以得到k-d树。这些数据结构的具体实现方法这里不说了,书上本来也是作为一个习题介绍的。     书里的第7章花了近50页介绍并分析各种排序算法,分析得很全。其中第11节花了10页介绍外部排序。所谓外部排序,就是说怎样快速地把一个根本无法全部读入内存的大文件进行排序。很多排序之所以可行是因为它们可以随意读写任意一个指定的数。但在大文件里,我们无法实现“第1234567890个元素和第 123个元素交换位置”,更无法实现递归之类的操作,而只能像磁带一样“过一遍”,从头到尾扫一遍,由于文件太大内存不能接受,因此必须要读一截扔一截。于是,外部排序产生了。不要以为这个限制会把排序速度拖得很慢。事实上,外部排序同样突破了O(n^2)的界限。它借助了归并排序中的“合并两个已经有序的数组”的思想,因为这个操作可以边读就边做。把文件先拆成两个文件,再把每个文件处理成一段一段的等长有序序列(一段多大取决于内存能一次处理多大),然后不断从两个文件中各取一段出来合并。可以看到,每段有序序列的长度变长了,变成了2倍长。过不了几次,这个长度将变成文件的总长。注意,我们必须要让每次合并时为下次合并做好准备(就是说合并后的结果仍然要是两个分了段的文件)。一个好的方法是将合并的结果交替存在两个不同的新文件中。     第9章讲图论算法。讲了图的遍历(广搜和深搜)、AOV、AOE、Dijkstra、网络流、Prim、Kruskal和NP问题。在讲深搜时,我学到了两个新东西,用线性时间查找割点(去掉了的话图就不连通了的点)和强分支(有向图中的一个分支满足其中任两个点之间都可以互相到达)。后来发现黑书上也有,又觉得这个东西很不好说,因此这里不想说了。说到了黑书还想顺便补一句:黑书真的看不得——太多错误了。不是说LRJ怎么了,LRJ在真正的大问题上有他的思想和经验,但很多细节的概念他也是昏的,这不利于初学者接受知识。不信哪天我还要写一篇日志纠正黑书的错误。引用政治书上抨击“人性自私论”的经典语言:“从理论到实践都是错的”。     第10章讲“算法设计技巧”,大概是些贪心啊,分治啊,动规啊,回溯啊,随机化啊之类的。调度问题、Huffman树、装箱问题近似算法、最近点距分治算法、最优二叉查找树、Floyd-Warshall、跳跃表、Miller-Rabin素性测试、博弈算法等都在这章中有讲,并且讲得相当好。由于这不是本书的重点内容,这里也不说了。     第11章整章都在讲摊还分析。这是一个相当复杂的问题,是分析时间复杂度的一个有力工具。它的分析告诉我们的不是某一个操作的复杂度,而是重复执行某一个操作的平均复杂度。研究这个是很有必要的,因为我们会遇到一些“越变越慢”的退化情形和“自我保持不变”的自调整性等数据结构,单个操作并不能反映它真正的效率。
    到这里,这本书的所有东西都已经介绍完了。总的来说,这本书很值得一看(虽然有些地方翻译得很差)。它的理论性很强,证明过程完整(再复杂的分析它也证明得很清楚,满足那些刨根问底的人);整本书自成一个体系,前后呼应;习题具有研究性,与课文互相补充。事实上,这些都是国外教材共有的特点。这算是我完整读过的第一本国外教材,今后我还会读一些。这几天在看《组合数学》(仍然是这个出版社出版的),看完后也打算写一下“对《组合数学》一书中部分内容的形象理解”。读一本国外教材,你会发现它与国内书籍的不同并会从中获益更多。
    这篇文章就写到这里了。号称是一个5000字缩写,没想到写着写着已经超过8000字了。而且,这个并不是缩写,而是一些简单的、系统的、清晰的、形象化的思想和理解。这篇文章或许对已经知道一些有关知识的人有用,但不适合一点也没有接触过数据结构与算法分析的人。如果有一个人能从中收获一件东西,我写这个的目的也就达到了。
(完)

数据结构与算法(一)基础

数据结构是一门研究非数值计算程序设计问题中,计算机的操作对象以及他们之间的关系和操作的学科

数据是用来描述现实世界的数字字符图像声音以及能够输入到计算机中并能被计算机识别的符号的集合

数据结构三方面内容:

(1)数据的逻辑结构指数据元素之间固有的逻辑关系

(2)数据的存储结构指数据元素及其关系在计算机内的表示

( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除,更新,查询,排序等

一.数据结构基础概念

逻辑结构包括:

(1)线性结构,若结构是非空集则仅有一个开始和终端结点,并且所有结点最多只有一个直接前趋和后继。
(2)非线性结构,一个结点可能有多个直接前趋和后继。:集合,树形结构、图形结构

存储结构包括:

1)顺序存储,逻辑相邻的结点存储在物理上相邻的存储单元内。逻辑顺序与存储顺序一致
2)链接存储,结点间的逻辑关系由附加指针字段表示,1.逻辑顺序与存储顺序不一致2.每个节点存取的费时不同
3)索引存储,存储结点信息的同时,建立附加索引表,有稠密索引和稀疏索引。
4)散列存储,按结点的关键字直接计算出存储地址。

(操作)算法时间复杂度

是该算法的时间耗费,是求解问题规模n的函数。记为O(n)。
时间复杂度按数量级递增排列依次为:常数阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平方阶O(n^2)、立方阶O(n^3)、……k次方阶O(n^k)、指数阶O(2^n)。

评价算法的标准:正确性,高效性,健壮性(容错),可读性。

抽象数据类型的形式描述为:

ADT = ( D,S,P )

  其中:D 是数据对象,

S 是 D 上的关系集,

P 是 D 的基本操作集。

ADT 抽象数据类型名 {

 数据对象: 数据对象的定义

 数据关系: 数据关系的定义

 基本操作: 基本操作的定义

} ADT 抽象数据类型名

二.各类数据结构特点(算法时间复杂度)

    索引 插入 删除 查询 排序
  静态数组 O(1) O(1)  
  动态数组 O(1) O(n) O(n) O(n)  
  单链表 O(n) O(1) O(1) O(n)  
  双链表 O(n) O(1) O(1) O(n)  
  二叉排序树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  红黑树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  B树 O(log(n)) O(log(n)) O(log(n)) O(log(n))  
  笛卡尔树 O(log(n)) O(log(n)) O(log(n))  
  哈希表 O(1) O(1) O(1)  
             
             
             
排序:

image

C++ 虚函数表解析

转载自耗子叔酷壳网(http://coolshell.cn/articles/7992.html

C++中的虚函数的作用主要是实现了多态的机制。关于多态,简而言之就是用父类型别的指针指向其子类的实例,然后通过父类的指针调用实际子类的成员函数。这种技术可以让父类的指针有“多种形态”,这是一种泛型技术。所谓泛型技术,说白了就是试图使用不变的代码来实现可变的算法。比如:模板技术,RTTI技术,虚函数技术,要么是试图做到在编译时决议,要么试图做到运行时决议。

关于虚函数的使用方法,我在这里不做过多的阐述。大家可以看看相关的C++的书籍。在这篇文章中,我只想从虚函数的实现机制上面为大家 一个清晰的剖析。

当然,相同的文章在网上也出现过一些了,但我总感觉这些文章不是很容易阅读,大段大段的代码,没有图片,没有详细的说明,没有比较,没有举一反三。不利于学习和阅读,所以这是我想写下这篇文章的原因。也希望大家多给我提意见。

言归正传,让我们一起进入虚函数的世界。

虚函数表

对C++ 了解的人都应该知道虚函数(Virtual Function)是通过一张虚函数表(Virtual Table)来实现的。简称为V-Table。在这个表中,主是要一个类的虚函数的地址表,这张表解决了继承、覆盖的问题,保证其容真实反应实际的函数。这样,在有虚函数的类的实例中这个表被分配在了这个实例的内存中,所以,当我们用父类的指针来操作一个子类的时候,这张虚函数表就显得由为重要了,它就像一个地图一样,指明了实际所应该调用的函数。

这里我们着重看一下这张虚函数表。C++的编译器应该是保证虚函数表的指针存在于对象实例中最前面的位置(这是为了保证取到虚函数表的有最高的性能——如果有多层继承或是多重继承的情况下)。 这意味着我们通过对象实例的地址得到这张虚函数表,然后就可以遍历其中函数指针,并调用相应的函数。

听我扯了那么多,我可以感觉出来你现在可能比以前更加晕头转向了。 没关系,下面就是实际的例子,相信聪明的你一看就明白了。

假设我们有这样的一个类:

1

2

3

4

5

6

7

class Base {

public:

virtual void f() { cout << "Base::f" << endl; }

virtual void g() { cout << "Base::g" << endl; }

virtual void h() { cout << "Base::h" << endl; }

};

按照上面的说法,我们可以通过Base的实例来得到虚函数表。 下面是实际例程:

1

2

3

4

5

6

7

8

9

10

11

12

typedef void(*Fun)(void);

Base b;

Fun pFun = NULL;

cout << "虚函数表地址:" << (int*)(&b) << endl;

cout << "虚函数表 — 第一个函数地址:" << (int*)*(int*)(&b) << endl;

// Invoke the first virtual function

pFun = (Fun)*((int*)*(int*)(&b));

pFun();

实际运行经果如下:(Windows XP+VS2003, Linux 2.6.22 + GCC 4.1.3)

虚函数表地址:0012FED4
虚函数表 — 第一个函数地址:0044F148
Base::f

通过这个示例,我们可以看到,我们可以通过强行把&b转成int *,取得虚函数表的地址,然后,再次取址就可以得到第一个虚函数的地址了,也就是Base::f(),这在上面的程序中得到了验证(把int* 强制转成了函数指针)。通过这个示例,我们就可以知道如果要调用Base::g()和Base::h(),其代码如下:

1

2

3

(Fun)*((int*)*(int*)(&b)+0);  // Base::f()

(Fun)*((int*)*(int*)(&b)+1);  // Base::g()

(Fun)*((int*)*(int*)(&b)+2);  // Base::h()

这个时候你应该懂了吧。什么?还是有点晕。也是,这样的代码看着太乱了。没问题,让我画个图解释一下。如下所示:

01

注意:在上面这个图中,我在虚函数表的最后多加了一个结点,这是虚函数表的结束结点,就像字符串的结束符“/0”一样,其标志了虚函数表的结束。这个结束标志的值在不同的编译器下是不同的。在WinXP+VS2003下,这个值是NULL。而在Ubuntu 7.10 + Linux 2.6.22 + GCC 4.1.3下,这个值是如果1,表示还有下一个虚函数表,如果值是0,表示是最后一个虚函数表。

下面,我将分别说明“无覆盖”和“有覆盖”时的虚函数表的样子。没有覆盖父类的虚函数是毫无意义的。我之所以要讲述没有覆盖的情况,主要目的是为了给一个对比。在比较之下,我们可以更加清楚地知道其内部的具体实现。

一般继承(无虚函数覆盖)

下面,再让我们来看看继承时的虚函数表是什么样的。假设有如下所示的一个继承关系:

02

请注意,在这个继承关系中,子类没有重载任何父类的函数。那么,在派生类的实例中,其虚函数表如下所示:

对于实例:Derive d; 的虚函数表如下:

03

我们可以看到下面几点:
1)虚函数按照其声明顺序放于表中。
2)父类的虚函数在子类的虚函数前面。

我相信聪明的你一定可以参考前面的那个程序,来编写一段程序来验证。

一般继承(有虚函数覆盖)

覆盖父类的虚函数是很显然的事情,不然,虚函数就变得毫无意义。下面,我们来看一下,如果子类中有虚函数重载了父类的虚函数,会是一个什么样子?假设,我们有下面这样的一个继承关系。

04

为了让大家看到被继承过后的效果,在这个类的设计中,我只覆盖了父类的一个函数:f()。那么,对于派生类的实例,其虚函数表会是下面的一个样子:

05

我们从表中可以看到下面几点,
1)覆盖的f()函数被放到了虚表中原来父类虚函数的位置。
2)没有被覆盖的函数依旧。

这样,我们就可以看到对于下面这样的程序,

1

2

3

Base *b = new Derive();

b->f();

由b所指的内存中的虚函数表的f()的位置已经被Derive::f()函数地址所取代,于是在实际调用发生时,是Derive::f()被调用了。这就实现了多态。

多重继承(无虚函数覆盖)

下面,再让我们来看看多重继承中的情况,假设有下面这样一个类的继承关系。注意:子类并没有覆盖父类的函数。

06

对于子类实例中的虚函数表,是下面这个样子:

07

我们可以看到:
1) 每个父类都有自己的虚表。
2) 子类的成员函数被放到了第一个父类的表中。(所谓的第一个父类是按照声明顺序来判断的)

这样做就是为了解决不同的父类类型的指针指向同一个子类实例,而能够调用到实际的函数。

多重继承(有虚函数覆盖)

下面我们再来看看,如果发生虚函数覆盖的情况。

08

下图中,我们在子类中覆盖了父类的f()函数。

09

下面是对于子类实例中的虚函数表的图:

我们可以看见,三个父类虚函数表中的f()的位置被替换成了子类的函数指针。这样,我们就可以任一静态类型的父类来指向子类,并调用子类的f()了。如:

1

2

3

4

5

6

7

8

9

10

11

Derive d;

Base1 *b1 = &d;

Base2 *b2 = &d;

Base3 *b3 = &d;

b1->f(); //Derive::f()

b2->f(); //Derive::f()

b3->f(); //Derive::f()

b1->g(); //Base1::g()

b2->g(); //Base2::g()

b3->g(); //Base3::g()

安全性

每次写C++的文章,总免不了要批判一下C++。这篇文章也不例外。通过上面的讲述,相信我们对虚函数表有一个比较细致的了解了。水可载舟,亦可覆舟。下面,让我们来看看我们可以用虚函数表来干点什么坏事吧。

一、通过父类型的指针访问子类自己的虚函数

我们知道,子类没有重载父类的虚函数是一件毫无意义的事情。因为多态也是要基于函数重载的。虽然在上面的图中我们可以看到Base1的虚表中有Derive的虚函数,但我们根本不可能使用下面的语句来调用子类的自有虚函数:

1

2

Base1 *b1 = new Derive();

b1->f1();  //编译出错

任何妄图使用父类指针想调用子类中的未覆盖父类的成员函数的行为都会被编译器视为非法,所以,这样的程序根本无法编译通过。但在运行时,我们可以通过指针的方式访问虚函数表来达到违反C++语义的行为。(关于这方面的尝试,通过阅读后面附录的代码,相信你可以做到这一点)

二、访问non-public的虚函数

另外,如果父类的虚函数是private或是protected的,但这些非public的虚函数同样会存在于虚函数表中,所以,我们同样可以使用访问虚函数表的方式来访问这些non-public的虚函数,这是很容易做到的。

如:

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

class Base {

private:

virtual void f() { cout << "Base::f" << endl; }

};

class Derive : public Base{

};

typedef void(*Fun)(void);

void main() {

Derive d;

Fun  pFun = (Fun)*((int*)*(int*)(&d)+0);

pFun();

}

结束语

C++这门语言是一门Magic的语言,对于程序员来说,我们似乎永远摸不清楚这门语言背着我们在干了什么。需要熟悉这门语言,我们就必需要了解C++里面的那些东西,需要去了解C++中那些危险的东西。不然,这是一种搬起石头砸自己脚的编程语言。

附录一:VC中查看虚函数表

我们可以在VC的IDE环境中的Debug状态下展开类的实例就可以看到虚函数表了(并不是很完整的)

附录 二:例程

下面是一个关于多重继承的虚函数表访问的例程:

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

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

#include <iostream>

using namespace std;

class Base1 {

public:

virtual void f() { cout << "Base1::f" << endl; }

virtual void g() { cout << "Base1::g" << endl; }

virtual void h() { cout << "Base1::h" << endl; }

};

class Base2 {

public:

virtual void f() { cout << "Base2::f" << endl; }

virtual void g() { cout << "Base2::g" << endl; }

virtual void h() { cout << "Base2::h" << endl; }

};

class Base3 {

public:

virtual void f() { cout << "Base3::f" << endl; }

virtual void g() { cout << "Base3::g" << endl; }

virtual void h() { cout << "Base3::h" << endl; }

};

class Derive : public Base1, public Base2, public Base3 {

public:

virtual void f() { cout << "Derive::f" << endl; }

virtual void g1() { cout << "Derive::g1" << endl; }

};

typedef void(*Fun)(void);

int main()

{

Fun pFun = NULL;

Derive d;

int** pVtab = (int**)&d;

//Base1's vtable

//pFun = (Fun)*((int*)*(int*)((int*)&d+0)+0);

pFun = (Fun)pVtab[0][0];

pFun();

//pFun = (Fun)*((int*)*(int*)((int*)&d+0)+1);

pFun = (Fun)pVtab[0][1];

pFun();

//pFun = (Fun)*((int*)*(int*)((int*)&d+0)+2);

pFun = (Fun)pVtab[0][2];

pFun();

//Derive's vtable

//pFun = (Fun)*((int*)*(int*)((int*)&d+0)+3);

pFun = (Fun)pVtab[0][3];

pFun();

//The tail of the vtable

pFun = (Fun)pVtab[0][4];

cout<<pFun<<endl;

//Base2's vtable

//pFun = (Fun)*((int*)*(int*)((int*)&d+1)+0);

pFun = (Fun)pVtab[1][0];

pFun();

//pFun = (Fun)*((int*)*(int*)((int*)&d+1)+1);

pFun = (Fun)pVtab[1][1];

pFun();

pFun = (Fun)pVtab[1][2];

pFun();

//The tail of the vtable

pFun = (Fun)pVtab[1][3];

cout<<pFun<<endl;

//Base3's vtable

//pFun = (Fun)*((int*)*(int*)((int*)&d+1)+0);

pFun = (Fun)pVtab[2][0];

pFun();

//pFun = (Fun)*((int*)*(int*)((int*)&d+1)+1);

pFun = (Fun)pVtab[2][1];

pFun();

pFun = (Fun)pVtab[2][2];

pFun();

//The tail of the vtable

pFun = (Fun)pVtab[2][3];

cout<<pFun<<endl;

return 0;

}

注:本文年代久远,所有的示例都是在32位机上跑的。