公共基础知识1.1

这是一个数据结构与算法的思维导图，从什么是算法、数据结构的基本概念、线性表及其顺序存储结构、线性链表、树与二叉树、查找技术、排序技术几个方面来介绍。

公共基础知识(1.1)

• 数据结构与算法
  • 什么是算法
    • 算法及其基本特征
      • 算法就是指对解题方案的准确而完整的描述
      • 基本特征
        • 可行性
          • 步骤可以实现；执行结果达到预期目的
        • 确定性
          • 步骤明确、不模棱两可、不准多义性
        • 有穷性
          • 有限的时间完成
        • 拥有足够的情报
          • 当提供的情报不够时，算法可能无效
    • 算法复杂度
      • 定义
        • 用来衡量算法优劣，包括算法的时间复杂度、算法的空间复杂度
      • 算法的时间复杂度
        • 执行算法所需要的计算工作量
        • 注：算法的时间复杂度≠算法程序执行的具体时间
          • 可以理解将算法的时间复杂度理解为计划时间
      • 算法的空间复杂度
        • 定义
          • 是指执行这个算法所需要的内存空间
        • 存储空间
          • 输入数据所占的存储空间
          • 程序本身所占的存储空间
          • 算法执行过程中所需要的额外空间
            • 算法执行过程中的工作单元
            • 某种数据结构所需要的附加存储空间
            • 注：若额外空间量不随问题规模的变化而变化，则称算法是原地工作的
          • 降低算法的空间复杂度
            • 主要应该减少输入数据所占的存储空间及额外空间
              • 通常采用压缩存储技术
  • 数据结构的基本概念
    • 什么是数据结构
      • 定义
        • 是指互相有关联的数据元素的集合（它包含数据和结构）
      • 数据的逻辑结构
        • 指反映数据元素之间逻辑关系（即前后件关系）的数据结构
      • 数据的存储结构（数据的物理结构）
        • 是数据的逻辑结构在计算机存储空间中的存放方式
    • 数据结构的表示
      • 数据的逻辑结构的数学形式定义
        • 数据结构是一个二元组
          • D=(D,R)
            • B表示数据结构
            • D是数据元素的集合
            • R是D上关系的集合，它反映了D中各数据之间的前后件关系
            • 例1:把一日三餐看作一个数据结构 则B=（D,R） D={早餐，午餐，晚餐} R={(早餐，午餐)，(午餐，晚餐)}
      • 图形表示
        • 例1：
          • 早餐
            • 数据节点（节点）
            • 午餐
              • 晚餐
      • 根节点
        • 数据结构中没有前件的节点
      • 终端节点（叶子节点）
        • 数据结构中没有后件的节点
      • 内部节点
        • 数据结构中除了根节点和终端节点以外的节点
    • 线性数据结构与非线性数据结构
      • 根据数据结构中各数据元素之间的前后件关系的复杂程度分类
      • 线性结构
        • 一个非空的数据结构
          • 空的数据结构即数据结构中没有数据元素
          • 有且只有一个根节点
          • 每一个节点最多只有一个前件，也最多只有一个后件
      • 非线性结构
        • 不满足线性结构的条件
        • 树形结构
        • 网状结构
  • 线性表及其顺序存储结构
    • 线性表的基本概念
      • 数据结构中，线性结构被称为线性表，线性表是最简单也是最常用的一种数据结构
      • 同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象
      • 例：数组、矩阵、向量
        • 线性表要么是空表，要么可表示为（a1，a2，a3…ai…an）（n≥0） 节点个数n表示为线性表的长度，当n=0时，称为空表
      • 非空线性表的的结构特点
        • 有且只有一个根节点
        • 每一个节点最多只有一个前件，也最多只有一个后件
    • 线性表的顺序存储结构
      • 顺序存储结构
        • 将线性表中的元素一个接一个地存储在一片相邻的存储空间
          • 这种顺序表示的线性表也称为顺序表
          • 顺序表特征
            • 线性表中所有元素所占的存储空间是连续的
            • 线性表中各数据元素在存储空间中是按逻辑顺序依次存放的
      • 链接存储结构
  • 栈和队列
    • 栈及其基本运算
      • 栈和一般线性表的实现方法类似，通常也可以采用顺序方式和链接方式
      • 定义
        • 栈是一种特殊的线性表，它所有的插入与删除都限定在表的同一端进行，允许插入和删除的一端称为栈顶，不允许删除和插入的一端称为栈底。当栈中没有元素时，称为空栈。
          • 类似于子弹上膛、卸弹
      • 栈的修改原则
        • "后进先出"或"先进后出"
      • 栈的基本运算
        • 入栈
        • 退站
        • 读栈顶元素
    • 队列及其基本运算
      • 定义
        • 是指允许在一端进行插入（队尾），而在另一端（队头或排头）进行删除的线性表
          • 
      • 队的修改原则
        • "先进先出"或"后进后出"
      • 循环列表及其运算
        • 在实际应用中，队列的顺序存储结构一般采用循环队列的形式
        • 定义
          • 将队列存储空间的最后一个位置绕到第一个位置， 形成逻辑上的环状空间，共队列循环使用。
            • 
        • 注：循环队列的初始状态为空，即front=rear=m
          • 当from=rear时，不能确定是队列满还是队列空， 在实际使用循环列表时，通常会加一个标志s来区 分队列满还是空。当s=0时表示队列空，当s=1时 表示队列满。
  • 线性链表
    • 线性链表的基本概念
      • 指线性表的链式存储结构，简称链表 这种链表每个节点只有一个指针域，又称为单链表
        •  在线性链表中，第一个元素没有前件，指向链表中的第一个节点的指针，是一个特殊的指针，称为这个链表的头指针（HEAD）。最后一个元素没有后件，因此，线性链表最后一个节点的指针域为空集，用NULL或0表示。 线性链表的存储单元是任意的，即各数据节点的存储序号可以是连续的，也可以是不连续的，各节点在存储空间中的位置关系与逻辑关系不一致，前后件关系由存储节点的指针来表示。指向第一个数据元素的头指针HEAD等于NULL或0时，称为空表。
    • 带链的栈
      • 
    • 带链的队列
      • 
    • 顺序表和链表的比较
      • 
    • 循环链表
  • 树与二叉树
    • 树的基本概念
      • 树是一种简单的非线性结构
        •  
      • 注：树的节点数等于树中所有节点的度之和加1
    • 二叉树及其基本性质
      • 二叉树的特点
        • （1）二叉树可以为空，空的二叉树没有节点，非空二叉树有且只有一个根节点。 （2）每个节点最多有两棵子树，即二叉树中不存在度大于2的节点。 （3）二叉树的子树有左右之分，其次序不能随意颠倒。
      • 二叉树的性质
        •  
      • 满二叉树和完全二叉树
        •   注：满二叉树一定是完全二叉树，完全二叉树一般不是满二叉树 完全二叉树的特点： （1）叶子节点只可能在最后两层出现 （2）对于任一节点，若其右子树的深度为m， 则该节点左子树的深度为m或为m+1
      • 二叉树的存储结构
        • 在计算机中，二叉树通常采用链式存储结构（二叉链表）。 用于存储二叉树中元素的存储节点由数据域和指针域两部分组成。 对于满二叉树和完全二叉树可以按层次进行顺序存储。
      • 二叉树的遍历
        • 若已知一棵二叉树的前序遍历序列和中序遍历序列，可以唯一确定这棵二叉树。 …………………………的后序遍历序列和中序遍历序列，可以………………………… …………………………的前序遍历序列和后序遍历序列，不可以………………………
        • 先左后右原则
        • 是指不重复地访问二叉树中所有节点
        • 前序遍历
          • A B D G E H C F I
        • 中序遍历
          • G D B E H A C F I
        • 后序遍历
          • 根节点一定在最后 左右子树均从深度大的转向深度小的
          • G D E H B I F C A
  • 查找技术
    • 顺序查找
      • 从线性表的第一个元素开始，逐个将线性表中的元素与被查元素进行比较
        • 最好情况 查1次 最坏情况 查n次 平均情况 查n/2次
      • 仅适用于顺序表的情况
        • 线性表为无序表
        • 线性表为有序表，采用链式存储结构
    • 二分法查找
      • 满足条件
        • 顺序存储结构
        • 线性表是有序表（元素按非递减排列）
      • 对于长度为n的有序线表，将查找元素X与中间项比较
        • 若X等于中间项的值，则查找成功。 若X小于中间项的值，则在线性表前半部分以二分法继续查找。 若X大于中间项的值，则在线性表后半部分以二分法继续查找。 注：每比较一次，可将查找范围缩小为原来的一半，故最坏情 况，需要次
  • 排序技术
    • 定义
      • 指将一个无序序列整理成按值非递减序列排列的有序序列
    • 交换类排序法
      • 交换类排序法基本思想：是借助数据元素的"交换"来进行排序的一种方法
      • 冒泡排序法
        • 在数据元素的序列中，对于某个元素，若其后存在一个元素小于它，则称之为存在一个逆序。 冒泡元素的基本思想就是通过两两相邻的数据元素之间比较和交换，不断消去逆序，知道所有元素有序为止。最坏情况，长度为n的线性表排列，次数为n（n-1）/2
      • 快速排序
        • 基本思想：在待排序的n个元素中取一个元素K（通常第一个元素），以元素K作为分割标准，把所有＜K的元素移到K前，把所有＞K的元素移到K后。以K为分界线，把线性表分成两个子表，这称为一趟排序。然后，对K前后的两个子表分别重复上述过程，直到分割的子表长度为1为止。 最坏情况，需要排n（n-1）/2次 ，但实际效率比冒泡排序高很多。
    • 插入类排序
      • 插入类排序基本思想：是每次将一个待排序元素，按其元素值的大小插入到前面已经排好序的子表中的适当位置，直到全部元素插入完成为止。
      • 简单插入排序法
        • 简单插入排序即把n个待排序的元素看成一个有序表和一个无序表，开始时，无序表只含有一个元素，而无序表包含n-1个元素，每次取无序表中的一个元素到有序表中的正确位置，当无序表为空时，排序完成。 最坏情况，需排序n（n-1）/2次
      • 希尔排序
        • 希尔排序的基本思想：先取一个整数（称为增量）d1<n，把全部元素分成d1个组，所有距离为d1倍数的元素放在一个组里，组成一个子序列，对每个子序列分别进行简单插入序列。然后取d2<d1，重复上述分组和排序工作，直到d1=1，即所有记录在一组为止。 希尔排序的效率与所选取的增量序列有关。最坏情况下，需要比较次。
    • 选择类排序法
      • 选择类排序的基本思想：通过每一趟从待排序序列中选择最小的元素，顺序放在已偶爱好虚的有序子表的后面，直到全部序列满足排序要求为止。
      • 简单选择排序法
        • 简单选择排序的基本思想：先从所有n个待排序的数据元素中选择最小的元素，将该元素与第1一个元素交换，再从剩下的n-1个元素中选出最小的元素与第2个元素交换。重复上述操作直到所有元素有序为止。 简单选择排序法在最坏情况下需要比较n（n-1）/2次
      • 堆排序法
        • 若有n个元素的序列（h1，h2，…，hn），将元素按顺序组成一棵完全二叉树，当且仅当满足下列条件时，称为堆。 [hi≥h2i，hi≥h（2i+1）]，或者[hi≤h2i，hi≤h（2i+1）]，其中，i=1、2、3，…，n/2 第一种情况称为大根堆，所有节点的值均大于等于左右子节点的值。 第二种情况称为小根堆，所有节点的值均小于等于左右字节点的值。 堆排序最坏情况需要次进行比较。