计算机软件技术基础 (2).doc

数据结构(C++版)

计算机软件技术基础(第二版)

第2章基本数据结构及其运算
2.1数据结构的基本概念
2.1.1两个例子

图2.1数据元素存放顺序不同的两个表

2.1.2什么是数据结构
1.数据的逻辑结构
2.数据的存储结构
2.1.3数据结构的图形表示

图2.2一年四季数据结构的图形表示

图2.3家庭成员间辈分关系数据结构的图形表示

图2.4例2.6数据结构的图形表示

图2.5不是线性结构的数据结构特例
2.2线性表及其顺序存储结构
2.2.1线性表及其运算
1.什么是线性表

2.线性表的顺序存储结构

图2.6线性表的顺序存储结构
3.线性表在顺序存储下的插入运算

图2.7线性表在顺序存储结构下的插入例
4.线性表在顺序存储下的删除运算

图2.8线性表在顺序存储结构下的删除例
5.顺序表类
2.2.2栈及其应用
1.什么是栈

图2.9主程序与子程序之间的调用关系

图2.10栈示意图
2.栈的顺序存储及其运算

图2.11栈在顺序存储结构下的运算
3.顺序栈类
4.表达式的计算

图2.12表达式A+B*C-D/E的计算过程5.递归的实现
2.2.3队列及其应用
1.什么是队列

图2.13具有6个元素的队列示意图

图2.14队列示意图
2.循环队列及其运算

图2.15循环队列存储空间示意图

图2.16循环队列运算例
3.循环队列类
4.队列的应用

图2.17通过缓冲区传送数据示意图
2.3线性链表及其运算
2.3.1线性链表的基本概念
1.线性链表

图2.18线性链表的存储空间

图2.19线性链表的一个存储结点

图2.20线性链表的逻辑结构

图2.21线性链表例

图2.22双向链表示意图
2.线性链表类
3.带链的栈

图2.23带链的栈

图2.24可利用栈及其运算
4.带链的队列

图2.25带链的队列及其运算
2.3.2线性链表的基本运算
1.线性链表的插入

图2.26线性链表的插入
2.线性链表的删除

图2.27线性链表的删除
2.3.3循环链表

图2.28循环链表的逻辑状态
2.3.4多项式的表示与运算

图2.29多项式非零系数项的结点结构

图2.30多项式的链式结构
1.多项式链表的生成
2.多项式链表的释放
3.多项式的输出
4.多项式的相加
5.多项式的相乘
2.4数组
2.4.1数组的顺序存储结构
1.二维数组以行为主的顺序存储
2.二维数组以列为主的顺序存储
2.4.2规则矩阵的压缩
1.下三角矩阵的压缩存储

图2.31用一维数组压缩存放下三角矩阵
2.对称矩阵的压缩存储
3.三对角矩阵的压缩存储

图2.32用一维数组压缩存放三对角矩阵
2.4.3一般稀疏矩阵的表示
1.稀疏矩阵的三列二维数组表示

图2.33稀疏矩阵的表示例

图2.34POS与NUM向量例

图2.35C++中稀疏矩阵的表示例

图2.36C++中POS与NUM向量例
2.稀疏矩阵的线性链表表示
3.十字链表

图2.37十字链表的结点结构

图2.38十字链表例
2.5树与二叉树
2.5.1树的基本概念

图2.39一般的树

图2.40学校行政层次结构树

图2.41书的层次结构树

图2.42a*(b+c/d)+e*h-g*f(s,t,x+y)的两种表达式树

图2.43树链表中的结点结构
2.5.2二叉树及其基本性质
1.什么是二叉树

图2.44二叉树例
2.二叉树的基本性质
3.满二叉树与完全二叉树

图2.45满二叉树

图2.46完全二叉树
2.5.3二叉树的遍历
1.前序遍历(DLR)

图2.47二叉树
2.中序遍历(LDR)
3.后序遍历(LRD)
2.5.4二叉树的存储结构
1.二叉链表

图2.48二叉树存储结点的结构

图2.49二叉树的链式存储结构
2.二叉链表类

图2.50给定二叉树
2.5.5穿线二叉树
1.穿线二叉树的概念
2.中序穿线二叉树

图2.51线索二叉树的存储结点的结构

图2.52中序线索二叉树
3.前序穿线二叉树
4.后序穿线二叉树
2.5.6表达式的线性化
1.有序树的二叉树表示

图2.53表达式a*(b+c/d)+e*h-g*f(s,t,x+y)的表达式树与对应的二叉树
2.表达式的线性化
2.6图
2.6.1图的基本概念

图2.54有向图

图2.55无向图
2.6.2图的存储结构
1.关联矩阵
2.求值矩阵

图2.56城市交通图
3.邻接表

图2.57邻接表中的存储结点结构

图2.58有值图

图2.59有值图的邻接表表示
4.邻接多重表

图2.60邻接多重表中的结点结构
2.6.3图的遍历
1.纵向优先搜索法
2.横向优先搜索法
2.6.4图邻接表类
1.由键盘输入生成图