外交部发言人马朝旭在回应刘晓波获奖时说:“刘晓波是因触犯中国法律而被中国司法机关判处徒刑的罪犯,其所作所为与诺贝尔和平奖的宗旨背道而驰。诺委会把和平奖授予这样一个人,完全违背了该奖项的宗旨,也是对和平奖的亵渎。”
中国的法律是对和平的尊重么?
问题一:哪里下载?
回答: https://www.microsoft.com/whdc/DevTools/Debugging/default.mspx上面的链接通常是一个web installer,但是也提供了ISO下载。这套工具中包括了kd,ntsd, cdb,和万能的Windbg,当然也包含了很多其他常见的工具。
问题二:装完之后怎么用?
回答:Windbg自然是用来Debug的,但是它也可以用来观察系统是如何运作的。要让Windbg正常的工作起来,还是有一定难度的,首先要做的一件事情就是把symbol path设定好。
什么是symbol path?编译原理中提到的符号表就是编译器用来找符号对应地址时候用的,同时在debug的时候,符号也能够用来帮助我们定位变量和函数的具体位置。如今的软件动辄几个GB,为了不增加最终用户磁盘空间的压力,所以把符号表和其他相关的信息存储到了另一个文件上(通常是dbg或pdb文件)。这样就确保最终编译出来的文件又小又快。
Windbg有很多中设定symbol path的方法,这里只需要介绍两种。
方法一:_NT_SYMBOL_PATH
把_NT_SYMBOL_PATH添加到环境变量中去,如_NT_SYMBOL_PATH=SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols
其中d:\symbols\7600是缓存,而http://msdl.microsoft.com/download/symbols是符号的下载地址。这里需要注意的是一定要使用管理员权限去打开debugger,否则无法读出环境变量。
方法二:.sympath
在任意个一个debugger中的命令行中键入:.sympath SRV*d:\symbols\7600*http://msdl.microsoft.com/download/symbols 也能达到同样的效果。
直接通过下载符号可以保证符号是正确的,但是这也造成了不小的负担,所以可以先下载已有的符号当缓存用:http://www.microsoft.com/whdc/devtools/debugging/symbolpkg.mspx但是这个缓存通常不是最新的,这也就是设定网络路径的好处了。
通过使用命令:!sym noisy可以使debugger把查询符号的位置和是否匹配的结果列出来。这样可以马上知道什么原因无法找到符号。比如ntdll.dll时常更新,7600里面的版本号和新的ntdll不匹配会导致无法找到符号。
private void Rotate_to_Left(Node x)
{
Node y = x.RChild;
Node z = x.Parent;
Node q = y.LChild;
if (z == NULL_NODE)
{
this.root = y;
}
else
{
if (z.LChild == x)
{
z.LChild = y;
}
else
{
z.RChild = y;
}
}
y.Parent = z;
y.LChild = x;
x.Parent = y;
x.RChild = q;
if (q != NULL_NODE)
{
q.Parent = x;
}
}
右旋转也一样只有一个子节点需要改变,代码如下:
private void Rotate_to_Right(Node x)
{
Node y = x.LChild;
Node z = x.Parent;
Node q = y.RChild;
if (z == NULL_NODE)
{
this.root = y;
}
else
{
if (z.LChild == x)
{
z.LChild = y;
}
else
{
z.RChild = y;
}
}
y.Parent = z;
y.RChild = x;
x.Parent = y;
x.LChild = q;
if (q != NULL_NODE)
{
q.Parent = x;
};
}
接着的关键问题就是如何计算节点的高度了,问题不难,但是注意我有一个null object: NULL_NODE。这个节点没有父,左,右和高度信息。
public int Height
{
get
{
if (this == NULL_NODE)
{
return 0;
}
List< Node > nodes = new List< Node >() { this };
List< List < Node > > height = new List< List< Node > >() { nodes };
while (true)
{
nodes = new List< Node >();
foreach (Node n in height[height.Count - 1])
{
if (n.LChild != NULL_NODE)
{
nodes.Add(n.LChild);
}
if(n.RChild != NULL_NODE)
{
nodes.Add(n.RChild);
}
}
if (nodes.Count != 0)
{
height.Add(nodes);
}
else
{
break;
}
}
return height.Count;
}
}
下面处理如何使这颗树回复平衡:
private void balance(Node x)
{
int balance_factor = x.LChild.Height - x.RChild.Height;
//There are 4 cases:
//1. balance factor increased form 1 to 2; do a roatation toward right can address the problem
//2. balance factor increased from -1 to -2; do a rotation toward left can address the problem
if (balance_factor == 2)
{
if (x.LChild.LChild.Height < x.LChild.RChild.Height)
{
this.Rotate_to_Left(x.LChild);
}
this.Rotate_to_Right(x);
}
if (balance_factor == -2)
{
if (x.RChild.LChild.Height > x.RChild.RChild.Height)
{
this.Rotate_to_Right(x.RChild);
}
this.Rotate_to_Left(x);
}
}
和二叉搜索树插入唯一不同的一点就是在插入结束的时候回溯到根节点:
public void Add(Node n)
{
Node p = this.root;
Node q = NULL_NODE;
if (p == NULL_NODE)
{
this.root = n;
}
else
{
while (p != NULL_NODE)
{
q = p;
if (n.Key > p.Key)
{
p = p.RChild;
}
else
{
p = p.LChild;
}
}
if (n.Key > q.Key)
{
q.RChild = n;
}
else
{
q.LChild = n;
}
n.Parent = q;
}
n = n.Parent;
while (n != NULL_NODE)
{
balance(n);
n = n.Parent;
}
}
Node p, child;
//This block set p as the node to be deleted.
if (n.LChild == null || n.RChild == null)
{
p = n;
}
else
{
p = Successor(n);
}
//In all 3 cases, there will be at most one child for n
if (p.LChild != null)
{
child = p.LChild;
}
else
{
child = p.RChild;
}
//Set the parent of the child
if (child != null)
{
child.Parent = p.Parent;
}
//Is the node to be deleted a root?
if (p.Parent == null)
{
this.root = child;
}
else
{
if (p.Parent.LChild == p)
{
p.Parent.LChild = child;
}
else
{
p.Parent.RChild = child;
}
}
//If the node to be deleted is not the paramter,
//this means an extra content replacement needs to be made.
if (p != n)
{
n.Key = p.Key;
}
Status InOrderTraverse(BiTree T, Status ( *Visit)(TElemType e)){
InitStack(S); p = T;
while(p || !StackEmpty(S)){
if (p) { Push(S, p); p = p->lchild; }
else {
Pop(S, p);
if(!Visit(p->data)) return ERROR;
p = p->rchild;
}
}
return OK
}
应该是一段很简洁高效的C/C++代码,但是看得我瞬间晕倒。我根本没看懂是怎么回事情。
再回头想一想什么才算利用栈写循环遍历呢?
首先,作为中序遍历,必然总要走所有的左子树。
Stack< Node > stack = new Stack< Node >();
Node n = this.root;
while (n != null)
{
stack.Push(n);
n = n.LChild;
}
这一步必然是这样的。
其次,当栈找完所有的左子树的时候,就要打印出该节点的值(这个没问题)。这个时候其实相当于在访问中间节点,因为如果把空的左节点看成非空,那么其实就是打印一个空值,也就是说正真的打印其实是中节点。那么此时只需要遍历该节点的右子树就可以了。
while (stack.Count != 0)
{
n = stack.Pop();
_visit(n);
stack.Push(n);
}
但是,光这段代码不可能继续去遍历这颗右子树啊!怎么办?这个时候看看原来的C/C++代码,有点感觉了。只要把这两个循环结合在一起就可以解决这个问题。灵感来自最后那句stack.Push,只要重新复制n就解决了,不过这其实是一个揣测的操作,我是一点理论根据也没有,就算对了,我感觉依然没有完全搞懂的样子。
while (n != null || stack.Count != 0)
{
if (n != null)
{
stack.Push(n);
n = n.LChild;
}
else
{
n = stack.Pop();
_visit(n);
n = n.RChild;
}
}
class MyArrayList< T >
{
private const int INIT_SIZE = 2;
public int Length { get; private set; }
public int Capacity { get; private set; }
private T[] array;
public MyArrayList():this(INIT_SIZE)
{
}
private MyArrayList(int size)
{
array = new T[size];
this.Length = 0;
this.Capacity = size;
}
public T this[int i] {
get
{
if (i < 0 || i > this.Length - 1)
throw new IndexOutOfRangeException();
return this.array[i];
}
}
private void CheckCapcity()
{
if (this.Length >= this.Capacity)
{
if (this.Length == int.MaxValue)
throw new OverflowException();
int i = this.Length - 1;
if (this.Length < int.MaxValue / 2)
{
this.Capacity *= 2;
}
else
{
this.Capacity = int.MaxValue;
}
Debug.Print("Expand to {0}", this.Capacity);
T[] newArray = new T[this.Capacity];
while (i >= 0)
{
newArray[i] = array[i];
i--;
}
this.array = newArray;
GC.Collect();
}
}
public void Add(T t)
{
this.CheckCapcity();
this.array[this.Length++] = t;
}
public T[] ToArray()
{
T[] a = new T[this.Length];
for (int i = 0; i < this.Length; i++)
{
a[i] = this.array[i];
}
return a;
}
public void Remove(int position)
{
if (position < 0 || position >= this.Length)
{
throw new IndexOutOfRangeException();
}
for (int i = position; i < this.Length - 1; i++)
{
this.array[i] = this.array[i + 1];
}
this.Length--;
}
public void Clear()
{
for (int i = 0; i < this.Length; i++)
{
this.array = null;
}
this.Length = 0;
}
}
以下为一个Hashtable:
class MyHashtable
{
private MyArrayList< object > keys;
private ValueChain[] values;
private class ValueChain
{
public object Value { get; set; }
public object Key { get; set; }
public ValueChain next;
public ValueChain(object key, object value)
{
this.Key = key;
this.Value = value;
this.next = null;
}
}
//Apparently this is way too samll, it can ensure that Collision happens.
private const int SIZE = 4;
private MyHashtable(int size)
{
this.keys = new MyArrayList< object >();
this.values = new ValueChain[size];
}
public object[] Keys
{
get
{
return this.keys.ToArray();
}
}
public object[] Values
{
get
{
MyArrayList< object > values = new MyArrayList< object >();
foreach (object k in this.Keys)
{
values.Add(this[k]);
}
return values.ToArray();
}
}
public object this[object k]
{
get
{
int h = hash(k);
if (this.values[h] == null)
{
throw new IndexOutOfRangeException();
}
else
{
ValueChain p = this.values[h];
while (p != null)
{
if (p.Key == k)
return p.Value;
p = p.next;
}
throw new IndexOutOfRangeException();
}
}
set
{
this.Add(k, value);
}
}
public MyHashtable()
: this(SIZE)
{
}
public void Add(object key, object value)
{
int h = hash(key);
ValueChain v = new ValueChain(key, value);
if (values[h] == null)
{
values[h] = v;
keys.Add(key);
}
else
{
ValueChain p = values[h];
ValueChain q = null;
while (p != null)
{
if (p.Key == key)
{
p.Value = value;
return;
}
q = p;
p = p.next;
}
q.next = v;
keys.Add(key);
Debug.Print("Collision: {0}", key);
}
}
private int hash(object key)
{
//Obviously, this is a dumb idea.
return Math.Abs(key.GetHashCode()) % SIZE;
}
}
很明显的一点就是在比较Key的时候泛型就不管用了,这个时候要么用IComparable和IComparer两个接口,要么就用object一了百了。显然图省事就是object啦~