1.2 基本概念和术语
 
 
 
1.2.1  数据、数据元素、数据项和数据对象
 
数据 (Data) :是客观事物的符号表示，是所有能输入到计算机中并被计算机程序处理的符号的总称。包括数值型的数据(整数、实数等)，非数值型的数据(文字、图像等)。 
 
数据元素(Data Element) :是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。某些情况下，数据元素称为元素、记录等。
 
数据项(Data Item) : 是组成数据元素的、有独立含义的、不可分割的最小单位。例如，某一张信息表中的一个字段都是数据项。
 
数据对象(Data Object) :是性质相同的数据元素的集合，是数据的一个子集。
 
 
 
数据结构(Data Structure)是相互之间存在一种或多种特定关系的数据元素的集合。数据结构包括逻辑结构和存储结构两个层次。
 
1.逻辑结构
数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
数据的逻辑结构有两个要素 : 一是数据元素；二是关系(指数据元素间的逻辑关系)。
 
数据元素之间通常有四类基本结构
( 1 )集合结构 :"属于同一集合"的关系外，别无其他关系。
( 2 )线性结构 :数据元素之间存在"一对一"的关系。
( 3 )树结构 :数据元素之间存在一对多的关系。
( 4 )图结构 :数据元素之间存在多对多的关系。
 
2.存储结构
数据对象在计算机中的存储表示称为数据的存储结构，也称为物理结构(即计算机存储器中的表现形式)。
 
数据元素在计算机中有两种基本的存储结构(顺序存储、链式存储)
( 1 )顺序存储结构
即数据元素在内存中的地址是连续存储的，且数据元素之间的逻辑关系也是连续存储的，在程序设计语言中使用数组来描述。
( 2 )链式存储结构
链式存储结构不像顺序存储结构要求所有的元素依次存放在一片连续的存储空间中。链式存储结构中的元素是随机存储在计算机的存储器中的，
数据元素是由程序设计语言中的指针连接起来的。
 
逻辑结构与存储结构的关系 :
  • 存储结构是逻辑关系的映像与元素本身的映像。
  • 逻辑结构是数据结构的抽象，存储结构是数据结构的实现。
  • 两者综合起来建立了数据元素之间的结构关系。

 

1.2.3 数据类型和抽象数据类型
 
1. 数据类型
数据类型(Data Type)是高级程序设计语言中的一个基本概念，(定义)数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
 
2. 抽象数据类型
抽象数据类型(Abstract Data Type,ADT)一般指由用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
    定义格式:
    ADT 抽象数据类型名{
       数据对象 :<数据对象的定义>
       数据关系 :<数据关系的定义>
       基本操作 :<基本操作的定义>
   }ADT 抽象数据类型名
其中，数据对象和数据关系的定义采用数学符号和自然语言描述(即伪代码)
 
1.4 算法和算法分析
 
1.4.1  算法的定义及特性
算法(Algorithm)是为了解决某类问题而规定的一个有限长的操作序列。
一个算法必须满足以下五个重要特性:
   (  1 )有穷性 。一个算法必须总是在执行有穷步后结束，且每一步都必须在有穷时间内完成。
   (  2 )确定性 。算法中的相关操作都要有确切的规定，不会产生二义性。
   (  3 )可行性 。算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。
   (  4 )输入 。一个算法有零个或多个输入。
   (  5 )输出 。一个算法有零个或多个输出。
 
1.4.2  评价算法优劣的基本标准
一个算法的优劣应由下面几方面来评价:
   (  1 )正确性 。在输入合理数据的情况下，能够在有限的运行时间内得到正确的结构。
   (  2 )可读性 。一个好的算法，应便于人们理解和相互交流，其次才是机器可执行性。
   (  3 )健壮性 。输入数据非法时，好的算法能够做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。
   (  4 )高效性 。高效性包括时间和空间两个方面。时间高效指执行效率高，空间高效指占用存储容量合理。
 
1.4.3  算法的时间复杂度(事前统计法)
 
算法中基本语句重复执行的次数是问题规模n的某个函数f(n)，算法的时间量度记作 :
                                               T(n) = O(f(n))
(定义)它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称做算法的渐进时间复杂度，简称时间复杂度(Time Complexity)。
 
 
分析算法时间复杂度的基本方法为 :①找出所有语句中语句频度最大的那条语句作为基本语句；②计算基本语句的频率得到问题规模n的某个函数f(n)；
③取其数量级用"O"表示即可。
 
常见的时间复杂度按数量级递增排列依次为: 常量阶O(1)、对数阶O(log2n)、线性阶O(n)、线性对数阶O(nlog2n)、平凡阶O(n²)、立方阶O(n³)、...
、k次方阶O(n^k)、指数阶O(2^n)等。