代码编织梦想

数据结构

1.1 数据结构概述

数据结构是计算机存储、组织数据的方式;通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。数据结构的优良将直接影响着我们程序的性能;常用的数据结构有:数组(Array)、栈(Stack)、队列(Queue)、链表(Linked List)、树(Tree)、图(Graph)、堆(Heap)、散列表(Hash)等;

在这里插入图片描述

1.2 数据结构的分类

1.2.1 排列方式

1)集合

集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系;

在这里插入图片描述

2)线性结构

线性结构:数据结构中的元素存在一对一的相互关系;

在这里插入图片描述

3)树形结构

树形结构:数据结构中的元素存在一对多的相互关系;

在这里插入图片描述

4)图形结构

图形结构:数据结构中的元素存在多对多的相互关系;

在这里插入图片描述

1.2.2 逻辑结构

数据结构按逻辑上划分为线性结构非线性结构

  • 线性结构有且仅有一个开始结点和一个终端结点,并且所有结点都最多只有一个直接前驱和一个直接后继。

典型的线性表有:链表、栈和队列。它们共同的特点就是数据之间的线性关系,除了头结点和尾结点之外,每个结点都有唯一的前驱和唯一的后继,也就是所谓的一对一的关系。

  • 非线性结构:对应于线性结构,非线性结构也就是每个结点可以有不止一个直接前驱和直接后继。常见的非线性结构包括:树、图等。

1.3 数据结构的实现

1.2.1 数组

  • 数组(Array):数组是有序元素的序列,在内存中的分配是连续的,数组会为存储的元素都分配一个下标(索引),此下标是一个自增连续的,访问数组中的元素通过下标进行访问;数组下标从0开始访问;

  • 数组的优点是:查询速度快;

在这里插入图片描述

  • 数组的缺点是:删除增加、删除慢;由于数组为每个元素都分配了索引且索引是自增连续的,因此一但删除或者新增了某个元素时需要调整后面的所有元素的索引;

新增一个元素40到3索引下标位置:

在这里插入图片描述

删除2索引元素:

在这里插入图片描述

总结:数组查询快,增删慢,适用于频繁查询,增删较少的情况;

1.2.2 链表

  • 链表(Linked List):链表是由一系列节点Node(也可称元素)组成,数据元素的逻辑顺序是通过链表的指针地址实现,通常情况下,每个节点包含两个部分,一个用于存储元素的内存地址,名叫数据域,另一个则指向下一个相邻节点地址的指针,名叫指针域;根据链表的指向不同可分为单向链表、双向链表、循环链表等;我们本章介绍的是单向链表,也是所有链表中最常见、最简单的链表;

链表的节点(Node):

在这里插入图片描述

完整的链表:

在这里插入图片描述

  • 链表的优点:新增节点、删除节点快;

在链表中新增一个元素:

在这里插入图片描述

在单向链表中,新增一个元素最多只会影响上一个节点,比在数组中的新增效率要高的多;

在链表中删除一个元素:

在这里插入图片描述

  • 链表的缺点:
    • 1)查询速度慢,查询从头部开始一直查询到尾部,如果元素刚好是在最尾部那么查询效率势必非常低;
    • 2)链表像对于数组多了一个指针域的开销,内存相对占用会比较大;

总结:数据量较小,需要频繁增加,删除操作的场景,查询操作相对较少;

1.2.3 栈

  • 栈(Stack):是一种特殊的线性表,仅能在线性表的一端操作,栈顶允许操作,栈底不允许操作。 栈的特点是:先进后出从栈顶放入元素的操作叫入栈(压栈),取出元素叫出栈(弹栈)。

入栈操作:

在这里插入图片描述

出栈操作:

在这里插入图片描述

栈的特点:先进后出,Java中的栈内存就是一个栈的数据结构,先调用的方法要等到后调用的方法结束才会弹栈(出栈);

1.2.4 队列

  • 队列(Queue):队列与栈一样,也是一种线性表,其限制是仅允许在表的一端进行插入,而在表的另一端进行删除。队列的特点是先进先出,从一端放入元素的操作称为入队,取出元素为出队;

在这里插入图片描述

队列的特点:先进先出;

1.2.5 树

是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:

  • 1)每个节点有0个或多个子节点;
  • 2)没有父节点的节点称为根节点;
  • 3)每一个非根节点有且只有一个父节点;
  • 4)除了根节点外,每个子节点可以分为多个不相交的子树;
  • 5)右子树永远比左子树大,读取顺序从左到右;

树的分类有非常多种,平衡二叉树(AVL)、红黑树RBL(R-B Tree)、B树(B-Tree)、B+树(B+Tree)等,但最早都是由二叉树演变过去的;

