Mar 11

MCPD: Windows Developer 3.5达成。。。

恩。。。昨天把3科一天考完了。。。本来是预约了两天的,不过考场允许一次考掉,就不跑两趟了。。。虽然563有好几题不是很确定,不过还是全部拿到了900+。。。505和563的题目和2.0版的完全不同,多了很多关于3.5新特性还有SQL Server 2008的题目。。。想找题库的朋友就要再等一段时间了。。。

顺便BS下那考场。。。那电脑屏幕能闪得人泪流满面。。。orz

Jan 27

MCTS 70-536复习笔记

突然心血来潮想去考MCTS,于是搞了本Training Kit来看。。。这里记录下之前没有学过/很少用过的知识点。。。

Ch. 2 Isolated Storage

Ch. 3 Regular Expressions

\d = [0-9]

\s = [ \f\n\r\t\v]

\w = [A-Za-z0-9_]

\b = Word boundary

{n,m}

(?<name>)

\k<name> = Back reference

Match.Result(“${name}”)

Ch.4

BitVector32: fixed 4-byte structure

BitArray: resizable reference type

Ch.5

IDeserializationCallback interface

XML Serialization Attributes

Ch.6

StringFormat class

Ch.7

Thread.BeginCriticalRegion, Thread.EndCriticalRegion

ExecutionContext

ThreadPool.RegisterWaitForSingleObject

Ch.8

Evidence

AppDomainSetup

Ch.9

Configuration file manipuation

Ch.10

debugger attributes

performance counter

Ch.11

Code Access Security

Ch.12

terms:

authentication: who the user is

authorization: whether the user can do something

Rfc2898DeriveBytes

Ch.16

CultrueInfo

RegionInfo

Aug 23

算法与数据结构学习笔记(7)

1、图

图由包含数据的顶点(Vertex)以及代表数据间关系的边(Edge)组成。现实中许多问题都可以用图表示。

  • 图有有向图、无向图、加权图等类型
  • 边可用邻接矩阵(Adjecency Matrix)或邻接表(Adjecency Matrix)表示
  • 图的主要遍历方法有深度优先搜索(DFS)、广度优先搜索(BFS)两种
  • 深度优先搜索使用栈实现,广度优先搜索使用队列实现
  • 最小生成树为连接所有顶点最少所需的边
  • 最小生成树中边的数量为顶点数量-1,且不能有循环
  • 可使用DFS建立最小生成树
  • 拓扑排序(Topological sorting)是把有向无循环图(Directed Acyclic Graph)的顶点按照出现顺序排序

2、加权图(Weighted Graph)

加权图的每条边都有一个权重(Weight),可用于表示距离、时间、价格等。

  • 最小生成树为连接所有顶点的总权重最低的边集合
  • 最小生成树建立方法:任选一个顶点为当前顶点,把所有边以权重作为优先级放入优先队列,从优先队列删除两端顶点均已在最小生成树中连接的边,再取出权重最小的边加入最小生成树。移动到新连接的顶点。重复直到所有顶点均已连接或所有边都测试过。
  • 最短路径问题可用Dijkstra算法解决
Aug 05

算法与数据结构学习笔记(6)

1、散列表

使用散列值作为索引存储数据,若散列函数实现得好,效率可接近O(1)。

处理散列碰撞的方法:

  • 线性跳跃:H1(N)+n
  • 平方跳跃:H1(N)+n2
  • 二次散列:H1(N)+n*H2(N)
  • 在内部使用链表(较简单,但性能会轻微下降)

(H1、H2为散列函数,N为数据,n为碰撞次数)

H2(N)必须与散列表大小互质,否则遇到多次碰撞时会陷入死循环。最简单的方法为确保散列表的大小为质数。

非链表实现的散列表的装入率(Load Factor)超过约三分之二时性能会大大下降。

链表实现的散列表装入率为1.0以下时性能最佳,在高装入率时的性能下降速度也比非链表实现慢,所以在数据量未知的情况下较为适合。

2、堆

