2005年02月13日
计算机自动编程－－路在何方？（1）

 

脱离解决问题的具体过程，仅通过向计算机描述所需程序需满足的功能，从而让计算机自己生成解决问题的方法，这无疑是计算机编程方式的必然方向。我在下文里将会称其为计算机自动编程。
曾经在csdn等处看到几篇关于计算机自动编程的文章，提出了一些设想，但它们总离不开一点,那就是计算机自动编程是要建立在未来计算机强大的计算能力之上的，因为它或多或少要和人工智能扯上联系。这样的未来真让人沮丧，因为知道现在计算机似乎还没有一点“智能”的影子，即使有了又会怎样呢？它的效率如何？它会不会继承人类智慧的缺陷呢？比如，它编出来的程序会不会也出现bug？
但仔细分析这个问题，前景或许没那么黯淡。
让我们回到第一段：
通过向计算机描述所需程序需满足的功能，从而让计算机自己生成解决问题的方法。
看来，计算机自动编程需要解决两个重大问题：
一是如何建立一种语言，用它来描述程序的功能。这种语言最好是高于现在的编程语言的，因为它不对解决问题的具体过程作出描述，我们不妨称之为“面向功能”的语言。
二是如何让计算机自己找到解决问题的办法。这无疑才是最重要的问题，我们要往下探索的也正是这个。
第一个问题中的语言是完全可以让现有语言代替的－－几乎所有问题都可以用一种程序化的办法获得其解决算法，那自然就是穷举（当然也有例外，比如输出只有一个bit的算法就不行）。我们可以毫不费力的用穷举法写出某个问题的解决算法，这个算法就已经包含了要实现功能的全部描述。
下一步要做的，就是如何把这个笨的恐怖的算法转化为一个低时间复杂度的算法。到此，第二个问题就转化为：
如何进行算法化简？
或许可以说，解决了这个问题就解决了计算机自动编程的问题。

每个算法都可以实现一个函数，尽管它或许是处理字符串之类数据类型的函数，我们是可以用编码将其定义域/值域映射到自然数集N上的。换句话说，每个算法所实现的功能，都可以用数论函数来表示。
这样，算法的化简，其实也就是其对应函数的化简。
要实现算法化简，必然要求找到一系列算法之间变换的规则（这里的算法必须是计算相同的函数的，我们将称之为等效算法），这类似于数学上的运算律，而事实上，数学中的运算律也正是来自于这组规则的。
那我们可以问很多问题，比如，这会是一组很简单的规则吗？使任一个算法都可以变换到它的任意等效算法的规则存在吗？是不是所有的算法都可以化简？

我们先来看第二个问题：使任一个算法都可以变换到它的任意等效算法的规则存在吗？

对于每一个证明问题，都可以看作是判定某个集合的所有元素是否都具有某一性质。进一步的，证明某一命题就是处理定义在某一集合X上的一个函数 f（x），看是否它对所有的输入都输出1。我们要是把计算这个f（x）的算法化简，将会的到什么呢？无疑，这个算法最简单的等效算法就只有一句：return 1。这说明，算法化简意味着计算机证明。
这里便出现了新的问题：根据哥德尔不完备性定理，存在这样的命题，它确实是为真的，可对它你却无法证明。问题是，如果化简这样的命题对应的f，结果怎样？如果非要达到最简，那岂不是要永远得不到结果？
这样我们就得出了答案：

使任一个算法都可以变换到它的任意等效算法是不可能的，因为这么一组变换规则并不存在。

原因是显而易见的，上文中提到的计算f（x）的算法是等效于return 1的，然而二者却无法相互变换。


第三个问题，我们可以由混沌作出猜测。

一个简单的函数，通过迭代往往会产生不可预测的行为。比如虫口模型：

Xn+1＝kXn（1－Xn）

这个方程看似简单，但它可以产生极其复杂的行为。比如，当k取大于3.5699的一些值时，若以n为x轴，X为y轴建立一个坐标系，将每次迭代获得的x值画出来，你将会发现，x的变化几乎是毫无规律可循的，换句话说，它的表现几乎和一个随机变量没什么两样，这就是混沌。
混沌在现实中无所不在。同样的现象也出现在元胞自动机（CA）中。

下面是一段引用：

分析了 256 个初级 CA 和其他更复杂的 CA 后，Wolfram 发现 CA 可以分为四类。数学家和作家 Rudy Rucker 在其报告“Things Computer Science Tells Us About Philosophy”中准确地描述了这四种类型（请参阅 参考资料）。

第 1 类：恒定。 （所有种子都“死了”）
第 2 类：重复。 （循环，条带）
第 2A 类： 嵌套。（正则分形）
第 3 类: （伪）随机。 （激变）
第 4 类: 复杂。 （“不规则”。滑行。 一般性计算）

Wolfram 作出了似乎有道理的声明，大多数第 3 类和第 4 类 CA 可能是 无法省略计算的（computationally irreducible）：给出一个初始状态，要找出某一细胞在第 n 步时的值，必须从初始配置开始，完成所有 n 步计算。就是说，没有公式或者快捷方式可以预测 CA 的未来状态。

在这里，第3、4类CA显然是走向混沌了。值得注意的是最后一句话，此时，“没有公式或者快捷方式可以预测 CA 的未来状态”。这也就意味着，如果我们用算法将X和n的函数关系表示出来后，是有可能无法期望用算法化简的到一个较简单算法的，唯一预测未来状态的方法就是一步步的计算。当然，这应该只是Wolfram的一个猜测，还未被严格证明的，直觉上我对这个观点的正确性是没有怀疑的，有兴趣的朋友可以试着去证明。

其实，这两个问题的意义只是让我们窥见算法化简的某些端倪，让我们了解了它的能力极限。它们并不意味着算法化简前途渺茫，因为毕竟在实际应用中是很少碰上上述情况的。

下面是一些题外话。
哥德尔不完备性定理第一条定理是这么说的：
任何一个兼容的数学形式化理论中，只要它强到足以在其中定义自然数的概念，就可以在其中构造在体系中既不能证明也不能否证的命题。

该定理并不意味着任何公理系统都是不完备的，如欧几里德几何就可以被公理化为一个完备的系统。事实上，几何问题的计算机证明已经被解决了，这启发我们野心小一点，去寻求小范围内的化简规则或许会有好的结果。

归类于： 数据结构与算法 — 岚焕 @ 3:19 am 评论(2)
算法速度影响因素的本质 一

 

算法速度影响因素的本质
表面上，算法速度的影响因素繁多，但事实上，如果我们穷根究底的话，也会在这个看似繁乱无序的世界里找出一些本质的东西。
先考虑这么一个问题：
如果b地在a地正东方，一个人要从a地去b地，那他可以有什么方法来缩短所花的时间？
第一当然是交通工具。选择汽车和步行自然不可能是相同的效果，这对应与下文的第一部分：函数存储
第二是不走弯路，若他向东南方向走了，那他就在南北方向上有了向南的偏移，之后他就必须向东北方向走来抵消刚才的偏移，这对应与下文的第三部分：计算冗余。
现在让他的行进速度和其经验相关，比如，翻过第一座山后由于有了经验，今后翻山的速度会有很大的提升，这对应于下文的第二部分：过程存储

1 函数存储
计算机能以最快速度实现的操作，我们将称之为基本操作。比如简单的加减、逻辑运算，存储器读取写入，if…then语句等等。
显然，计算机能进行的基本操作越多，算法速度就越容易提升。图灵机可进行的基本操作是很少的，一个简单的加法都要计算上很多步，因此没人会去试图造台图灵机作电脑用^_^。
对输入为有限种可能的情况，我们可以建立一个散列表，将输入直接映射到内存地址上，而存储的内容为相应输入的输出结果，这样便产生了一个运行时间几乎和一次基本操作相当的算法。这样其实就是相当于把所要计算的函数直接存储到了内存里，使计算机又多了一个基本操作。可以看出这样对算法的速度提升会是惊人的（虽然是牺牲空间得到的）。这样方法其实我们在作算术中就应用到了：小学生背乘法表是为了什么？存储一系列函数，等计算更复杂的乘法时便可以将它分解成这些函数，然后快速得到结果。相必没人作乘法是先拆成加法，再一个个加起来吧？
综上所述，当算法中出现对一个函数的频繁调用，而这个函数又是定义域有限且元素不多的，我们就可以把该函数存储到内存里，做成一个基本操作，这样就会对算法效率有质的影响。

