数据结构是一种计算机科学技术领域广泛使用的专业术语，在很多书籍以及博客中，对数据结构的解释为数据在计算机的存储方式，很容易让人误以为数据结构只是一种数据的物理存储方式，其实不然，数据结构可以理解为：数据 + 结构。数据是描述客观事物的符号，为程序操控，存储在计算机上，结构包括数据的逻辑结构和存储结构。
2.数据的逻辑结构

数据元素间抽象化的相互关系，与数据的存储无关，独立于计算机，但逻辑结构决定元素的输入、存储、发送、处理和信息传递的基本操作功能。逻辑结构有四种基本类型：集合结构、线性结构、树形结构和图形结构。表和树是最常用的两种高效数据结构，许多高效的算法能够用这两种数据结构来设计实现

2.1.集合结构

由若干元素集合在一起形成的团聚体（或称集合体）相互堆积起来的一种结构类型，数据元素之间无其他的关系，仅仅属于同一集合体而已。

2.2.线性结构

数据元素之间存在一一对应的关系，其开始节点和终端节点具有唯一性，除了开始开始节点和终端节点，其他的元素有且仅有一个前驱节点和后继节点，线性表就是一个典型。

2.3.树形结构

数据元素之间存在着一一对应的关系，每一个数据元素只有一个前驱节点，但是却又很多后继节点 终端节点可以有多个。二叉树就是一个典型。

2.4.图形结构

又称为非线性结构，数据元素之间存在着多对多的关系，其前驱节点和后继节点的个数可以是任意多个

注：四种逻辑结构存在着关系：树形结构是图形结构的特殊形式，而线性结构又是树形结构的特殊形式。

3.数据的存储结构

存储结构描述了数据在计算机内部的存储安排

3.1.顺序存储结构

把逻辑上相邻的数据存储在物理位置上相邻的存储单位里，用物理位置上的相邻来体现逻辑上的相邻，此种存储结构的又在于节省了存储空间，因为分配给数据的存储单元完全用于了数据的存储，数据之间的逻辑关系没有占用存储空间，可以实现对数据的随机存取，每个节点对应一个序号，由这个序号可以计算出数据的存储地址，缺点在于不变于数据的修改，对数据的插入和删除可能要移动一系列的数据。

3.2.链式存储结构

逻辑上相邻的两个数据元素不一定在物理位置上也要相邻，数据元素之间的相邻是用添加的指针来标识的，优点在于由于不要求在物理上的相邻，所以在进行插入，删除等时，只需要改变相邻节点的指针域，不必移动数据的位置，相对于顺序结构，链式的缺点在于存储空间利用率太低，因为存储数据的一部分单元用于了存储数据之间的逻辑关系，由于相邻的节点在物理位置上不一定相邻，所以不能进行随机存在。

3.3.索引存储结构

该结构在存储数据元素的同时，还建立了一个附加的索引表，索引表中的每一项称为索引项（关键字，地址），关键字唯一标识一个数据元素 ，地址是指向数据元素的指针，采用了索引的存储结构可以所及存取数据元素，在进行插入，删除等时，只需要移动相应索引表中的地址，不必移动数据，故而大大提高了数据的查找速度，缺点在于添加了索引表，降低了存储空间的利用率

3.4.散列（哈希）存储结构

就是根据数据元素的关键字通过哈希函数计算出一个数值用做数据元素的存储地址，优点在于查找速度快，只需要给出关键字可立即计算出该数据元素的地址 特点是指存储数据元素不存储数据之间的逻辑关系，只适合进行快速查找和插入的场合

4.重拾数据结构

数据结构对一些科班出生来说，可能并不陌生但是很多人在校期间对这些专业基石课不以为然，相对于枯燥无味的数据结构与算法课程，大家可能更倾向于去学习一些更实用的开发框架，本人也是如此，对当时一些流行的框架爱不释手，觉得数据结构课程很鸡肋，食之无味，弃之可惜，学习它是因为要应付学校的考试和日后的求职面试，觉得在实际开发中并不实用，可是现实很快打了我一个响亮的耳光。

1）一个完整的计算机系统是由硬件系统和软件系统两大部分组成

2）计算机软件是指程序和与程序相关的文档的集合

3）按功能可把软件分为“系统软件”和“应用软件”两部分

系统软件：操作系统语言处理程序，数据库管理系统

应用软件：各种管理软件，用于工程计算的软件包，辅助设计软件

4）通常把未配置任何软件的计算机称为“裸机”

5）操作系统可以被看作是计算机系统的核心，统管整个系统资源，制定各种资源的分配策略，调度系统中运行的用户程序，协调它们对资源的需求，从而使整个系统在高效、有序的环境里工作。

6）发展的动力：

(1) 提高计算机资源的利用率的需要

(2) 方便用户使用计算机的需要

(3) 硬件技术不断发展的需要

(4) 计算机体系结构发展的需要

7）操作系统是在“裸机”上加载的第一层软件，是对计算机硬件系统功能的首次扩充

8）操作系统的定义：

操作系统是控制和管理计算机硬件和软件资源，合理地组织计算机工作流程，以及方便用户使用计算机的一个大型程序

9）操作系统的功能：

Ø 处理机管理：进程控制，进程同步，进程通信、调度、实施CPU分配

Ø 存储器管理：内存分配，内存保护，地址映射，内存扩充

Ø 设备管理：缓冲管理，设备分配，设备管理

Ø 文件管理：存储空间管理，目录管理，读写管理和保护

Ø 与用户有关的接口：用户接口，程序接口，人机交互

10）操作系统另一种定义：操作系统是一组能有效地组织和管理计算机硬件和软件资源，合理地对各类作业进行调度，以及方便用户使用的程序的集合

操作系统的种类：

1) 单道批处理系统

特点：单路性、独占性、自动性、封闭性、顺序性

缺点：系统的资源得不到充分的利用

2) 多道批处理系统

特点：多路性、共享性、自动型、封闭性、无序性、调度性

好处：

ü 提高CPU的利用率

ü 提高内存和I/O设备的利用率

ü 增加系统吞吐量

缺点：平均周转时间长，无交互能力

3) 分时系统

分时系统是指在一台主机上连接了多个配有显示器和键盘的终端，由此所组成的系统，该系统允许多个用户同时通过自己的终端，以交互方式使用计算机，共享主机中的资源。

采用了“时间片轮转”的处理机调度策略

4) 实时系统

实时系统是指系统能及时响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行

第二章 处理机管理

1) 进程是指在系统中能独立运行并作为资源分配的基本单位，它是由一组机器指令，数据和堆栈等组成的，是一个能独立运行的活动实体，多个进程可以并发执行和交换信息

2) 程序是一个在时间上严格有序的指令集合

3) 在单道程序设计下，系统具有的特点

a. 资源的独占性

b. 执行的顺序性

c. 结果的再现性

在多道程序设计环境下，系统具有：

a. 执行的并发性

b. 相互的制约性

c. 状态的多变性（不可再现性）

5) 并发、并行、串行

a. 从宏观上看是并行，同时在内存的多个程序都在执行着，互不影响

b. 从微观上看是串行，由于CPU在任何时刻只能执行一个程序，因此这些程序轮流占用CPU，交替执行着

c. 我们把“逻辑上相互独立的程序，在执行时间上相互重叠，一个程序的执行还没有结束，另一个程序的执行已经开始”的这种特性称为程序执行的并发性

6) 对进程的描述

a. 进程是程序的一次执行过程

b. 进程的运行活动是建立在某个数据集合上的

c. 进程是在获得资源的基础上从事自己的运行活动

7) 进程的特征

结构特征、动态性、并发性、独立性、异步性

进程是一个动态的概念

不同进程可以执行同一个程序

每一个进程都有自己的生命周期

进程之间具有并发性，进程间会相互制约

8) 程序和进程的区别

a. 程序是指令的有序集合，是静态的，进程是程序在处理机上的一次执行过程，是动态的。程序的存在时永久的，而进程是有生命周期的，它因创建而产生，因调度而运行，因撤销而消亡

b. 进程是程序的一次执行过程，程序是进程赖以存在的基础

c. 进程具有并发性，而程序并发执行会失去可再现性

d. 进程是系统分配和调度的独立单位，进程由程序、数据集合和进程控制块组成

9) 系统进程的使用级别高于用户进程

10) 进程的状态

创建、就绪、运行、阻塞

a. 一个进程从运行状态变为就绪状态，一定会引起另一个进程从就绪变为运行

b. 一个进程从运行状态变为阻塞状态，一定会引起另一个进程从运行状态变为就绪状态；这种因果变迁绝对不可能发生，因为一个CPU不可能真正同时运行两个进程

c. 一个进程从阻塞状态变为就绪状态，不一定会引起另一个进程从就绪状态变为运行状态

11) 进程的三个组成部分：程序、数据集合、进程控制块（PCB）

12) 进程控制块是进程存在的唯一标示

a. 作用：通过PCB，是原来不能独立运行的程序，成为一个可以独立运行的基本单位，一个能够并发执行的进程

b. 其中的信息：进程标识符、处理机状态、进程调度信息、进程控制信息

13) 操作系统中把做出“决定把CPU分配给谁用”的程序称为“进程调度程序”

14) 常用的进程调度算法：

a. 先来先服务调度算法

b. 时间片轮转调度算法：为就绪队列中的每一个进程分配一个称为“时间片”的时间段，它是允许该进程占用CPU的最长时间长度

c. 优先数调度算法：优先数高的先调度，若相同则先来先服务

d. 多级队列调度算法：时间片调度和优先数调度算法的结合

15) 进程调度程序的主要功能

a. 记录系统中所有进程的有关情况，比如进程的当前状态，优先数等

b. 确定分配处理机的算法

c. 完成处理机的分配

d. 完成处理机的回收

16) 把处理剂分配给进程后，还有一个允许它占用多长时间的问题，有两种处理方式，一种是不可剥夺方式，另一种是剥夺方式

17) 为了对进程进行有效的管理和控制，操作系统要提供若干基本的操作以便能创建进程、撤销进程、阻塞进程、唤醒进程，把具有这种特性的程序称为“原语”，原语的不可分割性，通常利用屏蔽中断的方法

18) 程序接口：操作系统在程序一级给予用户的支持

命令接口：操作系统在控制一级给予用户的支持

19) CPU指令系统中的指令分为两类

a. 操作系统和用户都能使用的指令，非特权指令

b. 只能由操作系统使用的指令，特权指令

20) CPU的两种工作状态：管态、目态

a. 当CPU处于管态时，可以执行包括特权指令在内的一切机器指令

b. 当CPU处于目态时，禁止使用特权指令

21) 访管指令

系统调用命令的程序属于操作系统，它应该在管态下执行

用户程序只有通过计算机系统提供的访管指令才能实现由目态转为管态，进而调用这些功能程序的目的

访管指令属于非特权指令，功能是执行它就会产生一个软中断，促使中央处理机由目态转为管态，进入操作系统并处理该中断

22) 从功能上看，可以把系统调用命令分为五大类：

a. 一是关于进程管理和控制的

b. 二是关于外部设备输入/输出的

c. 三是关于磁盘文件管理的

d. 四是关于访问系统信息的

e. 五是关于存储申请与释放的

23) 从形式上看，操作系统提供的系统调用与一般的过程调用（子程序调用）相似，但它们有着明显 的区别

作业管理：

1) 把一个作业提交给系统时，系统要开辟一个作业控制块JCB，以便随时记录作业的信息

2) 被系统接纳的作业，在没有投入运行之前，称为后备作业。这些作业存放在辅助存储器中，并由他们的JCB连接在一起，形成所谓的后备作业队列

3) 作业调度：按照某种规则，从后备作业队列中挑选作业进入内存，参与处理机的竞争，这个过程称为作业调度

4) 作业的状态：

a. 提交状态：进入辅助存储器，作业的信息还没有全部进入系统，系统也没有为它建立JCB，感知不到它的存在

b. 后备状态：建立起了JCB，并将JCB排到后备作业队列中

c. 运行状态：（阻塞、运行、就绪）都属于运行状态

d. 完成状态：也是一个暂时性的状态

5) 作业的调度算法：

a. 先来先服务：以作业进入后备作业队列的先后次序

周转时间=完成时间-到达时间

注：若分配一定的内存，且不允许作业在内存中移动时，要考虑所占内存大小

b. 短作业优先：从后备作业队列中挑选所需CPU时间最少且资源能够得到满足的作业

注：如果所有作业“同时”到达后备作业队列，那么采用短作业优先的作业调度算法总会获得最小的平均周转时间

c. 响应比高着优先：先调度响应比高着   

响应比=已等待时间/所需CPU时间

6) 在确定作业调度算法时应注意的问题：

a. 公平对待后备作业队列中的每一个作业，避免无故或无限期的延迟一个作业的执行，使各类用户感到满意

b. 使进入内存的多个作业，能均衡地使用系统中的资源，避免出现有的资源没有作业使用，有的资源却被多个作业争抢的“忙闲”不均的情况

c. 力争在单位时间内为尽可能多的作业提供服务，提高整个系统的吞吐能力

第三章 存储管理

1)  计算机操作系统的存储器：CPU寄存器，主存，辅存

2) 在考虑计算机存储器的设计时，必须顾及

a. 价格、容量、访问时间

b. 存取时间越快，价格越高，容量越小

3) 高速缓存：介于寄存器和存储器之间的存储器，主要用于备份主存中较常用的数据，以减少处理机对主存储器的访问次数，提高程序执行速度

高速缓存容量远大于寄存器，比内存约小两到三个数量级左右

为了缓和内存与处理机（CPU）速度的不匹配

4) 字（字长）：一次传送数据的长度{16、32、64…}依系统而定

（主）内存储器和高速缓存之间是以“块”为单位传递数据的

高速缓存与CPU之间则以“字”为单位传递数据

5) 存储器管理的功能：

a. 内存的分配与回收

b. 存储的保护和共享

c. 地址定位

d. 存储扩充

6) 内存储器由一个个存储单元组成，一个存储单元可存放若干个二进制的位（bit），8个二进制位被称为一个字节（byte）

7) 在操作系统中，把用户程序指令中的相对地址变为所在绝对地址空间中的绝对地址的这个过程，称为地址重定位

8) 地址的定位方式：

a. 绝对定位方式：是在程序装入内存之前，程序指令中的地址就已经是绝对地址，已经正确地反映了它将要进入的存储区的位置，不适用于多道程序设计环境

b. 静态重定位（多道程序环境下）

根据内存的具体情况将装入模块装入到内存的适当位置，会使装入模块中的所有逻辑地址与实际装入内存后的物理地址不同。

这种地址重定位是在程序执行前完成的

c. 动态重定位

将地址重定位的时间推迟到程序执行时再进行

所以装入内存的所有地址都仍是逻辑地址

连续分配存储方式 ：

1) 单一连续分配（静态重定位）

a. 单道程序环境下，总体上把内存储器分为两个分区：系统区和用户区

b. 系统总是把整个用户区分配给一个用户使用，把分配给了用户但未被使用的区域称为“内部碎片”

