程序员面试题整理笔记

1、

进程和线程的主要差别在于它们是不同的操作系统资源管理方式。

进程有独立的地址空间，一个进程崩溃后，在保护模式下不会对其它进程产生影响，而线程只是一个进程中的不同执行路径。

线程有自己的堆栈和局部变量，但线程之间没有单独的地址空间，一个线程死掉就等于整个进程死掉，所以多进程的程序要比多线程的程序健壮，但在进程切换时，耗费资源较大，效率要差一些。

但对于一些要求同时进行并且又要共享某些变量的并发操作，只能用线程，不能用进程。

一个线程包含以下内容：

一个指向当前被执行指令的指令指针；

一个栈；

一个寄存器值的集合，定义了一部分描述正在执行线程的处理器状态的值； 一个私有的数据区。

竞态条件

竞态条件指的是一种特殊的情况，在这种情况下各个执行单元以一种没有逻辑的顺序执行动作，从而导致意想不到的结果。

举一个例子，线程T 修改资源R 后，释放了它对R 的写访问权，之后又重新夺回R 的读访问权再使用它，并以为它的状态仍然保持在它释放它之后的状态。但是在写访问权释放后到重新夺回读访问权的这段时间间隔中，可能另一个线程已经修改了R 的状态。

另一个经典的竞态条件的例子就是生产者/消费者模型。生产者通常使用同一个物理内存空间保存被生产的信息。一般说来，我们不会忘记在生产者与消费者的并发访问之间保护这个空间。容易被我们忘记的是生产者必须确保在生产新信息前，旧的信息已被消费者所读取。如果我们没有采取相应的预防措施，我们将面临生产的信息从未被消费的危险。 如果静态条件没有被妥善的管理，将导致安全系统的漏洞。同一个应用程序的另一个实例很可能会引发一系列开发者所预计不到的事件。一般来说，必须对那种用于确认身份鉴别结果的布尔量的写访问做最完善的保护。如果没有这么做，那么在它的状态被身份鉴别机制设置后，到它被读取以保护对资源的访问的这段时间内，很有可能已经被修改了。已知的安全漏洞很多都归咎于对静态条件不恰当的管理。其中之一甚至影响了Unix 操作系统的内核。

死锁指的是由于两个或多个执行单元之间相互等待对方结束而引起阻塞的情况。例如：

一个线程T1获得了对资源R1的访问权。

一个线程T2获得了对资源R2的访问权。

T1请求对R2的访问权但是由于此权力被T2所占而不得不等待。

T2请求对R1的访问权但是由于此权力被T1所占而不得不等待。

T1和T2将永远维持等待状态，此时我们陷入了死锁的处境！

针对此问题主要有三种解决方案：

1）在同一时刻不允许一个线程访问多个资源。

2）为资源访问权的获取定义一个关系顺序。换句话说，当一个线程已经获得了R1的访问

权后，将无法获得R2的访问权。当然，访问权的释放必须遵循相反的顺序。

3）为所有访问资源的请求系统地定义一个最大等待时间（超时时间），并妥善处理请求失败的情况。几乎所有的.NET 的同步机制都提供了这个功能。

前两种技术效率更高但是也更加难于实现。事实上，它们都需要很强的约束，而这点随着应用程序的演变将越来越难以维护。尽管如此，使用这些技术不会存在失败的情况。大的项目通常使用第三种方法。事实上，如果项目很大，一般来说它会使用大量的资源。在这种情况下，资源之间发生冲突的概率很低，也就意味着失败的情况会比较罕见。我们认为这是一种乐观的方法。秉着同样的精神，我们在19.5节描述了一种乐观的数据库访问模型。

2、

A ）malloc 与free 是C++/C语言的标准库函数，new/delete是C++的运算符。它们都可用于申请动态内存和释放内存。

B ）对于非内部数据类型的对象而言，光用malloc/free无法满足动态对象的要求。对象在创建的同时要自动执行构造函数，对象在消亡之前要自动执行析构函数。由于malloc/free是库函数而不是运算符，不在编译器控制权限之内，不能够把执行构造函数和析构函数的任务强加于malloc/free。

C ）因此C++语言需要一个能完成动态内存分配和初始化工作的运算符new ，以一个能完成清理与释放内存工作的运算符delete 。注意new/delete不是库函数。

D ）C++程序经常要调用C 函数，而C 程序只能用malloc/free管理动态内存 new 是个操作符, 和什么"+","-","="...有一样的地位. malloc 是个分配内存的函数, 供你调用的.

new 是保留字, 不需要头文件支持. malloc 需要头文件库函数支持. new 建立的是一个对象, malloc 分配的是一块内存.

free()到底释放了什么简而言之：

这个问题比较简单，其实我是想和第二大部分的题目相呼应而已！哈哈！free()释放的是指针指向的内存！注意！释放的是内存，不是指针！这点非常非常重要！指针是一个变量，只有程序结束时才被销毁。释放了内存空间后，原来指向这块空间的指针还是存在！只不过现在指针指向的内容的垃圾，是未定义的，所以说是垃圾。因此，前面我已经说过了，释放内存后把指针指向NULL ，防止指针在后面不小心又被解引用了。非常重要啊这一点

址空间

在进行C/C++编程开发时，经常会遇到malloc/free 与 new/delete 这两对操作，主要功能就是可以在程序运行过程中动态的申请、释放内存，从而达到对内存的操作。但是这两对操作是有区别的，不能交叉搭配使用：即不能free 掉new 来的内存，也不能delete 掉malloc 来的内存空间。虽然有时候可以delete 掉malloc 来的内存，或者free 掉new 来的内存，但是通常情况下会给程序带来不可预知的错误，相信这不是编程人员所希望看到的。要养成一

个良好的习惯就是严格的配对使用：只用free 来释放malloc 的内存空间、只用delete 来释放new 来的内存空间。

这两对操作的区别：

1、malloc/free是C/C++中的方法（函数），new/delete是C++中的操作符。

2、malloc 申请的是heap 区的内存空间，而new 则是申请的free store 区的内存空间。

3、使用free 之前要判断，使其free 的指针是！NULL 的，使用delete 则无须判断。

4、free 掉的内存是该指针指向的一段内存空间，里面应该是空的。而delete 掉的内存是里面确实存有数据或者对象的。

5、一下举例说明其区别：

malloc 和free(及其变体) 会产生问题的原因在于它们太简单：他们不知道构造函数和析构函数。

假设用两种方法给一个包含10个string 对象的数组分配空间，一个用malloc ，另一个用new ：

string *stringarray1 =

static_cast(malloc(10 * sizeof(string)));

string *stringarray2 = new string[10];

其结果是，stringarray1确实指向的是可以容纳10个string 对象的足够空间，但内存里并没有创建这些对象。而且，如果你不从这种晦涩的语法怪圈里跳出来的话，你没有办法来初始化数组里的对象。换句话说，stringarray1其实一点用也没有。相反，stringarray2指向的是一个包含10个完全构造好的string 对象的数组, 每个对象可以在任何读取string 的操作里安全使用。

