中国科学技术大学：《数据结构及其算法》课程教学资源（教案讲义）第1章 绪论（主讲：张昱、马建辉）

1.1 什么是数据结构 1.2 基本概念和术语 1.3 抽象数据类型的表示与实现 1.4 算法和算法分析 1.4.1 算法 1.4.2 算法设计的要求 1.4.3 算法效率的度量 1.4.4 算法的存储空间的需求

• 概述面向对象语言的重要概念和实现技术 • 以C++语言为例，介绍如何将C++程序翻译成C程序 • 实际的编译器大都把C++程序直接翻译成低级语言程序

• C语言编译系统 – 预处理器、编译器、汇编器、连接器 – 目标文件的格式、静态库、动态连接 • Java运行系统

• 一个简单的代码生成算法 – 涉及存储管理、指令选择、寄存器分配和计算次序选择等基本问题 • 通过一个完整的例子来介绍代码优化

– 介绍几种常用的中间表示：后缀表示、图形表示和三地址代码 – 用语法制导定义和翻译方案来说明源语言的各种 构造怎样被翻译成中间形式

• 讨论一个活动记录中的数据布局 • 程序执行过程中，所有活动记录的组织方式

–简要介绍语法制导的翻译 – 介绍静态检查中最典型的部分 —— 类型检查 忽略其他的静态检查：控制流检查、唯一性检查、关联名字检查等

– 上下文无关文法 – 自上而下分析和自下而上分析 – 围绕分析器的自动 围绕分析器的自动 成展开 生

– 词法分析器：把构成源程序的字符流翻译成记号流，还完成和用户接口的一些任务 – 围绕词法分析器的自动生成展开 – 介绍正规式、状态转换图和有限自动机概念