c. 单一连续分区存储管理的缺点：

a) 由于每次只能有一个进入内存，故它不适用于多道程序设计，工作效率不高，资源利用率低

b) 只要作业比用户区小，在用户区里就会形成碎片，造成资源浪费

c) 大作业无法在小内存中运行

d. 为缓解大作业小内存的情况提出覆盖技术和对换技术

a) 覆盖技术：允许一个作业的若干个程序段使用同一个存储区

b) 对换技术：以辅助存储器作为内存的后援（硬盘）

2) 固定分区存储管理（静态）：分区数目、大小固定

a. 预先把内存储器中可供分配的用户区划分成若干个连续分区，每个分区的尺寸可以相同，可以不同。每个分区中只允许装入一个作业运行，系统可以为每一个分区设置一个后备作业队列，一个作业到达时，总是进入到“能容纳该作业的最小分区”的那个后备队列中去排队

b. 分区的分配与释放方案：

a) 在队列中挑选出第一个可容纳的作业进入

i. 优点：选择效率高

ii. 缺点：小作业->大内存

b) 在这个队列中进行搜索，找到这个分区能够容纳的最大的那个作业，让它进入运行

i. 优点：存储空间利用率高，产生内部碎片尽可能的小

ii. 缺点：选择效率低

c) 在系统中至少保留一个小的分区，以避免因为运行小作业而被迫分配打分去的发生

d) 为具体管理各个分区，并建立一个“分区分配表”，其中包括每个分区的起始位置大小及状态

c. 特点

a) 它是最简单的，具有“多道”色彩的存储管理方案，提高资源利用率

b) 当把一个分区分配给某个作业时，该作业的程序将一次性的全部装入到分配给他的连续分区里

c) 静态重定位，在分区内的程序不能随意移动

d. 缺点

a) 进入分区的作业尺寸不见得与分区的长度相吻合，势必产生内部碎片，引起资源的浪费

b) 如果到达作业的尺寸比任何一个分区的长度都大，它就无法运行

3) 可变分区存储管理：

分区的边界划分随作业的需求可变，分区的数目随着进入作业的多少可变，消灭了内部碎片（可能会产生内部碎片）。

外部碎片是指无法分配给用户使用的存储区

a. 基本思想：在作业要求装入内存储器时，如果当时内存储器中有足够的存储空间满足该作业的需求，就划分出一个与作业相对地址空间同样大小的分区，并分配给它

b. 要解决的问题

a) 采用一种新的地址重定位技术，动态地址重定位，以便程序能够在内存储器中随意移动，为空闲区的合并提供保证

b) 记住系统中各个分区的使用情况

c) 给出分区分配算法

c. 地址动态重定位过程（在程序执行时动态完成）

a) 为实施地址动态重定位，硬件要增加一个地址转换机构，这个机构一般由地址转换线路和一个定位寄存器（基址寄存器）组成

b) 地址的静态重定位和动态重定位的比较

i. 地址转换时刻：静态重定位是在程序运行之前完成地址转换的，而动态重定位是在程序执行时完成

ii. 谁来完成任务：静态重定位是由软件完成地址转换工作的，而动态重定位则是由一套硬件提供的地址转换机构来完成

iii. 完成的形式：静态重定位是在装入时一次性集中地把程序指令中所有要转换的地址加以转换；而动态重定位则是每执行一条执行时，就对其地址加以转换

iv. 完成的结果：实施静态重定位，原来的指令地址部分被修改了，而动态重定位只是按照所形成的地址去执行这条指令，并不对指令本身做任何修改

d. 空闲区的合并

e. 分区的管理

a) 表格法：一张已分配表，一张空闲表（分区号，分区大小，分区起始地址、状态）

b) 单链表法：一个存放该分区的长度，另一个存放它下一个空闲分区的起始地址

c) 双链表法：还存放上一个空闲区起始地址

f. 空闲分区的分配算法

a) 最先适应算法：要求空闲分区链以地址递增的次序链接（对大作业不利）

b) 最佳适应算法：每次为作业分配内存时，总是把能满足要求，又是最小的空闲分区分配给作业，避免“大材小用” 按其容量

c) 最坏适应算法：挑选一个最大的空闲区，从中分割一部分存储空间给作者使用，以至于存储器中缺乏大的空闲分区，照顾中小作业的需求

d) 循环首次适应算法：从上次分配的位置之后开始查找

g. 可变分区存储管理的特点

a) 作业一次性的全部装入到一个连续的存储分区中

b) 分区是按照作业对存储的需求划分的，所以不会出现内部碎片

c) 为了确保作业能够在内存中移动，要有硬件的支持，实行指令地址的动态重定位

h. 缺点：

a) 仍然没有解决小内存裕兴大作业的问题，只要作业的存储需求大于系统提供的整个用户区，该作业就无法投入运行

b) 虽然避免了内部碎片，但有可能出现极小的翻去暂时分配不出去的情形，引起了外部碎片，

c) 为了形成大的分区，可变分区存储管理通过移动程序来达到分区合并的目的，然而程序的移动是很花费时间的，增加了系统在这方面的投入与开销

4) 分页式存储管理：

需要两次访问内存，目的是提高内存利用率

a. 分页式储存管理是将固定分区方法与动态重定位技术结合在一起，需要硬件支持

基本思想：首先把整个内存储器划分成大小相等的许多分区，每个分区称为“一块”

b. 在分页式存储管理中，块是存储分配的单位

a) 用户作业仍然是相对于“0”进行编址，形成一个连续的相对地址空间

b) 用户程序相对地址空间中的每一个分区被称为“页”，用户相对地址空间中的每一个相对地址，都可以用（页号，页内位移）这样的数对来表示

i. 物理地址=页的大小*页号+页内位移

ii. 页号=相对地址/块尺寸

iii. 页内位移=相对地址%块尺寸

c. 页与块对应关系表称为“页表”

a) 快速寄存器组单独起名为“相联寄存器”，简称“快表”

b) 快表与页表联合工作，先查找快表，若无再查找页表并把数据写入快表

c) （访问页表时间+访问一次内存时间）*命中率+访问快表时间*命中率=平均内存存取时间

d) 页面尺寸大多选在512byte到64kb之间

d. 特点：

a) 内存储器实现被划分成相等尺寸的块，它是进行存储分配的单元

b) 用户作业的相对地址空间按照块的尺寸划分成页，这是在系统内部进行的，用户感觉不到

c) 相对地址空间中的页可以进入内存中的任何一个空闲块，并且分页式存储管理实行的是动态重定位，因此它打破了一个作业必须占据连续的存储空间的限制，作业在不连续的存储区里，也能够得到正确的运行

e. 缺点：

a) 平均每一个作业要浪费半页大小的存储块，会产生内部碎片

b) 作业虽然可以不占据连续的存储区，但是每次仍然要求一次全部进入内存。因此，如果作业很大，其存储需求大于内存，仍然存在小内存不能运行大作业的问题

5) 分段式存储管理：

a. 目的：方便用户使用编程，存储共享，存储保护，动态增长，动态链接

b. 要求用户将自己的整个作业程序以多个相互独立的称为“段”的地址空间提交给系统，每个段都是一个从“0”开始的一维地址空间，长度不一，操作系统按照段长为作业分配内存空间

c. 段表：段号、段长、该段在内存的基址（起始地址）{段号，段内位移}

a) 物理地址=段的起始地址+段内地址

b) 逻辑地址=段号+段内地址

d. 分段与分页的区别：

a) 页是信息的物理单位，段是信息的逻辑单位

i. 分页提高内存的利用率，仅仅是系统管理上的需要，用户不可见。段是信息的逻辑单位，它通常包括的是一组意义相对完整的信息，分段段的目的主要在于能更好地满足用户的需要

b) 页的尺寸由系统决定，段的尺寸因段而异

i. 段的长度取决于用户编写的程序，通常由编译程序在对源程序进行编译时根据信息的性质来划分

c) 页的地址空间是一维的，段的地址空间是二维的

i. 分页：用户必须通过链接编辑程序，把各程序段链接成一个相对于0编址的线性空间，程序中是通过地址编号来确定空间中的位置的。因此用户向系统提供的是一个一维的逻辑地址空间。

ii. 分段：用户不把各程序段链接成一个相对于0进行编制的一维线性空间，各程序段之间是通过{段号，段内位移}进行访问的。因此，用户向系统提供的是一个二维的逻辑地址空间

6) 段页式存储管理：（三次访问内存）

a. 基本原理：分段和分页原理的结合，即先将用户程序分成若干个段，再把每个段分成若干个页，并为每一个段赋予一个段名。

a) 作业地址空间结构：主程序段，子程序段，数据段

b) 地址结构：段号，段内页号，页内地址

b. 系统设置了位示图、段表和页表，记录主存的使用情况和作业分配情况

a) 逻辑地址=段号+页号+页内位置

b) 块号*块长+页内地址

c. 虚拟存储器：是具有请求调入功能和置换功能，能从逻辑上对内存容量加以扩充的一种存储器系统，其逻辑容量由内存容量和外存容量之和所决定，其运行速度接近于内存速度。

a) 特征：多次性、对换性、虚拟性、离散性

d. 请求分页式存储管理（需要硬件支持）

a) 是基于分页式存储管理的一种虚拟存储器

“请求分页式”是指当程序运行中需要某一页时，再把它从辅助存储器里调入内存使用，解决了小内存与大作业的矛盾，但会产生内部碎片

b) 缺页中断是指在指令执行期间，若发现所要访问的指令或数据不在内存时，便立即产生和处理缺页中断信号，以便能及时将所缺之页面调入内存

e. 缺页中断与一般中断的区别 {缺页中断率=缺页次数/页面总数}

a) 缺页中断是在执行一条指令中间时产生的中断，并立即去处理，一般中断则是一条指令执行完毕后，当发现有中断请求时，才去响应和处理

b) 缺页中断处理完成后，仍返回到原指令去执行，因为那条指令并未执行；而一般中断则是到下一条指令去执行，因为上一条指令已经执行完毕了

f. 影响缺页中断次数的因素：

a) 分配给作业的内存块数

b) 页面尺寸

c) 程序的实现

7) 页面淘汰（置换）算法：

页面淘汰是由缺页中断引起的，但缺页中断不见得一定引起页面淘汰

a. 先进先出页面淘汰（置换）算法（FIFO）

淘汰最先进入内存的页面 （3个内存块都为空，3次缺页中断）

b. 最近最久未用页面淘汰（置换）算法（LRU）

总是把最长时间未被访问过的页面淘汰出去 （需要寄存器和栈）

c. 最近最少用页面淘汰（置换）算法（LFU）

总是把当前使用的最少的页面淘汰出去

为每个内存中的页面设置一个计数器（移位寄存器） 加1

d. 最优（最佳）页面淘汰（置换）算法（OPT）

把以后不再使用的或最长时间内不会用到的页面淘汰出去（理论上，不会实现）

注：对于FIFO页面淘汰算法，有时增加分配给作业的可用内存块数，它的缺页次数反而上升，通常称为异常现象

第四章 设备管理

1．“设备”泛指计算机系统中的各种外部设备，外设（即主机以外的其他所有设备）在众多的I/O设备中，并不是所有的设备都是可以共享的，可以借助于磁盘，把只能独享的设备变为共享，这就是所谓的“虚拟设备” {SPOOLing技术}

2．设备是指计算机中用以在机器之间进行传送和接收信息，完成用户输入/输出（I/O）操作的那些部件。比如磁盘、磁带、打印机、显示器、鼠标、键盘······

3．计算机I/O系统的组织结构：

（1）底层是具体的设备和硬件接口

（2）中间是系统软件（与设备相关软件、与设备无关软件）

（3）用户程序

4．I/O设备一般是由执行I/O操作的机械部分和执行控制I/O的电子部件组成

（1）执行I/O操作的机械部分就是一般的I/O设备

（2）执行控制I/O的电子部件称为设备控制器或适配器

① 为了能够使CPU设备控制器中的各个寄存器进行通信，通常采用“单独的I/O空间”和“内存映射I/O”两种方法

② 设备控制器是CPU与外围设备之间的接口，是一个可编址设备，每一个地址对应一个设备

功能：

Ø 接收和识别命令

Ø 数据交换

Ø 标识和报告设备的状态

Ø 地址识别

Ø 数据缓冲区

Ø 差错控制

组成：

Ø 设备控制器与处理机（CPU）的接口

Ø 设备控制器与设备的接口

Ø I/O逻辑：用于实现对设备的控制

5．设备驱动程序：

6．设备处理方式：

（1）为每一类设备设置一个进程，专门用于执行这类设备的I/O操作

（2）在整个系统中设置一个I/O进程，专门用于执行系统中所有各类设备的I/O操作

（3）不设置专门的设备处理进程，而只为各类设置相应的设备驱动程序，供用户或系统进程调用

7．设备驱动程序的处理过程

（1）将抽象要求转换为具体要求

（2）对服务请求进行校验，即检查I/O请求的合法性

（3）检查设备的状态

（4）传送必要的参数

（5）启动I/O设备

（6）工作方式的设置

I/O接口程序：是操作系统中与设备无关的软件，它从上层接收用户对设备提出的I/O请求，然后负责吧I/O请求转变成所需要的I/O命令，调用具体的设备驱动程序去执行

系统都是用主设备号和次设备号组成“逻辑设备名”

操作系统提供的设备无关性的优点：

ü 方便用户

ü 提高设备的利用率

8．计算机设备的分类

（1）基于设备的从属关系

a. 系统设备（键盘、显示器、打印机、磁盘驱动）

b. 用户设备

（2）基于设备的分配特性

a. 独享设备（打印机）

b. 共享设备

c. 虚拟设备（SPOOLing技术）

（3）基于设备的工作特性

a. 输入/输出设备（字符设备）

b. 存储设备（块设备） 磁盘、磁带

（4）按信息交换的单位

a. 块设备：用于存储信息，属于结构设备。磁盘、磁带（以块为单位传送信息）

b. 字符设备：以单个字符为单位来传送信息。 键盘

9．设备管理的目标

a. 提高外部设备的利用率

b. 为用户提供便利、统一的使用界面

10．设备管理的功能

a. 提供一组I/O命令

b. 进行设备的分配和回收

c. 对缓冲区进行管理

d. 实现真正的I/O操作

11．输入输出管理步骤

（1）用户在程序中使用系统提供的输入/输出命令发出I/O请求

（2）输入输出管理程序接受这个请求

（3）“设备驱动程序”来具体完成所要求的的I/O操作

（4）实现设备中断处理程序来处理这个请求

设备的输入输出管理程序由3块内容组成：接受用户的I/O请求，组织管理输入输出进行，输入输出的善后处理

设备控制：

1) 设备控制块DCB中存放的是一台具体设备的有关信息，找到一个设备的DCB，就得到了该设备的特性，各种参数，使用情况等，所以DCB是设备管理中最重要的一条数据结构

2) 独享设备中具有排他性，只能采取“静态分配”的策略

