Data Structures & Algorithm, Department of Computer Science and Technology, TsingHua University Deng JunHui
前言
本文档节选自清华大学邓俊辉老师编著的《数据结构（C++语言版）》教材。需特别说明的是，邓俊辉老师为教材的唯一版权所有者。此文档仅为鄙人在学习过程中整理的重点知识摘要，不涉及任何版权主张。
第1章 绪论
§1.1 计算机与算法
计算机科学的核心在于研究计算方法与过程的规律，而不仅仅是作为计算工具的计算机本身，因此E. Dijkstra及其追随者更倾向于将这门科学称作计算科学（Computing Science）。
1.1.1 绳索计算机
公元前2000 年的古埃及人已经知道如何解决如下实际工程问题：通过直线l上给定 的点P，作该直线的垂线。
perpendicular(l, P)
输入：直线l及其上一点P
输出：经过P且垂直于l的直线
- 取12段等长绳索，依次首尾联结成环 //联结处称作“结”，按顺时针斱向编号为0..11
- 奴隶A看管0号结，将其固定于点P处
- 奴隶B牵动4号结，将绳索沿直线l斱向尽可能地拉直
- 奴隶C牵动9号结，将绳索尽可能地拉直
- 经过0号和9号结，绘制一条直线
算法1.1 过直线上给定点作直角
以上由古埃及人发明、由奴隶与绳索组成的这套计算工具，乍看起来与现代的电子计算机相去甚远。但就本质而言，二者之间的相似之处远多于差异，它们同样都是用于支持和实现计算过程的物理机制，亦即广义的计算机。
1.1.2 尺规计算机
欧氏几何 都分别给出了一套几何作图流程，也就是具体的算法。比如，经典的线段三等分过程可描述为如 算法1.2所示。该算法的一个典型的执行实例如图1.2所示。