假设你想了个怪招对stringarray1数组里的对象进行了初始化，那么在你后面的程序里你一定会这么做：

free(stringarray1);

delete [] stringarray2;// 参见条款5：这里为什么要加上个"[]"

调用free 将会释放stringarray1指向的内存，但内存里的string 对象不会调用析构函数。如果string 对象象一般情况那样，自己已经分配了内存，那这些内存将会全部丢失。相反，当对stringarray2调用delete 时，数组里的每个对象都会在内存释放前调用析构函数。

既然new 和delete 可以这么有效地与构造函数和析构函数交互，选用它们是显然的。 把new 和delete 与malloc 和free 混在一起用也是个坏想法。对一个用new 获取来的指针调用free ，或者对一个用malloc 获取来的指针调用delete ，其后果是不可预测的。大家都知道“不可预测”的意思：它可能在开发阶段工作良好，在测试阶段工作良好，但也可能会最后在你最重要的客户的脸上爆炸。

new/delete和malloc/free的不兼容性常常会导致一些严重的复杂性问题。举个例子，里通常有个strdup 函数，它得到一个char*字符串然后返回其拷贝：

char * strdup(const char *ps); // 返回ps 所指的拷贝

在有些地方，c 和c++用的是同一个strdup 版本，所以函数内部是用malloc 分配内存。这样的话，一些不知情的c++程序员会在调用strdup 后忽视了必须对strdup 返回的指针进行free 操作。为了防止这一情况，有些地方会专门为c++重写strdup ，并在函数内部调用了new ，这就要求其调用者记得最后用delete 。你可以想象，这会导致多么严重的移植性问题，因为代码中strdup 以不同的形式在不同的地方之间颠来倒去。

c++程序员和c 程序员一样对代码重用十分感兴趣。大家都知道，有大量基于malloc 和free 写成的代码构成的c 库都非常值得重用。在利用这些库时，最好是你不用负责去free 掉由库自己malloc 的内存，并且/或者，你不用去malloc 库自己会free 掉的内存，这样就太

好了。其实，在c++程序里使用malloc 和free 没有错，只要保证用malloc 得到的指针用free ，或者用new 得到的指针最后用delete 来操作就可以了。千万别马虎地把new 和free 或malloc 和delete 混起来用，那只会自找麻烦。

既然malloc 和free 对构造函数和析构函数一无所知，把malloc/free和new/delete混起来用又像嘈杂拥挤的晚会那样难以控制，那么，你最好就什么时候都一心一意地使用new 和delete 吧

3、栈空间和堆空间

一个由C/C++编译的程序占用的内存分为以下几个部分：

1、栈区（stack ）操作方式类似于数据结构的栈。

2、堆区（heap ）：一般是由程序员分配释放，若程序员不释放的话，程序结束时可能由OS 回收，值得注意的是他与数据结构的堆是两回事，分配方式倒是类似于数据结构的链表。

3、全局区（static ）静态变量的存储是放一块的，初始化的全局变量和静态变量放一块区域，没有初始化的在相邻的另一块区域，程序结束后由系统释放。

4、文字常量区：常量字符串就是放在这里，程序结束后由系统释放。

5、程序代码区：存放函数体的二进制代码。

堆和栈的区别：

一、由以上综述就可以得知，他们程序的内存分配方式不同。

二、申请和响应不同：

1、申请方式：stack 由系统自动分配，heap 需要程序员自己申请，C 中用函数malloc 分配空间，用free 释放，C++用new 分配，用delete 释放。

2、申请后系统的响应：

栈：只要栈的剩余空间大于所申请的空间，体统将为程序提供内存，否则将报异常提示栈溢出。

堆：首先应该知道操作系统有一个记录内存地址的链表，当系统收到程序的申请时，会遍历该链表，寻找第一个空间大于所申请的空间的堆结点，然后将该结点从空闲结点链表中删除，并将该结点的空间分配给程序。另外，对于大多数系统，会在这块内存空间中的首地址处记录本次分配的大小，这样代码中的delete 或free 语句就能够正确的释放本内存空间。另外，由于找到的堆结点的大小不一定正好等于申请的大小，系统会将多余的那部分重新放入空闲链表中。

三、 申请的大小限制不同：

栈：在windows 下，栈是向低地址扩展的数据结构，是一块连续的内存区域，栈顶的地址和栈的最大容量是系统预先规定好的，能从栈获得的空间较小。

堆：堆是向高地址扩展的数据结构，是不连续的内存区域，这是由于系统是由链表在存储空闲内存地址，自然堆就是不连续的内存区域，且链表的遍历也是从低地址向高地址遍历的，堆得大小受限于计算机系统的有效虚拟内存空间，由此空间，堆获得的空间比较灵活，也比较大。

四、申请的效率不同：

栈：栈由系统自动分配，速度快，但是程序员无法控制。

堆：堆是有程序员自己分配，速度较慢，容易产生碎片，不过用起来方便。

五、堆和栈的存储内容不同：

栈：在函数调用时，第一个进栈的是主函数中函数调用后的下一条指令的地址，然后是函数的各个参数，在大多数的C 编译器中，参数是从右往左入栈的，当本次函数调用结束后，局部变量先出栈，然后是参数，最后栈顶指针指向最开始存的地址，也就是主函数中的下一条指令。

堆：一般是在堆得头部用一个字节存放堆得大小，具体内容由程序员安排。

4、数据库索引的作用和优点缺点

为什么要创建索引呢？这是因为，创建索引可以大大提高系统的性能。

第一，通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。

第二，可以大大加快 数据的检索速度，这也是创建索引的最主要的原因。

第三，可以加速表和表之间的连接，特别是在实现数据的参考完整性方面特别有意义。 第四，在使用分组和排序 子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。

第五，通过使用索引，可以在查询的过程中，使用优化隐藏器，提高系统的性能。

也许会有人要问：增加索引有如此多的优点，为什么不对表中的每一个列创建一个索引呢？这种想法固然有其合理性，然而也有其片面性。虽然，索引有许多优点， 但是，为表中的每一个列都增加索引，是非常不明智的。这是因为，增加索引也有许多不利的一个方面。

第一，创建索引和维护索引要耗费时间，这种时间随着数据 量的增加而增加。

第二，索引需要占物理空间，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。

第三，当对表中的数据进行增加、删除和修改的时候，索引也要动态的维护，这样就降低了数据的维护速度。

索引是建立在数据库表中的某些列的上面。因此，在创建索引的时候，应该仔细考虑在哪些列上可以创建索引，在哪些列上不能创建索引。一般来说，应该在这些列 上创建索引，例如：

在经常需要搜索的列上，可以加快搜索的速度；

