考试题型：
    平时分40%
    1.单选（30）2.填空（20）3.判断（10）4.算法阅读分析（10）5.综合分析（30）

    第一章：数据结构与算法概述

    • 数据（data)—数据元素（data element）—数据项（data item）

    三者之间的关系：数据>数据元素>数据项
    程序=算法+数据结构

    1. 数据结构的两个层次：

    逻辑结构 便于查找
    集合、线性结构（线性表，栈，队列，串，数组）、非线性结构（树、图）
    存储结构（物理结构） 便于增删
    顺序存储结构 —- 相对位置表示
    链式存储结构 —- 指针表示

    1. 算法定义：一个有穷的指令集

    算法描述：自然语言，流程图，程序设计语言，伪码
    算法时间复杂度：
    算法中关键操作（循环和递归）重复执行的次数是问题规模n的某个函数f(n),算法的时间复杂度记作：
    T(n)=O(f(n))
    T(n)=常数—>O(n)=1=O(1)
    T(n)=xn+x—>O(n)=n=O(n)(对于多项式只需保留n的最高次项)
    e.g.T(n)=5n3+n2—>n3 =O(n3)

    • for循环：有a重循环嵌套，就是O(na)，如果含有i*=2则为O(logn)
    • if循环：选择时间复杂度最高的分支

    （表示随着n的增大，算法执行的时间的增长率和f(n)的增长率相同，称渐近时间复杂度）
    时间复杂度速度对比：
    O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)

    第二章：线性表及应用
    线性表的定义：用数据元素的有限序列表示
    image.png

    线性表的结构：逻辑结构，物理结构

    • 顺序存储——-顺序表
    • 链式存储——-链表

    插入操作：在顺序表Ｌ的第i个位置插入元素e
    image.pngimage.png
    1）判断插入位置i是否合法
    2）判断储存空间是否已满
    3）元素依次后移一位，空出第i个位置
    4）将e放入i位置
    5）表长度变成n+1
    删除操作：删除e
    image.pngimage.png
    1）判断位置i
    2）元素依次向前移一个位置
    3）表长度变成n-1

    • 顺序表的特点： 随机存取法

    逻辑结构和存储结构一致、访问每个元素时间相等

    • 顺序表的优缺点：

    优点：存储密度大、随机存储任一元素
    缺点：需移动大量元素、浪费存储空间、属于静态存储，数据元素个数不能自由扩充

    • 单链表：

    image.png
    插入：求ai-1的指针p，并执行插入操作
    image.png
    删除：求ai-1的指针pre，并执行删除操作
    image.png
    双向链表：
    插入：
    image.png
    删除：
    image.png

    • 链表的特点： 顺序存取法

    位置任意，只能通过头指针进入链表
    优点：个数可以自由扩充、进行操作不用移动数据元素，只需改变链接指针
    缺点：存储密度小、存取效率不高（只能采用顺序存取）

    第三章：栈和队列

    • 定义：只能在表的一端（栈顶）进行插入和删除运算的线性表
    • 特点：只在栈顶运算，先进后出，后进先出
    • 实现方式：顺序栈、链栈

    顺序栈：
    入栈： image.png出栈：
    image.png
    链栈：
    入栈：
    image.png出栈：
    image.png

    • 解决顺序队列假溢出的办法:

      把顺序队列所使用的存储空间构造成一个逻辑上首尾相连的循环队列。

    • 循环队列问题：无法区分队满和队空

    • 解决：用一个单元，起到区别作用

    image.png
    链队列和循环队列的入队出队操作，头尾指针发生什么变化

    第四章：串、数组和广义表

    • 数组的存储：

    顺序存储：数组的顺序存储是将数组元素按照下标的变化规律存放在一块连续的存储区域中。下标的变化有两种方式：
    行优先存储方式、列优先存储方式
    image.png
    image.png

    • 广义表：

    求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表
    求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表
    image.png

    第五章：树和二叉树

    • 二叉树的五个性质
    1. 性质1: 在二叉树的第i层上至多有2i-1个结点,第i层上至少有1个结点
    2. 性质2: 深度为k的二叉树至多有2k-1个结点,深度为k时至少有k个结点
    3. 性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1 （即n0=n2+1）
    4. 性质4：具有n个结点的完全二叉树深度必为log2n+1
    5. 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

    image.png

    • 二叉树的顺序存储和链式存储（适合满二叉树和完全二叉树）
      • 顺序存储：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
      • 链式存储：image.png

    在n个结点的二叉链表中，有 n 个空指针域
    二叉树的查找结点
    image.png
    获取双亲节点
    image.png
    二叉树遍历：先序、中序、后序

    第六章：有向图和无向图
    图的两种存储结构：

    • 图的邻接矩阵存储

    image.png

    1. 有向图：

    image.png

    1. 无向图：（对称）

    image.png

    1. 带权图

    image.png

    • 图的链式存储：

    • 邻接表和图的转化

    • 图的遍历：

      1. 深度优先搜索（DFS）

    image.png

    1. 广度优先搜索

    image.png
    弗洛伊德算法—-floyd O(n3)

    第七章：查找
    查找的基本概念：

    1. 查找表:由同一类型的数据元素（或记录）构成的集合
    2. 动态查找:对查找表具有修改操作
    3. 静态查找:对查找表没有修改操作
    4. 关键字:记录中某个数据项的值，可用来识别一个记录
      1. 主关键字：唯一标识数据元素
      2. 次关键字：可以标识若干个数据元素

    顺序查找：
    把待查关键字key存入表头（“哨兵”），从后向前逐个比较，可免去查找过程中每一步都要检测是否查找完毕，加快速度。
    image.png
    时间复杂度：
    1.查找成功：（n+1）/2
    2.查找失败：n+1
    折半查找
    image.png
    采用顺序存储结构的有序表，不宜用于链式结构
    时间复杂度O(log2n )
    二叉排序树
    二叉排序树或是空树，或是满足如下性质的二叉树：
    (1)若其左子树非空，则左子树上所有结点的值均小于根结点的值；
    (2)若其右子树非空，则右子树上所有结点的值均大于根结点的值；
    (3)其左右子树本身又各是一棵二叉排序树
    生成过程：从空树出发，经过一系列的查找、插入操作之后，可生成一棵二叉排序树
    image.png
    第八章：排序
    希尔排序（直接插入排序）:每趟只需比较 1 次，不移动 　总比较次数为 n-1

    冒泡排序
    排序算法的平均时间复杂度、稳定性 p66