程序 = 数据结构 + 算法《禅与计算机程序设计艺术》 / 陈光剑

程序 = 数据结构 + 算法

“数据结构和算法是过去 50 年来最重要的发明之一，它们是软件工程师需要了解的基础工具。” 《Think Data Structures: Algorithms and Information Retrieval in Java》(Allen B.Downey)

基本数据类型

道生一，一生二，二生三，三生万物。

在计算机程序设计的世界里，先有基本数据类型，复合组装成复杂对象类型，不同对象之间再进行交互操作，进而形成丰富多彩的虚拟世界。

其实，这个过程中的原理，跟现实世界是一样的。我们人类的脑子里对这个世界的认知，恐怕没有人敢说他真正懂得这个世界本来的样子。仅仅是量子物理的世界跟广义相对论的时空世界，就把这个地球上绝大部分人的脑袋弄迷糊。

我们的数字计算机的世界，是简化了的物理世界——在这个世界里，任何事物的存在，都可以用0和1来表达——清楚简单、准确无误。任何数据结构模型，都是清晰可见的。

我们这里讲的数据结构，对应的是抽象数据类型、类、模型、实体等这些的概念，是数据的逻辑模型，不是数据的物理模型。

如果不了解计算机相关的知识和思想，可能很难明白计算机的工作原理。因为，经历从各层硬件到各层软件的层层抽象后，计算机内部已经复杂得让人难以想象。

比如芯片，指甲盖儿那么大，却有几亿甚至几十亿个晶体管电子器件，每个晶体管电子器件的电流和电压，在1秒内，能变化几亿甚至几十亿次。学过排列组合的朋友，应该知道，芯片内部每时每刻的状态数量，是一个天文数字。

再比如操作系统。大概有10G的源代码，一Byte一个字符，也就是说有超过100亿个字符，每行按标准80字符来算的话，超过1亿行。WinXP系统有2亿行。Android系统为例，少说点也有1亿行代码。假设一本书有500页 (正反算两页，这已经是一本很厚的书了)，书的单面印50行代码，那么一本书就能印刷25000行代码。如果把操作系统的代码都印刷在书上，那就是4000本书。

当我们拿着手机，聊微信、逛淘宝、刷抖音时，我们是否意识到发生了什么呢？

通过手机app、中间件、操作系统、驱动程序，我们在操纵着手机芯片中的电压和电流，操纵着芯片中的无数分子中的原子中的电子。

我们还利用了麦克斯韦电磁场理论，通过电磁场和电磁波的方式，远程操纵着马化腾的服务器、马云的服务器、张一鸣的服务器的芯片中的无数分子中的原子中的电子。我们用的电，来自几千公里之外的发电厂，通过一百年前特斯拉发明的交流电系统传输到我们房子里面的电路插座……真有点武侠小说的感觉，手指在手机上轻轻一滑，世界各地的计算机芯片中的电子为之一振。

是的，从微观层面讲，那些电子在杂乱无章地“乱窜”，充满着不确定性。但是，通过抽象，我们拥有了宏观层面确定的欧姆定律、基尔霍夫定律。然而，电流电压依然会存在上下轻微波动，并不准确，于是通过再次抽象，我们拥有了确定的与或非门电路；通过再次抽象，我们拥有了确定的芯片；通过再次抽象，我们拥有了确定的驱动程序、操作系统、中间件；最后，我们拥有了确定的、带功能意义的应用程序/app, 于是乎，我们滑动着手机，玩着，乐着。

计算机，从顶层的应用程序往下看，处处都有抽象，处处都是编码和转换。我们没有办法，也没有必要弄清计算机的每个细节，但只要把握住了计算机的工作原理，弄清一些核心概念，还是能在一定抽象度上搞懂计算机。

抽象，是计算机科学和技术中最重要的思想，没有之一。抽象的重要性，在操作系统中的体现尤为明显。

通过层层抽象，我们才可以轻松地聊微信、逛淘宝、刷抖音，而最背后的最底层，不过是芯片中的电子在“乱窜”而已。

万物皆数：Number

毕达哥拉斯：数是宇宙万物的本原

毕达哥拉斯（Pythagoras，约公元前580年~约前500（490）年）古希腊数学家、哲学家。