但基本操作少了也有它的好处，这样各种操作容易各司其职，功能互不交叉，要用操作a完成的功能b肯定不能替代，比如说变量值加1操作和goto语句。这样以来，要实现某个功能时就不需在各个可行的基本操作中进行孰优孰劣选择了。所以想用函数存储优化算法是很困难的，如果有一天计算机可以自己生成算法了，它是基本上不可能掌握上面所说的这种方法的，除非依赖人工智能。它可以轻松掌握的方法或许应该是下面这个：

2 过程存储
下文中将出现的“过程”不同于一般编程语言中“过程”的概念，它是指函数的一次特定调用，包括输入值和被调用函数。调用一个过程所返回的值即该输入值经该函数计算后的结果。在一次计算的某个时刻，访问任一个变量都相当于调用了一个过程，那是向前访问过去的计算结果，而调用函数是向后将数据或控制权传给未来的函数；反过来也成立，向过去只可能出现过程调用，而向未来只可能出现函数调用。

数据结构对算法速度的影响是和电子计算机提供的两个基本操作相关的，就是内存的读/写。和他们相关的其实还有建立中间变量之类一切和存储/读取相关的操作。
建立合适的数据结构，建立合适的中间变量都有可能大幅度提高算法效率，那它们的本质是什么呢？
一个量的存储便意味着今后可随时以一个单位时间的运算速度调用计算出该量的过程，这样，如果一个过程在一次计算中出现多次，那么将其第一次运行所得结果存储从而替代后来的多次运算无疑是高效的，这正是变量存读问题的关键所在：将计算过的结果存储，之后免除了计算过程，我们暂且称之为过程存储。
显然，过程存储是不同于函数存储的。后者是算法设计时就将函数“存储”了，它是运行中“存储”的；后者是通过增加基本操作来提高速度，而前者只是避免了重复计算，并未增加基本操作。
过程存储和函数存储一样，也是适用于当算法中出现对一个函数的频繁调用，而这个函数又是定义域有限且元素不多的时候。当然，它的效率会稍低。

过程存储还有另一个优美的描述，就是跨时间的信息传递。我们不妨把存储和读取的概念从视野中完全抹掉，一个量的存储只是将其传递给了未来的一个或多个函数，而读取只是接受了过去某个过程传来的输入。这样，过程的调用概念就更广了，成为了跨时间的概念。
这样我们不难理解中间变量和数据结构对算法影响的实质了，前者充当了调用过去过程的桥梁，避免了同一过程的重复计算，而后者是前者更复杂的形式，而且与指针关系紧密，所以我们暂且只举例说明。
例:
某算法的输入中包含一字符串s，算法运行中将对s进行大量的查找工作。
如果仅靠以上信息而且不考虑空间复杂度的话，我们知道散列表是存储s的最佳选择。
S中出现的所有字符通过散列函数f映射到不同的内存地址，而内存中的数据则为相应各字母在字符串中的位置。这样要比不改变S的数据结构而每次查找都用遍历S的方法好的多。
我们来分析它和过程存储的关系：建立散列表时，若在内存地址为A（值为f（K））的项中写入了一个数组，它存储了K出现在S中的所有位置。那么，这就相当于向未来的函数提供了这样一个过程的调用：
遍历S，记录所有值等于K的元素在S中的位置并将其放入一个数组中，返回这个数组。
当然，这个调用花费的时间是很短的，而远非遍历一遍S的时间。

3 计算冗余

下面我们只考虑数值计算中的情况。
且看这一段代码：

a++
a–

恐怕天下没比这更弱智的代码了吧？可它确实是代表了一类的影响因素，也就是我们要称之为计算冗余的东西。
看这个函数：

f（x）＝5x－3x

我们可以马上写出两种计算它的算法，一个按部就班的算（算法a）而另一个直接算2x的值（算法b）。然而二者在运行时间上是有不小差异的，影响二者运行时间的因素，正是计算冗余。
对算法a，如果用一个变量Y来存储结果的话，它是先被循环加x加5次，再被循环减x减3次，中间经过了先增大后减小的过程；而对算法b，却只是个增大的过程。它可以看成是a中增大x和减小x一对操作互相抵消的结果。
显然，计算冗余是由一对效果相反的操作同时出现在算法中造成的不必要的计算。但是否算法只要出现了相反操作就意味着还可以化简呢？显然不是，比如这个函数：

g（x，y）＝1+x-y

直接计算它的算法我们可以马上写出来，计算中必然会出现相反的操作，但是它已经是最简单的形式了，我们不可能靠抵消相反操作来化简它。
这二者的区别其实在于：前者计算中的一对相反操作（增大x和减小x）所进行的次数（5次和3次）是不决定于输入变量的，是仅靠算法本身就能确定的，它是算法本身所具有的一个属性，故我们可以依据它来进行算法的化简；而对于后者，一对相反操作（加1和减1）的次数（y次和z次）是决定于算法本身的，它随着输入变量不同的值而改变，因而是不可化简的。
我们可作如下总结：
一个算法中若出现了效果相反的操作且二者的次数都不是由输入变量决定的，那这个算法可以用抵消的方法化简。
虽然是在数值计算的实例中推出来的，可这个思想并不只适用于数值计算，它应该是对任何数据类型都有效的。

4 信息利用
先看这个问题：
折半查找的高效来自何处？
显然这里不关过程存储的事，必然是其他因素的缘故。
它的高效是因为利用了输入字串的有序。从信息的角度看，我们编写算法时并非对输入信息是一无所知的，它至少包含这一点，即：字串是有序的，且该序是由小到大（或反之）的。
这就是编程者对信息的利用充分与否的问题了。设计程序前必然会掌握关于该程序的一系列信息，主要包括输入数据的相关信息和功能描述。功能描述决定了程序的功能（或者说它所实现的函数），而数据相关信息则是预先知道的程序输入（函数定义域）信息的特征的描述。如果能将这些信息充分在算法中表达出来，也就是算法如果能充分利用这些信息，能对速度提升有很大影响。
类似的例子在实际应用中是很常见的，比如统计关键词被搜索的频率来调整算法，优先搜索频率高者。

归类于： 数据结构与算法 — 岚焕 @ 3:12 am 评论(0)
2005年02月10日
后入为主—-虚函数

后入为主—-虚函数

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


后入为主

                    —-虚函数

作者：HolyFire

说一个人后入为主，通常是说耳根子软，人家说什么就把原先的忘掉了，别人说向东走，他就向东走，一会儿有人说向西了，他立马赶回来。不过好处显而易见，这个人特别听话，如果你有时候不知道自己要干什么，或者不确定一会儿要干什么，那么就叫他在旁边等着，到你拿定主意的时候，再告诉他你的要求，让他照办。现实中这样的事情并不少见，秘书需要作记录，写报告，安排行程，联络客户等等，而这些工作都是在你的指示下去做的。如果编程的时候也有这么听话的代码就好了，当然这不是做梦，这完全可以实现。

我们小学的时候就学过求解方程，里面提到的概念有一个未知数，他用一个可以为任意数的符号代表一个暂时不知道值的数，然后通过运算规则得到符合要求的值，用编程的角度来看，他加上了一个间接层，我们暂时不处理数值，而是处理一个与数值有关的符号，如果变化的是数值也就是对应的属性，我们可以用成员变量来处理，如果变化的是运算规则呢。记得作微积分吗，y=f（x）。这个f(x)是可变的，要让我们的解决方案通用于各种可能的f(x)，那就要提供一个间接层来连接不同的函数，在C++中这太简单了，用函数指针就可以办到。

指针的作用就是可以保存某种类型的对象在内存中的位置，改变指针的值就可以让他指向不同对象。（形象的说法，可以让我们更容易理解指针的意图，指针本身也是一个类型）

在C++中实现虚函数就是用函数指针的，编译器在类中隐藏了一个函数指针数组（因为成员函数可能有很多）叫做虚函数表。

