什么是数据结构

数据结构这个词几乎和Java一样始终贯彻着开发人员的工作，而我们许多人对于数据结构也是一知半解却又不求甚解，觉得没有必要刨根问底。但无论是出于工作还是出于个人求知因素，我们都应该弄懂到底什么是数据结构？

俗话说，遇事不决问度娘，想要回答什么是数据结构？我们先来看看百度百科对于数据结构的定义：数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。

而维基百科中的定义是：数据结构基于抽象数据类型（ADT），数据类型的数学模型，其中数据类型是从数据用户的角度通过其行为（语义）定义的，特别是在可能的值，对该类型数据的可能的操作以及行为方面这些操作。

ADT不在乎其值的内存表示形式或其操作如何实现。这就像一个Java接口，它是与任何实现断开连接的数据类型。相反，数据结构是一个或多个ADT的具体实现，类似于Java类如何实现接口。

数据结构伴生的一个词就容器，从容器中存储和检索数据项的任何内容都可以视为数据结构。包括Employee，Vehicle，Array和List ADT派生的数据结构。

许多数据结构旨在描述各种实体。例如，Employee类的实例是存在的用于描述各种员工的数据结构。相反，某些数据结构作为其他数据结构的通用存储容器而存在。例如，数组可以存储原始值或对象引用。我将后一类数据结构称为容器。除了聚合，我们看到的所有数据结构都是容器。

在大学中使用设计模式向大学生介绍数据结构已经相当普遍，我们在大学里开设的数据结构课上应该有所接触。布朗大学的一篇论文调查了几种对设计高质量数据结构有用的设计模式。其中典型的Adapter模式对于设计堆栈和队列很有用。我们来看下面的代码实例。

将适配器模式用于堆栈和队列（DequeStack.java）

public class DequeStack implements Stack

{

   Deque D; // holds the elements of the stack

   public DequeStack()

   {

      D = new MyDeque();

   }

   @Override

   public int size()

   {

      return D.size();

   }

   @Override

   public boolean isEmpty()

   {

      return D.isEmpty();

   }

   @Override

   public void push(Object obj)

   {

      D.insertLast(obj);

   }

   @Override

   public Object top() throws StackEmptyException

   {

      try

      {

         return D.lastElement();

      }

      catch(DequeEmptyException err)

      {

         throw new StackEmptyException();

      }

   }

   @Override

   public Object pop() throws StackEmptyException

   {

      try

      {

         return D.removeLast();

      }

      catch(DequeEmptyException err)

      {

         throw new StackEmptyException();

      }

   }

}

上面的代码摘自了布朗大学的DequeStack课程，该课程演示了Adapter模式。请注意，Stack和Deque是描述堆栈和双端队列ADT的接口。MyDeque是实现的类Deque。当然目前的数据结构体系已经比较完善，想通过Adapter模式设计出新的数据结构虽说不是天方夜谭也无疑是希望渺茫。

在计算机科学的发展过程中，数据结构也随之发展，程序设计中常用的数据结构包括如下几个。

1.数组(Array)

数组是一种聚合数据类型，它是将具有相同类型的若干变量有序地组织在一起的集合。

2.栈( Stack)

栈是一种特殊的线性表，它只能在一个表的一个固定端进行数据结点的插入和删除操作。

3. 队列(Queue)

队列和栈类似，也是一种特殊的线性表。

4.链表( Linked List)

链表是一种数据元素按照链式存储结构进行存储的数据结构，这种存储结构具有在物理上存在非连续的特点。

5.树( Tree)

树是典型的非线性结构，它是包括，2个结点的有穷集合K。

6.图(Graph)

图是另一种非线性数据结构。

7.堆(Heap)

堆是一种特殊的树形数据结构，一般讨论的堆都是二叉堆。[5]

8.散列表(Hash)

散列表源自于散列函数(Hash function)，其思想是如果在结构中存在关键字和T相等的记录，那么必定在F(T)的存储位置可以找到该记录，这样就可以不用进行比较操作而直接取得所查记录。

其实，由于数据结构本身自带的热度，网上有着各种各样关于数据结构的定义和理解，本文也是结合了一些大咖们的观点全面的介绍了一下什么是数据 结构 ，并总结出来的一些自己的理解。学而不思则罔，希望每个人都能够在学习数据结构的过程中多多融入自己的理解，多加思考，才能真正学好数据结构这门课。