软考-数据结构所有知识点总结-白红宇的个人博客

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

发布日期：2021-05-07 09:30:25 浏览次数：17 分类：精选文章

本文共 1470 字，大约阅读时间需要 4 分钟。

文章目录

数组

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

在这里插入图片描述

稀疏矩阵

所谓的稀疏矩阵，就是当前矩阵中的大量元素是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

平衡度 = 左子树的深度 - 右子树的深度

在这里插入图片描述

在这里插入图片描述

图

在这里插入图片描述

在这里插入图片描述

邻接矩阵

在这里插入图片描述

在这里插入图片描述

邻接表

在这里插入图片描述

在这里插入图片描述

图的遍历

在这里插入图片描述

在这里插入图片描述

拓扑排序

在这里插入图片描述

普利姆算法

依次选出从红点集到蓝点集最短的一条边，不形成环

在这里插入图片描述

克鲁斯卡尔算法

选5条最小边

在这里插入图片描述

上一篇：R语言实现递归（1 2 -1 3 1 -2 -1）

下一篇：R语言生成有标签的三维数组

发表评论

最新留言

路过，博主的博客真漂亮。。

[***.116.15.85]2025年04月06日 05时29分29秒

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

推荐文章

ubuntu学习笔记-常用文件、命令以及作用（hosts、vim、ssh） 2021-05-08

SLAM学习笔记-求解视觉SLAM问题 2021-05-08

还在一个一个手动安装虚拟机吗？Cobbler自动部署装机一键最小化安装打把游戏就好了 2021-05-08

程序员应该知道的97件事 2021-05-08

create-react-app路由的实现原理 2021-05-08

Linux环境变量配置错误导致命令不能使用(杂谈) 2021-05-08

openstack安装（九）网络服务的安装--控制节点 2021-05-08

shell编程(六)语言编码规范之(变量) 2021-05-08

vimscript学习笔记(二)预备知识 2021-05-08

SSM项目中遇到Could not autowire. No beans of ‘XXX‘ type found.错误 2021-05-08

Android数据库 2021-05-08

HTML基础，块级元素/行内元素/行内块元素辨析【2分钟掌握】 2021-05-08

STM8 GPIO模式 2021-05-08

23种设计模式一：单例模式 2021-05-08

Qt中的析构函数 2021-05-08

C语言实现dijkstra(adjacence matrix) 2021-05-08

三层框架+sql server数据库实战教学-徐新帅-专题视频课程 2021-05-08

【单片机开发】智能小车工程（经验总结） 2021-05-08

【单片机开发】基于stm32的掌上游戏机设计 (项目规划) 2021-05-08

C++&&STL 2021-05-08

白红宇的个人博客 - 记录点点滴滴的事 - 您是第 459557629 位访客

访问时间: 2025-04-19 17:29:29 访问IP: 18.218.44.61 Copyright © 2020 - 2025 css8.cn 京ICP备2021015314号-1 手机版