在作为主键的列上，强制该列的唯一性和组织表中数据的排列结构；

在经常用在连接的列上，这 些列主要是一些外键，可以加快连接的速度；

在经常需要根据范围进行搜索的列上创建索引，因为索引已经排序，其指定的范围是连续的；

在经常需要排序的列上创 建索引，因为索引已经排序，这样查询可以利用索引的排序，加快排序查询时间；

在经常使用在WHERE 子句中的列上面创建索引，加快条件的判断速度。

同样，对于有些列不应该创建索引。一般来说，不应该创建索引的的这些列具有下列特点：

第一，对于那些在查询中很少使用或者参考的列不应该创建索引。这是因 为，既然这

些列很少使用到，因此有索引或者无索引，并不能提高查询速度。相反，由于增加了索引，反而降低了系统的维护速度和增大了空间需求。

第二，对于那 些只有很少数据值的列也不应该增加索引。这是因为，由于这些列的取值很少，例如人事表的性别列，在查询的结果中，结果集的数据行占了表中数据行的很大比 例，即需要在表中搜索的数据行的比例很大。增加索引，并不能明显加快检索速度。

第三，对于那些定义为text, image和bit 数据类型的列不应该增加索引。这是因为，这些列的数据量要么相当大，要么取值很少。

第四，当修改性能远远大于检索性能时，不应该创建索 引。这是因为，修改性能和检索性能是互相矛盾的。当增加索引时，会提高检索性能，但是会降低修改性能。当减少索引时，会提高修改性能，降低检索性能。因 此，当修改性能远远大于检索性能时，不应该创建索引。

创建索引的方法和索引的特征

创建索引的方法

创建索引有多种方法，这些方法包括直接创建索引的方法和间接创建索引的方法。直接创建索引，例如使用CREATE INDEX 语句或者使用创建索引向导，间接创建索引，例如在表中定义主键约束或者唯一性键约束时，同时也创建了索引。虽然，这两种方法都可以创建索引，但 是，它们创建索引的具体内容是有区别的。

使用CREATE INDEX 语句或者使用创建索引向导来创建索引，这是最基本的索引创建方式，并且这种方法最具有柔性，可以定制创建出符合自己需要的索引。在使用这种方式 创建索引时，可以使用许多选项，例如指定数据页的充满度、进行排序、整理统计信息等，这样可以优化索引。使用这种方法，可以指定索引的类型、唯一性和复合 性，也就是说，既可以创建聚簇索引，也可以创建非聚簇索引，既可以在一个列上创建索引，也可以在两个或者两个以上的列上创建索引。

通过定义主键约束或者唯一性键约束，也可以间接创建索引。主键约束是一种保持数据完整性的逻辑，它限制表中的记录有相同的主键记录。在创建主键约束时，系 统自动创建了一个唯一性的聚簇索引。虽然，在逻辑上，主键约束是一种重要的结构，但是，在物理结构上，与主键约束相对应的结构是唯一性的聚簇索引。换句话 说，在物理实现上，不存在主键约束，而只存在唯一性的聚簇索引。同样，在创建唯一性键约束时，也同时创建了索引，这种索引则是唯一性的非聚簇索引。因此， 当使用约束创建索引时，索引的类型和特征基本上都已经确定了，由用户定制的余地比较小。

当在表上定义主键或者唯一性键约束时，如果表中已经有了使用CREATE INDEX 语句创建的标准索引时，那么主键约束或者唯一性键约束创建的索引覆盖以前创建的标准索引。也就是说，主键约束或者唯一性键约束创建的索引的优先 级高于使用CREATE INDEX语句创建的索引。

索引的特征

索引有两个特征，即唯一性索引和复合索引。

唯一性索引保证在索引列中的全部数据是唯一的，不会包含冗余数据。如果表中已经有一个主键约束或者唯一性键约束，那么当创建表或者修改表时，SQL Server自动创建一个唯一性索引。然而，如果必须保证唯一性，那么应该创建主键约束或者唯一性键约束，而不是创建一个唯一性索引。当创建唯一性索引 时，应该认真考虑这些规则：当在表中创建主键

约束或者唯一性键约束时，SQL Server自动创建一个唯一性索引；如果表中已经包含有数据，那么当创建索引时，SQL Server检查表中已有数据的冗余性；每当使用插入语句插入数据或者使用修改语句修改数据时，SQL Server检查数据的冗余性：如果有冗余值，那么SQL Server取消该语句的执行，并且返回一个错误消息；确保表中的每一行数据都有一个唯一值，这样可以确保每一个实体都可以唯一确认；只能在可以保证实体 完整性的列上创建唯一性索引，例如，不能在人事表中的姓名列上创建唯一性索引，因为人们可以有相同的姓名。

复合索引就是一个索引创建在两个列或者多个列上。在搜索时，当两个或者多个列作为一个关键值时，最好在这些列上创建复合索引。当创建复合索引时，应该考虑 这些规则：最多可以把16个列合并成一个单独的复合索引，构成复合索引的列的总长度不能超过900字节，也就是说复合列的长度不能太长；在复合索引中，所 有的列必须来自同一个表中，不能跨表建立复合列；在复合索引中，列的排列顺序是非常重要的，因此要认真排列列的顺序，原则上，应该首先定义最唯一的列，例 如在（COL1，COL2）上的索引与在（COL2，COL1）上的索引是不相同的，因为两个索引的列的顺序不同；为了使查询优化器使用复合索引，查询语 句中的WHERE 子句必须参考复合索引中第一个列；当表中有多个关键列时，复合索引是非常有用的；使用复合索引可以提高查询性能，减少在一个表中所创建的 索引数量。

5、IP 地址分类

最初设计互联网络时，为了便于寻址以及层次化构造网络，每个IP 地址包括两个标识码（ID ），即网络ID 和主机ID 。同一个物理网络上的所有主机都使用同一个网络ID ，网络上的一个主机（包括网络上工作站，服务器和路由器等）有一个主机ID 与其对应。Internet 委员会定义了5种IP 地址类型以适合不同容量的网络，即A 类~E类。

其中A 、B 、C3类（如下表格）由InternetNIC 在全球范围内统一分配，D 、E 类为特殊地址。

A 类IP 地址

一个A 类IP 地址是指， 在IP 地址的四段号码中，第一段号码为网络号码，剩下的三段号码为本地计算机的号码。如果用二进制表示IP 地址的话，A 类IP 地址就由1字节的网络地址和3字节主机地址组成，网络地址的最高位必须是“0”。A 类IP 地址中网络的标识长度为8位，主机标识的长度为24位，A 类网络地址数量较少，有126个网络，每个网络可以容纳主机数达1600多万台。

A 类IP 地址 地址范围1.0.0.0到126.255.255.255[1] （二进制表示为：00000001

[**************]0 00000000 - 01111110 11111111 11111111 11111111）。最后一个是广播地址。

