数 据结构是在整个计算机科学与技术领域上广泛被使用的术语。它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。数 据结构有逻辑上的数据结构和物理上的数据结构之分。逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安 排。数据结构是数据存在的形式。

数据结构是信息的一种组织方式，其目的是为了提高算法的效率，它通常与一组算法的集合相对应，通过这组算法集合可以对数据结构中的数据进行某种操作。

数据结构主要研究什么？

数据结构作为一门学科主要研究数据的各种逻辑结构和存储结构，以及对数据的各种操作。因此，主要有三个方面的内容：数据的逻辑结构；数据的物理存储结构；对数据的操作（或算法）。通常，算法的设计取决于数据的逻辑结构，算法的实现取决于数据的物理存储结构。

什么是数据结构？什么是逻辑结构和物理结构？

数据是指由有限的符号（比如，"0"和"1"，具有其自己的结构、操作、和相应的语义）组成的元素的集合。结构是元素之间的关系的集合。通常来说，一个数据结构DS 可以表示为一个二元组：

DS=(D,S), //i.e., data-structure=(data-part,logic-structure-part)

这里D是数据元素的集合（或者是“结点”，可能还含有“数据项”或“数据域”），S是定义在D（或其他集合）上的关系的集合，S = { R | R : D×D×...}，称之为元素的逻辑结构。

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。表和树是最常用的两种高效数据结构，许多高效的算法可以用这两种数据结构来设计实现。表是线性结构的（全序关系），树(偏序或层次关系)和图（局部有序(weak/local orders)）是非线性结构。

数据结构的物理结构是指逻辑结构的存储镜像(image)。数据结构 DS 的物理结构 P 对应于从 DS 的数据元素到存储区M（维护着逻辑结构S）的一个映射：

P:(D,S) --> M

存储器模型：一个存储器 M 是一系列固定大小的存储单元，每个单元 U 有一个唯一的地址 A(U)，该地址被连续地编码。每个单元 U 有一个唯一的后继单元 U'=succ(U)。

P 的四种基本映射模型：顺序（sequential）、链接（linked）、索引（indexed）和散列（hashing）映射。

因此，我们至少可以得到4×4种可能的物理数据结构：

（并不是所有的可能组合都合理）

数据结构DS上的操作：所有的定义在DS上的操作在改变数据元素（节点）或节点的域时必须保持DS的逻辑和物理结构。

DS上的基本操作：任何其他对DS的高级操作都可以用这些基本操作来实现。最好将DS和他的所有基本操作看作一个整体——称之为模块。我们可以进一步将该模块抽象为数据类型（其中DS的存储结构被表示为私有成员，基本操作被表示为公共方法），称之为ADT。作为ADT，堆栈和队列都是一种特殊的表，他们拥有表的操作的子集。

对于DATs的高级操作可以被设计为（不封装的）算法，利用基本操作对DS进行处理。

好的和坏的DS：如果一个DS可以通过某种“线性规则”被转化为线性的DS（例如线性表），则称它为好的DS。好的DS通 常对应于好的（高效的）算法。这是由计算机的计算能力决定的，因为计算机本质上只能存取逻辑连续的内存单元，因此如何没有线性化的结构逻辑上是不可计算 的。比如对一个图进行操作，要访问图的所有结点，则必须按照某种顺序来依次访问所有节点（要形成一个偏序），必须通过某种方式将图固有的非线性结构转化为 线性结构才能对图进行操作。

树是好的DS——它有非常简单而高效的线性化规则，因此可以利用树设计出许多非常高效的算法。树的实现和使用都很简单，但可以解决大量特殊的复杂问题，因此树是实际编程中最重要和最有用的一种数据结构。树的结构本质上有递归的性质——每一个叶节点可以被一棵子树所替代，反之亦然。实际上，每一种递归的结构都可以被转化为（或等价于）树形结构。

计算机中数据的描述方式

我们知道，数据可以用不同的形式进行描述或存储在计算机存储器中。最常见的数据描述方法有：公式化描述、链接描述、间接寻址和模拟指针。

• 公 式化描述借助数学公式来确定元素表中的每个元素分别存储在何处，也就通过公式计算元素的存储器地址。最简单的情形就是把所有元素依次连续存储在一片连续的 存储空间中，这就是通常所说的连续线性表，即数组。复杂一点的情形是利用复杂的函数关系根据元素的某些特征来计算元素在内存中的位置，这种技术称为散列技 术(Hash，经常音译为哈希技术)。
• 在链接描述中，元素表中的每个元素可以存储在存储器的不同区域中，每个元素都包含一个指向下一个元素的指针。这就是通常所说的链表。这种描述方法的好处是，知道了第一个元素的位置，就可以依次找到第n个元素的位置，而且在其中插入元素非常方便，缺点是查找某个元素要遍历所有在该元素之前的元素，实际应用中经常和公式化描述结合起来使用。
• 在间接寻址方式中，元素表中的每个元素也可以存储在存储器的不同区域中，不同的是，此时必须保存一张表，该表的第i项指向元素表中的第i个元素，所以这张表是一个用来存储元素地址的表。指针数组（元素为指针的数组）就是这种描述法的应用。这种描述方法是公式化描述和链接描述的一种折衷方案，同时具有两种描述方法的优点，但是需要额外的内存开销。
• 模 拟指针非常类似于链接描述，区别在于它用整数代替了指针，整数所扮演的角色与指针所扮演的角色完全相同。模拟指针的描述方式是链接描述和公式化描述的结 合，元素被存储在不同的区域中，每个元素包含一个指示下一个元素位置的整数，可以通过某种公式由该整数计算出下一个元素的存储器地址。线性表的游标实现就是模拟指针描述法。

转自：http://www.programfan.com/blog/article.asp?id=5306

AHCI

　　AHCI，全称为Serial ATA Advanced Host Controller Interface（串行ATA高级主控接口/高级主机控制器接口），是在Intel的指导下，由多家公司联合研发的接口标准，它允许存储驱动程序启用高级串行 ATA 功能，如本机命令队列和热插拔，其研发小组成员主要包括Intel、AMD、戴尔、Marvell、迈拓、微软、Red Hat、希捷和StorageGear等著名企业。

　　AHCI本质是一种PCI类设备，在系统内存总线和串行ATA设备内部逻辑之间扮演一种通用接口的角色（即它在不同的操作系统和硬件中是通用的）。这个类设备描述了一个含控制和状态区域、命令序列入口表的通用系统内存结构；每个命令表入口包含SATA设备编程信息，和一个指向（用于在设备和主机传输数据的）描述表的指针。

　　AHCI通过包含一个PCI BAR（基址寄存器），来实现原生SATA功能。由于AHCI统一接口的研发成功，使得支持串行ATA产品的开发工作大为简化，操作系统和设备制造商省去了单独开发接口的工作，取而代之的是直接在统一接口上进行操作，可以实现包括NCQ（Native Command Queuing）在内的诸多功能。

　　AHCI模式则与IDE模式相反，装系统时需要安装SATA驱动（而且貌似只有这个模式才能打开NCQ功能）。

　　RAID模式是要有两块硬盘才能实现的，具体情况可以参照一下网上组建RAID的文章，如果你只有一块硬盘就可以忽略它了。

　　补充： NCQ是一种新的硬盘技术，简单来说开启它之后从一个程序跳到另一个程序时速度会更快，要实现它首先就要在BIOS里选择AHCI模式，然后在装系统时安装相应的驱动（一般在主板驱动盘里有），安装好系统之后基本上就可以实现了 。

　　一直以来SCSI硬盘在多任务负载下的表现能力为人称道，其根本的原因除了SCSI接口惊人的接口速率外，便是它的指令排序功能。以往的PATA、SATA硬盘也正是因为缺少一种指令优化执行功能而在性能上落后于SCSI硬盘。针对这一困境，Intel的AHCI 1.0规范首次引入的NCQ（Native Command Qu），它的应用能够大幅度减少硬盘无用的寻道次数和数据查找时间，这样就能显著增强多任务情况下硬盘的性能。

　　另外，作为SATA标准的改进版，Intel完善了Serial ATA II接口的详细规格，并表示串行ATA II的研发将属于AHCI统一接口的第二个阶段。而其中第一阶段从06年已经开始，不少厂商也推出Serial ATA接口的产品，包括硬盘和主板。但这仅仅是作为过渡，在第二阶段，Serial ATA II将会凭借更高的信号传输速度直接取代SATA.

　　————————————理论结束，现在看看你的电脑是不是支持它

　　注：AHCI 需要英特尔? 应用程序加速器 4.1 或更高版本，并与下列控制器集线器一同置入芯片组：

　　英特尔? 82801GBM I/O 控制器集线器 (ICH7M) - 仅限 AHCI

　　英特尔? 82801GR I/O 控制器集线器 (ICH7R) - RAID 和 AHCI

　　英特尔? 82801GH I/O 控制器集线器 (ICH7DH) - RAID 和 AHCI

　　英特尔? 82801FR I/O 控制器集线器（ICH6R）- RAID 和 AHCI

　　英特尔? 82801FBM I/O 控制器集线器 (ICH6M) - 仅限 AHCI

　　基于 ICH7 和 ICH6 的芯片组，以及基于 ICH5 和 ICH5R 的芯片组，未使用 AHCI。

　　如果你的芯片不支持，千万不要乱用哦！

　　01.何谓AHCI功能？

　　全名 Advanced Host Controller Interface，中译：进阶主机

　　控制器介面，它是 Intel 所主导的一项技术，可以发挥SATA

　　硬碟的潜在加速功能，大约可增加30%的硬碟读写速度。

　　02.何谓SATA硬碟？

　　指 Serial ATA硬碟，是由PATA：Parellel ATA演进；SATA目

　　前为主流，排线细、传输速度快，而PATA排线宽，速度较慢

　　，旧电脑硬碟都是用此架构，将被世代交替，俗称IDE硬碟，

　　故新买电脑要选择SATA硬碟，且需是SATA2的规格。

　　03.AHCI所需具备之要件？

　　-1.硬碟机必须有NCQ(Native Command Queuing )原生伫列之

　　功能，一般都是SATA2的硬碟，目前市面上所贩卖的SATA

　　硬碟应该都是此规格。

　　-2.电脑主机板南桥晶片，要有支援AHCI的能力，故旧电脑是

　　无法享受。

　　-3.电脑BIOS要将AHCI功能打开，未打开也是无法享受。

　　04.如何开启AHCI功能？新安装作业系统(OS)：

　　XP光碟开机安装系统，必须先按下F6载入具备AHCI功能

　　之SATA驱动程式 F6FLPY32.ZIP；那事先已经安装好XP

　　的电脑，未载入正确Driver之人士，不就要重灌电脑了吗？

　　05.作业系统已经存在，想补救，开启AHCI功能？

　　-1.先将SATA硬碟，插在非南桥晶片所支援的SATA插槽座，

　　例如JMicron晶片，不知外插卡可以吗？

　　-2.进入BIOS将JMicron晶片由BASIC改成AHCI模式。

　　-3.进入BIOS将INTEL晶片由IDE改成AHCI模式。

　　-4.进入XP，安装IMSM(Intel Matrix Storage Manager)

　　Intel® 矩阵储存技术 IATA621.EXE Driver。

　　-5.将SATA硬碟插回南桥ICH的SATA插槽，就可OK了！