毕达哥拉斯出生在爱琴海中的萨摩斯岛（今希腊东部小岛）的贵族家庭，自幼聪明好学，曾在名师门下学习几何学、自然科学和哲学。因为向往东方的智慧，毕达哥拉斯经过万水千山，游历了当时世界上两个文化水准极高的文明古国——巴比伦和印度，以及埃及（有争议），吸收了美索不达米亚文明和印度文明的文化。后来他到意大利的南部传授数学及宣传他的哲学思想，并和他的信徒们组成了一个所谓“毕达哥拉斯学派”的政治和宗教团体。

毕达哥拉斯学派认为数是宇宙万物的本原。研究数学的目的并不在于使用而是为了探索自然的奥秘。

事物的性质是由某种数量关系决定的，万物按照一定的数量比例而构成和谐的秩序。从三个苹果等事物中抽象出了五这个数。

这在今天看来很平常的事，但在当时的哲学和实用数学界，这算是一个巨大的进步。在实用数学方面，它使得算术成为可能。在哲学方面，这个发现促使人们相信数是构成实物世界的基础。

数制

1．十进制数（Decimal）

十进制数是人们十分熟悉的计数体制，它的数码是用0、1、2、3、4、5、6、7、8、9十个数字符号来表示，基数是10，进位规律是“逢十进一”。

为什么现代人普遍使用十进制？
在人类发展史上，并不是所有人都选择了十进制。古巴比伦人用的是60进制，玛雅人用的是20进制。罗马人的计数系统干脆就没有进制。古埃及也有类似的情况。所以并不存在什么十进制的必然性。
回头去看历史的话，十进制的计数系统在现代占据统治地位很大程度上是历史的偶然。现代的这套“阿拉伯数字”的计数系统其实是古印度人的发明。来自中亚的伊斯兰化的突厥人征服了印度，把印度纳入到了伊斯兰世界。然后阿拉伯人又在长期的征服与贸易的过程中把这套计数系统传播到了世界各地。如果当初占据亚欧交通枢纽的不是阿拉伯人，或者当时巴布尔没有打下印度，那完全有可能我们今天用的计数方式不是十进制，而是十二进制，二十进制或是六十进制之类的。至于说十进制的来源是十根手指头，这只能说是一种可能的猜测。

2．二进制数（Binary）

与十进制数类似，二进制数的数码是用0、1两个数字符号来表示，基数为2，进位规律是“逢二进一”。

数字电子电路中，逻辑门的实现直接应用了二进制。现代的计算机和依赖计算机的设备里都用到二进制。每个数字称为一个比特（Bit，Binary digit）。

3．八进制数（Octonary）

在八进制数中，它的数码是用0、1、2、3、4、5、6、7八个数字符号来表示，基数是8，进位规律是“逢八进一”。

4．十六进制数（Hexadecimal）

在十六进制数中，它的数码是用0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F十六个数字和字母符号来表示，基数是16，进位规律是逢十六进一。

二进制数、八进制数、十六进制数和十进制数之间的对应关系：

关于有理数、无理数、实数、复数等概念，比如说无限不循环小数，计算机无能为力，没有办法准确表达，只能尽量逼近，近似数值计算。这也是计算机程序设计与纯粹数学理论之间的鸿沟。这就好比是，量子力学的理论多么优美，广义相对论的思想多么宏大，但是，人类就是没办法把两种理论统一放到同一个宇宙体系中。这难道是理想与现实的永恒的裂缝？

计算机世界为什么选择了二进制？

早期的机械式和继电式计算机都用具有10个稳定状态的基本元件来表示十进制数据位0,1,2,…,9。一个数据的各个数据位是按10的指数顺序排列的。例如，从0v到9v, 总共有10个电压位，由于电子线路器件的原因及其内部复杂性，如果一根电线的电压值是7.49v, 那么，请问，它表示的是数字7还是数字8呢？这就尴尬了。

但是,要求处理机的基本电子元件具有10个稳定状态比较困难，十进制运算器逻辑线路也比较复杂。从莱布尼茨到布尔，再到香农，都在苦苦探索着。最后探索出了解决之道：可以使用二进制来计算，然后用电路来实现二进制计算。