A 类IP 地址的子网掩码为255.0.0.0，每个网络支持的最大主机数为256的3次方-2=16777214台。

[2]

B 类IP 地址

一个B 类IP 地址是指，在IP 地址的四段号码中，前两段号码为网络号码。如果用二进制表示IP 地址的话，B 类IP 地址就由2字节的网络地址和2字节主机地址组成，网络地址的最高位必须是“10”。B 类IP 地址中网络的标识长度为16位，主机标识的长度为16位，B 类网络地址适用于中等规模的网络，有16384个网络，每个网络所能容纳的计算机数为6万多台。

B 类IP 地址地址范围128.0.0.0-191.255.255.255[3] （二进制表示为：10000000 00000000 00000000 00000000----10111111 11111111 11111111 11111111）。 最后一个是广播地址。 B 类IP 地址的子网掩码为255.255.0.0，每个网络支持的最大主机数为256的2次方-2=65534台

C 类IP 地址

一个C 类IP 地址是指，在IP 地址的四段号码中，前三段号码为网络号码，剩下的一段号码为本地计算机的号码。如果用二进制表示IP 地址的话，C 类IP 地址就由3字节的网络地址和1字节主机地址组成，网络地址的最高位必须是“110”。C 类IP 地址中网络的标识长度为24位，主机标识的长度为8位，C 类网络地址数量较多，有209万余个网络。适用于小规模的局域网络，每个网络最多只能包含254台计算机。

C 类IP 地址范围192.0.0.0-223.255.255.255[3] （二进制表示为: 11000000 00000000 00000000 00000000 - 11011111 11111111 11111111 11111111）。

C 类IP 地址的子网掩码为255.255.255.0，每个网络支持的最大主机数为256-2=254台 D 类IP 地址

D 类IP 地址在历史上被叫做多播地址(multicast address)，即组播地址。在以太网中，多播地址命名了一组应该在这个网络中应用接收到一个分组的站点。多播地址的最高位必须是“1110”，范围从224.0.0.0到239.255.255.255。

特殊的网址

每一个字节都为0的地址（“0.0.0.0”）对应于当前主机；

IP 地址中的每一个字节都为1的IP 地址（“255．255．255．255”）是当前子网的广播地址； IP 地址中凡是以“11110”开头的E 类IP 地址都保留用于将来和实验使用。

IP 地址中不能以十进制“127”作为开头，该类地址中数字127．0．0．1到127．255．255．255用于回路测试，如：127.0.0.1可以代表本机IP 地址，用“http://127.0.0.1”就可以测试本机中配置的Web 服务器。

网络ID 的第一个8位组也不能全置为“0”，全“0”表示本地网络。

6、HTTP 协议详解

引言

HTTP 是一个属于应用层的面向对象的协议，由于其简捷、快速的方式，适用于分布式超媒体信息系统。它于1990年提出，经过几年的使用与发展，得到不断地完善和扩展。目前在WWW 中使用的是HTTP/1.0的第六版，HTTP/1.1的规范化工作正在进行之中，而且HTTP -NG(Next Generation of HTTP)的建议已经提出。

HTTP 协议的主要特点可概括如下：

1. 支持客户/服务器模式。

2. 简单快速：客户向服务器请求服务时，只需传送请求方法和路径。请求方法常用的有GET 、HEAD 、POST 。每种方法规定了客户与服务器联系的类型不同。由于HTTP 协议简单，使得HTTP 服务器的程序规模小，因而通信速度很快。

3. 灵活：HTTP 允许传输任意类型的数据对象。正在传输的类型由Content -Type 加以标记。

4. 无连接：无连接的含义是限制每次连接只处理一个请求。服务器处理完客户的请求，并收到客户的应答后，即断开连接。采用这种方式可以节省传输时间。

5. 无状态：HTTP 协议是无状态协议。无状态是指协议对于事务处理没有记忆能力。缺少状态意味着如果后续处理需要前面的信息，则它必须重传，这样可能导致每次连接传送的数据量增大。另一方面，在服务器不需要先前信息时它的应答就较快。

一、HTTP 协议详解之URL 篇

http （超文本传输协议）是一个基于请求与响应模式的、无状态的、应用层的协议，常基于TCP 的连接方式，HTTP1.1版本中给出一种持续连接的机制，绝大多数的Web 开发，都是构建在HTTP 协议之上的Web 应用。

HTTP URL (URL是一种特殊类型的URI ，包含了用于查找某个资源的足够的信息) 的格式如下： http://host[":"port][abs_path]

http 表示要通过HTTP 协议来定位网络资源；host 表示合法的Internet 主机域名或者IP 地址；port 指定一个端口号，为空则使用缺省端口80；abs_path指定请求资源的URI ；如果URL 中没有给出abs_path，那么当它作为请求URI 时，必须以“/”的形式给出，通常这个工作浏览器自动帮我们完成。

eg:

1、输入：www.guet.edu.cn

浏览器自动转换成：http://www.guet.edu.cn/

2、http:192.168.0.116:8080/index.jsp

二、HTTP 协议详解之请求篇

http 请求由三部分组成，分别是：请求行、消息报头、请求正文

1、请求行以一个方法符号开头，以空格分开，后面跟着请求的URI 和协议的版本，格式如下：Method Request-URI HTTP-Version CRLF

其中 Method 表示请求方法；Request -URI 是一个统一资源标识符；HTTP -Version 表示请求的HTTP 协议版本；CRLF 表示回车和换行（除了作为结尾的CRLF 外，不允许出现单独的CR 或LF 字符）。

请求方法（所有方法全为大写）有多种，各个方法的解释如下：

GET 请求获取Request -URI 所标识的资源

POST 在Request -URI 所标识的资源后附加新的数据

HEAD 请求获取由Request -URI 所标识的资源的响应消息报头

PUT 请求服务器存储一个资源，并用Request -URI 作为其标识

DELETE 请求服务器删除Request -URI 所标识的资源

TRACE 请求服务器回送收到的请求信息，主要用于测试或诊断

CONNECT 保留将来使用

OPTIONS 请求查询服务器的性能，或者查询与资源相关的选项和需求

应用举例：

GET 方法：在浏览器的地址栏中输入网址的方式访问网页时，浏览器采用GET 方法向服务器获取资源，eg:GET /form.html HTTP/1.1 (CRLF)

POST 方法要求被请求服务器接受附在请求后面的数据，常用于提交表单。

eg ：POST /reg.jsp HTTP/ (CRLF)

Accept:image/gif,image/x-xbit,... (CRLF)

...

HOST:www.guet.edu.cn (CRLF)

Content -Length:22 (CRLF)

Connection:Keep-Alive (CRLF)

Cache -Control:no-cache (CRLF)

(CRLF) //该CRLF 表示消息报头已经结束，在此之前为消息报头

user=jeffrey&pwd=1234 //此行以下为提交的数据