是以韩国三星、LG为首的一批厂商开发的一种所谓的Super-Multi刻录机，目的是将所有的刻录标准一网打尽。这种所谓的Super-Multi产品就称为RAMBO(在三星选择进入DVD刻录领域时，它最先看中的是DVD-RAM，这可能是RAMBO一词的由来）。它是过去几种DVD刻录标准的集合，只是一种现行的叫法，而非一种新的刻录标准，它包含了DVD-Multi和DVD-Dual。Rambo光驱支持刻录盘片的格式包括CD-R/RW，DVD+R/RW，DVD-R/RW，DVD-RAM

IDE

　　IDE有多种含义

　　解释一：

　　集成设备电路，Integrated Device Electronics，一般会作为ATA硬件的接口，它的本意是指把“硬盘控制器”与“盘体”集成在一起的硬盘驱动器。把盘体与控制器集成在一起的做法减少了硬盘接口的电缆数目与长度，数据传输的可靠性得到了增强，硬盘制造起来变得更容易，因为硬盘生产厂商不需要再担心自己的硬盘是否与其它厂商生产的控制器兼容。对用户而言，硬盘安装起来也更为方便。IDE这一接口技术从诞生至今就一直在不断发展，性能也不断的提高，其拥有的价格低廉、兼容性强的特点，为其造就了其它类型硬盘无法替代的地位。

　　　IDE ATA/ATAPI控制器

　　PIO的英文拼写是“Programming Input/Output Model”，PIO模式是一种通过CPU执行I/O端口指令来进行数据的读写的数据交换模式。是最早先的硬盘数据传输模式，数据传输速率低下，CPU占有率也很高，大量传输数据时会因为占用过多的CPU资源而导致系统停顿，无法进行其它的操作。PIO数据传输模式又分为PIO mode 0、PIO mode 1、PIO mode 2、PIO mode 3、PIO mode 4几种模式，数据传输速率从3.3MB/s到16.6MB/s不等。受限于传输速率低下和极高的CPU占有率，这种数据传输模式很快就被淘汰。

　　IDE架构剖析与发展趋势

　　Enhanced IDE接口历史(一)

　　1． AT ATTACHMENT （ATA）：ATA接口是个人电脑上最具有实力的存储接口，ATA接口早先被广泛应用于IBM及其兼容机，它被定义为标准的硬盘接口。

　　2． ATA-1：ATA硬盘接口的第一代标准ANSI X3.279-1994，也就是早期的IDE接口。

　　3． ATA-2：ATA硬盘接口的第二代标准ANSI X3.279-1995，就是大家所知道的Fast ATA或者称之为Enhanced IDE（EIDE）接口。

　　4． Apple-ATA：Apple上使用的ATA接口，当然也是由标准的ATA接口演化而来的，在ANSI的国际标准提案申请为X3T9.2/90-143.Revision 3.1，这一个由标准ATA接口规格演化而来Apple-ATA支持IDE接口的硬盘LBA驱动模式，但是没有支持ATATP。

　　5． ATA-3：ATA硬盘接口的第三代标准ANSI X3T13/2008D Revision 7（draft），同样包含在Fast ATA或Enhanced IDE的接口之中，一般使用者大多都知道Fast ATA或是Enhanced IDE接口，而对原来Fast ATA或Enhanced IDE接口居然还包括了ATA-2以及ATA-3两组国际标准。

　　6． ATAPI：AT Attachment Packet Interface，这是ATA Protocol的延伸，被定义用来支持CD-ROM光驱以及Tape磁带机，这一个ATAPI Protocol容许硬盘以外的设备使用ATA数据线。

　　7． ATA/ATAPI-4：ATA硬盘接口的第四代标准ANSI X3T13/D96153（draft），也就是大家所知道的Ultra ATA或是Ultra DMA，这一个版本支持33MB/sec的数据传输率（in burst mode），相信各位读者对ATA-4/Ultra DMA都是比较熟悉的了。

　　8． ATA/ATAPI-5：这是目前ATA硬盘接口的比较新的一代标准，这一规格里规定的数据流传输速率（in burst mode）为66MB/sec，并且加强了内部资料的检查与错误修正的算法，强化了资料的完整性和可靠性。

　　9． ATA/ATAPI-6：还有更新的一个标准，是ATA/ATAPI-5的改进，这一规格里规定的数据流传输速率（in burst mode）为100MB/sec。

　　表一：

　　PIO驱动模式的资料传输速率

　　PIO Mode Cycle time Transfer Rate

　　PIO Mode 0 600ns 3.3Mbytes/sec

　　PIO Mode 1 383ns 5.2Mbytes/sec

　　PIO Mode 2 240ns 8.3Mbytes/sec

　　PIO Mode 3 180ns 11.1Mbytes/sec

　　PIO Mode 4 120ns 16.6Mbytes/sec

　　Enhanced IDE接口发展至今，ULTRA DIRECT MEMORY ACCESS（ULTRA-DMA）的是目前最新的目前大家最为熟悉的就是Ultra-DMA的资料传输率最高可以达到ATA-3标准的四倍，也就是66.6Mbytes/sec。

　　实际上硬盘接口的鼻祖，除了SCSI界面以外，就是MFM/ST-506 Bus接口了，后来经过不断的演变才演进成为今天的Enhanced IDE接口，而在Enhanced IDE之前的IDE/AT-BUS接口，则仅仅提供了PIO驱动模式，而没有DMA驱动模式，这两种驱动模式简单来讲区别主要是在数据传输时是否需要CPU来控制。在PIO模式下，任何一个硬盘的读取动作，都必须经过CPU来控制管理，所以只要硬盘读写动作频繁的时候，CPU的资源就被大量的消耗，今儿降低了电脑整体的效率。而在DMA模式下，硬盘和内存之间的数据可以直接交换，这样就不会占用CPU的资源，提高了电脑的整体效率。读者千万不要忽略掉从PIO到DMA的进步，事实上个人电脑内的任何一个动作都必须运用系统的内存，毕竟CPU内部的缓存器容量太小了，所以凡是程序的读取、运算都必须在内存上操作，这样从硬盘到内存的数据交换就会非常频繁，所以简化这么一步对于电脑整体性能的提高还是非常突出的。

　　以前硬盘采用PIO模式的时候，只要一开始大量的硬盘读写操作，就会使得电脑的性能急剧下降，让人感觉电脑总在等待什么似的，实际上SCSI接口一开始也是采用PIO模式，后来也演变成了DMA模式，IDE/AT-BUS接口也不例外，到了PIO Mode 4驱动模式之后，IDE/AT-BUS接口已经成功的演化成为Enhanced IDE接口，驱动模式也由PIO Mode 4升级为Multi－word DMA Mode2，原本预计还有一个PIO Mode 5会问世的，但是DMA Mode已经出现，PIO Mode已经没有市场了。

　　所以读者可以认为Enhanced IDE接口的特点主要在于：驱动模式的改变，增加了对非硬盘存储设备的支持等，而且原本是一组的IDE界面现在也增加到了两组。

　　DMA的全名为Direct Memory Access直接内存存取，采用DMA驱动模式以后，CPU不再象往常那样需要花费相当多的时间在硬盘的O/I操作上，DMA的意义就是在于让硬盘和内存直接沟通，所有的硬盘操作都不需要占用太多的CPU时间。

　　接着让我们来看看DMA Mode的相关资料。

　　DMA驱动模式资料传输速率

　　DMA Mode I/O Cycle time Transfer Rate

　　Single-word DMA Mode 0 900ns 2.1 Mbytes/sec

　　Single-word DMA Mode 1 480ns 4.2 Mbytes/sec

　　Single-word DMA Mode 2 240ns 8.4 Mbytes/sec

　　Multi-word DMA Mode 0 480ns 4.2 Mbytes/sec

在不记得硬盘结构的情况下可以使用

grub> root (hd0,按下TAB   

的方式来查看硬盘情况，选择EXT格式得硬盘作为引导。进入LINUX系统后修改系统可以通过修改/BOOT/grub.conf文件来进行。

转自：http://blog.sina.com.cn/s/blog_4a668047010005d7.html

任何语言只要表达能力足够强，都可用于编写PE病毒。但现存的绝大部分PE病毒都是直接用汇编编写的，一方面是因为汇编编译后的代码短小精悍，可以充分进行人工优化，以满足隐蔽性的要求；另外一方面之所以用汇编是因为其灵活和可控，病毒要同系统底层有时甚至是硬件打交道，由于编译器的特点不尽相同，用高级语言实现某些功能甚至会更加麻烦，比如用汇编很方便地就可以直接进行自身重定位、自身代码修改以及读写IO端口等操作，而用高级语言实现则相对烦琐。用汇编还可以充分利用底层硬件支持的各种特性，限制非常少。但是用汇编编写病毒的主要缺点就是编写效率低，加上使用各种优化手段使得代码阅读起来相当困难，不过作为一种极限编程技术，对病毒作者而言，这些似乎都已经不再重要。本文假设读者熟悉汇编语言，各种举例使用Intel格式的汇编代码，编译器可使用MASM或FASM进行编译，由于汇编语言表述算法较为不便，因此算法和原理性表述仍然采用C语言。在讲述各种技术时，部分代码直接取自病毒Elkern的源代码，该病毒在2002年曾经大规模流行，其代码被收录于著名病毒杂志29A第7期中，有兴趣的读者可参阅其完整代码。

* 重定位

病毒自身的重定位是病毒代码在得以顺利运行前应解决的最基本问题。病毒代码在运行时同样也要引用一些数据，比如API函数的名字、杀毒软件的黑名单、系统相关的特殊数据等，由于病毒代码在宿主进程中运行时的内存地址是在编译汇编代码时无法预知的，而病毒在感染不同的宿主时其位于宿主中的准确位置同样也无法提前预知，因此病毒就要在运行时动态确定其引用数据的地址，否则，引用数据时几乎肯定会发生错误。对于普通的PE文件比如动态链接库而言，在被加载到不同地址处时由加载器根据PE中一个被称为重定位表的特殊结构动态修正引用数据指令的地址，而重定位表是由编译器在编译阶段生成的，因此动态链接库本身无需为此做任何额外处理。病毒代码则不同，必须自己动态确定需引用数据的地址。比如一段病毒代码被加载在0x400000处，地址0x401000处的一条语句及其引用的数据定义如下所示，相关地址是编译器在编译时计算得到的，这里假设编译时预设的基地址也是0x400000：
401000:
mov eax,dword ptr [402035]
......
402035:
db "hello world!",0
　　如果病毒代码在宿主中也加载到基地址0x400000，显然是能够正常执行的，但如果这段代码被加载在基地址0x500000运行时则出错，对病毒而言，这是大多数时候都会遇到的情况，因为指令中引用的仍然是0x402035这个地址。如果病毒代码不是在宿主进程中而是作为一个具有重定位表的独立PE文件运行，正常情况下由系统加载器根据重定位表表项将 mov eax,dword ptr [402035]中的0x402035修改为正确值0x502305，这样这句代码就变成了mov eax,dword ptr [5402035]，程序也就能准确无误地运行了。不过很可惜，对在其它进程内运行病毒代码而言，必须采取额外的手段、付出额外的代价感染宿主PE文件时就及时加以解决，否则将导致宿主进程无法正常运行。

至少有两种方法可以解决重定位的问题：

A）第一种方法就是利用上述PE文件重定位表项的特殊作用构造相应的重定位表项。在感染目标PE文件时，将引用自身数据的需要被重定位的地址全部写入目标PE文件的重定位表中，如果目标PE无任何重定位表项（如用MS linker的/fixed）则创建重定位表节并插入新的重定位项；若已经存在重定位表项，则在修改已存在的重定位表节，在其中插入包含了这些地址的新表项。重定位的工作就完全由系统加载器在加载PE文件的时候自动进行了。重定位表项由PE文件头的DataDirectory数据中的第6个成员IMAGE_DIRECTORY_ENTRY_BASERELOC指向。该方法需要的代码稍多，实现起来也相对比较复杂，另外如果目标文件无重定位表项（为了减小代码体积，这种情况也不少见），处理起来就比较麻烦，只有用高级语言编写病毒才常用该种方法，在一般的PE病毒中很少使用。

B）利用Intel X86体系结构的特殊指令，call或fnstenv等指令动态获取当前指令的运行时地址，计算该地址与编译时预定义地址的差值（被称为delta offset），再将该差值加到原编译时预定的地址上，得到的就是运行时数据的正确地址。对于intel x86指令集而言，在书写代码时，通过将delta offset放在某个寄存器中，然后通过变址寻址引用数据就可以解决引用数据重定位的难题。还以上例说明，假如上述指令块被操作系统映射在0x500000处那么代码及其在内存中的地址将变为：
501000:
mov eax,dword ptr [402035]
......
502035:
db "hello world!",0

　　显然，mov指令引用的操作数地址是不正确的，如果我们知道了mov指令运行时地址是0x501000，那么计算该地址和编译时该指令预设地址的差值：0x501000-0x401000 = 0x100000。很显然指令引用的实际数据地址应该为0x402035+0x100000 = 0x502035。从上例可以看出，只要能够在运行时确定某条指令动态运行时的地址，而其编译时地址已知，我们就能够通过将delta offset加到相应的地址上正确重定位任何代码或数据的运行时地址。原理如图4所示：

图4 delta iffset

通常只要在病毒代码的开始计算出delta offset，通过变址寻址的方式书写引用数据的汇编代码，即可保证病毒代码在运行时被正确重定位。假设ebp包含了delta offset，使用如下变址寻址指令则可保证在运行时引用的数据地址是正确的：
;ebp包含了delta offset值
401000:
mov eax,dword ptr [ebp+0x402035]
......
402035:
db "hello world!",0
在书写源程序时可以采用符号来代替硬编码的地址值，上述的例子中给出的不过是编译器对符号进行地址替换后的结果。现在的问题就转换成如何获取delta offset的值了，显然：
call delta
delta:
pop ebp
sub ebp,offset delta
在运行时就动态计算出了delta offset值，因为call要将其后的第一条指令的地址压入堆栈，因此pop ebp执行完毕后ebp中就是delta的运行时地址，减去delta的编译时地址“offset delta”就得到了delta offset的值。除了用明显的call指令外，还可以使用不那么明显的fstenv、fsave、fxsave、fnstenv等浮点环境保存指令进行，这些指令也都可以获取某条指令的运行时地址。以fnstenv为例，该指令将最后执行的一条FPU指令相关的协处理器的信息保存在指定的内存中，结构如下图5所示：

图5 浮点环境块的结构

该结构偏移12字节处就是最后执行的浮点指令的运行时地址，因此我们也可以用如下一段指令获取delta offset：
fpu_addr:
fnop
call GetPhAddr
sub ebp,fpu_addr

GetPhAddr:
sub esp,16
fnstenv [esp-12]
pop ebp
add esp,12
ret

　　delta offset也不一定非要放在ebp中，只不过是ebp作为栈帧指针一般过程都不将该寄存器用于其它用途，因此大部分病毒作者都习惯于将delta offset保存在ebp中，其实用其他寄存器也完全可以。
　　在优化过的病毒代码中并不经常直接使用上述直接计算delta offset的代码，比如在Elkern开头写成了类似如下的代码：
call _start_ip
_start_ip:
pop ebp
;...
;使用
call [ebp+addrOpenProcess-_start_ip]
;...
addrOpenProcess dd 0
;而不是
call _start_ip
_start_ip:
pop ebp
sub ebp,_start_ip
call [ebp+addrOpenProcess]

　　为什么不采用第二种书写代码的方式？其原因在于尽管第一种格式在书写源码时显得比较罗嗦，但是addrOpenProcess-_start_ip是一个较小相对偏移值，一般不超过两个字节，因此生成的指令较短，而addrOpenProcess在32 Win32编译环境下一般是4个字节的地址值，生成的指令也就较长。有时对病毒对大小要求很苛刻，更多时候也是为了显示其超俗的编程技巧，病毒作者大量采用这种优化，对这种优化原理感兴趣的读者请参阅Intel手册卷2中的指令格式说明。

* API函数地址的获取

在能够正确重定位之后，病毒就可以运行自己代码了。但是这还远远不够，要搜索文件、读写文件、进行进程枚举等操作总不能在有Win32 API的情况下自己用汇编完全重新实现一套吧，那样的编码量过大而且兼容性很差。Win9X/NT/2000/XP/2003系统都实现了同一套在各个不同的版本上都高度兼容的Win32 API，因此调用系统提供的Win32 API实现各种功能对病毒而言就是自然而然的事情了。
　　所以接下来要解决的问题就是如何动态获取Win32 API的地址。最早的PE病毒采用的是预编码的方法，比如Windows 2000中CreateFileA的地址是0x7EE63260，那么就在病毒代码中使用call [7EE63260h]调用该API，但问题是不同的Windows版本之间该API的地址并不完全相同，使用该方法的病毒可能只能在Windows 2000的某个版本上运行。因此病毒作者自然而然地回到PE结构上来探求解决方法，我们知道系统加载PE文件的时候，可以将其引入的特定DLL中函数的运行时地址填入PE的引入函数表中，那么系统是如何为PE引入表填入正确的函数地址的呢？答案是系统解析引入DLL的导出函数表，然后根据名字或序号搜索到相应引出函数的的RVA（相对虚拟地址），然后再和模块在内存中的实际加载地址相加，就可以得到API函数的运行时真正地址。在研究操作系统是如何实现动态PE文件链接的过程中，病毒作者找到了以下两种解决方案：

A)在感染PE文件的时候，可以搜索宿主的函数引入表的相关地址，如果发现要使用的函数已经被引入，则将对该API的调用指向该引入表函数地址，若未引入，则修改引入表增加该函数的引入表项，并将对该API的调用指向新增加的引入函数地址。这样在宿主程序启动的时候，系统加载器已经把正确的API函数地址填好了，病毒代码即可正确地直接调用该函数。

B）系统可以解析DLL的导出表，自然病毒也可以通过这种手段从DLL中获取所需要的API地址。要在运行时解析搜索DLL的导出表，必须首先获取DLL在内存中的真实加载地址，只有这样才能解析从PE的头部信息中找到导出表的位置。应该首先解析哪个DLL呢？我们知道Kernel32.DLL几乎在所有的Win32进程中都要被加载，其中包含了大部分常用的API，特别是其中的LoadLibrary和GetProcAddress两个API可以获取任意DLL中导出的任意函数，在迄今为止的所有Windows平台上都是如此。只要获取了Kernel32.DLL在进程中加载的基址，然后解析Kernel32.DLL的导出表获取常用的API地址，如需要可进一步使用Kernel32.DLL中的LoadLibrary和GetProcAddress两个API更简单地获取任意其他DLL中导出函数的地址并进行调用。

* 获取Kernel32.DLL基址

　　获取Kernel32.DLL基址的方法很多，最常见的一种是搜索法，如果已知Kernel32.DLL加载的大致地址，那么可由该地址向高地址或低地址进行搜索可以找到其基址。另外一种方法是搜索NT PEB结构中的模块列表获取Kernel32.DLL的准确加载基址。下面看一下具体的实现代码：

方法1：暴力搜索获取Kernel32.DLL的基址

最初的病毒是指定一个大致的加载地址，比如根据实验在9X下其加载地址是0xBFF70000；在Windows 2000下加载基址是0x77E80000；在XP和2003下其加载基址是0x77E60000，因此在NT系统下就可以从0x77e00000开始向高地址搜索，在9X下可以从0xBFF00000开始向高地址搜索，如果搜索到Kernel32.DLL的加载地址，其头部一定是“MZ”标志，由模块起始偏移0x3C的双字确定的PE头部标志必然是“PE”标志，因此可根据这两个标志判断是否找到了模块加载地址，也许有人认为该方法不可靠，因为如果恰好有某段数据符合这两个特征，那么找到的基址可能就是错误的，但经实验证明，该判断方法非常可靠，基本不会出现错误。有一点需要注意的是，在所有版本的Windows系统下Kernel32.DLL的加载基址都是按照0x10000对齐的，根据这一特点可以不必逐字节搜索，按照64K对齐的边界地址搜索即可。
从大致的一个地址开始搜索Kernel32.DLL基址可能会出现读写到未映射内存区域的情况，因此需要和SEH配合使用。如果有在各个版本下准确获取Kernel32.DLL中某地址的通用方法，那么就可以更可靠地从该地址开始向低地址搜索，显然会更加通用。事实上，这种方法是存在的。在系统加载PE文件跳转到PE入口点第一条指令的时候，堆栈顶保存的就是Kernel32.DLL中的某个地址，Elkern中采用的就是这种方法：
_start:
pushfd ;If some flags,especial DF,changed,some APIs can crash down!!!
pushad
_start_@1 equ $
;......
mov ebx,[esp+9*4] ;前面已经由pushfd和pushad压入了9个双字
and ebx,0ffe00000h ;该地址为Kernel32.dll模块下方的某个地址
　　　　　　　　　　　　　　　　;先减去0x100000确保该地址处于Kernel32.dll的下方
　　　　　　　　　　　　　　　　;向高地址搜索如果将来Windows的发行版本中Kernel32.dll
　　　　　　　　　　　　　　　　;大小和代码结构发生变化，该方法可能无效

　　ebx中现在已经是Kernel32.DLL基址之前某个地址了，后续代码可以向高地址搜索其基址。该方法有一个缺点，就是必须明确知道程序入口的堆栈指针值，或间接可计算出该值，对于那些在程序入口获取控制权的病毒代码而言，是可以的，但对于采用EPO技术的病毒而言，该方法则不适用。事实上还有另外一种更加通用的方法，我们知道在Win32程序执行过程中fs段寄存器的基址总是指向进程的TEB，TEB的第一个成员指向SEH链表，该链表每个节点都是一个EXCEPTION_REGISTRATION结构，该结构定义如下：
struct EXCEPTION_REGISTRATION{
struct EXCEPTION_REGISTRATION *prev;
void* handler;
};
在Windows下SEH链表最后一个成员的handler指向Kernel32.DLL中函数UnhandledExceptionFilter的起始地址，利用这一特性我们可以写出更通用的代码：
xor esi,esi
lods dword [fs:esi];取得SEH链表的头指针
@@:
inc eax ;是否是最后一个SEH节点，检查prev是否为0xFFFFFFFF
je @F
dec eax
xchg esi,eax
LODSD ;下一个SEH节点
jmp near @B
@@:
LODSD ;取得Kernel32.dll中UnhandledExceptionFilter的地址

在有的病毒直接以0x7FFDE000作为TEB的指针值，其原因在于在Windows 2003 SP1、Windows XP SP2以前的NT类系统上，该值是固定的，这样的确可以节省一两个字节。但是在Windows 2003 SP1、Windows XP SP2中，情况已经发生了变化，出于安全性的考虑，Windows系统开始动态映射TEB了，也就是说，指向TEB的指针值不再固定，因此这种硬编码的方法也就走到了尽头。此时可以按照前面的方法向低地址搜索判断直到找到Kernel32.dll的基址为止。Elkern中判断是否找到了Kernel32.dll基址的相关代码如下：
search_api_addr_@1:
add ebx,10000h
jz short search_api_addr_seh_restore
cmp word ptr [ebx],'ZM' ;是否是MZ标志
jnz short search_api_addr_@1
mov eax,[ebx+3ch]
add eax,ebx
cmp word ptr [eax],'EP' ;是否具有PE标志
jnz short search_api_addr_@1
;找到了kernel32.dll的基址

方法2：搜索PEB的相关结构获取Kernel32.DLL的基址

前述TEB偏移0x30处，亦即FS:[0x30]地址处保存着一个重要的指针，该指针指向PEB（进程环境块），PEB成员很多，这里并不介绍PEB的详细结构。我们只需要知道PEB结构的偏移0xC处保存着另外一个重要指针ldr，该指针指向PEB_LDR_DATA结构：
typedef struct _PEB_LDR_DATA
{

ULONG Length; // +0x00
BOOLEAN Initialized; // +0x04
PVOID SsHandle; // +0x08
LIST_ENTRY InLoadOrderModuleList; // +0x0c
LIST_ENTRY InMemoryOrderModuleList; // +0x14
LIST_ENTRY InInitializationOrderModuleList;// +0x1c
} PEB_LDR_DATA,*PPEB_LDR_DATA; // +0x24
　　该结构的后三个成员是指向LDR_MODULE链表结构中相应三条双向链表头的指针，分别是按照加载顺序、在内存中的地址顺序和初始化顺序排列的模块信息结构的指针。LDR_MODULE结构如下所示：
typedef struct _LDR_MODULE
{
LIST_ENTRY InLoadOrderModuleList; // +0x00
LIST_ENTRY InMemoryOrderModuleList; // +0x08
LIST_ENTRY InInitializationOrderModuleList; // +0x10
PVOID BaseAddress; // +0x18
PVOID EntryPoint; // +0x1c
ULONG SizeOfImage; // +0x20
UNICODE_STRING FullDllName; // +0x24
UNICODE_STRING BaseDllName; // +0x2c
ULONG Flags; // +0x34
SHORT LoadCount; // +0x38
SHORT TlsIndex; // +0x3a
LIST_ENTRY HashTableEntry; // +0x3c
ULONG TimeDateStamp; // +0x44
// +0x48
} LDR_MODULE, *PLDR_MODULE;

　　Peb->Ldr->InInitializationOrderModuleList指向按照初始化顺序排序的第一个LDR_MODULE节点的InInitializationOrderModuleList成员的指针，在WinNT平台（不包含Win9X）下，该链表头节点的LDR_MODULE结构包含的是NTDLL.DLL的相关信息，而链表的下一个节点所包含的就是Kernel32.dll相关的信息了，该节点LDR_MODULE结构中的BaseAddress不正是我们所苦苦寻找的吗。注意InInitializationOrderModuleList是LDR_MODULE的第3个成员，因此要获取BaseAddress的地址，只需将其指针加8再derefrence即可。因此下面的汇编代码即可获取Kernel32.DLL的基址：

mov eax, dword ptr fs:[30h] ;获取PEB基址
mov eax, dword ptr [eax+0ch] ;获取PEB_LDR_DATA结构指针
mov esi, dword ptr [eax+1ch]
;获取InInitializationOrderModuleList链表头第一个LDR_MODULE节点
InInitializationOrderModuleList成员的指针
lodsd ;获取双向链表当前节点后继的指针
mov ebx, dword ptr [eax+08h] ;取其基地址，该结构当前包含的是
　　　　　　　　　　　　　　　　　　　　　;kernel32.dll相关的信息

该方法在所有的Windows NT（包括Windows 2003 SP1和Windows XP SP2）操作系统上都是有效的，唯一的缺憾是由于PEB结构不同，该方法在Win9X系统上无效。听起来可能比较费解，还是用一张图更加清晰一些：

图6 利用PEB搜索kernel32.dll基地址的过程

* 解析PE文件的导出函数表

　　PE文件的函数导出机制是进行模块间动态调用的重要机制，对于正常的程序，相关操作是由系统加载器在程序加载前自动完成的，对用户程序是透明的。但要想在病毒代码中实现函数地址的动态解析以取代加载器，那就有必要了解函数导出表的结构了。在图1中可以看到在PE头结构IMAGE_OPTIONAL_HEADER32结构中包含一个DataDirectory数组结构，该结构包含16个成员，每个成员都是一个IMAGE_DATA_DIRECTORY结构：
　　typedef struct _IMAGE_DATA_DIRECTORY {
　　 DWORD VirtualAddress;
　　 DWORD Size;
　　} IMAGE_DATA_DIRECTORY, *PIMAGE_DATA_DIRECTORY;
　　DataDirectory数组的每个结构都指向一个重要的数据结构，第一个成员指向导出函数表（索引0），第2个成员指向PE文件的引入函数表（索引1）。DataDirectory中的第一个成员指向导出函数表的IMAGE_EXPORT_DIRECTORY结构：
typedef struct _IMAGE_EXPORT_DIRECTORY {
DWORD Characteristics;
DWORD TimeDateStamp;
WORD MajorVersion;
WORD MinorVersion;
DWORD Name;
DWORD Base;
DWORD NumberOfFunctions;
DWORD NumberOfNames;
DWORD AddressOfFunctions; // RVA from base of image
DWORD AddressOfNames; // RVA from base of image
DWORD AddressOfNameOrdinals; // RVA from base of image
} IMAGE_EXPORT_DIRECTORY, *PIMAGE_EXPORT_DIRECTORY;
AddressOfFunctions是一个双字数组，包含了所有导出函数的RVA，另外两个成员AddressOfNames也是一个双字数组，包含了指向导出函数名字的字符串的RVA，AddressOfNameOrdinals是一个字数组（16bit），和AddressOfNames数组是并行的，和AddressOfNames数组一起确定了相应引出函数的序号，该序号可直接用于索引AddressOfFunctions数组获取导出函数的地址。因此病毒搜索指定的API就包含了如下步骤：

a)获取NumberOfNames的值以及AddressOfNames、AddressOfNameOrdinals和AddressOfFunctions的数组的地址。
b)搜索AddressOfNames数组，按字符串对比，若找到相应的API，转d
c)若NumberOfNames名字尚未全部搜索完毕，转b继续搜索，若搜索完毕，则表明未找到进行错误处理，这一步通常可以省略，因为我们已经知道相应的DLL中肯定导出了相应的函数。
d）获取当前函数名字指针在AddressOfNames数组中的索引，在AddressOfNameOrdinals数组中取出以该值索引的函数序号，以该序号值作为AddressOfFunctions数组的索引，在AddressOfFunctions数组中取出导出函数的RVA值，加上基址就得到了运行时导出函数的地址。