用电路来实现二进制表示和二进制计算，我们今天看起来似乎很简单，但探索出这条路，并不容易。莱布尼茨发明了二进制，但他在做自己的乘法器时，并没有意识到二进制的重要性。莱布尼茨终生未婚，在科学和哲学史上，他真可谓是百科全书式的人物。

多数元件具有两个稳定状态，二进制运算也比较简单,而且能节省设备，二进制与处理机逻辑运算能协调一致，且便于用逻辑代数简化处理机逻辑设计。二进制遂得到广泛应用。

逻辑代数

布尔创建了逻辑代数，也称布尔代数，在很大程度上，为后来的电路设计及其简化，做出了很大的贡献。现在很多编程语言中都内部了布尔类型，以纪念这位先驱。

布尔代数起源于数学领域，是一个用于集合运算和逻辑运算的公式：〈B，∨，∧，¬ 〉。其中B为一个非空集合，∨，∧为定义在B上的两个二元运算，¬为定义在B上的一个一元运算。
通过布尔代数进行集合运算可以获取到不同集合之间的交集、并集或补集，进行逻辑运算可以对不同集合进行与、或、非。

20世纪以来，逻辑代数一直是数字电路设计的基础，并且所有现代编程语言提供支持。几乎所有现代通用计算机都用二值布尔逻辑做运算；也就是说它们的电路是二值布尔逻辑的物理表示。几种表示方式：导线上电压的高低，磁性存储设备中磁畴的方向，打孔卡或纸带上的洞，等等。

用电路来实现二进制

香农，正是香农，最先洞察到了开关系统和布尔逻辑之间的关系，并发表了论文《继电器和开关电路的符号化分析》，可以说，这篇文论让人们意识到，可以用电路来实现二进制表示和二进制计算。香农活到了二十一世纪，当他看着这个世界，因为他的贡献而变得如此美好时，内心一定是很欣慰的。

1938年香农在MIT获得电气工程硕士学位，硕士论文题目是《A Symbolic Analysis of Relay and Switching Circuits》（继电器与开关电路的符号分析）。当时他已经注意到电话交换电路与布尔代数之间的类似性，即把布尔代数的“真”与“假”和电路系统的“开”与“关”对应起来，并用1和0表示。于是他用布尔代数分析并优化开关电路，这就奠定了数字电路的理论基础。哈佛大学的Howard Gardner教授说，“这可能是本世纪最重要、最著名的一篇硕士论文。”

逻辑门

逻辑门是在集成电路上的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”或二进制当中的1和0，从而实现逻辑运算。通常组合使用实现更为复杂的逻辑运算。一些厂商通过逻辑门的组合生产一些实用、小型、集成的产品，例如可编程逻辑器件FPGA等。

二进制与字符表达

字符信息的表示

1．字符编码

目前主要用ASCII码（American Standard Code for Information Interchange），即美国标准信息交换码，已被国际标准化组织ISO（International Organization for Standardization）定为国际标准。ASCII码采用一个字节（8个二进制位）表示一个字符，ASCII码分为标准ASCII码和扩展ASCII码。

标准ASCII码的最高位为0，其范围用二进制表示为00000000 ～ 01111111，用十六进制表示为00 ～ 7F，用十进制表示为0 ～ 127，共128个编码。在128个编码中，有34个控制字符，52个英文大小写字母，10个数字（0～9），32个字符和运算符（见书本P19 表1-5标准ASCII码表）。

2．汉字编码

为了能在计算机中处理汉字，就必须对汉字进行编码，但汉字都有自己的形状，其基本字符较多，用一个字节编码显然是不够的。目前的汉字编码方案大多都采用两个字节，例如我国制定的“中华人民共和国国家标准信息交换汉字编码”（GB2312-80），简称国标码。在GB2312-80中规定用两个字节即16位二进制代码表示一个汉字，并且每个字节的高位规定为1，这样只可以表示128 × 128=16384个汉字。

汉字输入码，又称“外部码”，简称“外码”，指用户从键盘上输入代表汉字的编码。为了能直接使用西文标准键盘进行汉字输入，必须为汉字设计相应的编码方法。

