[科普中国]-应用数据结构

数据结构背景

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

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

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

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

分析步骤其分析步骤为:

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

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

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

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

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

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

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

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

应用数据结构解决表达式中括号匹配问题抽象数据的逻辑结构在此问题中操作对象为表达式的括号，括号的匹配的表达式都具有这样的特点:在从左至右扫描表达式的过程中，最先扫描到的右括号必定与之前最后扫描到的左括号相匹配。根据这特点及栈的先进后出的特点可以将表达式抽象成栈，表达式中的左、右括号为栈中的数据元素。并且该逻辑结构具有出栈及入栈的操作能够满足任务的需求。

选用存储数据的物理结构顺序栈占用存储空间小，不浪费空间，同时进栈与出栈操作程序执行效率高。所以解决该问题可采用顺序存储结构实现栈。顺序栈的特点是:用一组连续的空间存放自栈底到栈顶的数据元素。数据元素之间存在线性关系，第一个入栈的数据元素称为栈底元素，最后一个入栈的数据元素称为栈顶元素，用指针TOP标志。顺序栈的基本操作包括:创建一个空栈、判断栈是否为满、判断栈是否为空、得出栈的长度、入栈、出栈、返回栈顶元素。如图所示:

顺序栈入栈操作的实现步骤为:1

判断如果栈己满，返回false，不允许入栈

若栈不满，将栈顶指针top+ 1

数据element存入top所指的空间中

操作成功返回true

顺序栈出栈操作的实现步骤为:

判断顺序栈状态，如果栈己空，不允许出栈

若栈不空，取出栈顶指针top所指的内容

栈顶指针top-1，指向下一个元素

返回出栈数据

算法描述关于括号匹配的操作是这样进行的:

(1)将输入的表达式按序存入数组，扫描整个数组，遇到左括号都进行栈

(2)遇到右括号

①先进行判空，若是空栈，则一个右括号入栈后一定是不匹配的

②如果判空后不是空栈，那么就把栈里的括号弹出并与遇到的第一个右括号进行匹配判断，若匹配则继续执行步骤1. 2，若不匹配则整个表达式也不匹配。

(3)当进行完上面得操作后，如果栈不为空，那就说明肯定还有括号留在栈中，那一定就是不匹配了。若整个表达式扫描完毕，栈也为空，则说明表达式中括号匹配。2

应用数据结构以上所讲的数据结构在计算机辅助机械设计系统中的应用主要有下列几个方面:2

为设计资料的数据描述提供依据从严格意义上来讲，应用程序中对任何一个变量的定义、对任何一个数据文件的存取都涉及到数据结构的问题。定义数据结构应遵循的一个基本原则是:数据结构简单、逻辑关系明确清晰、便于操作、存取速度快、运行效率高、占用存储空间少。对简单意义的变量一般可以用常量、单变量来定义；对较为复杂的数据一般可以用一维数组、多维数组、结构变量或指针来定义。2

适合应用软件适合应用软件作业中对设计模型作实时修改的需要。如增加、删除、修改记录等。应根据实际情况，对线性结构的数据和非线性结构的数据构造不同的数据结构，以便于提高数据操作的效率。顺序存储结构和链式存储结构各有优缺点，它们适合于不同的场合，因而选用时应权衡考虑。

为数据检索提供条件在设计中常常需要根据设计对象的某些特征、属性来检索一些数据以供设计之用，为此就必须利用数据结构来提供条件。如一部机器可能由很多个零件组成，应用软件作业中可能需要根据零件的名称、材料、标准件或非标准件等条件进行检索。这就需要很好地定义零件信息的数据结构以便检索。

为数据通信提供条件如为网络机械设计、数据交换及共享数据资源提供条件。智能化、集成化和网络化是目前CAD发展的趋势。这些都涉.及到大量数据的通信和交换。只有严密、高效的数据结构才能保证计算机辅助机械设计技术的健康发展。