看起来似乎比较罗嗦，实际上这是PE设计时为考虑灵活性而做出的牺牲。不过实现起来还是比较简单的，通常汇编代码编译后不到100字节。以下是在Kernel32搜索GetProcAddress的完整代码：

push esi
;esi=VA Kernel32.BASE
;edi=RVA K32.pehdr
mov ebp,esi
mov edi,[ebp+edi+peh.DataDirectory]

push edi esi

mov eax,[ebp+edi+peexc.AddressOfNames]
mov edx,[ebp+edi+peexc.AddressOfNameOrdinals]
call @F
db "GetProcAddress",0
@@:
pop edi
mov ecx,15
sub eax,4
next_:
add eax,4
add edi,ecx
sub edi,15
mov esi,[ebp+eax]
add esi,ebp
mov ecx,15
repz cmpsb ;进行字符串比较，判断是否为要查找的函数
jnz next_

pop esi edi

sub eax,[ebp+edi+peexc.AddressOfNames]
shr eax,1
add edx,ebp
movzx eax,word [edx+eax]
add esi,[ebp+edi+peexc.AddressOfFunctions]
add ebp,[esi+eax*4] ;ebp=Kernel32.GetProcAddress.addr
;use GetProcAddress and hModule to get other func
pop esi ;esi=kernel32 Base
在前面解析导出函数表获取API地址的时候，采用的是直接比较字符串的方法判断是不是找到了相应的API，其实还可以计算函数名字的hash，然后同预计算的hash进行比对，现代的PE病毒更多采用的hash的方法，其原因在于一般的函数名字长度都大于4字节，而用hash只要占用4个字节或2个字节，可以节省空间，此外还有抗病毒分析的作用，因为hash要比字符串名字费解得多。hash算法的设计只要能保证无冲突即可，可以用crc等成熟算法，也可以设计自己的简单算法。在Elkern中就使用了crc16算法。

