第一章 数据结构与算法

算法

算法基本特征

• 算法：是指解题方案的准确而完整的描述（算法不等于程序）

  • 可行性：在设计一个算法时，必须考虑可行性
  • 确定性：算法中的每一个步骤必须是明确定义的，不可以是模凌两可
  • 有穷性：必须在有限的时间内完成
  • 足够的情报：是指算法要有一定的输入数据和必要的输出结果

算法的基本要素

• 对数据对象的运算和操作：

  • 算术运算、逻辑运算、关系运算、数据传输

• 算法的控制结构：

  • 算法中各操作之间的执行顺序；
  • 描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等；
  • 一个算法一般可以用顺序、选择、循环三种基本结构组合而成

时间和空间复杂度

• 算法的时间复杂度：是指执行算法所需要的计算工作量，可以用算法所执行的基本运算次数度量。（选择题）**
• 算法的空间复杂度：是指执行算法所需要的内存空间。包括算法程序、输入的初始数据以及算法执行过程中需要的额外空间。**
• 算法的时间复杂度和算法的空间的复杂度相互独立

数据结构的基本概念

数据结构

• 数据：需要处理的数据元素的集合，一般来说，这些数据元素，具有某个共同的特征

  • 数据元素是数据的基本单位，即数据集合的个体
  • 有时一个数据元素可由数据项（Data Item）组成。数据项是数据的最小单位
• 结构：所谓“结构”，是集合各个数据元素之间存在的某种关系（或联系）
• 数据结构：是指相互有关联的数据元素的集合

• 数据结构的分类

  • 逻辑结构

    • 定义：指反映数据元素之间的逻辑关系（即前后件关系）的数据结构

      • demo：早餐———中餐———晚餐

    • 线性结构：线性表，栈，队列

      • 有且只有一个根结点，它无前件
      • 每一个节点最多有一个前件，也最多一个后件

    • 非线性结构：树形结构、网状结构

      • 不满足以上两个条件的结构就是非线性结构

  • 存储结构

    • 定义：数据的物理结构，是数据的逻辑结构在计算机存储空间中的存放方式

    • 顺序存储

      • 这种存放的方式主要用于线性的数据结构，它把逻辑上相邻的数据元素存储在物理上相邻的存储单位元里

    • 链式存储

      • 每一个节点至少包含一个指针域，用指针的指向来体现数据元素之间在逻辑上的联系
    • 1、一种逻辑结构可以有多种存储结构
    • 2、不同的存储结构其处理数据的效率是不同的

  • 运算

    • 插入，删除，查找，排序

线性表以及顺序存储结构

线性表

• 线性表是n（n>=0）个数据元素构成的有限序列，表中除第一个元素外的每一个元素，有且只有一个前件，除最后一个元素外，有且只有一个后件

  • 例如：

    • 1、英文字母
    • 2、地理学中的四向
    • 3、表格

线性表的顺序存储结构

• 通常，线性表看可以采用顺序存储和链式存储，但一般使用顺序存储结构。

• 线性表的顺序存储又叫做顺序表

  • 特点：

    1. 线性表中所有元素所占的存储空间是连续的；
    2. 线性表中数据元素在存储空间中是按逻辑顺序依次存放的；
    3. 可以随机访问数据元素；
    4. 做插入、删除时需要移动大量元素，因此线性表不便于插入与删除元素。

栈和队列

栈

• 栈是限定在一端进行插入和删除的线性表

  1. 栈是只能在栈顶进行插入和删除
  2. 栈的修改原则是“先进后出”或者“后进先出”**
  3. 栈底指针不变，栈中元素随栈顶指针的变化而动态变化**
  4. *栈具有记忆功能*
  5. *栈支持子程序调用*

队列

• 队列是指允许在一端进行插入，而在另一端进行删除的线性表。原则是：先进先出（或后进后出）

• 特点

  1. 队列只允许在队尾进行插入，而在对头进行删除。
  2. 队列的修改原则是“先进先出”或“后进后出”
  3. 队列中元素随队头指针和队尾指针的变化而动态改变

循环队列

• 循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间。

  1. rear > fornt
        s = rear - fornt
  2. rear < fornt
        s = 容量 + rear - fornt
  3. rear = fornt
        s = 1 或者 s = 0

线性链表

线性链表的定义

线性链表的特点

1. 各数据结点的存储空间可以不连续
2. 各数据元素的存储顺序与逻辑顺序可以不一致
3. 线性表的链式存储所占存储空间大于顺序存储结构
4. 查找结点时链式存储结构要比顺序存储慢
5. 链式存储插入删除元素比顺序存储灵活

线性链表的操作

• 在线性链表中进行插入与删除，不需要移动链表中的元素

线性表

• 线性表顺序存储结构
• 线性链表存储结构
• 双向链表
• 循环链表

树与二叉树 ⭐️⭐️⭐️⭐️⭐️

树

• 树是n（n>0）个元素的有限集合。它有且仅有一个成为根的元素；其余元素是互不相交的子树。

• 常用术语

  1. 父结点、子结点
  2. 根结点、叶子结点
  3. 结点的度（拥有的子结点数）、树的度（结点拥有最多的那个度）
  4. 树的深度（层数）
  5. 子树

二叉树

• 二叉树：是一个有限的集合，该集合或者为空，或者由一个根结点及两颗互不相交的左右二叉子树所组成。

• 二叉树具有以下两个特点：

  1. 非空二叉树只有一个根结点
  2. 每一个结点最多有两颗子树，且分别称为该结点的左子树与右子树。

特殊二叉树

• 满二叉树：除最后一层外，每一层上的结点数均达到最大值。
  
• 完全二叉树：除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点。
  
• 满二叉树是完全二叉树，完全二叉树不是满二叉树

二叉树的性质 ⭐️⭐️⭐️

• 非空二叉树只有一个根结点，每个结点最多有两棵树，分别称为左子树和右子树。

  1. 在二叉树的第k层上，最多有2^{k-1}个结点

1. 深度为m的二叉树最多有2^m-1个结点
2. 度为0的结点（叶子结点）总比度为2的结点多一个
3. *有n个结点的二叉树深度至少为[log_2n]+1*

二叉树的遍历 ⭐️⭐️⭐️

1. *前序遍历（步骤）根左右*

   1. 访问根结点
   2. 前序遍历左子树
   3. 前序遍历右子树

2. *中序遍历（步骤）左根右*

   1. 中序遍历左子树
   2. 访问根结点
   3. 中序遍历右子树

3. *后序遍历（步骤）左右根*

   1. 后序遍历左子树
   2. 后序遍历右子树
   3. 访问根结点

查找技术

顺序查找

• 顺序查找：对于长度为n的线性表，平均要进行n/2次比较，在最坏情况下进行n次比较。
• 顺序查找适用于无序表活链式线性表（无论是有序还是无序）

二分查找

• 二分查找：适用于顺序存储的有序表，对长度为n的线性表，在最坏情况下进行log_2n**次比较。
  
• 注意：即使是有序线性表，如果采用链式存储结构，也只能用顺序查找

排序技术

排序

• 记住最坏情况 ⭐️⭐️

快速排序

• 基本思想

  1. 在要排序的序列中找一个数作为基准数（通常为第一个数）
  2. 通过交换将这个序列中所有比基准数大的数放在右边，比基准数小的数放在左边。
  3. 以基准数为分割线分为两个子表，对两个子表重复上述步骤

第一章总结