本书按照教育部高等学校大学计算机课程教学指导委员会提出的“三个层次五门课”
的系列课程体系设置的第二层次的一门基础理论课的课程大纲编写而成，系统介绍了计算
机软件技术的基本内容，包括数据结构、计算机操作系统、软件工程及数据库技术。本书
内容丰富、重点突出，体系结构和内容选取强调基础性和实用性，符合理工科学生的认知
规律，各章后均配有选择题、填空题和问答题，供学生练习使用。
本书适合作为高等院校理工科非计算机专业教材，也可供科技人员及计算机爱好者阅
读，还可作为全国计算机二级考试软件理论基础部分的参考用书。

本书按照教育部高等学校大学计算机课程教学指导委员会提出的“三个层次五门课”系列
课程体系设置的第二层次的一门基础理论课的课程大纲编写而成。通过本书的学习，学生会
对计算机软件设计所需的基本知识和技巧有一个全面的认识，为软件设计开发工作打下坚实的
基础。
学习本书需要学习一门计算机编程语言作为先导课程，推荐C 语言。针对非计算机专业的
理工科学生，着重介绍了数据结构、计算机操作系统、软件工程和数据库技术等方面的基础理
论知识。一方面涵盖尽可能多的专业知识以提高学生对计算机软件开发的专业素养，一方面增
加与全国计算机考级考试二级考试的契合度，做到技能提高和考证通过两不耽误。内容力求由
浅入深，通俗易懂，简明扼要，注重实用技术。
本书共4 章，第1 章数据结构，主要讲述算法与数据结构的基本概念及常用的典型数据结
构与算法，包括链表、队列、栈、数组等线性数据结构，二叉树、哈夫曼树等树形数据结构和
简单的图形数据结构。在算法方面，结合数据结构讲述了查找与排序算法。第2 章计算机操作
系统，主要介绍操作系统的几大管理功能：处理器管理、存储管理、作业管理、设备管理与文
件管理。第3 章软件工程，介绍软件工程的概念、常用开发模型以及新型软件工程技术。第4
章数据库技术，主要介绍数据库的基本概念与技术，包括数据库的基础知识、数据库的数据模
型、结构化查询语言、数据库设计以及新型数据库技术。
本书内容简明清晰、重点突出、实例丰富、图文并茂，并结合每章内容给出了习题，以达
到通过练习巩固每章所学知识的目的。
本书由李廷元、付茂洺、何元清任主编，高大鹏、戴蓉、张欢任副主编。其中，李廷元、
高大鹏编写了第1 章，付茂洺、张欢编写了第2 章，戴蓉编写了第3 章，何元清、张欢编写了
第4 章，刘晓东、王欣、张选芳主审。
本书在编写和出版过程中得到了许多老师的热情支持和帮助，在此对他们一并表示诚挚的
谢意！
由于编者水平有限，加之时间仓促，书中难免存在疏漏和不足之处，恳请同行和读者不吝
赐教。
编 者
2017 年2 月

