第一章 数据结构与算法

算法

算法基本特征

  • 算法:是指解题方案的准确而完整的描述(算法不等于程序)

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

算法的基本要素

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

    • 算术运算、逻辑运算、关系运算、数据传输
  • 算法的控制结构

    • 算法中各操作之间的执行顺序;
    • 描述算法的工具通常有传统流程图、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. 每一个结点最多有两颗子树,且分别称为该结点的左子树与右子树。

image-20220216090507352

image-20220216090547790

特殊二叉树

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

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

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

    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. 访问根结点

查找技术

顺序查找

image-20220216101142084

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

二分查找

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

排序技术

排序

image-20220216101420434

  • 记住最坏情况 ⭐️⭐️

快速排序

  • 基本思想

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

第一章总结

image-20220216103712380

最后修改:2022 年 02 月 20 日
如果觉得我的文章对你有用,请随意赞赏