a. 静态分配：用户作业开始之前，由系统一次分配给该作业所需的设备，控制器和通道，不会发生死锁

b. 动态分配：在进程执行过程中进行的设备分配，可能造成死锁

对独享设备采用的分配算法：

v 先来先服务

v 优先级高者先服务

3) 共享磁盘的调度

磁盘是一种典型的共享存储设备，允许多个作业进程同时使用，而不是让一个作业在整个运行期间独占。“同时使用”是指当一个作业进程暂时不用时，其他作业进程就可以使用。每一个时刻只有一个作业用

4) 调度算法

a. “先来先服务”调度算法（并不理想）（移臂调度，减少查找时间）

以I/O请求到达的先后次序作为磁盘调度的顺序

b. “最短查找时间”调度算法

把距离磁头当前位置最近的I/O请求作为下一次调度的对象

c. “电梯”调度算法（SCAN）

总是沿着此案移动臂的移动方向选择距离磁头当前位置最近的I/O请求，作为下一次调度的对象

d. “单向扫描”调度算法（循环扫描 CSCAN）

总是从0号柱面开始往里移动移动臂，遇到有I/O请求就进行处理，直到到达最后一个请求柱面，然后移动臂立即带动磁头不做任何服务地快速返回到0号柱面，开始下一次扫描

对I/O设备的控制方式（数据传输方式）

1) 程序循环测试方式（程序查询式）

是指用户进程使用start指令启动设备后，不断地执行test指令，去测试所启动设备的状态寄存器。只有在状态寄存器出现了所需要的状态后，才停止测试工作，完成输入/输出。

数据寄存器：用来存放传输的数据

状态寄存器：用来记录设备当前所处状态

2) 中断方式

所谓“中断”是一种使CPU暂时中止正在执行的程序而转去处理特殊时间的操作。

引起中断的时间称为中断源。

程序中产生的中断，由CPU的某些错误结果（如，计算机溢出）产生的中断称为“内中断”，由外部设备控制器引起的中断称为“外中断”

3) 直接存储器存取方式（DMA方式）

特点：能使I/O设备直接和内存储器进行成批数据的快速传输。（单位：块数据）

DMA控制器包括四个寄存器：数据寄存器，状态寄存器，地址寄存器，字节计数器

DMA控制器的组成：主机与DMA控制器的接口；DMA控制器与块设备的接口；I/O控制逻辑

4) 通道方式

通道方式能够使CPU彻底从I/O中解放出来。CPU进行善后处理和启动。

通道是一个独立于CPU的，专门用来管理输入/输出操作的处理机。

通道是通过执行通道程序并与设备控制器共同实现对I/O设备的控制的。

它规定了设备应该执行的各种操作的顺序。由一系列通道指令所构成，CPU对I/O请求只去做启动和善后处理工作，输入/输出的管理以及数据传输等事宜，全部由通道独立完成。

缓冲：

1) 原因：

a. 缓和CPU与I/O设备间速度不匹配的矛盾

b. 减少对CPU的中断频率，放宽对CPU中断响应时间的限制

c. 解决数据粒度不匹配的问题

d. 提高CPU和I/O设备之间的并行性

2) 缓冲的实现

a. 采用专门的硬件寄存器，比如设备控制器里的数据寄存器，“硬件缓冲”

b. 在内存储器中开辟出n个单元，作为专用的I/O缓冲区，以便存放输入/输出的数据，这种缓冲区就是“软件缓冲”

c. 根据缓冲区的个数：单缓冲区、双缓冲区、多缓冲区、缓冲池

3) 虚拟设备

a. 通过多道程序技术可将一台物理CPU虚拟为多台逻辑CPU，需要硬件的支持。作为后援的硬盘（大容量），具有设备与CPU并行工作的能力

4) SPOOLing技术

a. 在主机的直接控制下，实现以前的脱机输入/输出功能，此时的外围操作与CPU对数据的处理同时进行，我们把这种在联机情况下实现的同时外围操作的技术称为SPOOLing技术，或假脱机技术

b. SPOOLing技术是对脱机输入/输出系统的模拟。SPOOLing系统建立在通道技术和多道程序技术的基础上，以高速随机外存（通常为磁盘）为后援存储器

5) 设备无关性：

应用程序中所用的设备，不局限于使用某个具体的物理设备。为每个设备所配置的设备驱动程序是与硬件紧密相关的软件。为了实现设备独立性，必须再在设备驱动程序上设置一层软件，称为与设备无关的I/O软件或设备独立性软件

6) 操作系统中实现虚拟设备的软件功能模块由3部分组成

a. 预输入程序

b. 缓输出程序

c. 井管理程序

7) SPOOLing系统由四部分组成

a. 输入井和输出井

在磁盘上开辟出来的两个存储区域，输入数据，输出数据

b. 输入缓冲区和输出缓冲区

在内存中开辟的两个缓冲区

c. 输入进程和输出进程

模拟外围控制机

d. 井管理程序

特点：

Ø 提高了I/O的速度

Ø 将独占设备改造为共享设备

Ø 实现了虚拟设备的功能

第五章 文件管理

1) 目标：提高外存储空间的利用率

主要任务：对用户文件和系统文件进行管理，方便用户使用，并保证文件的安全性

文件存储设备是以块为单位进行管理的

2) 所谓“文件”是指具有完整逻辑意义的一组相关信息的集合，它是在磁盘上保存信息，而且能方便以后读取的方法，文件用符号名加以标识，这个符号名就被称为“文件名”

3) 文件是指由创建者所定义的，具有文件名的一组相关元素的集合，可分为有结构文件和无结构文件两种。在有结构的文件中，文件由若干个相关记录组成而无结构文件则被看成是一个字符流。文件在文件系统中是一个最大的数据单位，它描述了对象集

文件属性：文件类型、文件长度、文件的物理位置、文件的建立时间（最后一次的修改时间）

4) 文件名：在不同的系统之间，对文件名的规定是不同的。一个文件名是在创建该文件时由用户给出的，操作系统将向用户提供组成文件名的命名规则

5) 很多操作系统采用句点‘.’隔开成两部分的文件名形式，句点之前的部分称为文件名，句点后面的部分称为文件的“扩展名”。又称后缀名，用于指示文件的类型

.bak 备份文件 .bas ABSIC源程序 .bin 可执行的二进制文件

.c C源程序 .dat 数据文件 .doc 文档文件

.hlp 帮助文件 .obj 目标文件 .pas Pascal文件

.txt 一般文本文件 .tmp 临时文件

1) 文件被存在大容量的辅助存储器（外存）中，当用户需要使用时，就通过文件名把相应的文件读到内存

2) “文件系统”是指操作系统中与文件管理有关的那部分软件，被管理的文件，以及管理文件所需要的数据结构（目录、索引表······）的总体

3) 对文件的分类

a. 按文件的性质和用途：系统文件、用户文件、库文件

b. 按文件中数据的形式：源文件、目标文件、可执行文件

c. 按存取控制属性分类：只执行文件、只读文件、读写文件

d. 按文件的保护性质：只读文件、读写文件、可执行文件、不保护文件

e. 按文件的保护期限：临时文件、档案文件、永久文件

f. 按文件的存取方式：顺序存取文件、随机存取文件

g. 按设备的类型：磁盘文件、磁带文件、打印文件

h. 按文件的物理结构：连续文件、链接文件、索引文件

i. 按文件的内容（组织形式和处理方式）：普通文件、目录文件、特殊文件

j. 按文件的逻辑结构：流式文件、记录式文件

4) 文件的逻辑结构

a. 从用户使用的角度出发组织的文件，被称为是文件的逻辑结构，一类是有结构的文件，这是指由一个以上的记录构成的文件，故又称为记录式文件

b. 从文件的组织方式来分，可以分为顺序文件，索引文件，索引顺序文件

c. UNIX操作系统总是以流失作为文件的逻辑结构

5) 文件的物理结构

a. 文件按不同的组织方式在辅存上存放，就会得到不同的物理结构，文件的物理结构有时也称为文件的“存储结构”

b. 文件在辅存（外存）上可以有3种不同的存放方式：连续存放、链接块存放以及索引表存放

c. 对应地文件就有3种物理结构，分别叫做顺序结构，链接结构和索引结构，也叫作连续文件，串联文件，索引文件

6) 存放方式

a. 连续存放—连续文件

不足之处：

v 必须预先知道文件的最大长度

v 会造成磁盘碎片

b. 链接块存放—串联文件

不会因为磁盘碎片而浪费存储空间，但使用的指针要占去一些字节，每个磁盘块存储数据的字节数不再是2的幂，从而降低了系统的运行效率

c. 索引表存放—索引文件

7) 文件的存取

a. 顺序存取

b. 随机存取

8) 磁盘空间的管理

a. 磁盘是以块为单位进行分配的

b. 磁盘与内存之间是以磁盘块为信息传输的单位

c. 选定了块的大小，还要对它们进行管理，即要记住哪些已经分配，哪些仍然空闲。

d. 常采用的磁盘存储空间管理方案有：位示图，空闲块表，空闲块链

9) 文件的操作：

创建文件、删除文件、打开文件、关闭文件、读文件、写文件

10) 系统是通过文件的目录来管理文件的

文件目录也是一种数据结构，用于标识系统中的文件及其物理地址

11) 为每一个文件开辟一个存储区，在它的里面记录着该文件的有关信息。

我们把该存储区称为“文件控制块”（FCB） 也是一个目录项

随系统的不同，一个文件的FCB中所包含的内容及大小也不尽相同

包含内容：

Ø 文件名称

Ø 文件在辅存中存放的物理位置

Ø 文件的逻辑结构

Ø 文件的物理结构

Ø 文件的存取控制信息

Ø 文件管理信息

12) 目录的层次结构

如果把所有文件的FCB都登记在一个文件目录中，这样由文件名查文件目录项，直接就能够找到所需要的文件，那么就成这种文件目录为一级目录结构

a) 优点：

i. 简单，能实现目录管理中最基本的功能—按名存取

b) 缺点：

i. 查找速度慢，不允许重名，不便于实现文件共享

二级目录结构：

由“主目录”与“用户目录”二级构成，在主目录（根目录）中，每个目录项的内容只是给出文件主名以及它的目录所在的磁盘地址。在一个个用户目录中，才是由问价的呢FCB组成的目录，用户目录，实际上就是一级目录

1) 两级目录结构的优点：

a. 提高了检索目录的速度

b. 在不同的文件目录中，可以使用相同的文件名

c. 不同用户还可使用不同的文件名访问系统中的同一个共享文件

2) 缺点：

a. 若一个用户可以拥有很多文件，则查找时间仍然很长

b. 用户无法对自己的文件进行再分类安排

3) 树型目录结构

允许每个用户可以拥有多个目录，即在用户目录的下面可以再分子目录，子目录的下面还可以再有子目录。但每个文件目录中，只能有一个根目录，每个文件和每个目录都只能有一个父目录

4) 从根目录出发到具体文件所经过的各层名字，就构成了文件的“路径名”，从根目录出发的这个路径名，也称为文件的“绝对路径名”。

文件的绝对路径名必须从根目录出发，且是唯一的，从分隔符开头

在UNIX系统中，路径名各部分之间是用“/”分隔

在MS-DOS系统中，路径各部分是用“\”分隔

在MVLTICS系统中，路径各部分之间是用“>”分隔

在当前目录下的文件的路径名，称为文件的相对路径名

5) 文件的“共享”是指一个文件可以被多个授权用户共同使用

分两种：

Ø 任何时刻只允许一个用户使用共享文件

Ø 允许多个用户同时使用同一个共享文件，只进行读操作

第六章 进程间的制约关系

1) 在多道程序设计环境下，进程程序的执行具有并发性，在相同的前提条件下，两次执行的结果有可能不相同，使得一个进程对另一个进程的影响无法预测，在操作系统里把这种由于时间因素的影响而产生的错误称为：“与时间有关的错误”

2) 进程间具有两种制约关系：互斥和同步

a. 由于对共享资源的争夺，导致进程之间出现互斥关系

b. 由于对任务的协调工作，导致进城之间出现同步关系

3) 把那些可以共享的资源（文件、队列、缓冲区、表格、变量······）统称为共享变量或临界资源

与一个共享变量（或共享资源）交往的多个进程，为了保证它们各自运行结果的正确性，当其中的一个进程正在对该变量（临界资源）进行操作时，就不允许其他进程同时对它操作。进程的这种制约关系被称为“互斥”

4) 注意（互斥进程）

a. 作为具有互斥关系的进程，它的一部分程序可能用于内部的计算以及内部的数据处理等，那么只有设计共享变量的那一部分程序，才真正需要保证互斥地执行，把进程程序中“真正需要保证互斥执行”的那一段程序（或在每个进程中访问临界资源的那段代码）称为该进程的临界区（临界段）

b. 具有互斥关系的进程，并不关心对方的存在，即使对方不存在，自己也能够正确地运行

c. 具有互斥关系的那些进程程序中的临界区，虽然都是针对同一个共享变量的程序，但在其上执行的操作可以相同也可以不同

d. 进程的临界区是相对于某个共享变量而言的，不同共享变量的临界区之间，不存在互斥关系

信号量及其定义在信号量上的P、V操作：

1) 如何来保证进程在临界区执行的互斥性，由信号量及其定义在信号量上的P、V操作具体完成，但遵循如下规则

a. 如果有若干个进程希望进入临界区时，至少应该允许一个进入，而不能谁也进不去

b. 每次只允许一个进程进入临界区

c. 进入临界区的进程不能无限期地把持临界区

2) 同步

a. 需要在某些点上协调相互的动作，谁先到达谁后到达是有顺序要求的

b. 这些进程都应该了解对方的工作，对方如果不存在，或任何一方单独运行，就会出现差错

c. 一方或双方的运行会直接地依赖于对方所产生的的信息，或发出的消息

3) 一个进程运行到某一点时，除非合作进程已经完成了某种操作或发来了信息，否则就必须暂时等待那些操作的完成或信息的到来。

进程间的这种关系被称为“同步”，暂停以取得同步的那一点称为“同步点”，需要等待一个进程完成的操作或发送的信息，称为“同步条件”

4) 一个信号量的建立必须经过说明，即应该准确说明S的意义和初值（不能为负）

每个信号量都有相应的队列，在建立信号量时，队列为空

可进行原子操作 P(wait)、V(signal)操作

5) 信号量S上的P操作

① Vs = Vs-1，把当前信号量S的取值减1

② 若Vs >= 0，则调用进程继续运行，若Vs < 0，则调用进程由运行状态变为阻塞状态，到与该信号量有关的队列Vq上排队等待，直到其他进程在S上执行V操作将其释放为止

6) 信号量S上的V操作

① Vs = Vs + 1，把当前信号量S的取值加1

② 若Vs > 0，则调用进程继续执行，若Vs <= 0，则先从与该信号量有关的队列Vq上摘下一个等待进程，让它从阻塞状态变为就绪状态，到就绪队列里排队，然后调用进程继续执行