HEAD 方法与GET 方法几乎是一样的，对于HEAD 请求的回应部分来说，它的HTTP 头部中包含的信息与通过GET 请求所得到的信息是相同的。利用这个方法，不必传输整个资源内容，就可以得到Request -URI 所标识的资源的信息。该方法常用于测试超链接的有效性，是否可以访问，以及最近是否更新。

2、请求报头后述

3、请求正文(略)

三、HTTP 协议详解之响应篇

在接收和解释请求消息后，服务器返回一个HTTP 响应消息。

HTTP 响应也是由三个部分组成，分别是：状态行、消息报头、响应正文

1、状态行格式如下：

HTTP -Version Status-Code Reason-Phrase CRLF

其中，HTTP -Version 表示服务器HTTP 协议的版本；Status -Code 表示服务器发回的响应状态代码；Reason -Phrase 表示状态代码的文本描述。

状态代码有三位数字组成，第一个数字定义了响应的类别，且有五种可能取值：

1xx ：指示信息--表示请求已接收，继续处理

2xx ：成功--表示请求已被成功接收、理解、接受

3xx ：重定向--要完成请求必须进行更进一步的操作

4xx ：客户端错误--请求有语法错误或请求无法实现

5xx ：服务器端错误--服务器未能实现合法的请求

常见状态代码、状态描述、说明：

200 OK //客户端请求成功

400 Bad Request //客户端请求有语法错误，不能被服务器所理解

401 Unauthorized //请求未经授权，这个状态代码必须和WWW -Authenticate 报头域一起使用

403 Forbidden //服务器收到请求，但是拒绝提供服务

404 Not Found //请求资源不存在，eg ：输入了错误的URL

500 Internal Server Error //服务器发生不可预期的错误

503 Server Unavailable //服务器当前不能处理客户端的请求，一段时间后可能恢复正常 eg ：HTTP/1.1 200 OK （CRLF ）

2、响应报头后述

3、响应正文就是服务器返回的资源的内容

四、HTTP 协议详解之消息报头篇

HTTP 消息由客户端到服务器的请求和服务器到客户端的响应组成。请求消息和响应消息都是由开始行（对于请求消息，开始行就是请求行，对于响应消息，开始行就是状态行），消息报头（可选），空行（只有CRLF 的行），消息正文（可选）组成。

HTTP 消息报头包括普通报头、请求报头、响应报头、实体报头。

每一个报头域都是由名字+“：”+空格+值 组成，消息报头域的名字是大小写无关的。

1、普通报头

在普通报头中，有少数报头域用于所有的请求和响应消息，但并不用于被传输的实体，只用于传输的消息。

eg ：

Cache -Control 用于指定缓存指令，缓存指令是单向的（响应中出现的缓存指令在请求中未必会出现），且是独立的（一个消息的缓存指令不会影响另一个消息处理的缓存机制），HTTP1.0使用的类似的报头域为Pragma 。

请求时的缓存指令包括：no -cache （用于指示请求或响应消息不能缓存）、no -store 、max -age 、max -stale 、min -fresh 、only -if -cached;

响应时的缓存指令包括：public 、private 、no -cache 、no -store 、no -transform 、must -revalidate 、

proxy -revalidate 、max -age 、s -maxage.

eg ：为了指示IE 浏览器（客户端）不要缓存页面，服务器端的JSP 程序可以编写如下：response.sehHeader("Cache-Control","no -cache");

//response.setHeader("Pragma","no-cache"); 作用相当于上述代码，通常两者//合用

这句代码将在发送的响应消息中设置普通报头域：Cache -Control:no-cache

Date 普通报头域表示消息产生的日期和时间

Connection 普通报头域允许发送指定连接的选项。例如指定连接是连续，或者指定“close ”选项，通知服务器，在响应完成后，关闭连接

2、请求报头

请求报头允许客户端向服务器端传递请求的附加信息以及客户端自身的信息。

常用的请求报头

Accept

Accept 请求报头域用于指定客户端接受哪些类型的信息。eg ：Accept ：image/gif，表明客户端希望接受GIF 图象格式的资源；Accept ：text/html，表明客户端希望接受html 文本。 Accept -Charset

Accept -Charset 请求报头域用于指定客户端接受的字符集。eg ：Accept -Charset:iso-8859-1,gb2312. 如果在请求消息中没有设置这个域，缺省是任何字符集都可以接受。

Accept -Encoding

Accept -Encoding 请求报头域类似于Accept ，但是它是用于指定可接受的内容编码。eg ：Accept -Encoding:gzip.deflate.如果请求消息中没有设置这个域服务器假定客户端对各种内容编码都可以接受。

Accept -Language

Accept -Language 请求报头域类似于Accept ，但是它是用于指定一种自然语言。eg ：Accept -Language:zh-cn. 如果请求消息中没有设置这个报头域，服务器假定客户端对各种语言都可以接受。

Authorization

Authorization 请求报头域主要用于证明客户端有权查看某个资源。当浏览器访问一个页面时，如果收到服务器的响应代码为401（未授权），可以发送一个包含Authorization 请求报头域的请求，要求服务器对其进行验证。

Host （发送请求时，该报头域是必需的）

Host 请求报头域主要用于指定被请求资源的Internet 主机和端口号，它通常从HTTP URL 中提取出来的，eg ：

我们在浏览器中输入：http://www.guet.edu.cn/index.html

浏览器发送的请求消息中，就会包含Host 请求报头域，如下：

Host ：www.guet.edu.cn

此处使用缺省端口号80，若指定了端口号，则变成：Host ：www.guet.edu.cn:指定端口号 User -Agent

我们上网登陆论坛的时候，往往会看到一些欢迎信息，其中列出了你的操作系统的名称和版本，你所使用的浏览器的名称和版本，这往往让很多人感到很神奇，实际上，服务器应用程

序就是从User -Agent 这个请求报头域中获取到这些信息。User -Agent 请求报头域允许客户端将它的操作系统、浏览器和其它属性告诉服务器。不过，这个报头域不是必需的，如果我们自己编写一个浏览器，不使用User -Agent 请求报头域，那么服务器端就无法得知我们的信息了。

请求报头举例：

GET /form.html HTTP/1.1 (CRLF)

