软件技术基础(修订版)
1994-12
北京航空航天大学出版社
内 容 简 介
本书是1990年出版的《软件技术基础》一书的修订版，在内容上作了一些增删与
修改，所有算法都给以必要的注释。
本书介绍计算机软件技术的基础理论知识，全书共分五篇，内容包括：程序设计
一般问题、数据结构、编译技术、操作系统和数据库系统。书中对上述内容从理论上作
了扼要的阐述，赋以最基本的概念和必要的算法，使读者能够用较少的学时获得计算
机软件方面必要的基础理论知识和算法设计能力。所有算法均使用类PASCAL程序
设计语言，易学易懂。
本书主要作为高等院校非计算机专业本科生和研究生的教材，也可供从事计算
机软件教学、科研工作的同志和生产部门的技术人员学习和参考。
目录
第一篇 编程的一些问题
第一章 编程的步骤与要求
§1.1什么是程序、什么是软件
§1.2编程的几个阶段
1.2.1编程的几个阶段
1.2.2研制大型软件（程序）系统的几点要求
§1.3程序设计的思维方法
1.3.1算法含义
1.3.2算法设计的基本思路
§1.4如何评价程序
第二章 结构化程序设计
§2.1一种新的编程方法
§2.2什么是结构化程序设计
§2.3结构化程序设计的方法
2.3.1不用或少用GOTO语句
2.3.2自顶向下，逐步求精
2.3.3分层结构与模块结构
2.3.4组织形式
§2.4结构化系统分析与设计
2.4.1结构化系统分析
2.4.2结构化系统设计
第三章 结构化程序语言
§3.1程序设计语言分类
§3.2程序语言的选择
§3.3结构化语言的特点
练习与思考题
参考文献
第二篇 数据结构
第四章 数据结构基本概念
§4.1什么是数据结构
§4.2为什么要研究数据结构
§4.3数据结构分类
§4.4数据结构中若干常用术语
§4.5算法语言
第五章 向量和数组
§5.1向量
5.1.1向量的定义
5.1.2向量的物理表示
5.1.3向量的性质
5.1.4向量运算
§5.2数组
5.2.1数组的定义
5.2.2数组的物理表示
5.2.3效率问题
§5.3稀疏数组
第六章 栈与队列
§6.1栈
6.1.1栈的定义与物理表示
6.1.2栈的运算
6.1.3多栈共享邻接空间
§6.2栈的应用
§6.3队列
6.3.1队列的定义与物理表示
6.3.2队列运算
§6.4循环队
6.4.1循环队的循环原理
6.4.2循环队运算
§6.5队列的应用
第七章 链 表
§7.1单向链表
7.1.1单向链表的结构形式
7.1.2链表运算
§7.2链表的存储空间
§7.3链接的栈和队列
§7.4循环链表
§7.5双向链表
§7.6链表的应用――一元多项式相加
§7.7十字链表
§7.8广义表及其应用
第八章 串
§8.1串的定义
§8.2串的物理表示
8.2.1串的顺序表示法
8.2.2串的链表表示法
§8.3串的运算
§8.4串的模式匹配
§8.5串的插入算法
第九章 树
§9.1树的基本概念
9.1.1树的定义
9.1.2树的基本术语
9.1.3树结构的表示方法
§9.2二叉树
9.2.1二叉树的定义
9.2.2二叉树的性质
9.2.3二叉树的物理表示
§9.3树和森林转换成二叉树
9.3.1树的二叉树表示
9.3.2森林的二叉树表示
§9.4遍历二叉树
9.4.1前序遍历
9.4.2中序遍历
9.4.3后序遍历
§9.5线索二叉树
9.5.1在二叉树中寻找结点的前驱和后继
9.5.2在线索树中求结点的前驱和后继
9.5.3二叉树线索化算法
9.5.4结点插入中序线索二叉树
§9.6哈夫曼树
9.6.1树的路径长度
9.6.2哈夫曼树及其算法
9.6.3哈夫曼树的应用
§9.7树的应用
9.7.1二叉分类树
9.7.2判定树
9.7.3集合的表示法
第十章 图
§10.1图的基本概念
§10.2图的物理表示
10.2.1邻接矩阵法
10.2.2邻接表法
10.2.3邻接多重表法
§10.3图的遍历与求图的连通分量
10.3.1纵向优先搜索法
10.3.2横向优先搜索法
10.3.3求图的连通分量
§10.4生成树和最小代价生成树
10.4.1什么是生成树和最小代价生成树
10.4.2最小代价生成树的构造方法
§10.5最短路径
10.5.1从某个源点到其它顶点的最短路径
10.5.2每对顶点间的最短路径
§10.6拓扑排序
10.6.1AOV网络与拓扑排序
10.6.2拓扑排序算法
§10.7关键路径
10.7.1什么是关键路径
10.7.2e（i）和l（i）的求法
10.7.3AOE网络的关键活动
第十一章 排序与查找
§11.1排序
11.1.1排序文件的物理表示
11.1.2选择排序
11.1.3冒泡排序
11.1.4线性插入排序
11.1.5折半插入排序
11.1.6希尔排序
11.1.7快速排序
11.1.8各种排序方法的比较
§11.2查找
11.2.1查找方法评价
11.2.2顺序查找法
11.2.3折半查找法
11.2.4分块查找法
11.2.5几种基本查找方法的比较
§11.3哈希方法
11.3.1构造哈希函数的几种方法
11.3.2处理冲突的方法
练习与思考题
参考文献
第三篇 编译技术
第十二章 编译工作的基本概念
§12.1从源程序到目标程序
12.1.1源程序和目标程序
12.1.2汇编程序
12.1.3编译程序
12.1.4解释程序
§12.2编译程序的工作过程
§12.3编译程序与其它软件工具
12.3.1编辑程序
12.3.2装入程序与连接程序
12.3.3排错程序
第十三章 词法分析
§13.1单词符号的种类和输出形式
§13.2读字符程序
13.2.1读字符准备
13.2.2超前搜索问题
§13.3词法分析的方法
13.3.1直接分析法
13.3.2状态转换图法
第十四章 语法分析
§14.1语言定义与语法结构
14.1.1形式语言描述
14.1.2文法和语言种类
14.1.3文法如何定义语言
§14.2语法分析工作的内容
§14.3语法分析的方法
14.3.1优先矩阵法
14.3.2优先数法
14.3.3状态矩阵法
14.3.4递归子程序法
§14.4各种语法分析方法的比较
第十五章 中间语言及其优化
§15.1如何从单词符号产生出中间语言
§15.2几种常用的中间语言
15.2.1逆波兰表示法
15.2.2四元组表示法
15.2.3三元组表示法
§15.3代码优化
第十六章 符号表和存储分配
§16.1符号表的结构
§16.2符号表的组织及操作
16.2.1符号表的操作
16.2.2标识符的局部性问题及其处理
§16.3存储空间分配
16.3.1静态分配存储单元
16.3.2动态分配存储单元
第十七章 出错处理
§17.1错误种类
17.1.1拼写错误
17.1.2语法错误
17.1.3语义错误
§17.2错误处理
§17.3遏止株连信息和重复信息
17.3.1遏止株连信息
17.3.2遏止重复信息
练习与思考题
参考文献
第四篇 计算机操作系统
第十八章 操作系统概论
§18.1设置操作系统的目的
18.1.1计算机的硬件组织
18.1.2软件的层次和虚拟机的概念
18.1.3设置操作系统的目的
§18.2操作系统的发展过程
18.2.1手工操作阶段
18.2.2早期批量处理阶段
18.2.3管理程序阶段
18.2.4多道程序的出现和操作系统的形成
§18.3操作系统的功能和类型
18.3.1多道批处理系统
18.3.2分时系统
18.3.3实时系统
第十九章 操作系统的基本功能
§19.1处理机管理
19.1.1中断处理
19.1.2处理机调度（处理机分配）和进程调度
§19.2存储管理
19.2.1存储管理的功能
19.2.2界地址存储管理
19.2.3虚拟存储的基本概念
19.2.4分页存储管理
19.2.5分段存储管理
19.2.6段页结合存储管理
19.2.7虚拟存储管理中的存储保护
§19.3设备管理
19.3.1外部设备分类和设备管理的功能
19.3.2外部设备的中断
19.3.3分配和驱动外部设备
19.3.4实现虚拟设备
§19.4文件管理
19.4.1文件与文件管理系统
19.4.2文件组织
19.4.3文件的使用
§19.5操作系统的用户界面
第二十章 几种操作系统介绍
§20.1UNIX操作系统
20.1.1UNIX操作系统的特点
20.1.2UNIX操作系统的结构
20.1.3UNIX操作系统的进程管理与存储管理
20.1.4UNIX操作系统的文件系统和设备管理
§20.2CP/M操作系统
20.2.1CP/M操作系统的结构
20.2.2CP/M操作系统的文件管理
20.2.3CP/M操作系统的发展
20.2.4PC―DOS简介
§20.3分布式操作系统
20.3.1分布式计算机系统概述
20.3.2分布式操作系统的特点
练习与思考题
参考文献
第五篇 数据库系统
第二十一章 数据库系统概述
§21.1数据库的概念
§21.2数据管理方法的发展
21.2.1人工管理阶段
21.2.2文件系统阶段
21.2.3数据库系统阶段
§21.3数据库技术的应用
§21.4数据模型
21.4.1层次模型
21.4.2网状模型
21.4.3关系模型
§21.5数据库系统的构成
21.5.1数据库系统
21.5.2数据库管理系统
§21.6数据库数据的存取过程
第二十二章 关系模型的数据库系统
§22.1基本概念
22.1.1笛卡尔积和关系
22.1.2关系数据语言的分类
§22.2关系代数
22.2.1传统的集合运算
22.2.2专门的关系运算
22.2.3检索操作
22.2.4存储操作
§22.3关系演算
22.3.1元组关系演算
22.3.2域关系演算
§22.4介于关系代数与关系演算之间的语言SQL
§22.5关系数据语言的特点
§22.6关系数据库的模式和子模式
22.6.1模式
22.6.2子（外）模式
§22.7查询优化概述
22.7.1查询优化问题的提出
22.7.2优化的一般策略
§22.8关系模式的规范化
22.8.1关系的规范化与范式
22.8.2函数依赖和码（关键字）
22.8.32NF
22.8.43NF
22.8.5BCNF（Boyce－Codd范式）
第二十三章 ORACLE关系数据库系统
§23.1概述
§23.2用户友好接口UFI
23.2.1SQL和UFI
23.2.2索引和聚集
23.2.3数据控制
23.2.4报表格式输出
23.2.5UFI命令
§23.3交互式应用工具IAF
23.3.1IAG使用概述
23.3.2IAP的调用
§23.4宿主语言接口HLI
第二十四章 网状模型的数据库系统
§24.1CODASYL系统的总体结构
§24.2CODASYL系统的数据模型
24.2.1记录类型
24.2.2系类型
24.2.3系值
24.2.4CODASYL系统对事物联系的表示方法
§24.3记录的存放方法
24.3.1域
24.3.2数据库码
24.3.3运行单位与当前值
24.3.4记录的定位方式
§24.4系类型的描述及其实现
24.4.1系序原则
24.4.2属籍类别
24.4.3系值选择
24.4.4系值内有关记录值的连接实现
§24.5模式数据描述语言
§24.6子模式数据描述语言
§24.7数据操纵语言
第二十五章 数据库的保护
§25.1安全性
§25.2数据的完整性
§25.3并发控制
§254数据库的恢复
第二十六章 数据库设计
§26.1数据库设计过程
§26.2数据字典
第二十七章 分布式数据库系统概述
§27.1定义与分类
§27.2分布式数据库系统的几个主要问题
27.2.1数据分布
27.2.2并发操作控制
27.2.3查询处理
27.2.4恢复处理
练习与思考题
参考文献
