学习目录

程序=数据结构+算法

1.数据、数据元素、数据项和数据对象

2.数据结构

3.数据类型和抽象数据类型

4.算法及算法分析

---

学习内容

程序=数据结构+算法

数据结构如何用数据正确地描述现实世界的问题，并存入计算机

算法如何高效地处理这些数据，以解决实际问题

1.数据、数据元素、数据项和数据对象

（1）数据（Data）是客观事物的符号表示，是所有能输入计算机中并能够被计算机程序处理的符号的总称。如整数、实数、字符、字符串及多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。

（2）数据元素（Data Element）是数据的基本单位，数据元素用于完整地描述一个对象，如图中的一个顶点，树中棋盘的一个状态。

（3）数据项（Data Item）是组成数据元素的、有独立含义的、不可分割的最小单位。如学生表中的学生姓名，学号等都是数据项。

（4）数据对象（Data Object）是性质相同的数据元素的集合，是数据的一个子集。如C={‘A’,‘B’,‘C’,‘a’,‘b’,‘c’}。

2.数据结构

     含义数据结构是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结构”的数据元素的集合，“结构”指数据元素之间存在的关系。数据结构包括逻辑结构和存储结构。

（1）逻辑结构数据结构的逻辑结构有两个要素一是数据元素；二是关系，关系是指数据元素间的逻辑关系。根据数据元素之间关系的不同特性，数据的逻辑结构通常有

下面4种结构中所举的示例是以某班级学生作为数据对象（数据元素是学生的学籍档案记录），来分别考察数据元素之间的关系。

• 集合结构数据元素之间除了“属于同一集合”的关系外，别无其他关系。例如确定一名学生是否为班级成员，只需将班级看作一个集合结构。
• 线性结构数据元素之间存在一对一的关系。例如将学生信息数据按照其入学报到的时间先后顺序进行排列，将组成一个线性结构。
• 树结构数据元素之间存在一对多的关系。例如在班级的管理体系中，班长管理多个组长，每位组长管理多名组员，从而构成树结构。
• 图结构或网状结构数据结构之间存在多对多的关系。例如多位同学之间的朋友关系，任何两位同学都可以是朋友，从而构成图结构或网状结构。

其中，集合结构、树结构、图结构或网状结构都属于非线性结构。

线性结构线性表、栈和队列、字符串、数组、广义表；

非线性结构树结构（树和二叉树），图结构（无向图和有向图），集合结构。

 （2）存储结构数据对象在计算机中的存储结构表示称为数据的存储结构，也称为物理结构。数据的存储结构分为

• 顺序存储结构是把逻辑上相邻的结点存储在物理上相邻的存储单元里，结点之间的关系有存储单元的邻接关系来体现。其优点是占用最少的存储空间；其缺点是由于只能使用相邻的一整块存储单元，可能产生较多的碎片现象。
• 链式存储结构将结点所占的存储单元分为两部分，一部分存放结点本身的信息，即为数据项；另一部分存放该结点的后继结点所对应的存储单元的地址，即为指针项。其优点是不会出现碎片现象，充分利用所有的存储单元；其缺点是每个结点占用较多的存储空间。
• 索引存储结构用结点的索引号来确定结点的存储地址。其优点是检索速度快。其缺点是增加了附加的索引表，会占用较多的存储空间；在增加和删除数据时由于要修改索引表因而会花费较多时间。
• 散列存储结构根据结点的值确定它的存储结构。其优点是检索、增加和删除结点的操作都很快；其缺点是采用不好的散列函数时可能会出现结点存储单元的冲突，为解决冲突需要附加的时间和空间开销。

若采用顺序存储结构，则各个元素在物理上必须是连续的；若采用非顺序存储结构，则各个元素在物理上可是是离散的。

数据的存储结构会影响存储空间分配的方便程度。

数据的存储结构会影响对数据运算的速度。

（3）数据运算施加于数据的操作。如对一张表格的查找、增加、修改、删除记录的工作。运算不仅仅是加减乘除，还包括算法。算法的实现是与数据的存储结构密切相关的。

运算的定义是针对逻辑结构的，指出运算的功能；运算的实现是针对存储结构的，指出运算的具体操作步骤。

