软件技术基础概论

这是一篇关于软件技术基础概论的思维导图，主要内容有第—章绪论、第二章线性表(线性结构一对一)、第三章栈和队列、第四章树与二叉树（树形结构—对多)等。

中心主题

• 第一章绪论
  • 数据的定义
    • 数据与数据之间的相互关系，即数据的组织形式。数据结构可以理解为相互之间存在着的某种特定关系的数据元素的集合；
  • 数据结构内容
    • 逻辑结构（数据元素之间逻辑关系的描述）
      • 集合结构（属于同一类别）
      • 线性结构（一对一）
      • 树形结构（一对多）
      • 图结构（多对多）
    • 存储结构
      • 1.顺序存储
      • 2.链式存储
      • 3.索引存储
      • 4.哈希（或散列）存储
    • 运算
      • 定义：建立在数据结构基础上对特定问题求解步骤的一种描述，是肉 感指令组成的有限序列。
      • 性质：有穷性、确定性、可行性、输入、输出
      • 算法分析：研究和比较算法性能的优劣---根据算法消耗时间和占据空间
      • 复杂度包括:
        • 空间复杂度
          • 一个程序的空间复杂度是指程序运行从开始到结束所需的存储量
        • 时间复杂度
          • 一个程序的时间复杂度是指程序运行从开始到结束所需要的时间
  • 对特定问题的求解，究竟采用何种数据结构和算法，需要看问题的具体要求 和现实环境的各种条件；数据结构的选择是否恰当将直接影响到算法的效率。
• 第二章线性表（线性结构一对一）
  • 顺序表-顺序存储
    • 用一组地址连续的存储单元按顺序依次存放线性表中的每一个元素，任意一个数据元素都可以随机存取，但插入和删除操作需要移动大量元素。
  • 链表-链式存储
    • 可用连续或不连续的存储单元来存储线性表中的元素，元素之间的逻辑关系与存储物理位置的邻接关系无关。且它是一个动态生成的过程，每个节点占用的存储空间不是预先分配好，而是在程序运行中动态生成的。
  • 单链表
    • 每个元素至多只有一个前驱元素和一个后继元素
  • 循环链表
    • 将单链表中最后一个结点的指针由空改为指向单链表的头结点，整个链 表形成一个环。不能随机存取，但插入、删除操作简便，无需大量移动元素。
• 第三章栈和队列
  • 栈（仅在表的一端进行操作的线性表，先进后出）
    • 顺序存储
      • 顺序栈——利用一组地址连续的存储单元依次存放由栈底到栈顶的所有 元素，附加 top 指针表示栈顶元素在顺序栈中的位置。
    • 链式存储
      • 链栈——克服顺序栈上溢问题。
  • 队列（在表的两端进行操作的线性表，先进先出）
    • 删除端（队头-front）
    • 插入端（队尾-rear）
    • 顺序队列（队空- 队满- 队中元素个数）
    • 链队（队空- 队满- 队中元素个数）
• 第四章树与二叉树（树形结构一对多）
  • 二叉树
    • 定义
      • 一棵二叉树是结点的一个有限集合，该集合: 1.或者为空 2.由一个根节点加上两棵别称为左子树和右子树的二叉树组成
    • 性质
      • 1.二叉树不存在度大于2的结点 2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
      • 注意:对于任意二叉树都是由以下几种情况而复合成的
  • 满二叉树（记住：满足公式-层数为K，且结点总数是2^k-1）
    • 定义
      • 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k-1，则它就是满二叉树。
    • 性质
      • 1.不存在度为1的结点，即所有分支结点都有左子树和右子树
      • 2.所有叶子结点都在同一层上
  • 完全二叉树（记住：右孩子存在，左孩子必存在）
    • 定义
      • 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。
    • 性质
      • 1.前n-1层为满的
      • 2.最后一层不满，但最后一层从左往右是连续的
  • 顺序存储
    • 连续的空间存储树的结点，自左向右，自上而下。
  • 链式存储
    • 借助指针存储结点的数据信息和地址信息。每个节点包含三部分信息：左 孩子地址，数据，右孩子地址。
  • 遍历形式
    • 先序
      • 巧记：根左右
    • 中序
      • 巧记：左根右
    • 后序
      • 巧记：左右根
• 第五章图（图结构多对多）
  • 定义
    • 图是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。
  • 存储
    • 邻接矩阵
      • 定义：邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}，则表示G中各顶点相邻关系需用一个n*n的矩阵。
      • ①对无向图而言，邻接矩阵一定是对称的，而且主对角线一定为零（在此仅讨论无向简单图），副对角线不一定为0，有向图则不一定如此。
      • ②在无向图中，任一顶点i的度为第i列（或第i行）所有非零元素的个数，在有向图中顶点i的出度为第i行所有非零元素的个数，而入度为第i列所有非零元素的个数。
      • ③用邻接矩阵法表示图共需要n^2个空间，由于无向图的邻接矩阵一定具有对称关系，所以扣除对角线为零外，仅需要存储上三角形或下三角形的数据即可，因此仅需要n（n-1）/2个空间。
    • 邻接表
      • 定义：存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。
  • 图的遍历
    • 深度优先
      • 定义：从图中的某个顶点出发，首先访问该顶点，然后依次从它的各个未访问的邻接点出发深度优先搜索遍历图，直至图中所有和开始的顶点有路径相同且未被访问的顶点都被访问到。若此时尚有顶点未被访问到，则另选一个未被访问到的顶点作为起始点，重复上述过程，直至所有的顶点都被访问到。
    • 广度优先
      • 定义:从某个顶点出发，在访问了该顶点之后依次访问它的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问他们的邻接点，并使得“先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问”，直至图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有未被访问到的顶点，则需要另选一个未曾访问过的顶点作为新的起始点，重复上述操作，直至图中所有顶点都被访问到为止。