static: 当static用来修饰全局变量时，它就改变了全局变量的作用域，使其不能被别的程序extern，限制在了当前文件里，当依然存放在全局存储区。

两种用途：

1，  宏观性统计变量。（全局统计时）

2，  减少局部数组建立和赋值的开销。（经常调用时）

const

用途：

1，  修饰输入参数：①对于非内部数据类型的输入参数，应该将“值传递”的方式改为“const引用传递”，目的是提高效率，e.g.  void Fun(A a)改为void Func(const A &a)。 ②对于内部数据类型的输入参数，不要将“值传递”的方式改为“const引用传递”，否则提高不了效率反而降低了函数可读性。e.g. void Fun(int x) 不要改为 void Fun(const int &x)。

2，  修饰函数返回结果：①以“指针传递”方式的函数返回值加const修饰，那么函数返回值的内容不能被修改，该返回值只能被赋给加const修饰的同类型指针。e.g. const char *str=getstring(); ②若函数返回值采用“值传递方式”，由于函数会把返回值复制到外部临时的存储单元中，加const修饰没有任何价值。③const成员函数的声明中，const关键字只能放在函数声明的尾部，表示该类成员不修改对象。

3，  Extern意味着“外来的”，它的作用在于告诉编译器：有这个变量，它可能不存在当前的文件中，但肯定存在于工程的其他文件中。

register: 这个关键字命令编译器尽可能的将变量存在CPU内部寄存器中而不是通过内存寻址访问以提高效率。

解决方法：重载‘=’操作符，并在函数中重新new空间，以方便析构函数释放。

e.g.

sample &operator=(sample &s)

