数据结构算法的描述和分析

数据结构概论

高级语言程序设计在解决某一实际问题的一般步骤是：分析实际问题、确定数学模型、设计或选择一个求解此数学模型的算法、编写程序进行调试和测试解决问题等几个步骤。

例1：已知：游泳池的长length和宽winde，求面积area。

问题设计的对象有：游泳池的长length和宽wide，面积area；对象之间的关系（数学模型）：A=L*W；

程序：

Main（）

{

int len，wide，area；

Scanf（“%d%d%\n”，&l，&w）；

Area=len*winde；

Printf（“area=%d”，area）；

}

 

解决游泳池面积或其他复杂的现实问题时，关键的不再是数学分析和计算方法，而是要设计出合适的数据结构，才能更有效有的解决生活的现实问题，著名的瑞士科学家沃思提出：程序设计=数据结构+算法      

简单来说，数据结构是研究非数值的程序设计问题中计算机的操作对象以及它们之间的关系和操作的学科。

具体来说，数据结构指的是数据之间的结构关系如何表示，如何存储，如何处理现实转化问题，即按某种关系组织起来的一组数据，再按一定的方式把它们存储在计算机的存储器中，并在这些数据上定义的一个运算的集合，称之为数据结构。

基本概念和常用的术语

数据：是客观事物的符号表示，在计算机科学中指所有能输入到计算机并能被计算机程序进行处理的符号总称。

数据元素：是数据的基本单位。在计算机程序中通常作为一个整体考虑和处理。

数据项：一个数据元素通常由若干个数据项组成，数据项是不可分割的最小单位。

数据对象：是具有相同性质的数据元素的集合。

数据结构是带有结构和操作的数据元素的集合。一般包含三个方面的内容。

• 数据的逻辑结构

在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系存在某种关系，这种数据元素是相互之间的关系称之为数据的逻辑结构。根据数据元素之间关系的不同特性，通常有下列四种基本结构形式。

（1）集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系，元素之间为松散关系。

（2）线性结构：结构中的数据元素存在一对一的关系，除第一个和最后一个元素外，其他每个元素都有且仅有一个直接前驱和一个直接后继。

（3）树形结构：数据元素之间存在一对多的关系。一个数据元素可以与一个或多个元素存在关系，而且具有层次之分，其结构形式如倒立的生长的树。

（4）图状结构或网状结构：数据元素之间存在多对多的关系，不存在层次关系。在这种关系中，数据元素之间不受任何限制。

以上描述的4种关系是数据元素之间的逻辑关系，又称之为逻辑结构。

• 数据的存储结构

讨论数据逻辑结构的目的是为了在计算机中实现对它的操作，因此还要研究如何在计算机中表示它。

数据元素在计算机中的存储（表示）方式称之为数据的物理结构，又称存储结构。它包含数据元素及数据元素之间关系的存储。是依赖于计算机语言的。

在计算机内，数据的存储结构可以用一下四种基本存储方法实现

（1）顺序存储结构：是将逻辑上相邻的元素节点存储在物理位置上也相邻的存储单元中，元素之间的逻辑关系由存储单元的邻接关系表示。由此得到的存储结构也称之为顺序结构。该结构通常用数组来实现。

（2）链式存储结构：不要求逻辑上相邻的元素（节点）在物理位置上也相邻，而是在结点中借助指针域与该结点逻辑上相邻元素在内存中的地址来实现结点间的逻辑关系。由此得到的存储结构称为链式存储结构。及借助于引用或指针来表示数据元素之间的逻辑关系，被存放的元素被随机的存放在内存中再用指针将它们链接在一起。

（3）索引存储结构：在存储元素信息的同时，还建立附加的索引表。

（4）散列存储结构：根据元素的关键字直接计算出该元素的存储地址。

三、数据的运算

数据的运算，即对数据元素施加的操作，是定义在数据的逻辑结构上的，每种逻辑结构都有一个运算的集合。

数据的运算地数据结构不可分割的一个方面，在给定了数据的逻辑结构和存储结构之后，按照定义的运算集合及运算性质的不同，可能导致完全不同的数据结构。

另外，同一种逻辑结构，可以采用不同的存储结构。选择何种存储结构来表示相应的逻辑结构，要根据具体问题具体分析，主要考虑的还是数据运算方便及算法的时间和空间上的要求。

算法的描述与分析

算法描述

算法：是对问题求解步骤的一种描述，是指令的有限序列。其中每条指令表示一个或多个操作。一个算法应具备以下5个特性：

有限性：算法必须在有限的步骤之后结束

确定性：算法的每一步都是确切的含义，无二义性。即在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出

输入：一个算法可以接受零个或多个输入

输出：一个算法至少有一个或多个输出

可行性：算法中的每一步都可以通过已经实现的基本运算的有限次运行来实现

算法分析

求解一个问题可能有多种不同的算法，而算法的好坏直接影响程序的执行效率，且不同算法之间的运行效率相差巨大。

设计一个“好”得算法应考虑达到算法应达到的四个目标：正确性、可读性、健壮性高效率与低存储量需求

一个算法的评价可以从算法执行的时间与算法的所占用的内存空间两个方面来进行。

算法的时间复杂度（time completexity）又称为计算复杂度，是算法有效性的度量之一。

在解决实际问题的过程中不管是简单或复杂的算法，都必须是经过对应着一定的基本操作的次数。显然，如果一个算法中，运行基本操作的次数越少，那么它运行的时间也就相对越少，反之，如果次数越多，其运行的时间也就相对越多。所以，通常用它来衡量一个算法的运行时间性能或称之为计算性能。

算法的空间复杂度（space completexity）是对一个算法在运行时占用存储空间大小的度量，也是衡量算法的有效性的一个重要的因素。因此，在分析一种算法的性能，不但需要分析算法的运行时间，还要分析算法所采用的的数据结构所占的空间。

存储空间包括内存和外存，一般用字节作为空间的基本度量单位，问题的规模（或大小）为n,算法所需空间的空间单元数s一般是问题规模n的函数f（n）记作：S(n)=O(F(n))