堆的内部为一棵完整二叉树,其基本特征为:父节点的数据一定大于(或小于)子节点的数据。堆的基本操作有插入和删除,时间复杂度均为O(log N)。

插入:把新节点放置在完整二叉树的尾部,然后上移(trickle up)到适当位置。

删除:保存二叉树的根节点数据,用二叉树的尾部节点替换根节点,再下移(trickle down)到适当位置(在下移时需要同时比较左子节点和右子节点,否则会破坏基本特征),最后返回保存的数据。

由于删除时返回的数据必定为堆内最大(或最小)的数据,而且时间复杂度比有序数组低,所以堆适合作为优先队列的内部结构。

堆排序:把所有数据插入堆,再取出即可。时间复杂度为O(N log N),但比快速排序慢。

提高堆排序的效率:由于对两个子节点为有效堆的节点进行下移后能得到一个有效堆(参考删除操作),所以可以把数组看成一棵二叉树,从底部的非叶节点开始(叶节点可视作一个有效堆),由右到左从下至上进行下移操作,完成后整个数组即成为一个有效堆。

Aug 02

算法与数据结构学习笔记(5)

1、2-3-4树

与红黑树相似,也是一种自平衡树。各类节点的红黑树对应结构,如下:

2-节点:黑色节点

3-节点:黑色节点+红色子节点

4-节点:黑色节点+2个红色子节点

4-节点的分割:新建一个节点,把原4-节点第3个元素移至新节点,并把第3、4个子节点连接至新节点;第2个元素移至父节点,最后把新节点连接到父节点。

2-节点的合并:

(1)从父节点移动与当前节点位置相邻的数据到当前节点,使用相邻节点的第一个或最后一个数据(取决于相邻节点的方向)填补空缺,并把相应的子节点连接到当前节点。

(2)若未合并前相邻节点不是2-节点,则可退出。

(3)若父节点为2-节点且不是根节点,先对其进行合并。

(4)把之前移到父节点的数据移动至当前节点,相邻节点剩余的一个子节点连接至当前节点,并删除相邻节点。如父节点未合并前为2-节点且为根节点,则设置当前节点为新根节点。

2、外部存储

  • B-树:二叉查找树及2-3-4树均为B-树的特殊形式
  • 索引
  • 排序:内存不足的情况下可用归并排序
Jul 28

算法与数据结构学习笔记(4)

1、二叉查找树

  • 时间复杂度(插入、查找、删除):O(log N)(平衡状态) ~ O(N)(不平衡状态)
  • 访问方法:前序、中序、后序遍历法
  • 删除有两个子节点的节点的方法:使用Inorder successor(这个词不知道怎么翻译。。。orz)替换该节点
  • 使用数组存储二叉树:左子节点索引=i * 2 + 1;右子节点索引=i * 2 + 2;父节点索引=(i -1) / 2

2、霍夫曼编码

  • 基本原理:在一段信息中,最常出现的字符使用最少的位(bit)表示,最少出现的字符使用最多的位表示,以达到压缩信息的目的
  • 编码步骤:
    1. 统计信息中各字符出现的次数
    2. 把所有字符放进一个优先队列,以次数为优先级
    3. 从优先队列取出两个元素组成一个二叉树节点,再以两元素的优先级相加作为新的优先级放回优先队列,重复直到队列里只剩下一个元素,该元素即为霍夫曼树
    4. 遍历霍夫曼树建立码表,节点的左叶表示为0,右叶表示为1
    5. 使用码表编码信息
  • 解码步骤:
    1. 定位到霍夫曼树的根部
    2. 逐位读取编码后的信息,遇到0定位到左叶,遇到1定位到右页
    3. 如到达树底部的字符节点,把该字符写入输出,重新定位到树的根部
    4. 重复2、3直到读取完所有信息

3、红黑树

红黑树为一种特殊二叉查找树,可把插入、删除、查找的时间复杂度保持在O(log N)。

性质:

1、所有节点要么是红色,要么是黑色

2、根节点一定是黑色