{

delete p;  //清除原来的指针

p=new char[strlen(s.p)+1];//重新申请指针及空间

strcpy(p,s.p);//拷贝构造过程

return *this;

}

    SDK是Software Development Kit的缩写，中文意思是“软件开发工具包”。这是一个覆盖面相当广泛的名词，可以这么说：辅助开发某一类软件的相关文档、范例和工具的集合都可以叫做“SDK”。具体到我们这个系列教程，我们后面只讨论广义 SDK 的一个子集——即开发 Windows 平台下的应用程序所使用的 SDK。

    其实上面只是说了一个 SDK 大概的概念而已，理解什么是 SDK 真有这么容易吗？恐怕没这么简单！为了解释什么是 SDK 我们不得不引入 API、动态链接库、导入库等等概念。^_^，不要怕，也就是几个新的名词而已，我也是到了大学快结束的时候才体会到其实学习新知识就是在学习新名词、新概念和新术语。

    首先要接触的是“API”，也就是 Application Programming Interface，其实就是操作系统留给应用程序的一个调用接口，应用程序通过调用操作系统的 API 而使操作系统去执行应用程序的命令（动作）。其实早在 DOS 时代就有 API 的概念，只不过那个时候的 API 是以中断调用的形式（INT 21h）提供的，在 DOS 下跑的应用程序都直接或间接的通过中断调用来使用操作系统功能，比如将 AH 置为 30h 后调用 INT 21h 就可以得到 DOS 操作系统的版本号。而在 Windows 中，系统 API 是以函数调用的方式提供的。同样是取得操作系统的版本号，在 Windows 中你所要做的就是调用 GetVersionEx() 函数。可以这么说，DOS API 是“Thinking in 汇编语言”的，而 Windows API 则是“Thinking in 高级语言”的。DOS API 是系统程序的一部分，他们与系统一同被载入内存并且可以通过中断矢量表找到他们的入口，那么 Windows API 呢？要说明白这个问题就不得不引入我们下面要介绍得这个概念——DLL。

    DLL（又是一个缩写，感觉 IT 这个行业里三字头缩写特别多），即 Dynamic Link Library（动态链接库）。我们经常会看到一些 .dll 格式的文件，这些文件就是动态链接库文件，其实也是一种可执行文件格式。跟 .exe 文件不同的是，.dll 文件不能直接执行，他们通常由 .exe 在执行时装入，内含有一些资源以及可执行代码等。其实 Windows 的三大模块就是以 DLL 的形式提供的（Kernel32.dll，User32.dll，GDI32.dll），里面就含有了 API 函数的执行代码。为了使用 DLL 中的 API 函数，我们必须要有 API 函数的声明（.H）和其导入库（.LIB），函数的原型声明不难理解，那么导入库又是做什么用的呢？我们暂时先这样理解：导入库是为了在 DLL 中找到 API 的入口点而使用的。

    所以，为了使用 API 函数，我们就要有跟 API 所对应的 .H 和 .LIB 文件，而 SDK 正是提供了一整套开发 Windows 应用程序所需的相关文件、范例和工具的“工具包”。到此为止，我们才真正的解释清楚了 SDK 的含义。

    由于 SDK 包含了使用 API 的必需资料，所以人们也常把仅使用 API 来编写 Windows 应用程序的开发方式叫做“SDK 编程”。而 API 和 SDK 是开发 Windows 应用程序所必需的东西，所以其它编程框架和类库都是建立在它们之上的，比如 VCL 和 MFC，虽然他们比起“SDK 编程”来有着更高的抽象度，但这丝毫不妨碍它们在需要的时候随时直接调用 API 函数。

说说SDK

    时下学计算机的大多想学编程，且大部分都是在Windows下工作的，而目前学得最热门的是VC，大多数人一开始就开始学习VC，VC是以C++为语言基础的开发工具，而C++是C语言的扩充，故要学好VC最好是先学好C和C++。

    用VC编写Windows程序有两种：1. Windwos c方式(SDK)，2. C++方式:即对SDK函数进行包装，如VC的MFC,BCB的OWL等。SDK编程就是直接调用Windows的API进行编程，平时人们常说"用 SDK写程序"就是指用Windows的API函数来写程序，API由上千个API函数组成(Win95的API有两千多个)。而MFC是API的封闭，结合面向对象程序设计的继承性和多态性组成一个个的"类"，共由一百多个类组成。尽管MFC比SDK方便，但要深入VC，直接去学MFC却是不明智的选择。只有在熟悉了MFC的运行机制的情况下，才有可能深入下去。所以学VC最好是先学用SDK编写程序，在此期间掌握Windows操作系统的工作原理和各API函数的应用，然后再深入MFC。

编程环境

    我们仍然用VC6的IDE(集成开发环境)来编写SDK程序，启动VC6后选择File菜单的New...选项，在出现的New对话框的Projects标签内选择Win32 Application，然后在Projects Name指定项目的名字，在Location中指定路径后按OK按钮，在出现的对话框中，如果你想要用C语言来写程序可以选择An emtpy project，如果你想创建一个带有WinMain入口函数和普通参数的设定的项目，可以选择A simple Win32 application，如果您想创建一个简单典型的“Hello World!”Win32SDK application应用程序，可以选择A typical "Hello World!" application。确定项目类型后按Finish完成。

    在VC6环境下，你依然可以使用资源编辑器和ClassWizar等工具完成程序的编写。用SDK编写程序关键是能够程序的来龙去脉，当然那样效率会很低，不比VB、PB那么快，任何东西都是有得有失，如你熟悉用SDK写程序后，对MFC会比较容易上手的，关键要熟悉C++的三大特性。

转自：http://blog.chinaunix.net/u1/51097/showart_422616.html

二，死锁预防（排除必要条件中的一个）
1，排除请求和保持
 一次性申请所有的需要的资源，即一次请求。
 缺点：资源独占，利用率低。
2，排除不剥夺
 当二次请求得不到满足时，释放已经占用的资源。
 缺点：增加了系统开销，降低了吞吐率。
3，排除环路等待
 为所有的资源进行线形排队，并赋予不同的序号，所有进程对资源的访问必须严格

按照资源序号递增的次序提出。

三，死锁避免
 银行家算法
四，死锁解除
 按照树的顺序从树根开始，对各子进程的资源剥夺以解除死锁的开销进行评估，不

断评估以选择出代价最小的资源剥夺进程，然后剥夺其资源，解除整个系统的死锁。夺该进程

的资源，使死锁被解除。

特别申明：转载一位大哥的程序
一．算法介绍:
**数据结构:
1.可利用资源向量Available
2.最大需求矩阵Max
3.分配矩阵Allocation
4.需求矩阵Need
  **功能介绍:
模拟实现Dijkstra的银行家算法以避免死锁的出现.分两部分组成:
第一部分:银行家算法(扫描)
1．如果Request<=Need,则转向2;否则,出错
2．如果Request<=Available,则转向3,否则等待
3．系统试探分配请求的资源给进程
4．系统执行安全性算法
第二部分:安全性算法
1.设置两个向量
(1).工作向量:Work=Available(表示系统可提供给进程继续运行所需要的各类资源数目)
(2).Finish:表示系统是否有足够资源分配给进程(True:有;False:没有).初始化为False
2.若Finish[i]=False&&Need<=Work,则执行3;否则执行4(I为资源类别)
3.进程P获得第i类资源,则顺利执行直至完成!并释放资源:
Work=Work+Allocation;
Finish[i]=true;
转2
4.  若所有进程的Finish[i]=true,则表示系统安全;否则,不安全!

二.原代码及注释:
#include<iostream.h>
#include<fstream.h>
#include<stdlib.h>
#include "windows.h"
#define MAX_PROCESS 32              //最大进程数
#define MAX_COURCE 64              //最大资源类别

int MAX_FACT_PROCESS;              //实际总进程数
int MAX_FACT_COURCE;               //实际资源类别数
int Available[MAX_COURCE];                 //可利用资源向量
int Max[MAX_PROCESS][MAX_COURCE];          //最大需求矩阵
int Allocation[MAX_PROCESS][MAX_COURCE];   //分配矩阵
int Need[MAX_PROCESS][MAX_COURCE];         //需求矩阵

int Request_PROCESS;                       //发出请求的进程
int Request_COURCE;                        //被请求资源类别
int Request_COURCE_NEMBER;                 //请求资源数

struct COMP{
int value;
int num;
int next;
};
int flag=0;
void Read_Initiate(void){                             //读入初始化文档
ifstream infile("Initiate.txt");
   if(!infile){
cout<<"不能打开输入文件:"<<"Initiate.txt"<<'\n';
exit(1);
}
cout<<"开始读入初始化文档"<<'\n';
int ch;
int Array[MAX_PROCESS*MAX_COURCE*2];
int num=0;
while(infile>>ch)
    Array[num++]=ch;
num=0;
   MAX_FACT_COURCE=Array[num++];
   for(int j=0;j<MAX_FACT_COURCE;j++)
Available[j]=Array[num++];
   MAX_FACT_PROCESS=Array[num++];
for(int i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
Max[i][j]=Array[num++];
}
infile.close();
}

void Write_Initiate(void){                                  //写入初始化文档(分配资源
ofstream outfile("Initiate.txt");
if(!outfile){
cout<<"不能打开初始化文档："<<'\n';
exit(1);
}
int Array[MAX_PROCESS*MAX_COURCE*2];
int num=0;
Array[num++]=MAX_FACT_COURCE;
   for(int i=0;i<MAX_FACT_COURCE;i++)
Array[num++]=Available[i];
Array[num++]=MAX_FACT_PROCESS;
for(i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Array[num++]=Max[i][j];

num=0;
outfile<<Array[num++]<<" ";
for(i=0;i<MAX_FACT_COURCE;i++)
outfile<<Array[num++]<<" ";
outfile<<'\n'<<Array[num++]<<endl;
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
outfile<<Array[num++]<<" ";
outfile<<endl;
}
DWORD m_delay=3000;
Sleep(m_delay);
outfile.close();
cout<<"修改初始化文档成功!"<<endl;
}