区位码是一种最通用的汉字输入码。它是根据国标GB2312-80将6763个汉字和一些常用的图形符号组成一个94×94的矩阵，即有94行和94列。每一行称为一个区，每一列称为一个位，区号与位号组合在一起称为区位码（区位号），它可准确确定某一汉字或图形符号。如汉字“啊”位于16区第01位，则“啊”字的区位码为：区号+位号，即1601。

国家标准GB2312-80中的汉字代码除了十进制形式的区位码外，还有一种十六进制形式的编码，称为国标码。国标码是不同汉字信息系统之间进行汉字交换时所使用的编码，它的编码值不同于区位码，其值是分别对区号、位号增加32（十六进制数20H）。

汉字机内码也称“机内码”，简称“内码”，指计算机内部存储、处理加工和传输汉字时所用的由0和1符号组成的代码。机内码可以通过区位码计算出来，其值是分别对区号、位号增加160（十六进制数A0H）。

3.汉字字库

对于每一个汉字，在计算机内都有对应的字形码和汉字模型（也称字模），所有字模的集合构成了字“模库”，简称“字库”。汉字在输出时，要先找到用于输出的字形码或字模，再将字模输出形成汉字。

汉字字形的构成方法有向量法（也称矢量法、轮廓字形）、点阵法。

4．汉字处理流程

汉字通过输入设备将外码送入计算机，再由汉字处理系统将其转换成内码进行存储、处理、加工和传送，当需要输出时再由汉字处理系统调用字库中汉字的字形码得到输出汉字的结果

编码与映射的思想

数组与链表：Array 与 List

映射表：HashMap

树与网络结构

无穷大是什么？

0 代表的概念

在物理世界无穷存在吗？

计算机二进制简史

1911年：6月15日，华尔街金融投资家弗林特（C.Flent）投资霍列瑞斯的制表机公司，成立了全新的CTR公司，但公司创立之初并没有涉足任何电子领域，反而生产诸如碎纸机或者土豆削皮机之类的产品。

1912年：美国青年发明家德•福雷斯特（L.De Forest）在帕洛阿托小镇首次发现了电子管的放大作用，为电子工业奠定了基础，而今日的帕洛阿托小镇也已成为硅谷的中心地带。

1913年：麻省理工学院教授万•布什（V.Bush）领导制造了模拟计算机“微分分析仪”。机器采用一系列电机驱动，利用齿轮转动的角度来模拟计算结果。

1924年：硅谷之父特曼担任斯坦福大学教授，对创建HP、成立斯坦福工业园区起到决定性作用

2月，由霍列瑞斯创办的制表机公司几经演变，最终更名为国际商用机器公司，即我们今天看到的IBM。

1935年：IBM制造了IBM601穿孔卡片式计算机，该计算机能够在一秒钟内计算出乘法运算。

1936年：阿兰.图灵发表论文《论可计算数及其在判定问题中的应用》，首次阐明了现代电脑原理，从理论上证明了现代通用计算机存在的可能性，图灵把人在计算时所做的工作分解成简单的动作，与人的计算类似，机器需要：（1）存储器，用于贮存计算结果；（2）一种语言，表示运算和数字；(3)扫描；（4）计算意向，即在计算过程中下一步打算做什么；（5）执行下一步计算。具体到一步计算，则分成：（1）改变数字可符号；（2）扫描区改变，如往左进位和往右添位等；（3）改变计算意向等。整个计算过程采用了二进位制，这就是后来人们所称的“图灵机”。

20多岁的德国工程师楚泽（K.Zuse）研制出了机械可编程计算机Z1，并采用了二进制形式，其理论基础即来源于布尔代数

1937年：11月，美国AT&T贝尔实验室研究人员斯蒂比兹（G. Stibitz）制造了电磁式数字计算机“Model-K”。

1938年：克劳德•艾尔伍德•香农（Claude Elwood Shannon）发表了著名论文《继电器和开关电路的符号分析》，首次用布尔代数对开关电路进行了相关的分析，并证明了可以通过继电器电路来实现布尔代数的逻辑运算，同时明确地给出了实现加，减，乘，除等运算的电子电路的设计方法。这篇论文成为开关电路理论的开端。

