测试派 Give testers a home.

数据结构与算法概述

数据结构

概述

• 数据结构一般用于描述数据与数据之间关系，是展现一组数据在程序中呈现的形式和存储的结构，常分为逻辑结构和物理结构
• 何为数据？
  • 数据是用于描述现实中的客观事物，是一个抽象的概念
  • 具体到程序设计过程中，如一个人，一组用户，都是程序中的数据
  • 在Java语言体系中，会对数据进行一定的分类，就有了数据的类型，像整型、字符串等
• 数据结构在描述数据关系时，常分为逻辑结构和物理结构

逻辑结构

• 集合结构
  • 多个数据间，数据归纳为同一集合中，除此之外，并无特定的关系；如生活中称呼的儿童、少年等，都是集合结构的体现
  • 结构如下图

• 线性结构
  • 多个数据间，存在一对一的连续或顺序关联关系
  • 常见的线性结构有顺序表、链表、栈、队列等
  • Java语言中，数组、List、Set、Stack、Queue系列的工具类都是线性结构
  • 结构如下图

• 树形结构
  • 多个数据间，存在从上往下的一对多的层次性关系，是非线性关系的典型结构之一
  • 常见的树形结构有树、二叉树、红黑树等
  • Java语言中，TreeMap、HashMap都有对于树的应用
  • 结构如下图

• 图形结构
  • 多个数据间，存在不限定的多对多的关系，也是非线性关系的典型结构之一
  • 常见的图形结构，如网络中的路由结构图，还有火车的列车运行图
  • 结构如下图

物理结构

• 物理结构是指数据的逻辑结构在计算机或软件系统的存储介质中的存储形式，并能很好的呈现数据间的逻辑结构关系
• 物理结构有两种，分别是顺序存储和链式存储
• 顺序存储
  • 把数据存储在地址连续的存储单元中
  • 优点：随机访问(查询)效率高
  • 缺点：内存要求高；内存利用率低，不方便进行扩展；插入、删除效率低，需要移动大量数据
• 链式存储
  • 把数据存储在任意空闲的存储单元中，数据通过类似指针的形式存储关联数据的地址
  • 优点：内存利用率高；插入、删除效率高
  • 缺点：一般包括数据域和指针域，结构稍复杂；随机访问(查询)效率低，每次都要从头遍历查找

常用数据结构

• 常用的逻辑结构有：数组、链表、双向链表、栈、队列、哈希表、堆、树、二叉树、红黑树、图等

【备注：部分图片来自网络】