软考-数据结构所有知识点总结

it2026-04-17 0

文章目录

数组稀疏矩阵线性表顺序表链表单链表循环链表双向链表顺序存储和链式存储的区别队列循环队列栈广义表树与二叉树二叉树满二叉树完全二叉树二叉树特性二叉树的遍历层次遍历前序遍历中序遍历后序遍历反向构造二叉树树转二叉树查找二叉树最优二叉树（哈夫曼数）线索二叉树平衡二叉树图邻接矩阵邻接表图的遍历拓扑排序普利姆算法克鲁斯卡尔算法

数组

是个程序员就不用多啰嗦了

稀疏矩阵

所谓的稀疏矩阵，就是当前矩阵中的大量元素是0或者是大量元素是同一个值，这时候我们只用存储一少部分不同的值。节省了空间

例题用代入法代入排除选项

线性表

顺序表

开辟连续的存储空间，采用一维数组的形式存

链表

开辟离散的空间，每一个节点分为数据域和指针域

单链表

删除节点 p->next = q->next

插入节点

s-next = p->next; p->next =s;

单链表有头结点的有优点

有头节点可以让单链表所有节点的操作方式一致，

循环链表

双向链表

顺序存储和链式存储的区别

队列

循环队列

栈

广义表

树与二叉树

节点的度：节点所拥有的孩子节点数树的度：在一个树所有节点中，节点的度最大的值就是树的度叶子节点：度为0的节点内部节点：即非叶子节点，也非根节点分支节点：：度不为0的节点层次：上面的数是4层

二叉树

满二叉树

每个节点的子节点的度小于等于2，整棵树，没有缺失的部分，非常完整

完全二叉树

相对于慢二叉树只会缺失右下角的节点

二叉树特性

在二叉树的第i层上最多有2的（i-1）次方个节点在深度为K的二叉树最多有2的k次方减1个节点对任何一颗二叉树，如果其叶子节点数为n,度为2的节点数为n2,则n=n2+1如果对一颗有n个节点的完全二叉树的节点按程序编号（从第一层到最后一层，每层从左到右),则对任一节点i（1<=i<=n）有：如果i=1,则节点无父节点，如果i>,则父节点为i/2向下取整，如果2i>n,则节点i为叶子节点，无左子节点，否则左子节点是2i,如果2i+1>n,则节点i无右子节点，否则，柚子节点是节点2i+1

二叉树的遍历

层次遍历

按第一层到最后一层的遍历一遍， 1 2 3 4 5 6 7 8（上图层次遍历后的顺序）

前序遍历

前序遍历指先访问根节点，再访问左子树和右子树节点 1 2 4 5 7 8 3 6

中序遍历

先访问左子树节点，再访问根节点，最后访问右子树节点 4 2 7 8 5 1 3 6

后序遍历

先访问左子树节点，再访问右子树节点，最后访问根节点 4 7 8 5 2 6 3 1

反向构造二叉树

由前序遍历的序列得到A必定是根节点，再由中序遍历得： B和H的位置轻松得到如下图：

树转二叉树

树转二叉树的主要特征：

一个树的孩子节点都会成为它的左子树节点一个树的兄弟节点都会成为它的右子树节点

查找二叉树

对于每棵树的根节点的左子树节点要比根节点小，右子树节点要比根节点大，叫做查找二叉树，或者排序二叉树，能够极大的提高查找的效率

最优二叉树（哈夫曼数）

将现有节点组成的带权路径最小的树

数的路径长度，就是层数减一权值：节点上的标数求所有叶子节点的带权路径长度的和，就是哈夫曼树的带权路径长度

线索二叉树

二叉树的会空闲大量的指针，可以利用起来，方便遍历。产生了线索二叉树

线索二叉树的左线索指针直线前序遍历循序的前驱节点，右线索指针指向他的后驱节点。

平衡二叉树

上面说过的查找二叉树，在统一序列下可能会产生不同形状的二叉树：如下面两棵同一序列的二叉树，右边的树更加饱满，左右更加平衡，所以的查找效率较高。这里就产生了平衡二叉树的概念：任意节点的左右子树深度相差不超过1.每个节点的平衡度只能为-1,0,1