专栏首页hui各数据结构的基本概念和术语汇总

各数据结构的基本概念和术语汇总

各数据结构的基本概念和术语汇总
  • 绪论
    • 什么是数据结构?
    • 基本概念和术语
    • 算法和算法分析
  • 线性结构
    • 线性表
    • 线性表的顺序表示
    • 线性表的链式表示
    • 线性表的顺序、链式存储结构比较
    • 栈和队列
  • 非线性结构
    • 树和二叉树
    • 图的定义和基本术语

绪论

什么是数据结构?

一般来说,用计算机解决一个具体问题时,大致需要经过下列几个步骤:

​ 1️⃣ 首先要从具体问题抽象出一个适当的数学模型

​ 2️⃣ 然后设计一个解决此数学模型的算法

​ 3️⃣ 最后编出程序,进行测试、调整 直至得到最终解答

自然语言 ——> 抽象数学模型 ——> 程序语言 ——> 运算

基本概念和术语

算法和算法分析

线性结构

线性表

  • 线性表(Linear List)是最常用且最简单的一种数据结构。一个线性是 n 个数据元素的有限序列。
  • 线性表中元素可以是各种各样的,同一线性表中元素必定具有相同的特性,即属同一数据对象,相邻数据元素之间存在着序偶关系

线性表的顺序表示

线性表的顺序表示指的是 用一组地址连续的存储单元 依次存储线性表的数据元素。

线性表中任一数据元素都可以 随机存取 ,所以 线性表的顺序存储结构是一种随机存取的存储结构

线性表的链式表示

n 个结点链接成一个链表,即为线性表的链式存储结构。

由于此链表的每一个结点中只包含一个指针域,故又称 线性链表单链表

单链表 中,取得第 i 个数据元素必须从头指针出发寻找,因此 单链表是一种非随机存取的存储结构

循环链表(Circular Linked List) 是另一种形式的链式存储结构。它的特点是表中最后一个结点的指正域指向头结点整个链表形成一个环

循环链表中任一结点出发均可找到表中其他结点。

双向链表(Double Linked List) 的结点有两个指针域,其一指向直接后继,另一指向直接前驱。

双向链表特点就是更方便找前驱结点。

线性表的顺序、链式存储结构比较

栈和队列

栈和队列也是线性表, 其特殊性在于栈和队列的基本操作是线性表的子集,他们是操作受限的线性表

非线性结构

树和二叉树

图的定义和基本术语

G = (V,E)
  • V:顶点(数据元素)的 有穷非空 集合
  • E:边的 有穷 集合

无向图:每条边都是无方向的

有向图:每条边都是有方向的

完全图:任意两个点都有一条边相连

稀疏图: 有很少边或弧的图

稠密图:有较多边或弧的图

:边、弧带权的图

邻接:有边、弧相连的两个顶点之间的关系

路径:接续的边构成的顶点序列。

路径长度:路径上边或弧的数目 / 权值之和。

回路(环):第一个顶点和最后一个顶点相同的路径。

简单路径:除路径起点和终点可以相同外,其余顶点均不相同的路径。

简单回路(简单环):除路径起点和终点相同外,其余顶点均不相同的路径。

连通图(强连通图)

在无(有)向图

G=( V, {E} )

中,若对任何两个顶点 v、u 都存在从 v 到 u 的路径,

则称 G 是 连通图(强连通图)。

权与网

  • 图中边或弧所具有的相关数称为 。表明从一个顶点到另一一个顶点的距离或耗费。
  • 带权的图称为

子图

连通分量(强连通分量)

  • 无向图 G 的 极大连通子图 称为 G 的 连通分量
  • 极大连通子图意思是:该子图是G连通子图,将G的任何不在该子图中的顶点加入,子图不再通

有向图 G 的 极大强连通子图 称为 G 的 强连通分量

极大强连通子图意思是:

该子图是 G 的强连通子图,将 D 的任何不在该子图中的顶点加入,子图不再是强连通的。

极小连通子图:该子图是 G 的连通子图,在该子图中删除任何一条边,子图不再连通。

生成树:包含无向图 G 所有顶点的极小连通子图。

生成森林:对非连通图,由各个连通分量的生成树的集合。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 - 链表

    顺序表的构建需要预先知道数据大小来申请连续的存储空间,而在进行扩充(插入、删除)时又需要进行数据的搬迁,所以使用起来并不是很灵活。

    忆想不到的晖
  • 数据结构 - 顺序表

    在程序中,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等。一组数据中包含的元素个数可能发生...

    忆想不到的晖
  • 单链表的头尾插法详解

    head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = NULL;

    忆想不到的晖
  • 谈谈我对投影的理解

    Peter Lu
  • 地图投影

    我们的地球是圆的,而我们的纸张是平面。为了将地球绘制在平面纸张上,我们需要将地球表面投影到平面上。地图投影的实质是建立空间地理坐标和平面直角坐标关系的过程。

    卡尔曼和玻尔兹曼谁曼
  • 漫画:Dijkstra 算法的优化

    在上一篇漫画中,小灰介绍了单源最短路径算法 Dijkstra,没看过的小伙伴可以看下:

    小灰
  • 50万的高级开发工程师带你做python文字识别系统开发

    通过开发一个可识别图片中文字的web应用,给大家展现python web开发的魅力

    云飞
  • 数据结构

    原因:2018年4月7日 星期六 说明:毕业近2年,系统的整理一下相关数据结构之所学,有基础,有拓展。

    ZHaos
  • 谨慎处理 Service Worker 的更新

    Service Worker 以其 异步安装 和 持续运行 两个特点,决定了针对它的更新操作必须非常谨慎小心。因为它具有拦截并处理网络请求的能力,因此必须做到网...

    ConardLi
  • Winforms 可能遇到的 1000 个问题 去掉最大化和最小化按钮使用系统的图标禁止用户修改窗口大小隐藏标题栏的图标

    如果需要去掉最大化和最小化按钮,只需要设置 MinimizeBox 或 MaximizeBox 为 false 请看下面代码

    林德熙

扫码关注云+社区

领取腾讯云代金券