注意：

a. 设置的信号量初值一定是一个非负的整数。而运行过程中，信号量的取值就不再受“非负”所限了

b. 只要进入了P(S)或V(S)，这两个动作就必须顺序地做完，中间不能被打断，为保证执行时的不可分割性，常采用关、开中断的方法来具体实现信号量上的P、V操作

c. 如果一个进程在做P操作后被阻塞，到关于信号量的队列上去排队等待，其含义是让进程的PCB到此队列上排队

7) 用P、V操作实现资源分配

做P操作即是申请一个资源，做V操作即是释放一个用完的资源

P操作后，若Vs > 0时，Vs的值就是这种资源的剩余数

若Vs < 0时，表示现在已经没有资源可以分配，申请资源的进程只能被阻塞到申请队列Vq上去排队等待，Vs的绝对值表示提出资源请求，但没有分配到资源的进程个数

V操作后，若Vs <= 0，表示申请资源的等待队列上有进程在等待该资源（表示V操作之前Vs <= -1，即至少有一个进程在队列上等待使用该资源），所以将该队列上的一个进程摘下，让它到就绪队列中排队

若Vs > 0，表示V操作之前Vs >= 0，即资源等待队列上没有进程在等待，只是收回了一个资源

1) 死锁：多个进程因竞争资源而造成的一种僵局，若无外力作用，这些进程将无法向前推进

2) 定义：即指系统中若存在一组（至少两个或以上）进程，它们中的每一个都占用了某种资源而又都在等待其中另一个所占用的资源，这种等待永远不会结束，这就是死锁

3) 产生死锁的4个必要条件

a. 互斥条件：进程对所分配的资源进行排它性使用，即在一段时间内，某资源只能被一个进程占用

b. 部分分配条件（占用并等待）：进程由于申请不到所需要的资源而等待时，仍然占据着已经分配到的资源

c. 非剥夺条件：已经分配给进程的资源，别的进程不能强行夺取资源，只能被占用它的进程自己释放

d. 循环等待条件：在多个进程之间，由于资源的占有和请求关系，从而形成了一个循环等待的态势

4) 处理死锁的方法：

a. 预防死锁：破坏产生死锁的4个必要条件之一，使系统不具备产生思索的条件

b. 忽略死锁：任凭死锁出现，当系统中出现死锁时，就将系统重新启动

c. 避免死锁：在资源的动态分配过程中，用某种方法防止系统进入不安全状态，从而可以避免死锁

d. 检测死锁并恢复：在死锁发生后，采取相应措施加以恢复。如：撤销一些进程，回收它们的资源，将它们分配给已处于阻塞状态的进程，使其继续执行

5) 预防死锁：

a. 互斥条件是非共享设备所必须的，不仅不能改变，还应加以保证

b. 破坏占用并等待条件：所有进程在开始运行之前，必须一次性地申请其在整个过程中所需要的全部资源，一次性分配

c. 破坏“分剥夺条件”：当进程提出新的资源请求得不到满足时，它必须释放已经保持的所有资源，待以后需要时再重新申请

d. 破坏循环等待条件：将系统中的所有资源进行统一编号，进程按编号的顺序，由小到大提出对资源使用的申请

6) 在信号量上的P、V操作，可以看作是进程间的一种通信方式，这种通信并不在进程间真正交换信息，而只是双方事先的一种约定。因此，用P、V操作实现的通信，称为进程间的一种低级通信

为了使进程间能够真正交换数据，操作系统备有高级通信命令，提供给用户在程序一级使用

高级进程通信分为直接通信和间接通信两种方式

间接通信是指通过信箱来传递消息

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<math.h>

#define MAXSIZE 1000 //链表的最大长度
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int ElemType;
typedef int Status; //函数类型，其值是函数结果状态代码，如OK等
typedef int Position;
typedef int LinkList;

struct Node{
    ElemType data; //数据域
    Position next;//指针域（游标）
} List[MAXSIZE]; //全局变量，静态链表的存储空间

void InitSpaceSL(void);//构造一个"模拟空间分配站",为全局变量
Position MallocSL(void); //"动态"分配空间给结点P
void FreeSL(Position P);//释放结点P的空间到"模拟空间分配站"
Status InitList(LinkList *L);//建立一个带头结点的空线性表L
Status ListEmpty(LinkList L);//判断线性表是否为空，若线性表为空，返回TRUE，否则返回FALSE
void DestroyList(LinkList *L);//销毁线性表L
Status ClearList(LinkList *L);//将线性表清空（只留下头结点）
int ListLength(LinkList L);//返回线性表L的元素个数
Status DisplayList(LinkList L);//输出线性表L的所有元素
Status GetElem(LinkList L, int i, ElemType *e);//将线性表L中第i个位置元素值赋给e
Status LocateElem(LinkList L, ElemType e);//在线性表L中查找是否存在与给定值e相等的元素
Status ListInsert(LinkList *L, int i, ElemType e);//在线性表L中的第i个位置之前插入新元素e
Status ListDelete(LinkList *L, int i, ElemType *e);//删除线性表L中的第i个位置，并将该元素值赋给e

int main(void)
{
    LinkList a = NULL;
    ElemType *p, e = 0;
    int i;
   
    InitSpaceSL(); //构造一个"模拟空间分配站",为全局变量
   
    InitList(&a);//建立一个空的线性表
   
    ListInsert(&a, 1, 1);
    for (i=1; i<10; i++)
    {
        ListInsert(&a, i, i+100);
    }
   
    DisplayList(a);
   
    printf("len = %d\n", ListLength(a));
    for (i=1; i<ListLength(a); i+=2)
    {
        ListDelete(&a, i, &e);//删除线性表L中的第i个位置，并将该元素值赋给e
    }
    printf("len = %d\n", ListLength(a));
    printf("e = %d\n", e);
   
    DisplayList(a);
   
    i = 5;
    e = 1050;
    if (LocateElem(a, e))//在线性表L中查找是否存在与给定值e相等的元素
    {
        printf("存在%d\n", e);
    }
    else
    {
        printf("不存在%d\n", e);
        ListInsert(&a, i, e);
    }
   
    DisplayList(a);
   
    ListDelete(&a, ListLength(a), &e);//删除线性表L中的最后一个元素
    DisplayList(a);
   
    ListDelete(&a, 1, &e);//删除线性表L中的第一个元素
    DisplayList(a);
   
   
    ClearList(&a);//将线性表清空（只留下头结点）
    DisplayList(a);
   
    return 0;
}

/*
函数名称：InitSpaceSL
函数功能：构造一个"模拟空间分配站",作为静态链表的存储空间.
初始化各结点的游标值，每个结点的游标值均表示其后继结点的数组下标 
输入变量：无
输出变量；无
*/
void InitSpaceSL(void)
{
    Position i;
   
    for (i=0; i<MAXSIZE-1; i++) //每个结点的游标值均表示其后继结点的数组下标
    {
        List[i ].next = i + 1;
    }
   
    List[MAXSIZE-1].next = 0;//尾结点的后继结点下标为0，即NULL
}

Position MallocSL(void) //"动态"分配空间给结点P
{
    Position P = 0;
   
    if (List[0].next != 0) //还有空间
    {
        P = List[0].next;
        List[0].next = List[P].next;
    }
   
    return P;
}

void FreeSL(Position P)//释放结点P的空间到"模拟空间分配站"
{
    List[P].next = List[0].next;
    List[0].next = P; //回收P结点的空间，实际上相当于入栈 ，List[0]即栈顶
}

Status InitList(LinkList *L)//建立一个带头结点的空线性表L
{
    *L = MallocSL(); //为链表的头结点分配空间
    if (!*L)
    {
        printf("Out of space!");
        return ERROR;
    }
   
    List[*L].next = 0;
   
    return OK;
}

Status ListEmpty(LinkList L)//判断线性表是否为空，若线性表为空，返回TRUE，否则返回FALSE
{
    return (List[L].next == 0) ? TRUE : FALSE;
}

void DestroyList(LinkList *L)//销毁线性表L
{
    Position s;
   
    while (*L != 0)
    {
        s = List[*L].next;
        FreeSL(*L);
        *L = s;
    }
}

Status ClearList(LinkList *L)//将线性表清空（只留下头结点）
{
    Position q, s = List[*L].next;
   
    while (s != 0)
    {
        q = List[s ].next;
        FreeSL(s);
        s = q;
    }
   
    List[*L].next = 0;
}

int ListLength(LinkList L)//返回线性表L的元素个数
{
    Position s = List[L].next;
    int count = 0;
   
    while (s != 0)
    {
        count++;
        s = List[s ].next;
    }
   
    return count;
}

Status DisplayList(LinkList L)//输出线性表L的所有元素
{
    Position s = List[L].next;
    int i = 0;
   
    if (s == 0)
    {
        printf("none!\n");   
        return ERROR;
    }
   
    while (s != 0)
    {
        printf("data[%d] = %d, ", i++, List[s ].data);
        s = List[s ].next;
    }
    printf("\n");
       
    return OK;
}

Status GetElem(LinkList L, int i, ElemType *e)//将线性表L中第i个位置元素值赋给e
{
    int j = 1;
    Position s = List[L].next; //p指向第一个结点（非头结点）
   
    while (s != 0 && j < i) //寻找第i个结点
    {
        j++;
        s = List[s ].next;
    }
   
    if (s == 0 || j > i) //第i个元素不存在
    {
        return ERROR;
    }
   
    *e = List[s ].data;
   
    return OK;
}

Status LocateElem(LinkList L, ElemType e)//在线性表L中查找是否存在与给定值e相等的元素
{
    Position s = List[L].next;

    while (s != 0)
    {
        if (List[s ].data == e)
            return TRUE;
        s = List[s ].next;
    }
   
    return FALSE;
}

Status ListInsert(LinkList *L, int i, ElemType e)//在线性表L中的第i个位置之前插入新元素e 
{
    int j = 1;
    Position s, p = *L; //p指向头结点
   
    while (p != 0 && j < i) //寻找第i-1个结点
    {
        j++;
        p = List[p].next;
    }
   
    if (p == 0 || j > i) //第i-1个结点不存在
    {
        return ERROR;
    }
   
    s = MallocSL(); //为新结点分配空间
    if (!s)
    {
        printf("Out of space!");
        return ERROR;
    }
   
    List[s ].data = e;
    List[s ].next = List[p].next;
    List[p].next = s;
   
    return OK;
}

Status ListDelete(LinkList *L, int i, ElemType *e)//删除线性表L中的第i个位置，并将该元素值赋给e
{
    int j = 1;
    Position q, p = *L; //p指向头结点
   
    while (p != 0 && j < i) //寻找第i-1个结点
    {
        j++;
        p = List[p].next;
    }
   
    if (List[p].next == 0 || j > i) //第i个结点不存在
    {
        return ERROR;
    }
   
    q = List[p].next; //q指向第i个结点
    *e = List[q].data;
    List[p].next = List[q].next;
    FreeSL(q);
   
    return OK;
}

   问题描述：假设给定了n个红色的水壶和n个蓝色的水壶，它们的形状和尺寸都不相同。所有红色水壶中所盛水的量都不一样，蓝色水壶也是一样。此外，对于每个红色的水壶，都有一个对应的蓝色水壶，两者所盛的水量是一样的。反之亦然。
  你的任务是将所盛水量一样的红色水壶和蓝色水壶找出来。为了达到这一目的，可以执行如下操作:挑选出一对水壶，其中一个是红色的，另一个是蓝色的：将红色水壶中倒满水；再将水倒入到蓝色的水壶中。通过这个操作，可以判断出来这两只水壶的容量哪一个大，或者是一样大。假设这样的比较需要一个时间单位。你的目标是找出一个算法，它通过执行最少次数的比较，来确定分组和配对问题。记住不能直接比较两个红色的或两个蓝色的水壶。

    思路分析：
为了验证配对是否正确，我在设计水壶的数据结构时安排了两个属性：水壶的储水量和水壶的编号。配对结束后，表示红蓝水壶的数组中下标相同的水壶储水量相同，但编号不一定相同。
数据结构如下：
typedef struct Kettle
{
    int value;//水壶的储水量
    int number; //水壶的编号
} Kettle;

    为了确保每个红色水壶中所盛水的量都不一样，并且都有一个对应的蓝色水壶，我设计了一个函数为红壶和蓝壶随机初始化各不相同的储水量。代码如下：
void CreatKettle(Kettle BlueK[], Kettle RedK[], int n)
{
    int i, j, pos, temp;
   
    for (i=0; i<n; i++)
    {
        BlueK[i ].value = RedK[i ].value = BlueK[i ].number = RedK[i ].number = i + 1;
    }
   
    for (i=0; i<n; i++) //采用插入式洗牌，只改变储水量，不改变序号
    {
        pos = rand() % n;
        temp = BlueK[0].value;
        for (j=0; j<pos; j++)
            BlueK[j].value = BlueK[j+1].value;
        BlueK[pos].value = temp;
       
        pos = rand() % n;
        temp = RedK[0].value;
        for (j=0; j<pos; j++)
            RedK[j].value = RedK[j+1].value;
        RedK[pos].value = temp;
    }
}

版本一：简明易懂的版本
先介绍最简单的方法，拿出第1个红色水壶，然后从n个蓝色水壶中去配对，需要Θ(n)次比较，找到配对的蓝水壶后，将其交换到最左边，使其下标与对应红水壶的下标相同。
重复上述操作，直到所有的红色水壶都完成了配对。总的时间复杂度为Θ(n^2)。
代码如下：
void Match_1(Kettle BlueK[], Kettle RedK[], int n)//最简单的配对算法，时间复杂度为 Θ(n^2)
{
    int i, j;
   
    for (i=0; i<n; i++)
    {
        for (j=i; j<n; j++)
        {
            if (RedK[i ].value == BlueK[j].value)
            {
                Swap(&BlueK[j], &BlueK[i ]);
                break;
            }
        }
    }
}

void Swap(Kettle *a, Kettle *b)
{
    Kettle temp = *a;
    *a = *b;
    *b = temp;
}

版本二：在配对某个红壶的同时将蓝壶分成两堆，以便缩小下一次配对的范围
    在版本一中，每次为红壶配对，都要遍历未配对的所有蓝壶，效率较低。我们可以在配对某个红壶的同时将蓝壶分成两堆，以便缩小下一次配对的范围，提高效率。代码如下：
void Match_2(Kettle BlueK[], Kettle RedK[], int n)
{
    int i, pos;
   
    pos = Partition(BlueK, RedK[0].value, 0, n-1);//先配对第一个红壶
    Swap(&BlueK[0], &BlueK[pos]);//将已配对水壶交换到最左边
   
    for (i=1; i<n; i++)//依次配对剩下的红壶
    {
        if (RedK[i ].value < BlueK[i-1].value)
            pos = Partition(BlueK, RedK[i ].value, i, pos);//在[i,pos]范围内寻找配对
        else
            pos = Partition(BlueK, RedK[i ].value, pos+1, n-1);//在[pos+1, n-1]范围内寻找配对
       
        Swap(&BlueK[i ], &BlueK[pos]);//将已配对水壶交换到最左边
    }
}

    Match_2()用到一个分割函数Partition()，这是一个类似快速排序的分割函数，可以以值为x的元素为枢纽元，将数组K[]分成两部分，并返回枢纽元的位置。代码如下：