• 第六章查找
  • 静态查找
    • 顺序查找
      • 性质
        • 思想：从第一个元素到最后一个元素逐个进行比较
        • 特点：最简单、最普通的查找方法
        • 适用范围：顺序与链式存储结构
      • 操作步骤
        • step1：从第一个元素开始查找
        • step2：用待查找关键字与各个节点关键字逐个进行比较；若找到相等节点，则查找成功；否则失败。
      • 算法评价
        • ASL=n\1*2\n（n+1）=2\（n+1）=O（n）
        • 一般情况下ASL=<2\n
        • 优点
          • 对结点的逻辑次序和存储结构无要求
          • N值较小时比较合适
        • 缺点
          • ASL较长
        • 讨论
          • 减少比较次数以提高效率（二分法）
    • 有序查找
      • 对分（折半）查找
        • 性质
          • 思想：有序序列中点设置为比较对象，如查找值小于中点，则将序列缩小到左半部分
          • 特点：高效的查找方法：明显减少比较次数，提高查找效率
          • 先决条件：表中数据元素必须有序
        • 操作步骤
          • step1：首先确定查找区间的中间位置
            • mid=int（（left+right）/2）
          • step2：用待查找关键字值与中间位置的关键字值进行比较
            • 相等：成功
            • 大于：后半部分继续二分查找
            • 小于：前半部分继续进行二分查找
          • step3：对确定的缩小区域再按二分公式，重复上述步骤
        • 算法评价
          • 数据结构
            • 一维数组
          • 优点
            • ASL<=log2n；一次比较后查找范围缩小一半
          • 缺点
            • 要求有序，所有数据元素要按大小排序
            • 顺序存储结构插入、删除操作不大便利
      • 分块查找
        • 性质
          • 顺序查找的一种改进方法
          • 用于分块有序表进行查找
        • 操作步骤
          • step1：先选取各块中最大关键字构成一个索引表
          • step2：对索引表进行对分或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找
        • 算法评价
          • 索引表使用对分法：ASL<=log2（s/n+1）+2/s
            • n为表长
            • s为块长
          • 优点
            • 插入删除操作方便
            • 只要找到相应的块，在块中任意位置操作均可
          • 缺点
            • 索引表增加了辅助存储空间
  • 动态查找
    • 二叉排序树
      • 定义：具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；
      • 性能分析：每个结点的C(i)为该结点的层次数。最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度(n+1)/2(和顺序查找相同），最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log 2 (n)成正比。 也就是说，最好情况下的算法时间复杂度为O(1)，最坏情况下的算法时间复杂度为O(n)。
    • 哈希表构造与查找
      • 构造方法
        • 直接地址法
        • 除留余数法
        • 数字分析法
        • 平方取中法
        • 折叠法
      • 处理冲突方法
        • 开放定址法
        • 再散列（哈希）法
      • 查找：查找过程与构造过程基本一致，即给定关键字Key值并根据构造哈希表时设定的哈希函数求得其存储地址
• 第七章排序
  • 插入排序
    • 基本思想：将n个元素的数列分为有序和无序，后将无序数列的第一个元素与有序数列从前往后逐个进行比较，插入有序数列合适位置
    • 算法步骤
      • step1：从有序数列｛a1｝无序数列｛a2，a3，a4……an｝开始进行排序
      • step2：处理第i个元素时，数列｛a1，a2，a3…ai-1｝已有序，数列｛ai……an｝无序。用ai于ai-1，ai-2进行比较，插入合适位置。（从前往后也可）
      • step3：重复step2，共进行n-1次的插入处理，数列全部有序
    • 算法评价
      • 插入算法比较次数和交换次数约为n^2/2
      • 这是一种稳定的算法
  • 交换排序
    • 冒泡排序
      • 性质：两两比较待排序记录的关键字；并交换不满足顺序要求的偶对元素，直到全部满足
      • 算法步骤
        • step1：通过比较和交换将最大的一个关键字交换到最后
        • step2：如法炮制，后一趟冒泡
        • step3：最多执行n-1趟冒泡
      • 算法改进
        • 若某次冒泡中没有进行交换，说明序列已经有序，则停止交换
      • 算法评价
        • 如有序，只需进行一趟；无序则需进行n-1趟
        • 待排序序列基本有序适合这种算法
        • 这一算法是稳定的
    • 快速排序
      • 性质：
        • 对冒泡排序的改进，基于交换排序
        • 基本思想：先以某种方法选一个元素K为分界点，用交换的方法将序列分为两个部分———比该值小的放左边，大的放右边，在分别对左、右两部分实施上述分解过程，直到各子序列长度为一
          • K的选取方法
            • 左边第一个元素
            • 取中点
            • 最大和最小值的平均值
      • 算法步骤
        • step1：分别从两端开始，指针i指向第一个元素A【left】，指针j指向最后一个元素A【right】，分界点取K
        • step2：循环（i≤j） 左边：若K＞A【i】，则i=i+1，继续比较；若K≤A【i】，则将A【i】交换到右边。右边同上。当i=j时，一次分解操作完成
        • step3：在对分解出的左右两个子序列按上述步骤继续进行分解，直至不可再分（子序列长度为一）
      • 算法评价
        • 分界点选取不同，排序效果差距很大
        • 比较次数为nlogn
        • 这是一种不稳定算法
  • 选择排序
    • 选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。适合从大量记录中选择一部分记录的场合。
  • 归并排序
    • 归并排序是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。