数据结构有哪几种?

更新日期: 2018-11-28阅读: 8.3k标签: 数据结构
数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成。包括三个组成成分:数据的逻辑结构、物理结构(存储结构)、数据运算结构。


1、集合(数据之间无关系)

集合是不同对象(称为成员)的无序聚集。集合的两个重要特点:

一、成员是无序的;
二,每个成员都只在集合中出现一次。

集合是离散数学中的重要部分,离散数学与计算机科学之间有着很深的渊源。在计算机科学中,我们使用集合来归类数据,尤其是当我们计划以后将其与其他数据相关联时。C语言并没有原生支持集合,而是作为一种抽象数据类型来实现。


2、线性结构(一对一)

线性结构的特点是:在数据元素的非空有限集中, 线性表简单来说就是数据元素的非空有限序列,其特点是可以从表中的任何位置进行插入([0 , n])和删除([0 , n-1])操作。  

(1)存在惟一的一个被称作“第一个”的数据元素和惟一的一个被称作“最后一个”的数据元素; 
(2)除第一个之外,集合中的每个数据元素均只有一个前驱;除最后一个之外,集合中的每一个数据元素均只有一个后继。  


3、树形结构(一对多)

数据结构中,使用树形结构表示数据表素之间一对多的关系,树形结构是一种非线型结构,定义:
树(Tree)是n(n≥0)个相同数据类型的数据元素的集合.树中的数据元素称为节点(Node).。n=0的树称为空树(Empty Tree);对于n>0的任意非空树T有:

(1)有且仅有一个特殊的结点称为树的根(Root)结点,根没有前驱结点;
(2)若n>1,则除根结点外,其余结点被分成了m(m>0)个互不相交的集合T1,T2,…,Tm,其中每一个集合Ti(1≤i≤m)本身又是一棵树。树T1,T2,…,Tm称为这棵树的子树(Subtree)。
由树的定义可知,树的定义是递归的,用树来定义树。因此,树(以及二叉树)的许多算法都使用了递归。树的形式定义为:树(Tree)简记为T,是一个二元组
T = (D, R)
其中:D是结点的有限集合;R是结点之间关系的有限集合。
树具有下面两个特点:
(1)树的根结点没有前驱结点,除根结点之外的所有结点有且只有一个前驱结点。
(2)树中的所有结点都可以有零个或多个后继结点。  


4、图形结构(多对多)

图形数据结构主要研究形状和图形数据元素之间的关系,它主要谈论几何形体在计算机内部的表示以及期间进行运算的基本方法。“算法+数据结构=程序”来说明数据结构在程序设计中所占的重要位置。 

 

5、数组

所谓数组,是有序的元素序列。若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按无序的形式组织起来的一种形式。这些无序排列的同类数据元素的集合称为数组。


6、栈(先进后出、线性表)
栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈,它是把新元素放到栈顶元素的上面,使之成为新的栈顶元素;从一个栈删除元素又称作出栈或退栈,它是把栈顶元素删除掉,使其相邻的元素成为新的栈顶元素。 
 

7、队列(先进先出、后进后出、线性表)

队列是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表。进行插入操作的端称为队尾,进行删除操作的端称为队头。


8、链表

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

每个节点包括两个部分:一个存储数据元素的数据域、另一个存储下一个节点地址的指针域


9、散列表

散列表(Hash table,也叫哈希表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。 给定表M,存在函数f(key),对任意给定的关键字值key,代入函数后若能得到包含该关键字的记录在表中的地址,则称表M为哈希(Hash)表,函数f(key)为哈希(Hash) 函数。


链接: https://www.fly63.com/article/detial/1443

内容以共享、参考、研究为目的,不存在任何商业目的。其版权属原作者所有,如有侵权或违规,请与小编联系!情况属实本人将予以删除!