第2章计算机组织
在本章中，我们检查的组织基本的计算机系统。一个简单的计算机有三个主要的子系统。中央处理单元，或CPU执行许多操作和控制计算机。微处理器通常作为计算机的CPU 。存储器子系统是用来存储由CPU执行的程序，随着程序的数据。输入/输出或I / O子系统，允许CPU与输入和输出设备，如键盘和显示器的个人计算机或本机键盘和数字显示的微波炉。
2.1计算机的基本组织
大多数计算机系统，嵌入式控制器在汽车和家电消费个人电脑和大型机，具有相同的基本组织。这个组织有三个主要部分组成： CPU ，内存子系统和I / O子系统。这些组件在图2-1所示的通用组织。
在本节中，我们首先描述用于将组件连接到在计算机系统中的系统总线。然后我们将研究的指令周期中，发生在计算机内提取，解码，并执行一个指令的操作顺序。
2.1.1系统总线
物理上，总线是一组电线。计算机组件连接到母线。将信息发送到另一个，从一个组件源组件输出数据到总线。目标组件，然后输入该数据从总线。作为一个计算机系统的复杂性增加，它变得更加有效（在最小化连接）使用的每对设备之间的总线，而不是直接连接。巴士在一块电路板上，并使用更少的空间，需要较少的功率比大量的直接连接。它们还需要在芯片上或芯片，包括CPU更少的标签。
在图2-1所示的系统有三个公交车。在该图中最上面的总线是地址总线。当CPU读取数据或指令或写入数据到内存，它必须指定希望访问的内存位置的地址。输出地址的地址总线，存储器的地址总线输入这个地址，并使用它来访问正确的内存位置。每个I / O设备，诸如键盘，显示器，或磁盘驱动器，具有一个唯一的地址。访问I / O设备时， CPU将在地址总线上的设备的地址。每个设备可以读取的地址总线，并确定它是否是被访问的CPU的移动设备。不同于其他总线，地址总线总是接收来自CPU的数据的CPU从不读取地址
1
总线。
数据通过数据总线传输。当CPU从存储器中读取数据时，它首先在它的地址总线的存储器地址输出。那么内存的数据输出到数据总线上，然后CPU可以从数据总线上读取数据。当记录数据到内存中， CPU首先输出到地址总线上的地址，然后将该数据输出到数据总线。内存中，然后在适当的位置中读取和存储的数据。读取数据和写入数据到I / O设备的处理是相似的。
控制总线是不同于其他两个总线。地址总线由n行，结合发送一个n位的地址值。同样地，数据总线的线一起工作，传输一个单独的多位值。与此相反，在控制总线是单独的控制信号的集合。这些信号指示数据是否被读入或写入的CPU ，是否CPU访问存储器或I / O设备，以及是否准备好传输数据的I / O设备或存储器。虽然这在图2-1所示为双向总线，它确实是一个收集（多）单向信号。这些信号是从CPU输出到存储器和I / O子系统，虽然有少数是由这些子系统输出到CPU 。我们更详细地研究这些信号，当我们在看的指令周期和子系统接口。
系统可能会有一个层次的巴士。例如，它可能使用它的地址，数据和控制总线访问存储器，和一个I / O控制器。 I / O控制器，反过来，可以访问所有的I / O设备，使用第二个总线，通常被称为I / O总线或本地总线。
2.1.2指令周期
指令周期是微处理器经过处理的指令的程序。首先，微处理器读取，或读取的指令从内存中。然后，解码指令，确定指令牵强。最后，执行必要的操作来执行指令。 （有些人还包括一个额外的元素到存储结果的指令周期中，在这里，我们作为执行功能的一部分，包括该操作）。这些功能 - 取指，译码和执行 - 包括一个序列或多个操作。
让我们从电脑启动时，与微处理器从内存中读取指令。首先，微处理器的指令的地址的地址总线上。内
2
存子系统输入这个地址，并解码它来访问所需的内存位置。
微处理器允许足够的时间内存地址译码和访问请求的内存位置后，微处理器断言读控制信号。读信号微处理器断言时，它已准备好读取数据从内存或I / O设备控制总线上的信号。 （有些处理器这个信号有不同的名字，但所有微处理器的信号来执行此功能。 ）根据微处理器，读信号可能是积极的高（断言 - 1）或低电平有效（断言 - 0） 。
读信号被断言时，存储器子系统将被提取到计算机系统的数据总线的指令代码，然后微处理器的输入来自总线的数据，并将其存储在其内部寄存器之一。在这一点上，微处理器取出的指令。
接着，微处理器对指令进行译码。每个指令都可能需要不同的操作顺序执行指令。当微处理器解码指令，它决定哪个指令是为了选择正确的顺序执行的操作。这样做是完全内的微处理器，它不使用系统总线。
最后，微处理器执行指令。的操作顺序执行指令，从指令到指令变化。执行程序可能从内存读取数据，写数据到内存，数据读取或写入数据的I / O设备， CPU内只执行操作，或执行这些操作的某种组合。我们现在就来看看计算机是如何执行这些操作从系统角度。
从内存读取数据，微处理器执行相同的操作序列，它使用从内存中读取指令。毕竟，取指令简单地读它从内存。图2-2 （a）所示，从存储器读取数据的操作的时序。
在图2-2中，注意顶部的标志， CLK 。这是计算机系统时钟，微处理器采用的系统时钟，使其操作同步。该微处理器的地址放置在总线上的一个时钟周期开始时，系统时钟的0/1序列。后面一个时钟周期，允许的时间内存地址译码和访问其数据，微处理器发出读信号。这会导致内存到系统数据总线将其数据。在这个时钟周期，微处理器读取关闭系统总线的数据，并将其存储在它的寄存器之一。在时钟周期的结束，它消除了地址的地址总线和拉高读信号。内存中，然后删除该数据从数据总线，完成存储器读操作。
在图2-2 （b）条中所示的存储器写操作的时序。该处理器放置到系统总线上的地址和数据在第一个时
3
钟周期。微处理器然后断言写控制信号（或其等价物） ，在第二个时钟周期的开始。正如读信号导致的内存中读取数据，写信号触发存储器存储数据。在这个周期期间的某些时间，存储器的数据总线上的数据写入到的内存位置的地址是在地址总线上。在这个周期结束时，通过除去从系统总线的地址和数据，并置为无效的写信号处理器完成存储器写操作。
的I / O读写操作都是类似的内存读取和写入操作。既可以使用内存映射I / O处理器或隔离的I / O。如果处理器支持内存映射I / O ，它遵循相同的操作序列输入或输出数据，读取数据或写数据到内存，序列，如图2-2所示。 （请记住，内存映射I / O ，处理器会将I / O端口，内存位置，所以它是合理治疗的I / O数据访问相同的内存访问）。使用隔离的处理器I / O遵循相同的过程，但有一第二控制信号来区分I / O和存储器的访问。 （ CPU的使用隔离I / O可以有一个内存位置和一个I / O端口，这使得这个必要的额外的信号具有相同的地址。 ）
最后，考虑完全在微处理器内执行的指令。的的INAC指令的相对简单CPU ， MOV R1 ，R2的8085微处理器的指令，可以被执行，而无需访问存储器或I / O设备。与指令解码，这些指令的执行不使用系统总线。
2.2 CPU的组织
该CPU控制计算机。它从内存中取出指令，供给所需要的存储器访问其数据，地址和控制信号。该CPU的指令进行解码，并控制执行过程。它执行一些内部操作，并提供所需要的内存和I / O设备执行指令的地址，数据和控制信号。在电脑上什么也没有发生，除非CPU会导致它发生。
在内部，该CPU具有三个部分，如图2-3所示。该寄存器部分，正如其名称所暗示的，包括一组寄存器和总线或其他通信机制。本节中的CPU处理器的指令集架构中的寄存器。系统地址总线和数据总线与本节的CPU 。寄存器部分中还包含其他寄存器由程序员不能直接访问的。相对简单的CPU包括寄存器锁存被访问的地址在存储器中，一个临时存储寄存器，以及其他的寄存器都它的指令集体系结构的一部分。
4
在取指部分的指令周期中，处理器首先指令地址输出到地址总线上。该处理器有一个寄存器，程序计数器， CPU保持在这个寄存器中取出的下一条指令的地址。前CPU输出到系统的地址总线上的地址，它会检索从程序计数器寄存器的地址。取指令的结束时，CPU读取的指令代码从系统数据总线。它存储在内部寄存器，这个值通常被称为指令寄存器或类似的东西。
算术逻辑单元ALU执行算术和逻辑操作，如添加或添加值。它接收其操作数寄存器部分CPU和存储其结果早在寄存器部分。由于ALU必须在一个单时钟周期完成其操作，只采用组合逻辑。在相对简单的CPU和8085微处理器的ADD指令执行期间使用ALU 。
正如CPU控制的计算机（除了它的其他功能） ，所述控制单元控制的CPU 。此单元产生内部控制信号，导致寄存器加载数据，递增或清除其内容，并输出其内容，以及导致ALU执行正确的功能。这些信号被显示在图2-3中为控制信号。控制单元接收从寄存器单元，它用来产生控制信号的某些数据值。此数据包括指令代码和标志寄存器的值的一些。控制单元也产生系统控制总线的信号，如读，写，和IO信号。微处理器通常取指，译码和执行一条指令执行一系列操作。以正确的顺序通过断言这些内部和外部的控制信号，所述控制单元使在CPU和其他的计算机来执行所需要的操作以正确地处理指令。
的CPU这样的描述是不完整的。目前的处理器有更复杂的功能，提高其性能。一个这样的机制，指令流水线，允许CPU取指令同时执行另一个指令。
在本节中，我们已经介绍了CPU从系统的角度来看，但我们还没有讨论其内部设计。我们研究的寄存器，数据路径和控制单元，所有这些共同采取行动，以使CPU正确地提取，解码和执行指令。 Microsequenced CPU具有相同的寄存器， ALU和数据路径硬连线的CPU ，但完全不同的控制单元。
2.3内存子系统组织
在本节中，我们检查一台电脑的内存子系统的建设和功能。
5
2.3.1记忆体的类型
有两种类型的存储芯片，只读存储器（ROM）和随机存取存储器（RAM） 。阅读只读存储器（ ROM ）芯片是专为应用中的数据是只读的。 （这些数据可以包括程序指令）。这些芯片被编程与由外部编程单元的数据之前，它们被添加到计算机系统。完成此操作后，数据通常不改变。 ROM芯片中始终保持它的数据，即使在芯片的电源被关闭。作为一个例子，一个嵌入式控制器用于微波炉可能连续运行一个程序，这并没有改变。这项方案可以存储在ROM中。
随机存取存储器（RAM） ，也被称为读/写存储器，可用来存储数据的变化。这是内存的类型简称为X MB内存的PC广告。不像ROM ， RAM芯片失去了他们的数据，一旦电源被切断。许多计算机系统，包括个人电脑，包括ROM和RAM 。
2.3.2超越基础
本章中所描述的内存子系统是足够小，嵌入式计算机。个人计算机和大型计算机系统，但是，需要更复杂的层次配置。这些电脑包括小，高速缓存存储器。计算机数据加载到缓存的物理内存，处理器可以更快速地存取缓存中的数据比它可以访问相同的数据在物理内存中。许多微处理器包括一些处理器芯片上的高速缓存。一台电脑，其中包括快取记忆体，还必须有一个高速缓存控制器，缓存和物理内存之间的数据移动。
在另一个极端，现代计算机，包括虚拟内存。这种机制使用硬盘作为计算机的内存中的一部分，花费在计算机的内存空间，同时最大限度地降低成本，因为一个字节的硬盘成本小于个字节的RAM 。与高速缓存一样，虚拟内存需要一个控制器移动至物理内存和硬盘之间的数据。
2.4 I / O子系统的组织与接口技术
CPU将内存同质。从CPU的角度来看，每个位置被读出并在完全相同的方式写入。每个存储单元都执行相同的功能 - 它存储数据值或由CPU使用的指令。
6
输入/输出（ I / O ）设备，在另一方面，是非常不同的。一台个人电脑的键盘和硬盘执行完全不同的功能，但都是I / O子系统的一部分。幸运的是，系统设计者之间的CPU和I / O设备的接口是非常相似的。
如图2-1所示，每个I / O设备连接到计算机系统的地址，数据和控制总线。每个I / O设备，包括I / O接口电路，它实际上是这个电路与巴士。该电路也与实际的I / O设备进行交互来传输数据。
图2-4显示了通用的接口电路的输入设备，诸如键盘。来自输入装置的数据的三态缓冲器。当地址总线和控制总线上的值是正确的，缓冲区被使能和数据传递到数据总线上。然后，该CPU可以读入这个数据。当条件是不正确的，逻辑块不会使缓冲区，他们是三态，并且不要放置在总线上的数据。
这种设计的关键是使能逻辑。正如每一个存储单元都有一个唯一的地址，每个I / O器件还具有一个唯一的地址。使能逻辑必须使缓冲区，除非它接收到正确的地址的地址总线。它也必须得到正确的控制信号，从控制总线。对于一个输入设备， RD （或RD ' ）信号必须被断言（以及/ IO信号，或相当于隔离I / O ）系统。
一个输出设备，诸如计算机监视器，接口电路的设计是有些不同的输入装置。如图2-5所示，三态缓冲器取代由注册。的三态缓冲器，用于在输入装置接口，以确保不超过一个设备写入数据到总线上，在任何时间。由于输出设备从总线读出的数据，而向其中写入数据，它们不需要缓冲区。所有输出设备的数据可以提供，只有正确的地址的设备将读取它。
负载逻辑使能逻辑所扮演的角色，在输入装置接口。当这种逻辑接收到正确的地址和控制信号，它断言LD信号的寄存器，从而导致它从系统的数据总线上读取数据。输出设备可以读取数据从寄存器在其休闲，而CPU执行其他任务。
一个变种，这种设计取代了寄存器三态缓冲器。相同的逻辑，用于加载寄存器是用来使三态缓冲器，而不是。虽然这可以为某些设计中，输出设备必须读入数据，而缓冲区中启用。一旦他们被禁止，三态输出缓
7
冲区和数据不再可用输出设备。
某些设备被用于输入和输出。一台个人电脑的硬盘驱动器就属于这一类。这样的设备要求，本质上是两个接口，一个用于输入和输出的组合的接口。一些逻辑元件，例如，检查地址在地址总线上的门，可以被用来产生两个缓冲器使能寄存器写入信号
I / O设备是远慢于CPU和内存。出于这个原因，他们可以有与CPU交互时的时序问题。为了说明这一点，考虑会发生什么，当CPU需要从磁盘读取数据。几毫秒，它可能需要的磁盘驱动器磁头的位置，正确地读取所需的值。在这个时候， CPU可读取无效的数据提取，解码，并执行上千条指令。
大多数CPU有一个控制输入信号称为就绪（或类似的东西） 。此输入通常是很高的。当CPU输出的地址的I / O设备和正确的控制信号，使三态缓冲器的I / O设备的接口， I / O设备的设置就绪低。该CPU读取该信号，并继续输出相同的地址和控制信号，使缓冲器保持启用。在硬盘驱动器的例子中，驱动器旋转的磁盘和读取所需的数据，直到它定位读出头。然后，CPU读取的数据总线，并继续正常运作。所产生的具有READY集低的额外的时钟周期被称为等待状态。也可以使用CPU的READY信号，用于同步数据传输的存储器子系统。
这些I / O接口都很好，如小型计算机，微波炉控制器，但他们遭受更大的计算机系统中表现不佳。但在所有的最小的系统，这是不能接受的CPU必须等待从一个I / O设备的数据的时钟周期。许多系统使用中断，使他们能够进行有效的工作，同时等待慢得多的I / O设备。
这些I / O接口也并不适合大数据量传输。在本章中的系统，每个字节的I / O设备和存储器之间传输的数据必须通过CPU的。许多常见的操作，如从磁盘中加载程序到内存，这是低效的。直接内存访问DMA，是一种用来绕过这些传输中的CPU ，因此他们更快速地执行。
第5章作业系统
8
最重要的程序在计算机上运行的操作系统。每一个通用的计算机必须有一个操作系统运行其他程序。一个操作系统的目的是执行基本任务，如识别从键盘输入，发送输出到显示屏幕，跟踪磁盘上的文件和目录，以及控制外围设备，如磁盘驱动器和打印机。
对于大型系统，操作系统有更大的责任和权力。它就像一个交通警察─它可以确保同时运行不同的程序和用户不互相干扰。操作系统还负责警卫工作，确保未经授权的用户没有对系统的访问。操作系统都可以进行分类，如下所示：
多用户：允许两个或多个用户同时运行程序。一些操作系统允许数百甚至数千个并发用户。
多处理：支持一个CPU上运行程序。
多任务：允许多个程序同时运行。
多线程：允许一个单一的程序同时运行的不同部分。
实时响应输入瞬间。通用的操作系统，如DOS和UNIX ，都不是实时的。
操作系统提供了软件平台的顶部，称为应用程序，其他程序可以运行。应用程序必须被写入到一个特定的操作系统上运行的顶部。你选择的操作系统，因此，在很大程度上决定你可以运行的应用程序。对于个人电脑，最流行的操作系统是DOS，OS / 2和Windows ，但也可提供其他如Linux 。
操作系统已经开发出两个主要目的。首先，他们提供了一个方便的开发环境和执行方案。二，操作系统尝试在调度计算的活动，以确保良好的性能，计算系统。
一般情况下，当一个新的计算机系统的安装，适合于该硬件的操作软件被购买。通常与操作软件的功能是：
9
1。作业管理
任何操作软件的一个非常重要的责任是由计算机系统来处理的调度工作。操作系统的设置处理程序的顺序，定义了序列中，特别是在执行作业。
2。资源管理
在计算机系统中的资源管理器是操作系统的另一个主要关注的。操作软件监督执行的所有程序，以及正在使用的设备。这将决定批准或拒绝一个特定的设备使用。
3。 I / O操作的控制
系统的资源分配是紧密相关操作软件的控制I / O操作。操作系统必须协调I / O操作和设备上，他们是执行。事实上，它设置了一个程序正在执行和使用的设备，他们必须在完成I / O操作的目录。
4 。内存管理
一个操作系统的最重要和最复杂的任务之一是存储器管理。它设法满足虚拟内存的最大能力利用主内存和辅助存储器之间的地址的交换。
5 。档案管理
的文件管理系统是一套提供服务的用户和应用程序使用的文件，包括文件存取，目录维护和访问控制系统软件。
第6章编程语言
10
6.1计算机语言
计算机语言都发生了戏剧性的变化，因为第一台电子计算机，建立协助第一次世界大战期间Ⅱ遥测计算。早期程序员的工作，用最原始的计算机指令：机器语言。这些指令代表的弦长的1和0 。不久，装配发明机器指令映射到人类可读和可管理的助记符，如ADD和MOV 。
随着时间的推移，更高级别的语言演变而来的，如BASIC和COBOL 。这些语言，让人们的工作与挪用的单词和句子的东西。如让我= 100 。这些指令翻译成机器语言由口译和编译器。口译员翻译程序，因为它读取它，把程序指令代码，直接转化为行动。编译器的代码转换成一个中间形式。此步骤称为编译，并产生一个对象文件。然后编译器调用一个链接，打开对象文件转换成一个可执行程序。
由于口译阅读代码，因为它是书面和现场执行的代码，口译容易为程序员工作。然而，编译器，引入额外的步骤编译和链接的代码，这是不方便的。编译器产生的程序是非常快的，每次运行。然而，耗时的任务已经完成的源代码翻译成机器语言。另一个优点许多编译语言，如C + +中，你可以分发可执行程序的人谁没有编译器。一个解释性的语言，你必须运行的程序。
多年来，计算机程序员的主要目标是写很短的代码，很快将执行。该计划所需的要小，因为内存是昂贵的。随着计算机变得更小，更便宜和更快，并作为存储器的成本下降了，这些优先级已经改变。今天，易于维护的代码写得很好，是一个溢价，也就是说，随着业务需求的变化，该方案可以扩展和增强没有很大的开支。
要求解决问题的程序员一直在变化。二十年前，方案是创建，管理大量的原始数据。人写的代码和使用程序的人，所有的计算机专业人士。如今，电脑更多的人使用，大多数计算机和程序如何工作所知甚少。电脑是谁比挣扎与计算机解决他们的业务问题有兴趣的人所使用的工具。
具有讽刺意味的是，为了变得更容易使用这个新的观众，节目已经变得更为复杂。飘的日子，当用户输
11
入的深奥难懂的指令提示，只看到原始数据流。今天的程序使用复杂的“用户友好界面”，涉及多个窗口，菜单，对话框，我们都熟悉。编写的程序，以支持这种新方法比只是10年前写的要复杂得多。作为编程的需求发生了变化，语言和写作计划所使用的技术演变而来的。
6.2面向对象编程
自从电脑成为在20世纪50年代，它一直是软件，利用它的力量来解决的应用问题。机代码，能够驱动原始硬件，是第一种语言提供给程序员。代码语句序列是最早形式的软件。很快就被确认，编程器和计算机之间的通信介质在编程的软件产品的整体生产率和质量是一个关键因素。
虽然电脑，硬件，接受革命后的革命，使用更快和更强大的组件，软件技术已明显落后在匹配这些进步。硬件技术已经彻底改变了几次：从管板级集成到集成电路分立晶体管，电阻和电容。即使是集成电路已经历了几次重大的进化步骤：从大规模集成（ LSI ）技术，超大规模集成（ VLSI ） ，最终圆片规模集成化。硬件工程能够跟上这样的步伐，通过开发新的技术来管理现代计算机系统的复杂性爆炸。
软件工程一直无法跟上的推进速度和计算能力的增加。大多数程序员在这个时代仍然可以使用比由第一程序员编程技术更先进一点的技术。这就是为什么我们面对的软件危机：软件变得越来越昂贵，质量不足，是很难估计和调度，管理几乎是不可能的。一些软件项目已经不可能超越今天的软件工程技术的范围来判断。虽然没有“银弹” ，承诺解决软件危机的视野中，它是“面向对象编程”的新技术，被视为大大推动软件技术的一个可能的第一步。
自从计算机被用来解决应用问题，这是软件的任务，以弥补在应用程序和计算机概念概念之间的差距。图6-1说明了这种语义鸿沟。在一侧的差距是应用程序的概念：例如，客户档案的整理，账户维护，或火箭发射。在另一边的概念是由计算机系统理解：电脉冲，微代码，机器代码指令，编程语言的结构。典型的编程任务是将应用到计算机概念的概念。如果翻译成功和计算机解决应用问题，一个成功的软件产品已经被开发出来。
12
在软件技术的进步驱动的欲望，使电脑的概念更容易从应用概念过渡。在软件技术的进步，已经缩小了双方的差距。一方面，他们提供的软件允许程序员来表示应用程序的问题更接近计算机系统方面的设计原则和技术。软件设计原理，如抽象，信息隐藏，模块化和逐步完善，允许程序员概念化的应用概念，并缓解其转化为计算机系统的概念。
在另一边，拥有先进的软件技术来操纵计算机系统使用的工具：编程语言的表现力。
在20世纪60年代后期，它被确认相结合的两种力量的软件设计技术和编程语言的进步是可能的。语言结构是一类。 A类实现抽象化，模块化和数据隐藏的概念。它这样做是通过分组功能，可应用于所有程序，用户定义的类型。类允许继承。继承的概念，涉及到逐步求精的设计理念，也可以重用现有的代码和数据结构的一类。
工程中的一个类的概念指到的软件技术的集成电路（IC）的硬件的发展相似的步骤。随着新的硬件系统也可以使用（或修改）的现成集成电路，它是现在可以构建软件系统，通过重用（或延长）的现成类。 “类”是面向对象编程的核心概念。面向对象编程的承诺语义差距显着缩小。
一些从函数调用和执行这种分离的面向对象的编程干的好处和灵活性。调用一个功能是被称为“一个消息发送到一个对象。其执行的执行被称为“消息的接收器执行相应的方法。 ”消息和方法的分离，极大地增加了在一个面向对象的程序的灵活性可能。
第7章的数据结构
7.1数据结构导论
数据来自于各种形状和大小，但往往也可以以同样的方式组织。例如，考虑要做的事情清单，在配方成分的列表，或一类的阅读列表。虽然每一个包含不同类型的数据，它们都包含以类似的方式组织：一个列表中的数据。列表是一个简单的例子，一个数据结构。当然，还有许多其他的常见的方式来组织数据，以及。
13
在计算中，一些最常见的组织，链接的列表，栈，队列，集合，哈希表，树，堆，优先级队列，和图表。使用数据结构的三个原因是效率，抽象和可重用性。
效率
数据结构算法更有效率的方式，使组织数据。例如，考虑的一些方法，我们可以组织数据搜索。一个简单的方法是将数组中的数据和搜索数据，通过遍历元素的元素，直到找到所需的元素。然而，这种方法是低效的，因为在许多情况下，我们最终遍历每个元素。我们可以通过使用另一种类型的数据结构，如一个哈希表或一个二叉树搜索的数据相当快。
抽象化
数据结构提供了一个更容易理解的方式来看待数据，因此，他们在解决问题提供一个抽象层。例如，通过将数据存储在堆栈中，我们可以集中精力栈，如压入和弹出元素，而不是如何实现每个操作细节，我们做的事情。换句话说，数据结构，让我们来谈谈较少编程方式的程序。
可重用性
数据结构是可重复使用的，因为它们往往是模块化的，上下文无关。它们是模块化的，因为每一个具有规定的接口，通过它的数据结构中存储的数据的访问限制。也就是说，我们只使用那些操作界面定义访问数据。数据结构是上下文无关的，因为它们可以使用任何类型的数据，并在各种情况或上下文。在C语言中，我们做任何类型的数据结构存储数据，使用void指针数据，而不是通过维持传抄中的数据的数据结构本身。
7.2栈
一个列表，使一个连续的链接结构更邀请的属性之一，是需要插入和删除列表中的条目里面。回想一下，它是这样的操作，有可能迫使大量的运动的名称，在一个连续的列表中的情况下填充或开设孔。如果我们限
14
制结构的端部这样的操作中，我们发现，使用一个连续的结构变得更方便的系统。这种现象的一个例子是一个堆栈，这是一个列表，在其中所有的插入和删除操作是在同一端的结构进行。这种限制的一个后果是，进入最后一个条目将永远是第一项删除 - 的观察，导致栈被称为后进先出（ LIFO ）结构。
一个堆栈的端部插入和删除的条目被称为堆栈的顶部。的另一端有时也被称为堆栈的基础。限制访问一个堆栈的最上面的项目，以反映这样一个事实，我们使用特殊术语时，指的插入和删除操作。插入的过程中，在栈上的对象被称为“推”操作，并删除一个对象的过程被称为一个弹出操作。因此，我们讲的一个条目推入堆栈和弹出一个堆栈条目。
7.2.1回溯
一个典型的应用程序的堆栈涉及执行程序涉及的程序。当执行一个程序的要求，本机必须转移其注意力的程序;但后来，当程序完成后，机器必须返回到原来的位置，然后再继续。这意味着，当初始传输，必须有一种机制记住执行最终返回的位置。
的情况是复杂的，由该程序本身可能要求的其他程序的执行，可要求又一，等等。因此，返回被记住的位置开始堆积。后来，随着完成这些程序，执行必须返回到适当的位置内的程序单元调用的完成过程。因此，我们需要一个系统来保存返回位置，后来他们以正确的顺序检索。
堆栈是一个理想的结构，建立这样一个系统。由于每个程序被调用时，相关的返回位置的一个指针，指向推入堆栈，为每个过程完成后，从堆栈的顶部条目用的保证获得一个指针返回到正确的位置。这个例子是代表堆栈的一般应用，它显示栈回溯的过程之间的关系。事实上，堆栈的概念中固有的任何过程中需要备份的系统以相反的顺序输入。
作为回溯另一个例子，假设我们要打印以相反的顺序一个链接列表的名字 - 那就是，姓在前。我们的问题是，只有这样我们才能访问的名称是通过以下的链接结构。因此，我们需要一种方式持有，直到所有的名
15
字都被检索和打印检索每个名称。我们的解决方案是遍历列表，从一开始到结束，而推到堆栈中找到我们的名字。列表到达终点后，我们打印的名字，我们弹出堆栈。
7.2.2栈的实现
要实现一个栈结构在计算机的内存中，这是习惯来预留一块大到足以容纳堆栈，因为它的增长和收缩的连续的存储单元。 （确定此块的大小往往是一个关键的决定，如果保留房间太少，堆栈最终超过分配的存储空间，如果太大的空间保留，会浪费内存空间，此块）的一端是指定为堆栈基地。正是在这里，被存储在栈上推的第一个条目，每增加一个条目被放在旁边，它的前身为堆栈保留块的另一端朝向生长。
因此，当条目被压入和弹出堆栈顶部的来回移动的存储单元内的保留块。的一种手段，因此需要保持纪录的顶级条目的位置。为了这个目的，最佳的条目的地址被存储在一个额外的存储单元被称为堆栈指针。即，堆栈指针指向堆栈的顶部。
完整的系统，如在图7-1所示的工作原理如下：要压入堆栈上的一个新的条目，我们首先调整的堆栈指针指向的空缺刚好超出堆栈顶部，然后将新条目这个位置。从栈中弹出一个入口，我们读到的数据指出，由堆栈指针，指针指向在堆栈上的下一个项目下来，然后调整。
我们观察到的列表的情况下，程序员可能会发现它有利的写程序，执行这些可以作为一个抽象的工具，以便堆栈的推入和弹出操作。需要注意的是，这些程序应该处理这种特殊情况下，尝试弹出条目从一个空栈，并推到一个完整的堆栈条目。特别是，一个完整的堆栈系统可能会包含推条目的程序，弹出条目，一个空栈，测试和测试完整的堆栈。
组织在一个连续的存储单元块堆栈显示在主内存中的概念结构和实际结构之间的差别不大。然而，假设我们不能保留一个固定的内存块，并保证堆栈将总是放不下。一种解决方案是执行堆栈，链接的结构类似的列表。这避免了堆栈限制到一个固定大小的块的限制，因为它允许在堆栈中的条目被塞进小件的可用空间，
16
在内存中的任何地方。在这种情况下，概念堆叠结构从内存中的数据的实际安排，会有很大的不同。
7.3队列
相反的同一端进行插入和删除堆栈，队列是一个列表，在其中插入的一端进行，而在其他所有删除。我们已经遇到这种结构在排队等待，我们承认它是一个先入先出（FIFO ）存储系统。其实，一个队列的概念中固有的供应对象以相同的顺序在它们到达任何系统。
两端的队列从这种等待行的关系，得到他们的名字。年底在该条目被删除的行头（或前）称为头（或有时就像我们说，未来受送达人在食堂的队列前） 。同样，被称为新条目被添加的队列结束的尾部（或后面） 。
在类似的方式存储一个堆栈，我们可以实现在一个块内的相邻单元格的计算机的存储器中的队列中。由于我们需要执行操作的结构两端，我们预留两个存储单元使用的指针，而不是只有一个，我们做了一摞。这些指针之一，被称为头指针跟踪队列的头;另一方面，被称为尾指针，跟踪的尾巴。当队列为空，这些指针指向的同一位置。每次一个条目被插入时，它被放置在所指向的位置的尾指针，然后被调整到尾指针指向下一个未使用的位置。以这种方式，尾指针总是指向队列尾部的第一个空缺。删除条目从队列中提取头指针所指向的条目，然后调整头指针指向的条目跟着删除的条目。
一个问题仍然迄今描述与存储系统。如果任其发展，队列通过记忆像冰川慢慢爬，摧毁在其路径中的任何其他数据。此运动是插入每一个新的条目，仅仅通过将其放置到前一个和相应的尾指针重新定位的结果，而自我中心政策。如果我们补充足够的条目，最终队列尾部一直延伸到机器的内存。
这种存储器消耗的队列的大小是没有结果的，但队列的接入过程的一个副作用。 （小而活跃的队列可以轻松地需要一台机器的内存资源比一个大，无效1 。 ）这个内存空间问题的一个解决方案可能是移动向前迈进了队列中的条目作为领先的去除，在同一人等着买东西，剧场门票的方式挺身而出每一次一个人已经送达。然而，这种群众运动的数据将是非常低效。我们需要的是一个区域内存没有被强制执行主要数据重排的
17
队列限制的一种方式。
一种常见的解决方案是在旁边设置一块内存队列，启动队列块的一端，并让队列转向块的另一端。然后，当队列尾部到达块结束时，我们只是开始回到原来端的块，这个时间是空置插入额外的条目。同样地，当在块中的最后一个条目最后变成队列头部的被删除时，头指针调整回其他条目的位置的块的开头，这个时候，等待。在这种方式中，该队列追逐块内的周围，而不是通过内存徘徊。
这样的技术成果的实现，被称为循环队列，因为效果是形成一个循环的块分配到队列的存储单元。至于队列而言，在块中的最后一个单元格是相邻的第一个单元格。
再次，我们应该认识到所设想的用户的一个队列中，在本机的存储器中的实际实现的环状结构的概念结构之间的差异。在先前的结构的情况下，这些差异是通常由软件桥接。这是一起用于数据存储的存储单元的集合，队列的实现应该包括一个程序的集合，插入和删除条目从队列以及检测队列是否是空还是满。
第8章软件工程
8.1软件生命周期
在软件工程中最根本的概念是软件生命周期。
8.1.1周期作为一个整体
软件生命周期，如图8-1所示。此数字代表一个事实，即一旦软件开发时，它进入一个周期的使用和修改，其余的软件生命继续。这样的模式是常见的许多制造产品。所不同的是，在其他的商品的情况下，修改阶段更准确地称为其他产品的修理或维护阶段，因为倾向于移动至所使用的，被修改为他们的部分被磨损。
软件，在另一方面，不磨损。相反，软件进入修改阶段，因为错误被发现，因为在软件的应用发生变化，
18
需要在软件的相应变化，或者是因为在先前的修改所做的更改被发现诱发其他问题在软件。例如，税法的变化，可能需要修改工资方案，计算扣缴税款，并常常在其他领域的方案可能不会发现，直到后来一段时间，这些变化可能产生不利影响。
不管为什么软件进入修改阶段，这个过程需要一个人（往往不是原作者）研究底层程序及其文档，直到程序，相关的计划的一部分，或至少了解。否则，任何的修改可能会引入更多的问题比它解决的。获取这种理解可以是一个困难的任务，即使当软件以及设计和记录。事实上，它往往是在这个阶段，一个软件最终的幌子下（往往如此） ，它是更容易从头开发一个新的系统，而不是成功修改现有的包丢弃。
经验表明，软件开发的过程中一点点的努力，可以使一个巨大的差异时，需要在软件中修改。
反过来，在软件工程中的大多数研究侧重于软件生命周期的发展阶段，目标是充分利用这方面的努力与利益杠杆。
8.1.2传统的发展阶段
开发阶段的软件生命周期内各阶段的分析，设计，实施和测试（图8-2） 。
分析软件生命周期的发展阶段开始与分析 - 一个主要目标是识别所提出的系统的用户的需求。如果系统是一个通用的产品在竞争激烈的市场中出售，这种分析将涉及一个基础广泛的调查，以确定潜在客户的需求。然而，如果该系统被设计为一个特定的用户，则该过程将是一个更窄的调查。
由于潜在的用户的需求被确定，它们被编译，以形成一组新的系统必须满足的要求。这些要求是所述的应用程序，而不是在数据处理领域的技术术语。一个要求可能是对数据的访问必须限制在授权的人员。另一种可能是年底的最后一个营业日，或显示在电脑屏幕上，必须坚持以纸张格式的数据形式安排目前使用的数据必须反映当前的库存状态。
19
的系统要求确定后，它们被转换成更多的技术的系统规格。例如，要求该数据被限制在授权的人员有可能成为规范，系统将不会响应，直到已批准的8位数的密码在键盘上键入或将显示数据以加密的形式，除非已知例行预处理只有经过授权的人员。
而分析设计集中在建议系统应该做什么，设计集中系统将如何实现这些目标。正是在这里，建立的软件系统的结构。
这是一个行之有效的原则，最好的大型软件系统是一个模块化结构。事实上，这是通过这种模块化分解的大型系统的实施成为可能。如果没有这样的细分，在一个大型系统的实施需要的技术细节会超过一个人的全面权力。
然而，随着模块化设计，只有细节有关模块正在考虑需要掌握。这种相同的模块化设计，也有利于今后的维护，因为它允许在模块化基础上作出的变化。 （如果更改要计算每个员工的健康福利的方式，那么只有模块处理与健康的好处需要加以考虑。 ）
然而，有一个模块的概念的区别。如果一个方法在传统的命令式范式方面的设计任务，模块包括程序和模块化设计的发展需要确定的各项任务，该系统必须执行的形式。与此相反，如果一个方法从面向对象的角度设计任务，模块能够被看见的对象和设计过程中的吞吐量的实体（对象）中所提出的系统，以及如何将这些实体的行为应该成为。
实施实施涉及到实际的写作程序，创建数据文件，数据库和发展。
测试测试实施是密切相关的，因为系统的每个模块实施，因为它是通常的测试。事实上，一个精心设计的系统中的每个模块可以独立于其他模块的测试通过使用简化的版本，称为存根，其他模块来模拟目标模块和系统其余部分之间的相互作用。当然，这种测试组件让整个系统的测试完成后，结合的各个模块。
不幸的是，一个系统的测试和调试成功地进行是非常困难的。经验表明，大型软件系统可以包含许多错
20
误，甚至在重大测试。许多这些错误可能未被发现的生命系统，但其他人可能造成重大的故障。消除这样的错误是软件工程的目标之一。事实上，他们仍然普遍手段，仍然需要做大量的研究。
8.1.3最新趋势
早期的软件工程方法坚持进行分析，设计，实施，测试，严格顺序的方式。感觉是太多大型软件系统的开发过程中，允许尝试和错误的技术风险。因此，软件工程师们坚持认为，在开始设计之前，完成整个分析系统，同样的设计在开始实施前完成。其结果是现在被称为瀑布模型的开发过程中，可以只在一个方向流动的事实，打个比方一个发展的过程。
你会注意到这四个问题解决阶段波利亚确定和分析，设计，实施，软件开发和测试阶段之间的相似性。毕竟，开发大型软件系统是解决的一个问题。另一方面，传统的瀑布式的软件开发方法是“随心所欲， ”试验和创造性解决问题的形成了鲜明的对比。鉴于瀑布方法旨在建立一个高度结构化的环境中，开发的进展，以顺序方式，创造性地解决问题的目的，其中一个可以放弃先前计划的攻击，追求火花的直觉，而不解释为什么一个非结构化的环境。
近年来，软件工程技术的出现，说明了增量模型的软件开发已经开始反映这一基本的矛盾。在此模型中，所需的软件系统构建的增量 - 即最终产品的简化版本具有有限功能的第一。一旦这个版本已经被测试，也许未来用户评价，越来越多的功能添加和增量的方式进行测试，直到该系统是完整的。例如，如果所开发的系统是一个寄存器一所大学的学生记录系统，第一个增量可能将只能够查看学生记录。一旦该版本是可操作的，额外的功能，如添加和更新记录的能力，以逐步的方式将增加。
增量模型是在软件开发的趋势走向建议的制度不完整的版本，称为原型，原型构建和评估的证据。增量模型的情况下，这些原型进化成完整的，最终的系统---一个过程被称为演化式原型。在其他情况下，原型可能被丢弃新鲜的实施有利于最终设计。这种方法被称为一次性成型。这个一次性的类别通常属于一个例子是快速原型，这在早期的发展阶段，建议系统的快速构建一个简单的例子。一个这样的原型，可能只有几指示
21
系统将如何与用户进行交互，就会有什么样的能力，让屏幕图像组成。我们的目标是不产生一个工作版本的产品，但获得的演示工具，可以用来澄清各方之间的沟通。例如，快速原型已经证明是有利的熨烫系统的要求，在分析阶段，或作为辅助销售演示过程中的潜在客户。
在软件工程中的另一个发展一直是计算机技术应用到软件开发过程本身，从而在被称为计算机辅助软件工程（ CASE ） 。这些电脑的系统被称为CASE工具，包括项目规划工具（即协助成本估算，项目调度，人员分配） ，项目管理工具， （协助监督开发项目的进展） ，文档工具（即艺术家撰写和组织文档） ，原型设计和模拟工具（即协助发展的原型） ，界面设计工具（即协助发展中的图形用户界面） ，编程工具（协助编写和调试程序） 。这些工具有些稍微比在其它应用程序中使用的字处理器，电子表格系统，和电子邮件通信系统。然而，其他人是相当复杂的封装设计，主要用于软件工程环境。例如，一些的CASE工具包括代码生成器，当给定的规格为系统的一部分，产生高层次的语言课程，实现该系统的一部分。
8.2设计方法
设计软件系统的开发方法是在软件工程中的一个重要的任务。在本节中，我们讨论了各种技术已发展以及目前的研究方向。
8.2.1自顶向下与自底向上的
也许最知名的战略是自上而下的方法与系统设计。这种方法的要点是，人们不应该尝试解决一个复杂的问题，在一个单一的步骤。相反，一个人的第一步应该是把问题分解成更小，更易于管理的子问题。然后，应该继续打破这些子成更小的问题。在这种方式下，一个复杂的问题变得更简单的解决方案的问题集体解决原始问题的集合。
自顶向下设计的结果往往是一个分层系统的优化，往往可以直接转化为模块化结构与命令式编程范式兼容。在层次结构中的最小的问题的解决方案成为程序模块，执行简单的任务，作为抽象工具的更为优越的模
22
块，以解决系统中的更复杂的问题。
相反，自顶向下的设计方法是自底向上的方法，一开始设计的一个系统，确定系统内的单个任务，然后考虑如何解决这些任务作为抽象的工具，可用于解决更复杂的问题。多年来，这种方法被认为逊色于自顶向下设计范式。
然而，今天，自底向上的方法已经获得了支持。这种转变的原因之一是，自顶向下的方法寻求解决方案，其中占主导地位的模块使用的子模块，其中每一个依赖于subsubmodules的，依此类推。然而，许多系统是最好的设计不是一个层次的性质。事实上，设计，由两个或两个以上的平等互动的模块，客户端 - 服务器模型，以及一般的并行处理应用程序，例如可能是一个更好的解决方案设计由上级模块依赖于下属执行其的任务。
底向上的设计兴趣增加的另一个原因是，它是更符合目标的既有的，现成的，现成的组件构建复杂的软件系统 - 这是一个目前的趋势在软件工程方法。
8.2.2设计模式
在努力寻找方法，使软件可以建造的现成组件，软件工程师们不断向建筑领域的灵感。特别令人感兴趣的是由克里斯托弗·亚历山大等书模式语言，描述了一组设计社区的模式。每个图案组成的语句的问题，其次是一个建议的解决方案。这个问题的目的是要普及，在这个意义上，他们解决的普遍性问题，而不是提出一个解决方案，为特定的情况下，提出的解决方案是通用的。
例如，一个图案，称为安静后背，地址，需要躲开的骚动在短期内有商务中心茶点。提出的解决方案是设计成商业区的“安静的背影” 。在某些情况下，可以设计区周围所有建筑物面临的主要街道 - 因此，提供安静的小街背后的建筑物。在其他情况下， “安静的背影”获得通过的公园，河流或教堂。
我们讨论的最重要的一点是，亚历山大的工作，试图找出普遍性的问题，并为解决这些问题提供模板。
23
今天，许多软件工程师正试图运用同样的方法，大型软件系统的设计。特别是，研究人员在应用设计模式的一种手段，可以构造软件系统提供通用的构建模块。
这种模式的一个例子是发布用户的模式，组成一个模块（发布者），必须将其“出版物”的副本其他模块（订阅） 。作为一个具体的例子，考虑在计算机屏幕上正在显示在不止一个格式 - 也许饼图以及条形图 - 同时数据的集合。在此设置，任何的数据变化应该体现在两个图形。因此，负责绘制图形的软件模块中的数据发生变化时，应当通知。然后，在这种情况下，保持数据的软件模块，发行所扮演的角色，必须发送更新信息到用户，这是负责绘制图形模块。
软件设计模式的另一个例子是容器组件模式。它捕获一个容器，它包含的部件，是自己的容器的一般概念。这样的模式的例子是一个操作系统的文件管理器中所使用的目录或文件夹。这些目录通常包含其他目录，这可能仍包含其他目录。总之，容器组件模式是指捕捉到递归的概念包含容器的容器。
一旦如发行者的订户或容器组件的模式已被确定，软件工程师提出的发展骨骼的程序单元，称为框架， ，实施柄的解决方案的相关的功能，而离开特定应用程序的特定功能为时隙，以被填充在后面的。陪框架，软件工程师提出文档描述的框架如何可以填写的基本模式在一个特定的环境中获得完整的实现。这些文件被称为一剂良方。亲切地称为集合框架连同他们的食谱食谱。
研究人员希望通过的食谱，软件工程师最终将能够为构建大型的，复杂的软件系统的现成组件 - 组件的框架。早期的研究结果表明，这种方法可以显着降低在开发一个新的系统所需的编程量。
所有的兴奋，已经产生超过设计模式在软件工程社区，有趣的是要注意的是亚历山大与他的建筑模式的结果并没有高兴。总之，他发现，从他的图案设计系统缺乏字符， 20世纪80年代初以来，一直专注于自己的工作方式来捕捉这种回避的质量。然而，软件工程师认为在软件开发中，我们的目标不涉及美和性格等素质，而是精度和效率。因此，他们继续，设计模式将被证明是比较成功的，比在软件工程领域的架构。
24
因篇幅问题不能全部显示，请点此查看更多更全内容