更多深度文章，请关注云计算频道：https://yq.aliyun.com/cloud 无论你是不是一名数据科学家，都不能忽视数据的重要性。数据科学家的职责就是分析、组织并利用这些数据。随着机器学习技术的广泛应用，深度学习吸引着大量的研究人员和工程师，数据科学家也将继续站在技术革命的浪潮之巅。 虽然编程能力对于数据科学家而言非常重要，但是数据科学家不完全是软件工程师，他应该是编程、统计和批判性思维三者的结合体。而许多软件工程师通过机器学习框架转型为数据科学家时，没有深刻地思考并理解这些框架背后的统计理论，所以统计学习理论成为了机器学习的理论框架。 为什么学习统计学习？理解不同技术背后的想法是非常重要的，只有真正理解了这些才能知道何时何地使用这些技术。首先必须理解简单的方法，以便掌握更复杂的方法。精确评估一个方法的性能，并且知道它工作情况的好坏显得非常重要。此外，这是一个令人兴奋的研究领域，在科学、工业和金融等方面具有重要的应用。最后，统计学习是培养现代数据科学家的一个基本素材。统计学习问题的例子包括以下几个部分： 确定前列腺癌的风险因素； 根据对数周期图分类记录的音素； 根据人口统计学、饮食和临床测量预测其是否有心脏病； 自定义垃圾电子邮件检测系统； 识别手写邮政编码中的数字； 将组织样本分类为对应的癌症； 建立人口调查数据中的工资与人口变量的关系； 此外，作者对数据挖掘进行了一定的研究，推荐 Intro to Statistical Learning (Hastie, Tibshirani, Witten, James)、Doing Bayesian Data Analysis (Kruschke)和 Time Series Analysis and Applications (Shumway, Stoffer)三本书，这里面有许多有价值的内容。在进入正题之前，想区分一下机器学习和统计学习，主要有以下几点区别： 机器学习是人工智能的一个分支； 统计学习是统计领域的一个分支； 机器学习更侧重于大规模应用和精度预测； 统计学习强调模型及其解释性、精度和不确定性； 但是这种区别变得越来越模糊，而且有大量相互交流； 机器学习在市场营销中占优势； 下面分享10项统计技术，任何数据科学家都应该学习，使得能够更高效地处理大数据集。 1.线性回归 在统计学中，线性回归是一种通过拟合因变量和自变量之间的最佳线性关系来预测目标变量的方法。线性回归主要分为简单线性回归和多元线性回归。简单线性回归使用一个自变量，通过拟合一个最佳线性关系来预测因变量；而多元线性回归使用一个以上的自变量来预测因变量。 2.分类 分类是一种数据挖掘技术，被用来将一个整体数据集分成几个类别，以为了更准确的预测和分析。分类技术中典型的代表是逻辑回归分析和判别分析。逻辑回归是一种预测分析，在用于描述数据时，解释一个二进制因变量与一个或多个序数、区间等变量之间的关系。逻辑回归可以检验的问题类型有： 每增加一磅体重或一天抽一包香烟对肺癌的概率有变化吗？（是/不是） 体重、卡路里与脂肪摄入量、参与者年龄对心脏病发作有影响？（是/不是） 在判别分析中，在每个响应类中分别对预测因子X的分布进行建模，然后利用贝叶斯定理将这些变量翻转到给定X值的响应类别的概率估计中。这样的模型可以是线性的也可以是二次型的。 线性判别分析计算每个观察的判别分数来分类它所处的响应变量类别，这些分数是通过寻找独立变量的线性组合得到，预测变量的协方差在响应变量Y的所有k级上都是相同的。 二次判别分析提供了另一种方法，预测变量不假设Y的k级上有共同的方差。 3.重采样方法 重采样是从原始数据样本中反复抽样的方法，是一种非参数统计推断方法。重采样在实际数据的基础上生成唯一的抽样分布，下面介绍两种最常用的重采样方法拔靴法（bootstrap）和交叉验证（cross-validation）： 拔靴法在许多情况下是一种有用的技术，如验证预测模型的性能、集成方法等。它的工作原理是通过从原始数据中重置采样，并将“未选择”的数据点作为测试用例，反复操作几次后，计算平均得分并作为模型性能的估计； 交叉验证将训练数据分割成k个部分，将k-1个部分作为训练集，使用剩余部分作为测试集，重复试验k次后，计算平均分并作为模型的性能估计； 4.子集选择 这种方法确定了我们认为与反应有关的P预测因子的一个子集，然后使用子集特征的最小二乘拟合模型。 最佳子集选择：对P个预测变量的所有可能组合分别使用最小二乘法进行拟合，最后在所有可能模型(2P)选择一个最优模型； 向前逐步选择：以一个不包含任何预测变量的零模型开始，依次向模型中添加一个变量，妹子只将能够最大限度地提升模型效果的变量加入模型中，直到所有的预测变量都包含在模型中； 向后逐步选择：以半酣所有P个预测变量的模型开始，每次移除一个最有用的预测变量； 混合方法：该方法遵循向前逐步选择步骤，但是在加入新变量的同时，也移除了不能提升模型拟合效果的变量； 5.特征缩减技术 通过对损失函数加入正则项，使得训练求解参数过程中将影响较小的特征的系数衰减到0，只保留重要的特征。最常用的两种方法分别是岭回归（ridge regression）和lasso： Ridge regression与最小二乘法相似，只是在平方误差的基础上增加了正则项，它损失了无偏性，来换取高的数值稳定性，从而得到较高的计算精度； Ridge regression的一个缺点是无法使得预测因子完全为零，只是逼近零，这使得模型无法很好地解释结果；而Lasso克服了这一缺点，能够迫使某些系数为零； 6.降维 降维是将估计P+1个系数减少为M+1个系数，其中M<P。这是通过计算M个不同的线性组合或变量的投影来实现的，然后利用M个投影作为预测因子，使用最小二乘法拟合线性回归模型。常用的两种降维方法是主成分回归和偏最小二乘法： 可以将主成分回归描述为从一组大的变量中导出低纬度特征集的方法。其思想是从中选择排在前面的几个主成分，然后利用从数据中抽出的主成分进行回归，达到降维的目的。 主成分回归面临的一个问题是不能保证提取的主成分完全很好地代表原始特征，偏最小二乘法是主成分回归的有监督替代方法，也是一种降维方法。它首先识别出一组小的特征集合，然后通过对新的M个特征最小二乘拟合成线性模型。与主成分回归不同的是偏最小二乘法利用响应变量识别新特性。 7.非线性模型 在统计学中，非线性回归是回归分析的一种形式，在这种分析中，观测数据是通过模型参数和因变量的非线性组合函数建模，数据用逐次逼近法进行拟合。下面是几个处理非线性模型的重要技术： 阶跃函数：如果实数域上的某个函数可以用半开区间上的指示函数的有限次线性组合来表示，那么这个函数就是阶跃函数，即阶跃函数是有限段分段常数函数的组合。 分段函数：在定义域内不同部分上，有不同的解析表达式。                                                                                                                      样条函数：样条是一种特殊的函数，是由多项式分段定义。在计算机图形学中，样条通常是指分段定义的多项式参数曲线，并且其结构简单、拟合准确，并能近似曲线拟合和交互式曲线设计中复杂的形状，受到广泛应用。 广义加性模型：是一种广义线性模型，其中线性预测器依赖于预测变量的未知光滑函数，专注于这些光滑函数的推理。 8.树形方法 树形方法可以用于回归和分类问题，这些涉及将预测空间分层或分段为一些简单的区域。由于分割预测空间的分裂规则可以用树形总结，所以这类方法也被称为决策树方法。以下方法是将多个树合并，然后得到一个单一的一致性预测： Bagging是通过原始数据训练额外的数据来减少预测的方差的方法。通过增加训练集的大小，虽然不能改善模型的预测能力，但是能减少方差，将预测调整到预期结果； Boosting是一种用几种不同的模型计算输出的方法，然后使用加权平均算法计算出结果的平均值，通过调节权重可以模型能为更广泛的输入数据提供良好的预测力；Random forest算法类似于Bagging，区别在于还需要绘制用于训练单个树的随机子集的特征。由于随机特征选择，这使得树更加独立，从而导致更好的预测性能； 9.支持向量机 支持向量机（SVM）是一种分类技术，简单地说，就是寻找一个超平面能最好地将两类点与最大边界区分开。本质上来说，它是一个有约束的优化问题，其中边界最大化受到数据点分布的约束。图中的数据点“支持”着超平面，超平面的两端上的训练样本就是支持向量。如果两类数据线性不可分时，可以将其投影到高维特征空间，使其线性可分。 10.无监督学习 上述内容只讨论了有监督学习技术，而这类技术运用的前提是需要有类别信息。而无监督学习就是在无类别信息情况下，寻找到好的特征。 常用的无监督学习算法有： 主成分分析（Principal Component Analysis）是通过识别一组具有最大方差切互不相关的特征的线性组合并作为研究的特征空间，从而产生低维表示的数据集； K-均值聚类(k-Mean clustering)是根据聚类中心的距离将数据划分为k个不同的簇； 层次聚类(Hierarchical clustering)是通过计算不同类别数据点间的相似度来创建一颗有层次的嵌套聚类树； 洞察背后的理论知识，能够便于今后的实际操作，希望这份基础数据科学统计指南能帮助到你。 作者信息 James Le，软件工程师、数据科学家、产品经理。 Linkedin: http://www.linkedin.com/in/khanhnamle94/ 本文由北邮@爱可可-爱生活老师推荐，阿里云云栖社区组织翻译。 文章原标题《The 10 Statistical Techniques Data Scientists Need to Master》，作者： James Le，译者：海棠，审阅：，附件为原文。 文章为简译，更为详细的内容，请查看原文  

