说明
数据产品经理教程 正在编写中,欢迎大家加微信 gairuo123 (备注:数据产品教程) 提供意见、建议、纠错、催更。应大家要求,作者开办数据产品和数据分析培训班,详情 数据产品经理培训 / 数据分析培训。
数据结构(英语:data structure)是计算机中存储、组织数据的方式。不同种类的数据结构适合不同种类的应用,部分数据结构甚至是为了解决特定问题而设计出来的。
正确的数据结构选择可以提高算法的效率。在计算机程序设计的过程中,选择适当的数据结构是一项重要工作。许多大型系统的编写经验显示,程序设计的困难程度与最终成果的质量与表现,取决于是否选择了最适合的数据结构。
堆栈(英语:stack)又称为栈或堆叠,是计算机科学中的一种抽象资料类型,只允许在有序的线性资料集合的一端(称为堆栈顶端,英语:top)进行加入数据(英语:push)和移除数据(英语:pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。常与另一种有序的线性资料集合队列相提并论。
堆栈使用两种基本操作:推入(压栈,push)和弹出(弹栈,pop):
堆栈的基本特点:
队列,又称为伫列(queue),计算机科学中的一种抽象资料型别,是先进先出(FIFO, First-In-First-Out)的线性表。在具体应用中通常用链表或者数组来实现。队列只允许在后端(称为rear)进行插入操作,在前端(称为front)进行删除操作。
队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。
数组数据结构(英语:array data structure),简称数组(英语:Array),是由相同类型的元素(element)的集合所组成的数据结构,分配一块连续的内存来存储。利用元素的索引(index)可以计算出该元素对应的存储地址。
最简单的数据结构类型是一维数组。二维数组,对应于数学上的矩阵概念,可表示为二维矩形格。数组通常用于实现数据库的表格,特别是查询表;表格有时也被当作是数组的同义词。
组是最早期和最重要的数据结构之一,很多程序都会用到数组。它们也用于实现许多其他数据结构,譬如列表(list)和字符串(string)。它们有成效地开展了计算机的寻址逻辑。在大多数现代计算机和许多外部存储设备中,存储器如同一维数组,索引就是其地址。编译器、处理单元(特别是向量处理器),经常会针对数组操作进行优化。
链表(Linked list)是一种常见的基础数据结构,是一种线性表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。
链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成,每个节点包含任意的实例数据(data fields)和一或两个用来指向上一个/或下一个节点的位置的链接("links")。链表最明显的好处就是,常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序,数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型,因为它包含指向另一个相同类型的数据的指针(链接)。链表允许插入和移除表上任意位置上的节点,但是不允许随机存取。链表有很多种不同的类型:单向链表,双向链表以及循环链表。
树(英语:tree)是一种抽象数据类型(ADT)或是实现这种抽象数据类型的数据结构,用来模拟具有树状结构性质的数据集合。它是由n(n>0)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。它具有以下的特点:
术语:
树的种类:
在数学的分支图论中,图(Graph)用于表示物件与物件之间的关系,是图论的基本研究对象。一张图由一些小圆点(称为顶点或结点)和连结这些圆点的直线或曲线(称为边)组成。西尔维斯特在1878年首次提出“图”这一名词。
堆(英语:Heap)是计算机科学中的一种特别的完全二叉树。若是满足以下特性,即可称为堆:“给定堆中任意节点P和C,若P是C的母节点,那么P的值会小于等于(或大于等于)C的值”。若母节点的值恒小于等于子节点的值,此堆称为最小堆(min heap);反之,若母节点的值恒大于等于子节点的值,此堆称为最大堆(max heap)。在堆中最顶端的那一个节点,称作根节点(root node),根节点本身没有母节点(parent node)。
堆始于J. W. J. Williams在1964年发表的堆排序(heap sort),当时他提出了二叉堆树作为此算法的数据结构。堆在戴克斯特拉算法(英语:Dijkstra's algorithm)中亦为重要的关键。
在队列中,调度程序反复提取队列中第一个作业并运行,因为实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。
散列表(Hash table,也叫哈希表),是根据键(Key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算一个关于键值的函数,将所需查询的数据映射到表中一个位置来访问记录,这加快了查找速度。这个映射函数称做散列函数,存放记录的数组称做散列表。
一个通俗的例子是,为了查找电话簿中某人的号码,可以创建一个按照人名首字母顺序排列的表(即建立人名x到首字母F(x)的一个函数关系),在首字母为W的表中查找“王”姓的电话号码,显然比直接查找就要快得多。这里使用人名作为关键字,“取首字母”是这个例子中散列函数的函数法则F(),存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。
更新时间:2021-03-14 10:13:16 标签:数据结构