什么是数据结构?
简而言之,数据结构是一个以特定形式存储数据的容器。这种“形式”允许数据结构在某些操作中更加高效。
常用的数据结构
常用的数据结构包括数组、堆栈、队列、链表、树、图表和哈希表等等,下面我们就简要介绍一下:
数组
数组是最简单和最广泛使用的数据结构。其他数据结构(如堆栈和队列)都是从数组派生的。下例是一个大小为4的简单数组:
每个数据元素都会分配一个称为索引值,该值对应于该项目在数组中的位置。大多数语言将数组的起始索引定义为0。
数组主要有两种类型:
堆栈
堆栈是一种只允许在表的一端进行插入操作和删除操作的线性表。其工作原理是后进先出。下图是包含三个数据元素(1,2和3)的堆栈示例:
堆栈的基本操作:
队列
与堆栈类似,队列是另一种线性数据结构,以顺序方式存储元素。Stack和Queue之间唯一的显着区别是,Queue不使用LIFO方法,而是实现先进先出方法。
Queue的一个现实生活例子是一排人在售票亭排队买票。如果再来一个人,那么他将从最后加入队列,而不是从头开始 - 站在前面的人将是第一个获得票离开。
下图是一个包含四个数据元素(1,2,3和4)的队列:
链表
链表是另一个重要的线性数据结构,它最初可能看起来类似于数组,但在内存分配,内部结构以及如何执行插入和删除的基本操作方面有所不同。
链表就像一个节点链,每个节点包含数据和指向链中后续节点的指针等信息。有一个头指针,它指向链表的第一个元素,如果列表是空的,那么它只是指向null或什么都没有。链表用于实现文件系统,哈希表和邻接列表。下面是链表的内部结构的直观表示:
链表的两种类型:
图
图是一组以网络形式相互连接的节点。节点也称为顶点。一对(x,y)称为边,表示顶点x连接到顶点y。边可以包含权重/成本,显示从顶点x到y遍历所需的成本。
图的类型:
在编程语言中,图形可以使用两种形式表示:
常见的图遍历算法:
树
树是一种分层数据结构,由顶点(节点)和连接它们的边组成。树类似于图形,但区分树和图形的关键点是树中不存在循环。树结构广泛用于人工智能和复杂算法,以提供解决问题的有效存储机制。这是一个简单树的图像,以及树数据结构中使用的基本术语:
以下是树木的类型:
哈希是一个用于唯一标识对象并将每个对象存储在一些预先计算的唯一索引(称为“密钥”)的过程。因此,该对象以“键值”对的形式存储,并且这些项的集合被称为“字典”。可以使用该键搜索每个对象。基于哈希有不同的数据结构,但最常用的数据结构是哈希表。哈希表通常使用数组实现。哈希数据结构的性能取决于以下三个因素:
这是一个如何在数组中映射哈希的说明。该数组的索引是通过哈希函数计算的。