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

美国社会学家曾提出过两个七度分立方法论。它指的是“你和任何人两个他们间所间距的人不会超过四个，换句话说，最多通过四个人你就能够认识任何人两个他们。”根据那个方法论，你和现今世界上的任何人两个人间只隔着四个人，不管对方在别的国家，属这三类白种人，是何种发色。

能窥见，他们生活在两个复杂的像蜂巢那样的现今世界，他们每一人并不是原则上的子代，而是和他们有联络的。在现今那个大统计数据时代，统计数据即社会财富。所以他们需要用计算机系统储存、预测大批的统计数据，抽取出与他们来说有用的统计数据。

他们每一人每天都在造成统计数据，例如他们在APP里闲聊、在实体店网购单厢造成大批的统计数据。正像人和人间有很多联络那样，统计数据和统计数据间也会有许多联络，没有别的统计数据是原则上存有的，即使有，这种统计数据也没利用价值，他们没必要去预测，科学研究它。

计算机系统流程不可否认就是用以涵盖统计数据以及统计数据与间亲密关系的一类子集。计算机系统流程的起源地是科学研究如何将密切相关的统计数据储存到计算机系统中，并为先期预测提供有效的统计管理工具。好的计算机系统流程，能让他们抓起蠢事四两拨千斤。精心设计优先选择的计算机系统流程能增添更高的反应速度和储存工作效率。

什么是计算机系统流程？

“计算机系统流程是计算机系统储存、组织统计数据的方式。计算机系统流程是指相互间存有一种或多种某一亲密关系的统计数据原素的子集。通常情况下，精心设计优先选择的计算机系统流程能增添更高的运行或者储存工作效率。计算机系统流程往往同高效率的检索演算法和检索控制技术有关。”

流程=计算机系统流程+演算法，计算机系统流程属于静态的部份，演算法的初始化为静态部份

为什么要学习计算机系统流程？

计算机系统流程是所有计算机系统系的老师recommend的两门专业课程。

计算机系统系的学生都开办过计算机系统流程课程，它是计算机系统应试者结构的核心和控制技术体系的终极目标。计算机系统流程作为计算机系统系的专业基础专业课程，是计算机系统备考的必修专业课程之一，如果有打算报读计算机系统系的科学博士生，尖萼计算机系统流程你是要要努力学习它的，同时，工作以后的同学，会有想去报读计算机系统 软考 、计算机系统 等级考试的，计算机系统流程也是必修的内容之一，科学控制技术在飞速发展，但是作为终极目标的科学控制技术没动摇，由于近年来演算法工程师的高薪火爆，使得计算机系统流程的重视流程空前高涨，总而言之，既然他们已经与计算机系统接轨就要掌握好它。

常见的计算机系统流程：

1．数组

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

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

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

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

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

数组的基本操作

· Insert – 在某个检索处插入原素

· Get – 读取某个检索处的原素

· Delete – 删除某个检索处的原素

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)：

以上就是八种常见的计算机系统流程，欢迎评论区留言~