数据结构-经济百科

什么是数据结构

数据结构是一种具有一定逻辑关系，在计算机中应用某种存储结构，并且封装了相应操作的数据元素的集合。它包含三方面的内容，逻辑关系、存储关系以及操作。

数据结构的内容

一般而言，数据结构的选择首先会从抽象数据类型的选择开始。一个设计良好的数据结构，应该在尽可能使用较少的时间与空间资源的前提下，为各种临界状态下的运行提供支持。数据结构可通过编程语言所提供的数据类型、引用及其他操作加以实现。

不同种类的数据结构适合于不同种类的应用，而部分甚至专门用于特定的作业任务。例如，当计算机网络依赖于路由表运作时，B树高度适用于数据库的封装。

在许多类型的程序设计中，选择适当的数据结构是一个主要的考虑因素。许多大型系统的构造经验表明，封装的困难程度与最终成果的质量与表现，都取决于是否选择了最优的数据结构。在许多时候，确定了数据结构后便能很容易地得到算法。而有些时候，思路则会颠倒过来：例如当某个关键作业需要特定数据结构下的算法时，会反过来确定其所使用的数据结构。然而，不管是哪种情况，数据结构的选择都是至关重要的。

系统构造的关键因素是数据结构而非算法的这一深入理解，导致了多种形式化的设计方法与编程语言的出现。绝大多数的语言都带有某种程度上的模块化思想，通过将数据结构的具体实现封装隐藏于受限接口之后的方法，来让不同的应用程序能够安全地重用这些数据结构。C++、Java、Python等面向对象的编程语言可使用类来完成这一功能。

因为数据结构的重要性毋庸置疑，现代编程语言及其运行环境在标准库中都包含了多种数据结构，例如C++标准模板库中的容器、Java集合框架以及微软的.NETFramework。

大多数数据结构都由数列、记录、可辨识联合、引用等基本类型构成。举例而言，可空引用（nullablereference，一种可被置空的引用）是引用与可辨识联合的结合体，而最简单的链式结构链表则是由记录与可空引用构成。

数据结构意味着接口或封装：一个数据结构可被视为两个函数之间的接口，或者是由数据类型联合组成的存储内容的访问方法封装。

数据结构的设计

应用数据结构解决生活中的问题的首要前提是研究应用什么数据结构解决生活中的问题。其分析步骤为：首先分析任务中的操作对象，即找出任务中涉及到的数据，从中总结和抽象出操作对象，并且分析操作对象之间的逻辑关系；其次根据任务中对操作对象的操作，研究应用何种存储方式来存储数据才能高效的执行程序并且占用较小的存储空间。选择数据结构的接口要最接近软件的需求。通常当有多个满足需要的接口数据结构实现时，可以根据比较他们的接口操作的运行时间以及数据结构消耗的空间来进行选择，有的时候时间和空间可以相互转换，比如可以用空间来交换操作的效率；最后在物理存储方式的基础上设计正确的算法实现操作，完成任务。

生活中所要处理的数据之间可以抽象出来不同的逻辑关系，建立不同的数据结构，但是针对实际问题要从中选取能够准确描述问题的基本特性并且易于实现的逻辑结构。例如八枚硬币中其中有一枚硬币是较为轻的，要求用一个天平将这枚轻的硬币判断出来，判断的过程采用将硬币分析两组或者三组，分别使用天平比较的方式来判断。这一判断过程可以用一个树形图来表示，所以可以将该问题抽象为判定树，构建树形结构。

根据选定的数据结构可以用不同的存储结构来实现。不同类型的数据结构常用的存储结构为顺序存储结构、链式存储结构、散列存储结构及索引存储结构。不同的存储结构具有不同的特点，大致上存在的差异在存储空间和运算效率两个方面。例如线性表的顺序存储结构与链式存储结构在存储空间上来对比，链式存储结构显然要多占用一部分存储空间。从运算效率上来对比，如果线性表需要进行大量的插入和删除操作的话，那么链式存储结构从执行效率上来讲要占有优势。而如果线性表要反复进行查询操作的话，顺序存储结构具备随机读写的特点，就比较适合这种情况。

确定数据的逻辑关系与存储结构的情况下，可以设计出不同的算法来实现应用。设计的算法应该是正确的算法。正确的算法的含义是：能够解决实际问题，输入的所有可能的合法的输入都能产生预期的正确的结果；能够在有穷的步骤内执行完程序；能够用最简短的语句最高效的完成任务。