数据结构

背景

计算机处理的信息和数据不仅包括数字，而且包括字符、表格、图形、图像、声音、动画等复杂问题，这些信息不只是简单、孤立的数据，而是存在某些关系的数据。独立的数据往往是毫无意义的，只有将它们组织在一起才能赋予它们确切的含义。如何组织、处理这些信息，就是数据结构的基本问题。数据结构就是指数据之间的结构层次关系。例如，给定二个点的坐标，计算机可以将它们连成一个三角形.也可以过这三个点作一个圆或画一段圆弧。但是，如果事先并没有确定这三个点之间的绘图关系，亦即如何组织利用这三个点进行画线、画圆或画圆弧，那么计算机就不能完成相应的动作。只有当点的坐标和绘图关系确定之后，计算机才能画出我们所希望的图形。因此，数据及其结构层次关系在计算机中的表达，是影响应用软件成败及效率高低的关键。

概念

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

数据的逻辑结构大致上可以分为线性结构和非线性结构。线性结构的数据元素之间存在一对一的关系，其特点是除了开头和最后一个节点外，其他的任意一个节点都只有一个直接前驱节点后后继节点。线性结构主要包括有线性表、栈和队列。树、集合、图都是非线性结构，其中树形结构模拟层次，图形结构模拟对称和非对称关系。研究数据结构是程序设计的需要，是为了使得程序设计更加的健壮、高效，使得程序的开发更加的方便。

数据结构的设计

应用数据结构解决生活中的问题的首要前提是研究应用什么数据结构解决生活中的问题。

分析步骤

其分析步骤为:

• 首先分析任务中的操作对象，即找出任务中涉及到的数据，从中总结和抽象出操作对象，并且分析操作对象之间的逻辑关系;

• 其次根据任务中对操作对象的操作，研究应用何种存储方式来存储数据才能高效的执行程序并且占用较小的存储空间。

• 选择数据结构的接口要最接近软件的需求。通常当有多个满足需要的接口数据结构实现时，可以根据比较他们的接口操作的运行时间以及数据结构消耗的空间来进行选择，有的时候时间和空间可以相互转换，比如可以用空间来交换操作的效率;

• 最后在物理存储方式的基础上设计正确的算法实现操作，完成任务。

建立数据结构

生活中所要处理的数据之间可以抽象出来不同的逻辑关系，建立不同的数据结构，但是针对实际问题要从中选取能够准确描述问题的基本特性并且易于实现的逻辑结构。

例如：八枚硬币中其中有一枚硬币是较为轻的，要求用一个天平将这枚轻的硬币判断出来，判断的过程采用将硬币分析两组或者三组，分别使用天平比较的方式来判断。这一判断过程可以用一个树形图来表示，所以可以将该问题抽象为判定树，构建树形结构。

存储结构

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

设计

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

应用数据结构解决表达式中括号匹配问题