# 数据结构系列

  • 本系列主要讲解基本的数据结构,以及其常见的操作

# 理解数据结构

  • 数据结构是计算机存储、组织数据的方式
  • 数据结构(data structure)是带有结构特性的数据元素的集合
  • 数据结构是相互之间存在一种或多种特定关系的数据元素的集合,即带“结构”的数据元素的集合
  • “结构”就是指数据元素之间存在的关系,分为逻辑结构和存储结构

# 数据的物理结构

  • 指数据的逻辑结构在计算机存储空间的存放形式
  • 数据的物理结构是数据结构在计算机中的表示(又称映像)
  • 由于具体实现的方法有顺序、链接、索引、散列等多种,所以,一种数据结构可表示成一种或多种存储结构
  • 用二进制位(bit)的位串表示数据元素

# 数据的存储结构

  • 一种数据结构的逻辑结构根据需要可以表示成多种存储结构,常用的存储结构有顺序存储、链式存储、索引存储和哈希存储等
  • 数据的顺序存储结构的特点是:借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系
  • 非顺序存储的特点是:借助指示元素存储地址的指针表示数据元素之间的逻辑关系

# 常见的数据结构

  • 数组Array:数组是一种聚合数据类型,它是将具有相同类型的若干变量有序地组织在一起的集合
  • 栈Stack:栈是一种特殊的线性表,它只能在一个表的一个固定端进行数据结点的插入和删除操作
  • 队列Queue:队列和栈类似,也是一种特殊的线性表。和栈不同的是,队列只允许在表的一端进行插入操作,而在另一端进行删除操作
  • 链表Linked List:链表是一种数据元素按照链式存储结构进行存储的数据结构,链表由一系列数据结点构成,每个数据结点包括数据域和指针域两部分。其中,指针域保存了数据结构中下一个元素存放的地址
  • 树Tree:树是典型的非线性结构,在树结构中的其他结点都有且仅有一个前驱结点,而且可以有两个后继结点
  • 图Graph:图是另一种非线性数据结构。在图结构中,数据结点一般称为顶点,而边是顶点的有序偶对
  • 堆Heap:堆是一种特殊的树形数据结构,堆的特点是根结点的值是所有结点中最小的或者最大的,并且根结点的两个子树也是一个堆结构
  • 散列表Hash:散列表源自于散列函数(Hash function),其思想是如果在结构中存在关键字和T相等的记录,那么必定在F(T)的存储位置可以找到该记录,这样就可以不用进行比较操作而直接取得所查记录

# 数据结构操作

  1. 检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值,找具有该字段值的节点
  2. 插入。往数据结构中增加新的节点
  3. 删除。把指定的结点从数据结构中去掉
  4. 更新。改变指定节点的一个或多个字段的值
  5. 排序。把节点按某种指定的顺序重新排列。例如递增或递减

# 数据结构的重要性

  • 数据结构同算法的重要性,都是考验程序员的基础功底
  • 理解数据结构,可以帮助我们进一步了解计算机对数据的存储与操作
  • 对不同问题通过使用不同的数据结构会产生不同的效果,通过使用最佳的数据结构,来使其达到预期效果
  • 比如导航,我们就需要使用图结构,通过图的一些操作可以实现找出去往目的地的一些路线,以及根据权重计算出来的最优路线
  • 把实际问题转换成合适的数据结构,并配合数据解构的操作以及合适的算法来达到高效解决问题
  • 所有的实际问题如果放到计算机上,都需要对其使用的数据进行建模,使用何种数据结构来操作这些数据更加方便,这就需要我们对数据结构有一点的认识才能快速的准确的判断出最佳表示
上次更新: 2020-5-17 18:20:47