软件基础简明教程

目录 第1章 绪论 1 1.1 计算机和计算机软件 1 1.1.1 计算机系统的组成 1 1.1.2 计算机语言与程序 2 1.1.3 软件的概念与软件的发展 4 1.2 数据结构概述 6 1.2.1 数据与数据元素 7 1.2.2 数据结构 7 1.3 算法与算法分析 10 1.3.1 算法的定义与描述 10 1.3.2 算法分析与复杂度计算 11 习题1 12 第2章 线性表 15 2.1 线性表及其逻辑结构 15 2.1.1 线性表的定义 15 2.1.2 线性表的基本操作 16 2.2 线性表的顺序存储结构及运算实现 16 2.2.1 顺序表 16 2.2.2 顺序表基本运算的实现 18 2.3 线性表的链式存储结构及运算实现 23 2.3.1 单链表 23 2.3.2 单链表基本运算的实现 25 2.3.3 循环链表 30 2.3.4 双向链表 32 2.3.5 单链表应用示例 34 习题2 36 第3章 特殊线性表 40 3.1 栈 40 3.1.1 栈的定义及基本运算 40 3.1.2 栈的存储结构及运算实现 41 3.2 队列 46 3.2.1 队列的定义及基本运算 46 3.2.2 队列的存储结构及运算实现 46 3.3 字符串 52 3.3.1 字符串的基本概念 52 3.3.2 字符串的顺序存储结构及基本运算 54 3.3.3 字符串的链式存储结构及基本运算 57 3.3.4 简单模式匹配 60 3.4 数组 62 3.4.1 数组的基本概念及存储结构 62 3.4.2 稀疏矩阵的三元组表示及矩阵转置 65 习题3 69 第4章 非线性数据结构 74 4.1 树与二叉树 74 4.1.1 树的基本概念 74 4.1.2 二叉树 76 4.2 二叉树的遍历 81 4.2.1 二叉树的遍历方法 81 4.2.2 遍历二叉树的递归算法及遍历示例 82 4.2.3 遍历二叉树的非递归算法 85 4.2.4 二叉树遍历的应用 87 4.3 哈夫曼树 91 4.3.1 哈夫曼树的基本概念及构造方法 91 4.3.2 哈夫曼算法的实现 93