Accept:image/gif,image/x-xbitmap,image/jpeg,application/x-shockwave -flash,application/vnd.ms-excel,application/vnd.ms-powerpoint,application/msword,*/* (CRLF)

Accept -Language:zh-cn (CRLF)

Accept -Encoding:gzip,deflate (CRLF)

If -Modified -Since:Wed,05 Jan 2007 11:21:25 GMT (CRLF)

If -None -Match:W/"80b1a4c018f3c41:8317" (CRLF)

User -Agent:Mozilla/4.0(compatible;MSIE6.0;Windows NT 5.0) (CRLF)

Host:www.guet.edu.cn (CRLF)

Connection:Keep-Alive (CRLF)

(CRLF)

3、响应报头

响应报头允许服务器传递不能放在状态行中的附加响应信息，以及关于服务器的信息和对Request -URI 所标识的资源进行下一步访问的信息。

常用的响应报头

Location

Location 响应报头域用于重定向接受者到一个新的位置。Location 响应报头域常用在更换域名的时候。

Server

Server 响应报头域包含了服务器用来处理请求的软件信息。与User -Agent 请求报头域是相对应的。下面是

Server 响应报头域的一个例子：

Server ：Apache -Coyote/1.1

WWW -Authenticate

WWW -Authenticate 响应报头域必须被包含在401（未授权的）响应消息中，客户端收到401响应消息时候，并发送Authorization 报头域请求服务器对其进行验证时，服务端响应报头就包含该报头域。

eg ：WWW -Authenticate:Basic realm="Basic Auth Test!" //可以看出服务器对请求资源采用的是基本验证机制。

4、实体报头

请求和响应消息都可以传送一个实体。一个实体由实体报头域和实体正文组成，但并不是说实体报头域和实体正文要在一起发送，可以只发送实体报头域。实体报头定义了关于实体正文（eg ：有无实体正文）和请求所标识的资源的元信息。

常用的实体报头

Content -Encoding

Content -Encoding 实体报头域被用作媒体类型的修饰符，它的值指示了已经被应用到实体正

文的附加内容的编码，因而要获得Content -Type 报头域中所引用的媒体类型，必须采用相应的解码机制。Content -Encoding 这样用于记录文档的压缩方法，eg ：Content -Encoding ：gzip Content -Language

Content -Language 实体报头域描述了资源所用的自然语言。没有设置该域则认为实体内容将提供给所有的语言阅读

者。eg ：Content -Language:da

Content -Length

Content -Length 实体报头域用于指明实体正文的长度，以字节方式存储的十进制数字来表示。 Content -Type

Content -Type 实体报头域用语指明发送给接收者的实体正文的媒体类型。eg ：

Content -Type:text/html;charset=ISO-8859-1

Content -Type:text/html;charset=GB2312

Last -Modified

Last -Modified 实体报头域用于指示资源的最后修改日期和时间。

Expires

Expires 实体报头域给出响应过期的日期和时间。为了让代理服务器或浏览器在一段时间以后更新缓存中(再次访问曾访问过的页面时，直接从缓存中加载，缩短响应时间和降低服务器负载) 的页面，我们可以使用Expires 实体报头域指定页面过期的时间。eg ：Expires ：Thu ，15 Sep 2006 16:23:12 GMT

HTTP1.1的客户端和缓存必须将其他非法的日期格式（包括0）看作已经过期。eg ：为了让浏览器不要缓存页面，我们也可以利用Expires 实体报头域，设置为0，jsp 中程序如下：response.setDateHeader("Expires","0");

五、利用telnet 观察http 协议的通讯过程

实验目的及原理：

利用MS 的telnet 工具，通过手动输入http 请求信息的方式，向服务器发出请求，服务器接收、解释和接受请求后，会返回一个响应，该响应会在telnet 窗口上显示出来，从而从感性上加深对http 协议的通讯过程的认识。

实验步骤：

1、打开telnet

1.1 打开telnet

运行-->cmd-->telnet

1.2 打开telnet 回显功能

set localecho

2、连接服务器并发送请求

2.1 open www.guet.edu.cn 80 //注意端口号不能省略

HEAD /index.asp HTTP/1.0

Host:www.guet.edu.cn

/*我们可以变换请求方法, 请求桂林电子主页内容, 输入消息如下*/

open www.guet.edu.cn 80

GET /index.asp HTTP/1.0 //请求资源的内容

Host:www.guet.edu.cn

2.2 open www.sina.com.cn 80 //在命令提示符号下直接输入telnet www.sina.com.cn 80 HEAD /index.asp HTTP/1.0

Host:www.sina.com.cn

3 实验结果：

3.1 请求信息2.1得到的响应是:

HTTP/1.1 200 OK //请求成功

Server: Microsoft-IIS/5.0 //web服务器

Date: Thu,08 Mar 200707:17:51 GMT

Connection: Keep-Alive

Content -Length: 23330

Content -Type: text/html

Expries: Thu,08 Mar 2007 07:16:51 GMT

Set -Cookie: ASPSESSIONIDQAQBQQQB=BEJCDGKADEDJKLKKAJEOIMMH; path=/

Cache -control: private

//资源内容省略

3.2 请求信息2.2得到的响应是:

HTTP/1.0 404 Not Found //请求失败

Date: Thu, 08 Mar 2007 07:50:50 GMT

Server: Apache/2.0.54

Last -Modified: Thu, 30 Nov 2006 11:35:41 GMT

ETag: "6277a-415-e7c76980"

Accept -Ranges: bytes

X -Powered -By: mod_xlayout_jh/0.0.1vhs.markII.remix

Vary: Accept-Encoding

Content -Type: text/html

X -Cache: MISS from zjm152-78.sina.com.cn

Via: 1.0 zjm152-78.sina.com.cn:80

X -Cache: MISS from th-143.sina.com.cn

Connection: close

失去了跟主机的连接

按任意键继续...

4 .注意事项：1、出现输入错误，则请求不会成功。

2、报头域不分大小写。

3、更深一步了解HTTP 协议，可以查看RFC2616，在http://www.letf.org/rfc上找到该文件。

4、开发后台程序必须掌握http 协议

六、HTTP 协议相关技术补充

1、基础：

高层协议有：文件传输协议FTP 、电子邮件传输协议SMTP 、域名系统服务DNS 、网络新闻传输协议NNTP 和HTTP 协议等

中介由三种：代理(Proxy)、网关(Gateway)和通道(Tunnel)，一个代理根据URI 的绝对格式来接受请求，重写全部或部分消息，通过 URI 的标识把已格式化过的请求发送到服务器。网关是一个接收代理，作为一些其它服务器的上层，并且如果必须的话，可以把请求翻译给下层的服务器协议。一 个通道作为不改变消息的两个连接之间的中继点。当通讯需要通过一个中介(例如：防火墙等) 或者是中介不能识别消息的内容时，通道经常被使用。

代理(Proxy)：一个中间程序，它可以充当一个服务器，也可以充当一个客户机，为其它客户机建立请求。请求是通过可能的翻译在内部或经过传递到其它的 服务器中。一个代理在发送请求信息之前，必须解释并且如果可能重写它。代理经常作为通过防火墙的客户机端的门户，代理还可以作为一个帮助应用来通过协议处 理没有被用户代理完成的请求。 网关(Gateway)：一个作为其它服务器中间媒介的服务器。与代理不同的是，网关接受请求就好象对被请求的资源来说它就是源服务器；发出请求的客户机并没有意识到它在同网关打交道。