void Allocated_list(void){                         //读入已分配资源列表
ifstream infile("Allocated_list.txt");
   if(!infile){
cout<<"不能打开输入文件:"<<"Allocated_list.txt"<<'\n';
exit(1);
}
cout<<"开始读入已分配资源列表"<<'\n';
int ch,num=0;
int Array[MAX_PROCESS*MAX_COURCE];
while(infile>>ch)
Array[num++]=ch;
num=0;
for(int i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Allocation[i][j]=Array[num++];
infile.close();
}

void Set_Need(void){                        //设置需求矩阵
cout<<"设置需求矩阵"<<'\n';
for(int i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Need[i][j]=Max[i][j]-Allocation[i][j];
}

void Read_Request(void){                           //读入请求向量
ifstream infile("Request_list.txt");
   if(!infile){
cout<<"不能打开输入文件:"<<"Request_list.txt"<<'\n';
exit(1);
}
   cout<<"开始读入请求向量"<<'\n';
int Array[3];
int num=0,ch;
while(infile>>ch)
    Array[num++]=ch;
   Request_PROCESS=Array[0];
   Request_COURCE=Array[1];
   Request_COURCE_NEMBER=Array[2];
infile.close();
}

void Write_Allocation(void){                         //修改资源分配列表(资源分配)
ofstream outfile("Allocated_list.txt");
if(!outfile){
cout<<"不能打开资源分配列表："<<'\n';
exit(1);
}
for(int i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
outfile<<Allocation[i][j]<<" ";
outfile<<endl;
}
   DWORD m_delay=3000;
Sleep(m_delay);
cout<<"修改资源分配列表成功!"<<endl;
outfile.close();
}

void Allocate_Source(void){                       //开始分配(已通过扫描和安全性检测)
cout<<'\n'<<"开始给第"<<Request_PROCESS<<"个进程分配第"<<Request_COURCE
<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
Write_Initiate();
Write_Allocation();
DWORD m_delay=3000;
Sleep(m_delay);
cout<<'\n'<<"祝贺您，资源分配已成功!"<<endl;
}

void Test_Safty(){                         //安全性检测
cout<<'\n'<<"进入安全性检测!"<<endl;
   int Work[MAX_COURCE];
for(int i=0;i<MAX_FACT_COURCE;i++){
Work[i]=Available[i];
}
   bool Finish[MAX_PROCESS][MAX_COURCE];
for(i=0;i<MAX_FACT_PROCESS;i++)
for(int j=0;j<MAX_FACT_COURCE;j++)
Finish[i][j]=false;
COMP Array[32];
for(i=0;i<MAX_FACT_PROCESS;i++)
{
Array[i].value=Need[i][Request_COURCE-1];
       Array[i].num=i;
}
for(i=0;i<MAX_FACT_PROCESS;i++)
for(int j=i+1;j<MAX_FACT_PROCESS;j++){
if(Array[i].value>=Array[j].value){
int t;
t=Array[j].value;
               Array[j].value=Array[i].value;
Array[i].value=t;
t=Array[j].num;
               Array[j].num=Array[i].num;
               Array[i].num=t;
}
else continue;
}
DWORD m_delay=3000;
Sleep(m_delay);
/*for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Need[i][j]<<'\t';
cout<<endl;
}
*/
if(Finish[Request_PROCESS-1][Request_COURCE-1]==false&&Need[Request_PROCESS-1][Request_COURCE-1]<=Work[Request_COURCE-1])
{
Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Request_PROCESS-1][Request_COURCE-1];
       Finish[Request_PROCESS-1][Request_COURCE-1]=true;
}
else
{
cout<<"未通过安全性测试，不与以分配"<<endl;
exit(0);
}
   for(i=0;i<MAX_FACT_PROCESS;i++){
if(Array[i].num==Request_PROCESS-1)
continue;
if(Array[i].num!=Request_PROCESS-1&&Finish[Array[i].num][Request_COURCE-1]==false&&Need[Array[i].num][Request_COURCE-1]<=Work[Request_COURCE-1]){
Work[Request_COURCE-1]=Work[Request_COURCE-1]+Allocation[Array[i].num][Request_COURCE-1];
               Finish[Array[i].num][Request_COURCE-1]=true;
}
}
   for(i=0;i<MAX_FACT_PROCESS;i++)
{
if(Finish[i][Request_COURCE-1]==true)
continue;
else
{
cout<<"未通过安全性测试，不与以分配"<<endl;
   exit(0);
}
}
cout<<'\n'<<"找到一个安全序列:"<<"P"<<Request_PROCESS<<"--->";
   for(i=0;i<MAX_FACT_PROCESS;i++){
if(Array[i].num==Request_PROCESS)
continue;
else
cout<<"P"<<Array[i].num<<"--->";
}
cout<<'\n'<<"已通过安全性测试!"<<endl;
Allocate_Source();
}

void RUN(void){                                        //执行银行家算法

   cout<<"*************************************************"<<'\n'<<"点击1执行!"
<<'\n'<<"点击2退出!"
<<'\n'<<"*************************************************"<<endl;
cin>>flag;
if(flag==2)
exit(0);
if(flag==1)
{
cout<<"开始扫描请求信息!"<<endl;
DWORD m_delay=3000;
Sleep(m_delay);
if(Request_COURCE_NEMBER>Need[Request_PROCESS-1][Request_COURCE-1])
{
cout<<'\n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
       cout<<"可是已超出该进程尚需的该类资源的最大数量,所以不予以分配!!"<<endl;
exit(0);
}
if(Request_COURCE_NEMBER>Available[Request_COURCE-1])
{
cout<<'\n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
       cout<<"可是系统中尚无足够的资源,所以进入等待队列!!"<<endl;
exit(0);
}
   else{
Available[Request_COURCE-1]=Available[Request_COURCE-1]-Request_COURCE_NEMBER;
       Allocation[Request_PROCESS-1][Request_COURCE-1]=Allocation[Request_PROCESS-1][Request_COURCE-1]+Request_COURCE_NEMBER;
       Need[Request_PROCESS-1][Request_COURCE-1]=Need[Request_PROCESS-1][Request_COURCE-1]-Request_COURCE_NEMBER;
cout<<"扫描通过"<<endl;
Sleep(m_delay);
Test_Safty();
}
}
else {
cout<<"输入错误,请重新输入!"<<'\n';
RUN();
}
}

void main(void){
   Read_Initiate();
cout<<MAX_FACT_COURCE<<'\t';
for(int i=0;i<MAX_FACT_COURCE;i++)
cout<<Available[i]<<'\t';
cout<<endl<<MAX_FACT_PROCESS<<endl;
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Max[i][j]<<'\t';
cout<<endl;
}
DWORD m_delay=3000;
Sleep(m_delay);
cout<<"读入成功"<<'\n';

Allocated_list();
for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Allocation[i][j]<<'\t';
cout<<endl;
}
Sleep(m_delay);
cout<<"读入成功"<<'\n';

Set_Need();
   for(i=0;i<MAX_FACT_PROCESS;i++){
for(int j=0;j<MAX_FACT_COURCE;j++)
cout<<Need[i][j]<<'\t';
cout<<endl;
}
   Sleep(m_delay);
cout<<"设置成功"<<'\n';

   Read_Request();
cout<<'\n'<<"第"<<Request_PROCESS<<"个进程请求第"<<Request_COURCE<<"类资源"<<Request_COURCE_NEMBER<<"个"<<endl;
cout<<'\n'<<"读入成功"<<'\n';

RUN();
}

三．数据测试
注:数组Array[I]表示第I+1个实际意义量
     需要创建三个txt文本。
1.Initiate.txt文本
3 3 3 2      //共有3类资源,Available[0]=3; Available[1]=3; Available[2]=2
5             //当前系统中有个进程
7 5 3         // Max[0][0]=7
3 2 2          //Max[1][1]=3
9 0 2
2 2 2
4 3 3
2.Allocated_list.txt文本
0 1 0         //Allocation[0][1]=1
2 0 0
3 0 2
2 1 1
0 0 2
3.Request_list.txt文本
2 1 1       //第2个进程请求第1类资源1个Request[1][0]=1
四．程序说明:
本程序假设当前时刻只有一个进程请求某一类资源n个.
若要满足某个进程当前时刻同时请求不止一类资源,则需要为最大需求矩阵Max,分配矩阵Allocation和需求矩阵Need增加维数,当然代码量也将大大增加,但是算法逻辑本身并无变化.

}

1, a是一个数组，所以a为地址，即0x12ff7c，所以%c输出时为将该地址当成单个字符处理，即对地位的0x7c以%c格式输出，即输出“|”(因为|的ASCII码是0x7C)。
2, b是一个字符，所以b在内存中为b的ASCII码98，所以很好理解为什么输出的是98 和b。
3, c是一个数字，0x7c为低位，所以输出0x7c的ASCII码"|"。
4, 最后四个为将字符串以%c的格式输出，输出为“？”，不知道该如何理解。。。。。。

5，aa和ba一个是8进制一个是16进制。

1)例子一:

f(n) = 　n + １;       (n <２)　
        　　　　 f[n/2] + f[n/4](n >;= 2);
        这个例子相对简单一些,递归程序如下:
        int     f_recursive(int n)
        {
               int u1, u2, f;
               if (n < 2)
                       f = n + 1;
               else {
                       u1 = f_recursive((int)(n/2));
                       u2 = f_recursive((int)(n/4));
                       f = u1 * u2;                                                              
               }
               return f;
        }

下面按照我们上面说的,确定好递归调用树的结构,这一步是最重要的.首先,什么是叶子结点
,我们看到当n < 2时f = n + 1,这就是返回的语句,有人问为什么不是f = u1 * u2,这也是一个
返回的语句呀?答案是:这条语句是在u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))之后
执行的,是这两条语句的父结点. 其次,什么是当前结点,由上面的分析,f = u1 * u2即是父结点
.然后,顺理成章的u1 = exmp1((int)(n/2))和u2 = exmp1((int)(n/4))就分别是左子树和右子
树了.最后,我们可以看到,这个递归函数可以表示成后序遍历的二叉调用树.好了,树的情况分析
到这里,下面来分析一下栈的情况,看看我们要把什么数据保存在栈中,在上面给出的后序遍历的如果这个过程你没
非递归程序中我们已经看到了要加入一个标志域,因此在栈中要保存这个标志域;另外,u1,u2和
每次调用递归函数时的n/2和n/4参数都要保存,这样就要分别有三个栈分别保存:标志域,返回量
和参数,不过我们可以做一个优化,因为在向上一层返回的时候,参数已经没有用了,而返回量也
只有在向上返回时才用到,因此可以把这两个栈合为一个栈.如果对于上面的分析你没有明白,建
议你根据这个递归函数写出它的递归栈的变化情况以加深理解,再次重申一点:前期对树结构和
栈的分析是最重要的,如果你的程序出错,那么请返回到这一步来再次分析,最好把递归调用树和
栈的变化情况都画出来,并且结合一些简单的参数来人工分析你的算法到底出错在哪里.
ok,下面给出我花了两天功夫想出来的非递归程序(再次提醒你不要气馁,大家都是这么过来
的).

int     f_nonrecursive(int n)
        {
               int stack[20], flag[20], cp;

                       
               /* 初始化栈和栈顶指针 */
               cp = 0;
               stack[0] = n;
               flag[0] = 0;
               while (cp >;= 0) {
                       switch(flag[cp]) {
                       case 0:                        /* 访问的是根结点 */
                               if (stack[cp] >;= 2) { /* 左子树入栈 */
                                      flag[cp] = 1; /* 修改标志域 */
                                      cp++;
                                      stack[cp] = (int)(stack[cp - 1] / 2);
                                      flag[cp] = 0;
                               } else {               /* 否则为叶子结点 */
                                      stack[cp] += 1;
                                      flag[cp] = 2;
                               }
                               break;
                       case 1:                        /* 访问的是左子树 */
                               if (stack[cp] >;= 2) { /* 右子树入栈 */
                                      flag[cp] = 2; /* 修改标志域 */
                                      cp += 2;
                                      stack[cp] = (int)(stack[cp - 2] / 4);
                                      flag[cp] = 1;
                               } else {               /* 否则为叶子结点 */
                                      stack[cp] += 1;
                                      flag[cp] = 2;
                               }
                               break;
                       case 2:                        /* */
                               if (flag[cp - 1] == 2) { /* 当前是右子树吗? */
                                      /*
                                       * 如果是右子树, 那么对某一棵子树的后序遍历已经
                                       * 结束,接下来就是对这棵子树的根结点的访问
                                       */
                                      stack[cp - 2] = stack[cp] * stack[cp - 1];
                                      flag[cp - 2] = 2;
                                      cp = cp - 2;
                               } else
                                      /* 否则退回到后序遍历的上一个结点 */
                                      cp--;
                               break;
                       }
               }
               return stack[0];
        }

算法分析:a)flag只有三个可能值:0表示第一次访问该结点,1表示访问的是左子树,2表示
已经结束了对某一棵子树的访问,可能当前结点是这棵子树的右子树,也可能是叶子结点.b)每
遍历到某个结点的时候,如果这个结点满足叶子结点的条件,那么把它的flag域设为2;否则根据
访问的是根结点,左子树或是右子树来设置flag域,以便决定下一次访问该节点时的程序转向.

2)例子二

快速排序算法
递归算法如下:

void    swap(int array[], int low, int high)
        {
               int temp;
               temp = array[low];
               array[low] = array[high];
               array[high] = temp;
        }
        int     partition(int array[], int low, int high)
        {
               int     p;
               p = array[low];
               while (low < high) {
                       while (low < high && array[high] >;= p)
                               high--;
                       swap(array,low,high);
                       while (low < high && array[low]  <= p)
                               low++;
                       swap(array,low,high);
               }
               return low;
        }

        void    qsort_recursive(int array[], int low, int high)
        {
               int p;
               if(low < high) {
                       p = partition(array, low, high);
                       qsort_recursive(array, low, p - 1);
                       qsort_recursive(array, p + 1, high);
               }
        }

需要说明一下快速排序的算法: partition函数根据数组中的某一个数把数组划分为两个部分,
左边的部分均不大于这个数,右边的数均不小于这个数,然后再对左右两边的数组再进行划分.这
里我们专注于递归与非递归的转换,partition函数在非递归函数中同样的可以调用(其实
partition函数就是对当前结点的访问).
再次进行递归调用树和栈的分析:
递归调用树:a)对当前结点的访问是调用partition函数;b)左子树:
qsort_recursive(array, low, p - 1);c)右子树:qsort_recursive(array, p + 1, high);
d)叶子结点:当low < high时;e)可以看出这是一个先序调用的二叉树
栈:要保存的数据是两个表示范围的坐标.

