闲话动态KML

Post on by michaelyin

最近在Google Map开发中开发中用到了动态生成KML在地图中动态显示数据,下面来简单的把其中的知识点讲一下。

KML是一种采用XML 语法与格式的语言,它被用来描述地理信息,如点,线,多边形等等,可以被Google map和Google Earth等软件识别并显示。我们可以在Google Earth把我们感兴趣的一些地点标识出来,然后生成KML文件,通过分享这个文件来让别人在Google map或者google earth中看到我们标注的信息。下面是一个简单的KML文件。

<?xml version="1.0" encoding="UTF-8"?>
<kml xmlns="http://www.opengis.net/kml/2.2">
  <Placemark>
    <name>Simple placemark</name>
    <description>Attached to the ground. Intelligently places itself 
       at the height of the underlying terrain.</description>
    <Point>
      <coordinates>-122.0822035425683,37.42228990140251,0</coordinates>
    < ...

算法学习之快速排序

Post on by michaelyin

快速排序通常是用于排序的最佳实用选择,因为它的平均性能相当好。

快速排序和先前讲到的合并排序一样,体现了算法设计中的分治的思想。我们首先将问题进行分解,将数组划分成两个部分A[p…q-1]和A[q+1…r],使得A[p…q-1]中的元素小于等于A[q],然后分别解决前面一个数组和后面一个数组的排序,最后进行合并,由于这两个数组是就地排序(in place)的,所以不用像合并排序中一样进行过多的合并的操作。

由于中间的分别排序的部分可以使用递归实现,所以快速排序中关键的地方就是如何将数组进行分解了。

