数据结构第一章：绪论

Abstract：今天《数据结构》开课，本文是第一章绪论的笔记。

什么是数据结构

• 计算机中存储和组织数据的方式，意味着接口或封装：一个数据结构可被视为两个函数之间的接口，或者是由数据类型联合组成的存储内容的访问方法封装。
  • why接口：设计出DS封装成接口，以不同的应用程序能够安全地重用这些DS
  • 一个设计良好的数据结构，应该在尽可能使用较少的时间与空间资源的前提下，为各种临界状态下的运行提供支持。数据结构可通过编程语言所提供的数据类型、引用及其他操作加以实现。
  • 系统构造的关键因素是数据结构而非算法
• 相互之间存在一种或多种特定关系的数据元素的集合，数据元素间的关系为结构。
• 程序设计 = 数据结构 + 算法

基本概念和术语

• 数据data：所有能输入到计算机中并被计算机程序加工、处理的符号的总称; 如整数、实数、字符串、图像、声音等。信息的载体，它能够被计算机识别、存储和加工处理。
• 数据元素data element：数据的基本单位（元素、记录、结点、顶点），在计算机程序中通常作为一个整体进行考虑和处理。
• 数据项data item：一个数据元素可由若干个数据项组成，数据项是数据的不可分割的最小单位。如：姓名、年龄等；
  • 初等项：不可分割，如性别、籍贯
  • 组合项：可分割，如学生成绩可划分为数学、物理、语文等
• 数据对象data object：由性质/类型相同的数据元素组成的集合；是数据的一个子集。
• 数据结构data structure：相互之间存在一种或多种特定关系的数据元素的集合。数据元素间的关系为结构。四类基本结构：集合（元素同属于一个集合的关系），线性结构（一对一的关系），树状结构（一对多的关系）和图状结构（多对多的关系）。
• 数据的逻辑结构：各元素间的逻辑关系，可以看作是从具体问题抽象出来的数学模型
• 物理结构：指数据的逻辑结构在计算机中的存储形式；逻辑结构面向问题，物理结构面向计算机，其基本目标是将数据及其逻辑关系存储到计算机的内存中。研究的是数据结构在计算机中的实现方法，包括数据结构中元素的表示及元素间关系的表示。

• 数据的存储结构：数据结构在计算机存储器中的映象(mapping)；存储结构也称为：存储表示,物理结构,物理表示。
• 结点/元素：计算机中由若干位bit组成的一个位串表示一个元素，这个位串即元素或结点（node）。

顺序存储结构：用元素在存储器中的物理相对位置来表示数据元素之间的逻辑关系。
非顺序/链式存储结构：用指示元素存储地址的指针表示数据元素间的逻辑关系；把数据元素存放在任意的存储单元里，这组存储单元可以是连续的也可以是不连续的。数据元素的存储关系不反映其逻辑关系，用指针存放数据元素的地址，我们通过地址可以找到相关联数据元素的位置。【即逻辑相邻的元素物理位置任意，以指针地址寻访相关联元素】如：

• 数据类型data type：是一个值的集合和定义在这个值上的一组操作的总称。
• 抽象数据类型(Abstract Data Type):与计算机的实现无关的数据类型，指一个数学模型以及定义在该模型上的一组操作，其定义只取决于它的一组逻辑特性，与其在计算机内部如何表示和实现无关。一个抽象数据类型定义了一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。

抽象数据类型（Abstract Data Type, ADT）可用三元组表示（D，S，T）：
ADT抽象数据类型名{
数据对象：（数据对象的定义）
数据关系：（数据关系的定义）
基本操作：（基本操作的定义）
}

基本操作的定义格式：
基本操作名（参数表）
初始条件：（初始条件描述）
操作结果：（操作结果描述）

• 数据结构的层次：

C语言核心子集

• 预定义变量和类型：#define
• typedef表示数据结构，元素类型为ElemType

基本操作语句

• 赋值
• 选择：if …else; switch…case…default
• 循环：for; while; do…while
• 结束：return (函数结束语句)；break（case结束）；exit（异常结束）
• 输入输出：scanf([格式串]，变量1，…，变量n)；printf
• 注释：//
• 基本函数：max;min;abs; floor; ceil; eof; eoln
• 逻辑运算约定：&&；||

算法Algorithm和算法分析

定义：对特定问题求解步骤的描述。

算法的描述工具：自然语言；程序设计语言（C）；流程图；伪码语言；类C；

算法的时间复杂度