网关经常作为通过防火墙的服务器端的门户，网关还可以作为一个协议翻译器以便存取那些存储在非HTTP 系统中的资源。

通道(Tunnel)：是作为两个连接中继的中介程序。一旦激活，通道便被认为不属于HTTP 通讯，尽管通道可能是被一个HTTP 请求初始化的。当被中继 的连接两端关闭时，通道便消失。当一个门户(Portal)必须存在或中介(Intermediary)不能解释中继的通讯时通道被经常使用。

2、协议分析的优势—HTTP 分析器检测网络攻击

以模块化的方式对高层协议进行分析处理，将是未来入侵检测的方向。

HTTP 及其代理的常用端口80、3128和8080在network 部分用port 标签进行了规定

3、HTTP 协议Content Lenth限制漏洞导致拒绝服务攻击

使用POST 方法时，可以设置ContentLenth 来定义需要传送的数据长度，例如ContentLenth:999999999，在传送完成前，内 存不会释放，攻击者可以利用这个缺陷，连续

向WEB 服务器发送垃圾数据直至WEB 服务器内存耗尽。这种攻击方法基本不会留下痕迹。 http://www.cnpaf.net/Class/HTTP/[**************]0.html

4、利用HTTP 协议的特性进行拒绝服务攻击的一些构思

服务器端忙于处理攻击者伪造的TCP 连接请求而无暇理睬客户的正常请求（毕竟客户端的正常请求比率非常之小），此时从正常客户的角度看来，服务器失去响应，这种情况我们称作：服务器端受到了SYNFlood 攻击（SYN 洪水攻击）。

而Smurf 、TearDrop 等是利用ICMP 报文来Flood 和IP 碎片攻击的。本文用“正常连接”的方法来产生拒绝服务攻击。

19端口在早期已经有人用来做Chargen 攻击了，即Chargen_Denial_of_Service，但是！他们用的方法是在两台Chargen 服务器之间产生UDP 连接，让服务器处理过多信息而DOWN 掉，那么，干掉一台WEB 服务器的条件就必须有2个：1. 有Chargen 服务2. 有HTTP 服务

方法：攻击者伪造源IP 给N 台Chargen 发送连接请求（Connect ），Chargen 接收到连接后就会返回每秒72字节的字符流（实际上根据网络实际情况，这个速度更快）给服务器。

5、Http 指纹识别技术

Http 指纹识别的原理大致上也是相同的：记录不同服务器对Http 协议执行中的微小差别进行识别.Http 指纹识别比TCP/IP堆栈指纹识别复杂许 多, 理由是定制Http 服务器的配置文件、增加插件或组件使得更改Http 的响应信息变的很容易, 这样使得识别变的困难；然而定制TCP/IP堆栈的行为 需要对核心层进行修改, 所以就容易识别.

要让服务器返回不同的Banner 信息的设置是很简单的, 象Apache 这样的开放源代码的Http 服务器, 用户可以在源代码里修改Banner 信息, 然 后重起Http 服务就生效了；对于没有公开源代码的Http 服务器比如微软的IIS 或者是Netscape, 可以在存放Banner 信息的Dll 文件中修 改, 相关的文章有讨论的, 这里不再赘述, 当然这样的修改的效果还是不错的. 另外一种模糊Banner 信息的方法是使用插件。

常用测试请求：

1：HEAD/Http/1.0发送基本的Http 请求

2：DELETE/Http/1.0发送那些不被允许的请求, 比如Delete 请求

3：GET/Http/3.0发送一个非法版本的Http 协议请求

4：GET/JUNK/1.0发送一个不正确规格的Http 协议请求

Http 指纹识别工具Httprint, 它通过运用统计学原理, 组合模糊的逻辑学技术, 能很有效的确定Http 服务器的类型. 它可以被用来收集和分析不同Http 服务器产生的签名。

6、其他：为了提高用户使用浏览器时的性能，现代浏览器还支持并发的访问方式，浏览一个网页时同时建立多个连接，以迅速获得一个网页上的多个图标，这样能更快速完成整个网页的传输。

HTTP1.1中提供了这种持续连接的方式，而下一代HTTP 协议：HTTP -NG 更增加了有关会话控制、丰富的内容协商等方式的支持，来提供

更高效率的连接。

7、哈夫曼树与哈夫曼编码

在一般的数据结构的书中，树的那章后面，著者一般都会介绍一下哈夫曼(HUFFMAN)

树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如

JPEG 中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树，

是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点

的权值乘上其到根结点的 路径长度（若根结点为0层，叶结点到根结点的路径长度

为叶结点的层数）。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

，N 个权值Wi(i=1,2,...n)构成一棵有N 个叶结点的二叉树，相应的叶结点的路径

长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL 是最小的。

哈夫曼编码步骤：

一、对给定的n 个权值{W1,W2,W3,...,Wi,...,Wn}构成n 棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti 中只有一个权值为Wi 的根结点，它的左右子树均为空。（为方便在计算机上实现算 法，一般还要求以Ti 的权值Wi 的升序排列。）

二、在F 中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。

三、从F 中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F 中。

四、重复二和三两步，直到集合F 中只有一棵二叉树为止。

简易的理解就是，假如我有A,B,C,D,E 五个字符，出现的频率（即权值）分别为5,4,3,2,1, 那么我们第一步先取两个最小权值作为左右子树构造一个新树，即取1，2构成新树，其结点为1+2=3，如图：

虚线为新生成的结点，第二步再把新生成的权值为3的结点放到剩下的集合中，所以集合变成{5,4,3,3}，再根据第二步，取最小的两个权值构成新树，如图：

再依次建立哈夫曼树，如下图：

其中各个权值替换对应的字符即为下图：

所以各字符对应的编码为：A ->11,B->10,C->00,D->011,E->010

霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩，加密解密等场合。

C 语言代码实现：

/*-------------------------------------------------------------------------

* Name: 哈夫曼编码源代码。

* Date: 2011.04.16

* Author: Jeffrey Hill+Jezze(解码部分)

* 在 Win -TC 下测试通过

* 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中 * 自底向上开始(也就是从数组序号为零的结点开始) 向上层层判断，若在 * 父结点左侧，则置码为 0, 若在右侧, 则置码为 1。最后输出生成的编码。 *------------------------------------------------------------------------*/

#include

#include

#define MAXBIT 100

#define MAXVALUE 10000

#define MAXLEAF 30

#define MAXNODE MAXLEAF*2 -1

typedef struct

{

int bit[MAXBIT];

int start;

} HCodeType; /* 编码结构体 */

typedef struct

{

int weight;

int parent;

int lchild;

int rchild;

int value;

} HNodeType; /* 结点结构体 */

/* 构造一颗哈夫曼树 */

void HuffmanTree (HNodeType HuffNode[MAXNODE], int n)