void    qsort_nonrecursive(int array[], int low, int high)
        {
               int m[50], n[50], cp, p;
               /* 初始化栈和栈顶指针 */
               cp = 0;
               m[0] = low;
               n[0] = high;
               while (m[cp] < n[cp]) {
                       while (m[cp] < n[cp]) {        /* 向左走到尽头 */
                               p = partition(array, m[cp], n[cp]); /* 对当前结点的访问 */
                               cp++;
                               m[cp] = m[cp - 1];
                               n[cp] = p - 1;
                       }
                       /* 向右走一步 */
                       m[cp + 1] = n[cp] + 2;
                       n[cp + 1] = n[cp - 1];
                       cp++;
               }
        }

3)例子三
阿克曼函数:

akm(m, n) = n + 1;                    (m = 0时)
                   akm(m - 1, 1);             (n = 0时)
                   akm(m - 1, akm(m, n - 1)); (m != 0且n != 0时)

递归算法如下:

int     akm_recursive(int m, int n)
        {
               int temp;
               if (m == 0)
                       return (n + 1);
               else if (n == 0)
                       return akm_recursive(m - 1, 1);
               else {
                       temp = akm_recursive(m, n - 1);
                       return akm_recursive(m - 1, temp);
               }
        }

这个例子相对难一些,不过只要正确的分析递归调用树和栈的变化情况就不难解决,先卖个关子,晚上再来公布答案,感兴趣的可以先想想.

好了,让我们回到递归与非递归的世界中,继续未完的旅途.

这道题的难点就是确定递归调用树的情况,因为从akm函数的公式可以看到,有三个递归调用,一般
而言,有几个递归调用就会有几棵递归调用的子树,不过这只是一般的情况,不一定准确,也不一定非要
机械化的这么作,因为通常情况下我们可以做一些优化,省去其中的一些部分,这道题就是一个例子.
递归调用树的分析:a)是当m=0时是叶子结点;b)左子树是akm(m - 1, akm(m, n - 1))调用中的
akm(m, n - 1)调用,当这个调用结束得出一个值temp时,再调用akm(m - 1, temp),这个调用是右子树
.c)从上面的分析可以看出,这个递归调用树是后序遍历的树.
栈的分析:要保存的数据是m, n,当n = 0 或 m = 0时开始退栈,当n = 0时把上一层栈的m值变为
m - 1,n变为1，当m = 0时把上一层栈的m值变为0,n变为n + 1.从这个分析过程可以看出,我们省略了
当n = 0时的akm(m - 1, 1)调用,原来在系统机械化的实现递归调用的过程中,这个调用也是一棵子树,
不过经过分析,我们用修改栈中数据的方式进行了改进.

int     akm_nonrecursive(int m, int n)
        {
               int m1[50], n1[50], cp;
               cp = 0;
               m1[0] = m;
               n1[0] = n;
               do {
                       while (m1[cp] >; 0) {          /* 压栈, 直到m1[cp] = 0 */
                               while (n1[cp] >; 0) { /* 压栈, 直到n1[cp] = 0 */
                                      cp++;
                                      m1[cp] = m1[cp - 1];
                                      n1[cp] = n1[cp - 1] - 1;
                               }
                               /* 计算akm(m - 1, 1),当n = 0时 */
                               m1[cp] = m1[cp] - 1;
                               n1[cp] = 1;
                       }
                       /* 改栈顶为akm(m - 1, n + 1),当m = 0时 */
                       cp--;
                       m1[cp] = m1[cp] - 1;
                       n1[cp] = n1[cp + 1] + 1;
               } while (cp >; 0 || m1[cp] >; 0);
               return n1[0] + 1;
        }
三.递归程序的分类及用途

   递归程序分为两类:尾部递归和非尾部递归.上面提到的几个例子都是非尾部递归,在一个选择分支中有至少

一个的递归调用.相对而言,尾部递归就容易很多了,因为与非尾部递归相比,每个选择分支只有一个递归调用,

我们在解决的时候就不需要使用到栈,只要循环和设置好循环体就可以了.下面再举几个尾部递归的例子吧,比较

简单我就不多说什么了.

   1)例子一

g(m, n) = 0                    (m = 0, n >;= 0)
           = g(m - 1, 2n) + n; (m >; 0, n >;= 0)

          
   a)递归程序
       

int            g_recursive(int m, int n)
        {
               if (m == 0 && n >;= 0)
                       return 0;
               return (g_recurse(m - 1, 2*n) + n);
        }

       
   b)非递归程序

int            g_nonrecursive(int m, int n)
        {
               int p;
               for (p = 0; m >; 0 && n >;= 0; m--, n *= 2)
                       p += n;
               return p;
        }

       
    2)例子二

 f(n) = n + 1 (n = 0)
           n * f(n/2)  (n >; 0)

    a)递归程序
       

int            f_recursive(int n)
        {
               if (n == 0)
                       return 1;
               return (n * f_recurse(n/2));
        }

    b)非递归程序

int     f_nonrecursive(int n)
        {
               int m;
               for (m = 1; n >; 0; n /= 2)
                       m *= n;
               return m++;
        }

      分析完了递归程序的分类,让我们回头看看在向非递归转换的过程中用到了什么来实现转换:

   1)循环,因为程序要在某个条件下一直执行下去,要代替递归程序,循环必不可少,对于尾部递归,循环结束的

     条件十分容易确定,只要按照不同分支的条件写出来就可以了.而对于非尾部递归程序,循环结束的条件一

     般是当栈为空时或者是结束了对递归调用树的遍历从树的根结点退出时,而且有的时候写成while()的形式

     ,有时写成do ...while的形式(如上面的akm函数),具体怎样,很难说清楚,取决于你对整个递归程序的分析

     .

   2)递归调用树,树的结构在转换的过程中是不可见的,你不必为转换专门写一个树结构,不过能不能把递归调用

     中的树遍历方式以及叶子结点,左子树,右子树等元素确定好是你能否正确解决问题的关键(这一点已经在

     上面的分析过程中展露无疑),确定好这些后,剩下的工作大部分就是按照给出的几种不同的遍历树的方式

     把程序进行改写,这个过程就考验你对树结构还有遍历方式是否很好的掌握了(看出基础的重要了吗?如果

     回答是,那么和我一样好好的打好基础吧,一切都还不晚!!).对于尾部递归而言,可以看作没有递归调用树,

     所以尾部递归的难度大大降低了.

   3)栈,非尾部调用中需要栈来保存数据,这一点已经很清楚了,需要注意几个问题:a)栈有时可能会出现不够的

     情况,拿上面的akm函数来说,我用的50个元素的数组,你如果把m和n值设置得大一些,这个栈就不能用了,有

     时你的算法正确了,不过没有注意到这个问题还是会出错的;反过来说,在递归调用中,系统或者编译器的优

     化功能不够好的化,在这个栈上可能会消耗很多空间,这个时候如果你把程序改成非递归的形式,然后再用

     动态分配技术分配栈可能就会把程序的性能提高一大块--这也是我们学习这门技术的意义之一,因为系统

     是机械化的,你如果知道更好的优化办法,为什么不用呢?

   什么时候可以用递归解决问题?到了这一步,如果你对于上面说的已经相当明白的话,这个问题不难回答,如果

   我们要解决的问题要分成几个小的部分,而其中的一些与你要解决的问题是一样的,只不过是问题的规模(如

   参数等)小了,那么这样的问题可以用递归来解决.根据问题设计好一个递归是所有这些的基础,转换也是在原

   来的递归程序上进行的,所以这一步一定要做好.通常,设计一个递归程序要注意一下几个问题:a)可以递归解

   决的问题是什么?b)入口和出口参数是什么--即要明确好出入的接口.

四.学习过程中参考到的一些资料

   1)<<算法导论>;>;  国防科大出版社  张益新 沈雁编著

     这本书比较老了,也许很难找了,不过参考价值不大,里面专门用了一章来讲这个问题,可惜用的是goto来实

     现递归调用的选择分支(所以我说参考价值不大),如果没有也无所谓的.

   2)http://db.pku.edu.cn/mzhang/  北京大学张铭老师的主页.

     上面可以找到一个张老师讲解递归和非递归转换的视频,有大概50多分钟吧,我没有听完,原先看第一本书

     的对于如何不用goto实现选择分支十分不解,张老师讲到的递归调用树真正让我豁然开朗,从此以后虽然还

     是有很多问题,不过明白了这个大体的解决思路就有了.

   3)<<数据结构>;>;  清华大学出版社  严蔚敏著

     这本书讲到栈的时候略微讲到了一些这方面的内容,网上可以找到一位叫一具的仁兄写的这本书的习题解答

     ,可以自己去找一找,我的中序和后序遍历的算法完全看的他写的.
      4) http://www.tztvu.edu.cn/kfjy/bkjy/jsj/bxk/sjjg/kcdh/忘了是什么的网页了
     里面的一个dn5.doc的文件中有讲解转换akm函数的方法,给我的启发很大,如果你对于我说的akm函数还有疑
     问,那么可以看看人家写的,他把递归调用树和栈的变化情况都写出来了,非常直观.

http://www.chinaunix.net 作者:converse 发表于：2006-08-24 09:00:06

原文：http://www.chinaunix.net/jh/23/331522.html
　　　http://blog.csdn.net/dragondwy/archive/2006/06/30/855391.aspx  http://liqunsun.spaces.live.com/blog/cns!285A08B51269F219!114.entry
如何用栈实现递归与非递归的转换

一.为什么要学习递归与非递归的转换的实现方法?
1)并不是每一门语言都支持递归的.
2)有助于理解递归的本质.
3)有助于理解栈,树等数据结构.

二.递归与非递归转换的原理.
递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,
这个"原理"并没有经过严格的数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.
学习过树结构的人都知道,有三种方法可以遍历树:前序,中序,后序.理解这三种遍历方式的递归和非
递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里以特殊的
二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难
了.
1)前序遍历
a)递归方式:

void preorder_recursive(Bitree T)             /* 先序遍历二叉树的递归算法 */
               {

                       if (T) {
                               visit(T);                      /* 访问当前结点 */
                               preorder_recursive(T->;lchild);       /* 访问左子树 */
                               preorder_recursive(T->;rchild);       /* 访问右子树 */
                       }
               }

b)非递归方式

void preorder_nonrecursive(Bitree T)          /* 先序遍历二叉树的非递归算法 */
               {
                       initstack(S);
                       push(S,T);                            /* 根指针进栈 */
                       while(!stackempty(S)) {
                               while(gettop(S,p)&&p) {               /* 向左走到尽头 */
                                      visit(p);              /* 每向前走一步都访问当前结点 */
                                      push(S,p->;lchild);

                               }
                               pop(S,p);
                               if(!stackempty(S)) {           /* 向右走一步 */
                                      pop(S,p);
                                      push(S,p->;rchild);
                               }
                       }
               }

2)中序遍历

a)递归方式

void inorder_recursive(Bitree T)              /* 中序遍历二叉树的递归算法 */
               {
                       if (T) {
                               inorder_recursive(T->;lchild); /* 访问左子树 */
                               visit(T);                      /* 访问当前结点 */
                               inorder_recursive(T->;rchild); /* 访问右子树 */
                       }
               }

b)非递归方式

void  inorder_nonrecursive(Bitree T)
               {
                       initstack(S);                         /* 初始化栈 */
                       push(S, T);                           /* 根指针入栈 */
                       while (!stackempty(S)) {                     
                               while (gettop(S, p) && p)      /* 向左走到尽头 */
                                      push(S, p->;lchild);
                               pop(S,p);                     /* 空指针退栈 */
                               if (!stackempty(S)) {
                                      pop(S, p);
                                      visit(p);              /* 访问当前结点 */
                                      push(S, p->;rchild);   /* 向右走一步 */
                               }
                       }
               }

