数据结构

计算机

机械计算机

机械计算机（英语：mechanical computer）由杠杆、齿轮等机械部件而非电子部件构成。最常见的例子是加法器和机械计数器，它们使用齿轮的转动来增加显示的输出。更复杂的例子可以进行乘法和除法。

1822 年, 英国人巴贝奇 Charles Babbage设计了差分机和分析机，其设计理论非常超前，类似于百年后的电子计算机，特别是利用卡片输入程序和数据的设计被后人所采用。

1834 年, Babbage 设想制造一台通用分析机，在只读存储器(穿孔卡片)中存储程序和数据。Babbage在以后的时间里继续他的研究工作，并于1840 年将操作位数提高到了40 位，并基本实现了控制中心(CPU)和存储程序的设想，而且程序可以根据条件进行跳转，能在几秒内做出一般的加法，几分钟内做出乘、除法。

图灵机

图灵是现代计算机设计思想的创始人, 1936年, 图灵向伦敦权威的数学杂志投了一篇论文，题为《论数字计算在决断难题中的应用》。在这篇开创性的论文中，图灵给“可计算性”下了一个严格的数学定义，并提出著名的“图灵机”(Turing Machine)的设想。“图灵机”不是一种具体的机器，而是一种思想模型, 这一理论奠定了整个现代计算机的理论基础。

冯诺依曼结构

1945年，以冯·诺依曼为核心的ENIAC机研制组发表了一个全新的”存储程序通用电子计算机方案”–EDVAC（Electronic Discrete Variable AutomaticComputer的缩写）．EDVAC方案明确奠定了新机器由五个部分组成，包括：运算器、逻辑控制装置、存储器、输入和输出设备，并描述了这五部分的职能和相互关系．EDVAC机还有两个非常重大的改进，即：

采用了二进制，不但数据采用二进制，指令也采用二进制.
建立了存储程序，指令和数据便可一起放在存储器里，并作同样处理．简化了计算机的结构，大大提高了计算机的速度。

EDVAC使用了大约6000个真空管和12000个二极管，占地45.5平方米，重达7850千克，消耗电力56千瓦

冯诺依曼结构:

电子计算机经历了电子管－晶体管－集成电路－超大规模集成电路的阶段，运行速度越来越快，而体积和成本也越来越低.

个人计算机

超级计算机

中国超算神威-太湖之光。

神威太湖之光超级计算机安装了40960个中国自主研发的“申威26010”众核处理器，该众核处理器采用64位自主申威指令系统，峰值性能为12.54京次/秒，持续性能为9.3京次/秒。（1京为1亿亿）

程序的发展

第一个写软件的人是Ada（Augusta Ada Lovelace）, 在1860年代她尝试为 Babbage（Charles Babbage）的机械式计算机写软件。

20世纪50年代，软件伴随着第一台电子计算机的问世诞生了。以写软件为职业的人也开始出现，他们多是经过训练的数学家和电子工程师。1960年代美国大学里开始出现授予计算机专业的学位，教人们写软件。

计算机语言最早由二进制０与１所组成，计算机通过读取穿孔卡片从而获得相应的指令序列，与人类所使用的语言相差甚远。

汇编语言在二进制码的基础上，加入了一定的助记符帮助程序员记忆操作码，但仍然十分繁琐。

而高级语言诸如Ｆｏｒｔｒａｎ，Ｃ，Ｃ＋＋，ＪＡＶＡ等，伴随着个人电脑的普及，使编程语言的可读性大大提高。计算机语言的不断发展，其根本推动力是抽象机制更高的要求，以及对程序设计思想更好的支持，也可以说使能够理解的语言提升到能够很好模拟人类思考问题的形式.

程序编译的过程

从源码到可执行程序的步骤：预编译、编译、链接、strip

预编译：预编译器执行。譬如C中的宏定义就是由预编译器处理，注释等也是由预编译器处理的。
编译：编译器来执行。把源码.c .S编程机器码.o文件。
链接：链接器来执行。把.o文件中的各函数（段）按照一定规则（链接脚本来指定）累积在一起，形成可执行文件。
strip：strip是把可执行程序中的符号信息给拿掉，以节省空间。（Debug版本和Release版本）

程序段的概念：代码段、数据段、bss段（ZI段）、自定义段

段就是程序的一部分，我们把整个程序的所有东西分成了一个一个的段，给每个段起个名字，然后在链接时就可以用这个名字来指示这些段。也就是说给段命名就是为了在链接脚本中用段名来让段站在核实的位置。

段名分为2种：一种是编译器链接器内部定好的，先天性的名字；一种是程序员自己指定的、自定义的段名。

先天性段名：

代码段：（.text），又叫文本段，代码段其实就是函数编译后生成的可执行代码
数据段：（.data），数据段就是C语言中有显式初始化为非0的全局变量
bss段：（.bss），又叫ZI（zero initial）段，未初始化全局变量，未初始化全局静态变量. 对应C语言中初始化为0的全局变量。
栈段（stack）：由编译器自动分配释放，存放函数的参数值、局部变量的值等。其操作方式类似于数据结构中的栈。
堆段（heap）：由程序员分配释放，若程序员不释放，程序结束时可能由操作系统回收。注意它与数据结构中的堆是两回事，分配方式倒是类似于链表。

测试程序:

#include <iostream>
using namespace std;

const int StackSize = 1.6*1024*1024;
int a[10];
int b;

int main(int argc, char *argv[])
{
  char tmp[StackSize] = {0};
  tmp[StackSize-1] = 'a';
  printf("%c\n",tmp[StackSize-1]);

  printf("%llx\n", tmp);

  printf("%llx\n", a);

  printf("%llx\n", &b);

  return 0;
}

程序

程序 = 算法 + 数据结构

计算机