二叉树的特点:每个结点最多有两颗子树

在这里插入图片描述

1.2.6 堆

  • 堆(Heap):堆可以看做是一颗用数组实现的二叉树,所以它没有使用父指针或者子指针。堆根据“堆属性”来排序,“堆属性”决定了树中节点的位置。

在这里插入图片描述

堆的特性:如果一个结点的位置为k,则它的父结点的位置为[k/2],而它的两个子结点的位置则分别为2k和2k+1。这样,在不使用指针的情况下,我们也可以通过计算数组的索引在树中上下移动:从arr[k]向上一层,就令k等于k/2,向下一层就令k等于2k或2k+1。

堆的定义如下:n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时,称之为堆;

(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1)满足前者的表达式的成为小顶堆(小根堆),满足后者表达式的为大顶堆(大根堆),很明显我们上面画的堆数据结构是一个大根堆;

大小根堆数据结构图:

在这里插入图片描述

一般来说将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

1.2.7 散列表

  • 散列表(Hash),也叫哈希表,是根据键和值 (key和value) 直接进行访问的数据结构,通过key和value来映射到集合中的一个位置,这样就可以很快找到集合中的对应元素。它利用数组支持按照下标访问的特性,所以散列表其实是数组的一种扩展,由数组演化而来。

散列表首先需要根据key来计算数据存储的位置,也就是数组索引的下标;

  • HashValue=hash(key)

散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里,这种存储空间可以充分利用数组的查找优势来查找元素,所以查找的速度很快。

在这里插入图片描述

在散列表中,左边是个数组,数组的每个成员包括一个指针,指向一个链表的头,当然这个链表可能为空,也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去,也是根据这些特征,找到正确的链表,再从链表中找出这个元素。

1.2.8 图

  • 图(Graph):图是一系列顶点(元素)的集合,这些顶点通过一系列边连接起来组成图这种数据结构。顶点用圆圈表示,边就是这些圆圈之间的连线。顶点之间通过边连接。

图分为有向图和无向图:

  • 有向图:边仅仅连接两个顶点,没有其他含义;
  • 无向图:边不仅连接两个顶点,并且具有方向;

在这里插入图片描述

例如,我们可以把图这种数据结构看做是一张地图:

地图中的城市我们看做是顶点,高铁线路看做是边;很显然,我们的地图是一种无向图,以长沙到上海为例,经过的城市有长沙、南昌、杭州、上海等地;那么从上海也可以按照原有的路线进行返回;

在这里插入图片描述

实现了图这种数据结构之后我们可以在此数据结构上做一些复杂的算法计算,如广度优先搜索算法、深度优先搜索算法等;

  • 广度搜索:搜索到一个顶点时,先将此顶点的所有子顶点全部搜索完毕,再进行下一个子顶点的子顶点搜索;

在这里插入图片描述

例如上图:以武汉为例进行广度搜索,

1)首先搜索合肥、南昌、长沙等城市;

2)通过合肥搜索到南京;

3)再通过南昌搜索到杭州、福州,

4)最终通过南京搜索到上海;完成图的遍历搜索;

不通过南京搜索到杭州是因为已经通过南昌搜索到杭州了,不需要再次搜索;

  • 深度搜索:搜索到一个顶点时,先将此顶点某个子顶点搜索到底部(子顶点的子顶点的子顶点…),然后回到上一级,继续搜索第二个子顶点一直搜索到底部;

在这里插入图片描述

例如上图:以武汉为例进行深度搜索,

1)首先搜索合肥、南京、上海等城市;

2)回到武汉,进行第二子顶点的搜索,搜索南昌、杭州等地;

3)回到南昌,搜索福州;

4)回到武汉,搜索长沙;

图是一种比较复杂的数据结构,在存储数据上有着比较复杂和高效的算法,分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。我们本次了解到这里即可;

记得点赞!!!

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Bb15070047748/article/details/119208588

数据结构(全)-爱代码爱编程

数据结构        数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下,精心选择的数据结构可以带来更高的运行或者存储效率。 数据结构往往同高效的检索算法和索引技术有关。 名词定义        数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间

java 中几种常用数据结构-爱代码爱编程

JAVA中常用的数据结构(java.util. 中) java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。其主要的关系(继承关系)有:  (----详细参见java api文档!) Collection---->Collectio

数据结构-爱代码爱编程

数据结构 一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。 数据:所有能被输入到计算机中,且能被计算机处理的符号的集合。是计算机操作的对象的总称。数据元素:数据(集合)中的一个“个体”,数据及结构中讨论的基本单位数据项:数据的不可分割的最小单

