绪论

算法+数据结构=程序设计

  • 程序设计：为计算机处理问题编制一组指令集
  • 算法：处理问题的策略
  • 数据结构：问题的数学模型

数据结构的定义

  • 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。

基本概念和术语

  1. 数据与数据结构
  • 数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中 并被计算机程序处理的 符号 的总称。 它是计算机程序加工的“原料”。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；一个编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归之于数据的范畴。
  • 数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。（视频中的描述：数据中的一个“个体” ，数据结构中讨论的基本单位，但不是最小单位，因为数据元素可以是一个简单的整数字符，也可以复杂到由多个数据项组成，因此，数据元素是数据项的集合）
  • 数据项：（视频：数据结构中讨论的最小单位）数据的不可分割的最小单位。
  • 数据对象：性质相同的数据元素的集合，是数据的一个子集。
  • 数据结构：（视频：带结构的数据元素的集合）相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。
  • 根据数据元素之间关系的不同特性，通常有下列4类基本结构：
    1. 集合 结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系（这和数学中的集合概念是一致的）。
    2. 线性结构 结构中的数据元素之间存在一个对一个的关系。
    3. 树形结构 结构中的数据元素之间存在一个对多个的关系。
    4. 图状结构或网状结构 结构中的数据元素之间存在多个对多个的关系。
    • 由于“集合”是数据元素之间关系极为松散的一种结构，因此也可用其他结构来表示它。
  • 数据结构的形式定义为：数据结构是一个二元组 Data_Structure = (D,S) ，其中：D是数据元素的有限集，S是D上 关系的有限集。
  • 上述数据结构的定义仅是对操作对象的一种数学描述，换句话说，是从操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构。然而，讨论数据结构的目的是为了在计算机种实现对它的操作，因此还需研究如何在计算机中表示它。
  1. 存储结构
  • （视频：数据的存储结构——逻辑结构在存储器中的映像）数据结构在计算中的表示（又称映像）称为数据的物理结构，又称存储结构。它包括数据元素的表示和关系的表示。
  • 数据元素的表示:
    • 在计算机中表示信息的最小单位是二进制数的一位，叫做位。
    • 在计算机中，我们可以用一个由若干位组合起来形成的一个位串表示一个数据元素，通常称这个位串为元素或结点。
    • 当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域。
    • 因此，元素或结点可看成是数据元素在计算机中的映像。
  • 关系的表示：
    • 两种表示方法：顺序映像和非顺序映像
    • 由此得到两种存储结构：顺序存储结构和链式存储结构
    • 顺序映像：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。
    • 非顺序映像：借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
  • 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。
  • （视频：在不同的编程环境中，存储结构有不同的描述方法。当用高级程序设计语言进行编程时，通常可用高级编程语言中提供的数据类型描述之。）
  1. 数据类型
  • （视频：在用高级程序语言编写的程序中，必须对程序中出现的每个变量、常量或表达式，明确说明它们所属的数据类型。）
  • 数据类型是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画（程序）操作对象的特性。在用高级程序设计语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。因此 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。例如，C语言中的整型变量，其值集为某个区间上的整数（区间大小依赖于不同的机器），定义在其上的操作为加、减、乘、除和取模等算术运算。
  • 按“值”的不同特性，高级程序设计语言中的数据类型可分为两类：一类是非结构的原子类型。原子类型的值是不可分解的，例如C语言中的基本类型（整型、实型、字符型和枚举类型）、指针类型和空类型。另一类是结构类型。结构类型的值是由若干成分按某种结构组成的，因此是可分解的，并且它的成分可以是非结构的，也可以是结构的。例如数组的值由若干分量组成，每个分量可以是整数，也可以是数值等。在某种意义上，数据结构可以看成是“一组具有相同结构的值”，则结构类型可以看成由一种数据结构和定义在其上的一组操作组成。
  • 实际上，在计算机中，数据类型的概念并非局限于高级语言中，每个处理器（包括计算机硬件系统、操作系统、高级语言、数据库等）都提供了一组原子类型或结构类型。例如，一个计算机硬件系统通常含有“位”“字节”“字”等原子类型，它们的操作通过计算机设计的一套指令系统直接由电路系统完成，而高级程序语言提供的数据类型，其操作需通过编译器或解释器转化成低层，即汇编语言或机器语言的数据类型来实现。引入“数据类型”的目的，从硬件角度看，是作为解释计算机内存中信息含义的一种手段，而对使用数据类型的用户来说，实现了信息的隐蔽，即 将一切用户不必了解的细节 都封装在类型中。例如，用户在使用“整数”类型时，既不需要了解“整数”在计算机内部是如何表示的，也不需要知道其操作是如何实现的。如“两整数求和”，程序设计者注重的仅仅是其“数学上求和”的抽象特性，而不是其硬件的“位”操作如何进行。
  1. 抽象数据类型
  • 抽象数据类型（abstract data type，简称ADT）是指一个数学模型以及定义在该模型上的一组操作。抽象数据类型的定义取决于它的一组逻辑特性，而与其在计算机内部如何表示和实现无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部的使用。
  • （视频：ADT有两个重要特征：
    1. 数据抽象 用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（外界使用它的方法）。
    2. 数据封装 将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节。
  • 抽象数据类型比数据类型的范畴更广，它不再局限于固有数据类型，还包括用户在设计软件系统时自己定义的数据类型。
  • 一个含抽象数据类型的软件模块通常应包含定义、表示和实现3个部分。
    1. 定义
    • 如前所述，抽象数据类型的定义有一个值域和定义在该值域上的一组操作组成。若按其值的不同特性，可细分为下列3种类型：
      1. 原子类型 属原子类型的变量的值时不可分解的。这类抽象数据类型较少，因为一般情况下，已有的固有数据类型足以满足需求。但有时也有必要定义新的原子数据类型，例如数位为100的整数。
      2. 固定聚合类型 属该类型的变量，其值由 确定数目的成分 按 某种结构 组成。例如，复数是由两个实数依确定的次序关系构成的。
      3. 可变聚合类型 和固定聚合类型相比较，构成可变聚合类型“值”的成分的数目不确定。例如，可定义一个“有序整数序列”的抽象数据类型，其中序列的长度是可变的。
      • 显然，后两种类型可统称为结构类型。
    • 和数据结构的形式定义相对应，抽象数据类型可用以下三元组表示 (D,S,P) 。其中，D是数据对象，S是D上的 关系集，P是对D的 基本操作集。
    • 多形数据类型是指其值的成分不确定的数据类型。从抽象数据类型的角度看，具有相同的数学抽象特性，故称之为多形数据类型。
    1. 表示和实现
    • 抽象数据类型可通过固有数据类型来表示和实现，即利用处理器中已存在的数据类型来说明新的结构，用已经实现的操作来组合新的操作。