作者：July、yansha。 出处：http://blog.csdn.net/v_JULY_v 。 引言     常关注本blog的读者朋友想必看过此篇文章：从B树、B+树、B*树谈到R 树，这次，咱们来讲另外两种树：Tire树与后缀树。不过，在此之前，先来看两个问题。     第一个问题： 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。     之前在此文：海量数据处理面试题集锦与Bit-map详解中给出的参考答案：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平均长度），然后是找出出现最频繁的前10个词。也可以用堆来实现（具体的操作可参考第三章、寻找最小的k个数），时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的哪一个。     第二个问题：找出给定字符串里的最长回文。例子：输入XMADAMYX。则输出MADAM。这道题的流行解法是用后缀树（Suffix Tree)，但其用途远不止如此，它能高效解决一大票复杂的字符串编程问题（当然，它有它的弱点，如算法实现复杂以及空间开销大），概括如下：  查询字符串S是否包含子串S1。主要思想是：如果S包含S1，那么S1必定是S的某个后缀的前缀；又因为S的后缀树包含了所有的后缀，所以只需对S的后缀树使用和Trie相同的查找方法查找S1即可（使用后缀树实现的复杂度同流行的KMP算法的复杂度相当）。  找出字符串S的最长重复子串S1。比如abcdabcefda里abc同da都重复出现，而最长重复子串是abc。  找出字符串S1同S2的最长公共子串。注意最长公共子串（Longest CommonSubstring）和最长公共子序列（LongestCommon Subsequence, LCS）的区别：子串（Substring）是串的一个连续的部分，子序列（Subsequence）则是从不改变序列的顺序，而从序列中去掉任意的元素而获得的新序列；更简略地说，前者（子串）的字符的位置必须连续，后者（子序列LCS）则不必。比如字符串acdfg同akdfc的最长公共子串为df，而他们的最长公共子序列是adf。LCS可以使用动态规划法解决。 Ziv-Lampel无损压缩算法。 LZW算法的基本原理是利用编码数据本身存在字符串重复特性来实现数据压缩，所以一个很好的选择是使用后缀树的形式来组织存储字符串及其对应压缩码值的字典。 找出字符串S的最长回文子串S1。例如：XMADAMYX的最长回文子串是MADAM（此即为上面所说的第二个问题：最长回文问题，本文第二部分将详细阐述此问题）。 多模式串的模式匹配问题。（suffer_array+二分）。    本文第一部分，咱们就来了解这个Trie树，然后自然而然过渡到第二部分、后缀树，接着进入第三部分、详细阐述后缀树的构造方法-Ukkonen，最后第四部分、对自动机，KMP算法，Extend-KMP，后缀树，后缀数组，trie树，trie图及其应用做个全文概括性总结。权作此番阐述，以备不时之需，在需要的时候便可手到擒来。ok，有任何问题，欢迎不吝指正或赐教。谢谢。 第一部分、Trie树 什么是Trie树     Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。     Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 它有3个基本性质： 根节点不包含字符，除根节点外每一个节点都只包含一个字符。 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。 每个节点的所有子节点包含的字符都不相同。 树的构建 举个在网上流传颇广的例子，如下：     题目：给你100000个长度不超过10的单词。对于每一个单词，我们要判断他出没出现过，如果出现了，求第一次出现在第几个位置。     分析：这题当然可以用hash来解决，但是本文重点介绍的是trie树，因为在某些方面它的用途更大。比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单。     现在回到例子中，如果我们用最傻的方法，对于每一个单词，我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd，那么在他前面的单词中，以b，c，d，f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的，在以a开头中的单词中，我们只要考虑以b作为第二个字母的，一次次缩小范围和提高针对性，这样一个树的模型就渐渐清晰了。     好比假设有b，abc，abd，bcd，abcd，efg，hii 这6个单词，我们构建的树就是如下图这样的：       当时第一次看到这幅图的时候，便立马感到此树之不凡构造了。单单从上幅图便可窥知一二，好比大海搜人，立马就能确定东南西北中的到底哪个方位，如此迅速缩小查找的范围和提高查找的针对性，不失为一创举。     ok，如上图所示，对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。     那么，对于一个单词，我只要顺着他从根走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。     这样一来我们查询和插入可以一起完成（重点体会这个查询和插入是如何一起完成的，稍后，下文具体解释），所用时间仅仅为单词长度，在这一个样例，便是10。     我们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。 前缀查询     上文中提到”比如说对于某一个单词，我们要询问它的前缀是否出现过。这样hash就不好搞了，而用trie还是很简单“。下面，咱们来看看这个前缀查询问题：     已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法： 最容易想到的：即从字符串集中从头往后搜，看每个字符串是否为字符串集中某个字符串的前缀，复杂度为O(n^2)。 使用hash：我们用hash存下所有字符串的所有的前缀子串，建立存有子串hash的复杂度为O(n*len)，而查询的复杂度为O(n)* O(1)= O(n)。 使用trie：因为当查询如字符串abc是否为某个字符串的前缀时，显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len)，而建立+查询在trie中是可以同时执行的，建立的过程也就可以成为查询的过程，hash就不能实现这个功能。所以总的复杂度为O(n*len)，实际查询的复杂度也只是O(len)。（说白了，就是Trie树的平均高度h为len，所以Trie树的查询复杂度为O（h）=O（len）。好比一棵二叉平衡树的高度为logN，则其查询，插入的平均时间复杂度亦为O（logN））。     下面解释下上述方法3中所说的为什么hash不能将建立与查询同时执行，而Trie树却可以： 在hash中，例如现在要输入两个串911，911456，如果要同时查询这两个串，且查询串的同时若hash中没有则存入。那么，这个查询与建立的过程就是先查询其中一个串911，没有，然后存入9、91、911；而后查询第二个串911456，没有然后存入9、91、911、9114、91145、911456。因为程序没有记忆功能，所以并不知道911在输入数据中出现过，只是照常以例行事，存入9、91、911、9114、911...。也就是说用hash必须先存入所有子串，然后for循环查询。 而trie树中，存入911后，已经记录911为出现的字符串，在存入911456的过程中就能发现而输出答案；倒过来亦可以，先存入911456，在存入911时，当指针指向最后一个1时，程序会发现这个1已经存在，说明911必定是某个字符串的前缀。     读者反馈@悠悠长风：关于这点，我有不同的看法。hash也是可以实现边建立边查询的啊。当插入911时，需要一个额外的标志位，表示它是一个完整的单词。在处理911456时，也是按照前面的查询9,91,911，当查询911时，是可以找到前面插入的911，且通过标志位知道911为一个完整单词。那么就可以判断出911为911456的前缀啊。虽然trie树更适合这个问题，但是我认为hash也是可以实现边建立，边查找。     吾答曰：但若反过来呢?比如说是先查询911456，而后查询911呢？你的在hash中做一个完整单词的标志就行不通了。因为，你查询911456时，并不知道后来911会是一个完整的单词。     至于，有关Trie树的查找，插入等操作的实现代码，网上遍地开花且千篇一律，诸君尽可参考，想必不用我再做多余费神。 查询     Trie树是简单但实用的数据结构，通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时，就是Trie开始。本质上，Trie是一颗存储多个字符串的树。相邻节点间的边代表一个字符，这样树的每条分支代表一则子串，而树的叶节点则代表完整的字符串。和普通树不同的地方是，相同的字符串前缀共享同一条分支。下面，再举一个例子。给出一组单词，inn, int, at, age, adv, ant, 我们可以得到下面的Trie：   可以看出： 每条边对应一个字母。 每个节点对应一项前缀。叶节点对应最长前缀，即单词本身。 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支，root->i->in。同理，ate, age, adv, 和ant共享前缀"a"，所以他们共享从根节点到节点"a"的边。     查询操纵非常简单。比如要查找int，顺着路径i -> in -> int就找到了。    搭建Trie的基本算法也很简单，无非是逐一把每则单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在，就共享，否则创建对应的节点和边。比如要插入单词add，就有下面几步： 考察前缀"a"，发现边a已经存在。于是顺着边a走到节点a。 考察剩下的字符串"dd"的前缀"d"，发现从节点a出发，已经有边d存在。于是顺着边d走到节点ad 考察最后一个字符"d"，这下从节点ad出发没有边d了，于是创建节点ad的子节点add，并把边ad->add标记为d。 实现 Trie树的单词查询实现         以下是trie树的简单实现。下图所示的测试只是做了一个非常简单的检测而已，先插入j而后查找j，再删除再查找，目的主要是看删除函数是否有效。日后再好好写下trie树用于单词频率统计的实现（单词统计hash表当然也可以实现，只不过如果用trie树统计单词出现频率，想象一下，当树中已有某个单词，再次遍历到同样的单词，便可以迅速高效的查询找到某个单词，为其出现计数+1，这得益于查找高效的所带来的好处）。 //copyright@singmelody //updated@2011 July #include <stdio.h> #include <malloc.h>  #include <string.h>  #define true 1  #define false 0   struct trieNode  {    trieNode():isword(false)        {              memset(next, 0, sizeof(next));      }       trieNode *next[26];       bool isword;  }Root;   void insert(char *tar) {       trieNode *p =&Root;       int id;        while(*tar)       {            id = *tar-'a';                  if(p->next[id] == NULL)          {                 p->next[id] =(trieNode *)malloc(sizeof(trieNode));          }             p = p->next[id];               tar++;       }       p->isword = true;  }    //找到返回 true 否则返回false  int search(char *tar)  {       trieNode *p = &Root;       int id;        while(*tar)        {             id = *tar - 'a';            if (p->next[id] == NULL)           {                   return false;           }             p = p->next[id];          tar++;     }          //判断结点是否标记       if (p->isword == true)         return true;      else            return false;  }    void remove(char *tar) {       trieNode *p =&Root;        int id;       while(*tar)      {             id = *tar-'a';            p = p->next[id];           tar++;      }       p->isword = false; }    void searchprocess() {       char searchstr[20];        printf("Please search:\n");        scanf("%s",searchstr);       printf("Now searching %s:\n",searchstr);         if (search(searchstr)==true)     {            printf("Success\n");       }        else     {             printf("Fail\n");      }  }   int main() {               //.....   return 0;  } Trie树单词频率统计实现     以下是用Trie树统计单词频率的实现，程序尚不完善，有很多地方还需改进。 // trie tree.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" //功能：统计一段英文的单词频率(文章以空格分隔，没有标点)  //思路：trie节点保存单词频率，然后通过DFS按字典序输出词频  //时空复杂度: O(n*len)(len为单词平均长度) //copyright@yansha 2011.10.25 //updated@July 2011.10.26 //程序尚不完善，有很多地方还需改进。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <assert.h> #define num_of_letters 26 #define max_word_length 20 // 定义trie树节点 struct Trie    {      int count;      Trie *next[num_of_letters];  };    // 定义根节点  Trie *root = NULL; /** * 建立trie树，同时保存单词频率 */ void create_trie(char *word) {   int len = strlen(word);   Trie *cur = root, *node;   int pos = 0;   // 深度为单词长度   for(int i = 0; i < len; ++i)   {     // 将字母范围映射到0-25之间     pos = word[i] - 'a';     // 如果当前字母没有对应的trie树节点则建立，否则处理下一个字母     if(cur->next[pos] == NULL)   //1、这里应该有个查找过程     {       node = (Trie *)malloc(sizeof(Trie));       node->count = 0;       // 初始化next节点       for(int j = 0; j < num_of_letters; ++j)       node->next[j] = NULL;       // 开始处理下一个字母       cur->next[pos] = node;       }   cur = cur->next[pos];   }   // 单词频率加1   cur->count++; } /** * 大写字母转化成小写字母 */ void upper_to_lower(char *word, int len) {   for (int i = 0; i < len; ++i)   {     if(word[i] >= 'A' && word[i] <= 'Z')     word[i] += 32;   } } /** * 处理输入 */ void process_input() {   char word[max_word_length];   // 打开统计文件(注意保持文件名一致)   FILE *fp_passage = fopen("passage.txt", "r");     assert(fp_passage);   // 循环处理单词   while (fscanf(fp_passage, "%s", word) != EOF)     {       int len = strlen(word);       if (len > 0)         upper_to_lower(word, len);       create_trie(word);     }     fclose(fp_passage);   } /** * 深度优先遍历 */  void trie_dfs(Trie *p, char *queue) {   for(int i = 0; i < num_of_letters; ++i)   {     if(p->next[i] != NULL)   {     // 定义队列头结点     char *head = queue;     // 在末尾增加一个字母     while (*queue != '\0')       queue++;     *queue = (char)(i + 'a');     queue = head;     // 在控制台打印单词及其频率     if (p->next[i]->count > 0)       printf("%s\t%d\n", queue, p->next[i]->count);     trie_dfs(p->next[i], queue);     // 在末尾去掉一个字母     head = queue;     while (*(queue+1) != '\0')       queue++;     *queue = '\0';     queue = head;     }   } } int main() {   // 初始化trie树根节点   root = (Trie *)malloc(sizeof(Trie));   for(int j = 0; j < num_of_letters; ++j)   root->next[j] = NULL;   // 处理输入   process_input();   // 分配一个保存单词中间结果的队列   char *queue = (char*) calloc(max_word_length, sizeof(char));   // 通过DFS打印结果   trie_dfs(root, queue);   system("pause");   return 0; } Trie树的应用     除了本文引言处所述的问题能应用Trie树解决之外，Trie树还能解决下述问题（节选自此文：海量数据处理面试题集锦与Bit-map详解）： 3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。 9、1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？ 10、 一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。 13、寻找热门查询：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录，这些查询串的重复读比较高，虽然总数是1千万，但是如果去除重复和，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就越热门。请你统计最热门的10个查询串，要求使用的内存不能超过1G。 (1) 请描述你解决这个问题的思路； (2) 请给出主要的处理流程，算法，以及算法的复杂度。     有了Trie，后缀树就容易理解了。本文接下来的第二部分，介绍后缀树。 第二部分、后缀树 后缀树的定义         后缀树（Suffix tree）是一种数据结构，能快速解决很多关于字符串的问题。后缀树的概念最早由Weiner 于1973年提出，既而由McCreight 在1976年和Ukkonen在1992年和1995年加以改进完善。     后缀，顾名思义，甚至通俗点来说，就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1...Sn便都是字符串S的后缀。     以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i。 S[1..8], XMADAMYX， 也就是字符串本身，起始位置为1   S[2..8], MADAMYX，起始位置为2      S[3..8], ADAMYX，起始位置为3        S[4..8], DAMYX，起始位置为4           S[5..8], AMYX，起始位置为5             S[6..8], MYX，起始位置为6                S[7..8], YX，起始位置为7                  S[8..8], X，起始位置为8                                  空字串，记为$。     而后缀树，就是包含一则字符串所有后缀的压缩Trie。把上面的后缀加入Trie后，我们得到下面的结构：     仔细观察上图，我们可以看到不少值得压缩的地方。比如蓝框标注的分支都是独苗，没有必要用单独的节点同边表示。如果我们允许任意一条边里包含多个字 母，就可以把这种没有分叉的路径压缩到一条边。另外每条边已经包含了足够的后缀信息，我们就不用再给节点标注字符串信息了。我们只需要在叶节点上标注上每 项后缀的起始位置。于是我们得到下图：     这样的结构丢失了某些后缀。比如后缀X在上图中消失了，因为它正好是字符串XMADAMYX的前缀。为了避免这种情况，我们也规定每项后缀不能是其它后缀的前缀。要解决这个问题其实挺简单，在待处理的子串后加一个空字串就行了。例如我们处理XMADAMYX前，先把XMADAMYX变为 XMADAMYX$，于是就得到suffix tree--后缀树了，如下图所示： 后缀树与回文问题的关联     那后缀树同最长回文有什么关系呢？我们得先知道两个简单概念：   最低共有祖先，LCA（Lowest Common Ancestor)，也就是任意两节点（多个也行）最长的共有前缀。比如下图中，节点7同节点10的共同祖先是节点1与借点，但最低共同祖先是5。 查找LCA的算法是O(1)的复杂度，这年头少见。代价是需要对后缀树做复杂度为O(n)的预处理。  广义后缀树(Generalized Suffix Tree)。传统的后缀树处理一坨单词的所有后缀。广义后缀树存储任意多个单词的所有后缀。例如下图是单词XMADAMYX与XYMADAMX的广义后缀 树。注意我们需要区分不同单词的后缀，所以叶节点用不同的特殊符号与后缀位置配对。      最长回文问题的解决     有了上面的概念，本文引言中提出的查找最长回文问题就相对简单了。咱们来回顾下引言中提出的回文问题的具体描述：找出给定字符串里的最长回文。例如输入XMADAMYX，则输出MADAM。       思维的突破点在于考察回文的半径，而不是回文本身。所谓半径，就是回文对折后的字串。比如回文MADAM 的半径为MAD，半径长度为3，半径的中心是字母D。显然，最长回文必有最长半径，且两条半径相等。还是以MADAM为例，以D为中心往左，我们得到半径 DAM；以D为中心向右，我们得到半径DAM。二者肯定相等。因为MADAM已经是单词XMADAMYX里的最长回文，我们可以肯定从D往左数的字串 DAMX与从D往右数的子串DAMYX共享最长前缀DAM。而这，正是解决回文问题的关键。现在我们有后缀树，怎么把从D向左数的字串DAMX变成后缀 呢？     到这个地步，答案应该明显：把单词XMADAMYX翻转（XMADAMYX=>XYMADAMX，DAMX就变成后缀了）就行了。于是我们把寻找回文的问题转换成了寻找两坨后缀的LCA的问题。当然，我们还需要知道 到底查询那些后缀间的LCA。很简单，给定字符串S，如果最长回文的中心在i，那从位置i向右数的后缀刚好是S(i)，而向左数的字符串刚好是翻转S后得到的字符串S‘的后缀S'(n-i+1)。这里的n是字符串S的长度。     可能上面的阐述还不够直观，我再细细说明下：     1、首先，还记得本第二部分开头关于后缀树的定义么： “先说说后缀的定义，顾名思义，甚至通俗点来说，就是所谓后缀就是后面尾巴的意思。比如说给定一长度为n的字符串S=S1S2..Si..Sn，和整数i，1 <= i <= n，子串SiSi+1...Sn便都是字符串S的后缀。”       以字符串S=XMADAMYX为例，它的长度为8，所以S[1..8], S[2..8], ... , S[8..8]都算S的后缀，我们一般还把空字串也算成后缀。这样，我们一共有如下后缀。对于后缀S[i..n]，我们说这项后缀起始于i。 S[1..8], XMADAMYX， 也就是字符串本身，起始位置为1   S[2..8], MADAMYX，起始位置为2      S[3..8], ADAMYX，起始位置为3        S[4..8], DAMYX，起始位置为4           S[5..8], AMYX，起始位置为5             S[6..8], MYX，起始位置为6                S[7..8], YX，起始位置为7                  S[8..8], X，起始位置为8                                   空字串，记为$。     2、对单词XMADAMYX而言，回文中心为D，那么D向右的后缀DAMYX假设是S(i)（当N=8，i从1开始计数，i=4时，便是S(4..8)）;而对于翻转后的单词XYMADAMX而言，回文中心D向右对应的后缀为DAMX，也就是S'(N-i+1)(（N=8，i=4，便是S‘（5..8）） 。此刻已经可以得出，它们共享最长前缀，即LCA（DAMYX，DAMX）=DAM。有了这套直观解释，算法自然呼之欲出： 预处理后缀树，使得查询LCA的复杂度为O(1)。这步的开销是O(N)，N是单词S的长度 ； 对单词的每一位置i(也就是从0到N-1)，获取LCA(S(i), S‘(N-i+1)) 以及LCA(S(i+1), S’(n-i+1))。查找两次的原因是我们需要考虑奇数回文和偶数回文的情况。这步要考察每坨i，所以复杂度是O(N) ； 找到最大的LCA，我们也就得到了回文的中心i以及回文的半径长度，自然也就得到了最长回文。总的复杂度O(n)。      用上图做例子，i为4时，LCA(4$, 5#)为DAM，正好是最长半径。当然，这只是直观的叙述。    上面大致描述了后缀树的基本思路。要想写出实用代码，至少还得知道下面的知识： 创建后缀树的O(n)算法。此算法有很多种，无论Peter Weiner的73年年度最佳算法，还是Edward McCreight1976的改进算法，还是1995年E. Ukkonen大幅简化的算法（本文第4部分将重点阐述这种方法），还是Juha Kärkkäinen 和 Peter Sanders2003年进一步简化的线性算法，都是O（n）的时间复杂度。至于实际中具体选择哪一种算法，可依实际情况而定。  实现后缀树用的数据结构。比如常用的子结点加兄弟节点列表，Directed 优化后缀树空间的办法。比如不存储子串，而存储读取子串必需的位置。以及Directed Acyclic Word Graph，常缩写为黑哥哥们挂在嘴边的DAWG。  后缀树的应用     后缀树的用途，总结起来大概有如下几种    查找字符串o是否在字符串S中。    方案：用S构造后缀树，按在trie中搜索字串的方法搜索o即可。    原理：若o在S中，则o必然是S的某个后缀的前缀。  例如S: leconte，查找o: con是否在S中,则o(con)必然是S(leconte)的后缀之一conte的前缀.有了这个前提，采用trie搜索的方法就不难理解了。。  指定字符串T在字符串S中的重复次数。    方案：用S+’$'构造后缀树，搜索T节点下的叶节点数目即为重复次数    原理：如果T在S中重复了两次，则S应有两个后缀以T为前缀，重复次数就自然统计出来了。。  字符串S中的最长重复子串    方案：原理同2，具体做法就是找到最深的非叶节点。    这个深是指从root所经历过的字符个数，最深非叶节点所经历的字符串起来就是最长重复子串。  为什么要非叶节点呢?因为既然是要重复，当然叶节点个数要>=2。  两个字符串S1，S2的最长公共部分    方案：将S1#S2$作为字符串压入后缀树，找到最深的非叶节点，且该节点的叶节点既有#也有$(无#)。      后缀树的代码实现，下期再续。第二部分、后缀树完。 第三部分、后缀树的构造方法-Ukkonen     接下来，咱们来了解后缀树的构造方法-Ukkomen。为了兼顾上文内容，以及加深印象，本部分打算从Trie树从头到位重新开始阐述一切。     Ukkonen的构造法O(n), 它比Sartaj Sahni的构造法O(nr), r为字母表大小 在时间上更有优势. 但我们不能说Sartaj Sahni的算法慢, 因为r往往会很小, 因此实际效率也接近线性, 两种构造法在思想上均有可取之处.   问题的起源   字符串匹配问题是程序员经常要面对的问题. 字符串匹配算法的改进可以使许多工程受益良多, 比如数据压缩和DNA排列。你可以把自己想象成一名工作于DNA排列工程的程序员. 那些基因研究者们天天忙着分切病毒的基因材料, 制造出一段一段的核苷酸序列. 他们把这些序列发到你的服务器里, 指望你在基因数据库中定位. 要知道, 你的数据库里有数百种病毒的数据, 而一个特定的病毒可以有成千上万的碱基. 你的程序必须像C/S工程那样实时向博士们反馈信息, 这需要一个很好的方案。  很明显, 在这个问题上采取暴力算法是极其低效的. 这种方法需要你在基因数据库里对比每一个核苷酸, 测试一个较长的基因段基本会把你的C/S系统变成一台古老的批处理机。 直觉上的解决方法 由于基因数据库一般是不变的, 通过预处理来把搜索简化或许是个好主意. 一种预处理的方法是建立一棵Trie. 我们通过Trie引申出一种东西叫作后缀Trie. (后缀Trie离后缀树仅一步之遥.) 首先, Trie是一种n叉树, n为字母表大小, 每个节点表示从根节点到此节点所经过的所有字符组成的字符串. 而后缀Trie的 “后缀” 说明这棵Trie包含了所给字段的所有后缀 (也许正是一个病毒基因).     图1 BANANAS的后缀Trie 上展示了文本BANANAS的后缀Trie. 关于这棵Trie有两个地方需要注意. 第一, 从根节点开始, BANANAS的每一个后缀都插入到Trie中, 包括BANANAS, ANANAS, NANAS, ANAS, NAS, AS, S. 第二, 鉴于这种结构, 你可以通过从根节点往下匹配的方式搜索到单词的任何一个子串. 这里所说的第二点正是我们认为后缀Trie优秀的原因. 如果你输入一个长度为N的文本并想在其中搜索一个长度为M的串, 传统的暴力匹配需要进行N*M次字符对比, 而一些改进过的匹配技术, 比如像Boyer-Moore算法, 可以在O(N+M)的时间开销内解决问题, 平均效率更是令人满意. 然而, 后缀Trie亮出了O(M)的牌子, 彻底鄙视了其他算法的成绩, 后缀Trie对比的次数仅仅相当于被搜索串的长度! 这确实是可圈可点的威力, 这意味着你能通过仅仅7次对比便在莎士比亚所有作品中找出BANANAS. 但有一点我们可不能忘了, 构造后缀Trie也是需要时间的. 后缀Trie之所以没有家喻户晓正是因为构造它需要O(n2)的时间和空间. 平方级的开销使它在最需要它的领域 --- 长串搜索 中被拒之门外. 横空出世 直到1976年, Edward McCreigh发表了一篇论文, 咱们的后缀树问世了. 后缀Trie的困境被彻底打破. 后缀树跟后缀Trie有着一样的布局, 但它把只有一个儿子的节点给剔除了. 这个过程被称为路径压缩, 这意味着树上的某些边将表示一个序列而不是单独的字符. 图2   BANANAS的后缀树 图2是由图1的后缀Trie转化而来的后缀树. 你会发现这树基本还是那个形状, 只是节点变少了. 在剔除了只有一个儿子的节点之后, 总节点数由23降为11. 经过证明, 在最坏情况下, 后缀树的节点数也不会超过2N (N为文本的长度). 这使构造后缀树的线性时空开销成为可能. 然而, McCreight最初的构造法是有些缺陷的, 原则上它要按逆序构造, 也就是说字符要从末端开始插入. 如此一来, 便不能作为在线算法, 它变得更加难以应用于实际问题, 如数据压缩. 20年后, 来自赫尔辛基理工大学的Esko Ukkonen把原算法作了一些改动, 把它变成了从左往右. 本文接下来的所有描述和代码都是基于Esko Ukkonen的成果. 对于所给的文本T, Esko Ukkonen的算法是由一棵空树开始, 逐步构造T的每个前缀的后缀树. 比如我们构造BANANAS的后缀树, 先由B开始, 接着是BA, 然后BAN, … . 不断更新直到构造出BANANAS的后缀树. 图3  逐步构造后缀树   初窥门径 加入一个新的前缀需要访问树中已有的后缀. 我们从最长的一个后缀开始(图3中的BAN), 一直访问到最短的后缀(空后缀). 每个后缀会在以下三种节点的其中一种结束.   一个叶节点. 这个是常识了, 图4中标号为1, 2, 4, 5的就是叶节点. 一个显式节点. 图4中标号为0, 3的是显式节点, 它表示该节点之后至少有两条边. 一个隐式节点. 图4中, 前缀BO, BOO, 或者非前缀OO, 它们都在某条表示序列的边上结束, 这些位置就叫作隐式节点. 它表示后缀Trie中存在的由于路径压缩而剔除的节点. 在后缀树的构造过程中, 有时要把一些隐式节点转化为显式节点。             图4  加入BOOK之后的BOOKKEEPER (也就是BOOK的后缀树) 如图4, 在加入BOOK之后, 树中有5个后缀(包括空后缀). 那么要构造下一个前缀BOOKK的后缀树的话, 只需要访问树中已存在的每一个后缀, 然后在它们的末尾加上K. 前4个后缀BOOK, OOK, OK和K都在叶节点上结束. 由于我们要路径压缩, 只需要在通往叶节点的边上直接加一个字符, 而不需要创建一个新节点. 在所有叶节点更新之后, 我们还需要在空后缀后面加上K. 这时候我们发现已经存在一条从0节点出发的边的首字符为K, 没必要画蛇添足了. 换句话说, 新加入的后缀K可以在0节点和2节点之间的隐式节点中找到. 最终形态见图5.                图5 加入BOOKK之后的BOOKKEEPER 相比图4, 树的结构没有发生变化 如果你是一位敏感的读者, 可能要发问了, 如果加入K我们什么都不做的话, 在查找的时候如何知道它到底是一个后缀呢还是某个后缀的一截? 如果你同时又是一位熟悉字符串算法的朋友, 心里可能马上就有答案了 --- 我们只需要在文本后面加个字母表以外的字符, 比如$或者#. 那我们查找到K$或K#的话就说明这是一个后缀了. 稍微麻烦一点的事情 从图4到图5这个更新过程是相对简单的, 其中我们执行了两种更新: 一种是将某条边延长, 另一种是啥都不做. 但接下来往图5继续加入BOOKKE, 我们则会遇到另外两种更新: 创建一个新节点来割开某一隐式节点所处的边, 并在其后加一条新边. 在显式节点后加一条新边.   图6先分割, 再添加 当我们往图5的树中加入BOOKKE的时候, 我们是从已存在的最长后缀BOOKK开始, 一直操作到最短的后缀空后缀. 更新最长的后缀必然是更新叶节点, 之前提到了, 非常简单. 除此之外, 图5中结束在叶节点上的后缀还有OOKK, OKK, KK. 图6的第一棵树展示了这一类节点的更新. 图5中首个不是结束在叶节点上的后缀是K. 这里我们先引入一个定义: 在每次更新后缀树的过程中, 第一个非叶节点称为激活节点. 它有以下性质:   所有比激活节点长的后缀都在叶节点上结束. 所有在激活节点之后加入的后缀都不在叶节点上结束.   后缀K在边KKE上的隐式节点结束. 在后缀树中我们要判断一个节点是不是非叶节点需要看它是否有跟待加入字符相同的儿子, 即本例中的E. 一眼可以看出, KKE中的第一个K只有一个儿子: K. 所以它是非叶节点(这里同时也是激活节点), 我们要给他加一个儿子来表示E. 这个过程有两个步骤:   在第一个K和第二个K之间把边分割开, 于是第一个K(隐式节点)成了一个显式节点, 如图6第二棵树. 在刚刚变身而来的显式节点后加一个新节点表示E, 如图6第三棵树. 由此我们又多了一个叶节点。   后缀K更新之后, 别忘了还有空后缀. 空后缀在根节点(节点0)结束, 显然此时根节点是一个显式节点. 我们看一下它后面有没有以E开头的边---没有, 那么加入一个新的叶节点(如果存在以E开头的边, 则不用任何操作). 最终如图7.   图7 归纳, 反思, 优化 借助后缀树的特性, 我们可以做出一个相当有效的算法. 首先一个重要的特性是: 一朝为叶, 终生为叶. 一个叶节点自诞生以后绝不会有子孙. 更重要的是, 每当我们往树上加入一个新的前缀, 每一条通往叶节点的边都会延长一个字符(新前缀的最后一个字符). 这使得处理通往叶节点的边变得异常简单, 我们完全可以在创建叶节点的时候就把当前字符到文本末的所有字符一股脑塞进去. 是的, 我们不需要知道后面的字符是啥, 但我们知道它们最终都要被加进去. 因此, 一个叶节点诞生的时候, 也正是它可以被我们遗忘的时候. 你可能会担心通往叶节点的边被分割了怎么办, 那也不要紧, 分割之后只是起点变了, 尾部该怎么着还是怎么着. 如此一来, 我们只需要关心显式节点和隐式节点上的更新. 还要提到一个节约时间的方法. 当我们遍历所有后缀时, 如果某个后缀的某个儿子跟待加字符(新前缀最后一个字符)相同, 那么我们当前前缀的所有更新就可以停止了. 如果你理解了后缀树的本质, 你会知道一旦待加字符跟某个后缀的某个儿子相同, 那么更短的后缀必然也有这个儿子. 我们不妨把首个这样的节点定义为结束节点. 比结束节点长的后缀必然是叶节点, 这一点很好解释, 要么本来就是叶节点, 要么就是新创建的节点(新创建的必然是叶节点). 这意味着, 每一个前缀更新完之后, 当前的结束节点将成为下一轮更新的激活节点. 好了, 现在我们可以把后缀树的更新限制在激活节点和结束节点之间, 效率有了很大的改善. 整理成伪代码如下: Update( 新前缀 ) {   当前后缀 = 激活节点   待加字符 = 新前缀最后一个字符        done = false;   while ( !done ) {   if ( 当前后缀在显式节点结束 )    {     if ( 当前节点后没有以待加字符开始的边 )       在当前节点后创建一个新的叶节点     else       done = true;   } else {     if ( 当前隐式节点的下一个字符不是待加字符 )      {       从隐式节点后分割此边        在分割处创建一个新的叶节点     } else       done = true;     if ( 当前后缀是空后缀 )       done = true;     else       当前后缀 = 下一个更短的后缀      }   激活节点 = 当前后缀 } 后缀指针 上面的伪代码看上去很完美, 但它掩盖了一个问题. 注意到第21行, “下一个更短的后缀”, 如果呆板地沿着树枝去搜索我们想要的后缀, 那这种算法就不是线性的了. 要解决此问题, 我们得附加一种指针: 后缀指针. 后缀指针存在于每个结束在非叶节点的后缀上, 它指向“下一个更短的后缀”. 即, 如果一个后缀表示文本的第0到第N个字符, 那么它的后缀指针指向的节点表示文本的第1到第N个字符. 图8是文本ABABABC的后缀树. 第一个后缀指针在表示ABAB的节点上. ABAB的后缀指针指向表示BAB的节点. 同样地, BAB也有它的后缀指针, 指向AB. 如此这般.   图8 加上后缀指针(虚线)的ABABABC的后缀树 介绍一下如何创建后缀指针. 后缀指针的创建是跟后缀树的更新同步的. 随着我们从激活节点移动到结束节点, 我把每个新的叶节点的父亲的路径保存下来. 每当创建一条新边, 我同时也在上一个叶节点的父亲那儿创建一个后缀指针来指向当前新边开始的节点. (显然, 我们不能在第一条新边上做这样的操作, 但除此之外都可以这么做.) 有了后缀指针, 就可以方便地一个后缀跳到另一个后缀. 这个关键性的附加品使得算法的时间上限成功降为O(N)。 第四部分、全文总结 自动机，KMP算法，Extend-KMP，后缀树，后缀数组，trie树，trie图及其应用     涉及到字符串的问题，无外乎这样一些算法和数据结构：自动机，KMP算法，Extend-KMP，后缀树，后缀数组，trie树，trie图及其应用。当然这些都是比较高级的数据结构和算法，而这里面最常用和最熟悉的大概是kmp，即使如此还是有相当一部分人也不理解kmp，更别说其他的了。当然一般的字符串问题中，我们只要用简单的暴力算法就可以解决了，然后如果暴力效率太低，就用个hash。当然hash也是一个面试中经常被用到的方法。这样看来，这样的一些算法和数据结构实际上很少会被问到，不过如果使用它们一般可以得到很好的线性复杂度的算法。     老实说，字符串问题的确挺复杂的，出来一个如果用暴力，hash搞不定，就很难再想其他的方法，当然有些可以用动态规划。下图主要说明下这些算法数据结构之间的关系。图中黄色部分主要写明了这些算法和数据结构的一些关键点。     图中可以看到这样一些关系：extend-kmp 是kmp的扩展；ac自动机是kmp的多串形式；它是一个有限自动机；而trie图实际上是一个确定性有限自动机；ac自动机，trie图，后缀树实际上都是一种trie；后缀数组和后缀树都是与字符串的后缀集合有关的数据结构；trie图中的后缀指针和后缀树中的后缀链接这两个概念及其一致。     KMP算法请参考本博客内的这两篇文章：六、教你从头到尾彻底理解KMP算法、updated，六（续）、从KMP算法一步一步谈到BM算法。     后缀树的构造可以用Ukkonen算法在线性时间内完成[，但是不仅构造算法实现相当复杂，而且后缀树存在着致命弱点：空间开销大且对大字母表时间效率不理想。至于后缀数组下次阐述，这里简单介绍下extend-kmp。而在介绍extend-kmp之前，咱们先要回顾下KMP算法。  kmp     首先这个匹配算法，主要思想就是要充分利用上一次的匹配结果，找到匹配失败时，模式串可以向前移动的最大距离。这个最大距离，必须要保证不会错过可能的匹配位置，因此这个最大距离实际上就是模式串当前匹配位置的next数组值。也就是max{Aj 是 Pi 的后缀  j < i}，pi表示字符串A[1...i],Aj表示A[1...j]。模式串的next数组计算则是一个自匹配的过程。也是利用已有值next[1...i-1]计算next[i]的过程。我们可以看到，如果A[i] = A[next[i-1]+1] 那么next[i] = next[i-1]，否则，就可以将模式串继续前移了。 整个过程是这样的： void next_comp(char * str){    int next[N+1];    int k = 0;    next[1] = 0;    //循环不变性，每次循环的开始，k = next[i-1]     for(int i = 2 ; i <= N ; i++){       //如果当前位置不匹配，或者还推进到字符串开始，则继续推进       while(A[k+1] != A[i] && k != 0){            k = next[k];       }            if(A[k+1] == A[i]) k++;       next[i] = k;    }  }     复杂度分析：从上面的过程可以看出，内部循环再不断的执行k = next[k]，而这个值必然是在缩小，也就是是没执行一次k至少减少1；另一方面k的初值是0，而最多++ N次，而k始终保持非负，很明显减少的不可能大于增加的那些，所以整个过程的复杂度是O(N)。     上面是next数组的计算过程，而整个kmp的匹配过程与此类似。extend-kmp     为什么叫做扩展-kmp呢，首先我们看它计算的内容，它是要求出字符串B的后缀与字符串A的最长公共前缀。extend[i]表示B[i...B_len] 与A的最长公共前缀长度，也就是要计算这个数组。观察这个数组可以知道，kmp可以判断A是否是B的一个子串，并且找到第一个匹配位置？而对于extend[]数组来说，则可以利用它直接解决匹配问题，只要看extend[]数组元素是否有一个等于len_A即可。显然这个数组保存了更多更丰富的信息，即B的每个位置与A的匹配长度。     计算这个数组extend也采用了于kmp类似的过程。首先也是需要计算字符串A与自身后缀的最长公共前缀长度。我们设为next[]数组。当然这里next数组的含义与kmp里的有所过程。但它的计算，也是利用了已经计算出来的next[1...i-1]来找到next[i]的大小，整体的思路是一样的。     具体是这样的：观察下图可以发现     首先在1...i-1,要找到一个k，使得它满足k+next[k]-1最大，也就是说，让k加上next[k]长度尽量长。实际上下面的证明过程中就是利用了每次计算后k+next[k]始终只增不减，而它很明显有个上界，来证明整个计算过程复杂度是线性的。如下图所示，假设我们已经找到这样的k，然后看怎么计算next[i]的值。设len = k+next[k]-1(图中我们用Ak代表next[k]),分情况讨论： 如果len < i 也就是说，len的长度还未覆盖到Ai,这样我们只要从头开始比较A[i...n]与A的最长公共前缀即可，这种情况下很明显的，每比较一次，必然就会让i+next[i]-1增加一. 如果len >= i,就是我们在图中表达的情形，这时我们可以看到i这个位置现在等于i-k+1这个位置的元素，这样又分两种情况： 如果 L = next[i-k+1] >= len-i+1,也就是说L处在第二条虚线的位置，这样我们可以看到next[i]的大小，至少是len-i+1,然后我们再从此处开始比较后面的还能否匹配，显然如果多比较一次，也会让i+A[i]-1多增加1. 如果 L < len-i+1 也就是说L处在第一条虚线位置，我们知道A与Ak在这个位置匹配，但Ak与Ai-k+1在这个位置不匹配，显然A与与Ai-k+1在这个位置也不会匹配，故next[i]的值就是L。这样next[i]的值就被计算出来了，从上面的过程中我们可以看到，next[i]要么可以直接由k这个位置计算出来，要么需要在逐个比较，但是如果需要比较，则每次比较会让k+next[k]-1的最大值加1.而整个过程中这个值只增不减，而且它有一个很明显的上界k+next[k]-1 < 2*len_A,可见比较的次数要被限制到这个数值之内，因此总的复杂度将是O(N)的。  后记     先说几件个人私事：1、个人目前尚未确定工作，本月月底前往北京；2、11月3、4日去北京 · 国家会议中心参加2011中国移动开发者大会（ http://cmdc.csdn.net/ ），说不定在当场便见到正在读此文的你；3、11月5日中午，中软同盟会北京分会、河北（保定）分会聚会，期待到时候诸君到来。      再者，总是有不少朋友要求我推荐几本有关算法学习的书籍或资料，在此，负责任的推荐如下书籍或资料（排名不分先后）：1、算法导论；2、编程珠玑；3、编程之美；4、结构之法算法之道blog。5、任何一本数据结构教材。         但凡看书不必囫囵吞枣，最好是闲或静下心来，再者，一本书看一遍大都都未必能看懂。如我个人书桌上摆着的一本《深度探索c++对象模型》，常常是看了又淡忘，忘了又看。而且此书能解决你所有有关虚拟继承，虚拟函数的问题，这是你在网上所能看到或找到的千篇一律的文章或资料所不能相比的。如下面的两幅来自此书的分别阐述虚拟单一继承（图1），虚拟多重继承（图2）的图，一切遁入眼帘，昭然若揭（P152~168）： 图1       虚拟单一继承 图2       虚拟多重继承     下述代码是改编自深度探索c++对象模型上的，为了做些测试，先贴下来，日后再下结论： // virtual.cpp : 定义控制台应用程序的入口点。 //#include "stdafx.h" #include <iostream> using namespace std; class Base1 {  public:     Base1(){}     virtual ~Base1(){}     virtual void speakClearly(){}     virtual Base1* clone() const{       // cout<<"it is Base1"<<endl;       // return ;   } protected:   float data_Base1; }; class Base2 { public:   Base2(){}   virtual ~Base2(){}   virtual void mumble(){}   virtual Base2* clone() const{     // cout<<"it is Base2"<<endl;     // return;   } protected:   float data_Base2; }; class Derived:public Base1,public Base2 { public:   Derived(){}   virtual ~Derived(){}   virtual Derived* clone() const   {     // cout<<"it is Derived"<<endl;     // return;   } protected:   float data_Dervied; }; int main() {   Base1* p1=new Derived();   p1->clone();   delete p1;   return 0; }     ok，这些东西本与本文无关，只是恰好看到了，不想却偏离了主题，扯了这么多。最后，分享乔布斯的一句话：当你意识到你终将死去，你会放下所有一切。若有任何问题，欢迎不吝赐教。转载，请注明出处。谢谢。

