计算机软件技术基础）

(1) 系统性。针对软件应用技术的需要，为读者提供软件设计与开发过程中所需要的系统知识和典型技术。

(2) 应用性。以应用为目的，提炼系统软件中的技术用于开发应用软件。书中实例丰富，有利于读者理解和掌握。习题丰富，有利于读者通过自己的练习提高能力。

(3) 可读性。本书深入浅出，使读者容易接受。

本书历经数次修订，是作者多年教学、科研成果的结晶，可用于高校理工类专业的计算机基础课教学。

　　《计算机软件技术基础（第四版）（新世纪计算机基础教育丛书（谭浩强主编）》针对高等学校的大学生、研究生以及科技工作者与研究人员学习计算机软件应用技术的需要，介绍了计算机软件设计的基础知识、方法与实用技术。书中主要内容包括集合与算法的基本概念、基本数据结构及其运算、查找与排序技术、资源管理技术、数据库设计技术、编译技术概述、应用软件设计与开发技术。每章都配有一定数量的习题。
　　《计算机软件技术基础（第四版）（新世纪计算机基础教育丛书（谭浩强主编）》内容丰富、通俗易懂、实用性强，可作为高等学校的教材，也可作为广大从事计算机应用工作的科技人员的参考书。

徐士良 清华大学电子工程系教授，曾担任全国计算机基础教育研究会理事、学术委员会副主任，全国计算机等级考试委员会委员。在系内首先开设并主讲计算机算法、数值分析、计算机基础、软件基础、数据结构、多种计算机程序设计语言等课程。编著出版了《计算机常用算法》、《数值分析与算法》、《计算机公共基础》、《计算机软件技术基础》、《实用数据结构》、《C语言程序设计教程》、《数据与算法》、多种语言版本的《常用算法程序集》等40多部教材，其中《软件应用技术基础》(《计算机软件技术基础》的前版)获原电子工业部优秀教材壹等奖。

预备知识1.1集合1
1.1.1集合及其基本运算1
1.1.2自然数集与数学归纳法3
1.1.3笛卡儿积5
1.1.4二元关系5
1.2算法6
1.2.1算法的基本概念6
1.2.2算法设计基本方法8
1.2.3算法的复杂度分析13
习题15
基本数据结构及其运算 2.1数据结构的基本概念17
2.1.1什么是数据结构17
2.1.2数据结构的图形表示20
2.2线性表及其顺序存储结构22
2.2.1线性表及其运算22
2.2.2栈及其应用31
2.2.3队列及其应用41
2.3线性链表52
2.3.1线性链表的基本概念52
2.3.2线性链表的插入与删除56
2.3.3带链的栈与队列61
2.3.4循环链表68
2.3.5多项式的表示与运算71
2.4线性表的索引存储结构78
2.4.1索引存储的概念782.4.2“顺序索引顺序”存储方式80
2.4.3“顺序索引链接”存储方式81
2.4.4多重索引存储结构82
2.5数组83
2.5.1数组的顺序存储结构83
2.5.2规则矩阵的压缩83
2.5.3一般稀疏矩阵的表示86
2.6树与二叉树112
2.6.1树的基本概念112
2.6.2二叉树及其基本性质115
2.6.3二叉树的遍历118
2.6.4二叉树的存储结构119
2.6.5穿线二叉树124
2.6.6表达式的线性化136
2.7图138
2.7.1图的基本概念138
2.7.2图的存储结构139
2.7.3图的遍历143
2.7.4最短距离问题144
2.7.5图邻接表类146
习题155
查找与排序技术3.1基本的查找技术158
3.1.1顺序查找158
3.1.2有序表的对分查找158
3.1.3分块查找163
3.2哈希表技术164
3.2.1哈希表的基本概念164
3.2.2几种常用的哈希表167
3.3基本的排序技术185
3.3.1冒泡排序与快速排序185
3.3.2简单插入排序与希尔排序190
3.3.3简单选择排序与堆排序192
3.3.4其他排序方法简介195
3.4二叉排序树及其查找1993.4.1二叉排序树的基本概念200
3.4.2二叉排序树的插入201
3.4.3二叉排序树的删除202
3.4.4二叉排序树查找204
3.5多层索引树及其查找206
3.5.1B－树207
3.5.2B＋树217
3.6拓扑分类227
3.7字符串匹配229
3.7.1字符串的基本概念229
3.7.2字符串匹配的KMP算法230
习题235
资源管理技术4.1操作系统的概念237
4.1.1操作系统的功能与任务237
4.1.2操作系统的发展过程238
4.1.3操作系统的分类241
4.2多道程序设计244
4.2.1并发程序设计244
4.2.2进程247
4.2.3进程之间的通信251
4.2.4多道程序的组织256
4.3存储空间的组织257
4.3.1内存储器的管理技术257
4.3.2外存储器中文件的组织结构261
习题268
数据库设计技术5.1数据库基本概念269
5.1.1数据库技术与数据库系统269
5.1.2数据描述274
5.1.3数据模型276
5.2关系代数280
5.3数据库设计286
5.3.1数据库设计的基本概念286
5.3.2数据库设计的过程287
5.3.3数据字典293
习题295
编译技术概述6.1编译程序的工作过程及其基本组成297
6.1.1编译程序的工作过程297
6.1.2编译程序的基本组成298
6.2状态矩阵法的编译过程299
6.2.1状态矩阵法的基本原理299
6.2.2状态矩阵的压缩300
6.3词法分析302
6.3.1词法分析的任务302
6.3.2读字符程序303
6.3.3状态矩阵法的词法分析过程304
6.3.4算术常数的识别和翻译307
6.4中间语言表示310
6.4.1波兰表示310
6.4.2三元组表示312
6.5语法的分析与加工316
习题321
应用软件设计与开发技术7.1软件工程概述322
7.1.1软件工程的概念322
7.1.2软件生命周期322
7.1.3软件支援环境325
7.2软件详细设计的表达326
7.2.1程序流程图326
7.2.2NS图327
7.2.3问题分析图PAD329
7.2.4判定表329
7.2.5过程设计语言PDL330
7.3结构化分析与设计方法331
7.3.1应用软件开发的原则和方法331
7.3.2结构化分析方法332
7.3.3结构化设计方法336
7.4测试与调试基本技术342
7.4.1测试342
7.4.2调试349
7.5软件开发新技术351
7.5.1原型方法351
7.5.2瀑布模型352
7.5.3面向对象技术353
习题354