第1 章 数据结构.............................................................................................................1
1.1 数据结构的基本概念.................................................................................................... 1
1.1.1 数据结构的研究内容及其重要性...................................................................... 1
1.1.2 数据结构的基本概念和术语............................................................................. 2
1.1.3 数据结构、数据类型和抽象数据类型.............................................................. 5
1.2 线性结构....................................................................................................................... 7
1.2.1 线性表............................................................................................................... 7
1.2.2 栈和队列......................................................................................................... 22
1.2.3 数组和广义表.................................................................................................. 29
1.2.4 串..................................................................................................................... 37
1.3 树和二叉树................................................................................................................. 39
1.3.1 树形结构基本概念.......................................................................................... 39
1.3.2 二叉树............................................................................................................. 42
1.3.3 二叉树的遍历.................................................................................................. 46
1.3.4 树、森林与二叉树的转换............................................................................... 49
1.3.5 哈夫曼树和哈夫曼编码................................................................................... 50
1.3.6 二叉排序树...................................................................................................... 53
1.4 图................................................................................................................................ 54
1.4.1 图的基本概念.................................................................................................. 54
1.4.2 有向图和无向图.............................................................................................. 54
1.4.3 子图与路径...................................................................................................... 56
1.4.4 连通图和连通分量.......................................................................................... 56
1.4.5 图的存储结构.................................................................................................. 57
1.4.6 图的遍历......................................................................................................... 59
1.5 查找和排序................................................................................................................. 61
1.5.1 查找................................................................................................................. 61
1.5.2 排序................................................................................................................. 69
本章小结.............................................................................................................................. 79
习题..................................................................................................................................... 79
第2 章 计算机操作系统................................................................................................ 91
2.1 计算机操作系统简介.................................................................................................. 91
2.1.1 操作系统概述.................................................................................................. 91
2.1.2 操作系统的发展及分类................................................................................... 92
2.1.3 操作系统的主要特征和功能........................................................................... 96
2 计算机软件技术基础
2.2 处理器管理................................................................................................................. 98
2.2.1 程序执行的基本特征...................................................................................... 98
2.2.2 进程的定义及特征.......................................................................................... 99
2.2.3 进程的状态和转换.........................................................................................100
2.2.4 进程的描述.....................................................................................................103
2.2.5 处理器调度.....................................................................................................107
2.2.6 进程调度........................................................................................................110
2.2.7 并发进程........................................................................................................113
2.2.8 临界区管理.....................................................................................................116
2.2.9 进程消息传递.................................................................................................124
2.2.10 死锁..............................................................................................................127
2.2.11 作业调度.......................................................................................................128
2.2.12 线程..............................................................................................................130
2.3 存储管理....................................................................................................................134
2.3.1 存储管理概述.................................................................................................134
2.3.2 连续存储管理.................................................................................................137
2.3.3 可变分区存储管理.........................................................................................138
2.3.4 主存扩充技术.................................................................................................140
2.3.5 分页式存储管理.............................................................................................141
2.3.6 分段式存储管理.............................................................................................144
2.3.7 段页式存储管理.............................................................................................145
2.3.8 虚拟存储管理.................................................................................................146
2.4 设备管理....................................................................................................................149
2.4.1 设备管理概述.................................................................................................149
2.4.2 I/O 控制方式..................................................................................................152
2.4.3 设备的分配.....................................................................................................155
2.4.4 设备无关性和缓冲技术..................................................................................157
2.4.5 设备驱动程序.................................................................................................159
2.5 文件管理....................................................................................................................160
2.5.1 文件系统的基本概念.....................................................................................160
2.5.2 文件的组织和存取.........................................................................................162
2.5.3 文件目录........................................................................................................164
2.5.4 文件存储空间管理.........................................................................................168
2.5.5 文件的共享.....................................................................................................170
本章小结.............................................................................................................................172
习题....................................................................................................................................172
第3 章 软件工程......................................................................................................... 175
3.1 软件工程概述.............................................................................................................175
3.1.1 软件................................................................................................................175
3.1.2 软件危机........................................................................................................177
3.1.3 软件工程........................................................................................................179
目录3
3.2 软件过程....................................................................................................................181
3.2.1 软件过程的概念.............................................................................................182
3.2.2 软件生存周期和软件过程模型......................................................................182
3.2.3 典型的软件过程模型.....................................................................................184
3.3 软件需求分析.............................................................................................................187
3.3.1 需求分析的概念.............................................................................................187
3.3.2 需求分析的任务.............................................................................................187
3.3.3 需求分析的技术.............................................................................................188
3.3.4 结构化分析法.................................................................................................189
3.3.5 数据流图........................................................................................................190
3.3.6 数据字典........................................................................................................192
3.3.7 加工说明........................................................................................................193
3.3.8 实体-联系图...................................................................................................194
3.3.9 状态转换图.....................................................................................................195
3.3.10 需求规格说明和验证....................................................................................196
3.4 软件设计....................................................................................................................197
3.4.1 软件设计概述.................................................................................................197
3.4.2 软件设计基本原理.........................................................................................197
3.4.3 模块化设计的优化.........................................................................................201
3.4.4 软件概要设计.................................................................................................202
3.4.5 面向数据流的设计.........................................................................................203
3.4.6 软件详细设计.................................................................................................205
3.5 面向对象技术.............................................................................................................209
3.5.1 面向对象的基本概念.....................................................................................209
3.5.2 面向对象的软件开发过程..............................................................................211
3.5.3 统一建模语言UML 概述...............................................................................212
3.6 软件编码....................................................................................................................213
3.6.1 编码风格........................................................................................................214
3.6.2 编程语言的选择.............................................................................................215
3.7 软件测试....................................................................................................................217
3.7.1 测试的目标和任务.........................................................................................217
3.7.2 软件测试方法.................................................................................................218
3.7.3 白盒测试技术.................................................................................................219
3.7.4 黑盒测试技术.................................................................................................220
3.7.5 软件测试策略.................................................................................................221
3.7.6 软件调试........................................................................................................223
3.8 软件维护....................................................................................................................224
3.8.1 软件维护的概念.............................................................................................224
3.8.2 软件维护的特点.............................................................................................225
3.8.3 软件的可维护性.............................................................................................227
3.8.4 软件维护过程.................................................................................................227
3.9 新型软件工程技术.....................................................................................................229
4 计算机软件技术基础
3.9.1 软件复用........................................................................................................229
3.9.2 软件能力成熟度模型.....................................................................................231
本章小结.............................................................................................................................234
习题....................................................................................................................................234
第4 章 数据库技术..................................................................................................... 240
4.1 数据库技术基础.........................................................................................................240
4.1.1 数据、数据库、数据库管理系统...................................................................241
4.1.2 数据库技术的产生与发展..............................................................................242
4.1.3 数据库系统.....................................................................................................244
4.1.4 数据库系统体系结构.....................................................................................246
4.2 数据描述....................................................................................................................248
4.3 数据模型....................................................................................................................249
4.3.1 数据模型的基本概念.....................................................................................249
4.3.2 层次数据模型.................................................................................................250
4.3.3 网状数据模型.................................................................................................251
4.3.4 关系数据模型.................................................................................................252
4.3.5 面向对象数据库模型.....................................................................................258
4.4 结构化查询语言（SQL） ...........................................................................................258
4.4.1 SQL 的产生及应用情况.................................................................................258
4.4.2 SQL 的特点....................................................................................................259
4.4.3 SQL 数据库体系结构.....................................................................................260
4.4.4 SQL 数据定义................................................................................................261
4.4.5 数据库的基本查询.........................................................................................264
4.4.6 数据更新........................................................................................................267
4.4.7 SQL 数据控制................................................................................................268
4.4.8 嵌入式SQL ....................................................................................................270
4.5 数据库设计................................................................................................................270
4.6 数据库新技术.............................................................................................................272
4.6.1 多媒体数据库.................................................................................................272
4.6.2 分布式数据库.................................................................................................274
4.6.3 网络环境下的数据库体系..............................................................................277
4.6.4 数据仓库........................................................................................................280
4.6.5 数据挖掘技术.................................................................................................283
本章小结.............................................................................................................................286
习题....................................................................................................................................287
参考文献....................................................................................................................... 292

李廷元：中国飞行学院计算机学院计算机科学教研室主任、教授、研究方向：算法分析、移动互联网。讲授课程：数据结构、JAVA程序设计、JSP网页设计；
付茂洺：中国飞行学院计算机学院计算机科学教研室副主任、副教授、研究方向：计算机图形图像、操作系统。讲授课程：计算机操作系统，C语言程序设计。
何元清：中国飞行学院计算机学院计算机工程教研室主任、教授、研究方向：并行计算。讲授课程：数据库原理及应用；算法设计。