1939年：元旦，美国斯坦福大学研究生比尔•休利特（B.Hewllet）和戴维•帕卡德（D.Packard）正式签署企业合伙协议，创办了Hewllet-Packard（HP)公司，即国内通称的惠普公司。

9月，贝尔实验室研制出M－1型计算机。

10月，约翰.阿塔纳索夫（John Vincent Atanasoff(1903-1995)）制造了后来举世闻名的ABC计算机的第一台样机，并提出了计算机的三条原则，（1）以二进制的逻辑基础来实现数字运算，以保证精度；（2）利用电子技术来实现控制，逻辑运算和算术运算，以保证计算速度；（3）采用把计算功能和二进制数更新存贮的功能相分离的结构。这就是著名的计算机三原则。

1940年：9月，贝尔实验室在美国达特默思大学演示M—1型机。他们用电报线把安置在校园内的M—1型机和相连，当场把一个数学问题打印出来并传输到纽约，M—1型机在达特默思大学的成功表演，首次实现了人类对计算机进行的远距离控制的梦想。

控制论之父维纳提出了计算机五原则，（1）不是模拟式，而是数字式；（2）由电子元件构成，尽量减少机械部件；（3）采用二进制，而不是十进制；（4）内部存放计算表；（5）在计算机内部存贮数据。

1941年：楚泽完成了Z3计算机的研制工作，这是第一台可编程的电子计算机。可处理7位指数、14位小数。使用了大量的真空管。每秒种能作3到4次加法运算，一次乘法需要3到5秒。

1942年：时任美国依阿华州立大学数学物理教授的阿塔纳索夫（John V. Atanasoff）与研究生贝瑞（Clifford Berry）组装了著名的ABC（Atanasoff-Berry Computer）计算机，共使用了300多个电子管，这也是世界上第一台具有现代计算机雏形的计算机。但是由于美国政府正式参加第二次世界大战，致使该计算机并没有真正投入运行。

1943年：贝尔实验室把U型继电器装入计算机设备中，制成了M—2型机，这是最早的编程计算机之一。此后的两年中，贝尔实验室相继研制成功了M－3和M－4型计算机，但都与M－2型类似，只是存储器容量更大了一些。

10月，绰号为“巨人”的用来破译德军密码的计算机在英国布雷契莱庄园制造成功，此后又制造多台，为第二次世界大战的胜利立下了汗马功劳。

1944年：8月7日，由IBM出资，美国人霍德华•艾肯（H.Aiken）负责研制的马克1号计算机在哈佛大学正式运行，它装备了15万个元件和长达800公里的电线，每分钟能够进行200次以上运算。女数学家格雷斯•霍波（G.Hopper）为它编制了计算程序，并声明该计算机可以进行微分方程的求解。马克1号计算机的问世不但实现了巴贝奇的夙愿，而且也代表着自帕斯卡计算机问世以来机械计算机和电动计算机的最高水平。

1946年：2月14日，美国宾夕法尼亚大学摩尔学院教授莫契利（J. Mauchiy）和埃克特（J.Eckert）共同研制成功了ENIAC (Electronic Numerical Integrator And Computer):计算机。这台计算机总共安装了17468只电子管，7200个二极管，70000多电阻器，10000多只电容器和6000只继电器，电路的焊接点多达50万个,机器被安装在一排2.75米高的金属柜里，占地面积为170平方米左右，总重量达到30吨，其运算速度达到每秒钟5000次加法，可以在3/1000秒时间内做完两个10位数乘法。

参考资料

https://www.zhihu.com/question/282808055/answer/973929755
https://baike.baidu.com/item/%E4%BA%8C%E8%BF%9B%E5%88%B6/361457
https://blog.csdn.net/stpeace/article/details/103317663
https://blog.csdn.net/h_kingone/article/details/108749215

物理学史
计算机历史
半导体物理学
半导体器件物理

《禅与计算机程序设计艺术》 / 陈光剑目录

第一性原理

什么是禅？

什么是计算机？

什么是程序设计？

什么是艺术？

宇宙之起源

物质之形成

半导体材料

纳米光刻

二极管、三极管

太极阴阳与二进制

布尔代数与数字逻辑系统

模拟电子电路系统

信号与处理

信息论

图灵机模型

冯诺依曼模型

计算机演化史

什么是编程？

编程语言进化史