计算机有哪些数据结构(@计算机专业同学，你必须知道的八大数据结构！)

高考留学教育网为您带来《计算机有哪些数据结构(@计算机专业同学，你必须知道的八大数据结构！)》，本文围绕计算机有哪些数据结构展开分析，讲述了关于计算机有哪些数据结构相关的内容，希望你能在本文得到想要的信息！

@计算机专业同学，你必须知道的八大数据结构！

美国心理学家曾提出过一个六度分离理论。它指的是“你和任何一个陌生人之间所间隔的人不会超过五个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”根据这个理论，你和世界上的任何一个人之间只隔着五个人，不管对方在哪个国家，属哪类人种，是哪种肤色。

可以看出，我们生活在一个复杂的像蜘蛛网一样的世界，我们每个人并不是单独的个体，而是和其他人有联系的。在当今这个大数据时代，数据即财富。所以我们需要用计算机存储、分析大量的数据，提取出对我们来说有价值的数据。

我们每个人每天都在产生数据，例如我们在APP里聊天、在网络商城购物都会产生大量的数据。正如人和人之间有很多联系一样，数据和数据之间也会有许多联系，没有哪个数据是单独存在的，即使有，这种数据也没有利用价值，我们没有必要去分析，研究它。

数据结构恰恰就是用来囊括数据以及数据与之间关系的一种集合。数据结构的起源是研究如何将相关联的数据存储到计算机中，并为后续分析提供有效的数据源。好的数据结构，能让我们做起事来事半功倍。精心选择的数据结构可以带来更高的计算速度和存储效率。

什么是数据结构？

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

程序=数据结构+算法，数据结构属于静态的部分，算法的调用为动态部分

为什么要学习数据结构？

数据结构是所有计算机专业的同学必学的一门课程。

数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以高效的获取数据或者修改数据。

计算机专业的学生都开设过数据结构课程，它是计算机学科知识结构的核心和技术体系的基石。数据结构作为计算机专业的专业基础课程，是计算机考研的必考科目之一，如果有打算报考计算机专业的研究生，这门数据结构你是必须要学好它的，同时，工作以后的同学，会有想去报考计算机 软考 、计算机 等级考试的，数据结构也是必考的内容之一，科学技术在飞速发展，但是作为基石的科学技术没有动摇，由于近年来算法工程师的高薪火爆，使得数据结构的重视程序空前高涨，总而言之，既然我们已经与计算机接轨就必须掌握好它。

常见的数据结构：

• 1.数组
• 2.栈
• 3.队列
• 4.链表
• 5.图
• 6.树
• 7.前缀树
• 8.哈希表

1．数组

数组(Array)大概是最简单，也是应用最广泛的数据结构了。比如栈，队列等其他数据结构也都是由数组演变而来。下图是包含四个元素（1、2、3、4）的简单数组。

每一个数组元素都关联一个正数值，我们称它为下标或者索引(index)。大多数编程语言将初始索引定义为0。

根据维度区分，有 2 种不同的数组：

· 一维数组(如上图所示)

· 多维数组(数组的元素为数组)

数组的基本操作

· Insert - 在某个索引处插入元素

· Get - 读取某个索引处的元素

· Delete - 删除某个索引处的元素

· Size - 获取数组的长度

2. 栈

Ctrl+Z，这是著名的撤销操作，在大部分编辑类软件中都支持这一操作。但你想过它是怎么实现的吗？解决问题的思路就是应用状态（有限个）保存到内存中，将最后的状态排在最先的位置。就比如常用的图像处理软件Photoshop中最大支持1000步的历史纪录。这时我们使用栈（stack）实现这个功能就非常方便了。

栈中的元素采用 LIFO (Last In First Out)，即后进先出。

举个例子：先放进桶里的大米总是最后才盛出来使用，这就是先进后出。

下图的栈有 3 个元素，3 在最上面，因此它会被第一个移除：

栈的基本操作

· Push — 在栈的最上方插入元素

· Pop — 返回栈最上方的元素，并将其删除

· isEmpty — 查询栈是否为空

