计算机软件技术基础

预备知识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

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