class A{

//…data members

public:

virtual func1();

virtual func2();

virtual func3();

//…func members

};

这个类里有三个虚函数

他们在内存里的某处

address1  [A::func1]  

address2  [A::func2]  

address3  [A::func3]  

实例化一个A类的对象a

A a;

得到a的结构是这样的

[

虚函数表

[func pointer1]  address1

[func pointer2]  address2

[func pointer3]  address3

]

[

data members

…

]

使用a的成员函数func1的时候，事实上由在[func pointer1]的值address1得到[A::func1]的位置，然后再调用它，显然这里多了一个寻找函数位置的步骤，所以，使用虚函数将降低执行效率，在效率和灵活性之间的取舍，就看你自己的要求了。

进一步，当从A继承一个类B的时候，情况有是怎么样的呢

class B : public A{

//…data members

public:

virtual func1();

virtual func2();

virtual func3();

//…func members

};

这个类里有三个虚函数

他们在内存里的某处

address4  [B::func1]  

address5  [B::func2]  

address6  [B::func3]  

实例化B类的一个对象

B b;

得到b的结构是这样的

[

A的虚函数表

[func pointer1]  address1

[func pointer2]  address2

[func pointer3]  address3

]

[

A的data members

…

]

[

B的虚函数表

[func pointer1]  address4

[func pointer2]  address5

[func pointer3]  address6

]

[

B的data members

…

]

为了正确执行b->func1对应的是address4处的[B::func1]，必须能知道要去B的虚函数表查找，呵呵，好的方法不应该只用一次，聪明的读者一看就知道，再加入一个指针就能操作不同的虚函数表，对了，这里C++隐藏了一个虚函数表指针来访问不同的虚函数表，在class B被创建的时候，这个指针指向B的虚函数表。

举一反三，如果从B类再继承类C，只要将虚函数表指针指向C的虚函数表即可。

到这里，虚函数的把戏都给大家拆穿了，C++中指针是个好东西，如果善加利用，则能功办事倍。

我们用C++来看一下虚函数的效果

#include <iostream>

#include <stdlib.h>

using namespace std;

class NormalA{

public:

       void DoSomething( void ){ cout << “This is class NormalA.” << endl; }

};

class NormalB : public NormalA{

public:

       void DoSomething( void ){ cout << “This is class NormalB.” << endl; }

};

class NormalC : public NormalB{

public:

       void DoSomething( void ){ cout << “This is class NormalC.” << endl; }

};

class VirtualA{

public:

       virtual void DoSomething( void ){ cout << “This is class VirtualA.” << endl; }

};

class VirtualB : public VirtualA{

public:

       void DoSomething( void ){ cout << “This is class VirtualB.” << endl; }

};

class VirtualC : public VirtualB{

public:

       void DoSomething( void ){ cout << “This is class VirtualC.” << endl; }

};

int main()

{

      NormalA na;

      NormalB nb;

      NormalC nc;

      VirtualA va;

      VirtualB vb;

      VirtualC vc;

      NormalA * pna;

      VirtualA * pva;  

      na.DoSomething();

      nb.DoSomething();

      nc.DoSomething();

      va.DoSomething();

      vb.DoSomething();

      vc.DoSomething();

      pna = &na;

      pna->DoSomething();

      pna = &nb;

      pna->DoSomething();

      pna = &nc;

      pna->DoSomething();

      pva = &va;

      pva->DoSomething();

      pva = &vb;

      pva->DoSomething();

      pva = &vc;

      pva->DoSomething();

      cin.get();

      return 0;

}

结果是

This is class NormalA.   //调用的是NormalA：：DoSomething();

This is class NormalB.   //调用的是NormalB：：DoSomething();

This is class NormalC.   //调用的是NormalC：：DoSomething();

This is class VirtualA.   //调用的是VirtualA：：DoSomething();

This is class VirtualB.   //调用的是VirtualB：：DoSomething();

This is class VirtualC.   //调用的是VirtualC：：DoSomething();

This is class NormalA.   //调用的是NormalA：：DoSomething(); 没有虚函数表，NormalA *指定了类型

This is class NormalA.   //调用的是NormalA：：DoSomething(); 没有虚函数表，NormalA *指定了类型

This is class NormalA.   //调用的是NormalA：：DoSomething(); 没有虚函数表，NormalA *指定了类型

This is class VirtualA.   //调用的是VirtualA：：DoSomething(); 虚函数表指针指向的是VirtualA

This is class VirtualB.   //调用的是VirtualB：：DoSomething(); 虚函数表指针指向的是VirtualB

This is class VirtualC.   //调用的是VirtualC：：DoSomething(); 虚函数表指针指向的是VirtualC

虚函数看来于函数重载有些共通之处，但是函数重载在编译期间就可以确定下来我们要使用的函数，是可预测的；而虚函数在运行时刻才能确定到具体的函数，是不可预测的，对于虚函数这一特性有一个专用术语—-晚绑定，运用虚函数这种方法叫做函数覆盖。

归类于： 数据结构与算法 — 岚焕 @ 10:09 pm 评论(0)
由始至终—-构造与析构

由始至终—-构造与析构

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


由始至终

                         —-构造与析构

作者：HolyFire

我们在平时的生活中一般会总结出一些规律，早上起床会刷牙洗脸，晚上会洗澡睡觉，这些都成了惯例。使用瓶装调味品时先将瓶盖打开，用完后将瓶盖盖上。这是一种好习惯。但是有些人不同，他们往往偷懒，一个常常不刷牙不洗脸不洗澡的人会有体味，东西放得乱七八糟的人生房间很不整洁。这些都是我们不希望看到的。当然编程中我们也不希望代码乱七八糟。

使用一个未初始化的变量简直就是灾难，使用一个未初始化的指针将导致崩溃。这是我的忠告。在C++中初始化不会有附加的效果，不会降低效率，我们要做的是养成好习惯，产生一个对象的时候就将它初始化。

对于

Object.Init();

Object.Free();

这样的调用并不是很困难，要记住他也不是难事，但是谁都不能保证他永远不会忘记，更糟糕的是

Object.Init();

Object.Free();

没有配对使用

Object.Init();

Object.Free();

Object.Free();

或

Object.Init();

Object.Init();

Object.Free();

会带来什么样的结果，谁也不知道，而且这样的错误，编译器不会报错。这是多么可怕的错误，一个程序员最怕遇上的就是这样的逻辑错误，它可能为了找这样的一个错误花上一整天时间。

让我们看看有什么好的办法。

一个对象按时间来分析，一般有三个阶段，出生，活动，死亡。与我们要做的有什么相关之处呢，初始化，运行，释放。很好，对照一下，我们发现在对象出生的时候初始化，死亡的时候释放，如果这一切能用这样的机制来操作，我们就再也不用担心会由于忘记或错误的使用带来麻烦了。

C++里就提供了这样的机制。使用他有个约定

class Object{

public:

       Object();   //与类同名的函数，该函数没有返回值，叫做构造函数

~Object();  //类似的，在构造函数名前加一个取反符号，叫做析构函数

};

构造函数将在对象产生的时候调用

析构函数将在对象销毁的时候调用

调用的过程和实现方法由编译器完成，我们只要记住他们调用的时间就行了，而且他们的调用是自动完成的，不需要我们控制。

#include <iostream>

using namespace std;

class Object{

public:

       Object(){ cout << “Object ON!” << endl; }

       ~Object(){ cout << “Object OFF!” << endl; }

};

void main()

{

       Object o;

}

运行结果

Object ON!

Object OFF!

构在函数和析构函数确实的执行了

现在我们来一个应用的例子

一个字符串类，它需要保存字符串的内容，但是它不知道字符串的大小，那么设计这个字符串类的时候，保存字符串的成员变量就不能用固定大小的数组，而是用可以间接操作数组的指针。

#include <iostream>

#include <string.h>

using namespace std;

class string{

private:

       char * data;

public:

       string(){ data = NULL; }

       string( char * str )

              {

              cout << “Copy string: ” << str << endl;

              data = new char[ strlen(str) + 1 ];

              memcpy( data , str , strlen(str) + 1 );

              }

       char * Data(){ return data; }

       ~string()