· Top — 返回栈最上方的元素，并不删除

3. 队列

队列(Queue)与栈类似，都是顺序存储的数据结构。它们的区别在于栈采用 LIFO 方式即后进先出，而队列FIFO，即先进先出。

举个例子：排队买票，先进入队伍的先拿到票然后离开队伍。后来到的则排到队伍的队尾，即先进先出。

下图展示了一个队列，1 是最上面的元素，它会被第一个移除：

队列的基本操作

· Enqueue — 在队列末尾插入元素

· Dequeue — 将队列第一个元素删除

· isEmpty — 查询队列是否为空

· Top — 返回队列的第一个元素

4. 链表

链表(Linked List)也是另一个重要的数据结构，乍一看可能像数组，但它们在内存分配方式、内部结构和插入删除操作方式上均有所不同。

链表是一系列节点组成的链，每一个节点保存了数据以及指向后续节点的指针。链表还包含一个头指针，它指向链表的第一个节点，如果链表为空，则头指针指向null或空。

链表可以用来实现文件系统、哈希表和邻接表。

下图展示了一个链表，它有 3 个节点：

链表分为 2 种：

· 单向链表

· 双向链表

链表的基本操作

· InsertAtEnd — 在链表结尾插入元素

· InsertAtHead — 在链表开头插入元素

· Delete — 删除链表的指定元素

· DeleteAtHead — 删除链表第一个元素

· Search — 在链表中查询指定元素

· isEmpty — 查询链表是否为空

5. 图

图(graph)是由多个网络形式相互连接的节点(vertex)构成。(x, y)表示一条边(edge)，它表示节点 x 与 y 相连。边可以包含权值(weight/cost)，即从顶点x到y所需的成本。

图分为两种:

· 无向图

· 有向图

在编程语言中，图有可能有以下两种形式表示：

· 邻接矩阵(Adjacency Matrix)

· 邻接表(Adjacency List)

遍历图的两种算法

· 广度优先搜索(Breadth First Search)

· 深度优先搜索(Depth First Search)

6. 树

树(Tree)是一种层级式的数据结构，由节点和连接节点的边组成。树是一种特殊的图，它与图最大的区别是不存在循环。

树被广泛应用在人工智能和一些复杂算法，它能提供高效的存储结构。

下图是一个简单的树以及与树相关的术语：

树有很多分类：

· N 叉树(N-ary Tree)

· 平衡树(Balanced Tree)

· 二叉树(Binary Tree)

· 二叉查找树(Binary Search Tree)

· 平衡二叉树(AVL Tree)

· 红黑树(Red Black Tree)

· 2-3 树(2–3 Tree)

其中，二叉树和二叉查找树是最常用的树。

7. 前缀树

前缀树(Prefix Trees 或者 Trie)也可以称之为“字典树”，与树类似，在处理字符串相关的问题时非常有效。它可以实现快速检索，常用来实现词典中的单词查询，也可以用于搜索引擎的自动补全甚至被用于IP的路由。

下图展示了在前缀树中如何存储“top”, “thus”和“their”三个单词：

单词是按照字母从上往下存储，“p”, “s”和“r”节点分别表示“top”, “thus”和“their”的单词结尾。

8. 哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数，存放记录的数组叫做哈希表。

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

哈希表通常由数组实现。

哈希表的性能取决于 3 个因素：

· 哈希函数

· 哈希表的大小

· 哈希冲突处理方式

下图展示了有数组实现的哈希表，数组的下标即为哈希值，由哈希函数计算，作为哈希表的键(key)，而数组中保存的数据即为值(value)：

以上就是八种常见的数据结构，欢迎评论区留言~

《计算机有哪些数据结构(@计算机专业同学，你必须知道的八大数据结构！)》来自网络，计算机有哪些数据结构的观点不代表本网站，仅作参考。

声明：本文内容均来自互联网，版权属于原作者，如有侵权，联系站长。本文网址：https://www.qmlxjy.com/lxzx/28516.html，文章标题：计算机有哪些数据结构(@计算机专业同学，你必须知道的八大数据结构！)