3)后序遍历

a)递归方式

void postorder_recursive(Bitree T)            /* 中序遍历二叉树的递归算法 */
               {
                  if (T) {
                          postorder_recursive(T->;lchild);   /* 访问左子树 */
                          postorder_recursive(T->;rchild);   /* 访问右子树 */
                          visit(T);                          /* 访问当前结点 */
                  }
               }

b)非递归方式

typedef struct {
                       BTNode* ptr;
                       enum {0,1,2} mark;
               } PMType;                                     /* 有mark域的结点指针类型 */
               void postorder_nonrecursive(BiTree T)         /* 后续遍历二叉树的非递归算法 */
               {
                       PMType a;
                       initstack(S);                         /* S的元素为PMType类型 */

                       push (S,{T,0});                       /* 根结点入栈 */
                       while(!stackempty(S)) {
                               pop(S,a);
                               switch(a.mark)
                               {
                               case 0:
                                      push(S,{a.ptr,1});     /* 修改mark域 */
                                      if(a.ptr->;lchild)
                                              push(S,{a.ptr->;lchild,0}); /* 访问左子树 */
                                      break;
                               case 1:
                                      push(S,{a.ptr,2});     /* 修改mark域 */
                                      if(a.ptr->;rchild)
                                              push(S,{a.ptr->;rchild,0}); /* 访问右子树 */
                                      break;
                               case 2:
                                      visit(a.ptr);          /* 访问结点 */
                               }
                       }
               }

4)如何实现递归与非递归的转换
通常,一个函数在调用另一个函数之前,要作如下的事情:a)将实在参数,返回地址等信息传递
给被调用函数保存; b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口.
从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调
函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.
所有的这些,不论是变量还是地址,本质上来说都是"数据",都是保存在系统所分配的栈中的.
ok,到这里已经解决了第一个问题:递归调用时数据都是保存在栈中的,有多少个数据需要保存
就要设置多少个栈,而且最重要的一点是:控制所有这些栈的栈顶指针都是相同的,否则无法实现
同步.
下面来解决第二个问题:在非递归中,程序如何知道到底要转移到哪个部分继续执行?回到上
面说的树的三种遍历方式,抽象出来只有三种操作:访问当前结点,访问左子树,访问右子树.这三
种操作的顺序不同,遍历方式也不同.如果我们再抽象一点,对这三种操作再进行一个概括,可以
得到:a)访问当前结点:对目前的数据进行一些处理;b)访问左子树:变换当前的数据以进行下一次
处理;c)访问右子树:再次变换当前的数据以进行下一次处理(与访问左子树所不同的方式).
下面以先序遍历来说明:

void preorder_recursive(Bitree T)             /* 先序遍历二叉树的递归算法 */

        {
               if (T) {
                       visit(T);                      /* 访问当前结点 */
                       preorder_recursive(T->;lchild);       /* 访问左子树 */
                       preorder_recursive(T->;rchild);       /* 访问右子树 */
               }
        }

visit(T)这个操作就是对当前数据进行的处理, preorder_recursive(T->;lchild)就是把当前
数据变换为它的左子树,访问右子树的操作可以同样理解了.
现在回到我们提出的第二个问题:如何确定转移到哪里继续执行?关键在于一下三个地方:a)
确定对当前数据的访问顺序,简单一点说就是确定这个递归程序可以转换为哪种方式遍历的树结
构;b)确定这个递归函数转换为递归调用树时的分支是如何划分的,即确定什么是这个递归调用
树的"左子树"和"右子树"c)确定这个递归调用树何时返回,即确定什么结点是这个递归调用树的
"叶子结点".

　　2、有C++特征的C结构

　 　当然了，C++不是复杂的C，C++本质上是面向对象的语言：包含继承、封装，以及多态。原始的C结构经过改造，成了面向对象世界的基石——类。除了成 员变量外，C++类还可以封装成员函数和其他东西。然而，有趣的是，除非为了实现虚函数和虚继承引入的隐藏成员变量外，C++类实例的大小完全取决于一个 类及其基类的成员变量！成员函数基本上不影响类实例的大小。

　　这里提供的B是一个C结构，然而，该结构有一些C++特征：控制成员可见 性的“public/protected/private”关键字、成员函数、静态成员，以及嵌套的类型声明。虽然看着琳琅满目，实际上只有成员变量才占 用类实例的空间。要注意的是，C++标准委员会不限制由“public/protected/private”关键字分开的各段在实现时的先后顺序，因 此，不同的编译器实现的内存布局可能并不相同。（在VC++中，成员变量总是按照声明时的顺序排列）。

　　3、单继承

　 　C++提供继承的目的是在不同的类型之间提取共性。比如，科学家对物种进行分类，从而有种、属、纲等说法。有了这种层次结构，我们才可能将某些具备特定 性质的东西归入到最合适的分类层次上，如“怀孩子的是哺乳动物”。由于这些属性可以被子类继承，所以，我们只要知道“鲸鱼、人”是哺乳动物，就可以方便地 指出“鲸鱼、人都可以怀孩子”。那些特例，如鸭嘴兽（生蛋的哺乳动物），则要求我们对缺省的属性或行为进行覆盖。

　　C++中的继承语法很简单，在子类后加上“:base”就可以了。下面的D继承自基类C。

　　这样的继承将造成怎样的类布局呢？下面我们还是用“字母类”来举例：

 
　 　使用虚继承，比起单继承和多重继承有更大的实现开销、调用开销。回忆一下，在单继承和多重继承的情况下，内嵌的基类实例地址比起派生类实例地址来，要么 地址相同（单继承，以及多重继承的最靠左基类），要么地址相差一个固定偏移量（多重继承的非最靠左基类）。然而，当虚继承时，一般说来，派生类地址和其虚 基类地址之间的偏移量是不固定的，因为如果这个派生类又被进一步继承的话，最终派生类会把共享的虚基类实例数据放到一个与上一层派生类不同的偏移量处。请 看下例：

 

 

成员函数

　　一个C++成员函数只是类范围内的又一个成员。X类每一个非静态的成员函数都会接受一个特殊的隐藏参数—— this指针，类型为X* const。该指针在后台初始化为指向成员函数工作于其上的对象。同样，在成员函数体内，成员变量的访问是通过在后台计算与this指针的偏移来进行。

 

　　1、覆盖成员函数

　 　和成员变量一样，成员函数也会被继承。与成员变量不同的是，通过在派生类中重新定义基类函数，一个派生类可以覆盖，或者说替换掉基类的函数定义。覆盖是 静态（根据成员函数的静态类型在编译时决定）还是动态（通过对象指针在运行时动态决定），依赖于成员函数是否被声明为“虚函数”。

　　Q从P继承了成员变量和成员函数。Q声明了pf()，覆盖了P::pf()。Q还声明了pvf()，覆盖了P::pvf()虚函数。Q还声明了新的非虚成员函数qf()，以及新的虚成员函数qvf()。

　 　为了实现这种机制，引入了隐藏的vfptr成员变量。一个vfptr被加入到类中（如果类中没有的话），该vfptr指向类的虚函数表 （vftable）。类中每个虚函数在该类的虚函数表中都占据一项。每项保存一个对于该类适用的虚函数的地址。因此，调用虚函数的过程如下：取得实例的 vfptr；通过vfptr得到虚函数表的一项；通过虚函数表该项的函数地址间接调用虚函数。也就是说，在普通函数调用的参数传递、调用、返回指令开销 外，虚函数调用还需要额外的开销。

　　回头再看看P和Q的内存布局，可以发现，VC++编译器把隐藏的vfptr成员变量放在P和Q实例 的开始处。这就使虚函数的调用能够尽量快一些。实际上，VC++的实现方式是，保证任何有虚函数的类的第一项永远是vfptr。这就可能要求在实例布局 时，在基类前插入新的vfptr，或者要求在多重继承时，虽然在右边，然而有vfptr的基类放到左边没有vfptr的基类的前面。

　　 许多C++的实现会共享或者重用从基类继承来的vfptr。比如，Q并不会有一个额外的vfptr，指向一个专门存放新的虚函数qvf()的虚函数表。 Qvf项只是简单地追加到P的虚函数表的末尾。如此一来，单继承的代价就不算高昂。一旦一个实例有vfptr了，它就不需要更多的vfptr。新的派生类 可以引入更多的虚函数，这些新的虚函数只是简单地在已存在的，“每类一个”的虚函数表的末尾追加新项。

　　2、多重继承下的虚函数

　　如果从多个有虚函数的基类继承，一个实例就有可能包含多个vfptr。考虑如下的R和S类：

 

 

　　5、虚继承下的虚函数

　 　T虚继承P，覆盖P的虚成员函数，声明了新的虚函数。如果采用在基类虚函数表末尾添加新项的方式，则访问虚函数总要求访问虚基类。在VC++中，为了避 免获取虚函数表时，转换到虚基类P的高昂代价，T中的新虚函数通过一个新的虚函数表获取，从而带来了一个新的虚函数表指针。该指针放在T实例的顶端。

 

  　　在此U增加了一个成员变量，从而改变了P的偏移。因为VC++实现中，T::pvf()接受的是嵌套在T中的P的指针，所以，需要提供一个调整块，把this指针调整到T::t1之后（该处即是P在T中的位置）。

　　6、特殊成员函数

　　本节讨论编译器合成到特殊成员函数中的隐藏代码。

　　6.1 构造函数和析构函数

　　正如我们所见，在构造和析构过程中，有时需要初始化一些隐藏的成员变量。最坏的情况下，一个构造函数要执行如下操作：

　　* 如果是“最终派生类”，初始化vbptr成员变量，调用虚基类的构造函数；

　　* 调用非虚基类的构造函数

　　* 调用成员变量的构造函数

　　* 初始化虚函数表成员变量

　　* 执行构造函数体中，程序所定义的其他初始化代码

　　（注意：一个“最终派生类”的实例，一定不是嵌套在其他派生类实例中的基类实例）

　　所以，如果你有一个包含虚函数的很深的继承层次，即使该继承层次由单继承构成，对象的构造可能也需要很多针对虚函数表的初始化。

　　反之，析构函数必须按照与构造时严格相反的顺序来“肢解”一个对象。

　　* 合成并初始化虚函数表成员变量

　　* 执行析构函数体中，程序定义的其他析构代码
　
　　* 调用成员变量的析构函数（按照相反的顺序）

　　* 调用直接非虚基类的析构函数（按照相反的顺序）

　　* 如果是“最终派生类”，调用虚基类的析构函数（按照相反顺序）

　 　在VC++中，有虚基类的类的构造函数接受一个隐藏的“最终派生类标志”，标示虚基类是否需要初始化。对于析构函数，VC++采用“分层析构模型”，代 码中加入一个隐藏的析构函数，该函数被用于析构包含虚基类的类（对于“最终派生类”实例而言）；代码中再加入另一个析构函数，析构不包含虚基类的类。前一 个析构函数调用后一个。

　　6.2 虚析构函数与delete操作符

　　考虑结构V和W。

 

 
 

Trackback: http://tb.blog.csdn.net/TrackBack.aspx?PostId=763797

String 类的原型如下

class String
{
   public:
          String(const char *str=NULL); //构造函数
          String(const String &other); //拷贝构造函数
          ~String(void); //析构函数
          String& operator=(const String &other); //等号操作符重载

网上看到，感觉讲得很清晰，刚好能解答我上次的笔试题