2.3　硬件设计要点 本节以电路的电磁兼容设计为出发点，简要介绍在硬件开发工程中的注意事项和要点，并讲述了板级电路的信号完整性设计、电源完整性设计一般原则。 2.3.1　电磁兼容问题 电磁兼容性是电子设备或系统的主要性能之一，电磁兼容设计是实现设备或系统规定功能、使系统效能得以充分发挥的重要保证。设计人员必须在设备或系统功能设计的同时进行电磁兼容设计，充分考虑系统、分系统与周围环境之间的相互骚扰。电磁兼容设计的目的是使所设计的电子设备或系统在预期的电磁环境中实现电磁兼容。最终的设备或系统应能在预期的电磁环境中正常工作，无性能损失或故障。同时，该设备或系统应不会对其他设备或系统的正常运行产生不利的影响。本小节仅向读者介绍在电路设计或产品设计时，应遵循的基本原则和设计要领，读者可通过阅读相关书籍进行深入学习。1．电磁兼容设计的基本内容在电子系统的开发中，每部分设计都应意识到电磁骚扰（EMI）问题。采取正确的防护措施能有效减小电子系统本身的EMI发射。大部分的骚扰问题可以在设计与开发过程中解决。若在设计之初未进行电磁兼容的考量与设计，工程师们将不得不在事后投入更多的精力去解决系统的骚扰问题，事后解决这些问题的成本也将成倍增加。而抗扰度是电磁兼容设计考量的另一个方面，是对设备或系统承受外接干扰能力的一个度量。电磁兼容性设计又可分为系统内和系统间两部分。主要是对系统之间及系统内部的电磁兼容性进行分析、预测、控制和评估，实现电磁兼容和最佳效费比。（1）系统间电磁骚扰的预测和控制系统间电磁骚扰的预测。系统间电磁骚扰的预测往往涉及处在同一电磁环境中的一个或多个潜在的电磁骚扰源与一个或多个敏感设备之间的干扰预测。通过归纳出包含许多参数的全面方案，可推导出电磁干扰预测的基本方程。对有用信号的控制：频谱管理和规定发射功率、信号类型（调制和带宽）、线的空间覆盖范围、方向性和极化、使用时间和地点等。在设计阶段还应尽量减小镜像频率响应、谐波频谱电平，以及乱真发射和乱真响应。对人为骚扰的控制。系统间人为骚扰源主要是其他系统的发射机谐波和乱真发射、高压输电线、工科医设备等的骚扰发射，可参照有关的EMC标准来考量和控制。自然骚扰源通常无法控制，只有在系统性能设计时加以考虑，并采取适当的防护措施等。（2）系统内电磁兼容的预测和设计系统内电磁兼容的预测，可通过理论分析、软件仿真等手段进行评估。通常将系统内电磁兼容设计分为五个部分：印制电路板设计和元器件的选用、滤波、屏蔽、布线以及接地。2．电磁兼容设计的效费比在设备或系统设计的初始阶段，同时进行电磁兼容设计，把电磁兼容的大部分问题解决在设计定型之前，可得到最高的效费比。如果等到生产阶段再去解决，非但在技术上带来很大的难度，而且会造成人力、财力和时间的极大浪费。3．电磁兼容设计的目标电磁兼容设计的目标是实现EMC指标要求并通过EMC试验和认证。EMC试验的项目通常依据产品应用的领域，并参考国家标准或行业标准而定。4．电磁兼容设计的方法电磁兼容设计的基本方法是指标分配和功能分块设计。也就是首先要根据有关的标准（国际、国家、企业、特殊标准等）把整体电磁兼容指标逐级分配到各功能块上，细化成系统级的、设备级的、电路级的和元件级的指标。然后，按照要实现的功能和电磁兼容指标进行电磁兼容设计，如按电路或设备要实现的功能、骚扰源的类型、骚扰传播的渠道等。具体有时钟电路设计、防静电设计、防雷设计等。在电磁兼容设计中有许多应用课题要解决，如电磁波的散射、透射、传输、孔缝耦合、绕射理论等在实际问题中的求解问题，各种骚扰源的机理和特性，各种骚扰参数的计算和测试，各种结构的屏蔽效果，各种防护方法、测试方法、选用标准等。在进行电磁兼容设计时，可根据防护措施在实现电磁兼容时的重要性，分层依次进行设计，例如，第一层为有源器件的选择和印制版设计；第二层为接地设计；第三层为屏蔽设计；第四层为滤波设计，然后进行综合设计。这称为分层与综合设计法。随着电子产品性能的不断提高，电磁兼容性问题会愈来愈突出。CPU主频的提升、总线速度的提高、开关电源的广泛使用及小型化、板卡频繁升级使得开关频率不断增加等因素使电子产品的电磁兼容设计越来越迫切，也越来越复杂。这也促使人们在进行产品开发之初就必须认真考虑电磁兼容设计。 2.3.2　信号完整性 在低速电路中，电平跳变时信号上升时间较长，器件间的互联线对电路的功能的影响可以忽略不计，没有高速电路设计经验的设计人员通常意识不到信号完整性问题。随着器件输出开关速度的提高，上升时间大多处于皮秒级，按照低速电路设计方式设计的电路几乎无法工作，无一例外地产生了信号完整性问题。另外，对低功耗和速度追求使得内核电压越来越低，而较低的内核电压极易受环境干扰，若不加以控制有可能湮没在噪声中。因此系统能容忍的噪声余量越来越小，这也使得信号完整性问题更加突出。信号完整性（Signal Integrity，SI）是2000年后发展起来的新技术。SI解决的是在高速电路中信号传输过程中的质量问题。信号完整性可以泛指由互联线引起的所有电信号异常现象，包括：噪声、干扰和时序等。狭义的信号完整性是指信号电压（或电流）波形的形状及质量，包括反射和串扰。由于物理互联造成的干扰和噪声，使得连线上信号的波形外观变差，出现了异常形状的变形，这称为信号完整性被破坏。信号完整性问题是物理互联在高速情况下的直接结果。提示?物理互联：物理互联（Interconnect）包括芯片内连线、芯片封装、PCB板及电子系统连接等，它们极大地影响高速时的信号和电源分配网络质量。真实的互联线包括芯片内连线、压焊点、封装引线、芯片引脚，以及芯片外的PCB板线接头、线条、接插件、连接电缆等。此外还有各种无源元件，包括介质、基板、屏蔽盒、机壳、机架等。过去人们简单地将100MHz时钟作为高速电路与低速电路的分界线。事实上，高频不一定高速，低频也不见得低速。信号完整性问题的根源在于信号上升时间的减小，即使布线拓扑结构没有变化，当系统中的数字信号的上升沿小于1纳秒时，互联不再透明，也可能对电路和系统造成颠覆性后果。随着现代数字电子系统核心频率的不断提高，ASIC/PCB的设计必然面临日益突出的信号完整性问题。信号不完整问题是物理互联在高速下必须认真对待的问题，否则将直接导致严重后果。信号完整性以传输线、电磁学等为理论基础，结合复杂的算法和模型，解决高速信号传输中的以下几个问题：反射、轨道塌陷、串扰、过冲、振铃、地弹、多次跨越逻辑电平错误、阻抗控制和匹配、EMC、热稳定性、时序分析等。接下来简述几种常见的信号完整性问题。1．反射反射（reflection）是指传输线上有回波。信号功率（电压和电流）的一部分经传输线上传输到负载端，但是有一部分被反射回来形成振铃。当信号沿着传输线向前传播时，无论什么原因使瞬时阻抗发生了改变，部分信号都将沿着与原传播方向相反的方向反射，而另一部分将继续传播，但幅度有所改变。瞬时阻抗发生改变的地方称为阻抗突变，或简称突变。引起反射的原因可能是信号传输中途遇到电阻、电容、电感、过孔、接插件等。图2.29显示了信号反射引起的波形畸变。电路设计时在时钟输出信号上串接一个小电阻，采用阻抗匹配的方法解决信号反射问题。阻抗在信号完整性问题中占据极其重要的地位。 2．串扰串扰（Crosstalk）是指在两个不同的电性能网络之间的互作用。产生串扰的称为Aggressor（侵略者），而被干扰的称为Victim（受害者）。通常，每一个网络既是Aggressor，又是Victim。当两根信号线靠得很近时，一根信号线上的信号会通过电磁场耦合到另一根信号线上，这就是串扰。虽然被串扰影响的信号线上的波形不一定和邻近信号波形相似，也不一定有明显的规律，更多的是表现为噪声形式。随着集成电路和PCB设计的微型化、信号传输空间的聚敛，信号传输通道必然靠得很近，因此信号的串扰问题无法避免，同时也是必须认真对待的问题。串扰问题在当今的高密度电路板中一直困扰着嵌入式开发人员。串扰大小和电路板上的很多因素有关，PCB板层的参数、信号线间距、驱动端和接收端的电气特性及线端连接方式对串扰都有一定的影响。当然，信号传输通道的物理间距最容易控制，也是最常用的解决串扰的方法。3．轨道塌陷噪声不仅存在于信号网络中，也存在于电源分配系统中。在电源分配系统中，由于存在能源传输通道阻抗，当传输通道中的电流发生变化时，电压会发生一定程度的衰减，甚至大幅跌落，通常将这一过程形象地称为“轨道塌陷”。轨道塌陷有时会产生致命的问题，比如电压“塌陷”致使主控电路复位，对于安全性要求较高的应用场合，这种情况是不允许发生的。此外，高性能处理器集成的门数越来越多，开关速度也越来越快，在更短的时间内消耗更多的开关电流，可以容忍的噪声变得越来越小。但同时控制噪声越来越难，因为高性能处理器对电源系统有苛刻的要求，构建更低阻抗的电源分配系统变得越来越困难，阻抗控制成为高速电路设计中不可回避的问题。通常，信号完整性采取经验法则、解析近似、数值仿真、实际测量等方法解决。工程师通过加强理论学习，在工程实践中不断积累实践经验，并结合运用分析仿真工具，可以全面提升自己解决信号完整性问题的分析和解决能力。值得一提的是，现在的SI仿真引擎完全可以仿真高速数字 PCB，自动屏蔽SI问题并生成精确的“引脚到引脚”延迟参数。这使得器件模型和电路板制造参数的精确性成为决定仿真结果的关键因素。很多设计工程师首先仿真“最小”和“最大”的设计角落，然后采用相关的信息来解决问题并调整生产率。后制造阶段采取上述措施可以确保电路板的SI设计品质。在电路板装配完成之后，仍然有必要将电路板放在测试平台上，利用示波器或者时域反射计测量，将真实电路板和仿真预期结果进行比较。这些测量数据可以帮助工程师改进模型和制造参数，以便在下一次预设计调研工作中做出更佳的（更少的约束条件）决策。常见的仿真工具有SPICE、Mentor公司的Hyperlynx、Candence公司的SigXP、Ansoft公司的HFSS和Agilent公司的ADS等。上述内容仅简单介绍几种常见的信号完整性问题，目的在于让刚涉足高速电路设计的工程师有初步的认识。信号完整性问题涉及面比较广，只有通过深入学习理论和不断积累工程实践才能逐步提升对信号完整性问题的认识和把握。 2.3.3　电源完整性 在以往的电路设计中，人们为了简化问题，通常把电源和地当成理想的情况来处理，将主要精力集中研究信号线，但在高速电路设计中，这种处理方法将给产品带来潜在的隐患。电源完整性和信号完整性是紧密联系在一起的，从广义上说，信号电源完整性属于信号完整性研究范畴，电源完整性直接影响最终PCB板的信号完整性。电源完整性和信号完整性二者是密切关联的，而且很多情况下，影响信号畸变的主要原因是电源系统。例如，地反弹噪声太大、去耦电容的设计不合适、回路影响很严重、多电源/地平面的分割不好、地层设计不合理、电流不均匀等。过去人们更关注对集成电路功耗的控制，很少注意电源完整性，尽管电源完整性在决定电源和能耗方面具有举足轻重的作用。随着现代数字电子系统核心频率的不断提高，电源完整性已成为主导的设计约束条件之一。1．电源完整性概念简单地讲，电源完整性是指特定电源与理想状态的接近程度，具体取决于电源的自然特性。对于家用设备的电源来说，主要关心的是电压幅度和频率，即不管附近的负荷和用电限制如何变化，电压幅度和频率能够保持多大的稳定性。对于优秀的电源完整性而言，重要的是供电电压差值中发生的降压和过冲或瞬时（和静态）变化保持在很小的范围内，比如标称值的5%，从而使集成电路保持可预测的性能。造成电源不稳定的根源主要有两方面：一是器件在高速开关状态下瞬态的交变电流过大；二是电流回路上存在的电感。从表现形式上来看，又可以分为三类：同步开关噪声（Simultaneous Switch Noise， SSN，也称为Δi噪声）、非理想电源阻抗影响、谐振及边缘效应。有关这些主题的内容，这里仅作简要介绍，读者可参阅相关的书籍深入学习。2．电源完整性的主要问题（1）电源阻抗控制电源噪声的产生在很大程度上归结于非理想的电源分配系统。电源分配系统的作用就是给系统内的所有器件提供足够的电源，这些器件不但需要足够的功率消耗，同时对电源的平稳性也有一定的要求。大部分数字电路器件对电源波动的要求在正常电压的±5%范围内。由于电源平面阻抗的存在，在瞬间电流通过的时候，器件端的电压就会产生一定的压降和摆动。为了保证每个器件始终都能得到正常的电源供应，就需要对电源的阻抗进行控制，也就是尽可能降低其交直流阻抗。为了降低电源的电阻和电感，电源层和地层通常采用电阻率低的材料，在允许的情况下，使电源线尽可能加粗，并尽可能减少长度。事实上，目前市面上基本上都采用了大面积的铜皮层作为低阻抗的电源分配系统。基于电源阻抗的要求，以往的电源总线形式已经不再适用于高速电路。当然，电源层本身的低阻抗也不能满足设计的需要，需要考虑的问题还有很多，比如，芯片封装中的电源引脚、连接器的接口，以及高频下的谐振现象等，这些都可能会造成电源阻抗显著增加。解决这些问题的最常用的方法就是合理增加去耦电容。（2）同步开关噪声分析同步开关噪声是指当器件处于开关状态，产生瞬间变化的电流（di/dt），在经过回流途径上存在的电感时，形成交流压降，从而引起噪声，也称为Δi噪声。如果是由于封装电感而引起地平面的波动，造成芯片地和系统地不一致，这种现象称为地弹。同样，如果是由于封装电感引起的芯片和系统电源差异，就称为电源反弹。所以，严格来说，同步开关噪声并不完全是电源的问题，它对电源完整性产生的影响最主要表现为地/电源反弹现象。同步开关噪声主要是伴随着器件的同步开关输出（Simultaneous Switch Output， SSO）而产生，开关速度越快，瞬间电流变化越显著，电流回路上的电感越大，则产生的SSN越严重。基本公式为： VSSN=N•LLoop•(dI/dt) 其中I指单个开关输出的电流，N是同时开关的驱动端数目，LLoop为整个回流路径上的电感，而VSSN是同步开关噪声的大小。（3）谐振及边缘效应电源平面可等效为由很多电感和电容构成的网络，与通常LC网络一样，在一定频率下，由这些电容和电感构成的电源网络也会发生谐振现象，从而影响电源层的阻抗。除了谐振效应外，电源平面和地平面的边缘效应同样是电源设计中需要注意的问题，这里说的边缘效应就是指边缘反射和辐射现象。如果抑制了电源平面上的高频噪声，就能很好地减轻边缘的电磁辐射，通常采用添加去耦电容的方法来解决这一问题。边缘效应是无法完全避免的，在设计PCB时，要尽量让信号走线远离铺铜区边缘，以避免受到太大的干扰。