              {

              if( data )

                     {

                     cout << “Free string: ” << data << endl;

                     delete data;

                     }

              }

};

void main()

{

       {

string s(“abcd”);

       cout <<”Show String: ” << s.Data() <<endl;

}

cin.get();

}

Copy string: abcd   //执行了string::string( char * str ) 构造函数

Show String: abcd

Free string: abcd       //由于在{}中产成的对象是临时对象，它的生命期在}后就结束了，所以string::~string() 析构函数被调用

申请内存和释放内存的操作自动完成了，构造函数和析构函数的目的在于一个类可以象普通类型一样初始化和释放，从而保证了封装。

上面的例子有两个构造函数，这么什么大不了的，我们看过《面面俱到—-重载》得都知道，重载的把戏。

要注意的是构造函数可以有参数，在继承中如何处理呢。

class mystring : public string{

public:

       mystring( char * str ):string( str ){ }

}

mystring( char * str ):string( str )

记住这样的形式，给自己的父类传递函数就用这样的书写格式，这是一个约定。

构造函数后面加上一个:表示后面是一个初始化序列，说它是一个序列是因为它可以初始化多个成员变量，在初始化序列里调用向父类传递参数是为了保证类的产生的顺序，先产生父类，然后是子类。使用初始化有个好处就是可以提高效率。

string(){ data = NULL; }

可以改写成

string():data(NULL){ }

他的作用是产生成员变量char * data时将他的值置为NULL。从而少了data = NULL;这步操作。

注意，这里构造和析构有一个顺序问题，就是构造时应该从基类开始按继承的层次顺序调用，析构的时候顺序正好相反。这样处理是因为，子类可能在构造函数里使用父类的成员变量，如果父类还没有创建，那就会有问题，而析构的时候，如果父类先析构，也会有这样的问题。

析构函数还有一个能否正确运行的问题。

#include <iostream>

using namespace std;

class One{

public:

       One(){ cout << “One ON!” << endl; }

       ~One(){ cout << “One OFF!” << endl; }

};

class Two : public One{

public:

       Two(){ cout << “Two ON!” << endl; }

       ~Two(){ cout << “Two OFF!” << endl; }

};

class Three : public Two{

public:

       Three(){ cout << “Three ON!” << endl; }

       ~Three(){ cout << “Three OFF!” << endl; }

};

void main()

{

       Three three;

}

运行结果

One ON!

Two ON!

Three ON!

Three OFF!

Two OFF!

One OFF!

正确

void main()

{

       Three * three = new Three;

        delete three;

}

运行结果

One ON!

Two ON!

Three ON!

Three OFF!

Two OFF!

One OFF!

正确

void main()

{

       One * three = new Three;

        delete three;

}

运行结果

One ON!

Two ON!

Three ON!

One OFF!

不好了，Two和Three的析构都没有运行，怎么会这样，原来One * three指出了指针指向的是一个One类的对象。如何得到正确的结果呢，如果能让One类记住被继承后的变化就好了。

对了！虚函数，在《后入为主—-虚函数》中可以知道，虚函数有这个特性，不信试试看。

class One{

public:

       One(){ cout << “One ON!” << endl; }

       virtual ~One(){ cout << “One OFF!” << endl; }

};

void main()

{

       One * three = new Three;

        delete three;

}

运行结果

One ON!

Two ON!

Three ON!

Three OFF!

Two OFF!

One OFF!

正确

这个特点很重要，我们要牢牢记住，我们称这种方法为“虚析构”，在多态里运用非常广泛，也是编写可复用代码的一个重要技巧。

构造和析构的作用机制就是自动化，简化编程的复杂度。还有要记住的是，在一个类的构造函数里分配了的资源尽量要记得在该类的析构函数里释放，当然也允许提前释放，你可以在析构函数里判断它是否已经释放，如果没有就释放。这就是—-由始至终，它间接的描述了一个对象的生和死（记住这一点很重要，因为我以后会讲到如何运用这个特性控制对象的生死）。

归类于： 数据结构与算法 — 岚焕 @ 10:08 pm 评论(0)
乱码大全(五)

乱码大全(五)

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


 

1. GB码和Big5码

    GB码是中国大陆、新加坡等国家和地区使用的一种汉字编码方法。Big5码是中国台湾省用的一种汉字编码方法。它们的编码方法是完全不同的两种方法，它们之间的转换只能通过“查表法”来进行。所以说转换的方法很简单，困难的是“表”的生成。很多文章对此都做过介绍，我在此就不详述了。在我的主页上有我写的“汉字转码通V1.0”的源程序，其中有这两个“表”，可以直接使用。

 

