编程菜鸟到大佬之路：数据结构（一）

数据结构C++版——邓俊辉课堂笔记

第一章 绪论

---

计算机与算法

• 计算机科学的核心在于研究计算方法与过程的规律，而不仅仅是作为计算工具的计算机本身，因此E. Dijkstra及其追随者更倾向于将这门科学称作计算科学（ computing science）。

• 起泡排序

  • D. Knuth曾指出，四分之一以上的CPU时间都用于执行同一类型的计算——按照某种约定的次序，将给定的一组元素顺序排列，比如将n个整数按通常的大小次序排成一个非降序列。 这类操作统称排序（sorting）。
  • 局部有序与整体有序
    • 在由一组整数组成的序列A[0, n - 1]中，满足A[i−1]⩽A[i]的相邻元素称作顺序的，否则是逆序的。
    • 有序序列中每一对相邻元素都是顺序的，对任意1⩽i<n都有A[i−1]⩽A[i]；反之，所有相邻元素均顺序的序列，也必然整体有序。
  • 扫描交换
    • 由有序序列的上述特征，我们可以通过不断改善局部的有序性实现整体的有序——从前向后依次检查每一对相邻元素，一旦发现逆序即交换二者的位置。
    • 对于长度为n的序列，共需做n - 1次比较和不超过n - 1次交换，这一过程称作一趟扫描交换。
    • 经过这样的一趟扫描，序列未必达到整体有序。果真如此，则可对该序列再做一趟扫描交换 。事实上，可能需要反复进行多次扫描交换， 在序列中不再含有任何逆序的相邻元素。
    • 多数的这类交换操作，都会使得越小（大）的元素朝上（下）方移动，直至它们抵达各自应处的位置。
  • 整数数组的起泡排序
    • 排序过程中， 所有元素朝各自最终位置亦步亦趋的移动过程，犹如气泡在水中的上下沉浮，起泡排序（bubblesort） 算法也因此得名。

      void bubblesort1A(int A, int n)     // 起泡排序算法（版本1A）： 0 <= n
      {
          bool sorted = false;      // 整体排序标志，首先假定尚未排序
          while (!sorted)     // 在尚未确认已全部排序之前，逐趟进行扫描交换
          {
              sorted = true;      // 假定已经排序
              for (int i = 0; i < n - 1; ++i)      // 自左向右逐对检查范围A[0, n)内各相邻元素
              {
                  if (A[i] > A[i+1])
                  {                s
                      swap(A[i], A[i+1]);
                      // 一旦A[i]和A[i+1]逆序，则交换，因整体排序不能保证，需要清除排序标志
                      sorted = false;
                  }
              }
              n --;       // 至此末尾元素必然就位，故可以缩短待排序序列的有效长度
          }
      }       // 借助布尔型标志位sorted，可及时提前退出。
      

算法

• 所谓算法，是指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。

• 算法还应必须具备以下要素：

  • 输入与输出
    • 待计算问题的任一实例，都需要以某种方式交给对应的算法，对所求解问题特定实例的这种描述统称为输入（input）。
    • 经计算和处理之后得到的信息，即针对输入问题实例的答案，称作输出（output）。
    • 在物理上，输出有可能存放于单独的存储空间中，也可能直接存放于原输入所占的存储空间中。
  • 基本操作、确定性与可行性
    • 所谓确定性和可行性是指，算法应可描述为由若干语义明确的基本操作组成的指令序列，且每一基本操作在对应的计算模型中均可兑现。
  • 有穷性与正确性
    • 任意算法都应在执行有限次基本操作之后终止并给出输出，此即所谓算法的有穷
      性（finiteness）。
    • 算法不仅应该迟早会终止，而且所给的输出还应该能够符合由问题本身在事先确定的条件，此即所谓算法的正确性（correctness）。
    • 证明算法有穷性和正确性的一个重要技巧，就是从适当的角度审视整个计算过程，并找出其所具有的某种不变性和单调性。其中的单调性通常是指， 问题的有效规模会随着算法的推进不断递减。不变性则不仅应在算法初始状态下自然满足，而且应与最终的正确性相呼应，当问题的有效规模缩减到0时，不变性应随即等价于正确性。
    • 起泡排序算法的不变性和单调性可分别概括为： 经过k趟扫描交换之后，最大的前k个元素必然就位；经过k趟扫描交换之后，待求解问题的有效规模将缩减至n - k。
  • 退化与鲁棒性
    • 同一问题往往不限于一种算法，而同一算法也常常会有多种实现方式，因此除了以上必须具备的基本属性，在应用环境中还需从实用的角度对不同算法及其不同版本做更为细致考量和取舍。这些细致的要求尽管应纳入软件工程的范畴，但也不失为成熟算法的重要标志。
    • 比如其中之一就是，除一般性情况外，实用的算法还应能够处理各种极端的输入实例。算法所谓的鲁棒性（robustness） ，就是要求能够尽可能充分地应对此类情况。
  • 重用性
    • 从实用角度评判不同算法及其不同实现方式时，可采用的另一标准是：算法的总体框架能否便捷地推广至其它场合。
    • 算法模式可推广并适用于不同类型基本元素的这种特性，即是重用性的一种典型形式。