/// <summary>
/// 对数组进行分组,返回分界处的index
/// </summary>
public static int Partition(int[] array, int firstIndex, int secIndex)
{
    int key = array[secIndex];
    int k = firstIndex;
    for (int j = firstIndex; j < secIndex; j++)
    {
        if (array[j] < key)
        {
            Utils.Swap(ref array[k], ref array[j]);
            k ...

由类能否包含自己说开去

Post on by michaelyin

下午在Coding的时候突然想到了一个问题,类到底能不能包含自己?在什么情况下能包自己?

当时正在实现一个类似链表的功能,在一个节点中需要有下个节点的引用的数据,比如像这样子的代码。

public class Node
{
    public int data;
    public Node Next;
}

在Node中有一个Node类型的引用地址,用来找到这个节点的下一个节点。默认构造函数调用后会将data置0,Next置null,当时我写到这里突然想起来好像在哪里看到过类中包含类自己是不行的。于是在Console中跑了一遍,运行结果是对的。断点显示初始化的值是我预计的结果。那到底在什么情况下类不能包含自己呢?要知道答案,我们还是先要说说初始化背后的故事。

在我初始化节点的时候我调用的是new Node()这个方法,这个时候.Net会首先计算类中成员需要的内存空间,这里就是int类型和Node引用类型的地址的空间(实际还有别的,不过和我们讨论的问题无关,故在这里省略),然后在内存中分配内存空间,分配了内存空间后就会对类中的变量进行初始化,比如我的代码中写的是public int data = 3;那么data这个变量就会在这时被赋值3,就变量初始化后然后会调用类的相应的构造函数,因为我这里没有实现构造函数,所以最后的值就是data的值为0,Node的值为null(引用类型的默认初始化值都是null).

到这里我们已经把类的初始化过程弄的比较清楚了,现在要做的就是如何改变代码使程序异常。我们把注意力放到public Node Next; 这一句上,这里我没有加new Node(),这个方法,所以Next的值为0,现在我们在后面把初始化类的代码加上。就像这样

public class Node
{       
    public int data;
    public Node Next = new Node ...

算法排序之堆排序

Post on by michaelyin

堆排序的重点在于对堆的理解,首先堆是一种数组对象,同时,它也可以被视为一棵完全二叉树,树中的每个节点从上到下,从左到右和数组中的每个元素是一一对应的,二叉树的每一层都是填满的,除了最后一层以外。

比如数组中的第一个元素就是二叉树的根节点,第二个就是元素就是根节点的左边的子节点,而第三个节点就是根节点的右边的子节点,然后第四个节点就是根节点的左边的子节点的左边的子节点,这样以此类推。

通过给定的节点的数组下标,我们可以求出该节点的左边子节点的坐标和右边子节点的坐标。

public static int Left(int parent)
{
    return (2 * parent) + 1;
}

public static int Right(int parent)
{
    return (2 * parent);
}
```csharp

堆有两种,一种是最大堆,一种是最小堆,最大堆的性质就是每个母节点都比它的子节点大,最小堆的性质则相反。我们这里的排序就用最大堆来排序。

Heapify这个方法用来保持最大堆的母节点总是比子节点大这个特性,将数组坐标i和数组输入,它从母节点i处开始比较,如果发现子节点比母节点大,那么就会让母节点下降,下降的母节点还有可能比下面的节点大,所以又进行比较。方法执行完之后,可以保证以i为根节点的子树成为最大堆。关于这个方法有两种实现方式,递归和循环调用,我都写出来了,大家可以都看一下。

```csharp
/// <summary>
/// 保证最大堆的性质,采用递归方法实现
/// </summary>
/// <param name="arrayToSort">< ...

字符编码那些事儿

Post on by michaelyin

这几天专门花时间好好看了下字符编码的东西,在这里写篇随笔把知识好好梳理一下。

讲到字符编码,还是从最基本的ASCII讲起咯。

在计算机刚开始使用时候,人们必须用计算机里面的01这样的二进制组合来表示一些基本的英文字母和字符,当然了,每个人都可以有自己的一套编码标准来完成这个看似简单的功能,不过,为了不同的计算机系统之间能够相互通信而不产生混乱,那么所有的计算机就必须采用相同的编码标准,所以美国的标准化组织就出台了ASCII编码标准,统一规定了上述符号和字母用哪些二进制来表示。在这里要加的一点是,标准ASCII只用了7位,最前面的一位是用来做奇偶校验的。比如英文字母a在ASCII编码中用二进制01100001表示,十六进制就是61.

使用了ASCII编码后,原本的问题得到了很好的解决。但是,这里又有了新的问题,它并不能对其他非英语国家有很好的支持。比如,我如何编码汉字,日本文字,朝鲜文字,阿拉伯语,还有俄罗斯语等等。由于汉字这样的文字数目较多,用一个Byte(也就是8 bit)来提供编码方案显然是不现实的,这时,双字节字符集(DBCS:double-byte character set)就出现了,它的出现就是为了解决刚刚说到的这个问题的。

先来解释下什么是DBCS,DBCS简单的说就是使用两个Byte来表示一个字符,而且DBCS的最初的还是ASCII代码,所以说DBCS是兼容ASCII的。而且它表示ASCII只用了一个Byte,这里说一个问题,假设给了你一连串的Byte数组,你解码的时候如何知道这个Byte的解码需要用到他的下一个Byte呢?这里需要看前一个Byte的最高位,也就是最左边的那个bit,前面已经说过,ASCII只用了7位,如果最高位不用来做奇偶校验的话,那么最高位其实是0,DBCS中的前面的一个Byte的最高位如果为1的话,那么我就可以知道这个字符的解码需要用到后面一个Byte.

不同的国家都有一套自己国家的字符的DBCS的解决方案,比如中国字符集就是GB2312,日本是shift_jis,韩国是ks_c_5601-1987,由于出现了不同的字符集,所以这里又出现了另外一个问题,两个Byte在不同的字符集中代表的字符是不一样的,所以计算机在跨语言通信时很麻烦。

这里还需要另外提到的一点是,上面提到的DBCS其实都是对于一种叫做ANSI编码的扩展,也就是说其实上面提到的那几种DBCS都是ANSI编码,只不过在简体中文操作系统中 ...