
本书是《计算机软件技术基础》的第二版,书中所有算法均采用C++描述。全书共6章,介绍了计算机软件设计的基础知识、方法与实用技术。主要内容包括:算法,基本数据结构及其运算,查找与排序技术,资源管理技术,数据库技术,应用软件设计与开发技术。第二版主要修订了第一版的前3章,在每章后都配有一定数量的习题。
本书内容丰富,通俗易懂,实用性强,可作为非计算机专业的研究生、大学生的软件课程教材,也可作为广大从事计算机应用工作的科技人员的参考书。
非计算机专业的学生(包括广大科技人员)学习和掌握软件技术不可能像计算机专业的学生那样学习软件的各门课程,因此有必要将主要的软件技术和知识在一门课程中介绍,但又不能是拼盘式的组合。在国外根本没有这样的教材,国内这样的教材也不多,有的教材虽然名称叫“软件技术”,但实际上是一些新软件的使用。本教材介绍的是软件技术,而不是软件的使用。
本教材主要是针对非计算机专业的学生对于计算机软件技术的需要,将有关软件基础知识以及应用技术介绍给读者。其特点如下:
(1) 系统性。本教材并不是简单地将计算机专业的各门课程内容拼装在一起,而是根据软件应用技术的需要,将它们有机地结合在一起,为读者提供软件开发中所需要的软件知识和技术。全书以数据结构与算法为基础,以软件技术为线索,系统性强。
(2) 强调应用。本教材强调以应用为目的,全书中实例比较丰富。全书几乎是围绕解决软件开发中所遇到的软件技术问题来展开的。在介绍系统软件(如操作系统)时,为了便于读者理解,也适当介绍一些原理,但主要还是介绍实现系统软件中的技术,以便读者将这些技术用到应用软件的开发中。
(3) 可读性强。本书深入浅出,通过例子引出基本概念,便于读者接受。
本书第二版主要修订的是第一版的前3章。书中所有的算法均采用C++描述。由于C++语言既可用于面向过程的程序设计,又支持面向对象的程序设计,因此,作者在对算法进行描述时,尽量采用最合适的程序设计方法。例如,对于基本的数据结构(如顺序存储与链式存储的线性表、栈、队列等)采用面向对象的方法,将数据与运算封装成类,以便在其他应用程序中直接使用;而对于同一批数据进行同类操作的各种算法(如对线性表的各种排序方法)采用面向过程的方法,将各种不同的算法用普通函数来描述。这样,书中的所有算法就可以直接在实际应用中方便地使用。
本书内容丰富,通俗易懂,实用性强,书中的所有算法程序(C++描述)均上机调试通过。本书可作为非计算机专业的研究生或大学生的软件课程教材,也可作为广大从事计算机应用工作的科技人员的参考书。由于作者水平有限,书中难免有不妥之处,恳请读者批评指正。
作者 2007年1月
1.1算法的基本概念1
1.1.1算法的基本特征1
1.1.2算法的基本要素2
1.2算法设计基本方法3
1.3算法的复杂度分析9
1.3.1算法的时间复杂度9
1.3.2算法的空间复杂度11
习题12
基本数据结构及其运算
2.1数据结构的基本概念13
2.1.1两个例子13
2.1.2什么是数据结构16
2.1.3数据结构的图形表示19
2.2线性表及其顺序存储结构21
2.2.1线性表及其运算21
2.2.2栈及其应用30
2.2.3队列及其应用41
2.3线性链表及其运算52
2.3.1线性链表的基本概念52
2.3.2线性链表的基本运算66
2.3.3循环链表71
2.3.4多项式的表示与运算75
2.4数组83
2.4.1数组的顺序存储结构83
2.4.2规则矩阵的压缩84
2.4.3一般稀疏矩阵的表示87
2.5树与二叉树113
2.5.1树的基本概念113
2.5.2二叉树及其基本性质116
2.5.3二叉树的遍历119
2.5.4二叉树的存储结构120
2.5.5穿线二叉树126
2.5.6表达式的线性化138
2.6图140
2.6.1图的基本概念140
2.6.2图的存储结构141
2.6.3图的遍历145
2.6.4图邻接表类146
习题152
查找与排序技术
3.1基本的查找技术155
3.1.1顺序查找155
3.1.2有序表的对分查找155
3.1.3分块查找160
3.2哈希表技术161
3.2.1哈希表的基本概念161
3.2.2几种常用的哈希表164
3.3基本的排序技术182
3.3.1冒泡排序与快速排序183
3.3.2简单插入排序与希尔排序188
3.3.3简单选择排序与堆排序192
3.3.4其他排序方法简介196
3.4二叉排序树及其查找200
3.4.1二叉排序树的基本概念201
3.4.2二叉排序树的插入202
3.4.3二叉排序树的删除204
3.4.4二叉排序树查找206
3.5多层索引树及其查找208
3.5.1B-树209
3.5.2B+树219
3.6拓扑分类229
习题232
资源管理技术
4.1操作系统的概念234
4.1.1操作系统的功能与任务234
4.1.2操作系统的发展过程235
4.1.3操作系统的分类238
4.2多道程序设计241
4.2.1并发程序设计241
4.2.2进程244
4.2.3进程之间的通信249
4.2.4多道程序的组织254
4.3存储空间的组织255
4.3.1内存储器的管理技术255
4.3.2外存储器中文件的组织结构259
习题266
数据库技术
5.1数据库基本概念267
5.1.1数据库技术与数据库系统267
5.1.2数据描述272
5.1.3数据模型275
5.2关系代数278
5.3数据库设计285
5.3.1数据库设计的基本概念285
5.3.2数据库设计的过程286
5.3.3数据字典293
5.4关系数据库语言SQL294
5.4.1SQL语言概述294
5.4.2数据库定义298
5.4.3数据查询303
5.4.4数据修改312
5.4.5数据控制315
5.4.6嵌入式SQL318
习题323
应用软件设计与开发技术
6.1软件工程概述325
6.1.1软件工程的概念325
6.1.2软件生命周期326
6.1.3软件支援环境328
6.2软件详细设计的表达329
6.2.1程序流程图330
6.2.2NS图331
6.2.3问题分析图PAD332
6.2.4判定表332
6.2.5过程设计语言333
6.3结构化分析与设计方法334
6.3.1应用软件开发的原则和方法334
6.3.2结构化分析方法336
6.3.3结构化设计方法340
6.4测试与调试基本技术346
6.4.1测试346
6.4.2调试353
6.5软件开发新技术355
6.5.1原型方法355
6.5.2瀑布模型356
6.5.3面向对象技术357
习题358
参考文献359