2. HZ码

    HZ码是为了使只能传送7bit信息的邮件服务器或网关能传送8bit信息而定义的编码，也是中文常用编码的一种。它和上面介绍的Quoted-Printable码都只能对文本进行编码，即编码时忽略控制字符。

    这种编码的也是很好辨认的：有许多“~{”和“~}”，而且总是成对出现。下面是HZ码的一个例子：

                         ~{!6BRBkKc7(4sH+!7~}

       ~{WwU_~}:mogao~{#,0WTF;F:WU>#(~}telnet://202.112.20.132:23~{#)3IT1!#~}

             ~{D*8_Hm<~9$WwJR#:~}http://mogao.bentiun.net

                     Emailto:mogao@371.net

          *********************************************              

          * ~{3}AK<GRdJ2C46<2;4xW_#,3}AKWc<#J2C46<2;AtOB~}*

          *********************************************

 

    您可以打开“南极星”看这段文字。

    它的算法更简单：读一个字符，如果是8位字符，就把它的最高位清零。把连续的8位字符清零后的输出用“~{”和“~}”括起来。解码时：把是用“~{”和“~}”括起来的部分每个字符的第8位置“1”即可。

 

    上面介绍的三种编码之间的转换是经常遇见的，我写的“汉字转码通V1.0”可以方便的在这三种之间转换，我把它的源程序公开，方便广大网友的学习。

 

三.其他常用编码

1.  Unicode

    Unicode应用中最典型的例子是：IE4以上版本对HTML的编码。它可以说是未来Windows下唯一的字符集。但它还很不完善，而且Win95和Win98对它的支持还很有限，甚至它还没有一套完整的标准。不过，微软最新推出的Office2000和马上就要推出的Windows2000将全面支持Unicode。Unicode取代其他编码将会是必然的趋势。不过，在近一两年Unicode并不会占主导地位，就是在占主导地位后，因为操作系统的差异，其他编码也不会立即消亡。它的中文资料可以在Office2000和Windows2000所带的文档中找到，它的官方网站是：http://www.unicode.org/。

 

2. Binhex

    BinHex 编码是 Macintosh 计算机（也就是俗称的“苹果电脑”）上用可打印字符表示/传输二进制文件的一种编码方法。它的主要用途是在电子邮件程序中Attach二进制文件。大部分的电子邮件程序不支持这种格式（Eudora支持），但用WINZIP可以进行解码。它的资料请查阅Macintosh计算机带的相关文档。

归类于： 数据结构与算法 — 岚焕 @ 9:54 pm 评论(0)
乱码大全(四)

乱码大全(四)

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


 

Quoted-Printable

    Quoted-Printable简称QP， 一般用在Email系统中。它通常用于少量文本方式的8位字符的编码，例如Foxmail就用它做对主题和信体的编码。这种编码的应该是很好辨认的：它有大量的“=”。下面是它的一个例子：

 

Mime-Version: 1.0

Content-Transfer-Encoding: quoted-printable

 

                         =A1=B6=C2=D2=C2=EB=CB=E3=B7=A8=B4=F3=C8=AB=A1=B7

       =D7=F7=D5=DF:mogao=A3=AC=B0=D7=D4=C6=BB=C6=BA=D7=D5=BE=A3=A8telnet://202.112.20.132:23=A3=A9=B3=C9=D4=B1=A1=A3

             =C4=AA=B8=DF=C8=ED=BC=FE=B9=A4=D7=F7=CA=D2=A3=BAhttp://mogao.bentiun.net

                     Emailto:mogao@371.net

          *********************************************              

          * =B3=FD=C1=CB=BC=C7=D2=E4=CA=B2=C3=B4=B6=BC=B2=BB=B4=F8=D7=DF=A3=AC=B3=FD=C1=CB=D7=E3=BC=A3=CA=B2=C3=B4=B6=BC=B2=BB=C1=F4=CF=C2*

          *********************************************

 

    你可以把它单独存成一个文件，取名为：mogao.eml，双击可以用OutLook打开（前两行为邮件的原始信息，从第四行开始为编码内容）。

    QP的算法可以说是最简单的也可以说是编码效率最低的（它的编码率是1:3），它是专门为了处理8位字符制定的。它的算法是：读一个字符，如果ASCII码大于127，即字符的第8位是1的话，进行编码，否则忽略（有时也对7位字符编码）。编码很简单，看下面的C语言描述即可：

/*QP编码*/

void qp(unsigned char sour,unsigned char first,unsigned char second)

/* 

  sour:要编码的字符

  first:编码后的第一个字符

   second:编码后的第二个字符

  first和second为返回值

*/

{

 if(sour>127)  

 {first=sour>>4;

  second=sour&15;

  if(first>9) first+=55;

  else first+=48;

  if(second>9) second+=55;

  else second+=48;

  printf(“%c%c%c”,’=',first,second);

 }

}

 

/*QP解码*/

void uqp(unsigned char sour,unsigned char first,unsigned char second)

/*

  sour:解码后的字符

  first:QP码的第一个字符

   second:QP码的第二个字符

  sour为返回值

*/

{

 if(first>=65) first-=55;

 else first-=48;

 if(second>=65) second-=55;

 else second-=48;

 sour=NULL;

 sour=first<<4;

 sour|=second;

}

 关于QP的详细说明和准确定义可以参阅RFC2045。


归类于： 数据结构与算法 — 岚焕 @ 9:53 pm 评论(0)
乱码大全(三)

乱码大全(三)

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


 

Base64

    Base64和下面将要介绍的Quoted-Printable都属于MIME（多部分( multi-part)、多媒体电子邮件和 WWW 超文本的一种编码标准，用于传送诸如图形、声音和传真等非文本数据）。MIME定义在RFC1341中。

    Base64是现今在互联网上应用最多的一种编码，几乎所有的电子邮件软件头把它作为默认的二进制编码，它已经成了现今电子邮件编码的代名词。

    下面是Base64的一个例子，从例子中，您也可以看到Base64与电子邮件的的紧密联系：

Content-Type: text/plain;charset=”cn-gb”

Content-Transfer-Encoding: BASE64

 

CQkJICAgIKG2wtLC68vjt6i088irobcNCgnX99XfOm1vZ2Fvo6yw19TGu8a619W+o6h0ZWxuZXQ6

Ly8yMDIuMTEyLjIwLjEzMjoyM6Ops8nUsaGjDQoJICAgICAgxKq438jtvP65pNf3ytKjumh0dHA6

Ly9tb2dhby5iZW50aXVuLm5ldA0KCQkJRW1haWx0bzptb2dhb0AzNzEubmV0DQoJICAgKioqKioq

KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqICAgICAgICAgICAgICAgDQoJ

ICAgKiCz/cHLvMfS5Mqyw7S2vLK7tPjX36Oss/3By9fjvKPKssO0tryyu8H0z8IqDQoJICAgKioq

KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq

 

    你可以把它单独存成一个文件，可以取名为：mogao.eml，双击可以用OutLook打开（前两行为邮件的原始信息，从第四行开始为编码内容）。

    Base64的算法同Uuencode的算法很接近，也很简单：它将字符流顺序放入一个 24 位的缓冲区，缺字符的地方补零。然后将缓冲区截断成为 4 个部分，高位在先，每个部分 6 位，用下面的64个字符重新表示：“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/”。如果输入只有一个或两个字节，那么输出将用等号“=”补足。这可以隔断附加的信息造成编码的混乱。它每行一般为76个字符。

    下面我给出Base64的编码和解码的C语言描述：

/*Base64编码*/

void Base64(unsigned char chasc[3],unsigned char chuue[4])

/* 

  chasc：未编码的二进制代码

  chuue：编码过的Base64代码

*/

{

 int i,k=2;

 unsinged char t=NULL;

 for(i=0;i<3;i++)

 {

  *(chuue+i)=*(chasc+i)>>k;

  *(chuue+i)|=t;

  t=*(chasc+i)<<(8-k);

  t>>=2;

  k+=2;

 }

 *(chuue+3)=*(chasc+2)&63;

 

 for(i=0;i<4;i++)

    if((*(chuue+i)>=0)&&(*(chuue+i)<=25)) *(chuue+i)+=65;

    else if((*(chuue+i)>=26)&&(*(chuue+i)<=51)) *(chuue+i)+=71;

    else if((*(chuue+i)>=52)&&(*(chuue+i)<=61)) *(chuue+i)-=4;

    else if(*(chuue+i)==62) *(chuue+i)=43;

    else if(*(chuue+i)==63) *(chuue+i)=47;

 

}

/*Base64解码*/

void unBase64（unsigned char chuue[4]，unsigned char chasc[3]）

/* 

chuue：未解码的Base64代码

chasc：解码过的二进制代码

*/

{int i,k=2;

 unsigned char t=NULL;

 

 for(i=0;i<4;i++)

     if((*(chuue+i)>=65)&&(*(chuue+i)<=90)) *(chuue+i)-=65;

     else if((*(chuue+i)>=97)&&(*(chuue+i)<=122)) *(chuue+i)-=71;

     else if((*(chuue+i)>=48)&&(*(chuue+i)<=57)) *(chuue+i)+=4;

     else if(*(chuue+i)==43) *(chuue+i)=62;

     else if(*(chuue+i)==47) *(chuue+i)=63;

     else if(*(chuue+i)==61) *(chuue+i)=0;

 

 for(i=0;i<3;i++)

 {*(chhex+i)=*(chuue+i)<<k;

  k+=2;

  t=*(chuue+i+1)>>8-k;

  *(chhex+i)|=t;

 }

}

归类于： 数据结构与算法 — 岚焕 @ 9:52 pm 评论(0)
乱码大全(二)

乱码大全(二)

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


 

2. Xxencode

    提到Uuencode不可能不提Xxencode， Xxencode的编码算法和 Uuencode基本相同，但是使用的是不同的字符集。XxEncode编码使用的字符是：

“+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz”与 Uuencode 相比，它的特殊字符更少。很多支持 Uuencode 编解码的工具都同时支持 Xxencode。

    这种编码的特征是：每一行开头用“h”标志。下面是Xxencode的一个例子：

begin 644 mogao.txt

h0EY760+U684qkh90uwjXhuWowwWfcPQB0UbLxxLTCapjNq3jcumkpxH4iwOu

hpxKycuVoNKliNLEu9mwmA16iAH2m9X6k9X2nAXcmAuCdgwbIgO4X1Ec760+U

h60+Ul8esrwXhjDutdBTrmh8XiaVoR5+u9mxhPqRVPmtWNKtoOLJi9atZR+o8

h0EY7FKpVOKloPndhPqRVPo+nBn2iPaJo1Ec760+U8Wce8Wce8Wce8Wce8Wce

h8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce60+U60+U60+U60+U60+U

h1Ec760+U8W0nzQ59jATGtAemkvGqj98vhDXLruCggzr-mxTXj8D8ggCohfmm

hiw5onw6e1Ec760+U8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce

A8Wce8Wce8Wce8Wce

+

end

 

    你可以把它单独存成一个文件：mogao.xxe，然后用Winzip打开，解压即得mogao.txt。

    Xxencode的编码算法和Uuencode基本相同，实现起来则更为简单，在此就不详述了。

    下面给出Xxencode编码和解码的C语言描述：

/*Xxencode编码*/

 void Xxe（unsigned char chasc[3],unsigned char chxxe[4])

/*

chasc：未编码的二进制代码

chxxe：编码过的Xxe代码

*/

{int i；

 static char set[]=

  “+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz”;

 chxxe[0]=chasc[0]>>2;

 chxxe[1]=(chasc[0]<<4)&48|(chasc[1]>>4)&15;

 chxxe[2]=(chasc[1]<<2)&60|(chasc[2]>>6)&3;

 chxxe[3]=chasc[2]&63;

 for(i=0;i<4;i++) chxxe[i]=set[chxxe[i]];                  /*查表*/

}

/*需注意的是，Xxencode文件正文部分中每一行的第一个字母是：从源文件中实际                 读取的字符数的ASCII值取后六位后用set[]查表得到的。*/

/*Xxencode解码*/

unsigned char set(unsigned char ch)                           /*查表函数*/

{if(ch==43) ch=0;

 else if(ch==45) ch=1;

 else if(ch>=48&&ch<=57) ch-=46;

 else if(ch>=65&&ch<=90) ch-=53;

 else if(ch>=97&&ch<=122) ch-=59;

 return ch;

}

 

void unXxe（unsigned char chxxe[4]，unsigned char chasc[3]）

/*

chxxe：未解码的Xxe代码

chasc：解码过的二进制代码

*/

{int k=2 ,i;

 unsigned char t;

 t=NULL;

 *chxxe=set(*chxxe);

 for(i=0;i<3;i++)

 {*(chxxe+i+1)=set(*(chxxe+i+1));

  (chhex+i)=*(chxxe+i)<<k;

  k+=2;

  t=*(chxxe+i+1)>>8-k;

  *(chhex+i)|=t;

 }

}

归类于： 数据结构与算法 — 岚焕 @ 9:50 pm 评论(0)
乱码算法大全(一)Uuencode

乱码算法大全(一)Uuencode

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


 

    相信上过网的朋友们都遇见过“乱码”，也就是在浏览网页或看Email时出现的不能辨认的字符。以前也有许多的文章介绍过“乱码”，不过他们的文章只是讲怎样辨别和怎样用工具解码，并没有详细介绍各种编码的算法的实现，本文将对互联网上最常用的几种编码的编码和解码算法作以详细的阐述。希望对想了解“乱码”算法或想在自己程序中实现这些功能朋友们有一些参考价值。本文的源程序用C语言写成，形式为函数，可直接使用。

Uuencode:

    Uuencode 是将二进制文件以文本文件方式进行编码表示、以利于基于文本传输环境中进行二进制文件的传输/交换的编码方法之一， 在邮件系统/二进制新闻组中使用频率比较高，经常用于 Attach 二进制文件。

    这种编码的特征是：每一行开头用“M”标志。下面是我做的一个测试用的文件mogao.txt，编码为Uuencode：

begin 644 mogao.txt

M”0D)(“`@(*&VPM+”Z\OCMZBT\\BKH;<-”@G7]]7?.FUO9V%OHZRPU]3&N\:Z

MU]6^HZAT96QN970Z+R\R,#(N,3$R+C(P+C$S,CHR,Z.IL\G4L:&C#0H)(“`@

M(“`@Q*JXW\CMO/ZYI-?WRM*CNFAT=’`Z+R]M;V=A;RYB96YT:75N+FYE=`T*

M”0D)16UA:6QT;SIM;V=A;T`S-S$N;F5T#0H)(“`@*BHJ*BHJ*BHJ*BHJ*BHJ

M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ(“`@(“`@(“`@(“`@(“`@

M#0H)(“`@*B”S_<’+O,?2Y,JRP[2VO+*[M/C7WZ.LL_W!R]?CO*/*LL.TMKRR

MN\’TS\(J#0H)(“`@*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ

,*BHJ*BHJ*BHJ*BHJ

`

end

 

    你可以把它单独存成一个文件：mogao.uue，然后用Winzip打开，解压即得mogao.txt。

    Uuencode的算法很简单，编码时它将3个字符顺序放入一个 24 位的缓冲区，缺字符的地方补零，然后将缓冲区截断成为 4 个部分，高位在先，每个部分 6 位，用下面的64个字符重新表示：

“`!”#$%&’()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_”

在文件的开头有“begin xxx 被编码的文件名”，在文件的结尾有“end”，用来标志Uue文件的开始和结束。编码时，每次读取源文件的45个字符，不足45个的用“NULL”补足为3的整数倍（如：23补为24），然后输入目标文件一个ASCII为：“32+实际读取的字符数”的字符作为每一行的开始。读取的字符编码后输入目标文件，再输入一个“换行符”。如果源文件被编码完了，那么输入“`（ASCII为96）”和一个“换行符”表示编码结束。

    解码时它将4个字符分别转换为4个6位字符后，截取有用的后六位放入一个 24 位的缓冲区，即得3个二进制代码。

    下面我给出Uuencode编码和解码的C语言描述：

/*Uuencode编码*/

void Uue(unsigned char chasc[3],unsigned char chuue[4])

/* 

chasc：未编码的二进制代码

chuue：编码过的Uue代码

*/

{int i,k=2;

 unsigned char t=NULL;

 for(i=0;i<3;i++)

 {*(chuue+i)=*(chasc+i)>>k;

  *(chuue+i)|=t;

  if(*(chuue+i)==NULL) *(chuue+i)+=96;

  else *(chuue+i)+=32;

  t=*(chasc+i)<<(8-k);

  t>>=2;

  k+=2;

 }

 *(chuue+3)=*(chasc+2)&63;

 if(*(chuue+3)==NULL) *(chuue+3)+=96;

 else *(chuue+3)+=32;

}

 

/*Uuencode解码*/

void unUue（unsigned char chuue[4]，unsigned char chasc[3]）

/* 

chuue：未解码的Uue代码

chasc：解码过的二进制代码

*/

{int i,k=2;

 unsigned char t=NULL;

 if(*chuue==96) *chuue=NULL;

 else *chuue-=32;

 for(i=0;i<3;i++)

 {*(chasc+i)=*(chuue+i)<<k;

  k+=2;

  if(*(chuue+i+1)==96) *(chuue+i+1)=NULL;

  else *(chuue+i+1)-=32;

  t=*(chuue+i+1)>>8-k;

  *(chasc+i)|=t;

 }

}

归类于： 数据结构与算法 — 岚焕 @ 9:49 pm 评论(1)
乱码算法大全

乱码算法大全

  发表时间：2004-8-10
作者：未知[获得此文档时候没有作者记录，深感抱歉，本文档全为转载]  


乱码算法大全

序

    相信上过网的朋友们都遇见过“乱码”，也就是在浏览网页或看Email时出现的不能辨认的字符。以前也有许多的文章介绍过“乱码”，不过他们的文章只是讲怎样辨别和怎样用工具解码，并没有详细介绍各种编码的算法的实现，本文将对互联网上最常用的几种编码的编码和解码算法作以详细的阐述。希望对想了解“乱码”算法或想在自己程序中实现这些功能朋友们有一些参考价值。本文的源程序用C语言写成，形式为函数，可直接使用。

一. 常用编码
1. Uuencode
    Uuencode 是将二进制文件以文本文件方式进行编码表示、以利于基于文本传输环境中进行二进制文件的传输/交换的编码方法之一， 在邮件系统/二进制新闻组中使用频率比较高，经常用于 Attach 二进制文件。
    这种编码的特征是：每一行开头用“M”标志。下面是我做的一个测试用的文件mogao.txt，编码为Uuencode：
begin 644 mogao.txt
M”0D)(“`@(*&VPM+”Z\OCMZBT\\BKH;<-”@G7]]7?.FUO9V%OHZRPU]3&N\:Z
MU]6^HZAT96QN970Z+R\R,#(N,3$R+C(P+C$S,CHR,Z.IL\G4L:&C#0H)(“`@
M(“`@Q*JXW\CMO/ZYI-?WRM*CNFAT=’`Z+R]M;V=A;RYB96YT:75N+FYE=`T*
M”0D)16UA:6QT;SIM;V=A;T`S-S$N;F5T#0H)(“`@*BHJ*BHJ*BHJ*BHJ*BHJ
M*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ(“`@(“`@(“`@(“`@(“`@
M#0H)(“`@*B”S_<’+O,?2Y,JRP[2VO+*[M/C7WZ.LL_W!R]?CO*/*LL.TMKRR
MN\’TS\(J#0H)(“`@*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ*BHJ
,*BHJ*BHJ*BHJ*BHJ
`
end

    你可以把它单独存成一个文件：mogao.uue，然后用Winzip打开，解压即得mogao.txt。
    Uuencode的算法很简单，编码时它将3个字符顺序放入一个 24 位的缓冲区，缺字符的地方补零，然后将缓冲区截断成为 4 个部分，高位在先，每个部分 6 位，用下面的64个字符重新表示：
“`!”#$%&’()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_”
在文件的开头有“begin xxx 被编码的文件名”，在文件的结尾有“end”，用来标志Uue文件的开始和结束。编码时，每次读取源文件的45个字符，不足45个的用“NULL”补足为3的整数倍（如：23补为24），然后输入目标文件一个ASCII为：“32+实际读取的字符数”的字符作为每一行的开始。读取的字符编码后输入目标文件，再输入一个“换行符”。如果源文件被编码完了，那么输入“`（ASCII为96）”和一个“换行符”表示编码结束。
    解码时它将4个字符分别转换为4个6位字符后，截取有用的后六位放入一个 24 位的缓冲区，即得3个二进制代码。
    下面我给出Uuencode编码和解码的C语言描述：
/*Uuencode编码*/
void Uue(unsigned char chasc[3],unsigned char chuue[4])
/* 
chasc：未编码的二进制代码
chuue：编码过的Uue代码
*/
{int i,k=2;
 unsigned char t=NULL;
 for(i=0;i<3;i++)
 {*(chuue+i)=*(chasc+i)>>k;
  *(chuue+i)|=t;
  if(*(chuue+i)==NULL) *(chuue+i)+=96;
  else *(chuue+i)+=32;
  t=*(chasc+i)<<(8-k);
  t>>=2;
  k+=2;
 }
 *(chuue+3)=*(chasc+2)&63;
 if(*(chuue+3)==NULL) *(chuue+3)+=96;
 else *(chuue+3)+=32;
}

/*Uuencode解码*/
void unUue（unsigned char chuue[4]，unsigned char chasc[3]）
/* 
chuue：未解码的Uue代码
chasc：解码过的二进制代码
*/
{int i,k=2;
 unsigned char t=NULL;
 if(*chuue==96) *chuue=NULL;
 else *chuue-=32;
 for(i=0;i<3;i++)
 {*(chasc+i)=*(chuue+i)<<k;
  k+=2;
  if(*(chuue+i+1)==96) *(chuue+i+1)=NULL;
  else *(chuue+i+1)-=32;
  t=*(chuue+i+1)>>8-k;
  *(chasc+i)|=t;
 }
}

2. Xxencode
    提到Uuencode不可能不提Xxencode， Xxencode的编码算法和 Uuencode基本相同，但是使用的是不同的字符集。XxEncode编码使用的字符是：
“+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz”与 Uuencode 相比，它的特殊字符更少。很多支持 Uuencode 编解码的工具都同时支持 Xxencode。
    这种编码的特征是：每一行开头用“h”标志。下面是Xxencode的一个例子：
begin 644 mogao.txt
h0EY760+U684qkh90uwjXhuWowwWfcPQB0UbLxxLTCapjNq3jcumkpxH4iwOu
hpxKycuVoNKliNLEu9mwmA16iAH2m9X6k9X2nAXcmAuCdgwbIgO4X1Ec760+U
h60+Ul8esrwXhjDutdBTrmh8XiaVoR5+u9mxhPqRVPmtWNKtoOLJi9atZR+o8
h0EY7FKpVOKloPndhPqRVPo+nBn2iPaJo1Ec760+U8Wce8Wce8Wce8Wce8Wce
h8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce60+U60+U60+U60+U60+U
h1Ec760+U8W0nzQ59jATGtAemkvGqj98vhDXLruCggzr-mxTXj8D8ggCohfmm
hiw5onw6e1Ec760+U8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce8Wce
A8Wce8Wce8Wce8Wce
+
end

    你可以把它单独存成一个文件：mogao.xxe，然后用Winzip打开，解压即得mogao.txt。
    Xxencode的编码算法和Uuencode基本相同，实现起来则更为简单，在此就不详述了。
    下面给出Xxencode编码和解码的C语言描述：
/*Xxencode编码*/
 void Xxe（unsigned char chasc[3],unsigned char chxxe[4])
/*
chasc：未编码的二进制代码
chxxe：编码过的Xxe代码
*/
{int i；
 static char set[]=
  “+-0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz”;
 chxxe[0]=chasc[0]>>2;
 chxxe[1]=(chasc[0]<<4)&48|(chasc[1]>>4)&15;
 chxxe[2]=(chasc[1]<<2)&60|(chasc[2]>>6)&3;
 chxxe[3]=chasc[2]&63;
 for(i=0;i<4;i++) chxxe[i]=set[chxxe[i]];   /*查表*/
}
/*需注意的是，Xxencode文件正文部分中每一行的第一个字母是：从源文件中实际                 读取的字符数的ASCII值取后六位后用set[]查表得到的。*/
/*Xxencode解码*/
unsigned char set(unsigned char ch)    /*查表函数*/
{if(ch==43) ch=0;
 else if(ch==45) ch=1;
 else if(ch>=48&&ch<=57) ch-=46;
 else if(ch>=65&&ch<=90) ch-=53;
 else if(ch>=97&&ch<=122) ch-=59;
 return ch;
}

void unXxe（unsigned char chxxe[4]，unsigned char chasc[3]）
/*
chxxe：未解码的Xxe代码
chasc：解码过的二进制代码
*/
{int k=2 ,i;
 unsigned char t;
 t=NULL;
 *chxxe=set(*chxxe);
 for(i=0;i<3;i++)
 {*(chxxe+i+1)=set(*(chxxe+i+1));
  (chhex+i)=*(chxxe+i)<<k;
  k+=2;
  t=*(chxxe+i+1)>>8-k;
  *(chhex+i)|=t;
 }
}

3. Base64
    Base64和下面将要介绍的Quoted-Printable都属于MIME（多部分( multi-part)、多媒体电子邮件和 WWW 超文本的一种编码标准，用于传送诸如图形、声音和传真等非文本数据）。MIME定义在RFC1341中。
    Base64是现今在互联网上应用最多的一种编码，几乎所有的电子邮件软件头把它作为默认的二进制编码，它已经成了现今电子邮件编码的代名词。
    下面是Base64的一个例子，从例子中，您也可以看到Base64与电子邮件的的紧密联系：
Content-Type: text/plain;charset=”cn-gb”
Content-Transfer-Encoding: BASE64

CQkJICAgIKG2wtLC68vjt6i088irobcNCgnX99XfOm1vZ2Fvo6yw19TGu8a619W+o6h0ZWxuZXQ6
Ly8yMDIuMTEyLjIwLjEzMjoyM6Ops8nUsaGjDQoJICAgICAgxKq438jtvP65pNf3ytKjumh0dHA6
Ly9tb2dhby5iZW50aXVuLm5ldA0KCQkJRW1haWx0bzptb2dhb0AzNzEubmV0DQoJICAgKioqKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqICAgICAgICAgICAgICAgDQoJ
ICAgKiCz/cHLvMfS5Mqyw7S2vLK7tPjX36Oss/3By9fjvKPKssO0tryyu8H0z8IqDQoJICAgKioq
KioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioqKioq

    你可以把它单独存成一个文件，可以取名为：mogao.eml，双击可以用OutLook打开（前两行为邮件的原始信息，从第四行开始为编码内容）。
    Base64的算法同Uuencode的算法很接近，也很简单：它将字符流顺序放入一个 24 位的缓冲区，缺字符的地方补零。然后将缓冲区截断成为 4 个部分，高位在先，每个部分 6 位，用下面的64个字符重新表示：“ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/”。如果输入只有一个或两个字节，那么输出将用等号“=”补足。这可以隔断附加的信息造成编码的混乱。它每行一般为76个字符。
    下面我给出Base64的编码和解码的C语言描述：
/*Base64编码*/
void Base64(unsigned char chasc[3],unsigned char chuue[4])
/* 
  chasc：未编码的二进制代码
  chuue：编码过的Base64代码
*/
{
 int i,k=2;
 unsinged char t=NULL;
 for(i=0;i<3;i++)
 {
  *(chuue+i)=*(chasc+i)>>k;
  *(chuue+i)|=t;
  t=*(chasc+i)<<(8-k);
  t>>=2;
  k+=2;
 }
 *(chuue+3)=*(chasc+2)&63;

 for(i=0;i<4;i++)
    if((*(chuue+i)>=0)&&(*(chuue+i)<=25)) *(chuue+i)+=65;
    else if((*(chuue+i)>=26)&&(*(chuue+i)<=51)) *(chuue+i)+=71;
    else if((*(chuue+i)>=52)&&(*(chuue+i)<=61)) *(chuue+i)-=4;
    else if(*(chuue+i)==62) *(chuue+i)=43;
    else if(*(chuue+i)==63) *(chuue+i)=47;

}
/*Base64解码*/
void unBase64（unsigned char chuue[4]，unsigned char chasc[3]）
/* 
chuue：未解码的Base64代码
chasc：解码过的二进制代码
*/
{int i,k=2;
 unsigned char t=NULL;
 
 for(i=0;i<4;i++)
     if((*(chuue+i)>=65)&&(*(chuue+i)<=90)) *(chuue+i)-=65;
     else if((*(chuue+i)>=97)&&(*(chuue+i)<=122)) *(chuue+i)-=71;
     else if((*(chuue+i)>=48)&&(*(chuue+i)<=57)) *(chuue+i)+=4;
     else if(*(chuue+i)==43) *(chuue+i)=62;
     else if(*(chuue+i)==47) *(chuue+i)=63;
     else if(*(chuue+i)==61) *(chuue+i)=0;

 for(i=0;i<3;i++)
 {*(chhex+i)=*(chuue+i)<<k;
  k+=2;
  t=*(chuue+i+1)>>8-k;
  *(chhex+i)|=t;
 }
}

4. Quoted-Printable
    Quoted-Printable简称QP， 一般用在Email系统中。它通常用于少量文本方式的8位字符的编码，例如Foxmail就用它做对主题和信体的编码。这种编码的应该是很好辨认的：它有大量的“=”。下面是它的一个例子：

Mime-Version: 1.0
Content-Transfer-Encoding: quoted-printable

       =A1=B6=C2=D2=C2=EB=CB=E3=B7=A8=B4=F3=C8=AB=A1=B7
 =D7=F7=D5=DF:mogao=A3=AC=B0=D7=D4=C6=BB=C6=BA=D7=D5=BE=A3=A8telnet://202.112.20.132:23=A3=A9=B3=C9=D4=B1=A1=A3
       =C4=AA=B8=DF=C8=ED=BC=FE=B9=A4=D7=F7=CA=D2=A3=BAhttp://mogao.bentiun.net
   Emailto:mogao@371.net
    *********************************************              
    * =B3=FD=C1=CB=BC=C7=D2=E4=CA=B2=C3=B4=B6=BC=B2=BB=B4=F8=D7=DF=A3=AC=B3=FD=C1=CB=D7=E3=BC=A3=CA=B2=C3=B4=B6=BC=B2=BB=C1=F4=CF=C2*
    *********************************************

    你可以把它单独存成一个文件，取名为：mogao.eml，双击可以用OutLook打开（前两行为邮件的原始信息，从第四行开始为编码内容）。
    QP的算法可以说是最简单的也可以说是编码效率最低的（它的编码率是1:3），它是专门为了处理8位字符制定的。它的算法是：读一个字符，如果ASCII码大于127，即字符的第8位是1的话，进行编码，否则忽略（有时也对7位字符编码）。编码很简单，看下面的C语言描述即可：
/*QP编码*/
void qp(unsigned char sour,unsigned char first,unsigned char second)
/* 
  sour:要编码的字符
  first:编码后的第一个字符
   second:编码后的第二个字符
  first和second为返回值
*/
{
 if(sour>127)  
 {first=sour>>4;
  second=sour&15;
  if(first>9) first+=55;
  else first+=48;
  if(second>9) second+=55;
  else second+=48;
  printf(“%c%c%c”,’=',first,second);
 }
}

/*QP解码*/
void uqp(unsigned char sour,unsigned char first,unsigned char second)
/*
  sour:解码后的字符
  first:QP码的第一个字符
   second:QP码的第二个字符
  sour为返回值
*/
{
 if(first>=65) first-=55;
 else first-=48;
 if(second>=65) second-=55;
 else second-=48;
 sour=NULL;
 sour=first<<4;
 sour|=second;
}

    现在大家知道为什么QP的编码率那么低了吧！关于QP的详细说明和准确定义可以参阅RFC2045。

二.汉字编码
1. GB码和Big5码
    GB码是中国大陆、新加坡等国家和地区使用的一种汉字编码方法。Big5码是中国台湾省用的一种汉字编码方法。它们的编码方法是完全不同的两种方法，它们之间的转换只能通过“查表法”来进行。所以说转换的方法很简单，困难的是“表”的生成。很多文章对此都做过介绍，我在此就不详述了。在我的主页上有我写的“汉字转码通V1.0”的源程序，其中有这两个“表”，可以直接使用。

2. HZ码
    HZ码是为了使只能传送7bit信息的邮件服务器或网关能传送8bit信息而定义的编码，也是中文常用编码的一种。它和上面介绍的Quoted-Printable码都只能对文本进行编码，即编码时忽略控制字符。
    这种编码的也是很好辨认的：有许多“~{”和“~}”，而且总是成对出现。下面是HZ码的一个例子：
       ~{!6BRBkKc7(4sH+!7~}
 ~{WwU_~}:mogao~{#,0WTF;F:WU>#(~}telnet://202.112.20.132:23~{#)3IT1!#~}
       ~{D*8_Hm<~9$WwJR#:~}http://mogao.bentiun.net
   Emailto:mogao@371.net
    *********************************************              
    * ~{3}AK<GRdJ2C46<2;4xW_#,3}AKWc<#J2C46<2;AtOB~}*
    *********************************************

    您可以打开“南极星”看这段文字。
    它的算法更简单：读一个字符，如果是8位字符，就把它的最高位清零。把连续的8位字符清零后的输出用“~{”和“~}”括起来。解码时：把是用“~{”和“~}”括起来的部分每个字符的第8位置“1”即可。

    上面介绍的三种编码之间的转换是经常遇见的，我写的“汉字转码通V1.0”可以方便的在这三种之间转换，我把它的源程序公开，方便广大网友的学习。

三.其他常用编码
1.  Unicode
    Unicode应用中最典型的例子是：IE4以上版本对HTML的编码。它可以说是未来Windows下唯一的字符集。但它还很不完善，而且Win95和Win98对它的支持还很有限，甚至它还没有一套完整的标准。不过，微软最新推出的Office2000和马上就要推出的Windows2000将全面支持Unicode。Unicode取代其他编码将会是必然的趋势。不过，在近一两年Unicode并不会占主导地位，就是在占主导地位后，因为操作系统的差异，其他编码也不会立即消亡。它的中文资料可以在Office2000和Windows2000所带的文档中找到，它的官方网站是：http://www.unicode.org/。

2. Binhex
    BinHex 编码是 Macintosh 计算机（也就是俗称的“苹果电脑”）上用可打印字符表示/传输二进制文件的一种编码方法。它的主要用途是在电子邮件程序中Attach二进制文件。大部分的电子邮件程序不支持这种格式（Eudora支持），但用WINZIP可以进行解码。它的资料请查阅Macintosh计算机带的相关文档。


三.总结
    由于篇幅所限，除了本文介绍的这几种常用编码外，还是有很多种编码的。如各种加密算法产生的“乱码”（我将在另外一篇文章中详细介绍）。本文中提到的所有文档和源程序在我的主页中均可下载，我的主页地址是：http://mogao.bentium.net。如果您对本文有什么意见请来信商榷，我的E-mail地址是：mogao@371.net。

注：我在本文中使用的例子“mogao.txt”的内容是：
       《乱码算法大全》
 作者:mogao，白云黄鹤站（telnet://202.112.20.132:23）成员。
       莫高软件工作室：http://mogao.bentiun.net
   Emailto:mogao@371.net
    *********************************************              
    * 除了记忆什么都不带走，除了足迹什么都不留下*
    *********************************************

归类于： 数据结构与算法 — 岚焕 @ 9:48 pm 评论(0)