参考文献355

　　本书第二版是普通高等教育“十一五”国家级规划教材，并被评为2008年度普通高等教育精品教材。
　　本次修订保持了前三版的特点，在第三版的基础上进行了如下几方面的调整与修改。
　　(1) 所有算法程序均采用C++语言进行描述。由于C++语言既可用于面向过程的程序设计，又支持面向对象的程序设计，因此，作者在对算法进行描述时，尽量采用最合适的程序设计方法。例如，对于同一批数据进行同类操作的单个算法采用面向过程的方法；对于基本的数据结构（如顺序存储与链式存储的线性表、栈、队列等）采用面向对象的方法，将数据与运算封装成类，以便在其他应用程序中直接使用。这样，书中的所有算法都可以直接在实际应用中方便地使用。
　　(2) 在第2章的2.7节中增加了最短距离问题的内容。
　　(3) 在第3章中增加了字符串匹配的内容。
　　本书内容丰富、通俗易懂、实用性强，书中所有算法程序均上机调试通过。本书可作为高等学校的大学生或研究生软件课程的教材，也可作为广大从事计算机应用工作的科技人员的参考书。
　　由于作者水平有限，书中难免有错误或不妥之处，恳请读者批评指正。
　　作者
　　本书第二版是普通高等教育“十一五”国家级规划教材，并被评为2008年度普通高等教育精品教材。
　　本次修订保持了第二版的特点（见第二版前言），主要在内容上作了如下几方面的调整。
　　(1) 在第1章中增加了集合方面的基本知识，对算法方面的基本内容进行了适当的精简。
　　(2) 在第2章中增加了索引存储结构的内容。
　　(3) 在第5章中删去了关系数据库语言SQL的内容。
　　(4) 新增加了编译技术概述一章。
　　本书内容丰富、通俗易懂、实用性强，书中所有算法程序均上机调试通过。本书可作为大学生或研究生的软件技术基础课程的教材，也可作为广大从事计算机应用工作的科技人员的参考书。
　　由于作者水平有限，书中难免有错误或不妥之处，恳请读者批评指正。
　　作者
　　高等学校非计算机专业的学生（包括广大科技人员）如何学习和掌握软件技术，是一个很重要的问题。他们不可能像计算机专业的学生那样学习软件的各门课程，因此有必要将主要的软件技术和知识在一门课程中介绍，但又不能是拼盘式的组合。国外根本没有这样的教材，国内这样的教材也不多。有的教材虽然名称叫“软件技术”，但实际上是一些新软件的使用。本教材介绍的是软件技术，而不是软件的使用。
　　本教材主要针对高等学校非计算机专业的学生学习计算机软件技术的需要，介绍有关软件基础知识及应用技术。其特点如下：
　　(1) 系统性。本教材不是将计算机专业各门课程的内容简单地拼装在一起，而是针对学生对软件应用技术的需要，将其有机结合，为读者提供软件开发中所需要的软件知识和技术。全书以数据结构与算法为基础，以软件技术为线索，系统性较强。
　　(2) 强调应用。本教材强调以应用为目的，书中实例比较丰富，内容围绕解决软件开发中所遇到的软件技术问题来展开。在介绍系统软件（如操作系统）时，为了便于读者理解，也适当介绍一些原理，但主要还是介绍实现系统软件中的技术，以便读者将这些技术用到应用软件的开发中。
　　(3) 可读性强。本书深入浅出，通过实例引出基本概念，便于读者接受。
　　此次对本书的修订主要是前三章。书中所有的算法均采用C++描述。由于C++语言既可用于面向过程的程序设计，又支持面向对象的程序设计，因此，作者在对算法进行描述时，尽量采用最合适的程序设计方法。例如，对于基本的数据结构（如顺序存储与链式存储的线性表、栈、队列等）采用面向对象的方法，将数据与运算封装成类，以便在其他应用程序中直接使用；而对于同一批数据进行同类操作的各种算法（如对线性表的各种排序方法）则采用面向过程的方法，将各种不同的算法用普通函数来描述。这样，书中的所有算法都可以直接应用。
　　本书内容丰富、通俗易懂、实用性强，书中所有算法程序（C++描述）均上机调试通过。本书可作为非计算机专业的大学生或研究生软件课程的教材，也可作为广大从事计算机应用工作的科技人员的参考书。
　　由于作者水平有限，书中难免有错误或不妥之处，恳请读者批评指正。
　　作者
　　随着计算机技术的深入发展，计算机技术的应用已经渗透到各个领域，特别是计算机软件的设计与开发，已经不只是计算机专业人员的事情了。现在，越来越多的软件需要非计算机专业的人员来设计与开发，很多系统软件与应用软件由非计算机专业人员来使用，并在此基础上进行二次开发。因此，普及计算机软件技术已经是大势所趋。
　　本书在《软件应用技术基础》（该书由清华大学出版社出版，获电子工业部优秀教材一等奖）一书的基础上改写而成，可满足广大非计算机专业的学生学习软件设计与开发的需要。作为应用计算机的科技人员，除了要掌握现有计算机软件的使用外，从实际应用出发，还必须要掌握软件设计与开发的基本知识和有关技术，如数据的组织、程序的组织、计算机资源的利用、数据的处理技术等，以便得心应手地进行应用软件的设计与开发。
　　全书共分6章，每章后面都附有一定数量的习题。
　　第1章介绍算法。内容主要包括算法的基本概念、算法的基本设计方法、算法的复杂度分析等内容。
　　第2章介绍基本数据结构及其运算。内容主要包括数据结构的基本概念，线性表、栈、队列及其在顺序存储结构下的运算和应用，线性链表及其运算，数组，二叉树的概念、存储及其应用，图的存储及其遍历。
　　第3章介绍常用的查找与排序技术。内容主要包括基本的查找技术、哈希表技术、基本的排序技术、二叉排序树及其查找、多层索引树及其查找、拓扑分类。
　　第4章介绍资源管理技术。内容主要包括操作系统的功能与任务、多道程序设计、存储空间的组织。
　　第5章介绍数据库技术。内容主要包括数据库基本概念、关系代数、数据库设计、关系数据库语言SQL。
　　第6章介绍应用软件设计与开发技术。内容主要包括软件工程概述、软件详细设计的表达、结构化分析与设计方法、测试与调试基本技术、软件开发新技术。
　　本书内容丰富、通俗易懂、实用性强，书中所有算法程序均上机调试通过。本书可作为高等学校非计算机专业的大学生或研究生软件课程的教材，也可作为广大从事计算机应用工作的科技人员的参考书。
　　由于作者水平有限，书中难免有错误或不妥之处，恳请读者批评指正。作者