• 是什么：算法中基本操作重复执行的次数的总和
• 语句频度：所有语句的执行次数f(n)
• 时间复杂度：T(n)=O(f(n))
• 根据时间复杂度衡量算法效率的前提是：针对同一问题
• 算法改进

举例：冒泡排序的C语言算法

算法的存储空间需求

• 空间复杂度S(n) = O(f(n));

程序运行所需的存储空间包括以下两部分：

• ⑴固定部分。这部分空间与所处理数据的大小和个数无关，或者称与问题的实例的特征无关。主要包括程序代码、常量、简单变量、定长成分的结构变量所占的空间。

• ⑵可变部分。这部分空间大小与算法在某次执行中处理的特定数据的大小和规模有关。例如100 个数据元素的排序算法与1000 个数据元素的排序算法所需的存储空间显然是不同的。

其他

学习目的

学习数据结构的目的是为了了解计算机处理对象的特性，将实际问题中所涉及的处理对象在计算机中表示出来并对它们进行处理。

课程内容

数据结构课程内容体系：三个层次五个要素

核心技术：分解和抽象

1.抽象层次：

从具体（即具体问题）到抽象（即数据结构）的过程

• 数据表示
  • 通过分解：划分出数据的三个层次
  • 通过抽象：舍弃数据元素的具体内容，得到逻辑结构
• 数据处理
  • 通过分解：将处理要求划分为各种功能
  • 通过抽象：舍弃实现细节，得到运算的定义

2.实现层次：

从抽象（即数据结构）到具体（即具体实现）的过程

• 通过增加对实现细节的考虑进一步得到存储结构和实现运算，从而完成设计任务

抽象数据类型

1.数据类型：

• 原子类型：不可分解，如int，float，string
• 结构类型：由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的

在某种意义上，数据结构可以看成是“一组具有相同结构的值”，而数据类型则可被看成是由一种数据结构和定义在其上的一组操作所组成的。

2.抽象数据类型 ~ 数据类型:

• 一个数学模型以及定义在该模型上的一组操作
• 定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关。即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
• 特征是使用与实现相分离，实行封装和信息隐蔽

算法与算法分析

算法与数据结构的关系紧密，在算法设计时先要确定相应的数据结构，而在讨论某一种数据结构时也必然会涉及相应的算法。下面就从算法特性、算法描述、算法性能分析与度量等三个方面对算法进行介绍。

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

• 算法必须具备的特性：

  • ⑴有穷性。一个算法必须在有穷步之后结束，即必须在有限时间内完成。
  • ⑵确定性。算法的每一步必须有确切的定义，无二义性。算法的执行对应着的相同的输入仅有唯一的一条路经。
  • ⑶可行性。算法中的每一步都可以通过已经实现的基本运算的有限次执行得以实现。
  • ⑷输入。一个算法具有零个或多个输入，这些输入取自特定的数据对象集合。
  • ⑸输出。一个算法具有一个或多个输出，这些输出同输入之间存在某种特定的关系。

• 一个算法若用程序设计语言来描述，则它就是一个程序

• 好算法：正确，可读，健壮（当输入不合法数据时，应能作适当处理，不至引起严重后果），高效

当我们将一个算法转换成程序并在计算机上执行时，其运行所需要的时间取决于下列因素：

• ⑴硬件的速度。例如使用486 机还是使用586 机。
• ⑵书写程序的语言。实现语言的级别越高，其执行效率就越低。
• ⑶编译程序所生成目标代码的质量。对于代码优化较好的编译程序其所生成的程序质量较高。
• ⑷问题的规模。例如，求100 以内的素数与求1000 以内的素数其执行时间必然是不同的。

*在各种因素都不能确定的情况下，很难比较出算法的执行时间, 但可算出时间复杂度/问题规模*。也就是说，使用执行算法的绝对时间来衡量算法的效率是不合适的。为此，可以将上述各种与计算机相关的软、硬件因素都确定下来，这样一个特定算法的运行工作量的大小就只依赖于问题的规模（通常用正整数n 表示），或者说它是问题规模的函数。

错题

• 数据的运算与采用何种存储结构有关
• 算法必须具备：输入，输出，可行性，有穷性，确定性
• 算法的时间复杂度为O(n2)，表明该算法的执行时间与成正比
• 【误！】在相同的问题规模下n下，时间复杂度为O(nlog2n)的算法在执行时间上总是优于时间复杂度为O()的算法
• 简单的嵌套循环的时间复杂度一般为O(n^2)
• 程序与算法：程序不一定是算法，算法不一定是程序