3.数据类型和抽象数据类型

（1）数据类型是一个值的集合和定义在此集合上的一组操作的总称。

• 原子类型其值不可再分的数据类型。布尔类型TRUE，FALSE，可进行操作与、或、非...；int类型-2147483648~2147483647，可进行操作加、减、乘、除、模运算...
• 结构类型其值可以再分解为若干成分（分量）的数据类型。如结构体

（2）抽象数据类型（ADT）一般指用户定义的、表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称，具体包括3个部分数据对象、数据对象上关系的集合以及对数据对象的基本操作的集合。

定义一个抽象数据类型就是在“定义”一种数据结构；确定了抽象数据类型的存储结构，才能“实现”这种数据结构。

4.算法及算法分析

（1）算法的定义为解决某类问题而规定的一个有限长的操作序列。（换一种说法则是对特定问题求解步骤的一种描述）例如要解决的问题是做番茄炒蛋，食材则是数据结构，步骤则为算法。

（2）算法的特性

• 有穷性一个算法必须总是在执行有穷步骤后结束，且每一步都必须在有穷时间内执行。注算法必须是有穷的，而程序可以是无穷的。
• 确定性算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。
• 可行性算法中的所有操作都可以通过将已经实现的基本操作运算执行有限次来实现。
• 输入一个算法有0个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主函数获得输入值。
• 输出一个算法有1个或多个输入。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

算法可以没有输入但一定要有输出。

（3）“好”算法的特性

• 正确性在有限的运行时间内得到正确的结果。
• 可读性便于人们理解，如注释。
• 健壮性当输入非法数据时，算法能适当的做出反应或进行处理，而不会产生莫名其妙的输出结果。
• 高效性高效率（花的时间少，时间复杂度低）与低存储量需求（不费内存，空间复杂度低）

（4）时间复杂度O(f(n))

衡量算法效率的方法有事后统计法和事前分析估算法（常用）

问题规模不考虑计算机的软硬件等环境因素，影响算法时间代价的最主要因素是问题的规模。

语句频度一条语句重复执行的次数

一个算法的执行时间大致上等于其所有语句执行时间的总和，而语句的执行时间则为该条语句的重复执行次数和执行一次所需时间的乘积。

常见的时间复杂度按数量级递增排队一次为

如何计算步骤

• 找到一个基本操作(最深层循环)
• 分析该基本操作的执行次数 x 与问题规模 n 的关系 x=f(n)
• x的数量级 O(x)就是算法时间复杂度 T(n)

例:1常量阶示例

{
   x++;
   s=0;
}

两条语句频度均为 1，算法的执行时间是一个与问题规模 n 无关的常数，所以算法的时间复杂度为T(n)= O(1)，称为常量阶。

实际上，如果算法的执行时间不随问题规模n的增长而增长，算法中语句频度就是某个常数。即使这个常数再大，算法的时间复杂度都是O(1)。例如，对上面的程序进行如下改动:

for(i=0;i<10000;i++)
{
   x++;
   s=0;
}

算法的时间复杂度仍然为O(1)。

例2线性阶示例

for(i=0;i 
循环体内两条基本语句的频度均为n)=n，所以算法的时间复杂度为T)= O)，称为线性阶
 
例3平方阶示例
 
x=0；y=0；
for(k=1;k<=n;k++)
x++;
for(i=l;i<=n;i++)
for(j=1;j<=n;j++)
y++;
 

 对循环语句只需考虑循环体中语句的执行次数，以上程序段中频度最大的语句是(6)，其频度为(n)=n^2，所以该算法的时间复杂度为T(n)= O(n^2)，称为平方阶。
 例4立方阶示例
 
x=1;
for(i=l;i<=n;i++)
  for(j=l;j<=i;j++)
 for(k=1;k<=j;k++)
   x++;
 
则该算法的时间复杂度为T(n)= 0(n^3)，称为立方阶
 
例5对数阶示例
 
for（i=1;i<=n;i=i2）
{
  x++;
  s=0;
}
 
算法的时间复杂度为T(n)= O(log2^n)，称为对数阶。