数据结构

概述

常见的数据结构包括数组、链表、栈、队列、树、堆、图、散列表。我们可以从数据逻辑结构（对数据之间关系的描述）、数据存储结构（数据在内存中的存储形式）两方面来对它们进行分类。

数据逻辑结构分类

数据逻辑结构反映了数据元素之间的逻辑关系，逻辑关系指数据元素之间的前后间关联关系，与它们在计算机中的存储位置无关。
数据逻辑结构分类可分为以下4种：

• 集合结构：集合结构的集合中的元素只是“同属于一个集合”，任何两个数据元素之间都没有逻辑关系，组织形式松散；
• 线性结构：数据结构中的元素存在一对一的相互关系；
• 树形结构：数据结构中的元素存在一对多的相互关系；
• 图形结构：数据结构中的元素存在多对多的相互关系。
  

数据存储结构分类

数据的存储结构反映了数据在计算机内存中的存放形式。一般来说，一种数据结构的逻辑结构可以表示成多种存储结构，常用的存储结构包括顺序存储、链式存储、索引存储和哈希存储等。
存储结构可大致分为顺序存储和链式存储2种：

• 顺序存储：将逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构；
• 链式存储：不要求逻辑上相邻的数据在物理位置上也相邻，结点间的逻辑关系是由附加的指针字段来表示。由此得到的存储表示称为链式存储结构，它依赖程序设计语言中的指针类型来实现。