数据的逻辑结构:结构定义中的“关系” 描述的是数据元素之间的逻辑关系,又称为逻辑结构,比如平常教学中所画的内存图,数组等为数据的逻辑结构.
数据的物理结构:数据结构在计算机中的实际表示形式称为数据的物理结构又称为物理存储。
线性结构中又分为顺序表和链表(按物理存储结构划分),顺序表按顺序存储结构,链表按链式存储结构。
按顺序存储结构存储,内存中分配连续一段地址。
队列(FIFO)和栈(FILO)的物理存储结构实现方式既可以是顺序表也可以是链表。
一维数组的物理存储结构是顺序表。下标从0开始。
头指针等于尾指针处于队空状态或队满状态。指针实际位置为指向队列下一个即将存储的区域。
广义表(Lists,又称列表)是一种非线性的数据结构,是线性表的一种推广。即广义表中放松对表元素的原子限制,容许它们具有其自身结构。
结点的度:与下一层的几个节点相关联(下面有几个分支),结点的度就为几。
树的度:所有结点中度数最大的结点即为树的度(最大分支的结点)。
叶子结点:度为0的结点(下面没有分支)。
分支结点:除了叶子结点,其他都是分支结点,包括根结点(有分支的结点)。
内部结点:除了叶子结点和根结点,剩下的就是内部结点(除去根结点的分支结点)。
层次:树从上到下的从1开始计算层次。
根据完全二叉树的特性,可以计算出任意节点n的双亲节点及左右孩子节点的序号,因此完全二叉树的节点可以按照从上到下从左到右的顺序依次存储到一维数组中。非完全二叉树存储时应先将其改造为完全二叉树,以空替代不存在的节点,比较浪费存储空间。
树结构链式存储类似线性结构链式存储,先定义包含数据域和引用域的节点(Node),然后通过引用域存储节点之间的关系。根据二叉树的结构来看,节点Node至少包含数据域(Data),引用域(左孩子LChild、右孩子RChild),为了方便通过孩子节点查找父节点,引用域中可以考虑添加父节点引用(Parent)。
如果完全二叉树根结点下标为0(例如用数组存储完全二叉树),对于任意结点i,左子结点为2*i+1(前提2*i+1
线性表中查找某个元素:从下标为0的元素开始遍历,如果使用排序二叉树,遍历的结点会少很多。
最优二叉树(哈夫曼树)
用于哈夫曼编码,节省存储空间和传输带宽,是无损压缩的方式。
中间结点都是构造出来的,原始数据都是叶子结点。
7的带权路径为7*4=28,3的带权路径为3*5=15
树的带权路径为所有叶子结点的带权路径总和:3*5+5*5+7*4+14*3+。
每个结点的平衡度只能为-1、0、1(结点平衡度 = 左子树深度-右子树深度)
邻接矩阵为了节省存储空间可以只存上三角或者下三角(稀疏矩阵)
数组中存储所有的结点,数组存储的这个结点能到哪个相邻的结点用链表的方式连接起来。
完成某些任务需要先完成某些任务。最小生成树,留下图中权值比较小的边。
直接找最短的边然后连起来。(边数 <= 结点数 - 1)
树的结点为n,则边的最大值为n-1(即树:边数<=节点数-1)