初探数据结构

在经过一段时间的JAVA基础学习之后，最近开始学习JAVA中的集合框架，当看到链表、散列这些数据结构的时候，总有一些云里雾里的感觉，迫不及待的想要了解其内部的实现。

目前手上有三本关于数据结构的书籍，《大话数据结构》，《数据结构与算法分析-C语言描述》，《算法-第四版》，这些书都经过很多人的推荐，内容应该都很优秀。

好了下面进入主题，虽然都是很基础的内容，但是理解掌握好这些基础的定义，对后面的学习有着很大帮助。

---

一、基本概念和术语

• 数据：是描述客观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。
• 数据元素：是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理。也称为记录。
• 数据对象：是性质相同的数据元素的集合，是数据的子集。

上面是一些官方的定义，下面是我自己的理解。

数据元素也就是一条条记录，它可以是单一的，也可以是由多个数据项组成。用过数据库的童鞋应该都知道，数据表中的每一行记录都是一个数据元素，每一列都是一个数据项，数据项是数据元素的子集。例如下图：每一个人记录都是一个数据元素，一个数据元素由姓名、年龄等这些数据项组成。

在数据集合中可以是性质相同的数据元素，也可以是性质不同的数据，而这里的数据对象其实就是性质相同数据元素的集合。

二、数据结构的分类

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

数据结构又可以分为下面两种结构：

1. 逻辑结构：是指数据对象中数据元素之间的相互关系。

   逻辑结构又分为以下四种：

   • 集合结构：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。
     
   • 线性结构：线性结构中的数据元素之间是一对一的关系。
     
   • 树形结构：树形结构中的数据元素之间存在一种一对多的层次关系。
     
   • 图形结构：图形结构的数据元素是多对多的关系。
     

2. 物理结构（存储结构）：是指数据的逻辑结构在计算机中的存储形式。

   物理结构又分为以下两种：

   • 顺序存储结构：是把数据元素存放在地址连续的存储单元里，其数据间的逻辑关系和物理关系是一致的。
     
   • 链式存储结构：是把数据元素存放在任意的存储单元里，这组存储单元可以是连续的，也可以是不连续的。
     

从前面我们知道了数据对象是性质相同的数据元素的集合，而数据结构在数据对象的基础上又多了一种或多种特定关系，这里的特定关系主要指的就是数据元素之间的逻辑结构和物理结构。

逻辑结构是一种抽象的结构，学过计算机组成的同学可能知道，在程序运行的时候，数据是存储在内存中的，而内存中的基本存储单位就是存储单元，那我们如何在内存中表示逻辑结构呢？

这里就用到了物理结构，我们可以将物理结构理解成具体的，逻辑结构理解成抽象的，使用物理结构反应数据元素之间的逻辑关系，如何存储数据元素之间的逻辑关系，是实现物理结构的重点和难点。

数据元素之间的存储结构形式有两种：顺序存储和链式存储。我们主要使用这两种存储方式来反映数据元素的逻辑结构。

三、抽象数据类型

• 数据类型：是一组性质相同的值的集合及定义在此集合上的一些操作的总称。

  又分下以下两种类型：

  • 原子类型：是不可以再分解的基本类型，包括整型、实型、字符型等。
  • 结构类型：由若干个类型组合而成，是可以再分解的。例如，整型数组是由若干个整型数据组成的。

• 抽象数据类型（ADT）：是指一个数学模型及其定义在该模型上的一组操作。

抽象数据类型：一个数据对象 + 数据对象中各数据元素的关系 + 数据元素的操作

前文中说了数据对象和数据对象中数据元素的关系组成数据结构有些不妥。这里我认为数据结构是通过抽象数据类型来实现的，也就是说抽象数据类型是数据结构的骨架。（个人见解）

四、总结

上述内容都是数据结构的基础，接下来的线性表、队列、散列表、二叉树等都是四种逻辑结构的具体实现，每一种数据结构都是相当于一个容器。尤其是线性表两种实现方式，是学习后面其他数据结构的基础。

在选择学习书籍的时候，建议尽量不要一上来就选择经典的大部头，经典虽好，但学习也需要循序渐进，理解不了不仅浪费时间，自己长时间无法得到正向反馈，也会严重磨灭自己学习情绪，尤其是需要转行自学的童鞋。我自己本身也是在脱产自学当中，前面一段时间买了很多经典的书籍，现在发现很多暂时都用不到，反而像《大话数据结构》这样简单易上手的书籍对自己帮助很大。

文中一些观点仅是个人见解，由于自己也是初学，有些见解难免产生错误，随着后面学习的深入，也不保证这些见解一直不变，如果你有不同的见解，欢迎一起交流。

原文链接：http://www.cnblogs.com/nwgdk/p/9025695.html
参考书籍：《大话数据结构》