点击查看第一章点击查看第二章 第3章 计 算 平 台 学习目标 了解计算机的基本构成、工作原理和基本指令系统。 掌握微型计算机的硬件系统结构。 掌握微型计算机各主要部件的功能和主要技术指标。 了解操作系统的功能和分类。 计算机系统的硬件和软件是相辅相成的两部分。硬件是计算机系统赖以工作的实体，它是各种物理部件的有机结合；软件是计算机系统中的程序及其文档，是计算机硬件和应用程序之间的接口。本章介绍计算机硬件系统的基本工作原理、计算机的主要硬件部分、软件系统的分类和构成以及操作系统的基本功能。3.1　计算机硬件系统概述计算机系统是能按照给定的程序来接收和存储信息，自动进行数据处理和计算，并输出结果信息的机器系统。3.1.1　计算机系统构成计算机系统由硬件系统和软件系统两大部分组成。硬件系统是指构成计算机的物理设备的总称，包括计算机主机及其外围设备，主要由中央处理器、内存储器、输入/输出设备等组成。软件系统是指管理计算机软件和硬件资源，控制计算机运行的程序、指令、数据及文档的集合。广义地说，软件系统还包括电子和非电子的有关说明资料、说明书、用户指南、操作手册等。硬件是计算机系统的物质基础，软件是计算机系统的灵魂。只有硬件系统和软件系统这两者密切地结合在一起，才能构成一个正常工作的计算机系统。计算机系统的组成结构如图3-1所示。 图3-1　计算机的组成 计算机系统是由若干相互独立而又相互作用的要素组成的有机整体，不同要素间存在着依赖关系，是按层次结构组织起来的，这种层次关系可用图3-2示意说明。各层之间的关系是：下层是上层的支撑环境，即上层依赖于下层。计算机系统的最底层是硬件，不含任何软件的机器称为裸机。距离硬件最近的软件是操作系统，其他任何软件必须在操作系统的支持下才能运行。再向上的其他各层是各种实用软件。最上层是直接面向用户的应用程序。 图3-2 计算机系统不同要素间的层次关系 3.1.2　冯·诺依曼计算机的基本组成自第一台计算机诞生以来，计算机的制造技术已经发生了翻天覆地的变化。但到目前为止，计算机硬件系统的构成依然是基于冯·诺依曼计算机原理的。冯·诺依曼计算机的设计思想可以概括为3点：1）计算机由5个基本部分组成，即运算器、控制器、存储器、输入设备和输出设备。2）程序由指令构成，程序和数据都用二进制数表示。3）采用存储程序的方式，任务启动时程序和数据同时送入内存储器中，计算机在无须操作人员干预的情况下，自动地逐条取出指令和执行任务。数据在五大部件间传输需要有数据总线，总线内传输的信息可以分为数据流和控制流两大类，如图3-3所示。图中实线为数据流，虚线为控制流。从图中可以看出，计算机以运算器为中心，输入、输出设备与存储器间的数据传送都通过运算器。控制器与其他各个部件进行交互，它是发布命令的“决策机构”，完成协调和指挥整个计算机系统的操作。 图3-3 冯·诺依曼计算机基本结构 下面简单介绍冯·诺依曼计算机的组成部件。1. 运算器运算器是进行算术运算和逻辑运算的部件，主要由算术逻辑单元（Arithmetic Logic Unit，ALU）和一组寄存器构成。在控制器的控制下，运算器对内存储器或寄存器中的数据进行算术逻辑运算，再将结果送到内存储器或寄存器中。算术逻辑单元的功能是进行算术运算和逻辑运算。算术运算指进行加、减、乘、除等基本运算；逻辑运算指“与”“或”“非”等基本操作。2. 控制器控制器是计算机的指挥中心，它控制着整个计算机的各个部件有条不紊地工作，从而自动执行程序。控制器一般由程序计数器、指令寄存器、指令译码器、时序电路和控制电路组成。控制器的基本功能就是从内存取指令，对指令进行分析，给出执行指令时计算机各部件需要的操作控制命令。运算器在控制器的控制下，对取自内存或内部寄存器的数据进行算术或逻辑运算。控制器和运算器合在一起称为中央处理器，它是计算机的核心。3. 存储器存储器主要用来存放程序和数据，分为内存储器和外存储器两种。计算机运行时将需要CPU执行的程序和数据存放在内存中，运算的中间结果和最终结果也要送至内存存放。需要长期保存的信息送入外存储器。4. 输入设备输入设备用来接收用户输入的原始数据和程序，并将它们转换为计算机能识别的二进制数存放到内存中。5. 输出设备输出设备用于将存放在内存中的数据转变为声音、文字、图像等易于被人们理解的表现形式。3.2　计算机基本工作原理计算机能够按照指定的要求完成复杂的科学计算或数据处理，这些功能是通过程序来实现的。计算机的工作过程就是自动连续地执行程序的过程，而程序是由一系列指令构成的。无论多么复杂的操作都要转化成一条条的指令，由计算机执行。3.2.1　指令和指令系统指令就是让计算机完成某个操作所发出的命令，由二进制代码构成。一条指令通常由两部分组成，前面是操作码部分，后面是操作数部分，如下所示：操作码指明该指令要完成的操作，如加、减、乘、除等。操作数是指参与运算的数或者其所在的内存单元的地址。操作数多数情况下是数据所在的地址，所以也常称为地址码。计算机是通过执行指令序列来解决问题的，因此每种计算机都有一组基本的指令集供用户使用，这组指令集即为计算机的指令系统。不同类型的计算机，指令系统所包含的指令数目与格式也不同。指令系统一般都应具有以下几类指令：1. 数据传送指令数据传送指令负责把数据、地址或立即数传送到寄存器或存储单元中。一般可分为通用数据传送指令、累加器专用传送指令、地址传送指令和标志寄存器传送指令。2. 数据处理指令数据处理指令主要是对操作数进行算术运算和逻辑运算。3. 程序控制转移指令程序控制转移指令是用来控制程序中指令的执行顺序，如条件转移、无条件转移、循环、子程序调用、子程序返回、中断、停机等。4. 输入/输出指令输入/输出指令用来实现外围设备与主机之间的数据传输。5. 其他指令其他指令包括对计算机的硬件进行管理的指令等。3.2.2　程序的执行过程计算机的工作过程实际上是快速执行指令的过程，为了解决特定的问题，人们编制了一条条的指令构成指令序列，这种指令序列就是程序。正确、合理、高效的程序代码，可以保证计算机能够解决问题，并加快计算机解决问题的速度。计算机执行指令一般分为两个阶段：第一阶段，将要执行的指令从内存取到CPU内；第二阶段，CPU对获取的指令进行分析译码，判断该条指令要完成的操作，然后向各部件发出完成该操作的控制信号，完成该指令的功能。当一条指令执行完后就进入下一条指令的取指操作。一般把计算机完成一条指令所花费的时间称为一个指令周期。第一阶段取指令的操作称为取指周期，将第二阶段称为执行周期。CPU不断地读取指令、分析指令、执行指令的过程就是程序的执行过程。下面以计算机指令070270H的执行过程为例，来说明计算机的基本工作原理。070270H指令占3个字节，它是一个累加器加法指令，例如累加器当前的数据是08H，该条指令要实现将内存单元0270H中的数据09H与累加器中的08H相加，并将结果存储于累加器中。１. 取指令假设程序计数器的地址为0100H，从内存储器中取出指令070270H，并送往指令寄存器，如图3-4中的①和②所示。2. 分析指令对指令寄存器中存放的指令070270H进行分析，由译码器对操作码07H进行译码，将指令的操作码转换成相应的控制电位信号，由地址码0270H确定操作数地址，如图3-4中的③和④所示。3. 执行指令由操作控制线路发出完成该操作所需要的一系列控制信息，来完成该指令所要求的操作。例如做加法指令，取内存单元0270H的值和累加器的值相加，结果放在累加器中，如图3-4中的⑤、⑥、⑦、⑧所示。4. 读取下一条指令一条指令执行完毕后，程序计数器加1，指向下一条指令，如图3-4中的⑨所示（如果有跳转指令，程序计数器跳转到给定的指令处），然后继续读取并执行0103H中的指令。 图3-4　指令的执行过程 3.3　微型计算机硬件组成当前，微型计算机得到越来越广泛的应用，成为计算机中发展最快的分支之一。下面主要介绍微型计算机的硬件结构和制造技术。3.3.1　微型计算机的主要性能指标衡量一台微型计算机的主要性能指标有运算速度、字长、主频、内存容量、存储周期、外围设备配置、可用性、可靠性和可维护性等指标。其中，主频、运算速度、存储周期是衡量计算机速度的性能指标。外围设备配置是指光盘驱动器的配置、硬盘的接口类型与容量、显示器的分辨率、打印机的型号与速度等性能。可靠性指在给定时间内计算机系统能正常运转的概率，通常用平均无故障时间表示。无故障时间越长，表明系统的可靠性越高。可用性指计算机的使用效率，它用计算机系统在执行任务的任意时刻能正常工作的概率表示。可维护性指计算机的维修效率，通常用平均修复时间来表示。此外，还有一些评价计算机的综合指标，如性能价格比、兼容性、系统完整性、安全性等。3.3.2　主板主板（main board）也叫主机板、系统板或母板。主板是装在机箱内、包含总线的多层印刷电路板，上面分布着构成微型计算机主系统电路的各种元器件和接插件。CPU等硬件和外设通过主板有机地组合成一套完整的系统。计算机主板既是连接各个部件的物理通路，也是各部件之间数据传输的逻辑通路。计算机在运行时对系统内的部件和外部设备的控制都必须通过主板来实现，因此，计算机的整体运行速度和稳定性在很大程度上取决于主板的性能。主板上面有芯片组、各种I/O控制芯片、扩展槽、CPU插座、电源插座等元器件。随着计算机技术的发展，高度整合的主板成为主板发展的一个必然趋势，现在的主板可以集成声卡、网卡、显卡以及各种新型接口。主板的结构标准是指主板上各元器件的布局排列方式和主板的尺寸大小、形状及所使用的电源规格等。目前的主流主板结构标准是Intel公司在1995年提出的ATX。ATX的特点是插槽多，扩展性强。ATX中CPU插座、内存插槽的位置布局更加合理，便于各种扩展卡的拆装。CPU靠近电源，可以更好地利用电源的通风冷却系统为CPU散热。硬盘、光驱等连接线的位置更接近于硬盘和光驱实体。ATX规范对整机的电源系统也做了改进，实现绿色节能，使PC机能工作在低电压的工作状态。图3-5所示为一个实际的ATX主板的布局结构及外形图。 图3-5 ATX结构的主板 有一种外形规格较小的Micro-ATX主板结构，它是ATX结构的简化版，又称Mini ATX或小板。这种主板扩展插槽较少，PCI插槽数量在3个或3个以下，多用于品牌机并配备小型机箱。Min-ITX主板的尺寸比Mini ATX主板还要小，耗电量更低，因此不需要使用风扇进行散热。Mini-ITX 主板只有一个用于扩展卡的 PCI 插槽。 Mini-ITX 外形规格的计算机可用于不便放置较大或运行有噪声的计算机的地方。除以上主板外，主板的结构标准还有NLX、Flex ATX、E-ATX（Extended ATX）等。NLX和Flex ATX是ATX的变种，多见于国外的品牌机。E-ATX主板尺寸较大，一般都需要特殊EATX机箱，大多支持两个以上CPU，多用于高性能工作站或服务器。目前主要的主板制造厂商有华硕（ASUS）、技嘉（GIGABYTE）和微星（MSI）等。下面以ATX结构的主板为例介绍主板的各项功能。1. 芯片组芯片组（chipset）是固定在主板上的一组超大规模集成电路芯片的总称，它负责连接CPU和计算机其他部件。芯片组是主板的灵魂，其性能的优劣，决定了主板性能的好坏与级别的高低。目前CPU的型号与种类繁多、功能特点不一，如果芯片组不能与CPU良好地协同工作，将严重地影响计算机的整体性能，甚至导致计算机不能正常工作。近年来，芯片组技术突飞猛进，每一次新技术的进步都带来计算机性能的提高。目前，比较典型的芯片组通常由两部分构成：南桥芯片和北桥芯片。南桥芯片是距离CPU较远的芯片，主要负责管理PCI和PCIE插槽、USB总线、SATA或SCSI接口、网卡、BIOS以及其他周边设备的数据传输。北桥芯片主要负责管理CPU、AGP或PCIE总线以及内存之间的数据传输。北桥芯片的数据处理量非常大，发热量也越来越大，所以现在的北桥芯片都覆盖着散热片，用来加强北桥芯片的散热，有些主板的北桥芯片还会加配风扇进行散热。一般来说，芯片组的名称就是以北桥芯片的名称来命名的。考虑到北桥芯片与处理器之间的通信最密切，为提高通信性能、缩短传输距离，北桥芯片距离CPU很近。目前，很多厂家将北桥集成整合到了CPU内部。生产芯片组的厂家主要有Intel、AMD、VIA、SiS、ULI、Ali、NVIDIA、IBM等。在台式机中，Intel芯片组占据Intel平台最大的市场份额。AMD芯片组在AMD平台中也占有很大的市场份额，NVIDIA、VIA、SiS基本退出主板芯片组市场。在笔记本、服务器/工作站领域，由于Intel平台具有的绝对优势，因此Intel的芯片组也占据了最大的市场份额。2. 外围设备接口微型计算机的外围设备（简称外设）接口有很多接口标准。图3-6所示为一组外围设备接口示例。 图3-6　外围设备接口 （1）串行接口和并行接口串行接口简称串口，通常指COM接口。串行接口的数据和控制信息按一位位的顺序传送。串行接口的特点是通信线路简单，只要一对传输线就可以实现双通信，从而降低了成本，适合远距离通信，但是利用串行接口通信速度会慢一些。串行接口按电气标准和协议分为RS-232、RS-422、RS-485等，一般用来连接串行鼠标和外置Modem等设备。并行接口又称并口，可实现数据的各位同时进行传送，其特点是传输速度快，但并行传送的线路长度受到限制。因为线路越长，传输的信号干扰就会加强，数据也就容易出错。现有计算机基本上都配有25针D形接头的并行接口，称为打印终端接口 （Line Print Terminal，LPT），如LPT 1、LPT 2……，一般用来连接打印机或扫描仪。在目前的品牌主板上，上述串口和并口已不再作为标配向用户提供，取而代之的是性能更高的USB接口。（2）USB接口通用串行总线接口标准（Universal Serial Bus，USB）是连接计算机系统与外围设备的一种串口总线标准，也是一种输入/输出接口的技术规范，被广泛地应用于个人计算机和移动设备等信息通信产品，并扩展至摄影器材、数字电视（机顶盒）、游戏机等其他相关领域。USB接口的主要优点为速度快、连接简单快捷、无须外接电源、统一输入/输出接口标准、支持多设备连接、支持热插拔、具有即插即用功能、具有高保真音频和良好的兼容性，USB接口现已成为PC 领域最受欢迎的总线接口标准。2008年发布的USB 3.0，其理论上的最大传输带宽为5.0Gbit/s。 2013年发布的USB 3.1，传输速率为10Gbit/s，采用的新型Type C接口不再分正反。2017年9月，出现了USB 3.2，速度为20Gbit/s。USB-IF（USB标准组织）重新调整了USB 3.x系列版本的命名，USB 3.0、USB 3.1、USB 3.2都统一在USB 3.2的序列之下，分别叫作USB 3.2 Gen 1、USB 3.2 Gen 2、USB 3.2 Gen 2x2。其中，最后一个命名源于使用了Type-C接口的双通道模式。（3）IEEE 1394接口IEEE 1394接口是苹果公司开发的串行标准，中文译名为火线接口（firewire）。1995年，IEEE把它作为正式的标准，编号为1394。作为一种数据传输的开放式技术标准，IEEE 1394被应用在众多领域，包括数码摄像机、高速外接硬盘、打印机和扫描仪等多种设备。1394接口有两种常用的接口形式：6芯以及4芯小型接口，6芯接口中除了数据线外，还包括有一组电源用以对连接的外设进行供电。4芯接口只有两对数据线而无电源，多使用在DV本体和笔记本计算机上。不同标准的接口和数据线之间可以用转换器进行转换连接。图3-7列出了4芯接口以及4芯和6芯数据线。 图3-7 　IEEE 1394接口 （4）其他接口PS/2接口最初是IBM公司的专利，是ATX主板的标准接口。PS/2接口是一种6针的圆形接口，仅能用于连接键盘和鼠标（鼠标接口用绿色标识，键盘接口用紫色标识）。PS/2接口的传输速率比COM接口稍快一些，而且不占用串口资源。PS/2接口是带电的（5 V电压），不支持热插拔。开机时插拔很可能烧坏主板上PS/2接口附近的电路。3. 总线扩展插槽总线（bus）是计算机内部传输指令、数据和各种控制信息的高速通道，按照总线的功能和传输数据的种类可以分为3类。 数据总线（Data Bus，DB）：数据总线是CPU和内存储器、I/O接口间传送数据的通路。由于它可在两个方向上往返传送数据，故是一种双向总线。 地址总线（Address Bus，AB）：地址总线是CPU向内存储器和I/O接口传送地址信息的通路，它是单方向的，只能从CPU向外传送。 控制总线（Control Bus，CB）：控制总线是CPU向内存储器和I/O接口传送控制信号以及接收来自外围设备向CPU传送应答信号、请求信号的通路。控制总线上的信息是双向传输的。 主板上的总线扩展插槽是CPU通过系统总线与外围设备联系的通道，系统的各种扩展接口卡都插在扩展插槽上，如显卡、声卡、网卡、采集卡及Modem等。微机总线的结构特点是标准化和开放性。从发展过程看，早期的微机总线结构标准有PC总线、ISA（Industry Standard Architecture）工业标准体系总线、PCI（Peripheral Component Interconnect）外设组件互连总线、PCI-X（PCI总线的改版，有更高的带宽，多用于服务器）和AGP（Accelerated Graphics Port）图形加速端口总线。目前，PCI-E（PCI Express）是新一代的总线接口，PCI-3.0标准的总线接口数据传输速率可达8GT/s。在2019年问世的PCI-E 5.0，其传输速度可达32GT/s。PCI-E的接口根据总线位宽不同而有所差异，包括X1、X4、X8以及X16。主板中的PCI插槽离CPU远些，数据通过南桥芯片再到CPU。PCI-E靠近CPU，直接与CPU进行交互。其中PCI-E X8/X16用来扩展显卡等设备，用于替代AGP插槽。PCI-E X4用来扩展磁盘阵列卡等中速设备，用于替代PCI-X插槽。PCI-E X1/X2主要是用来扩展声卡、网卡等低速设备，用于淘汰PCI插槽。另外还有Mini PCI E接口，常用来接驳无线模块。 4. BIOS与CMOSBIOS（Basic Input Output System）即基本输入/输出系统，它是一组固化到计算机主板的ROM（Read Only Memory，只读存储器）芯片上的含有计算机启动指令的系统程序。存放BIOS的ROM芯片也称为ROM BIOS。BIOS保存着计算机最重要的基本输入/输出程序、系统设置信息、开机后自检程序和系统自启动程序。其主要功能是为计算机提供最底层的、最直接的硬件设置和控制。计算机开机后，由BIOS初始化硬件，然后搜索一个引导设备（如硬盘、U盘或光驱）来启动相应的系统软件。目前市面上较流行的主板BIOS主要有 Award BIOS、AMI BIOS、Phoenix BIOS等。由于用于固化BIOS软件的BIOS芯片是只读的，即使计算机断电，芯片里的内容还是会保留不变。如果需要修改计算机硬件的设置，可以在计算机启动时通过按相应的键进入BIOS设置界面来做一些设置，比如硬件的启动顺序、电压、频率、开关、模式等。这些利用BIOS设置的计算机硬件配置信息需要保存在一个可读/写的RAM（Random Access Memory，随机存储器）芯片上。这个芯片就是CMOS（Complementary Metal Oxide Semiconductor，互补金属氧化物半导体）芯片。CMOS芯片一个特点—断电之后数据会丢失，所以主板上都配有时钟电路（带有3V纽扣电池）来给CMOS芯片供电，以保证数据不丢失。在主板中，CMOS芯片通常放置在纽扣电池的旁边。3.3.3　中央处理器1. CPU的组成和基本结构CPU是一块超大规模集成电路芯片，它是整个计算机系统的核心。CPU主要包括运算器、控制器和寄存器3个部件。运算器的主要部件是算术逻辑单元，其核心功能是实现数据的算术运算和逻辑运算。运算器主要完成各种算术运算和逻辑运算；控制器是指挥中心，主要完成指令的分析、指令及操作数的传送、产生各种控制信号、协调整个CPU需要的时序逻辑等。内部寄存器包括通用寄存器和专用寄存器，其功能是暂时存放运算的中间结果或数据。2. Intel CPU的发展1971年，Intel 公司首先推出Intel 4004 CPU，然后经历了286、386、486的发展。1993年开始推出了流行长达13年之久的“奔腾”处理器系列。2006年7月，Intel发布了基于Core微架构的Core 2（酷睿 2）处理器。Core 2分双核（Duo）、四核（QUAD）、八核3种。2011年1月，Intel第二代智能Core i系列发布，分为i7/i5/i3（分别代表高、中、低端）三大系列，工艺统一为32 nm，并且在除了六核产品之外都内置了图形处理器（Graphic Processing Unit，GPU）芯片。2012～2018年间，Intel相继发布了酷睿三代到酷睿九代处理器。2017年出现了i9系列。目前的酷睿九代可以达到8核16线程，最大睿频（动态加速频率）可达5GHz。Intel几个时期发布的CPU外形如图3-8所示。 图3-8　Intel CPU系列外形图 3. CPU插槽CPU具备不同的外形规格，这就要求主板上配备特定的插槽或插座。CPU插槽指用于安装CPU的插座，不同类型的CPU具有不同的外形规格，它们使用的CPU插座结构是不一样的。LGA、PGA、BGA是3种CPU的封装形式，全称分别是栅格阵列封装、插针网格阵列封装和球栅阵列结构封装。LGA是Intel自己定义的一个针脚插座，是触点型、没有针的CPU。PGA封装的芯片内外有多个方阵形的插针，安装时，将芯片插入专门的ZIF CPU插座，该技术一般用于插拔操作比较频繁的场合。BGA的CPU是没有插座的，使用的是球型矩阵锡球，直接焊接在主板上，这种CPU通常是为轻薄笔记本式计算机设计的。现在Intel产品接口的布局是高端型号用LGA2011，主流型号用LGA1151、LGA1155，后面4位数字代表着接口针脚数。AMD CPU常采用针脚式封装，主流接口型号是 Socket AM4。4. CPU的性能指标CPU性能的高低直接决定着一个微机系统的性能。CPU的性能主要由以下几个因素决定：（1）字长CPU的字长是衡量计算机性能的一个重要指标，其大小直接反映计算机的数据处理能力，字长越长，CPU可同时处理的数据二进制位数就越多，运算能力就越强，计算精度就越高。目前的酷睿系列多为64位CPU。（2）主频、超频、睿频CPU主频又称为CPU工作频率，即CPU内核运行时的时钟频率。一般来说，主频越高，一个时钟周期内完成的指令数也越多，CPU的速度也就越快。由于CPU的内部结构不尽相同，所以并非所有时钟频率相同的CPU性能都一样。CPU超频是指通过某些设置，使CPU的主频超过固有的频率。超频的方法一个是硬件设置，一个是软件设置。其中，硬件设置比较常用，它又分为跳线设置和BIOS设置两种。睿频指的是应对复杂应用时，处理器可以自动提高运行主频，以符合高工作负载的应用需求。当进行工作任务切换时，如果只有内存和硬盘在进行主要的工作，处理器会立刻处于节电状态。这样既保证了能源的有效利用，又使程序速度大幅提升。睿频较高时，热功耗增加，发热量变大，性能更强。但最新的睿频标准限制了维持在高主频的时间，即只有在程序真正需要提升主频来更快地计算数据时，才允许处理器超过散热设计功耗（Thermal Design Power，TDP）一小段时间来达到最大高睿频频率以获取最快的运算效能。（3）外频外频是CPU与主板之间同步运行的速度，它是由主板为CPU提供的基准时钟频率。例如，100 MHz外频特指数字脉冲信号在每秒振荡一亿次。CPU的外频决定着整个计算机的运行速度。外频越高，CPU与外围设备之间同时可以交换的数据量越大。主频大小用公式表示为：主频=外频×倍频。其中，倍频是指CPU主频与外频之间的相对比例关系。在相同的外频下，倍频越高，CPU的频率也越高。但实际上，在外频相同的前提下，高倍频的CPU本身意义并不大。这是因为CPU与系统之间的数据传输速率是有限的，一味追求高倍频而得到高主频的CPU就会出现明显的“瓶颈”效应，CPU从系统中得到数据的极限速度仍不能满足CPU运算的速度。（4）核心数量和线程数核心数量是指一个CPU中集成的计算内核的数量，常见的有单核、双核、四核、六核和八核。譬如双核就是两个相对独立的CPU核心单元组，它们可以同时处理两个数据流。线程数是一种逻辑的概念，它通过算法模拟出CPU的核心数量。譬如，双线程指一个核心单元组可以运行两个线程，让计算机认为这个核心有两个虚拟核心。例如，酷睿i9 9900K是八核、十六线程的。（5）制造工艺制造工艺的单位通常用纳米（nm）表示，它是指集成电路中晶体管门电路的尺寸。制造工艺的趋势是向密集度更高的方向发展。密度愈高的IC设计，意味着在同样面积的IC中，可以拥有密度更高、功能更复杂的电路设计。从2015年Intel发布的第五代酷睿CPU开始，Intel已经把产品制造工艺升级到14 nm工艺。2018年的第九代酷睿仍采用14nm的制造工艺，不过其功耗和性能方面有了显著的提升，称之为14nm++。AMD的CPU制造工艺目前可以达到12nm。（6）CPU架构CPU架构指CPU接收和处理信号的方式，及其内部元件的组织方式，先进的架构可以使CPU在单位时间内执行更多的指令。目前CPU分类主要分为两大阵营，一个是以Intel、AMD为首的复杂指令集CPU，另一个是以IBM、ARM为首的精简指令集CPU。两个不同类型的CPU，其产品的架构也不相同，例如，Intel、AMD的CPU是X86架构的，而IBM公司的CPU采用PowerPC架构，ARM公司的是ARM架构。（7）缓存缓存大小也是衡量CPU性能的重要指标之一，而且缓存的结构和大小对CPU速度的影响非常大，CPU内缓存的运行频率极高，一般是和处理器同频运作，工作效率远远大于系统内存和硬盘。3.3.4　存储器存储器是计算机系统中用来存储程序和数据的设备，存储器的容量和性能在很大程度上影响着整个计算机的功能和工作效率。存储器分为内存储器和外存储器。1. 内存储器内存储器又称主存储器，简称内存。内存位于系统主板上，可以直接与CPU进行信息交换，运行速度较快，容量相对较小。内存储器主要用来存放计算机系统中正在运行的程序及处理程序所需要的数据和中间计算结果，以及与外部存储器交换信息时作为缓冲。内存控制器是计算机系统内部控制内存并且使内存与CPU之间交换数据的重要组成部分。内存控制器决定了计算机系统所能使用的最大内存容量、内存类型和速度、数据宽度等重要参数，从而也对计算机系统的整体性能产生较大影响。（1）内存储器的主要技术指标 内存容量：在主内存储器中含有大量存储单元，每个存储单元可存放8位二进制信息。内存容量反映内存存储数据的能力。内存容量越大，能处理的数据量就越大，其运算速度一般也越快。一些操作系统和大型应用软件会对内存容量有要求。其中最大内存容量是指主板最大能够支持的内存的容量。一般来讲，最大容量数值取决于主板芯片组和内存扩展槽等因素。 内存主频：内存主频表示内存的速度，它代表着该内存所能达到的最高工作频率。内存主频是以MHz为单位来计量的。内存主频越高，在一定程度上代表着内存所能达到的速度越快。 读/写时间：从存储器读一个字或向存储器写入一个字所需的时间称为读/写时间。两次独立的读/写操作之间所需的最短时间称为存储周期。内存的读/写时间反映了存储器的存取速度。 （2）内存的分类 ROM：ROM中的数据理论上是永久的，即使在关机后，保存在ROM中的数据也不会丢失。因此，ROM常用于存储微型机的重要信息，如主板上的BIOS等。PROM（Programmable ROM，可编程ROM）可以用专用的编程器进行一次写入，成本比ROM高，写入速度低于量产的ROM，所以仅适用于少量需求或ROM量产前的验证。EPROM（Erasable Programmable ROM，可擦写可编程ROM）可以通过EPROM擦除器利用紫外线照射擦除数据，并通过编程器写入数据。EEPROM（Electrically Erasable Programmable ROM，电可擦写可编程ROM）可直接用编程电压进行信息的擦除和写入。Flash Memory（闪存存储器）或Flash ROM属于EEPROM类型，可以直接使用工作电压擦除和写入。它既有ROM的特点，又有很高的存取速度，功耗很小。 目前Flash Memory被广泛用在PC机的主板上，用来保存BIOS程序，便于进行程序的升级。Flash Memory也用于硬盘中，使硬盘具有抗震、速度快、无噪声、耗电低的优点。 RAM：RAM主要用来存放系统中正在运行的程序、数据和中间结果，以及用于与外围设备的信息交换。它的存储单元可以读出，也可以写入。一旦关闭电源或发生断电，RAM中的数据就会丢失。随机是指数据不是线性依次存取，而是自由指定地址进行数据存/取。 根据存储原理，RAM又分为SRAM（Static Random Access Memory，静态随机存取存储器）和DRAM（Dynamic Random Access Memory，动态随机存取存储器）。SRAM是一种具有静止存取功能的内存，不需要刷新电路即能保存它内部存储的数据，因此SRAM具有较高的性能。但是，SRAM的集成度较低，不适合做容量大的内存，一般是用在处理器的缓存中。DRAM每隔一段时间要刷新充电一次，否则内部的数据即会消失，SDRAM（Synchronous Dynamic Random Access Memory，同步动态随机存储器）就是其中的一种。SDRAM工作时需要同步时钟，内部命令的发送与数据的传输都以它为基准。SDRAM从发展到现在已经经历了SDR SDRAM、DDR SDRAM、DDR2 SDRAM、DDR3 SDRAM和DDR4 SDRAM。由于DRAM存储单元的结构能做得非常简单，所用元件少、功耗低，已成为大容量RAM的主流产品。DDR SDRAM（Dual Data Rate SDRAM，双倍速率SDRAM）简称DDR。DDR在时钟信号上升沿与下降沿各传输一次数据，这使得DDR的数据传输速率为传统SDRAM的两倍。DDR2内存拥有两倍于DDR的预读取能力，即在每个时钟周期处理多达4 bit的数据。DDR2在封装方式上进行改进，而且DDR2耗电量更低，散热性能更优良。DDR3是针对Intel新型芯片的新一代内存技术，主要是满足计算机硬件系统中CPU对内存带宽的要求，一般内存主频在1333 MHz以上。同DDR2相比，DDR3的主要优势如下：工作频率更高，每个时钟周期可预处理8 bit的数据；发热量较小；内存电压小（标准电压1.5V），降低了系统平台的整体功耗；通用性好。DDR4采用16 bit预取机制，同样内存频率下，其理论速度是DDR3的两倍，最高可达3200MHz。DDR4内存的标准工作电压为1.2V，具有超高速、低耗电、高可靠性等特点。（3）内存与CPU通信Intel CPU最初通过前端总线（Front Side Bus，FSB）连接到北桥芯片，进而通过北桥芯片和内存、显卡交换数据。CPU与内存的数据传输遵循“CPU—前端总线—北桥—内存控制器”模式。所以，前端总线是CPU和外界交换数据的最主要通道。虽然前端总线频率可以达到1600MHz（4倍于外频工作），但与不断提升的内存频率（特别是高频率的DDR3、DDR4）、高性能显卡（特别是多显卡系统）相比，前端总线成为CPU与芯片组和内存、显卡等设备传输数据的瓶颈。为了解决这一问题，Intel将内存控制器集成到CPU中，CPU无须通过北桥芯片就能与内存通信。用于CPU和系统组件之间通信的快速通道互联（Quick Path Interconnect，QPI）技术也取代了前端总线。QPI是一种实现点到点连接的技术，它支持多个处理器的服务器平台，QPI可以用于多处理器之间的互联。Intel采用了4+1 QPI互联方式（4个处理器，1个I/O），这样多处理器的每个处理器都能直接与物理内存相连，每个处理器之间也能彼此互联来充分利用不同的内存，可以让多处理器的访问延迟下降、等待时间变短，只用一个内存插槽就能实现与四路处理器通信。由于在很多Intel CPI架构中，北桥芯片都被集成到了CPU中，所以QPI总线也被集成到CPU内部， CPU内部的北桥芯片通过直接媒体接口（Direct Media Interface，DMI）总线与南桥芯片通信。与FSB相比，QPI使处理器和系统组件之间的通信更加方便。处理器之间的峰值带宽可达96GB/s，满足CPU之间、CPU与芯片组之间的数据传输要求。QPI互联架构具备可靠性、实用性和扩展性等性能。而AMD推出的HT（Hyper Transport）技术，本质上是一种为主板上的集成电路互连而设计的端到端总线技术，目的是加快芯片间的数据传输速度，即为AMD CPU到主板芯片之间的连接总线（如果主板芯片组是南北桥架构，则指CPU到北桥）加速。高速缓冲存储器（Cache）是介于CPU和主存储器之间的规模较小但速度很高的存储器，它可以用高速的静态存储器芯片实现，或者集成到CPU芯片内部，用于存储CPU最经常访问的指令或者操作数据。当CPU向内存中写入或读出数据时，这个数据也被存储进高速缓冲存储器中。当CPU再次需要这些数据时，CPU就从高速缓冲存储器读取数据，而不是访问较慢的内存。若Cache中没有需要的数据，CPU会再去读取内存中的数据。目前，CPU一般设有一级缓存（L1 Cache）、二级缓存（L2 Cache）和三级缓存（L3 Cache）。L1 Cache是CPU内核的一部分，主要负责CPU内部的寄存器和外部Cache之间的缓冲。内置的L1 Cache的容量和结构对CPU的性能影响较大。不过在CPU管芯面积不能太大的情况下，L1 Cache的容量不可能做得太大。一般服务器CPU的L1 Cache的容量是32～56 KB。 L2 Cache用于存储CPU处理数据时需要用到，但L1 Cache无法存储的数据，以前PC机L2 Cache容量最大为512KB，现在笔记本式计算机中也可以达到2MB，而服务器和工作站上所用CPU的L2 Cache更高，可以达到8MB以上。L3 Cache是为读取二级缓存后未命中的数据设计的一种缓存。在拥有L3 Cache的CPU中，只有约5%的数据需要从内存中调用，这进一步提高了CPU的效率。CPU内缓存的运行频率极高，一般是和处理器同频运作。缓存的结构和容量大小对CPU速度的影响非常大。目前，主流的CPU往往具备多级缓存，如Intel公司的CPU酷睿i9 9900K配备了2MB的L2 Cache和16MB的L3 Cache。（4）内存插槽内存正反两面都带有金手指，通过金手指与主板上的内存插槽相连。SIMM（Single Inline Memory Module，单列直插内存模块）是较早的内存插槽类型，后来被DIMM（Dual Inline Memory Module，双列直插内存模块）技术取代。DDR DIMM则采用184 Pin DIMM结构，金手指每面有92 Pin，金手指上只有一个卡口。DDR2 和DDR3为240 Pin DIMM结构，DDR4是288 Pin DIMM结构。图3-9所示为DDR4内存和对应的288 Pin DIMM插槽。 图3-9　DIMM插槽 为了满足笔记本电脑对内存尺寸的要求，出现了SO-DIMM（Small Outline DIMM Module，小外形双列内存模组）插槽。SO-DIMM根据SDRAM和DDR内存规格不同而不同。目前，笔记本式计算机中常用的内存条接口有DDR3 的204 Pin SO-DIMM接口和DDR4的260 Pin SO-DIMM接口。主要的内存厂家有Kingston（金士顿）、Samung（三星）和Crucial（英睿达）等。2. 外存储器外存储器又称辅助存储器，简称外存。移动硬盘、光盘、闪存盘等存储器都是CPU不能直接访问的外存储器，需要经过内存以及I/O设备来交换其中的信息。外存储器存储容量大，存取速度相对内存要慢得多，但存储的信息稳定，可以长时间保存信息。外存储器主要用于存放等待运行或处理的程序或文件。（1）闪存卡与读卡器 闪存卡（flash card）是利用闪存技术实现存储电子信息的存储器，是一种非易失性存储器，即使断电数据也不会丢失。闪存卡体积小，常用在数码照相机、掌上计算机、MP3播放器和手机等小型数码产品中作为存储介质。 闪存技术分为NOR型和NAND型闪存。NOR型闪存价格比较贵，容量较小，适用于需要频繁读/写的场合，如智能手机的存储卡。NAND型闪存成本低，且容量大。市面上的闪存卡产品一般都使用NAND型闪存，如Smart Media（SM卡）、Compact Flash（CF卡）、Multi Media Card（MMC卡）、Secure Digital（SD卡）、Memory Stick（记忆棒）、XD-Picture Card（XD卡）、Microdrive（微硬盘）。U盘是闪存的一种，其最大的特点是小巧便于携带、存储容量大、价格便宜。 读卡器是一个接口转换器，可以将闪存卡插入读卡器的插槽，通过读卡器的端口连接计算机。读卡器多采用USB接口连接计算机。根据卡片类型的不同，可以将其分为接触式和非接触式IC卡读卡器。 按存储卡的种类分为CF卡读卡器、SM卡读卡器、PCMICA卡读卡器以及记忆棒读写器等，还有双槽读卡器可以同时使用两种或两种以上的卡；按端口类型分可分为串行口读卡器、并行口读卡器、USB读卡器。内存卡大量应用于智能手机和照相机中。（2）硬盘存储器硬盘（hard disk）是计算机主要的存储媒介之一，硬盘有机械硬盘（Hard Disk Drive，HDD）、固态硬盘（Solid State Disk，SSD）、固态混合硬盘（Solid State Hybrid Drive，SSHD）。 机械硬盘。机械硬盘是一种磁介质的外部存储设备，数据存储在密封的硬盘驱动器内的多片磁盘片上。这些盘片一般是在以铝或玻璃为主要成分的片基表面涂上磁性介质所形成的。 按照磁盘面的顺序，依次称为0面、1面、2面等，对应于每个面都要有一个读/写磁头，称为0磁头（head）、1磁头、2磁头等。磁盘片的每一面上，以转动轴为轴心、以一定的磁密度为间隔的若干个同心圆，被划分成磁道（track）。为了有效地管理硬盘数据，将每个磁道划分成若干段，每段称为一个扇区（sector），并规定一个扇区存放512 B的数据。所有盘片中相同半径磁道组成的空心圆柱体称为柱面（cylinder）。另外，硬盘还有一个着陆区（landing zone），它是指硬盘不工作时磁头停放的区域，通常指定一个靠近主轴的内层柱面作为着陆区。着陆区不用来存储数据，因此可以避免硬盘受到振动时，以及在开、关电源瞬间磁头紧急脱落所造成的数据丢失。目前，一般的硬盘在电源关闭时会自动将磁头停在着陆区内。硬盘盘面和硬盘结构示意图如图3-10和图3-11所示。 图3-10　硬盘盘面示意图 图3-11　硬盘结构示意图 从整体角度，硬盘接口分为IDE、SATA、SCSI和光纤通道4种。 IDE（Integrated Drive Electronics，电子集成驱动器）：也称之为ATA（Advanced Technology Attachment，高级技术附加装置），它是曾经普遍使用的外部接口，主要接硬盘和光驱。IDE接口采用16位数据并行传送方式，一个IDE接口只能接两个外部设备。由于IDE接口数据传输速度慢、线缆长度过短、连接设备少，现已被淘汰。 SCSI（Small Computer System Interface，小型计算机系统接口）：是一种用于计算机和智能设备之间（硬盘、光驱、打印机、扫描仪等）系统级接口的独立处理器标准，是智能的通用接口标准。SCSI接口主要应用于中、高端服务器和高档工作站中，具有应用范围广、多任务、带宽大、CPU占用率低以及支持热插拔等优点。 SATA（Serial ATA，串行ATA）：是一种计算机总线，主要功能是用作主板和大容量存储设备（如硬盘及光盘驱动器）之间的数据传输。SATA分别有SATA1、SATA2和SATA3三种规格。目前的主流是SATA3，传输速率达到6 Gbit/s 。 光纤通道（fiber channel）：最初是专门为网络系统设计的，随着存储系统对速度的需求增大，才逐渐应用到硬盘系统中。光纤通道硬盘是为提高多硬盘存储系统的速度和灵活性开发的，它的出现大大提高了多硬盘系统的通信速度。光纤通道的主要特性有：热插拔性、高速带宽、远程连接、连接设备数量大等。光纤通道主要用在高端服务器上。衡量硬盘性能的主要技术指标有硬盘容量、平均寻道时间、平均等待时间、平均访问时间、转速、数据传输速率和数据缓存。 硬盘容量：作为计算机系统的数据存储器，容量是硬盘最主要的参数，常见的单位是GB或TB硬盘容量的计算公式为：硬盘的容量=柱面数×磁头数×扇区数× 512 B。平均寻道时间、平均等待时间和平均访问时间：硬盘的平均寻道时间（average seek time）是指硬盘磁头在接收到系统指令后，从初始位置移到目标磁道所需的时间。它在一定程度上体现了硬盘读取数据的能力，是影响硬盘内部数据传输速率的重要参数。目前，硬盘的平均寻道时间通常在10 ms之内。 硬盘的平均等待时间又称潜伏期（latency），是指磁头已处于要访问的磁道，等待所要访问的扇区旋转至磁头下方的时间。平均等待时间为盘片旋转一周所需时间的一半，一般应在4 ms以下。 平均访问时间（average access time）是指磁头从起始位置到达目标磁道位置，并且从目标磁道上找到要读/写的数据扇区所需的时间。平均访问时间体现了硬盘的读/写速度，它包括硬盘的寻道时间和等待时间，即平均访问时间=平均寻道时间+平均等待时间。 转速：硬盘的转速是指硬盘内驱动电动机主轴的转动速度，单位为r/min。转速越大，内部传输速率就越快，访问时间就越短，硬盘的整体性能也就越好。目前，硬盘的主轴转速一般为5400～7200 r/min。 数据传输速率：硬盘的数据传输速率是指硬盘读/写数据的速度，单位为兆字节每秒（MB/s）。硬盘数据传输速率又包括内部数据传输速率和外部数据传输速率。内部传输速率（internal transfer rate）也称为持续传输速率（sustained transfer rate），它是指磁头到硬盘缓存之间的传输速度。内部传输速率主要依赖于硬盘的旋转速度。 外部传输速率（external transfer rate）也称为突发数据传输速率（burst data transfer rate）或接口传输速率，它标称的是系统总线与硬盘缓存之间的数据传输速率。外部数据传输速率与硬盘接口类型及硬盘缓存的大小有关；硬盘的外部数据传输速率远远高于其内部传输速率。 缓存芯片：缓存芯片是指硬盘内部的高速缓冲存储器，用于缓解硬盘数据传输速率和内存传输速率的瓶颈。目前硬盘的高速缓冲存储器一般为64 MB。 固态硬盘：固态硬盘是用固态电子存储芯片阵列制成的存储设备，由控制单元和存储单元组成，如图3-12所示。 图3-12　固态硬盘 固态硬盘的存储介质分为两种：一种是闪存芯片（NAND型），另一种是DRAM。基于闪存的固态硬盘数据保护不受电源限制，可移植性强，适用于各种环境。常见的有笔记本硬盘、微硬盘、存储卡和U盘。通常所说的固态硬盘指基于闪存的固态硬盘。基于DRAM的固态硬盘是一种高性能的存储器，使用寿命长，但是需要独立电源来保证数据安全，应用范围较小。固态硬盘的性能指标主要有标称读/写速度、随机读/写速度（4KB/s）以及平均无故障时间。其中随机读/写速度是测试固态硬盘读/写小文件时的速度。NTFS分区格式里4KB被定义为一个簇。因为系统启动、大型软件载入都会加载许多1 KB左右的配置文件和其他很多小文件，这时随机读/写速度就发挥作用了。衡量单位是IOPS（Input/Output Operations Per Second），即每秒进行读/写（I/O）操作的次数。现在主流的读/写速度都在10 000 IOPS以上，即每秒最高能读或写10 000个4 KB的文件。固态硬盘的接口规范和定义、功能及使用方法与普通硬盘完全相同，在产品外形和尺寸上也与普通硬盘一致，包括3.5"、2.5"、1.8"等多种类型。由于固态硬盘没有普通硬盘的旋转介质，因而抗振性极佳，同时工作温度范围很宽，扩展温度的电子硬盘可工作在-45～+85℃。广泛应用于军事、车载、工控、视频监控、网络监控、网络终端、电力、医疗、航空、导航设备等领域。 固态混合硬盘：固态混合硬盘是把传统磁性硬盘和闪存集成到一起的一种硬盘。闪存部分可以存储用户经常访问的数据，可以达到如固态硬盘效果的读取性能。 目前的混合硬盘不仅能提供更佳的性能，还可减少硬盘的读/写次数，从而使硬盘耗电量降低，特别是使笔记本式计算机的电池续航能力提高，同时混合硬盘亦采用传统磁性硬盘的设计，因此没有固态硬盘容量小的缺点。 （3）光盘存储器光盘存储器（optical disc）是利用光存储技术进行读/写信息的存储设备，主要由光盘、光盘驱动器和光盘控制器组成。光盘存储器最早用于激光唱机和影碟机，后来由于多媒体计算机的迅速发展，光盘存储器便在微型计算机系统中获得广泛应用。普通光盘、光驱的外观和磁光盘表面如图3-13所示。 图3-13　光盘、光驱外观和磁光盘表面 按技术和容量划分，可将光盘分为CD（Compact Disc）、DVD（Digital Video Disc）和Blu-ray Disc（蓝光光盘）。通常CD可提供650～700 MB的存储空间，一张DVD的单面单层盘片容量达4.7 GB，Blu-ray Disc容量可达到25 GB或27GB。按照用途划分，光盘又分为不可擦写光盘和可擦写光盘。不可擦写光盘有CD-ROM和DVD-ROM等，光盘上的数据由生产厂商烧录，用户只可读取光盘上的数据。可擦写光盘有CD-R（CD Recordable）、CD-RW（CD Rewritable）、DVD-RW（DVD Rewritable）等，其中CD-R为可记录式光盘，只能用光盘刻录机一次性将数据写入光盘，用于以后读取。因为是通过激光灼烧方式改变记录层的凹凸来完成数据写入，所以是不可擦除的。重复擦写式光盘CD-RW和DVD-RW通过激光可在光盘上反复多次写入。盘面的记录层材质呈现结晶和非结晶两种状态，这两种状态就可以表示数字1和0。激光束的照射可以使材质在结晶和非结晶两种状态之间相互转换，从而实现信息的写入和擦除。由于状态的转换是可逆的，所以这种光盘可以重复擦写。数据传输速率是光驱的基本参数，它指的是光驱在1 s内所能读出的最大数据量。最早的CD-ROM数据传输速率为150 KB/s，这种速率的光盘驱动器称为1倍速驱动器，即1X=150 KB/s，传输速率为300 KB/s的光驱称为2倍速光驱，记为2X，依次类推。DVD的速度是CD无法比拟的，DVD的1倍速参数比CD大得多，为1.35 MB/s，而且目前所有DVD驱动器都可以读取CD光盘。3.3.5　输入/输出设备1. 输入设备把外部数据传输到计算机中所用的设备称为输入设备。常用的输入设备有键盘、鼠标和扫描仪等。（1）键盘键盘是计算机中最基本、最常用的标准输入设备。键盘主要由按键开关和一个键盘控制器组成，每按下一个键盘按键时，就产生与该键对应的二进制代码，并通过接口送入计算机。键盘按接口可分为PS/2接口、USB接口和无线键盘等。（2）鼠标鼠标是一种应用普遍的输入设备，广泛用于图形用户界面使用环境。其工作原理是当移动鼠标时，把移动距离及方向的信息变成脉冲信号送入计算机，计算机再将脉冲信号转变为光标的坐标数据，从而达到指示位置的目的。鼠标按照工作原理分为机械鼠标、光电鼠标和激光鼠标。机械鼠标又名滚轮鼠标，在底部的凹槽中有一个起定位作用从而使光标移动的滚轮。机械鼠标按照工作原理又可分为第一代的纯机械式和第二代的光电机械式（简称光机式）。机械鼠标的使用受环境限制、精度较低，目前市面上的机械鼠标已经较少。光电鼠标是通过红外线或激光检测鼠标的位移，将位移信号转换为电脉冲信号，再通过程序的处理和转换来控制屏幕上的光标定位和移动。除普通光电鼠标外，还出现了蓝光、针光和无孔式光电鼠标。使用激光做定位照明光源的鼠标称为激光鼠标。使用发光二极管和蓝光技术的鼠标称为蓝影鼠标。常见的鼠标接口类型有串行接口、PS/2接口和USB接口。按照与计算机连接方式的不同，鼠标可分为有线鼠标、无线鼠标，以及支持有线和无线连接的双模式鼠标。无线鼠标没有线缆连接，使用距离长，可以离主机远达7～15 m。缺点是由于使用内置电池，连续使用时间受电池容量限制。目前一般用2.4 GHz无线和2.4GHz蓝牙技术实现与主机的无线通信。无线连接中还有多连方式，指几个具有多连接功能的同品牌产品通过一个接收器进行操作。（3）扫描仪扫描仪是一种光、机、电一体化的设备，以扫描方式将图形或图像信息转换为数字信号。扫描仪作为一种计算机输入设备，具有键盘和鼠标所不具备的功能，从最原始的图片、照片、胶片到各类文稿资料，甚至纺织品、标牌面板、印制板样品等三维对象都可用扫描仪输入到计算机中，进而实现对这些图像形式的信息的处理、管理、使用、存储、输出等。配合光学字符识别（Optic Character Recognize，OCR）技术，扫描仪还能将扫描的文稿转换成计算机的文本形式。扫描仪的主要类型有：滚筒式扫描仪、平面扫描仪、笔式扫描仪、便携式扫描仪、馈纸式扫描仪、胶片扫描仪、底片扫描仪和名片扫描仪。2. 输出设备（1）显示器显示器是计算机系统中最基本的输出设备。目前，显示器的主要种类有CRT显示器、LCD显示器和LED显示器等。CRT显示器是一种使用阴极射线管的显示器，优点是可视角度大、无坏点、色彩还原度高、响应时间短。但是因为其辐射较大、闪烁，且能耗高、体积大，所以除专业领域外，很少采用。LCD显示器是一种采用液晶为材料的显示器。液晶是介于固态和液态间的有机化合物，将其加热会变成透明液态，冷却后会变成结晶的混浊固态。在电场作用下，液晶分子会发生排列上的变化，从而影响所通过的光线的变化，这种光线的变化通过偏光片的作用可以表现为明暗的变化，通过对电场的控制最终控制了光线的明暗变化，从而达到显示图像的目的。其特点是体积小、重量轻、耗能少、工作电压低，目前被广泛采用。LED显示器通过控制半导体发光二极管来显示图像，集微电子技术、计算机技术、信息处理于一体，以其色彩鲜艳、动态范围广、亮度高、清晰度高、工作电压低、功耗小、寿命长、耐冲击、色彩艳丽和工作稳定可靠等优点，成为最具优势的新一代显示媒体之一。LED显示器已广泛应用于大型广场、体育场馆、新闻发布现场、证券交易大厅等场所，可以满足不同环境的需要。显示器的主要技术参数有3种： 屏幕尺寸：屏幕尺寸是指矩形屏幕的对角线长度，以in（英寸）为单位，表示显示屏幕的大小，目前台式机显示器的屏幕尺寸主要以20 in以上为主。 屏幕比例：指显示器横向宽度和纵向高度的尺寸比例。普通屏幕的比例是4:3。为了满足家庭娱乐或其他方面的需求，出现了宽屏显示器，屏幕比例通常是16:9、16:10或21:9。 分辨率：分辨率指屏幕所能显示像素的数目，通常写成（水平点数）×（垂直点数）的形式。同样尺寸的显示器，分辨率越高，画面显示越精细。常用的有1600×1200像素、1024×768像素、1920×1080像素和2560×1080像素等，高分辨率显示器多用于进行图像分析。 另外，衡量显示器性能的指标还有亮度、对比度、响应时间、可视角度、刷新频率等。曲面显示器的基本参数还有屏幕曲率。显示适配器又称显卡，是连接主机和显示器之间的文字和图形传输系统的设备。显卡分为集成显卡、独立显卡及混合式显卡。集成显卡是指主板芯片组集成了显示芯片（一般将显卡、网卡、声卡做成一个很小的芯片集合在了主板里），使用这种芯片组的主板可以不需要独立显卡实现普通的显示功能，以满足一般的家庭娱乐和商业应用。集成的显卡不带有显存，使用系统的一部分内存作为显存，具体的数量一般是系统根据需要自动动态调整的。显然，如果使用集成显卡运行需要大量占用显存的程序，对整个系统的影响会比较明显。此外，其系统内存的频率通常比独立显卡的显存低很多，因此集成显卡的性能比独立显卡差很多。独立显卡分为内置独立显卡和外置独立显卡。通常独立显卡都是内置独立显卡，它需要插在主板的相应接口，譬如PCI-E插槽上。独立显卡具备单独的显存，不占用系统内存，而且独立显卡自带GPU，所以独立显卡能够提供更好的显示效果和运行性能。独立显卡系统功耗大，发热量也较大，通常配有散热器。混合式集成显卡指既有主板上的独立显存又有从内存中划分的显存，可同时使用。显示器和投影仪设备必须通过接口连接到计算机的显卡上才能将计算机的输出信息显示或投影到屏幕上。显卡的接口类型通常有VGA、HDMI、DVI和DP，如图3-14所示。 图3-14 显卡接口示意图 VGA接口也称为D-Sub接口，只接收模拟信号输入，从而降低了显示的分辨率，接口数据传输速率较低，无法达到高清的要求。HDMI（High Definition Multimedia Interface，高清晰度多媒体接口）是一种不压缩、全数字的视频/音频接口，可在同一线缆上传送音频和视频信号，传输质量较高，且具有即插即用的特点。DVI（Digital Visual Interface，数字视频接口）主要分为DVI-D和DVI-I接口，DVI-D和HDMI一样只能接收数字信号，不兼容模拟信号。DVI-I接口可同时兼容模拟和数字信号。兼容模拟信号并不意味着模拟信号的接口D-Sub可以连接在DVI-I接口上，而是必须通过一个转换接头才能使用，一般采用这种接口的显卡都会带有相关的转换接头。DP（Display Port）接口也是一种高清数字显示接口标准，可以连接计算机和显示器，也可以连接计算机和家庭影院。DP是面向液晶显示器开发的接口，具有较高的带宽，能最大限度地整合外围设备，具有高度的可扩展特性。目前的显示器通常提供多种视频接口。（2）打印机传统打印机是将输出结果打印在纸张上的一种输出设备，按打印颜色分为单色打印机和彩色打印机；按工作方式分为击打式打印机和非击打式打印机，击打式打印机包括点阵打印机，也叫针式打印机，非击打式打印机包括喷墨打印机和激光打印机。传统打印机的主要技术指标有以下几种： 打印速度，通常用PPM（Page Per Minute，每分钟打印的纸张数量）表示，另外也可用CPS（Character Per Second，每分钟打印的字符数量）来度量。 打印分辨率，用DPI（Dot Per Inch，每英寸点数）表示，DPI值越高，打印效果越精细，所需的打印时间越长。 最大打印尺寸，一般为A4和A3两种规格。 一般来说，点阵式打印机打印速度慢、噪声大，主要耗材为色带，价格便宜。喷墨打印机噪声小，打印速度次于激光打印机，主要耗材为墨盒。激光打印机打印速度快、噪声小，主要耗材为硒鼓，价格贵但耐用。图3-15所示为常见的针式打印机和激光打印机的外观。 图3-15　打印机 3D打印技术是以数字模型文件为基础，运用特殊蜡材、粉末状金属或塑料等可黏合材料，通过逐层打印的方法来制造三维物体的技术。3D打印的过程是：先通过计算机建模软件构建三维数字模型，再将建成的三维模型“分区”成逐层的截面，即切片，然后打印机根据切片逐层打印。 图3-16 一种3D打印机 图3-16所示为一种3D打印机。图3-17a所示为使用3D打印机打印的工艺品；图3-17b所示为2015年7月美国DM公司使用3D打印技术制造的超级跑车“刀锋（Blade）”。它采取3D打印机打印组件，然后采用人工拼接的方式进行制造。 图3-17　3D打印机打印成品 3D打印无须机械加工或使用模具，就能直接从计算机图形数据中生成任何形状的物体， 从而极大地缩短了产品的生产周期，提高了生产效率。衡量3D打印机性能的主要指标有打印速度、打印成本、打印机细节分辨率、打印精度和打印材料性能等。3.3.6　其他设备1. 声卡声卡的主要功能就是实现音频数字信号和音频模拟信号之间的相互转换。声卡将音频数字信号转换成音频模拟信号的过程称为数模转换，简称D/A转换；将音频模拟信号转换成音频数字信号的过程称为模数转换，简称A/D转换。在声卡进行A/D和D/A转换的过程中，有两个重要的指标：采样频率和采样位数。采样频率是指录音设备在模数转换过程中1 s内对声音模拟信号的采样次数。采样率越高，记录下的声音信号与原始信号之间的差异就越小，声音的还原就越真实。目前，主流声卡的采样频率一般分为22.05 kHz、44.1 kHz和48 kHz 3个等级，分别对应调频（FM）广播级、CD音乐级和工业标准级音质。采样位数就是在模拟声音信号转换为数字声音信号的过程中，对满幅度声音信号规定的量化数值的二进制位数。主流声卡支持的采样精度通常有16位、18位、20位和24位。采样位数越大，量化精度越高，声卡的分辨率也就越高。声卡所支持的声道数也是衡量声卡档次的重要指标之一。常见的有双声道、5.1声道和7.1声道。双声道指左、右两个声道。5.1声道包含左主声道、右主声道、中置声道、左环绕声道、右环绕声道以及低音声道。与5.1声道相比，7.1多了两个环绕声道，其环绕声道为左前环绕、右前环绕、左后环绕和右后环绕。目前声卡的安装方式有外置和内置两种，对应的总线接口分别是USB和PCI-E（或PCI）。其中外置声卡不受电路体积的限制，可以设计更为复杂的模拟电路并采用更好的屏蔽设计，从而大幅度地提升音质。外置声卡的主要问题是USB接口的优先级低于PCI接口，当系统繁忙时USB接口会因争抢不到足够的CPU时间而断续，基于USB共享总线的原因，当外置USB声卡与其他大数据量传输的USB设备（USB硬盘、USB光驱等）同时使用时会出现爆音现象。图3-18所示分别是内置声卡和外置声卡。 图3-18　声卡 2. 网卡网卡的主要作用有两个：一是将计算机的数据封装为帧，并通过网线（对无线网络来说就是电磁波）将数据发送到网络上去；二是接收网络上传过来的帧，并将帧重新组合成数据，发送到所在的计算机中。网卡充当了计算机和网络之间的物理接口。现在使用的网卡基本上都是以太网网卡。衡量网卡性能的主要参数是网卡速率，即指网卡每秒钟接收或发送数据的能力，单位是Mbps（Million bits per second）或Mbit/s，即每秒传输的比特数。目前主流的网卡主要有10/100 Mbit/s和10/100/1000 Mbit/s的自适应以太网卡、1000 Mbit/s和10 000 Mbit/s的以太网卡。网卡接口类型主要有PCI、PCI-X、PCI-E和USB等。3.4　计算机软件系统分类软件是计算机系统的重要组成部分，是各种程序、数据及其文档的总称，它可以扩展计算机的功能、提高计算机的效率。计算机软件系统常见的分类有以下几种。3.4.1　系统软件和应用软件软件是各种程序及其文档的总称，微型计算机系统的软件包括系统软件和应用软件。系统软件的主要作用是协调各个硬件部件，对整个计算机系统资源进行管理、调度、监视和服务。系统软件一般包括操作系统、语言编译程序、数据库管理系统、联网及通信软件和系统诊断等辅助程序，如Windows 10、C语言编译程序、Oracle数据库管理程序、杀毒软件。应用软件是指各个不同领域的计算机用户为某一特定的需要而开发的各种应用程序，例如文字处理软件、表格处理软件、绘图软件、网页设计软件、平面设计软件、财务软件和过程控制软件等。 3.4.2　本地软件和在线软件本地软件是指将软件下载并安装在用户本地的计算机上，软件的全部或大部分功能在用户本地计算机系统上运行。目前，大多数软件都是这种类型。本地软件由软件开发商发布其软件安装程序，使用该软件的每个用户都必须获取软件的安装程序，才能将软件安装在自己的计算机系统上。在线软件是指软件供应商将应用软件统一部署在自己的服务器上，用户通过互联网即可访问部署了应用软件的服务器，使用软件功能，而不必在自己的计算机系统上安装、运行该软件。软件供应商通过Internet以在线软件的方式为用户提供软件服务功能，不仅可以避免盗版软件的出现，还简化了软件的维护工作。用户不必再购买软件，无须对软件进行维护，降低了购买和维护成本。3.4.3　商业软件、免费软件、自由软件和开源软件商业软件是指被作为商品进行交易的计算机软件。用户必须向软件供应商支付费用以购买软件使用许可证，才能使用商业软件。免费软件是指可以自由、免费使用并传播的软件。但是，免费软件的源代码不一定会公开，也不能用于商业用途，并且在传播时必须保证软件的完整性。免费软件往往成为软件供应商推广其商业软件的方法。软件供应商发布其商业软件的免费版本，往往功能受限，或者在其中植入广告，只有用户支付费用后，才能获得软件的完整功能或移除广告。常见的免费软件有QQ、360安全卫士等。自由软件是一种可以不受限制地自由使用、复制、研究、修改和分发的，尊重用户自由的软件。自由软件通常是让软件以“自由软件授权协议”的方式发布（或是放置在公有领域），其发布以源代码为主。自由软件的主要协议有GPL（GUN General Public License，GUN通用公共许可证）和BSD（Berkeley Software Distribution，伯克利软件发行版）。GPL是指软件使用者必须接受软件的授权，才能使用该软件。由于使用者免费取得了自由软件的源代码，如果使用者修改了源代码，基于公平互惠的原则，使用者也必须公开其修改的成果。BSD 开源协议更为宽松，鼓励代码共享，但需要尊重代码作者的著作权。BSD由于允许使用者修改和重新发布代码，也允许使用或在BSD代码上开发商业软件发布和销售，因此是对商业集成很友好的协议。著名的自由软件有Linux操作系统、MySQL数据库管理系统、Firefox浏览器等。开源软件（Open Source Software，OSS）是一种源代码可以任意被获取的计算机软件，这种软件的版权持有人在软件协议的规定之下保留一部分权利并允许用户学习、修改、提高这款软件的质量。开源协议通常符合开放源代码定义的要求。一些开源软件被发布到公有领域。开源软件常被公开和合作地开发，同时也是一种软件散布模式。一般的软件仅可获取已经过编译的二进制可执行文件，通常只有软件的作者或著作权所有者等拥有程序的源代码。有些软件的作者只将源代码公开，却不符合“开放源代码”的定义及条件，因为作者可能设置公开源代码的条件限制，诸如限制可阅读源代码的对象、限制派生产品等，此称为公开源代码的免费软件（Freeware，例如知名的模拟器软件MAME），因此公开源代码的软件并不一定可称为开放源代码软件。开源软件与自由软件是两个不同的概念，只要符合开源软件定义的软件就能被称为开源软件。而自由软件有比开源软件更严格的概念，因此所有自由软件都是开放源代码的，但不是所有的开源软件都能被称为自由软件。但一般来说，绝大多数开源软件也都符合自由软件的定义。开放源代码的规定较宽松，而自由软件的规定较严苛。很多的开放源代码所认可的授权并不被自由软件所认可。3.4.4　软件许可证软件许可证是一种具有法律性质的合同或指导，目的在于规范受著作权保护的软件的使用或散布行为。通常的授权方式会允许用户使用单一或多份该软件的复制品，因为若无授权而使用该软件，将违反著作权法给予该软件开发者的专属保护。从效用上来说，软件授权是软件开发者与其用户之间的一份合约，用来保证在符合授权范围的情况下，用户将不会受到控告。上述的GPL和BSD就是常见的软件的许可证。根据许可证使用时间来分，软件许可证可大致分为终身许可证和年度许可证。 终身许可证：顾名思义，指的是一旦与软件开发商达成协议，签订合同后可终身无限制地使用该软件。此类许可证多见于个人用户领域。 年度许可证：指的是客户与软件开发商签订协议，按年付费来使用该软件。此类软件许可证多见于商业软件领域。 相比终身许可证，年度许可证不太像是购买软件使用，而更像是租赁软件使用，不过却更为灵活。另外，软件使用许可证还可以分为商业软件许可证和自由软件许可证。商业软件许可证会明确许可方的版权归属、法定权利，比较完整地保证软件开发者的权益。针对不同的环境和被许可人（例如，个人用户、商业用户和团体用户）可提供不同的商业软件许可证文本。商业软件许可证中包含了如软件安装、使用培训、运行支持、排错性维护和版本升级等技术服务内容，并明确约定如何收取费用。自由软件许可证一般从知识产权角度进行定义，即约定许可人获得什么程度的使用自由。常见的自由软件许可证有GPL和BSD。3.5　操作系统的功能和分类操作系统（Operating System，OS）的出现是计算机软件发展史上的一个重大转折，为计算机的普及和发展做出了重要贡献。目前，根据不同的硬件配置和不同的应用需要出现了多种计算机操作系统。本节主要介绍操作系统的功能和分类。3.5.1　操作系统的概念操作系统是管理和控制计算机硬件与软件资源的计算机程序，其功能是使计算机系统所有资源最大限度地发挥作用，为用户提供方便、有效、友善的服务界面。操作系统是最基本、最重要的系统软件，任何其他软件都必须在操作系统的支持下才能运行。如果没有操作系统，用户要直接使用计算机，不仅要熟悉计算机硬件系统，而且要了解各种外围设备的物理特性。对普通的计算机用户来说，这几乎是不可能的。操作系统就是为了填补人与机器之间的鸿沟而配置在计算机硬件之上的一种软件。计算机启动后，总是先把操作系统调入内存，然后才能运行其他软件。开机后用户看到的是已经加载了操作系统的计算机。操作系统使计算机用户界面得到了极大改善，用户不必了解硬件的结构和特性就可以利用软件方便地执行各种操作，从而大大提高了工作效率。3.5.2　操作系统的分类随着计算机技术的迅速发展和计算机的广泛应用，用户对操作系统的功能、应用环境、使用方式不断提出了新的要求，因而逐步形成了不同类型的操作系统。根据操作系统的功能和使用环境的不同，操作系统一般可分为实时操作系统、分时操作系统、批处理操作系统、单用户操作系统、网络操作系统、分布式操作系统等。1. 实时操作系统实时操作系统（real-time operating system）是指使计算机能及时响应外部事件的请求，在规定的严格时间内完成对该事件的处理，并控制所有实时设备和实时任务协调一致工作的操作系统。实时操作系统追求的目标是对外部请求在严格时间范围内做出反应，有较高的可靠性和完整性。实时操作系统根据其实时性的刚性需求程度不同，分为软实时和硬实时操作系统。软实时操作系统是从统计的角度，任何一个任务都可以有一个预期的处理时间，但是任务一旦超过截止期限，也不会带来什么致命的漏洞。例如，RTLinux操作操作系统就是一种软实时操作系统。硬实时操作系统是指系统要在最坏（负载最重）的情况下下确保服务时间，即对于事件响应时间的截止期限是必须能满足的。例如，用于好奇号火星探测车的VxWorks系统就是硬实时操作系统。2. 分时操作系统分时操作系统（rime sharing operating system）是指一台主机连接了若干个终端。分时操作系统将CPU的时间划分成若干个片段，称为时间片。操作系统以时间片为单位，轮流为每个终端用户服务。由于计算机高速的运算，每个用户轮流使用时间片而每个用户并不会感到有别的用户存在。分时操作系统侧重于及时性和交互性，使用户的请求尽量能在较短的时间内得到响应。分时操作系统典型的例子就是UNIX和Linux操作系统。3. 批处理操作系统批处理操作系统（batch processing operating system）的工作方式是：用户将作业交给系统操作员，系统操作员将许多用户的作业组成一批作业，然后输入计算机中，在系统中形成一个自动转接的连续的作业流；然后启动操作系统，系统自动、依次执行每个作业；最后由操作员将作业结果交给用户。批处理操作系统的特点是：作业的运行完全由系统自动控制，系统的吞吐量大，资源的利用率高。4. 单用户操作系统单用户操作系统（single user operating system）按同时管理的作业数可分为单用户单任务操作系统和单用户多任务操作系统。单用户单任务操作系统只能同时管理一个作业运行，CPU运行效率低，如DOS。单用户多任务操作系统允许多个程序或多个作业同时存在和运行。现在大多数个人计算机操作系统是单用户多任务操作系统，允许多个程序或多个作业同时存在和运行。5. 网络操作系统网络操作系统（network operating system）是基于计算机网络，在各种计算机操作系统的基础上按网络体系结构协议标准开发的系统软件，包括网络管理、通信、安全、资源共享和各种网络应用，其目标是实现相互通信及资源共享。网络操作系统通常用在计算机网络系统中的服务器上。流行的网络操作系统有Linux、UNIX、BSD、Windows Server、Mac OS X Server、Novell NetWare等。6. 分布式操作系统分布式操作系统（distributed operating system）是由多台计算机通过网络连接在一起而组成的系统，系统中任意两台计算机可以通过远程过程调用交换信息，系统中的计算机无主次之分，系统中的资源被提供给所有用户共享，一个程序可分布在几台计算机上并行地运行，互相协调完成一个共同的任务。分布式操作系统的引入主要是为了增加系统的处理能力、节省投资、提高系统的可靠性。常见的分布式操作系统有MDS、CDCS等。3.5.3　操作系统的引导启动计算机就是把操作系统的核心部分调入内存，这个过程又称为引导系统。在关机状态下，打开电源开关启动计算机称为冷启动；通过按主机上的Reset按钮重启计算机称为复位启动；在电源打开的情况下，通过开始菜单、任务管理器或者快捷键（一般PC中是【Ctrl+Alt+Del】键）重新启动计算机，称为热启动。冷启动和复位启动都要重新上电，检测硬件，电流对硬件有冲击。热启动不重新上电，不检测硬件，直接加载数据。一台装有Windows操作系统的计算机冷启动过程如下：1）计算机加电时，电源给主板及其他设备发出电信号。2）电脉冲使处理器芯片复位，并查找含有BIOS的ROM芯片。3）BIOS执行加电自检，即检测各种系统部件，如总线、系统时钟、扩展卡、RAM芯片、键盘及驱动器等，以确保硬件连接合理及操作正确。自检的同时显示器会显示检测到的系统信息。4）系统自动将自检结果与主板上CMOS芯片中的数据进行比较。CMOS芯片是一种特殊的只读存储器，其中存储了计算机的配置信息，包括内存容量、键盘及显示器的类型、软盘和硬盘的容量及类型，以及当前日期和时间等，自检时还要检测所有连接到计算机的新设备。如果发现了问题，计算机可能会发出长短不一的提示声音，显示器会显示出错信息，如果问题严重，计算机还可能停止操作。5）如果加电自检成功，BIOS就会到外存中去查找一些专门的系统文件（也称为引导程序），一旦找到，这些系统文件就被调入内存并执行。接下来，由这些系统文件把操作系统的核心部分导入内存，然后操作系统就接管、控制了计算机，并把操作系统的其他部分调入计算机。6）操作系统把系统配置信息从注册表调入内存。在Windows中，注册表由几个包含系统配置信息的文件组成。在操作过程中，计算机需要经常访问注册表以存取信息。当上述步骤完成后，显示器屏幕上就会出现Windows的桌面和图标，接着操作系统自动执行“开始”|“所有程序”|“启动”子菜单中的程序。至此，计算机启动完毕，用户可以开始用计算机来完成特定的任务。3.5.4　操作系统的功能操作系统是一个庞大的管理控制程序，它大致包括如下4个管理功能：处理器管理、存储器管理、设备管理、文件管理。1. 处理器管理（1）单道程序和多道程序在计算机处理任务时，任一时刻只允许一个程序在系统中，正在执行的程序控制了整个系统的资源，一个程序执行结束后才能执行下一个程序，这称为单道程序系统。此时计算机的资源利用率低，大量资源在许多时间处于闲置状态。多道程序是指允许多道相互独立的程序在系统中同时运行。从宏观角度看，多道程序处于并行状态；从微观角度看，各道程序轮流占有CPU，交替执行。多道程序系统也称为多任务系统。（2）进程的概念在多任务环境中，处理器的分配、调度都是以进程（process）为基本单位的，因此，对处理器的管理可归结为对进程的管理。进程就是一个程序在一个数据集上的一次执行。进程与程序不同，进程是动态的、暂时的，存在于内存中，进程在运行前被创建，在运行后被撤销。而程序是计算机指令的集合，是静态的、永久的，存储于硬盘、光盘等存储设备。一个程序可以由多个进程加以执行。如果将程序比作乐谱，进程就是根据乐谱演奏出的音乐；如果将程序比作剧本，进程就是一次次的演出。进程具有以下特性： 动态性：动态性是进程最基本的特征。进程具有一定的生命期—进程由创建而产生，由调度而执行，因得不到资源而暂停执行，因撤销而消亡。 并发性：多个进程同时存在于内存中，在一段时间内同时运行。并发性是进程重要的特征之一，引入进程就是为了描述操作系统的并发性，提高计算机系统资源的利用率。 独立性：进程是一个能够独立运行的基本单位，也是CPU进行资源分配和调度的基本独立单位。 异步性：进程按各自独立的、不可预知的速度向前推进，导致程序不可再现性。所以，在操作系统中必须采取某种措施来保证各程序之间能协调运行。 结构特征：由程序段、数据段和进程控制块组成。进程管理主要实现以下4个功能： 进程控制：负责进程的创建、撤销及状态转换。进程的执行是间歇的、不确定的。进程在它的整个生命周期中有3个基本状态—就绪、运行和等待。基本状态的转换如图3-19所示。 图3-19 进程的状态和转换 进程同步：多个进程之间相互合作来完成某一任务，把这种关系称为进程的同步。为保证进程安全、可靠地执行，要对并发执行的进程进行协调。 进程通信：进程之间可以通过互相发送消息进行合作，进程通信通过消息缓冲完成进程间的信息交换。 进程调度：其主要功能是根据一定的算法将CPU分派给就绪队列中的一个进程。由进程调度程序实现CPU在进程间的切换。进程调度的运行频率很高，在分时系统中往往几十毫秒就要运行一次。进程调度是操作系统中最基本的一种调度，其策略的优劣直接影响整个系统的性能。常见的进程调度算法有先来先服务法、最高优先权优先调度法、时间片轮转法等。在Windows 10环境下，打开任务管理器（按【Ctrl+Alt+Del】组合键）后，在“文件”菜单下的“进程”选项卡中，第一部分的“应用”显示当前正在执行的程序，第二部分的“后台进程”显示了计算机中正在运行的一批系统进程，如图3-20所示。选择“进程”选项卡，得到图3-21所示的进程详细列表，在其中可以查看进程的ID号、进程状态、进程占用CPU和内存信息等。 图3-20　应用程序和进程列表 图3-21　进程详细信息 （3）线程由于进程是资源的拥有者，因此在创建、撤销和进程切换过程中，系统必须付出较大的时空开销，从而限制了并发程度的进一步提高。随着硬件和软件技术的发展，为了更好地实现并发处理和共享资源，提高CPU的利用率，目前许多操作系统把进程再细分成线程（thread）。线程又被称为轻量级进程（Light Weight Process，LWP），描述进程内的执行，是操作系统分配CPU时间的基本单位。一个进程可以有多个线程，线程之间共享地址空间和资源。CPU所支持的线程数也是衡量CPU性能的主要指标之一。通常CPU支持的线程数与CPU核心相等，或是CPU核心的两倍。线程具有以下属性： 不拥有资源。 是进程内一个相对独立的、可调度的执行单元。 可并发执行。 共享进程资源。 在Windows中，线程是CPU的分配单位。目前，大部分应用程序都是多线程的结构。2. 存储器管理存储器资源是计算机系统中最重要的资源之一。存储器管理的主要目的是合理、高效地管理和使用存储空间，为程序的运行提供安全可靠的运行环境，使内存的有限空间能满足各种作业的需求。存储器管理应实现下述主要功能： 内存分配：内存分配的主要任务是按一定的策略为每道正在处理的程序和数据分配内存空间。为此，操作系统必须记录整个内存的使用情况，处理用户提出的申请，按照某种策略实施分配，接收系统或用户释放的内存空间。 内存保护：不同用户的程序都放在内存中，因此必须保证它们在各自的内存空间活动，不能相互干扰，不能侵占操作系统的空间。内存保护的一般方法是设置两个界限寄存器，分别存放正在执行的程序在内存中的上界地址值和下界地址值。当程序运行时，要对所产生的访问内存的地址进行合法性检查。也就是说，该地址必须大于或等于下界寄存器的值，并且小于上界寄存器的值，否则属于地址越界，访问将被拒绝，引起程序中断并进行相应处理。 内存扩充：内存扩充指借助虚拟存储技术实现增加内存的效果。由于系统内存容量有限，而用户程序对内存的需求越来越大，这样就出现各用户对内存“求大于供”的局面。如果在物理上扩充内存受到某些限制，就可以采用逻辑上扩充内存的方法，也就是“虚拟存储技术”，即把内存和外存联合起来统一使用。虚拟存储技术的原理是：作业在运行时，没有必要将全部程序和数据同时放进内存，只把当前需要运行的那部分程序和数据放入内存，且当其不再使用时，就被换出到外存。程序中暂时不用的其余部分存放在作为虚拟存储器的硬盘上，运行时由操作系统根据需要把保存在外存上的部分调入内存。虚拟存储技术使外存空间成为内存空间的延伸，增加了运行程序可用的存储容量，使计算机系统似乎有一个比实际内存储器容量大得多的内存空间。 下面以Windows 10为例，说明查看和设置计算机虚拟内存的方法。首先右击桌面上的“这台电脑”图标，在弹出的快捷菜单中选择“属性”命令，在打开的窗口左侧面板中单击“高级系统设置”，在打开的“系统属性”对话框中选择“高级”选项卡，单击“性能”选项组中的“设置”按钮，在打开的“性能选项”对话框中选择“高级”选项卡，在“虚拟内存”选项组中单击“更改”按钮，打开如图3-22所示的“虚拟内存”对话框。用户可以更改虚拟内存的物理盘符和虚拟内存的大小。也可以在虚拟内存设置界面勾选“自动管理所有驱动器的分页文件大小”复选框，即可让操作系统自动分配虚拟内存。虚拟内存不仅仅有扩大RAM的功能，还可以对系统稳定性起到一定帮助。 地址映射：当用户使用高级语言编制程序时，没有必要也无法知道程序将存放在内存中的什么位置，因此，一般用符号来代表地址。当编译程序将源程序编译成目标程序时，将把符号地址转换为逻辑地址（也称为相对地址），而逻辑地址不是真正的内存地址。当程序进入内存时，由操作系统把程序中的逻辑地址转换为真正的内存地址，这就是物理地址。这种把逻辑地址转换为物理地址的过程称为“地址映射”，也称为“重定位”。 图3-22 虚拟内存设置 3. 设备管理计算机系统中大都配置许多外围设备，如显示器、键盘、鼠标、硬盘、CD-ROM、网卡、打印机、扫描仪等。设备管理的主要任务是对计算机系统内的所有设备实施有效的管理，使用户方便、灵活地使用设备。设备管理应实现下述功能： 设备分配：有时多道作业对设备的需求量会超过系统的实际设备拥有量。因此，进行设备管理时需要根据用户的I/O请求和一定的设备分配原则为用户分配外围设备。设备管理不仅要提高外设的利用率，而且要有利于提高整个计算机系统的工作效率。 设备传输控制：实现物理的输入/输出操作，即启动设备、中断处理、结束处理等。 设备独立性：又称设备无关性，即用户编写的程序与实际使用的物理设备无关，由操作系统把用户程序中使用的逻辑设备映射到物理设备。 缓冲区管理：缓冲区管理的目的是解决CPU与I/O设备之间速度不匹配的矛盾。在计算机系统中，CPU的速度最快，而外围设备的处理速度相对较慢，因此降低了CPU的使用效率。使用缓冲区可以提高外设与CPU之间的并行性，从而提高整个系统的性能。 设备驱动：实现CPU与通道和外设之间的通信。操作系统依据设备驱动程序来实现CPU与其他设备的通信。设备驱动程序直接与硬件设备打交道，告诉系统如何与设备进行通信，完成具体的输入/输出任务。对操作系统中并未配备其驱动程序的硬件设备，必须手动安装由硬件厂家随同硬件设备一起提供的或从网络中查找下载的设备驱动程序。 4. 文件管理（1）文件系统文件是按一定格式建立在存储设备上的一批信息的有序集合。在计算机系统中，所有的程序和数据都是以文件的形式存放在计算机的外存储器上。例如，一个C语言源程序、一个Word文档、各种可执行程序等都是文件。文件名是指文件的主名和扩展名，但在很多情况下要指明文件在磁盘中的位置，必须采用完整的文件名，即文件所在的盘符、路径及文件名。例如：C:Program Files (x86)Microsoft OfficerootOffice16指明了文字处理软件Word在硬盘上的存放位置。文件系统是对文件存储设备的空间进行组织和分配，负责文件存储并对存入的文件进行保护和检索的系统。在文件系统的管理下，用户可以按照文件名访问文件，而不必考虑各种外存储器的差异，不必了解文件在外存储器上的具体物理位置等存放细节。文件系统为用户提供了一个简单、统一的访问文件的方法。Windows操作系统使用的文件系统有FAT32、NTFS、ExFAT。 FAT（File Allocation Table，文件分配表）分区文件系统：如FAT16、FAT32，无法存放大于4 GB的单个文件，而且容易产生磁盘碎片，目前应用较少。 NTFS（New Technology File System，新技术文件系统）：是一种日志式的文件系统，即将各种文件操作信息写入存储设备，所以在发生文件损坏和故障时可以通过日志很容易地恢复到之前的情形，这使得NTFS在操作系统的运行方面有着FAT32不可比拟的优势。最大单个文件可到2 TB，能够提供FAT文件系统所不具备的性能、安全性、可靠性与先进特性。 ExFAT（Extended File Allocation Table File System，扩展FAT）：是为了解决FAT32不支持4 GB及更大的文件而推出的一种适合于闪存的文件系统。 （2）文件管理的功能文件管理负责管理系统的软件资源，并为用户提供对文件的存取、共享和保护等手段。文件管理应实现下述功能： 树形目录管理：将目录和文件按树形的层次结构进行组织并管理。目录管理包括目录文件的组织、目录的快速查询等。 文件存储空间的管理：文件是存储在外存储器上的，为了有效地利用外存储器上的存储空间，文件系统要合理地分配和管理存储空间。它必须标记哪些存储空间已经被占用，哪些存储空间是空闲的。文件只能保存在空闲的存储空间中，否则会破坏已保存的信息。 文件操作的一般管理：实现文件的操作，负责完成数据的读/写，一般管理包括文件的创建、删除、打开、关闭等。 文件的共享和保护。在多道程序设计的系统中，有些文件是可供多个用户公用的，是可共享的。但这种共享不应该是无条件的，而应该受到控制，以保证共享文件的安全性。文件系统应该具有安全机制，即提供一套存取控制机制，以防止未授权用户对文件的存取以及防止授权用户越权对文件进行操作。 习题一、简答题 微型计算机由哪几部分组成？各部分的功能是什么？ 简述计算机的基本工作原理。 什么是指令？什么是程序？ 北桥芯片和南桥芯片各有什么作用？ 内存储器和外存储器的用途是什么，二者有什么区别？ RAM和ROM的区别是什么？ 机械硬盘与固态硬盘的区别是什么？ 什么是总线？简要说明AB、DB、CB的含义及其功能。 显示器的主要参数是什么？ 简述3D打印机的工作原理。 什么是操作系统？它有哪些功能？ 进程的基本特性是什么？简述进程3种状态的转换。 存储器管理的主要功能是什么？ 设备管理的主要任务是什么？ 文件管理的主要任务是什么？ 二、填空题 冯·诺依曼计算机由5个基本部分组成，即　　　　、 　　　　、　　　　、输入设备和输出设备。 通常所说的CPU芯片包括　　　　。 计算机执行指令一般分为　　　　　和　　　　两个阶段。 计算机的运算速度主要取决于　　　　　。 目前，微型计算机主板的主流结构为　　　　结构。 主板的芯片组通常由　　　　和　　　　组成。 目前的CPU制造工艺为　　　　级别（填入长度单位）。 存储器分为　　　　和　　　　两种。 内存是一个广义的概念，它包括　　　　和　　　　。 DDR的数据传输速率为传统SDRAM的　　　　倍。 存储BIOS的芯片类型是　　　　。 配置高速缓冲存储器是为了解决　　　　。 微机工作时如果突然断电将会使　　　　中的数据丢失。 主板上的SATA接口表示的是　　　　接口。 计算机的外设很多，主要分成两大类：一类是输入设备；另一类是输出设备。其中，显示器、音箱属于　　　　设备，键盘、鼠标、扫描仪属于　　　　设备。 计算机指令由操作码和　　　　构成。 声卡的主要功能就是实现音频数字信号和音频　　　　之间的相互转换。 与独立显卡相比，　　　　运行需要大量占用显存的程序，对整个系统的影响会比较明显。 自由软件是一种可以不受限制地自由使用、复制、研究、修改和分发的，尊重用户自由的软件。自由软件的主要协议是　　　　。 进程最基本的特征是　　　　。