int Partition(Kettle K[], int x, int left, int right)
{
    while (left < right)
    {
        while (K[left].value < x)
            left++;
        while (K[right].value > x)
            right--;
           
        Swap(&K[left], &K[right]);
    }
   
    return left;
}

版本三：类快速排序算法
由于每个红色水壶中所盛水的量都不一样，并且都有一个对应的蓝色水壶，因此我们只需分别将其进行排序即可。但是不能直接比较同种颜色的水壶，只有颜色不一样的水壶才能进行比较，因此需要交叉比较，互为枢纽元素。
     整个排序过程中利用快速排序的思想，调用了版本二中的分割函数Partition()，采用交叉分割的方法，具体描述如下：
1. 从红色水壶序列中随机选择一个作为枢轴元素
2. 利用红色水壶枢轴元素RedK[posRedK]对蓝色水壶序列进行分割，并返回对应蓝色水壶的编号posBlueK。
3. 利用BlueK[posBlueK]对红色水壶序列进行进行分割，并返回对应红色水壶的编号posRedK，很显然此时posRedK ==posBlueK。
4．递归调用函数QuickMatch()，对分割好的序列进行配对。
算法的时间复杂度为O(nlgn)，最坏的情况下时间复杂度为O(n^2)。
代码如下：

void Match_3(Kettle BlueK[], Kettle RedK[], int n)//快速配对算法的驱动函数
{
    QuickMatch(BlueK, RedK, 0, n-1);
}

void QuickMatch(Kettle BlueK[], Kettle RedK[], int left, int right)//类似快速排序的快速配对算法
{
    int posBlueK, posRedK;
   
    if (left < right)
    {
        posRedK = rand() % (right-left+1) + left; //从红色水壶中随机选择一个作为枢轴元素
        posBlueK = Partition(BlueK, RedK[posRedK].value, left, right);//将蓝壶分成两堆，并返回配对蓝壶的编号
        posRedK = Partition(RedK, BlueK[posBlueK].value, left, right); //将红壶分成两堆，并返回配对红壶的编号
        //递归调用函数QuickMatch()，对分割好的序列进行配对
        QuickMatch(BlueK, RedK, left, posRedK-1);
        QuickMatch(BlueK, RedK, posRedK+1, right);
    }
}

测试主函数：
int main(void)
{
    Kettle BlueK[MAXSIZE], RedK[MAXSIZE];
    int i, n = 6;
   
    CreatKettle(BlueK, RedK, n);
    Print(BlueK, RedK, n);
Match_1(BlueK, RedK, n);
// Match_2(BlueK, RedK, n);
// Match_3(BlueK, RedK, n);
    Print(BlueK, RedK, n);
   
    return 0;
}

输出数据函数：
void Print(Kettle BlueK[], Kettle RedK[], int n)
{
    int i;
   
    for (i=0; i<n; i++)
    {
        printf ("BlueK[%d]: %d, %d  RedK[%d]: %d, %d\n", i, BlueK[i ].number, BlueK[i ].value, i, RedK[i ].number, RedK[i ].value);
    }
    printf("\n");
}

    巧若拙（欢迎转载，但请注明出处：http://blog.csdn.net/qiaoruozhuo）

    本文只探究迷宫寻址中深度优先搜索的递归和非递归算法比较，其他相关代码详见《迷宫问题（巧若拙）》http://blog.csdn.net/qiaoruozhuo/article/details/41020745

    深度优先搜索的递归算法是很容易实现的，只需设置一个驱动函数，然后递归调用子函数就可以了。
代码如下：
int DeepSearchWay()//寻找路径：深度搜索
{
    CopyMiGong();
     
    if (c_map[begin[0]][begin[1]] == OPEN && Search(begin[0], begin[1]))
    {
        c_map[begin[0]][begin[1]] = ROAD;
        return true;
    }
       
    return false;
}

int Search(int x, int y)//深度搜索递归子函数
{
    int i;

       c_map[x][y] = PASSED; 
    if (IsEnd(x, y)) //找到出口
    {
        c_map[x][y] = ROAD; 
        return true;
    }
     
    for (i=0; i<4; i++)//判断当前路径点四周是否可通过
    {
        if (c_map[x+zx[ i]][y+zy[i ]] == OPEN && Search(x+zx[i ], y+zy[i ]))
        {
            c_map[x][y] = ROAD;
            return true;
          }
   }
   return false;
}

深度优先搜索的非递归算法需要人工设置一个栈，把搜索过的点存储到栈中，走不通的点就退栈，找到出口就退出函数。
代码如下：
int DeepSearchWay_2()//寻找路径：深度搜索
{
    int x, y;
    int top = 0; //栈顶指针
    int sum = 0;//累积搜索过的点数量

    CopyMiGong();
    way[0].x = begin[0];
    way[0].y = begin[1];
    way[0].pre = 0;
    c_map[way[0].x][way[0].y] = PASSED; //该点已走过

    while (top >= 0)
    {
          if (way[top].pre < 4)
          {
            x = way[top].x + zx[way[top].pre];
            y = way[top].y + zy[way[top].pre];

            if (c_map[x][y] == OPEN)//如果某个方向可通过，将该点纳入栈
            {
                sum++;
                top++;
                way[top].x = x;
                way[top].y = y;
                way[top].pre = 0;
                c_map[x][y] = PASSED;
               
                if (IsEnd(x, y)) //找到出口
                {
                    PutStack(top); //把栈路径显示到迷宫中
                    printf("\n深度优先搜索可行路径，总共搜索过%d个点\n", sum);
                    return true;
                }
            }
            else  //否则换个方向
                way[top].pre++;
        }
        else
        {
               top--;
           }
    }
    return false;
}

void PutStack(int top) //把栈路径显示到迷宫中
{
    CopyMiGong();

       while (top >= 0)
    {
        c_map[way[top].x][way[top].y] = ROAD;
        top--;
    }
}

深度优先搜索最短路径，除了存储当前遍历结点的栈以外，需要额外设置一个栈存储最短路径。为了避免重复搜索某顶点，我为各个顶点设置了路径长度，只有当前路径长度小于原来的路径长度时，才搜索该顶点。
找到出口后并不退出函数，若当前路径长度小于最小路径长度，则更新最小路径长度，否则直接退栈进入上一点，继续搜索。
直到所有可能的路径被搜索完毕，输出最短路径。
代码如下：
int DeepSearchWay_3()//寻找路径：深度搜索（最短路径）
{
    int x, y, i, j;
    int top = 0; //栈顶指针
    int pathLen[M+2][N+2] = {0};
    struct stype shortWay[M*N];
    int flag = false; //标记是否能到达终点 
    int sum = 0;//累积搜索过的点数量
   
    for (x=0; x<M+2; x++) //设置各点初始路径长度均为最大值
        for (y=0; y<N+2; y++)
            pathLen[x][y] = MAXLEN;

    CopyMiGong();
    minLen = MAXLEN;  //最短路径
    way[0].x = begin[0];
    way[0].y = begin[1];
    way[0].pre = 0;
    pathLen[begin[0]][begin[1]] = 0;

    while (top >= 0)
    {
          if (way[top].pre < 4)
          {
            x = way[top].x + zx[way[top].pre];
            y = way[top].y + zy[way[top].pre];

            if (c_map[x][y] == OPEN && pathLen[x][y] > top+1)//如果某个方向可通过，且为最短路径，将该点纳入栈
            {
                sum++;
                top++;
                way[top].x = x;
                way[top].y = y;
                way[top].pre = 0;
                pathLen[x][y] = top;
                if (IsEnd(x, y)) //找到出口
                {
                    if (top < minLen)
                    {
                        minLen = top;
                        for (i=0; i<=top; i++)
                        {
                            shortWay[i ] = way[i ];
                        }
                       
                    }

                    flag = true;
                    top--;
                }
            }
            else  //否则换个方向
                way[top].pre++;
        }
        else
        {
               top--;
           }
    }
   
    if (flag)
    {
        for (i=0; i<=minLen; i++)
        {
            way[i ] = shortWay[i ];
        }
        PutStack(minLen); //把栈路径显示到迷宫中
    }
   
    printf("\n深度优先搜索最短路径，总共搜索过%d个点\n", sum);
       
    return flag;
}

题目描述：
假设有n个变量（1<=n<=26，变量名用单个小写字母表示），还有m个二元组（u,v），分别表示变量u小于v。那么，所有变量从小到大排列起来应该是什么样子的呢？
    例如有4个变量a,b,c,d，若以知a<b,c<b,d<c，则这4个变量的排序可能是a<d<c<b。尽管还有可能其他的可能，你只需找出其中的一个即可。
输入：
输入为一个字符串，其中包含N+N个字符，依次表示N个关系式（1<=N<=100000），例如序列"abcbdc"表示a<b,c<b,d<c.
输出：
给出一个字符串，其中存储了一个符合要求的变量序列，例如，字符串"adcb"表示a<d<c<b。
   
算法分析：
    这是典型的拓扑排序问题。先简单科普一下，所谓拓扑排序，是指将一个有向无环图G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若<u，v> ∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(TopoiSicai Order)的序列，简称拓扑序列。
    我们先将变量作为顶点输入到图数据结构中。表示图的数据结构有多种，由于本题对应的是稀疏图，应该以边为主要研究对象，所以可以把数据结构设置为邻接表或边表集。
    我们先来看邻接表数据结构：
typedef char VertexType; //顶点类型由用户自定义
typedef int EdgeType; //边上的权值类型由用户自定义

typedef struct EdgeNode{ //边表结点
    int adjvex;  //邻接点域，存储该顶点对应的下标
//    EdgeType weight; //权值，对于非网图可以不需要
    struct EdgeNode *next; //链域，指向下一个邻接点
} EdgeNode;

typedef struct VertexNode{ //顶点表结点
    VertexType data; //顶点域，存储顶点信息
    int in;   //存储顶点入度的数量
    EdgeNode *firstEdge; //边表头指针
} VertexNode;

由于变量名用单个小写字母表示，我们可以设置一个大小为26的数组存储顶点；又由于26个字母不见得都会出现，故我们设置一个全局变量int book[MAXM] = {0}; 用来标记某字母是否出现。
首先创建一个图，读入顶点和边信息。代码如下：
/*
函数名称：CreateGraph
函数功能：把顶点和边信息读入到表示图的邻接表中
输入变量：char *data：存储了N个关系式的字符串
          VertexNode *GL ： 顶点表数组
输出变量：表示图的顶点表数组
返回值：int ：顶点数量
*/
int CreateGraph(char *data, VertexNode *GL)
{
    int i, u, v;
    int count = 0;//记录顶点数量
    EdgeNode *e;
   
    for (i=0; i<MAXM; i++)//初始化图
    {
        GL[i ].data = i + 'a';
        GL[i ].in = 0;
        GL[i ].firstEdge = NULL;
        book[i ] = 0;
    }
   
    for (i=0; data[i ]!='\0'; i+=2)//每次读取两个变量 
    {
        u = data[ i] - 'a'; //字母转换为数字，'a'对应0，'b'对应1，以此类推
        v = data[i+1] - 'a';
        book[u ] = book[v] = 1;
       
        e = (EdgeNode*)malloc(sizeof(EdgeNode)); //采用头插法插入边表结点
        if (!e)
        {
            puts("Error");
            exit(1);
        }
        e->adjvex = v;
        e->next = GL[u ].firstEdge;
        GL[u ].firstEdge = e;
       
        GL[v].in++;
    }
   
    for (i=0; i<MAXM; i++)//计算顶点数量
    {
        if (book[i ] != 0)
            count++;
    }
   
    return count;
}

拓扑排序算法其实非常简单，只需要搜索入度为0的弧尾顶点，然后将其对应的弧头顶点入度减1，如果该弧头顶点入度也变成了0，就将其存储到栈（或队列）中。搜索的方法有深度优先和广度优先两种。代码分别如下：
/*
函数名称：TopoLogicalSort_DFS
函数功能：拓扑排序，采用深度优先搜索获取拓扑序列
输入变量：char *topo：用来存储拓扑序列的字符串
          VertexNode *GL ： 顶点表数组
          int n：顶点个数
输出变量：用来存储拓扑序列的字符串
返回值：int ：拓扑排序成功返回真，若存在环则返回假
*/
int TopoLogicalSort_DFS(char *topo, VertexNode *GL, int n)
{
    int i, u, v, top;
    int count = 0; //用于统计输出顶点的个数
    EdgeNode *e;
    int Stack[MAXM];
   
    for (top=i=0; i<MAXM; i++)//将入度为0的顶点入栈
    {
        if (book[i ] != 0 && GL[i ].in == 0)
        {
            Stack[top++] = i;
        }
    }
   
    while (top > 0)//采用深度优先搜索获取拓扑序列
    {
        u = Stack[--top];
        topo[count++] = u + 'a';
       
        for (e=GL[u ].firstEdge; e!=NULL; e=e->next)//将u的邻接点入度减1，并将入度为0的顶点入栈
        {
            v = e->adjvex;
            if (--GL[v].in == 0)
                Stack[top++] = v;
        }
    }
    topo[count] = '\0';
   
    return (count == n);//如果count小于顶点数，说明存在环
}

/*
函数名称：TopoLogicalSort_BFS
函数功能：拓扑排序，采用广度优先搜索获取拓扑序列
输入变量：char *topo：用来存储拓扑序列的字符串
          VertexNode *GL ： 顶点表数组
          int n：顶点个数
输出变量：用来存储拓扑序列的字符串
返回值：int ：拓扑排序成功返回真，若存在环则返回假
*/
int TopoLogicalSort_BFS(char *topo, VertexNode *GL, int n)
{
    int i, u, v, front, rear;
    EdgeNode *e;
   
    front = rear = 0;
    for (i=0; i<MAXM; i++)//将入度为0的顶点入栈
    {
        if (book[i ] != 0 && GL[i ].in == 0)
        {
            topo[rear++] = i + 'a';
        }
    }
   
    while (front < rear)//采用广度优先搜索获取拓扑序列
    {
        u = topo[front++] - 'a';
       
        for (e=GL[u ].firstEdge; e!=NULL; e=e->next)//将u的邻接点入度减1，并将入度为0的顶点入栈
        {
            v = e->adjvex;
            if (--GL[v].in == 0)
                topo[rear++] = v + 'a';
        }
    }
    topo[rear] = '\0';
   
    return (rear == n);//如果count小于顶点数，说明存在环
}

我们也可以用边表集来表示图，数据结构如下：
typedef struct Edge{ //边集数组
    int u, v; //弧尾和弧头
    int next; //指向同一个弧尾的下一条边
//    EdgeType weight; //权值，对于非网图可以不需要
} EdgeLib;

