31
2020
12

今天来简单了解一下数据结构

 2020年是个特殊的年,新冠肺炎的疫情改变了好多的命运,也让我们看到了祖国的伟大。国内疫情控制相对稳定后,前两天出去面试碰到笔试问堆和栈的区别。栈我知道,但堆是什么玩意来着?瞬间冒出一身冷汗,数据结构就这么忘完了吗?

  于是乎,回来找度娘了解了一下,瞬间觉得很亲切,堆的感觉又回来了,神奇的是,看到堆的定义后,其实是完全知道的,但完全不知道这个就是堆,两者关联不起来了,完蛋。果然很多东西要经常使用和温习,稍微一松懈就全忘记。

  我自己学了学,顺便也给大家温习一下。

  数据结构是计算机存储、组织数据的方式,数据结构是指相互之间存在一种或多种关系的数据元素的集合。数据结构是带有结构特性的数据元素的集合,主要研究的是数据的逻辑结构和数据的物理结构以及它们之间的关系。数据结构.png

一、 逻辑结构

  逻辑结构与数据在计算机中存储的位置无关,逻辑结构包括:

    1、 集合,元素之间除了同属一个集合的关系外,别无其他关系。

    2、 线性结构,元素之间存在一对一的关系。

    3、 树形结构,元素之间存在一对多的关系。

    4、 图形结构,元素之间存在多对多的关系。

  逻辑结构还可以通过简单分类为线性结构和非线性结构。

  线性结构特点:

    1、 非空

    2、 有且仅有一个开头和结尾

    3、 每个节点最多有一个前驱和一个后继

    举例:线性表、栈、队列、串

  非线性结构特点:

    1、 非空

    2、 一个节点可能存在多个前驱和多个后继

    举例:数组、广义表、树、图

二、 存储结构

    数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。包括:

    1、 顺序存储

    2、 链式存储

    3、 索引存储

    4、 哈希存储

    然而在程序设计中,我们常见的数据结构包括:

    1、 数组(Array)

        数组是一种聚合数据类型,它是将具有相同类型的若干变量有序的组织在一起的集合。数组可以说是最基本的数据结构,在各种编程语言中都有对应。数组可以有一维赫尔多维的形式。

    2、 栈(Stack)

        栈是一种特殊的线性表,栈按照后进先出的逻辑来存储数据,像是一个盒子,先放进去的东西会被沉到最底下,而拿的时候只能从盒子上边一次取出。

    3、 队列(Queue)

        队列也是一种特殊的线性表。但队列与其名字相符,类似于现实生活中的排队买东西,先来的一定先处理,后来的只能排到队尾。

    4、 链表(Linked List)

        链表是一种数据元素按照链式结构进行存储的数据结构,链表中的所有结点都包括数据域和指针域,指针域中包含了下一个元素存放的位置,链表读取时必须按照指针链接的次序。需要注意的是,链表的存储是非连续的。

    5、 树(Tree)

        树是典型的非线性结构,在树结构中,有且仅有一个根节点,该节点没有前驱节点,而其他节点都有且仅有一个前驱节点。

    6、 图(Graph)

        图中,数据结点被称为顶点,而边是顶点的有序偶对。如果两个顶点之间存在一条边,那么就表示这两个顶点具有相邻关系。

    7、 堆(Heap)

        堆是一种特殊的树形数据结构,一般讨论的堆都是二叉堆。堆的特点是根节点的值是所有结点中最小的或最大的,并且根结点的两个子树也是一个堆结构。

    8、 散列表(Hash)

        给定表M,存在函数f(key),对任意给定的关键字key,代入函数后若能得到包含关键字的记录所在的表中的地址,则称表M为哈希表,函数f(key)为哈希函数。

    

    所有数据结构中,我们常用的方法为:增删查改和排序。


原创文章如转载,请注明出处“六一哥笔记

« 上一篇 下一篇 »

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。