计算机软件技术基础

目录 第1部分 数据结构 第1章 概述 1 1.1 计算机软件技术 1 1.2 数据结构的概念 2 1.2.1 数据结构中的概念和术语 3 1.2.2 数据的逻辑结构和物理结构 4 1.3 算法和算法分析 6 1.3.1 算法的基本概念 6 1.3.2 算法的分析与度量 6 1.4 抽象数据类型 8 1.4.1 抽象数据类型的概念 8 1.4.2 抽象数据类型的实现 8 小结 10 习题1 11 第2章 线性结构 12 2.1 线性表 12 2.1.1 线性表的定义 12 2.1.2 线性表的顺序存储与实现 13 2.1.3 线性表的链式存储与实现 20 2.1.4 顺序表和链表的比较 30 2.2 栈和队列 31 2.2.1 栈 31 2.2.2 队列 40 2.3 串 48 2.3.1 串及其基本运算 48 2.3.2 串的定长顺序存储及其基本运算 49 2.4 数组和特殊矩阵 51 2.4.1 多维数组 51 2.4.2 特殊矩阵的压缩存储 54 小结 57 习题2 58 第3章 非线性数据结构 61 3.1 树和二叉树 61 3.1.1 树的定义和基本概念 61 3.1.2 树的存储结构 63 3.1.3 二叉树的定义和性质 65 3.1.4 二叉树的存储与实现 68 3.1.5 二叉树的遍历 71 3.1.6 树、森林与二叉树的转换 80 3.2 图 82 3.2.1 图的定义和基本概念与基本操作 82 3.2.2 图的存储结构 85 3.2.3 图的遍历 89 小结 92 习题3 92 第4章 查找和排序 94 4.1 查找 94 4.1.1 查找的相关术语 94 4.1.2 顺序查找 96 4.1.3 折半查找 97 4.1.4 分块查找 100 4.1.5 二叉排序树查找 101 4.1.6 哈希表查找 103 4.2 排序 108 4.2.1 排序的基本概念 108 4.2.2 插入排序 109 4.2.3 简单选择排序 111 4.2.4 交换排序 113 4.2.5 快速排序 114 4.2.6 希尔排序 118 4.2.7 归并排序 119 小结 121 习题4 122 第2部分 操作系统 第5章 操作系统概述 123