3、红色节点的子节点是黑色

4、所有从根节点到子节点或空节点(空节点定义为黑色)的路径,必须包含同等数量的黑色节点

在插入及删除节点时将对一些节点进行旋转及改变颜色,以保持4个性质。

节点的旋转:

以节点A为顶点进行左(右)旋转,即使用A的右(左)子节点代替A,A移至新节点的左(右)子节点。如新节点已存在左(右)子节点,则把它移至A的右(左)子节点。

  A          C

  /\          /\

 B C   --〉      A E

   /\         /\

  D E       B D

注:经过旋转后的节点仍然符合二叉查找树的特征

插入步骤:

1、将新节点设置为红色

2、查找插入点

  *)查找时如遇到黑色节点的两个子节点都为红色的情况,则改变这三个节点的颜色(例外情况:如果该节点为根节点,则仍然为黑色),然后修复红红冲突。

3、插入节点,如新节点为根,则把颜色改为黑色

4、插入后,如遇到红红冲突,则进行以下步骤:

  1. 如当前节点为内侧节点(即节点的方向与父节点不同)则进行旋转以转换为外侧节点,继续2
  2. 把祖父节点和父节点(如在2中进行过旋转,则为新节点)的颜色翻转,然后向父节点的反方向旋转

  G          G         N

  /          /          /\

 P   --〉    N    --〉  P G

  \         /

  N       P

 (1)       (2)

注:因为性质1,祖父节点必然存在;因为性质3,其必然为黑色。

删除步骤:

http://en.wikipedia.org/wiki/Red-black_tree#Removal

(不想打了。。。太复杂了。。。orz

Jul 17

算法与数据结构学习笔记(3)

1、归并排序(Merge Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(N)
  • 比较次数比快速排序少,但移动次数比快速排序多

2、希尔排序(Shell Sort)

  • 时间复杂度:O(N log2 N)
  • 空间复杂度:O(1)
  • 选择好的间隔能极大提高性能,目前已知最好的间隔为:1, 4, 10, 23, 57, 132, 301, 701,(2.3hn-1)

3、快速排序(Quick Sort)

  • 时间复杂度:O(N log N)
  • 空间复杂度:O(1)
  • 通常情况下为最快的通用排序算法之一,但某些时候复杂度会提升到O(N2)
  • 预先排序第一个、中间及最后一个元素能减少复杂度为O(N2)的概率

Update 7.17:

4、基数排序(Radix Sort)

  • 时间复杂度:O(N)(?)
  • 空间复杂度:O(N)
  • 速度很快,但是只能排序数值类型
Jul 04

算法与数据结构学习笔记(2)

1、链表

  • 简单链表
  • 双端链表
  • 双向链表

2、抽象数据类型(ADT)

抽象数据类型描述了数据的储存形式及可对数据实现的操作,其具体实现可以有多种形式。

3、迭代器

迭代器用于遍历数据结构内的数据,并可对其进行某些操作。

Jul 03

算法与数据结构学习笔记(1)

学了4章才想起来做笔记。。。orz

1、无序数组

运算复杂度:

插入:O(1)

删除:O(N)

查找:O(N)

2、有序数组

运算复杂度:

插入:O(N)

删除:O(N)

查找:O(N)(线性搜索),O(log N)(二分搜索)

3、大O表示法(Big O notation,是这样译没错吧囧)

复杂度排序:O(1) < O(log N) < O(N) < O(N log N) < O(N2)

4、二分搜索

运算复杂度:O(log N)

5、简单排序算法

  • 冒泡排序
  • 选择排序
  • 插入排序

运算复杂度:均为O(N2)

空间复杂度:O(1)

效率比较:冒泡 < 选择 < 插入

6、栈、队列

特性:

栈:后入先出(LIFO)

队列:先入先出(FIFO)

 

运算复杂度:插入和删除均为O(1)

7、优先队列

运算复杂度(数组实现):

插入:O(N)(线性搜索),O(log N)(二分搜索)

删除:O(1)

8、逆波兰表达式