为了表示顶点信息，我们还需要设置两个数组：int In[MAXM], first[MAXM]; //分别存储顶点的入度和第一条边信息。
边表集实现拓扑排序的算法和邻接表非常相似，也是先读入图的顶点和边信息，然后进行拓扑排序。代码如下：
/*
函数名称：CreateGraph_2
函数功能：把顶点和边信息读入到表示图的边表集中
输入变量：char *data：存储了N个关系式的字符串
          int In[]：存储了顶点的入度信息
          int first[]：指向以该顶点为弧尾的第一条边
          EdgeLib edge[]：存储了边信息的边表集
输出变量：表示图的边表集数组
返回值：int ：顶点数量
*/
int CreateGraph_2(char *data, int In[], int first[], EdgeLib edge[])//创建一个图
{
    int i, j;
    int count = 0;//记录顶点数量
   
    for (i=0; i<MAXM; i++)//初始化图
    {
        first[ i ] = -1;
        book[ i ] = 0;
        In[ i ] = 0;
    }
   
    for (j=i=0; data[ i ]!='\0'; i+=2,j++)//每次读取两个变量 
    {
        edge[j].u = data[i ] - 'a'; //字母转换为数字，'a'对应0，'b'对应1，以此类推
        edge[j].v = data[i+1] - 'a';
        book[edge[j].u] = book[edge[j].v] = 1;
       
        edge[j].next = first[edge[j].u];
        first[edge[j].u] = j;
        In[edge[j].v]++;
    }
   
    for (i=0; i<MAXM; i++)//计算顶点数量
    {
        if (book[i ] != 0)
            count++;
    }
   
    return count;
}

/*
函数名称：TopoLogicalSort
函数功能：拓扑排序，采用广度优先搜索获取拓扑序列
输入变量：char *topo：用来存储拓扑序列的字符串
          EdgeLib edge[]：存储了边信息的边表集
          int In[]：存储了顶点的入度信息
          int first[]：指向以该顶点为弧尾的第一条边
          int n：顶点个数
输出变量：用来存储拓扑序列的字符串
返回值：int ：拓扑排序成功返回真，若存在环则返回假
*/
int TopoLogicalSort(char *topo, EdgeLib edge[], int In[], int first[], int n)
{
    int i, u, front, rear;
   
    front = rear = 0;
    for (i=0; i<MAXM; i++)//将入度为0的顶点入栈
    {
        if (book[i ] != 0 && In[i ] == 0)
        {
            topo[rear++] = i + 'a';
        }
    }
   
    while (front < rear)//采用广度优先搜索获取拓扑序列
    {
        u = topo[front++] - 'a';
        for (i=first[u ]; i!=-1; i=edge[i ].next)
        {
            if (--In[edge[i ].v] == 0)
                topo[rear++] = edge[i ].v + 'a';
        }
    }
    topo[rear] = '\0';
   
    return (rear == n);//如果count小于顶点数，说明存在环
}

这里只给出了相关函数，完整的测试代码请到巧若拙的博客（http://blog.csdn.net/qiaoruozhuo）查看。

寄存器定义
  寄存器是中央处理器内的组成部份。寄存器是有限存贮容量的高速存贮部件，它们可用来暂存指令、数据和位址。在中央处理器的控制部件中，包含的寄存器有指令寄存器(IR)和程序计数器(PC)。在中央处理器的算术及逻辑部件中，包含的寄存器有累加器(ACC)。
  寄存器是内存阶层中的最顶端，也是系统获得操作资料的最快速途径。寄存器通常都是以他们可以保存的位元数量来估量，举例来说，一个 “8 位元寄存器”或 “32 位元寄存器”。寄存器现在都以寄存器档案的方式来实作，但是他们也可能使用单独的正反器、高速的核心内存、薄膜内存以及在数种机器上的其他方式来实作出来。
  寄存器通常都用来意指由一个指令之输出或输入可以直接索引到的暂存器群组。更适当的是称他们为 “架构寄存器”。
  例如，x86 指令及定义八个 32 位元寄存器的集合，但一个实作 x86 指令集的 CPU 可以包含比八个更多的寄存器。
  寄存器是CPU内部的元件，寄存器拥有非常高的读写速度，所以在寄存器之间的数据传送非常快。
[编辑本段]
寄存器用途
  1.可将寄存器内的数据执行算术及逻辑运算；
  2.存于寄存器内的地址可用来指向内存的某个位置，即寻址；
  3.可以用来读写数据到电脑的周边设备。
