自考本科数据结构02331
2021-05-27 21:35:12 6 举报AI智能生成
自考本科数据结构02331
作者其他创作
大纲/内容
数据结构
第1章 概论
第2章 线性表
逻辑定义
由n个数据元素组成的有限序列。数据元素的个数n为表的长度。当n为0时称为空表
逻辑特征
有且仅有一个称为开始元素的结点，它没有前趋，仅有一个直接后继元素
有且仅有一个称为终端元素的结点，它没有后继，仅有一个直接前趋
其余元素称为内部元素，它们都有且仅有一个直接前趋和一个直接后继
线性表的顺序存储结构
特点
元素在表中的相邻关系，在计算机内也存在着相邻的关系
存储结构
基本运算
插入运算
时间复杂度O（n）
平均次数n/2
删除运算
平均次数(n-1)/2
其他运算
线性表逆置
查找线性表最大值和最小值
线性表的链式存储结构
单链表
带头结点
不带头结点
建立单链表
头插法
尾插法
查找运算
按结点序号查找
按结点值查找
拆分链表
合并链表
循环链表
头结点
建立链表
尾指针
双向链表
单向转双向
顺序表和链表的比较
时间
存取元素
顺序表随机存取表中任一元素，按位置访问元素时间复杂度为O(1)
插入删除
平均移动表中一般元素，时间复杂度为O（n）
不需要移动元素，确定位置后插入删除操作时间复杂度为O（1）
空间
存储空间
顺序表预算分配，可能会闲置空间或者溢出
链表动态分配，不会出现闲置空间或者溢出
存储密度
顺序表不需要为逻辑关系增加额外开销，存储密度为1
链表需要额外的指针来体现出逻辑关系，存储密度小于1
适用情况
顺序表适用于表长变化不大且事先能确认范围，经常按序号查找运算，少插入删除操作的情况
链表适合表长度变化较大，频繁的插入删除操作
第3章 栈与队列
栈
定义
限定在表的一端进行插入和删除运算的线性表，通常将插入、删除的一端称为栈顶，另一端称为栈底部。不含元素的空表称为空栈
插入
删除
初始化栈
判栈空
取栈顶元素
置空栈
判栈满
进栈
退栈
顺序栈
链式栈
队列
操作受限的线性表，它只允许在表的一端进行元素插入，而在另一端进行元素删除。允许插入的一端称为队尾，允许删除的一端称为对头。
置空队列
入队列
出队列
取队头
判对空
判队满
顺序队列
循环队列
栈队列
应用实例
中缀表达式转后缀表达式
后缀表达式计算
第4章 多维数组和广义表
多维数组和运算
存储方式
按行优先顺序存储
按列优先顺序存储
转置矩阵
矩阵的压缩存储
特殊矩阵
对称矩阵
三角矩阵
稀疏矩阵
三元组表
建立顺序存储稀疏矩阵的三元组表
三元组稀疏矩阵转置
广义表
取表头
取表尾
()和(())的区别
基本运算的实现
建立广义表的存储结构
输出广义表
广义表的查找
长度和深度
第5章 树与二叉树
树的基本概念
树是n(n>=0)个结点的有限集T
有且仅有一个特定的称为根的结点
当n>1时，其余的节点可分为m(m>0)个不互相交的有限集，每个集合本身又是一棵树，并成为根的子树
表示法
树形表示
嵌套集合表示
凹形表表示
基本术语
结点
一个结点拥有的子树数称为该结点的度
度数为零的节点被称为叶子节点或终端节点
树中结点的层次是从根开始算起
树
一棵树中结点最大度数称为该树的度
树中结点的最大层次称为树的深度或高度
森林
m(m >=0)棵互不相交的树的集合
二叉树
每个结点最多只有两棵子树
它或者是空值，或者是由一个根结点及两棵互不相交的分别称为这个根的左子树和右子树的二叉树组成
五种形态
空二叉树
仅有根节点
右子树为空
左子树为空
左右子树非空
性质
在二叉树的第i层上至多有2^i-1个结点（i>=1）
深度为k的二叉树至多有2^k-1个结点(k >= 1)
对任何一颗二叉树T，若其终端结点数为n0，度数为2的结点数为n2，则n0 = n2+1
具有n个结点的完全二叉树的深度为logn向下取整+1或者log(n+1)向上取整
特殊情形的二叉树
满二叉树
完全二叉树
顺序存储结构
编号为i的节点qi
若2i+1<n，则qi的左孩子结点编号为2i+1；否则无左孩子
若2i+2<n，则qi的右孩子结点编号为2i+2；否则无右孩子
完全二叉树而言，顺序存储结构既简单又节省存储空间
链式存储结构
运算
二叉树生成
按广义表表示二叉树结构生成二叉链表
按完全二叉树的层次顺序依次输入结点信息建立二叉链表
二叉树遍历
递归遍历
前序遍历
中序遍历
后序遍历
非递归遍历
栈的中序遍历
指针数组的中序遍历
栈的前序遍历
按层遍历
应用
根据已知的前序遍历和中序遍历或已知的后序遍历和中序遍历推出树的结构
二叉树链式存储的深度
二叉树链式存储的按值查找
二叉树链式存储的找结点的层次
线索二叉树
每个结点中增加两个指针域来存放遍历时等到的前趋和后继信息。指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索二叉链表，相应的二叉树称为想线索二叉树
二叉树的线索化
如果根结点的左孩子指针域为空，则将左线索标志域置1，同时把前趋结点的指针赋给根结点的左指针域，即给根结点加左线索
如果根结点的右孩子指针域为空，则将右线索标志域置1，同时把后继结点的指针赋给根结点的右指针域，即给根结点加右线索
将根结点指针赋给存在前趋结点指针的变量，以便当访问下一个节点时，此跟结点作为前趋结点
查找某结点的后继结点
线索二叉树的遍历
树和森林
双亲表示法
孩子链表法
孩子兄弟表示法
树、森林与二叉树的转换
树、森林到二叉树的转换
二叉树到树、森林的转换
树和森林的遍历
哈夫曼树及其应用
是一类带权路径长度最短的树
概念
两个节点构成的路径上的分支(边)数目成为路径长度
树根到树中每个结点的路径长度之和称为树的路径长度
结点赋上一个具有某种意义的实数，此实数为该节点的权
从树根节点到某结点之间的路径长度与该节点上权的乘积称为该节点的带权路径长度
哈夫曼算法
在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的附加根结点的权值为左、右子树上根结点的权值之和
从F中删除这两棵树，同时把新树加入到F中
重复上述两个步骤，直到F中只有一棵树为止
生成哈夫曼树
哈夫曼编码
第6章 图
V（G）表示图G的顶点集合
E（G）表示图G的边集合
有向图
若每条边都是有方向的，则称该图为有向图
有向边又称为弧，边的起点称为弧尾，边的终点称为弧头
有向图的边的取值范围是0~n(n-1)，具有n(n-1)条边的有向图称为有向完全图
顶点v的度分为入度ID(v)和出度OD(v)。入度是以该顶点为终点的入边数目，出度是以该顶点为起点的出边数目，该顶点的度等于入度和出度之和
无向图
边均是顶点的无序对，通常用圆括号表示
无向图的边的取值范围是0~n(n-1)/2，具有n(n-1)/2条边的无向图成为无向完全图
顶点v的度定义为以该顶点为一个端点的边的数目，记为D(v)
度数和边数的关系
不管是有向图或是无向图，边数 e = (D(v1)+D(v2)+D(v3)+···+D(vi))/2
简单路径
顶点均不相同的路径
回路、环
一条简单路径上的起点和终点为同一个顶点
简单回路
一条路径上除了起点和终点可以为同一个顶点外，其余均不相同
路径长度
一条路径上经过的边的数目或权值之和
权
边上的数值，边上带权的图称为带权图，带权的连通图称为网络
连通
顶点w和顶点v之间存在路径
连通图
图中任意两个顶点都是连通的
连通分量
非连通图中的每个连通分量
强连通图
有向图中，任意两个顶点都连通
领接矩阵
有向图矩阵中1的个数就是图的边的数量
无向图的邻接矩阵是对称的
时间复杂度O(n^2)
领接表
找出度容易，入度困难
时间复杂度O(n+e)
逆邻接表
图的遍历
深度优先遍历 DFS
广度优先遍历 BFS
图的生成树和最小生成树
深度优先生成树
广度优先生成树
最小生成树
普里姆(Prim)算法
克鲁斯卡尔(Kruskal)算法
最短路径
拓扑排序
术语
顶点表示活动
边表示活动间先后关系的有向无环图(DAG)称为顶点活动网，简称AOV网
AOV网不允许有回路
拓扑序列
所有活动可排成一个线性序列，使得每个活动的所有前趋活动都排在该活动的前面，此序列就是拓扑序列
由AOV网构造拓扑序列的过程称为拓扑排序
第7章 排序
插入排序
基本思想
每次讲一个待排序的记录按其关键字的大小插入到前面已排好序的适当位置，使数列依然有序，直到全部记录插入完为止
直接插入排序
希尔排序
有待加强
二叉树的特性
具有n个节点的完全二叉树的深度为logn向下取整+1或log(n+1)向上取整
排序算法的时间复杂程度与空间复杂度
二分查找算法
哈弗曼编码
图的计算公式
二维数组的计算公式
树的计算公式
排序
0 条评论
下一页