{

/* i、j ： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/ int i, j, m1, m2, x1, x2;

/* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */

for (i=0; i

{

HuffNode[i].weight = 0;//权值

HuffNode[i].parent =-1;

HuffNode[i].lchild =-1;

HuffNode[i].rchild =-1;

HuffNode[i].value=i; //实际值，可根据情况替换为字母

} /* end for */

/* 输入 n 个叶子结点的权值 */

for (i=0; i

{

printf ("Please input weight of leaf node %d: \n", i);

scanf ("%d", &HuffNode[i].weight);

} /* end for */

/* 循环构造 Huffman 树 */

for (i=0; i

{

m1=m2=MAXVALUE; /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */

x1=x2=0;

/* 找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 */ for (j=0; j

{

if (HuffNode[j].weight

{

m2=m1;

x2=x1;

m1=HuffNode[j].weight;

x1=j;

}

else if (HuffNode[j].weight

{

m2=HuffNode[j].weight;

x2=j;

}

} /* end for */

/* 设置找到的两个子结点 x1、x2 的父结点信息 */

HuffNode[x1].parent = n+i;

HuffNode[x2].parent = n+i;

HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;

HuffNode[n+i].lchild = x1;

HuffNode[n+i].rchild = x2;

printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight); /* 用于测试 */

printf ("\n");

} /* end for */

/* for(i=0;i

{

printf("

Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);

}*///测试

} /* end HuffmanTree */

//解码

void decodeing(char string[],HNodeType Buf[],int Num)

{

int i,tmp=0,code[1024];

int m=2*Num-1;

char *nump;

char num[1024];

for(i=0;i

{

if(string[i]=='0')

num[i]=0;

else

num[i]=1;

}

i=0;

nump=&num[0];

while(nump

{tmp=m-1;

while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))

{

if(*nump==0)

{

tmp=Buf[tmp].lchild ;

}

else tmp=Buf[tmp].rchild;

nump++;

}

printf("%d",Buf[tmp].value);

}

}

int main(void)

{

HNodeType HuffNode[MAXNODE]; /* 定义一个结点结构体数组 */

HCodeType HuffCode[MAXLEAF], cd; /* 定义一个编码结构体数组， 同时定义一个临时变量来存放求解编码时的信息 */

int i, j, c, p, n;

char pp[100];

printf ("Please input n:\n");

scanf ("%d", &n);

HuffmanTree (HuffNode, n);

for (i=0; i

{

cd.start = n-1;

c = i;

p = HuffNode[c].parent;

while (p != -1) /* 父结点存在 */

{

if (HuffNode[p].lchild == c)

cd.bit[cd.start] = 0;

else

cd.bit[cd.start] = 1;

cd.start --; /* 求编码的低一位 */

c=p;

p=HuffNode[c].parent; /* 设置下一循环条件 */

} /* end while */

/* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */

for (j=cd.start+1; j

{ HuffCode[i].bit[j] = cd.bit[j];}

HuffCode[i].start = cd.start;

} /* end for */

/* 输出已保存好的所有存在编码的哈夫曼编码 */

for (i=0; i

{

printf ("%d 's Huffman code is: ", i);

for (j=HuffCode[i].start+1; j

{

printf ("%d", HuffCode[i].bit[j]);

}

printf(" start:%d",HuffCode[i].start);

printf ("\n");

}

/* for(i=0;i

for(j=0;j

{

printf ("%d", HuffCode[i].bit[j]);

}

printf("\n");

}*/

printf("Decoding?Please Enter code:\n");

scanf("%s",&pp);

decodeing(pp,HuffNode,n);

getch();

return 0;

}

8、设计模式

设计模式——结构型模式（包含7种）

结构型设计模式是从程序的结构上解决模块之间的耦合问题。包括以下七种模式：

1.Adapte 适配器模式：Adapter 模式通过类的继承或者对象的组合侧重于转换已有的接口，类适配器采用“多继承”的实现方式，带来了不良的高耦合，所以一般不推荐使用。对象适配器采用“对象组合”的方式，更符合松耦合精神。

例如：笔记本 电源适配器，可以将220v 转化为适合笔记本使用的电压。

2.Bridge 桥接模式：将抽象部分与实现部分分离，使它们都可以独立的变化。减少因变化带来的代码的修改量。

例如：经典例子, 电灯开关，开关的目的是将设备打开或关闭，产生的效果不同。

3.Composite 组合模式：将对象组合成树形结构以表示“部分-整体”的层次结构。Composite 模式使得客户对单个对象和组合对象的使用具有一致性。从而解决了解决客户程序与复杂对象容器的解耦，即：通过继承统一的接口，我们可以将容器对象及其子对象看成同一类对象使用，以减少对象使用中的复杂度。

例如：让用户一致地使用单个对象和组合对象，1+2和（1+1）+（2*3）都是合法的表达式。 单个与整体都可以进行加法运算符的操作。

4.Decorator 装饰模式：动态地给一个对象添加一些额外的职责。就增加功能来说，Decorator 模式相比生成子类更为灵活。[GOF 《设计模式》]Decorator模式采用对象组合而非继承的手法，实现了在运行时动态的扩展对象功能的能力，而且可以根据需要扩展多个功能，避免

了单独使用继承带来的“灵活性差”和“多子类衍生问题”。同时它很好地符合面向对象设计原则中“优先使用对象组合而非继承”和“开放-封闭”原则。

例如：一幅画，可以直接挂到墙上，也可以加上框架和镶上玻璃后，再挂到墙上。

5.Facade 外观模式：为子系统中的一组接口提供一个一致的界面，简化接口。

例如：我们拨打10086，可以办理，彩铃，手机报，全时通等业务（子对象），而10086则是为子对象所使用的一致界面。

6.Flyweight 享元模式：运用共享技术有效地支持大量细粒度的对象。[GOF 《设计模式》]。 解决：面向对象的思想很好地解决了抽象性的问题，一般也不会出现性能上的问题。但是在某些情况下，对象的数量可能会太多，从而导致了运行时的代价。那么我们如何去避免大量细粒度的对象，同时又不影响客户程序使用面向对象的方式进行操作，享元模式的出现恰好解决了该问题。

例如：公共交换电话网（PSTN ）是享元的一个例子。有一些资源例如拨号音发生器、振铃发生器和拨号接收器是必须由所有用户共享的。当一个用户拿起听筒打电话时，他不需要知道使用了多少资源。对于用户而言所有的事情就是有拨号音，拨打号码，拨通电话。

7.Proxy 代理模式：为其他对象提供一种代理以控制这个对象的访问。解决直接访问某些对象是出现的问题。

例如：律师本身就是我们维权的一个代理！

小总结：从代码的角度看Adapter 适配器模式和Proxy 代理模式有些类似，前者是解决现有对象在新的环境中所遇到的问题，后者是解决直接访问对象时出现的问题，这两种模式从使用角度看都是解决直接访问对象时出现的问题，只是含义不十分相同。