[编辑本段]
数据寄存器
  8086 有14个16位寄存器，这14个寄存器按其用途可分为(1)通用寄存器、(2)指令指针、(3)标志寄存器和(4)段寄存器等4类。
  (1)通用寄存器有8个, 又可以分成2组,一组是数据寄存器(4个),另一组是指针寄存器及变址寄存器(4个).
  数据寄存器分为:
  AH&AL＝AX(accumulator)：累加寄存器，常用于运算;在乘除等指令中指定用来存放操作数,另外,所有的I/O指令都使用这一寄存器与外界设备传送数据.
  BH&BL＝BX(base)：基址寄存器，常用于地址索引；
  CH&CL＝CX(count)：计数寄存器，常用于计数；常用于保存计算值,如在移位指令,循环(loop)和串处理指令中用作隐含的计数器.
  DH&DL＝DX(data)：数据寄存器，常用于数据传递。
  他们的特点是,这4个16位的寄存器可以分为高8位: AH, BH, CH, DH.以及低八位：AL,BL,CL,DL。这2组8位寄存器可以分别寻址，并单独使用。
  另一组是指针寄存器和变址寄存器，包括：
  SP（Stack Pointer）：堆栈指针，与SS配合使用，可指向目前的堆栈位置；
  BP（Base Pointer）：基址指针寄存器，可用作SS的一个相对基址位置；
  SI（Source Index）：源变址寄存器可用来存放相对于DS段之源变址指针；
  DI（Destination Index）：目的变址寄存器，可用来存放相对于 ES 段之目的变址指针。
  这4个16位寄存器只能按16位进行存取操作，主要用来形成操作数的地址，用于堆栈操作和变址运算中计算操作数的有效地址。
  (2) 指令指针IP(Instruction Pointer)
  指令指针IP是一个16位专用寄存器，它指向当前需要取出的指令字节，当BIU从内存中取出一个指令字节后，IP就自动加1，指向下一个指令字节。注意，IP指向的是指令地址            的段内地址偏移量，又称偏移地址(Offset Address)或有效地址(EA，Effective Address)。
  (3)标志寄存器FR(Flag Register)
  8086有一个18位的标志寄存器FR，在FR中有意义的有9位，其中6位是状态位，3位是控制位。
  OF： 溢出标志位OF用于反映有符号数加减运算所得结果是否溢出。如果运算结果超过当前运算位数所能表示的范围，则称为溢出，OF的值被置为1，否则，OF的值被清为0。
  DF：方向标志DF位用来决定在串操作指令执行时有关指针寄存器发生调整的方向。
  IF：中断允许标志IF位用来决定CPU是否响应CPU外部的可屏蔽中断发出的中断请求。但不管该标志为何值，CPU都必须响应CPU外部的不可屏蔽中断所发出的中断请求，以及CPU内部产生的中断请求。具体规定如下：
  (1)、当IF=1时，CPU可以响应CPU外部的可屏蔽中断发出的中断请求；
  (2)、当IF=0时，CPU不响应CPU外部的可屏蔽中断发出的中断请求。
  TF：跟踪标志TF。该标志可用于程序调试。TF标志没有专门的指令来设置或清楚。
  （1）如果TF=1，则CPU处于单步执行指令的工作方式，此时每执行完一条指令，就显示CPU内各个寄存器的当前值及CPU将要执行的下一条指令。
  （2）如果TF=0，则处于连续工作模式。
  SF：符号标志SF用来反映运算结果的符号位，它与运算结果的最高位相同。在微机系统中，有符号数采用补码表示法，所以，SF也就反映运算结果的正负号。运算结果为正数时，SF的值为0，否则其值为1。
  ZF： 零标志ZF用来反映运算结果是否为0。如果运算结果为0，则其值为1，否则其值为0。在判断运算结果是否为0时，可使用此标志位。
  AF：下列情况下，辅助进位标志AF的值被置为1，否则其值为0：
  (1)、在字操作时，发生低字节向高字节进位或借位时；
  (2)、在字节操作时，发生低4位向高4位进位或借位时。
  PF：奇偶标志PF用于反映运算结果中“1”的个数的奇偶性。如果“1”的个数为偶数，则PF的值为1，否则其值为0。
  CF：进位标志CF主要用来反映运算是否产生进位或借位。如果运算结果的最高位产生了一个进位或借位，那么，其值为1，否则其值为0。)
  4)段寄存器(Segment Register)
  为了运用所有的内存空间，8086设定了四个段寄存器，专门用来保存段地址：
  CS（Code Segment）：代码段寄存器；
  DS（Data Segment）：数据段寄存器；
  SS（Stack Segment）：堆栈段寄存器；
  ES（Extra Segment）：附加段寄存器。
  当一个程序要执行时，就要决定程序代码、数据和堆栈各要用到内存的哪些位置，通过设定段寄存器 CS，DS，SS 来指向这些起始位置。通常是将DS固定，而根据需要修改CS。所以，程序可以在可寻址空间小于64K的情况下被写成任意大小。 所以，程序和其数据组合起来的大小，限制在DS 所指的64K内，这就是COM文件不得大于64K的原因。8086以内存做为战场，用寄存器做为军事基地，以加速工作。
  以上是8086寄存器的整体概况, 自80386开始，PC进入32bit时代，其寻址方式，寄存器大小，功能等都发生了变化。
  =============================以下是80386的寄存器的一些资料======================================
  寄存器都是32-bits宽。
  A、通用寄存器
  下面介绍通用寄存器及其习惯用法。顾名思义，通用寄存器是那些你可以根据自己的意愿使用的寄存器，修改他们的值通常不会对计算机的运行造成很大的影响。通用寄存器最多的用途是计算。
  EAX：通用寄存器。相对其他寄存器，在进行运算方面比较常用。在保护模式中，也可以作为内存偏移指针（此时，DS作为段 寄存器或选择器）
  EBX：通用寄存器。通常作为内存偏移指针使用（相对于EAX、ECX、EDX），DS是默认的段寄存器或选择器。在保护模式中，同样可以起这个作用。
  ECX：通用寄存器。通常用于特定指令的计数。在保护模式中，也可以作为内存偏移指针（此时，DS作为 寄存器或段选择器）。
  EDX：通用寄存器。在某些运算中作为EAX的溢出寄存器（例如乘、除）。在保护模式中，也可以作为内存偏移指针（此时，DS作为段 寄存器或选择器）。
  同AX分为AH&AL一样，上述寄存器包括对应的16-bit分组和8-bit分组。
  B、用作内存指针的特殊寄存器
  ESI：通常在内存操作指令中作为“源地址指针”使用。当然，ESI可以被装入任意的数值，但通常没有人把它当作通用寄存器来用。DS是默认段寄存器或选择器。
  EDI：通常在内存操作指令中作为“目的地址指针”使用。当然，EDI也可以被装入任意的数值，但通常没有人把它当作通用寄存器来用。DS是默认段寄存器或选择器。
  EBP：这也是一个作为指针的寄存器。通常，它被高级语言编译器用以建造‘堆栈帧'来保存函数或过程的局部变量，不过，还是那句话，你可以在其中保存你希望的任何数据。SS是它的默认段寄存器或选择器。
  注意，这三个寄存器没有对应的8-bit分组。换言之，你可以通过SI、DI、BP作为别名访问他们的低16位，却没有办法直接访问他们的低8位。
  C、段选择器：
  实模式下的段寄存器到保护模式下摇身一变就成了选择器。不同的是，实模式下的“段寄存器”是16-bit的，而保护模式下的选择器是32-bit的。
  CS 代码段，或代码选择器。同IP寄存器(稍后介绍)一同指向当前正在执行的那个地址。处理器执行时从这个寄存器指向的段（实模式）或内存（保护模式）中获取指令。除了跳转或其他分支指令之外，你无法修改这个寄存器的内容。
  DS 数据段，或数据选择器。这个寄存器的低16 bit连同ESI一同指向的指令将要处理的内存。同时，所有的内存操作指令 默认情况下都用它指定操作段(实模式)或内存(作为选择器，在保护模式。这个寄存器可以被装入任意数值，然而在这么做的时候需要小心一些。方法是，首先把数据送给AX，然后再把它从AX传送给DS(当然，也可以通过堆栈来做).
  ES 附加段，或附加选择器。这个寄存器的低16 bit连同EDI一同指向的指令将要处理的内存。同样的，这个寄存器可以被装入任意数值，方法和DS类似。
  FS F段或F选择器(推测F可能是Free?)。可以用这个寄存器作为默认段寄存器或选择器的一个替代品。它可以被装入任何数值，方法和DS类似。
  GS G段或G选择器(G的意义和F一样，没有在Intel的文档中解释)。它和FS几乎完全一样。
  SS 堆栈段或堆栈选择器。这个寄存器的低16 bit连同ESP一同指向下一次堆栈操作(push和pop)所要使用的堆栈地址。这个寄存器也可以被装入任意数值，你可以通过入栈和出栈操作来给他赋值，不过由于堆栈对于很多操作有很重要的意义，因此，不正确的修改有可能造成对堆栈的破坏。
  * 注意 一定不要在初学汇编的阶段把这些寄存器弄混。他们非常重要，而一旦你掌握了他们，你就可以对他们做任意的操作了。段寄存器，或选择器，在没有指定的情况下都是使用默认的那个。这句话在现在看来可能有点稀里糊涂，不过你很快就会在后面知道如何去做。
  指令指针寄存器：
  EIP 这个寄存器非常的重要。这是一个32位宽的寄存器 ，同CS一同指向即将执行的那条指令的地址。不能够直接修改这个寄存器的值，修改它的唯一方法是跳转或分支指令。(CS是默认的段或选择器)
  上面是最基本的寄存器。下面是一些其他的寄存器，你甚至可能没有听说过它们。(都是32位宽)：
  CR0, CR2, CR3(控制寄存器)。举一个例子，CR0的作用是切换实模式和保护模式。
  还有其他一些寄存器，D0, D1, D2, D3, D6和D7(调试寄存器)。他们可以作为调试器的硬件支持来设置条件断点。
  TR3, TR4, TR5, TR6 和 TR? 寄存器(测试寄存器)用于某些条件测试。
[编辑本段]
寄存器分类
  数据寄存器 - 用来储存整数数字（参考以下的浮点寄存器）。在某些简单/旧的 CPU，特别的数据寄存器是累加器，作为数学计算之用。
  地址寄存器 - 持有存储器地址，以及用来访问存储器。在某些简单/旧的CPU里，特别的地址寄存器是索引寄存器（可能出现一个或多个）。
  通用目的寄存器 （GPRs） - 可以保存数据或地址两者，也就是说他们是结合 数据/地址 寄存器的功用。
  浮点寄存器 （FPRs） - 用来储存浮点数字。
  常数寄存器 - 用来持有只读的数值（例如 0、1、圆周率等等）。
  向量寄存器 - 用来储存由向量处理器运行SIMD（Single Instruction, Multiple Data）指令所得到的数据。
  特殊目的寄存器 - 储存CPU内部的数据，像是程序计数器（或称为指令指针），堆栈寄存器，以及状态寄存器（或称微处理器状态字组）。
  指令寄存器（instruction register） - 储存现在正在被运行的指令
  索引寄存器（index register） - 是在程序运行实用来更改运算对象地址之用。
  在某些架构下，模式指示寄存器（也称为“机器指示寄存器”）储存和设置跟处理器自己有关的数据。由于他们的意图目的是附加到特定处理器的设计，因此他们并不被预期会成微处理器世代之间保留的标准。
  有关从 随机存取存储器 提取信息的寄存器与CPU（位于不同芯片的储存寄存器集合）
  存储器缓冲寄存器（Memory buffer register）
  存储器数据寄存器（Memory data register）
  存储器地址寄存器（Memory address register）
  存储器型态范围寄存器（Memory Type Range Registers）

译注: 备注后面跟随的数字即书中的页码
备注 viii (Notes viii)

Steele, Guy L., Jr., Scott E. Fahlman, Richard P. Gabriel, David A. Moon, Daniel L. Weinreb , Daniel G. Bobrow, Linda G. DeMichiel, Sonya E. Keene, Gregor Kiczales, Crispin Perdue, Kent M. Pitman, Richard C. Waters, 以及 John L White。Common Lisp: the Language, 2nd Edition. Digital Press, Bedford (MA), 1990.
备注 1 (Notes 1)

McCarthy, John.Recursive Functions of Symbolic Expressions and their Computation by Machine, Part I. CACM, 3:4 (April 1960), pp. 184-195.

McCarthy, John.History of Lisp. In Wexelblat, Richard L. (Ed.) Histroy of Programming Languages. Academic Press, New York, 1981, pp. 173-197.
备注 3 (Notes 3)

Brooks, Frederick P. The Mythical Man-Month. Addison-Wesley, Reading (MA), 1975, p. 16.

Rapid prototyping is not just a way to write programs faster or better. It is a way to write programs that otherwise might not get written at all. Even the most ambitious people shrink from big undertakings. It’s easier to start something if one can convince oneself (however speciously) that it won’t be too much work. That’s why so many big things have begun as small things. Rapid prototyping lets us start small.
备注 4 (Notes 4)

同上， 第 i 页。
备注 5 (Notes 5)

Murray, Peter and Linda. The Art of the Renaissance. Thames and Hudson, London, 1963, p.85.
备注 5-2 (Notes 5-2)

Janson, W.J. History of Art, 3rd Edition. Abrams, New York, 1986, p. 374.

The analogy applies, of course, only to paintings done on panels and later on canvases. Well-paintings continued to be done in fresco. Nor do I mean to suggest that painting styles were driven by technological change; the opposite seems more nearly true.
备注 12 (Notes 12)

car 与 cdr 的名字来自最早的 Lisp 实现里，列表内部的表示法：car 代表“寄存器位址部分的内容”、cdr 代表“寄存器递减部分的内容”。
备注 17 (Notes 17)

对递归概念有困扰的读者，可以查阅下列的书籍：

Touretzky, David S. Common Lisp: A Gentle Introduction to Symbolic Computation. Benjamin/Cummings, Redwood City (CA), 1990, Chapter 8.

Friedman, Daniel P., and Matthias Felleisen. The Little Lisper. MIT Press, Cambridge, 1987.

譯註：這本書有再版，可在這裡找到。
备注 26 (Notes 26)

In ANSI Common Lisp there is also a lambda macro that allows you to write (lambda (x) x) for #'(lambda (x) x) . Since the use of this macro obscures the symmetry between lambda expressions and symbolic function names (where you still have to use sharp-quote), it yields a specious sort of elegance at best.
备注 28 (Notes 28)

Gabriel, Richard P. Lisp Good News, Bad News, How to Win BigAI Expert, June 1991, p.34.
备注 46 (Notes 46)

Another thing to be aware of when using sort: it does not guarantee to preserve the order of elements judged equal by the comparison function. For example, if you sort (2 1 1.0) by < , a valid Common Lisp implementation could return either (1 1.0 2) or (1.0 1 2) . To preserve as much as possible of the original order, use instead the slower stable-sort (also destructive), which could only return the first value.
备注 61 (Notes 61)

A lot has been said about the benefits of comments, and little or nothing about their cost. But they do have a cost. Good code, like good prose, comes from constant rewriting. To evolve, code must be malleable and compact. Interlinear comments make programs stiff and diffuse, and so inhibit the evolution of what they describe.
备注 62 (Notes 62)

Though most implementations use the ASCII character set, the only ordering that Common Lisp guarantees for characters is as follows: the 26 lowercase letters are in alphabetically ascending order, as are the uppercase letters, and the digits from 0 to 9.
备注 76 (Notes 76)

The standard way to implement a priority queue is to use a structure called a heap. See: Sedgewick, Robert. Algorithms. Addison-Wesley, Reading (MA), 1988.
备注 81 (Notes 81)

The definition of progn sounds a lot like the evaluation rule for Common Lisp function calls (page 9). Though progn is a special operator, we could define a similar function:

(defun our-progn (ftrest args)
  (car (last args)))

This would be horribly inefficient, but functionally equivalent to the real progn if the last argument returned exactly one value.
备注 84 (Notes 84)

The analogy to a lambda expression breaks down if the variable names are symbols that have special meanings in a parameter list. For example,

(let ((&key 1) (&optional 2)))

is correct, but the corresponding lambda expression

((lambda (ftkey ftoptional)) 1 2)

is not. The same problem arises if you try to define do in terms of labels . Thanks to David Kuznick for pointing this out.
备注 89 (Notes 89)

Steele, Guy L., Jr., and Richard P. Gabriel. The Evolution of Lisp. ACM SIGPLANNotices 28:3 (March 1993). The example in the quoted passage was translated from Scheme into Common Lisp.
备注 91 (Notes 91)

To make the time look the way people expect, you would want to ensure that minutes and seconds are represented with two digits, as in:

(defun get-time-string ()
  (multiple-value-bind (s m h) (get-decoded-time)
    (format nil "~A:~2,,,'0@A:~2,,,'O@A" h m s)))

备注 94 (Notes 94)

In a letter of March 18 (old style) 1751, Chesterfield writes:

“It was notorious, that the Julian Calendar was erroneous, and had overcharged the solar year with eleven days. Pope Gregory the Thirteenth corrected this error [in 1582]; his reformed calendar was immediately received by all the Catholic powers of Europe, and afterwards adopted by all the Protestant ones, except Russia, Sweden, and England. It was not, in my opinion, very honourable for England to remain in a gross and avowed error, especially in such company; the inconveniency of it was likewise felt by all those who had foreign correspondences, whether political or mercantile. I determined, therefore, to attempt the reformation; I consulted the best lawyers, and the most skillful astronomers, and we cooked up a bill for that purpose. But then my difficulty began; I was to bring in this bill, which was necessarily composed of law jargon and astronomical calculations, to both of which I am an utter stranger. However, it was absolutely necessary to make the House of Lords think that I knew something of the matter; and also to make them believe that they knew something of it themselves, which they do not. For my own part, I could just as soon have talked Celtic or Sclavonian to them, as astronomy, and they would have understood me full as well; so I resolved to do better than speak to the purpose, and to please instead of informing them. I gave them, therefore, only an historical account of calendars, from the Egyptian down to the Gregorian, amusing them now and then with little episodes; but I was particularly attentive to the choice of my words, to the harmony and roundness of my periods, to my elocution, to my action. This succeeded, and ever will succeed; they thought I informed them, because I pleased them; and many of them said I had made the whole very clear to them; when, God knows, I had not even attempted it.”

See: Roberts, David (Ed.) Lord Chesterfield’s Letters. Oxford University Press, Oxford, 1992.
备注 95 (Notes 95)

In Common Lisp, a universal time is an integer representing the number of seconds since the beginning of 1900. The functions encode-universal-time and decode-universal-time translate dates into and out of this format. So for dates after 1900, there is a simpler way to do date arithmetic in Common Lisp:

(defun num->date (n)
  (multiple-value-bind (ig no re d m y)
                       (decode-universal-time n)
    (values d m y)))

(defun date->num (d m y)
  (encode-universal-time 1 0 0 d m y))

(defun date+ (d m y n)
  (num->date (+ (date->num d m y)
                (* 60 60 24 n))))

Besides the range limit, this approach has the disadvantage that dates tend not to be fixnums.
备注 100 (Notes 100)

Although a call to setf can usually be understood as a reference to a particular place, the underlying machinery is more general. Suppose that a marble is a structure with a single field called color:

(defstruct marble
  color)

The following function takes a list of marbles and returns their color, if they all have the same color, or n i l if they have different colors:

(defun uniform-color (1st)
  (let ((c (marble-color (car 1st))))
    (dolist (m (cdr 1st))
      (unless (eql (marble-color m) c)
        (return nil)))
    c))

Although uniform-color does not refer to a particular place, it is both reasonable and possible to have a call to it as the first argument to setf . Having defined

(defun (setf uniform-color) (val 1st)
  (dolist (m 1st)
    (setf (marble-color m) val)))

we can say

(setf (uniform-color *marbles*) 'red)

to make the color of each element of *marbles* be red.
备注 100-2 (Notes 100-2)

In older Common Lisp implementations, you have to use defsetf to define how a call should be treated when it appears as the first argument to setf. Be careful when translating, because the parameter representing the new value comes last in the definition of a function whose name is given as the second argument to defsetf . That is, the call

(defun (setf primo) (val 1st) (setf (car 1st) val))

is equivalent to

(defsetf primo set-primo)

(defun set-primo (1st val) (setf (car 1st) val))

备注 106 (Notes 106)

C, for example, lets you pass a pointer to a function, but there’s less you can pass in a function (because C doesn’t have closures) and less the recipient can do with it (because C has no equivalent of apply). What’s more, you are in principle supposed to declare the type of the return value of the function you pass a pointer to. How, then, could you write map-int or filter , which work for functions that return anything? You couldn’t, really. You would have to suppress the type-checking of arguments and return values, which is dangerous, and even so would probably only be practical for 32-bit values.
备注 109 (Notes 109)

For many examples of the versatility of closures, see: Abelson, Harold, and Gerald Jay Sussman, with Julie Sussman.Structure and Interpretation of Computer Programs. MIT Press, Cambridge, 1985.
备注 109-2 (Notes 109-2)

For more information about Dylan, see: Shalit, Andrew, with Kim Barrett, David Moon, Orca Starbuck, and Steve Strassmann. Dylan Interim Reference Manual. Apple Computer, 1994.

At the time of printing this document was accessible from several sites, including http://www.harlequin.com andhttp://www.apple.com. Scheme is a very small, clean dialect of Lisp. It was invented by Guy L. Steele Jr. and Gerald J. Sussman in 1975, and is currently defined by: Clinger, William, and Jonathan A. Rees (Eds.) Revised4 Report on the Algorithmic Language Scheme. 1991.

This report, and various implementations of Scheme, were at the time of printing available by anonymous FTP from swiss-ftp.ai.mit.edu:pub.

There are two especially good textbooks that use Scheme—Structure and Interpretation (see preceding note) and: Springer, George and Daniel P. Friedman. Scheme and the Art of Programming. MIT Press, Cambridge, 1989.
备注 112 (Notes 112)

The most horrible Lisp bugs may be those involving dynamic scope. Such errors almost never occur in Common Lisp, which has lexical scope by default. But since so many of the Lisps used as extension languages still have dynamic scope, practicing Lisp programmers should be aware of its perils.

One bug that can arise with dynamic scope is similar in spirit to variable capture (page 166). You pass one function as an argument to another. The function passed as an argument refers to some variable. But within the function that calls it, the variable has a new and unexpected value.

Suppose, for example, that we wrote a restricted version of mapcar as follows:

(defun our-mapcar (fn x)
  (if (null x)
      nil (cons (funcall fn (car x))
                (our-mapcar fn (cdr x)))))

Then suppose that we used this function in another function, add-to-all , that would take a number and add it to every element of a list:

(defun add-to-all (1st x)
  (our-mapcar #'(lambda (num) (+ num x))
              1st))

In Common Lisp this code works fine, but in a Lisp with dynamic scope it would generate an error. The function passed as an argument to our-mapcar refers to x . At the point where we send this function to our-mapcar , x would be the number given as the second argument to add-to-all . But where the function will be called, within our-mapcar , x would be something else: the list passed as the second argument to our-mapcar . We would get an error when this list was passed as the second argument to + .
备注 123 (Notes 123)

Newer implementations of Common Lisp include avariable *read-eval* that can be used to turn off the # . read-macro. When calling read-from-string on user input, it is wise to bind *read-eval* to nil . Otherwise the user could cause side-effects by using # . in the input.
备注 125 (Notes 125)

There are a number of ingenious algorithms for fast string-matching, but string-matching in text files is one of the cases where the brute-force approach is still reasonably fast. For more on string-matching algorithms, see: Sedgewick, Robert. Algorithms. Addison-Wesley, Reading (MA), 1988.
备注 141 (Notes 141)

In 1984 CommonLisp, reduce did not take a :key argument, so random-next would be defined:

(defun random-next (prev)
  (let* ((choices (gethash prev *words*))
         (i (random (let ((x 0))
                      (dolist (c choices)
                        (incf x (cdr c)))
                      x))))
    (dolist (pair choices)
      (if (minusp (decf i (cdr pair)))
        (return (car pair))))))

备注 141-2 (Notes 141-2)

In 1989, a program like Henley was used to simulate netnews postings by well-known flamers. The fake postings fooled a significant number of readers. Like all good hoaxes, this one had an underlying point. What did it say about the content of the original flames, or the attention with which they were read, that randomly generated postings could be mistaken for the real thing?

One of the most valuable contributions of artificial intelligence research has been to teach us which tasks are really difficult. Some tasks turn out to be trivial, and some almost impossible. If artificial intelligence is concerned with the latter, the study of the former might be called artificial stupidity. A silly name, perhaps, but this field has real promise—it promises to yield programs that play a role like that of control experiments.

Speaking with the appearance of meaning is one of the tasks that turn out to be surprisingly easy. People’s predisposition to find meaning is so strong that they tend to overshoot the mark. So if a speaker takes care to give his sentences a certain kind of superficial coherence, and his audience are sufficiently credulous, they will make sense of what he says.

This fact is probably as old as human history. But now we can give examples of genuinely random text for comparison. And if our randomly generated productions are difficult to distinguish from the real thing, might that not set people to thinking?

The program shown in Chapter 8 is about as simple as such a program could be, and that is already enough to generate “poetry” that many people (try it on your friends) will believe was written by a human being. With programs that work on the same principle as this one, but which model text as more than a simple stream of words, it will be possible to generate random text that has even more of the trappings of meaning.

For a discussion of randomly generated poetry as a legitimate literary form, see: Low, Jackson M. Poetry, Chance, Silence, Etc. In Hall, Donald (Ed.) Claims for Poetry. University of Michigan Press, Ann Arbor, 1982. You bet.

Thanks to the Online Book Initiative, ASCII versions of many classics are available online. At the time of printing, they could be obtained by anonymous FTP from ftp.std.com:obi.

See also the Emacs Dissociated Press feature, which uses an equivalent algorithm to scramble a buffer.
备注 150 (Notes 150)

下面这个函数会显示在一个给定实现中，16 个用来标示浮点表示法的限制的全局常量：

(defun float-limits ()
  (dolist (m '(most least))
    (dolist (s '(positive negative))
      (dolist (f '(short single double long))
        (let ((n (intern (string-upcase
                            (format nil "~A-~A-~A-float"
                                          m  s  f)))))
          (format t "~30A ~A ~%" n (symbol-value n)))))))

备注 164 (Notes 164)

快速排序演算法由霍尔于 1962 年发表，并被描述在 Knuth, D. E. Sorting and Searching. Addison-Wesley, Reading (MA), 1973.一书中。
备注 173 (Notes 173)

Foderaro, John K. Introduction to the Special Lisp Section. CACM 34:9 (Setember 1991), p.27
备注 176 (Notes 176)

关于 CLOS 更详细的信息，参考下列书目：

Keene, Sonya E. Object Oriented Programming in Common Lisp , Addison-Wesley, Reading (MA), 1989

Kiczales, Gregor, Jim des Rivieres, and Daniel G. Bobrow. The Art of the Metaobject Protocol MIT Press, Cambridge, 1991
备注 178 (Notes 178)

让我们再回放刚刚的句子一次：*我们甚至不需要看程序中其他的代码一眼，就可以完成种种的改动。*这个想法或许对某些读者听起来担忧地熟悉。这是写出面条式代码的食谱。

面向对象模型使得通过一点一点的来构造程序变得简单。但这通常意味著，在实践上它提供了一种有结构的方法来写出面条式代码。这不一定是坏事，但也不会是好事。

很多现实世界中的代码是面条式代码，这也许不能很快改变。针对那些终将成为面条式代码的程序来说，面向对象模型是好的：它们最起码会是有结构的面条。但针对那些也许可以避免误入崎途的程序来说，面向对象抽象只是更加危险的，而不是有用的。
备注 183 (Notes 183)

When an instance would inherit a slot with the same name from several of its superclasses, the instance inherits a single slot that combines the properties of the slots in the superclasses. The way combination is done varies from property to property:

    The :allocation , :initform (if any), and :documentation (if any), will be those of the most specific classes.
    The :initargs will be the union of the :initargs of all the superclasses. So will the :accessors , :readers , and:writers , effectively.
    The :type will be the intersection of the :types of all the superclasses.

备注 191 (Notes 191)

You can avoid explicitly uninterning the names of slots that you want to be encapsulated by using uninterned symbols as the names to start with:

(progn
  (defclass counter () ((#1=#:state :initform 0)))

  (defmethod increment ((c counter))
    (incf (slot-value c '#1#)))

  (defmethod clear ((c counter))
    (setf (slot-value c '#1#) 0)))

The progn here is a no-op; it is used to ensure that all the references to the uninterned symbol occur within the same expression. If this were inconvenient, you could use the following read-macro instead:

(defvar *symtab* (make-hash-table :test #'equal))

(defun pseudo-intern (name)
  (or (gethash name *symtab*)
      (setf (gethash name *symtab*) (gensym))))

(set-dispatch-macro-character #\# #\[
  #'(lambda (stream char1 char2)
      (do ((acc nil (cons char acc))
           (char (read-char stream) (read-char stream)))
          ((eql char #\]) (pseudo-intern acc)))))

Then it would be possible to say just:

(defclass counter () ((#[state] :initform 0)))

(defmethod increment ((c counter))
  (incf (slot-value c '#[state])))

(defmethod clear ((c counter))
  (setf (slot-value c '#[state]) 0))

备注 204 (Notes 204)

下面这个宏将新元素推入二叉搜索树：

(defmacro bst-push (obj bst <)
  (multiple-value-bind (vars forms var set access)
                       (get-setf-expansion bst)
    (let ((g (gensym)))
      `(let* ((,g ,obj)
              ,@(mapcar #'list vars forms)
              (,(car var) (bst-insert! ,g ,access ,<)))
         ,set))))

备注 213 (Notes 213)

Knuth, Donald E. Structured Programming with goto Statements.Computing Surveys , 6:4 (December 1974), pp. 261-301
备注 214 (Notes 214)

Knuth, Donald E. Computer Programming as an ArtIn ACM Turing Award Lectures: The First Twenty Years. ACM Press, 1987

This paper and the preceding one are reprinted in: Knuth, Donald E. Literate Programming. CSLI Lecture Notes #27, Stanford University Center for the Study of Language and Information, Palo Alto, 1992.
备注 216 (Notes 216)

Steele, Guy L., Jr. Debunking the “Expensive Procedure Call” Myth or, Procedural Call Implementations Considered Harmful or, LAMBDA: The Ultimate GOTO. Proceedings of the National Conference of the ACM, 1977, p. 157.

Tail-recursion optimization should mean that the compiler will generate the same code for a tail-recursive function as it would for the equivalent do. The unfortunate reality, at least at the time of printing, is that many compilers generate slightly faster code for dos.
备注 217 (Notes 217)

For some examples of calls to disassemble on various processors, see: Norvig, Peter. Paradigms ofArtificial Intelligence Programming: Case Studies in Common Lisp. Morgan Kaufmann, San Mateo (CA), 1992.
备注 218 (Notes 218)

A lot of the increased popularity of object-oriented programming is more specifically the increased popularity of C++, and this in turn has a lot to do with typing. C++ gives you something that seems like a miracle in the conceptual world of C: the ability to define operators that work for different types of arguments. But you don’t need an object-oriented language to do this—all you need is run-time typing. And indeed, if you look at the way people use C++, the class hierarchies tend to be flat. C++ has become so popular not because people need to write programs in terms of classes and methods, but because people need a way around the restrictions imposed by C’s approach to typing.
备注 219 (Notes 219)

Macros can make declarations easier. The following macro expects a type name and an expression (probably numeric), and expands the expression so that all arguments, and all intermediate results, are declared to be of that type. If you wanted to ensure that an expression e was evaluated using only fixnum arithmetic, you could say (with-type fixnum e).

(defmacro with-type (type expr)
  `(the ,type ,(if (atom expr)
                   expr
                 (expand-call type (binarize expr)))))

(defun expand-call (type expr)
  `(,(car expr) ,@(mapcar #'(lambda (a)
                              `(with-type ,type ,a))
                          (cdr expr))))

(defun binarize (expr)
  (if (and (nthcdr 3 expr)
           (member (car expr) '(+ - * /)))
      (destructuring-bind (op a1 a2 . rest) expr
        (binarize `(,op (,op ,a1 ,a2) ,@rest)))
    expr))

The call to binarize ensures that no arithmetic operator is called with more than two arguments. As the Lucid reference manual points out, a call like

(the fixnum (+ (the fixnum a)
               (the fixnum b)
               (the fixnum c)))

still cannot be compiled into fixnum additions, because the intermediate results (e.g. a + b) might not be fixnums.

Using with-type , we could duplicate the fully declared version of poly on page 219 with:

(defun poly (a b x)
  (with-type fixnum (+ (* a (expt x 2)) (* b x))))

If you wanted to do a lot of fixnum arithmetic, you might even want to define a read-macro that would expand into a(with-type fixnum ...) .
备注 224 (Notes 224)

在许多 Unix 系统里， /usr/dict/words 是个合适的单词文件。
备注 226 (Notes 229)

T is a dialect of Scheme with many useful additions, including support for pools. For more on T, see: Rees, Jonathan A., Norman I. Adams, and James R. Meehan. The T Manual, 5th Edition. Yale University Computer Science Department, New Haven, 1988.

The T manual, and T itself, were at the time of printing available by anonymous FTP from hing.lcs.mit.edu:pub/t3.1 .
备注 229 (Notes 229)

The difference between specifications and programs is a difference in degree, not a difference in kind. Once we realize this, it seems strange to require that one write specifications for a program before beginning to implement it. If the program has to be written in a low-level language, then it would be reasonable to require that it be described in high-level terms first. But as the programming language becomes more abstract, the need for specifications begins to evaporate. Or rather, the implementation and the specifications can become the same thing.

If the high-level program is going to be re-implemented in a lower-level language, it starts to look even more like specifications. What Section 13.7 is saying, in other words, is that the specifications for C programs could be written in Lisp.
备注 230 (Notes 230)

Benvenuto Cellini’s story of the casting of his Perseus is probably the most famous (and the funniest) account of traditional bronze-casting: Cellini, Benvenuto. Autobiography. Translated by George Bull, Penguin Books, Harmondsworth, 1956.
备注 239 (Notes 239)

Even experienced Lisp hackers find packages confusing. Is it because packages are gross, or because we are not used to thinking about what happens at read-time?

There is a similar kind of uncertainty about def macro, and there it does seem that the difficulty is in the mind of the beholder. A good deal of work has gone into finding a more abstract alternative to def macro. But def macro is only gross if you approach it with the preconception (common enough) that defining a macro is like defining a function. Then it seems shocking that you suddenly have to worry about variable capture. When you think of macros as what they are, transformations on source code, then dealing with variable capture is no more of a problem than dealing with division by zero at run-time.

So perhaps packages will turn out to be a reasonable way of providing modularity. It is prima facie evidence on their side that they resemble the techniques that programmers naturally use in the absence of a formal module system.
备注 242 (Notes 242)

It might be argued that loop is more general, and that we should not define many operators to do what we can do with one. But it’s only in a very legalistic sense that loop is one operator. In that sense, eval is one operator too. Judged by the conceptual burden it places on the user, loop is at least as many operators as it has clauses. What’s more, these operators are not available separately, like real Lisp operators: you can’t break off a piece of loop and pass it as an argument to another function, as you could map-int .
备注 248 (Notes 248)

关于更深入讲述逻辑推论的资料，参见：Stuart Russell 及 Peter Norvig 所著的 Artificial Intelligence: A Modern Approach。
备注 273 (Notes 273)

Because the program in Chapter 17 takes advantage of the possibility of having a setf form as the first argument todefun , it will only work in more recent Common Lisp implementations. If you want to use it in an older implementation, substitute the following code in the final version:

(proclaim '(inline lookup set-lookup))

(defsetf lookup set-lookup)

(defun set-lookup (prop obj val)
  (let ((off (position prop (layout obj) :test #'eq)))
    (if off
        (setf (svref obj (+ off 3)) val)
        (error "Can't set ~A of ~A." val obj))))

(defmacro defprop (name &optioanl meth?)
  `(progn
     (defun ,name (obj &rest args)
       ,(if meth?
          `(run-methods obj ',name args)
          `(rget ',name obj nil)))
     (defsetf ,name (obj) (val)
       `(setf (lookip ',',name ,obj) ,val))))

备注 276 (Notes 276)

If defmeth were defined as

(defmacro defmeth (name obj parms &rest body)
  (let ((gobj (gensym)))
    `(let ((,gobj ,obj))
       (setf (gethash ',name ,gobj)
             #'(lambda ,parms
                 (labels ((next ()
                            (funcall (get-next ,gobj ',name)
                                     ,@parms)))
                   ,@body))))))

then it would be possible to invoke the next method simply by calling next :

(defmeth area grumpy-circle (c)
  (format t "How dare you stereotype me!""/,")
  (next))

备注 284 (Notes 284)

For really fast access to slots we would use the following macro:

(defmacro with-slotref ((name prop class) &rest body)
  (let ((g (gensym)))
    `(let ((,g (+ 3 (position ,prop (layout ,class)
                              :test #'eq))))
       (macrolet ((,name (obj) `(svref ,obj ,',g)))
         ,@body))))

It defines a local macro that refers directly to the vector element corresponding to a slot. If in some segment of code you wanted to refer to the same slot in many instances of the same class, with this macro the slot references would be straight svrefs.

For example, if the balloon class is defined as follows,

(setf balloon-class (class nil size))

then this function pops (in the old sense) a list of ballons:

(defun popem (ballons)
  (with-slotref (bsize 'size balloon-class)
    (dolist (b ballons)
      (setf (bsize b) 0))))

备注 284-2 (Notes 284-2)

Gabriel, Richard P. Lisp Good News, Bad News, How to Win BigAI Expert, June 1991, p.35.

早在 1973 年， Richard Fateman 已经能证明在 PDP-10 主机上， MacLisp 编译器比制造商的 FORTRAN 编译器，产生出更快速的代码。

译注:该篇 MacLisp 编译器在 PDP-10 可产生比 Fortran 快的代码的论文在这可以找到
备注 399 (Notes 399)

It’s easiest to understand backquote if we suppose that backquote and comma are like quote, and that ```,x`` simply expands into (bq (comma x)) . If this were so, we could handle backquote by augmenting eval as in this sketch:

(defun eval2 (expr)
  (case (and (consp expr) (car expr))
    (comma (error "unmatched comma"))
    (bq (eval-bq (second expr) 1))
    (t  (eval expr))))

(defun eval-bq (expr n)
  (cond ((atom expr)
         expr)
        ((eql (car expr) 'comma)
         (if (= n 1)
             (eval2 (second expr))
             (list 'comma (eval-bq (second expr)
                                   (1- n)))))
        ((eql (car expr) 'bq)
         (list 'bq (eval-bq (second expr) (1+ n))))
        (t
         (cons (eval-bq (car expr) n)
               (eval-bq (cdr expr) n)))))

In eval-bq , the parameter n is used to determine which commas match the current backquote. Each backquote increments it, and each comma decrements it. A comma encountered when n = 1 is a matching comma. Here is the example from page 400:

> (setf x 'a a 1 y 'b b 2)
2
> (eval2 '(bq (bq (w (comma x) (comma (comma y))))))
(BQ (W (COMMA X) (COMMA B)))
> (eval2 *)
(W A 2)

At some point a particularly remarkable molecule was formed by accident. We will call it the Replicator. It may not necessarily have been the biggest or the most complex molecule around, but it had the extraordinary property of being able to create copies of itself.

Richard Dawkins

The Selfish Gene

We shall first define a class of symbolic expressions in terms of ordered pairs and lists. Then we shall define five elementary functions and predicates, and build from them by composition, conditional expressions, and recursive definitions an extensive class of functions of which we shall give a number of examples. We shall then show how these functions themselves can be expressed as symbolic expressions, and we shall define a universal function apply that allows us to compute from the expression for a given function its value for given arguments.

John McCarthy

Recursive Functions of Symbolic Expressions and their Computation by Machine, Part I