集团旗下网站: 迈领人才网 | 奇酷方舟 | 红砖升本
全国咨询热线:400-807-8991
您现在所在的位置:首页 >学习资源 > Unity游戏/VR/AR入门教材 > VR开发入门教程45:数据结构简述

VR开发入门教程45:数据结构简述

来源:奇酷教育 发表于:

VR开发 VR教程 VR培训

  数据结构

  一般将数据结构分为两大类: 线性数据结构和非线性数据结构。

  线性数据结构有: 线性表、栈、队列、串、数组和文件;

  非线性数据结构有: 散列表、树和图。

  线性表

  线性表的逻辑结构是n个数据元素的有限序列:

  (a1, a2 ,a3,…an)

  n为线性表的长度(n≥0),n=0的表称为空表。

  数据元素呈线性关系。必存在唯一的称为“第一个”的数据元素;必存在唯一的称为“最后一个”的数据元素;除第一个元素外,每个元素都有且只有一个前驱元素; 除最后一个元素外,每个元素都有且只有一个后继元素。

  所有数据元素在同一个线性表中必须是相同的数据类型。

  线性表按其存储结构可分为顺序表和链表。用顺序存储结构存储的线性表称为顺序表;用链式存储结构存储的线性表称为链表。

  将线性表中的数据元素依次存放在某个存储区域中,所形成的表称为顺序表。一维数组就是用顺序方式存储的线性表。

  链表

  栈(Stack)也是一种特殊的线性表,是一种后进先出(LIFO)的结构。

  栈是限定仅在表尾进行插入和删除运算的线性表,表尾称为栈顶(top),表头称为栈底(bottom)。

  栈的物理存储可以用顺序存储结构,也可以用链式存储结构。

  队列(Queue)是限定所有的插入只能在表的一端进行,而所有的删除都在表的另一端进行的线性表。

  表中允许插入的一端称为队尾(Rear),允许删除的一端称为队头(Front)。

  队列的操作是按先进先出(FIFO)的原则进行的。

  队列的物理存储可以用顺序存储结构,也可以用链式存储结构。

  散列表又称为哈希表。散列表算法的基本思想是:

  以结点的关键字为自变量,通过一定的函数关系(散列函数)计算出对应的函数值,以这个值作为该结点存储在散列表中的地址。

  当散列表中的元素存放太满,就必须进行再散列,将产生一个新的散列表,所有元素存放到新的散列表中,原先的散列表将被删除。在C#语言中,通过负载因子(load factor)来决定何时对散列表进行再散列。例如:如果负载因子是0.75,当散列表中已经有75%的位置已经放满,那么将进行再散列。

  负载因子越高(越接近1.0),内存的使用效率越高,元素的寻找时间越长。负载因子越低(越接近0.0),元素的寻找时间越短,内存浪费越多。