算法和算法分析

  • 算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作；此外，一个算法还具有下列5个重要特性：
    1. 有穷性 一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内（一个简单的程序不可以执行三天三夜）完成。
    2. 确定性 算法中每一条指令必须有确切的含义，读者理解时不会产生二义性。并且，在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。
    3. 可行性 一个算法是能行的，即算法中描述的操作都是已经实现的基本运算执行有限次来实现的。
    4. 输入 一个算法有0个或多个的输入，这些输入取自于某个特定的对象的集合。
    5. 输出 一个算法有1个或多个的输出，这些输出是同输入有着某些特定的关系的量。
  • 算法设计的要求
    通常设计一个“好”的算法应考虑达到以下目标。
    1. 正确性 算法应当满足具体问题的需求。
    • 首先，算法应当满足以特定的“规格说明”方式给出的需求。
    • 其次，对算法是否“正确”的理解可以有以下四个层次：
      a. 程序中不含语法错误；
      b. 程序对于几组输入数据能够得出满足规格说明要求的结果；
      c. 程序对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；
      d. 程序对于一切合法的输入数据都能产生满足规格说明要求的结果。
      （通常以第c层意义的正确性作为衡量一个程序是否合格的标准。）
    1. 可读性 算法主要是为了人的阅读与交流，其次才是机器执行。可读性好有助于人对算法的理解；另一方面，晦涩难懂的程序易于隐藏较多错误，难以调试和修改。
    2. 健壮性 当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。并且，处理出错的方法应是返回一个表示错误或错误性质的值，而不是打印错误信息或异常，并中止程序的执行，以便在更高的抽象层次上进行处理。
    3. 效率与低存储量需求 通俗地说，效率指的是算法执行的时间。对于同一个问题如果有多个算法可以解决，执行时间短的算法效率高。存储量需求指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。（因为：求100个人的平均分与求1000个人的平均分所花的执行时间或运行空间显然有一定的差别。）
  • 算法效率的度量
    度量一个程序的执行时间通常有两种方法：
    1. 事后统计的方法 （让算法变成一个程序，在机器上执行并计时）
      缺点：
      (1) 必须执行程序
      (2) 其他因素掩盖算法本质
    2. 事前分析估算的方法（通常使用的）
      和算法执行时间相关的因素：
      (1) 算法选用的策略
      (2) 问题的规模
      (3) 编写程序的语言
      (4) 编译程序产生的机器代码的质量
      (5) 机器执行指令的速度
      （后三条和计算机的软件和硬件有关，和设计算法无关，所以设计算法时只考虑前两条）
    • 所以 算法的执行时间 是 问题规模 的函数。我们称算法执行时间为一个特定算法的“运行工作量”，只依赖于问题的规模的大小。
    • 算法的时间量度记作 T(n)=O(f(n))，表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同（算法是f(n)这个函数数量级的），称作算法的渐进时间复杂度，简称时间复杂度。
    • 算法=控制结构（顺序、分支和循环3种）+原操作（指固有数据类型的操作）
    • 算法的执行时间=Σ原操作(i)的执行次数×原操作(i)的执行时间
    • （原操作的执行时间对于不同的算法来说都是一个定值，因此我们在估计算法的时候，往往把它忽略掉了，所以）算法的执行时间 和 原操作的执行次数之和 成正比。
    • 从算法中选取一种对于所研究的问题来说是基本操作的原操作，以该基本操作在算法中重复执行的次数作为算法运行时间的衡量准则。
    • 算法的空间复杂度：S(n)=O(g(n))
    • 算法的存储量包括：
      1. 输入数据所占空间
      2. 程序本身所占空间
      3. 辅助变量所占空间
    • 若输入数据所占空间只取决于问题本身，和算法无关，则只需要分析除输入和程序之外的辅助变量所占额外空间。
    • 若所需额外空间相对于输入数据量来说是常数，则称此算法为原地工作。
    • 若所需存储量依赖于特定的输入，则通常按最坏情况考虑。

线性表

线性结构的特征

  • 线性结构是一个数据元素的有序集。

    注意这里的“有序集”指的是次序上的有序，而不是数值上的有序。

  • 线性结构的基本特征：
  1. 集合中必存在唯一的一个“第一元素”。
  2. 集合中必存在唯一的一个“最后元素”。
  3. 除最后元素之外，均有唯一的后继。
  4. 除第一元素之外，均有唯一的前驱。

这里开始讲算法，感觉质量不高，不想看视频也不记笔记了。因为前边概念部分，教材写得很长又很乱，就想看看作者对此是怎么解释的，因此上面的笔记即为绪论部分的解释，若有不懂的地方可以来回顾这些笔记看看作者对概念的解释。不过对比了一下王道的概念，貌似讲得还算清楚；那就结合王道和以上笔记，以及书本内容，对概念重新理解一下吧。