计算机软件技术基础 .doc

《计算机软件技术基础 .doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第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、.线性表在顺序存储下的删除运算图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通过缓冲区传送数

3、据示意图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多项式非零系数项的结

4、点结构图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++中稀疏矩阵的

5、表示例图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)

6、图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图的基本概

7、念图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.由键盘输入生成图邻接表2.输出图邻接表3.纵向优先搜索法遍历图4.横向优先搜索法遍历图习题