数据结构之结构类型_栖息的梧桐树的博客-爱代码爱编程

       偶然看到了专门用来处理关系结构的图数据库,根据其介绍了解到其原理是数据结构的图结构。而令人尴尬的是,说道图结构的特点,算法,我竟然完全没有了一点印象。大学学习的这门课程已经还给了老师。书到用时方恨少啊。当时就有一点回头复习数据结构的想法。后来碰到了广度优先算法,深度优先算法,都是在树结构的基础上的算法。坚定了我回头复习数据结构的想法。  

什么是数据结构-爱代码爱编程

** - 什么是数据结构 ** 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一个目的,即为了方便后期对数据的再利用,就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的加和值,无

数据结构有哪些,常用数据结构详解-爱代码爱编程

通过上节我们知道,数据结构是学习数据存储方式的一门学科,那么,数据存储方式有哪几种呢?本节将对数据结构的学习内容做一个简要的总结。 数据结构大致包含以下几种存储结构: 线性表,还可细分为顺序表、链表、栈和队列; 树结构,包

数据结构图的知识点大全总结(包括各类常见算法都有本人自己的独特分析)_kkkgoing的博客-爱代码爱编程_数据结构图知识点总结

一、图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:G(V,E),其G表示一个图,V是图G中顶点的集合,E是图G中边的集合。 (1)在线性表中我们把数据元素叫元素,树中将数据元素叫结点,在图数据元素称之为顶点(Vertex)。 (2)线性表中可以没有数据元素,称之为空表。树中可以没有结点称之为空树。对于图,图中不能没有顶点。强调

八大数据结构-爱代码爱编程

八大数据结构 数据结构分类 1、数组 2、栈 3、队列 4、链表 5、树 6、散列表 7、堆 8、图 1、数组 数组是可以再内存中连续存储多个元素的结构,在内存中的分配也是连续的,数组中的元素通过数组下标进行访问,数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。优点: 1、按照索引查询元素速度快 2、按照索引遍历数组方便 缺点

几种常见的数据结构,你知道哪些?-爱代码爱编程

数据结构在实际应用中非常常见,现在各种算法基本都牵涉到数据结构,因此,掌握数据结构算是软件工程师的必备技能。 一、什么是数据结构 数据结构,直白地理解,就是研究数据的存储方式。 我们知道,数据存储只有一个目的,即为了方便后期对数据的再利用,就如同我们使用数组存储 {1,2,3,4,5} 是为了后期取得它们的加和值,无缘由的数据存储行为是对存储空间的不

九大常见数据结构-爱代码爱编程

数据结构想必大家都不会陌生,对于一个成熟的程序员而言,熟悉和掌握数据结构和算法也是基本功之一。数据结构本身其实不过是数据按照特点关系进行存储或者组织的集合,特殊的结构在不同的应用场景中往往会带来不一样的处理效率。 常用的数据结构可根据数据访问的特点分为线性结构和非线性结构。线性结构包括常见的链表、栈、队列等,非线性结构包括树、图等。数据结构种类繁多,本文

【数据结构】八种常见数据结构介绍-爱代码爱编程

相似文章推荐: 算法简介七大查找算法的理解与实现路径规划中的Dijkstra(狄克斯特拉)与A星算法八大经典排序算法的理解、动图演示和C++方法实现 零. 总览 数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八

java的程序结构有哪几种_java数据结构有哪些?-爱代码爱编程

Java中有几种常用的数据结构,主要分为Collection和map两个主要接口(接口只提供方法,并不提供实现),而程序中最终使用的数据结构是继承自这些接口的数据结构类。 Collection---->Collections Map----->SortedMap------>TreeMap          Map----

数据结构及算法详解-爱代码爱编程

目录 1 算法的衡量标准2 数据结构3 排序算法3.1 排序3.2 算法稳定性3.3 排序算法4 二分查找4.1 二分查找4.2 代码实现4.2.1 递归版本4.2.2 递归优化版本4.2.3 非递归版本4.2.4 二分查找-位置4.2.5 第一个位置4.2.6 最后一个位置5 非线性数据结构-树 1 算法的衡量标准 1.1 算法 解决问题

c语言八大数据结构有哪些,C语言中都有哪些常见的数据结构你都知道几个??...-爱代码爱编程

上次在面试时被面试官问到学了哪些数据结构,那时简单答了栈、队列/(ㄒoㄒ)/~~其它就都想不起来了,今天有空整理了一下几种常见的数据结构,原来我们学过的数据结构有这么多~ 首先,先来回顾下C语言中常见的基本数据类型吧O(∩_∩)O C语言的基本数据类型有:整型int,浮点型float,字符型char等等 添加描述 那么,究竟什么是数据结构呢