数据结构

数据结构知识点串联思维导图，详细阐述具体概念、算法、操作等内容，帮你理清思路的同时标注重难点，让你事半功倍，学习更高效！

数据结构

• 第一章基础知识
  • 考小题
    • 1.数据元素是数据的基本单位
    • 2.数据项是数据的不可再分的最小标识单位
    • 3.数据对象：是具有相同构成的数据元素的集合，是数据的一个子集
    • 4.数据结构
      • 是相互之间 存在多种特定关系的 具有相同构成的数据元素的有限集合
      • 表示方式： DS=(D,R)或 DS=(D,S)
        • D是数据元素的有限集
        • R或S是D上关系的有限集
  • 四种基本类型
    • 1.集合
      • 数据元素除了“同属于一个集合”的关系外，无其他关系
    • 2.线性结构
      • 特点： 1.存在1对1的关系 2.数据元素件有严格的先后次序
      • 线性表也属于线性结构
      • 在线性结构中，除了首元素和尾元素，每一个元素都有唯一的前驱元素和后继元素
        • 前驱元素和后继元素都是专有名词
    • 3.树型结构
      • 特点： 1.存在1对多的关系 2.数据元素层次分明
    • 4.网状结构
      • 也叫做图型结构
      • 特点： 1.存在多对多的关系
  • 三要素
    • 1.逻辑结构
      • 与数据本身的形式，内容，相对位置，个数都无关 描述的是逻辑上的联系
      • 逻辑上可以把数据结构分为
        • 线性结构
          • 线性表
          • 栈
          • 队列
          • 串
        • 非线性结构
          • 树型结构
          • 网状结构
    • 2.存储结构
      • 也说物理结构
      • 定义：数据结构在计算机中的表示 称为数据的存储结构或物理结构
      • 主要包括两大类
        • ①顺序存储
          • 定义：用连续的存储空间来存储数据
            • 如数组
          • 特点：物理结构和逻辑结构保持一致
            • 即逻辑上相邻的元素在物理存储中也是相邻的
        • ②链式存储
          • 定义：每一个存储元素在存储时不一定相邻，极有可能是分散
          • 特点：元素与元素之间的逻辑关系是同过其“地址”建立的
            • 地址;指针
  • 抽象数据类型ADT
    • 具体包括三部分
      • 1）数据对象 2) 数据关系————数据对象 关系上的集合 3) 基本操作————对数据对象的基本操作的集合
      • 抽象数据类型记作：ADT=<D,R,P>
        • D——数据对象
        • P——基本操作
        • R——数据关系
  • 算法
    • 是求解问题的有限步骤的序列
    • 程序是算法的一种实现
    • 特点（5个）
      • 1）有穷性 2）确定性————每条指令理解起来不能有歧义 3）可行性 4）有输入————有大于等于零个输入 5）有输出————有大于等于1个输出
        • 算法不一定有输入，但一定有输出
    • 评价（4个）
      • 1）正确性 2）可读性 3）健壮性————对出错情况和异常情况的处理能力 4）效率和存储量要求
        • 效率——描述算法的执行时间； 存储量要求——指的是算法执行过程中需要的最大存储空间
          • 算法效率的度量是通过时间复杂度和空间复杂度来描述
            • 空间复杂度S（n）
              • 评估算法所耗费的存储空间
              • 是衡量一个算法耗费存储空间的指标
            • 评估算法时间开销的方法（2种）
              • 语句执行频度
                • 是指该语句在算法中被重复执行的次数——即循环次数
                • T（n）:所有语句的执行频度之和
                  • T（n）也叫做时间开销函数
                    • 由于复杂算法无法写出 T(n)函数表达式， 所以用T(n)的数量级来表示算法执行时间
                      • 时间复杂度主要分析T(n)的数量级
                        • 时间复杂度英文：O（f(n））
                          • n增大，时间复杂度也增大
                            • n是问题规模（元素个数），问题规模越小越好
                              • 算法的时间复杂度取决于
                                • 1）问题规模n
                                • 2）待处理的问题初态
                          • 语句执行频度始终为常数，时间复杂度为O（1）——称为常数阶
                          • 常用时间复杂度：（由低到高） 1. O（1）————常数阶 2. O (log₂n)———对数阶 3. O（n）————线性阶 4. O（nlog₂n) 5. O(n²) 6. O(n³) 7. O(2ⁿ)————指数阶 8. O(n!)————阶乘 9. O(nⁿ)
                            • 从上到下阶越来越大， 但算法的时间性能越来越差
                          • 计算时间复杂度
                            • 通过语句频度T（n）求时间复杂度两步骤 1）只保留最高次项 2）去掉最高次项系数
                            • 计算时间复杂度一般求最坏情况下的时间复杂度
                            • 遵循规则
                              • 1）加法原则
                                • 两个时间复杂度相加，结果取最大
                              • 2）乘法原则
                                • 两个时间复杂度相乘，结果直接相乘即可
                                • 只能用于内外嵌套，且彼此独立的循环
                            • 程序里的时间复杂度是求所有循环语句的执行频度之和
                              • int i; for(i=0;i<n;i++){ 语句1; ——————语句1时间复杂度O（n） } for(i=0;i<n*n;i++){ 语句2; ——————语句1时间复杂度O（n²） } 整体时间复杂度为 O（n）+O（n²） 计算 O（n）+O（n）————两个时间复杂度相加，取最大 O（n）+O（n²）=O（n²）
                            • 算法中通常采用最内层循环语句的频度来分析时间复杂度
                              • 注意循环嵌套
                            • 求程序段的时间复杂度
                              • 1）单独的一个循环
                                • 步骤
                                  • ①设循环次数为 t ②找到 t 和 i (i是增量）的关系写表达式 ③带入循环条件 ④把t表示出来 ⑤计算遵循时间复杂度计算两步骤
                                    • 增量：找出现在条件中出现的变量的增量
                              • 2）循环的嵌套
                                • 情况
                                  • ①循环嵌套，但每一层的循环彼此独立 方法：每一层循环的时间复杂度+乘法原则
                                    • 彼此独立，指内循环的条件中不含外循环的变量
                                  • ②循环嵌套彼此不独立——内循环与外循环有关 方法：求和法+两步骤
                                    • 求和法T(n)=（首项+尾项）*项数/2
                    • 计算语句执行频度T（n）
              • 1）事后统计法
              • 2）事前分析估算法
                • 常用
• 第二章 线性表L
  • 非常重要，数据结构50%的考题从这里出
  • 内存分配
    • 动态存储：按需分配
      • 函数
        • malloc函数（麦 浪磕）
          • 指针函数
          • 作用：在内存的动态存储区分配一个长度为size的连续空间
          • 线性表分配内存表达式
            • 顺序表
              • L.elem=(ElemType*) malloc(LIST_INIT_SIZE * sizeof（ElemType)
              • 分配错误：if（L.elem==NULL）return ERROR;
            • 单链表
              • L=(LinkList) malloc(sizeof（LNode)
              • 分配错误：if（L==NULL）return ERROR;
        • free函数
          • 作用：将malloc函数分配的内存释放掉
    • 静态存储：如数组，分配的是固定不变的；
  • 线性表
    • 线性表的基本操作
      • 1.初始化操作
      • 2.销毁操作
      • 判空操作
      • 求长度操作
      • 5.获取元素操作
      • 6.定位操作
      • 7.插入操作
      • 8.删除操作
      • 9.遍历操作
    • 线性表的顺序存储
      • 线性表的顺序存储也叫顺序表
      • 顺序表
        • 是基于数组实现的
        • 用连续的存储单元来分配内存， 从而使得逻辑上相邻的两个元素·在物理结构上也相邻
        • 特点：随机存储
          • 交换元素值用到的就是随机存取
            • 对应时间复杂度为O（1）
        • 线性表的第i个元素ai的存储位置为： LOC（ai）=LOC（a1）+（i-1）*k
          • i是位序，位序从1开始
            • 位序=下标+1
            • 下标=位序-1
            • 长度=位序
        • 定义顺序表：SqList L;
        • 顺序表当前容量：L.listsize
        • 顺序表长度：L.length
        • 顺序表元素：L.elem【i】
          • i是下标，下标从0开始
            • L.elem【0】表示位序为1的元素
        • 数据类型为：ElemType型
        • 基本操作算法
          • 1）初始化操作
            • 1.分配内存
              • L.elem=(ElemType*) malloc(LIST_INIT_SIZE * sizeof（ElemType)
              • 分配错误：if（L.elem==NULL）return ERROR;
            • 2.设置当前容量=LIST_INIT_SIZE
            • 3.设置当前长度=0
          • 2）获取元素操作
            • 检查位序合法性 1 ≦ i ≦ listlenght
              • 写成if (1>i || i> L.lenght) return ERROR;
            • 该算法时间复杂度为O（1）
          • 3)插入元素操作
            • 实现核心：循环右移
              • 将位序小的赋值给位序大的
              • 记住长度要+1
            • 同样，要检查位序合法性
            • 结论： 1> 在长度为n的线性表中第i个元素前插入一个元素，需要移动n-i+1个元素 2>最好情况——在表尾插入————时间复杂度为O(1) 3>最坏情况——在表头插入————时间复杂度为O(n) 4>平均情况：在长度为n的顺序表中插入一个元素，平均移动 n/2个元素——时间复 杂度为O(n)
              • 该算法时间复杂度为O(n)
          • 4)删除元素操作
            • 实现核心：循环左移
              • 将位序大的赋值给位序小的
              • 记住长度要-1
            • 同样，要检查位序合法性
            • 结论： 1> 在长度为n的顺序表中删除第i个元素时，需要移动n-i个元素 2>最好情况——删除表尾元素————时间复杂度为O(1) 3>最坏情况——删除表头元素————时间复杂度为O(n) 4>平均情况：在长度为n的顺序表中删除一个元素，平均移动 (n-1)/2个元素——时 间复杂度为O(n)
              • 该算法时间复杂度为O(n)
          • 5)定位元素操作
            • 实现核心：顺序查找
            • 结论： 设顺序表有n个元素 2>最好情况——第一个元素就找到了————时间复杂度为O(1) 3>最坏情况——没有找到该元素————时间复杂度为O(n) 4>平均情况：平均查找 (n+1)/2个元素——时间复杂度为O(n)
              • 该算法时间复杂度为O(n)
          • 6)遍历操作算法
            • 头部是void型
              • 其他都是status型
              • Void LinkList_Sq(Sqlist L)
          • 6）归并操作
            • 将两个有序表合成1个
              • 有序是指升序或降序
            • 步骤： 1.创建新表表C 2.将表1与表2两两比较，较小的元素保存到表C，较大元素继续与另一个表中的其他 元素比较，直到其中一个表没有元素为止 3.将剩余表中的元素复制到表C
              • 表C的序必须一致，若无特殊说明，默认由小到大
            • 结论： 设有序表La与有序表Lb各有n个元素，归并算法最少比较n次，最多比较2n-1次 2>最好情况————表1元素都小于表2元素 ————比较n次 3>最坏情况————表1，表2元素两两交叉，各自有大有小——比较2n-1次
    • 线性表的链式存储
      • 用任意一组的存储单元来存储数据
        • 存储单元可以连续，也可以不连续
      • 分类
        • 单链表
        • 双链表
        • 循环链表
      • 单链表
        • 由结点构成
          • 结点由
            • 数据域data
              • 存放数据信息
            • 指针域next
              • 存放后继元素（下一个元素）的存储位置
        • 分类
          • 带头结点的单链表
            • 头结点的数据域不保存数据信息
            • 线性表为空表
              • 单链表中只有头结点，且头结点的指针域为空
            • 判断单链表是否为空
              • L—>next==NULL
            • 单链表表示方法
              • 头指针：L
              • 头结点的数据域：L->data
              • 数据域：p->data
              • 指针域：p->next
              • 首结点的地址 L->next
              • 尾结点的地址 p->next==NULL
          • 不带头结点的单链表
            • 判断单链表是否为空
              • L==NULL
        • 创建头指针：LinkList L；
        • 创建指针：LinkList p；
        • 为结点分配内存
          • L=(LinkList) malloc(sizeof（LNode)
          • 分配错误：if（L==NULL）return ERROR;
        • 基本操作算法
          • 1）初始化操作
            • 1.分配内存
              • L=(LinkList) malloc(sizeof（LNode)
              • 分配错误：if（L==NULL）return ERROR;
            • 2.空表，头结点指针域为空
              • 指针域：p->next==NULL
          • 2)遍历操作算法
            • 头部是void型
              • 其他都是status型
              • Void LinkList_L(Linklist L)
          • 3）获取元素操作
            • 检查位序合法性 i>= 1
              • 写成if (i< 1) return ERROR;
              • 首结点位序为1； 头结点没有位序
            • 该算法时间复杂度为O（n）
              • 已知第i个元素的指针的情况下， 访问第i+1个元素的时间复杂度为O(1), 在第i个位置后插入元素的时间复杂度为O(1)
          • 4)插入元素操作
            • 实现核心：获取元素操作+尾插法或头插法
              • 尾插法
              • 头插法
            • 同样，要检查位序合法性
            • 该算法时间复杂度为O(n)
          • 5)删除元素操作
            • 实现核心：循环左移
              • 将位序大的赋值给位序小的
              • 记住长度要-1
            • 同样，要检查位序合法性
            • 同样，要用到获取元素操作
            • 该算法时间复杂度为O(n)
              • 删除单链表表尾元素————时间复杂度为O(1)
      • 其他链表
        • 循环链表
          • 尾结点 p->next==L
          • 判断循环链表是否为空
            • L—>next==L
        • 双链表
          • 两个指针域：prior和next
          • 判断双链表是否为空
            • L—>prior==NULL
            • L—>next==NULL
          • 尾结点 p->next==NULL
        • 循环双链表
          • 判断循环双链表是否为空
            • L—>prior==L
            • L—>next==L
          • 尾结点
            • p->prior==L
            • p->next==p
    • 顺序表，单链表对比 1）顺序表的存储密度大，单链表的存储密度小（小于1） 2）顺序表是预分配存储空间，单链表是按需分配存储空间 3）顺序表支持随机读取，单链表不支持随机读取 4）顺序表查找元素方便，链表查找元素不方便 5）顺序表插入、删除元素效率低，需要移动大量元素 单链表插入、删除元素效率高，不需要移动大量元素
• 第三章——栈S
  • 栈也是一种线性表
  • 通常记作S={a1,a2,a3………an}(n>=0)
  • 栈只允许在表尾进行插入和删除
    • 栈是操作受限的线性表
  • 入栈push
    • 栈只能在表尾（——也就是栈顶）插入、删除元素
    • 向栈中插入元素的操作被称为入栈
    • 只能在栈顶插入——新元素会成为新的栈顶元素
  • 出栈pop
    • 删除栈中元素的操作被称为出栈
    • 只能在栈顶插入——删除元素的下一个元素会成为新的栈顶元素
  • eg：出入栈序列
  • 特点：先进后出
    • 因此也叫先进后出的线性表或LIFO结构
  • S表为空时——叫空栈
  • n个不同元素进栈，出栈元素的不同排列个数为：
    • 也可以说出栈的可能性为
    • 为数学排列组合公式
  • 一个栈的输入序列为1,2,3..........n，若输出序列的第一个元素是n，输出的第i个元素是n-i+1
  • 一个栈的输入序列为1,2,3..........n，若输出序列的第一个元素是i，输出的第j个元素是不确定的
  • 栈的基本操作
    • 1.初始化操作InitStack(&S)
    • 2.销毁操作DestoryStack(&S)
    • 3.判空操作StackEmpty(S)
    • 4.求长度操作StackLenght(S)
    • 5.读取栈顶元素操作GetTop(S,&e)
      • 前提：栈S存在，且不为空
    • 6.入栈操作Push(&S,e)
      • 前提：栈S存在
    • 7.出栈操作Pop(&S,&e)
      • 前提：栈S存在，且不为空
    • 8.遍历操作
  • 栈的顺序存储
    • 同样用连续的存储单元来分配内存，依次存放栈底到栈顶的元素
    • 定义栈：SqStack S；
    • 栈顶指针top
      • 作用：指示栈顶元素的位置
        • 但top不指向栈顶元素，始终指向栈顶元素的下一个元素
          • 栈顶元素表示方法：S.(top-1)
    • 栈底指针base
      • 作用：指示栈底元素的位置，指向栈底元素
    • 栈的当前容量：stacksize
    • 空栈
      • 判断条件： S.top==S.base
    • 基本操作算法
      • 1）初始化操作
        • 1.分配内存
          • L.base=(ElemType*) malloc(STACK_INIT_SIZE * sizeof（ElemType)）
          • 分配错误：if（L.base==NULL）return ERROR;
        • 2.设置当前容量=STACK_INIT_SIZE
      • 2)入栈操作
        • 入栈操作要先判断栈是否是满栈
        • 栈满扩容
          • 判断栈是否满了条件 S.top-S.base>=S.stacksize
        • 核心代码： *S.top=e; S.top++;
          • S.top是一个指针，*是取内容运算符，*S.top就是内容
          • 栈只允许在表尾进行插入和删除，所有用top栈顶指针
            • top始终指向栈顶元素的下一个元素
          • 可以合二为一 S.top++=e
          • S.top++;是入栈时更改top的操作
      • 3)删除元素操作
        • 入栈操作要先判断栈是否是空栈
        • 要判断是否为空栈
          • if（S.top==S.base）return ERROR;
        • 核心代码： S.top--; e=*S.top;
          • S.top--;是出栈时更改top的操作
      • 4）读取栈顶元素操作
        • 同样要判断是否为空栈
        • 栈顶元素表示方法：S.(top-1)
        • 核心代码： e=S.(top-1);
  • 栈的应用
    • 1.检测括号是否匹配
      • 括号总是成对出现的
      • 算法检测步骤
        • 可能会考简答题
        • 1）从左到右依次扫描每个字符，当扫描到左括号时，令其入栈 2）当扫描到右括号时，则检查栈顶是否为对应的左括号，若是则做 出栈处理 若不是 则表明出现错误 3）当扫描结束时，若栈为空，则匹配成功。否则，表明栈中还有尚未匹配的左括号，匹配失败
          • （、[ 都是左括号
    • 2.进制转换
      • 是考试高频算法
      • 进制转换通常会用到的结构是：栈
      • 十进制转其他进制
• 队列
  • 是线性表
  • 通常记作Q={a1,a2,a3………an}(n>=0)
  • 队列只允许在表尾进行插入操作，表头进行删除操作
    • 因此：队列是操作受限的线性表
  • 入队enqueue
    • 向队列中插入元素称为入队
      • 在表尾插入元素
    • 只能在队尾插入——新元素会成为新的队尾元素
  • 出队dequeue
    • 删除队列中元素的操作称为出队
      • 删除表头元素
    • 只能删除表头元素——原第二个元素会成为新的队头元素
  • 特点：先进先出
    • 队列又被称为先进先出的线性表或者FIFO结构
  • 空队
    • 当Q为空时
    • 有且仅有一个头结点
  • 队列的基本操作
    • 1.初始化操作InitQueue(&Q)
    • 2.销毁操作DestoryQueue(&SQ
    • 3.判空操作QueueEmpty(Q)
    • 4.求长度操作QueueLenght(Q)
    • 5.读取队头元素操作GetHead(Q,&e)
      • 前提：队列Q存在，且不为空
    • 6.入队操作EnQueue(&Q,e)
      • 前提：队列Q存在
      • 只能在队尾插入元素
    • 7.出队操作DeQueue(&Q,&e)
      • 前提：队列Q存在，且不为空
      • 只能在队头删除元素
    • 8.遍历操作QueueTraverse(Q,visit())
      • visit是函数
  • 队列的链式存储
    • 单链表
      • 定义队列 LinkQueue Q；
      • 队头指针：Q . front
      • 队尾指针：Q . read
      • 基本操作算法
        • 1）初始化操作
          • 1.分配内存
            • Q . front=(QNode*) malloc(sizeof（QNode)
            • 分配错误：if（Q . front==NULL）return ERROR;
          • 2.空队，头结点指针域为空
            • Q . front==Q . read
            • 指针域：Q . front->next==NULL
        • 2)入队操作
          • 前提：队列Q存在
          • 只能在队尾插入——新元素会成为新的队尾元素
          • 生成新结点（保存新元素）并分配内存
            • p=(QNode*) malloc(sizeof（QNode)
            • 分配错误：if（p==NULL）return ERROR;
          • 核心代码： p->data=e; p->next=NULL; Q.read->next=p; Q.read=p;
        • 3)出队操作
          • 只能删除队头元素——使原第2个元素会成为新的队头元素
          • 前提：队列Q存在，且不为空
            • 检查空队
              • if（Q . front==Q . read）return ERROR;
          • 将队头地址保存到新指针P中
          • 核心代码： p=Q . front->next e=p->data; Q . front->next=p->next; if(Q.read==p)Q . front==Q . read; free(p);
            • if(Q.read==p)Q . front==Q . read;
              • 特殊情况： 当删除最后一个元素时，队头，队尾重合，为空队
  • 队列的顺序存储
    • 顺序队列
      • 用连续的存储单元来分配内存， 从而使得逻辑上相邻的两个元素·在物理结构上也相邻
      • • n是下标，位序从1开始
          • 下标=位序-1
          • 位序=下标+1
          • 长度=位序
      • 定义两个整型变量front和read
        • 队列判空条件：front==read
        • 每当入队一个新元素时，read+1
        • 每当入队一个元素时，front+1
      • • 非空队列中， front始终指向队头元素， read始终指向队尾元素的下一个元素
      • 引申问题
        • 问题1：随着元素出队前面的空间会浪费掉，怎么办？
        • 问题2：元素依次入队，read会越界，不指向队尾元素的下一个元素，怎么办？
        • 假溢出问题
          • 循环队列
      • 循环队列
        • 作用：可以充分利用空间
        • 重要结论
          • 设循环队列最大容量为M
            • 计算front，read的下一个出现位置： front=（front+1）%M read=（read+1）%M
            • 计算队列长度（或当前队列元素个数） （read-front+M）%M
        • 判断循环队列已满依据
          • （read+1）%M==front
        • 在最大容量为M的循环队列中，最多存储M-1个元素
        • 循环队列判空条件：front==read
• 串
  • 考1~2道小题
  • 是线性结构
  • 串是由n(n>=0)个字符组成的序列
  • 通常记作s=‘a1,a2,a3………an’(n>=0)
    • 为了不与变量名混淆，用单引号括起来，但单引号本身不属于串
    • s是串的名字
      • a1,a2,a3………an是串的值
        • 串的每个数据都是单个字符
  • 串的长度
    • 串中字符数目n称为串的长度
  • 空串
    • 长度为0的串
  • 子串
    • 串中任意个 连续的字符 组成的子序列称为该串的子串
      • 原串称为主串
        • 主串最长的子串是它本身
      • eg：s='tianjin'————主串 s₁='tian'————子串 s₂='jin'————子串
      • 空串是任意串的子串
  • 通常把字符在序列中的序号称为该字符在串中的位置
    • 从1开始
  • 子串在主串中的位置
    • 是指子串的第一个字符在主串的位置
  • 串相等
    • 同时满足
      • 1.串的长度相等
      • 2.对应位置上的字符相等
  • 若串长度为n，其子串的个数为 [ n (n+1) /2 ]+1
    • 最后加1是指加空串
  • 串的基本操作
    • 1.串复制操作StrCopy(&T,S)
      • 由串S复制得到串T
    • 2.串连接操作Concat(&T,S1,S2)
      • 由T返回SI和S2连接成的新串
    • 3.取子串操作SubString(&Sub,S,pos,len)
      • 位置：pos 长度：len
      • 用Sub返回串S中第pos个字符起 长度为len的子串
    • 4.求子串位置操作Index(S,T,pos)
      • 考试简化版本Index(S,T)
      • 返回串S中从第pos个字符起子串T首次出现的位置
    • 考小题
    • 5.串插入操作StrInster(Q&S,pos,T)
  • 串的存储
    • 分类
      • 1.顺序存储表示
        • 1.定长顺序存储表示
          • 用固定长度的数组来存储每一个串
        • 2.堆分配存储表示
          • 用一组地址连续的存储单元来依次存放串值
      • 2.链式存储表示
• 数组
  • 也是线性结构
  • 数组是由n（n>=1）个相同类型的数据元素构成的有序列表
  • n维数组可以看作是以n-1维数组构成的一维数组
  • n维数组被认为是扩展的线性表
  • 数组的存储结构
    • 一维数组A【0..........n-1】,其存储结构关系式为： LOC（ai）=LOC（a0）+i ×L（0≦i≦n）
      • LOC代表元素地址或位置 LOC（ai）代表元素ai的地址
      • L是每个数组元素所占的存储单元/字节
  • 多维数组有两种映射方法
    • 指按行存储，还是按列存储
    • 重点二维数组eg：a[2][3]
    • 1.先行优先
      • 设二维数组行下标与列下标范围为 行：【0 ，h1 】————行数：h1+1 列：【0 ，h2 】————列数：h2+1
        • 行列从0开始
      • 存储结构关系式：
        • 基地址是指首元素
        • L还是每个数组元素所占的存储单元/字节
      • 如下图：
    • 2.先列优先
      • 设二维数组行下标与列下标范围为 行：【0 ，h1 】————行数：h1+1 列：【0 ，h2 】————列数：h2+1
        • 行列从0开始
      • 存储结构关系式：
    • 当行列下标从1开始时
      • 存储结构关系式： 行和列（i 和 j 都减一）
      • 每个关系式里都要同时减一
    • 没有基地址时
      • 设基地址为x，解方程
• 矩阵
  • 矩阵可以用二维数组来存储
  • 矩阵是站在数学角度上，数学上行列都是从1开始
  • 数组与矩阵不同，数组行列都是从0开始
  • 压缩存储
    • 可能考简答题
    • 指为 多个值相同的元素只分配一个存储空间，对零元素不分配存储空间，其目的是节省存储空间
  • 对称矩阵
    • 矩阵行列都是从1开始的
    • 定义：设A为n阶方阵（n行n列），若有aij=aji(1<=i,1<=j),则称A为对称矩阵
    • 对称矩阵上分三个部分
      • 上三角区(i<j)
      • 主对角线（i=j）
      • 下三角区（i>j）
      • 对称矩阵上三角区和下三角区的对应元素相同
        • 存储时只需要存储下三角区元素（包括主对角线上元素）即可
          • 共n(n+1)/2个元素
    • • 也可以说矩阵元素在数组中的存储位置k
    • 求元素地址
      • 第一步：①求下标 第二步：②求地址
        • 求地址公式：
  • 三角矩阵
    • 特点上三角区或下三角区的所有元素为同一个常量
      • 二选一可以是上三角矩阵，也可以是下三角矩阵
    • 存储思绪类似于对称矩阵，不同点：在存储完下三角区和主对角线上的元素以后，还有加一个存储相同常量的存储单元
  • 稀疏矩阵
    • 特点
      • 1.非零元素很少（远远少于0） 2.分布无规律
        • 同时满足才是稀疏矩阵
    • 核心思想：仅仅存储0元素
    • 一个三元组唯一确定了稀疏矩阵中的一个非零元素
    • 考点：写三元组表
      • 一个稀疏矩阵唯一地对应一个三元组表
    • 稀疏矩阵有多种压缩存储方案
• 广义表
  • 又被称为列表（Lists）
  • 广泛的应用于人工智能语言LISP
  • LS是广义表的名字
  • 广义表长度
    • n是广义表的长度
    • 广义表元素个数
  • n=0时ls被称为空表
  • 广义表元素
    • 是单个数据——叫广义表的原子
    • 是一个广义表——叫广义表的子表
  • 通常用大写字母——表示广义表 小写字母——表示原子
  • 当LS非空，首元素α1称为LS的表头，记作Head(LS)
    • 即广义表非空时 表头——是一个元素； 表尾——是一个表
    • 获取表头操作
    • 其余元素组成表尾，记作Tail(LS)
      • 获取表尾操作
  • 广义表的深度
    • 表中括号的最大层数
      • 深度可以是无穷
• 树BiTree
  • 树是树形结构的简称
  • 树结构具有层次性
  • 是非线性结构
  • 存在一对多的特点
  • 定义:树是n个元素（元素这里称作结点）的有限集
    • n=0，成为空树
  • 根结点
    • 在任意一颗非空树中，有且仅有一个根的结点
  • 子树
  • 结点的度
    • 度=这个结点拥有的子树棵树 或者：度=这个结点的分支个数
  • 树的度
    • 指一个树里最大的分支数
    • 树的度不等于结点的度
  • 叶子结点
    • 也叫终端结点
    • 指度=0的结点
  • 分支结点
    • 也叫非终端结点
    • 指度≠0的结点
  • 孩子结点
    • 子树的根节点叫孩子结点
  • 双亲结点
    • 孩子结点的上一层结点
  • 深度/高度
    • 树的最大层次
  • 堂兄弟
  • 有序树
    • 结点子树从左到右是有次序的不能更换
    • 反之，无序树
  • 森林
    • m颗互不相交的树的集合
  • 树是一个递归的定义
  • 树的性质
    • 1）度为m的树
      • 有两层含义
        • 1.这棵树里任意结点的度<=m
        • 2.至少有一个结点的度为m
      • 度为m的树的第n层最多有mⁿ-¹个结点
      • 高度为h时最少有 h+m-1个结点
    • 2)m叉树
      • 有两层含义题
        • 1.树里任意结点的度<=m
        • 2.所有结点的度可以<m
      • m叉树的第n层最多也有mⁿ-¹个结点
      • 高度为h时
        • 最多有 个结点
        • 最少有 h 个结点
    • 3）树的结点数=总度数+1
      • 结点数=分支结点+叶子结点
        • 叶子结点是度=0的结点
    • 4）具有n个结点的m叉树
      • 的最小高度为
  • 二叉树
    • 定义：任意结点的度<=2的有序树
    • 二叉树是有序树，每一个结点有左右之分， 左边叫左子树，右边是右子树 左子树的根节点叫左孩子 右子树的根节点叫右孩子
    • 二叉树的五种基本形态
      • ①空二叉树 ②只有根结点二叉树 ③右子树为空的二叉树 ④左子树为空的二叉树 ⑤左、右子树都非空的二叉树
    • n个结点可以构成多少种不同的二叉树
    • 性质
      • 深度为h的二叉树最多有 个结点
      • 在二叉树的第n层上最多有2ⁿ-¹个结点
      • 深度为h的二叉树最多有 个叶子结点
    • 满二叉树
      • 深度深度为h的二叉树最多有 个结点
      • 定义：如果深度为h的二叉树具有 个结点，该树叫做满二叉树
      • 满二叉树中每一个结点数都达到了最大值2ⁿ-¹个
      • 除叶子节点外，其他结点的度为2
    • 完全二叉树
      • 按层编号
        • 对满二叉树自上而下自左而右的顺序编号
      • 定义：一个深度为h，具有n个结点的二叉树，如果它的结点分布和深度为h的满二叉树的前n个结点相同，则称之为完全二叉树
      • 性质
        • 1）若完全二叉树的深度为h，则它的前h-1层是全满的。
        • 2）完全二叉树中叶子结点只可能出现在倒数前两层
        • 3）对任意一个结点，它右子树上的子孙的最大层为k，那左子树上的子孙的最大层为k或者k+1
        • 4）如果有度为1的结点，那只有一个
          • 且该节点只有左孩子没有右孩子结点
        • 5）结点树为
          • 奇数
            • 每一个分支结点都有左孩子和右孩子
          • 偶数
            • 编号最大的分支结点只有左孩子，没有右孩子
        • 6）子主结点树为n
          • 常考，注意是完全二叉树
          • n为奇数
            • 叶子结点有（n+1）/2个
          • n为偶数
            • 叶子结点有n/2个
        • 7）具有n个结点的完全二叉树的深度为
        • 对完全二叉树按层编号
          • 对任意一个结点i有以下结论
            • 1）i>1,这个结点的双亲结点为：
              • 向下取整
            • 2）若2i≤n，结点i的左孩子是结点2i。否则，结点i是叶子结点。
            • 3）)若2i+1≤n，结点i的右孩子是结点 2i+1 否则，结点i无右孩子
    • 二叉树的存储结构
      • 同线性表类似，二叉树也有顺序和链式两种存储结构。
      • 1)顺序存储结构
        • 可能考简答题
        • 顺序存储结构就是用一组地址连续的存储单元来存储二叉树的结点
        • 分情况说明
          • a)完全二叉树
            • 对于完全二叉树，可将结点按层序编号，然后依次存放在数组中。
              • 数组下标任然从0开始
          • b)一般二叉树
            • 1.首先将它与同深度的满二叉树作对比。 2.然后按结点在满二叉树中的位置，将其存储在一维数组的相应分量中。 3.对于不存在的结点，其相应数组分量置为0。
        • 适合存储完全·二叉树
      • 2）链式存储结构
        • 对于二叉树，通常用二叉链表来表示
        • 在二叉链表中，每个结点包含三个域
          • 左指针域Ichild
            • 存放的是其左孩子结点的地址（指向左孩子）。
          • 数据域data
            • 用来存储数据元素的值
          • 右指针域rchild
            • 存放的是其右孩子结点的地址（指向右孩子）。
        • 每个结点有两个指针，也叫二叉链表
        • 在二叉链表中，头指针指向根结点
        • 二叉链表中，叶子结点的左、右指针域为空
        • 在二叉链表中有些结点的指针域为空，在含有n个结点的二叉链表中，共有n+1个空结点
        • 基础定义
          • T->data————表示根节点的数据域 T->Ichild————表示根节点左孩子的地址 T->rchild————表示根节点右孩子的地址
          • 定义根结点指针
            • BiTree T;
          • 定义其他结点指针
            • BiTree P1，P2；
          • 创建结点
            • T=（BiTree）malloc(sizeof(BiNode)
        • 二叉树的遍历
          • 必考考点
          • 按一定的次序访问二叉树的所有结点，而且每个结点只能访问一次
          • 得到遍历序列的方法
            • 1）分支结点逐层展开法
            • 2）标点划线法
              • 可以用来验证方法一
          • 遍历方式
            • 1.先序遍历（先根变量）
              • 总结：根左右
              • 结论：在先序遍历中，根结点第一个被访问
                • 根节点是先序遍历的第一个结点
              • 先序遍历算法
                • 这几个代码要会写
                • 用函数实现
            • 2.中序遍历（中根遍历）
              • 总结：左根右
              • 中序遍历算法
              • 结论：在中序遍历中，左结点第一个被访问
                • 左节点是中序遍历的第一个结点
            • 3.后序遍历（后根遍历）
              • 总结：左右根
                • ！！！千万不要记错，不是右根左
              • 结论：在后序遍历中，根结点最后一个被访问
                • 根节点是后序遍历的最后一个结点
              • 后序遍历算法
            • 4.层序遍历
              • 一层一层遍历，自上而下，自左向右依次遍历
          • 由二叉树的遍历构造二叉树
            • 只知道二叉树的前、中、后序遍历序列的其中的一种，无法唯一的确定一棵二叉树。
            • 已知前序遍历序列+ 中序遍历序列可以唯一的确定一棵二叉树。
            • 已知后序遍历序列+中序遍历序列可以唯一的确定一棵二叉树。
            • 找出左、右子树，确定每一层的根节点
  • 树·的存储结构
    • 1.双亲表示法
      • 数组
      • 双亲表示法是用一片地址连续的存储区域来存储树的结点，并在每个结点中附设一个指示器，指示其双亲结点的位置。
        • 即数组
      • 根节点没有双亲结点，双亲位置写-1即可
      • 双亲位置写数字下标
      • 优缺点
        • 优点：找结点双亲非常容易
        • 缺点：找孩子结点非常麻烦
    • 2.孩子表示法
      • 普通单链表
      • 在孩子表示法中，树中每个结点的孩子存放在一个单链表中，而且这些单链表的头指针保存在一个一维数组里。
      • 单链表是有序的
      • 叶子结点的孩子链表为空表
      • 优缺点
        • 优点：找孩子结点非常容易
        • 缺点：找双亲结点非常麻烦
    • 3.孩子兄弟表示法
      • 二叉链表
      • 用二叉链表来表示，也叫二叉链表表示法/二叉树表示法
      • 二叉链表由3个域组成
        • 与其他二叉链表还是有不同的
        • 两个指针域，1个地址域
        • data——存放结点的值 firstchild——指针域，指向结点的第一个孩子结点 nextsibling——指针域，指向结点的右兄弟结点
  • 树和二叉树的互相转化
    • 原理：树的孩子兄弟表示法
    • 快捷法
      • 野路子，用来验证
      • 在已知数中划线 1）在亲兄弟间加一条边 2）除第一个·孩子外，删除与其他孩子的边
  • 森林和二叉树的相互转化
    • 建立在树和二叉树的互相转化
    • 核心
      • 对于一个森林，如果把其他树的根结点看成是第一棵树根结点的兄弟，则同样可以用二叉链表来存储，
    • 特点
      • 1)二叉树的根结点是森林中第一棵树的根结点。
      • 2）二叉树的左子树是由第一棵树根结点的子树森林所对应的二叉树。
      • 3）二叉树的右子树是由除第一棵树之外其余树组成的森林所对应的二叉树。
    • 快捷法
      • 同样可以用
      • 在已知数中划线 1）在亲兄弟间加一条边 2）除第一个·孩子外，删除与其他孩子的边
  • 树和森林的遍历
    • 因为树和二叉树可以相互转化，森林和树可以相互转换，所以树和森林的遍历可以转化成二叉树的遍历
    • • 树的遍历没有中根遍历
      • 森林的遍历没有后跟遍历
      • 第二个易错
    • 树和森林遍历序列的方法——也是那两种
      • 1）分支结点逐层展开法
      • 2）标点划线法
        • 可以用来验证方法一
  • 最优二叉树
    • 哈夫曼树
    • 必考题，考简答题
    • 路径
      • 树中一个结点到另一个结点之间的分支构成了两结点之间的路径
    • 路径长度
      • 路径上分支的数目（边数）称为该路径的长度。
    • 结点的权/权值
      • 在实际应用中，有时需要为树上的结点附上一个有特定意义的实数，
    • 结点的带权路径长度
      • 指从结点到根结点之间的路径长度与结点权值的乘积。
    • 树的带权路径长度
      • 指树中所有叶子结点的带全路径长度之和。
      • 通常记作WPL
    • 最优二叉树定义
      • 在含有n个带权叶子结点的二叉树中，其中带权路径长度(WPL)最小的二叉树称为哈夫曼树，也称为最优二叉树。
    • 最优二叉树不唯一
    • 哈夫曼树构造算法
      • 给n个权值，构造除最优二叉树， 求WPL
      • 操作
        • 1.根据给定的n个权值(W1,W2.....wn}
          • 每一个初始权值最终都会成为叶子结点
          • 最终哈夫曼树 根节点的权值=所有初始权值之和
          • 构造n棵二叉树
            • 每一棵只有一个根结点
        • 2.将n棵二叉树放到一个集合中F=(T1, T2,….Tn)，其 中Ti为只有权值为wi的根结点的二叉树
        • 3.在集合中选取两颗 根节点权值最小的 树
          • 分别作为左、右子树，构建一颗新二叉树
            • 一般小的放左子树
          • 新二叉树的根节点的权值=左子树根节点权值+右子树根节点权值
        • 4.将这两颗二叉树删掉
        • 5.将新二叉树加入到集合F中
        • 6不断重复3,4,5操作，直到集合中只剩一棵树为止
          • 这棵树是哈夫曼树
            • 哈夫曼树不唯一，但权值唯一
      • eg：以{1,2,2,37}为权值，构造哈夫曼树
        • 有n个权值
        • 每一颗二叉树只有一个根结点
        • 不断选取权值最小的两棵树构建新二叉树
      • 哈夫曼树不一定是完全二叉树
      • 每一个初始权值最终都会成为叶子结点
      • 一棵树有n个叶子结点的哈夫曼树，它的结点总数为：2n-1
      • 哈夫曼树中不存在度为1的树
    • 结论
  • 哈夫曼编码
    • 在数据通信中，若对每个字符 用相等长度的 二进制位 表示，这种编码方式称为哈夫曼编码
    • 编码长度是固定的
      • 每一个字符的 编码长度为2
    • 总长度编码也是这课二叉树的带权路径长度
    • eg：四个字符：A,B,C,D
      • 采用固定长度编码后： A： …00——出现了10次 B： …01——出现了8次 C： …10_——出现了（200-10--8-2）=80次 D： …11_——出现了2次 总长度编码为=2*（10+8+2）=200
    • 哈夫曼编码，约定左分支表示0，右分支表示1
    • 若允许对不同字符 用不等长度的 二进制表示，这种编码方式称为可变长度编码
      • 对应二叉树：
        • 编码长度就是单个叶子结点的带全路径长度
      • 哈夫曼编码也是一种可变长度编码
    • 得到哈夫曼编码
      • 1先构建哈夫曼树
      • 2.写编码序号
        • 约定左分支表示0，右分支表示1
      • 3.写成每个权值的序号（从根节点——到叶子结点）
      • 哈夫曼编码格式： 字符…序号
        • 中间不用加冒号
    • 哈夫曼编码也不是唯一的，但WPL唯一
    • 前缀编码
      • 没有一个编码是另一个编码的前缀，这样的编码是前缀编码
      • 哈夫曼编码就是一种前缀编码
      • eg A…11; B…1101————这两个编码不是前缀编码
      • eg A…11; B…1101————这两个编码是前缀编码
• 第七章图
  • 图是图型结构的简称，是一种非线性数据结构，它是我们迄今所学到的最复杂的结构，
  • 在线性表虫，每个数据元素只有一个直接前驱和直接后继，数据元素可排成一个序列。在树中，结点之间有明显的层次性，一个结点虽然可以和下层的多个结点相关，但只能和上层的一个结点相关。在图中，任意两个数据元素都可以相关。图被广泛地应用于交通、通信等领域。
  • 一图的基本定义
    • 图的定义
      • 与其他数据结构一样，图也是由数据对象和数据关系两部分构成，图通常记G=(V，R)，
        • 在研究图时，数据元素常被称作顶点
        • 简称顶点集，用|V表示图G中顶点的个数。
          • 顶点集
            • V是数据元素的集合，在研究图时，数据元素常被称作顶点，所以V是构成图的顶 点的集合，简称顶点集
              • V是一个非空集合，即至少要有一个顶点。
            • 用|V|表示图中顶点的个数。
        • R 描述了V中顶点之间的关系（边）
          • 用|E|表示图G中边的个数。
            • 图中的边可以为0
              • eg1:只有顶点没有边的图也是合法的
          • 一条边的两头必须都有顶点。
    • 2.弧和有向图
      • 在有向图中，顶点之间的关系是有方向的
      • 弧
        • 弧表示方法：<起点，终点>
          • 起点也叫弧尾，终点也叫弧头
          • 起点和终点不可以互换位置，意义是不一样的 eg:<v,w>≠<w,v>
        • 弧用尖括号表示
        • • 要知道这些式子的含义，会考画图
    • 3.边和无向图
      • 在无向图中，顶点之间关系是没有方向的
      • 边
        • 如果R是对称的（即如果<v,w>∈R，则一定有<w,v>∈R)，则称（v,w）或者（w,v）是一条边
      • 边用圆括号表示
    • 4.完全图和有向完全图
      • 任意一个有n个顶点的无向图它的边数e满足：
        • 无向完全图
          • 也叫完全图
            • 即任意两个顶点之间都有边
          • 当无向图有1/2(n(n-1)条边
      • 对于任一个有n个顶点的有向图，它的弧数a满足：n≤a≤n(n-1)
        • 有向完全图
          • 即任意两个顶点之间都有弧
          • 有n(n-1)条弧的有向图称为
    • 5.权和网
      • 权
        • 在有些应用中，需要为图的边/弧附设一个有特定意义的实数，该实数称为边/弧的权。
          • 注意：不是为顶点附设实数哦
      • 网
        • 也叫带权图
        • 这种带权的图称为网
    • 6.子图
      • 是原来图的一部分
      • 这一部分和原图的这一部分一模一样
    • 7.邻接点
      • 无向图
        • 两个顶点a,b间有一条边，就互为邻接点
          • 可以说a是b的邻接点，也可以说b是a的邻接点
          • 并称边（a,b）与顶点a,b相关联
      • 有向图
        • 两个顶点a,b间有一条弧，就称顶点a邻接到顶点b
          • 或顶点b邻接自顶点a
          • 并称弧<a，b>与顶点a， b相关联。
    • 8.顶点的度、入度和出度
      • 考小题较多
      • 2)对于有向图中某顶点v来说
      • ②入度
        • 记为ID(v)
          • 顶点V的入度=以它为终点的弧的数目
      • ③出度
        • 记为OD(v)
          • 顶点v的出度=以它为起点的弧的数目
      • 入度，出度都是对有向图而言
      • ①顶点的度
        • 记为TD(v)
          • 对于无向图中顶点v的度=与它相关联的边的数目
          • 对于有向图中顶点v的度=顶点v的入度+出度之和
      • 结论：有向图中，各个顶点的入度之和=出度之和=总弧线树
      • 结论：对于无向图，全部顶点的总度数=总边数的2倍
      • 常考
    • 9.路径、简单路径和环路
      • 顶点序列
        • 从顶点V到顶点W的路径是一个顶点序列（A,B,C）
      • 路径
        • 路径用圆括号（）表示
        • 无向图
          • 没有方向
            • v到w的路径和w到v的是一样的
        • 有向图
          • 在有向图中，顶点之间的路径也是有向的。
          • 有向图中，顶点v到w有路径 不代表顶点w到v也有路径
      • 简单路径
        • 如果在路径的顶点序列中无重复顶点，则称该路径为简单路径
      • 环路
        • 顶点序列第一个顶点与最后一个顶点相同的路径称为环路。
    • 10. 连通、连通图和连通分量
      • 只对于无向图而言
      • 连通
        • 连通不代表是连通图
        • 两个顶点间有路径，这两个顶点是连通的
      • 连通图
        • 只对于无向图而言
        • 如果图中任意两个顶点都是连通的，则G称为连通图
          • 环路上的顶点一定是强连通图
      • 无向图
        • 两个顶点间有路径，这两个顶点是连通的
        • 有些无向图本身虽然不是连通图，但它的某些子图是连通图
          • 我们把其中的极大连通子图（包含尽可能多的顶点和边）称为连通分量。
      • 连通分量
        • 只有一个顶点的子图也是连通分量
        • 要满足三点
          • 1.是无向图子图
          • 2.是连通图
          • 3.尽可能的更多的包含的顶点和边
            • 子图的所有顶点之间都有路径
        • 结论
          • 对于n个结点的无向图G
            • 1)若图G是连通图，则最少有n-1条边
              • 对有n个顶点的无向图，如果其边数少于n-1条，则肯定不是连通图。
            • 2)若图G是非连通图，则最多有
    • 11.强连通、强连通图和强连通分量
      • 只针对有向图而言
      • 强连通
        • 有向图中，两个顶点都是都是双向通行的，则这两顶点是强连通的
          • 要注意双向通行包括环路
            • 也就是说不是明显的双向箭头
            • 环路上的顶点一定是强连通图
      • 强连通图
        • 如果图中任意两个顶点都是强连通的，则称G为强连通图。
          • 有些有向图本身虽然不是强连通图，但它的某些子图是强连通图
            • 我们把其中的极大强连通子图称为强连通分量
      • 强连通分量
        • 要满足三点
          • 1.是有向图子图
          • 2.是强连通图
          • 3.尽可能的更多的包含的顶点和弧
            • 子图的所有顶点之间都是双相通行的
        • 结论
          • 对于n个结点的有向图G，若G是强连通图，则最少有n条弧
    • 12.生成树
      • 只对于无向图而言
      • 一个连通图的含有全部顶点的极小连通子图（边尽可能的少，但要保持连通）称为该图的生成树。
      • 要满足四点
        • 1.是连通无向图的子图
        • 2.是包含全部的顶点
        • 3.保持连通
          • 不一定是连通图
        • 4.边尽可能的少
          • 去掉边顶点就不连通了
      • 生成树不唯一
      • 对于有n个顶点的连通图特点:
        • 1）生成树有且仅有n-1条边。 2)生成树上不会含有环路。 3）在生成树上再添上一条边就会构成环路。
        • 对有n个顶点的无向图，如果其边数少于n-1条，则肯定不是连通图。
  • 二、图的常用基本操作
    • 了解即可，不考察代码
  • 三、图的存储结构
    • 必考内容·
    • 1）邻接矩阵表示法 2）邻接表表示法 3）十字链表表示法 4）邻接多重表表示法
      • 方法一二是考试的重点，其余两中知道名称即可
    • 研究图从两方面研究
      • 图G表示为：G=（V,R）
      • V是顶点集合，简称关系集 R是关系集合，简称关系集
      • 存储图时，不仅要存储顶点集还要存储关系集
    • 1.邻接矩阵表示法
      • 邻接矩阵
        • 邻接矩阵存储图的关系集
        • 定义：若图G=(V，R)有n个顶点，则其邻接矩阵A是一个n阶方阵，其矩阵元是这样确定的：
        • 里面的数值只有两种，0和1
        • • 简单点就是说两个顶点是有关系的，有边或者弧，结果就是1， 没有关系，没有边或者弧，结构就是0
        • 邻接矩阵表示法以行序为准
        • 邻接矩阵表示法使用默认规则
          • 顶点用数字标注
            • 各个顶点的序号是从小到大排列的如1,2,3,4,5……
          • 顶点用字母标注
            • 各个顶点的序号是按26个英文字母排列如a,b,c,d,……
        • 特点
          • 1)无向图的邻接矩阵是对称矩阵
            • a(i,j)=a(j,i)
          • 2)有向图的邻接矩阵不一定是对称矩阵。
          • 3)有向完全图的邻接矩阵是一个对称矩阵
          • 无向图的邻接矩阵中第i行元素的和就是顶点vi的度TD(vi)
          • 有向图的邻接矩阵中第i行元素的和就是顶点 vi的出度OD(vi) 第i列元素的和就是顶点vi的入度ID(vi)。
            • 有向图顶点的度=入度+出度
          • 利用邻接矩阵容易判断任意两个顶点间是否有强/边相连
        • 给定一个图的邻接矩阵要先判断是有向图还是无向图
          • 无向图是一个对称矩阵
        • 考试画邻接矩阵画成二维数组的
        • 邻接矩阵是唯一的
      • 邻接矩阵表示法用一维数组vexs来存储顶点信息
        • 二维数组arcs存储邻接矩阵
      • 邻接矩阵表示法的空间复杂度为O(|V|²)
        • |V|是图里顶点的个数
        • 适合稠密图
          • 稠密图：边比较多的图
      • 邻接矩阵表示也可以表示网
        • 给图的边或弧赋值称为权，带权的图称为网
        • 表示网时：矩阵里的数字不再是0和1
        • 当图顶点间
          • 当图顶点间有边或弧，矩阵里的数字是 ：权值
            • 此时自己到自己可以写0，也可以写无穷∞
          • 没有有边或弧，矩阵里的数字是 ：∞（数学无穷号）
    • 2）邻接表表示法
      • 邻接表 表示法是用一维数组来存储顶点集
        • 用一个单链表来存储所有相关联的边，并把头指针存在所示位置
      • 邻接矩阵表示法是唯一的
        • 可以判断邻接点，这是邻接点的次序也是唯一的
        • 上图：v1的邻接点有两个，v2和v3，其中v2是v1的第一个邻接点
      • • 无向图的顶点一维数组不需要画方格
      • 邻接表表示法不唯一
      • 邻接表表示法中顶点的度TD(vi）就是结点的个数————TD(V1)=2(有两个结点)
      • 邻接表中单链表结点的数量=无向图边的2倍
      • 有向图中
        • 结点的个数就是对应结点的出度
          • 邻接表表示法求出度容易，入度难
            • 因此发明了逆向的邻接表求入度
              • 结点的个数就是对应结点的入度
        • 单链表表示的是以顶点Vi为起点的弧（即V1—>V2）
        • • 无向图的顶点一维数组需要画方格
        • 邻接表结点数=有向边弧数
      • 邻接表空间复杂度
        • 有向图：O(|V|+2|E|)
        • 无向图：O(|V|+|E|)
      • 邻接表适合存储稀疏图
        • 稀疏图边特别少的图
  • 三、图的遍历
    • 必考题，考大题
    • 定义：从图的某一顶点出发，按一定的路径访问图中其它顶点，并且使每一顶点只被访问一次。
    • 为避免一个顶点被多次访问，我们设置一个标志数组visited
      • 标志数组的元素初值为0.
      • 一旦vi被访问了，便置相应数组元素为1。
    • 图的遍历方法有两种：
      • 不考代码
      • a)广度优先搜索遍历（简称BFS） b）深度优先搜索遍历（简称DFS）
        • 简称要记住
        • 这两种方法对无向图和有向图都适用。
        • 时间复杂度只有对应图的表示方法有关
          • 邻接矩阵表示法的空间复杂度为O(|V|²)
            • |V|是图里顶点的个数
            • 适合稠密图
              • 稠密图：边比较多的图
          • 邻接表复杂度
            • 无向图：O(|V|+|E|)
    • 1.广度优先搜索BFS
      • 类似于树的层次遍历
      • 不考代码
      • 对图做广度优先遍历
        • 广度优先生成树
          • 如果图是连通图，对其做优先遍历，生成的是广度优先生成树
            • 无向图——连通图——生成树
          • 对应·有n个顶点的图，他的优先生成树有n-1条边
          • 步骤
          • 列题
            • 题目中约定了邻接点次序的
              • 答案是唯一的
              • • 
              • • 
            • 题目中没有约定邻接点次序的
              • 答案不唯一，有多个
        • 广度优先生成森林
          • 如果图是非连通图，对其做优先遍历，生成的是广度优先生成森林
            • 非连通图——生成森林
          • 步骤：先对一个图遍历，在对另一部分遍历
    • b）深度优先搜索遍历（简称DFS）
      • 不考代码
      • 对图做深度优先遍历
        • 特点：一路走到黑
        • 深度优先生成树
          • 如果图是连通图，对其做优先遍历，生成的是广度优先生成树
            • 无向图——连通图——生成树
          • 对应·有n个顶点的图，他的优先生成树有n-1条边
          • 步骤：借助一个栈
            • 没有邻接点就返回
          • 列题
            • 题目中约定了邻接点次序的
              • 答案是唯一的
            • 题目中没有约定邻接点次序的
              • 答案不唯一，有多个
        • 深度优先生成森林
          • 如果图是非连通图，对其做优先遍历，生成的是广度优先生成森林
            • 非连通图——生成森林
          • 步骤：先对一个图遍历，在对另一部分遍历
  • 最小生成树
    • 绝对重点，考大题
    • 网：带权值的图
    • 最小生成树定义：权值之和最小的生成树
    • 最小生成树不唯一
    • 最小生成树问题
      • 在城市建设通信网问题
        • 使通信网连通且花费最小就是最小生成树问题
        • 顶点是城市
        • 边是通信线路
        • 边上的权值是花费开销
    • 最小生成树算法
      • 1.普里姆算法——Prim算法
      • 2.克鲁斯卡尔算法——Kruskal算法
    • 1.普里姆算法——Prim算法
      • 考试书写方法画图，计算代价（计算权值）
      • 从顶点开始
      • 时间复杂度O（n²）
      • 适合求边稠密的连通网的最小生成树
      • 步骤：
        • 1.从任意顶点X开始 2.选择权值最小的邻接点 3.按照原图的位置将该邻接点画出 4.继续从顶点X开始重复上面的步骤
    • 2.克鲁斯卡尔算法——Kruskal算法
      • 从边开始
      • 考试书写方法画图，计算代价（计算权值）
      • 时间复杂度O（elog₂e）
        • e是边数
      • 适合求边稀疏的连通网的最小生成树
      • 步骤：
        • 2.选择权值最小的边 3.使得两头的顶点连通 4.继续选择权值最小的边——原本连通的不选
          • 原本连通的不选——两个顶点间有路径——直接路径，间接路径都算
  • 最短路径
    • 路径的长度=路径上边或弧的权值之和
    • 用有向图
    • 最短路径问题
      • 书写方法打表格
      • 单源最短路径
        • 从某个顶点到其他各个顶点的最短路径
      • 单源最短路径算法
        • 迪杰斯特拉Dijkstra算法——不适用与带负权值的图
      • 步骤：每一轮都会确定一条V0到其他顶点的最短路径 每确定一个顶点，就将它加入到集合S中 两个顶点间没有路径就写无穷号∞
    • 见课本P102页
  • 七、拓扑排序
    • 考点：给一个有序图，找图它可能的所有拓扑排序
    • 1.有向无环图：是指无环路的有向图，简称DAG (Directed Acycline Graph)，常用它来描述一项工程或一个教学计划等。
    • 2.AOV网：它用有向图的顶点表示活动，用弧表示活动之间的优先关系。（即先后次序）
      • AOV网属于有向无环图
      • A_—>B代表先完成A，在完成B
      • 一个表示实际问题的AOV网中不应有环。
    • 3.拓扑排序：实际含义：找到做事的先后顺序
    • 概念了解即可
    • 4.拓扑序列不唯一
    • 5.拓扑排序步骤：
      • 1）在有向图中选取一个入度为0（没有前驱）的顶点输出。 2）从图中删除该顶点和所有以它为起点的有向边。 3) 重复步骤(1)和(2)直到全部顶点均已输出，或直到图中剩余部分无入度为 0 的顶点为止此时说明有向图中存在环）。
        • 因此可以通过拓扑排序检测一个图中有没有环
• 第八章查找
  • 1.查找
    • 查找又称为检索
    • 关键字(Key)： 静态查找表的顺序存储表示（简称顺序表）如下 图所示，为描述该存储结构，我们定义如下类型 105 徐小贱升本课堂
      • 特点/作用：唯一标识该元素的某个数据项的值，使用基于关键字的查找，查找结果应该是唯一的。
    • 查找长度：在查找运算中，需要对比关键字的次数称为查找长度。
    • 平均查找长度(ASL)：所有查找过程中进行关键字的比较次数的平均值。
    • 静态查找：只需要查找操作。
    • 动态查找：除了查找，还需要插入、删除数据。
    • 考试可能考简答题
  • 二、顺序查找
    • 顺序查找又叫线性查找，通常用于线性表，其思想是从头到尾挨个查找（或从尾到头）。
    • 通常采用顺序存储结构来表示静态查找表。
      • 顺序存储结构也就是顺序表
    • 静态查找表 的顺序存储结构表示简称顺序表
      • 用SSTable类型表示静态查找表 的顺序存储结构或顺序表
    • ST.elem[i].key 表示 ST这个查找表的第I条记录的关键字
    • 顺序查找结论： 最好情况：找到第n个记录仅需比较1次， 找到第i个记录比较n-i+1次 最坏的情况找到第1个记录需比较n次， 顺序查找算法的平均查找长度为(n+1)/2
      • 时间复杂度为O（n)
    • 算法
      • 要背
      • 哨兵可以得到减少循环中比较的次数，从而提高效率
      • • 顺序表下标为0的表是不保存记录的，是有其他作用的——用来设置哨兵
  • 三、折半查找（二分查找）
    • 绝对重点
    • 折半查找只适用于有序的顺序表，不适用于链表。
    • 背算法——107页
    • 判定树
      • 将折半查找法用二叉树来表示
      • 看判定树
        • 左子树对应左区间，右子树对应右区间
        • K值比根节点小走左子树，大走右子树
        • 二叉树缺少的位置补充虚拟结点——用来演示查找失败
    • 时间复杂度为O（log₂n)
    • 1)对于有n个记录的有序表，其判定树的高度为（log₂n +1）——向下取整。 2)折半查找算法的平均查找长度为ASLbs=log₂(n+1)-1。 3）不论查找成功与否，折半查找过程所需比较次数不超过判定树的高度h。 5）折半查找判定树中右子树结点数比左子树结点数多0或1个（平衡二叉树）。
  • 四、分块查找
    • 分块查找又称索引顺序查找，它吸取了顺序查找和折半查找各白的优点，既有动态结构。 又适用于快速查找。
    • 分块查找的基本思想是将查找表分块，块内的元素可以无序,但块间的元素是有序的，即第一个块中的最大关键字小于第二个块中的所有记录的关键字，
    • 查找表中有n个记录，每个块有S条记录
      • 用了顺序查找
        • 分块查找的平均查找长度为
          • 当分法
            • 平均查找长度最小值为
      • 用来折半查找
        • 分块查找的平均查找长度为
  • 哈希表
    • 考大题
    • 类似数组
    • 有叫散列表
    • Hash table
    • 是一种数据结构
    • 时间复杂度O（1）
    • 特点：数据元素队关键字与其存储地址直接相关（存在一种映射关系）
    • 通过哈希函数H(key)实现
      • 用哈希函数计算出的地址叫哈希地址
      • 将这些地址存储起来叫哈希表
    • 关键字存储位置：H(key)=key%m
      • m是哈希表关键字个数，即长度
    • 不同关键字的通过计算得到相同的存储地址————这几个关键字叫做同义词
    • 哈希冲突——一个哈希地址已经有关键字，存不下其他元素
    • 哈希函数构造法：除留余数法H(key)=key%p
      • %运算也叫MOD
      • p选择的是比m略小的质数
    • 处理哈希冲突的方法
      • 1.链地址法
        • 将同义词存放在同一个单链表中
        • 哈希函数对谁求余，哈希表的长度就是谁
          • 只限于拉链法
        • 表为空表，单链表中没有目标关键字，就是查找失败，查找长度=0
      • 2.再哈希法
      • 3.开放定值法
        • 公式：Hi=(H(key)+di)MODm
        • 题目中给的是最初的哈希函数H(key)，用于计算最初的哈希地址
        • 没有冲突计算出初始的哈希地址直接填写即可，有冲突重新计算
          • Hi
        • di是增量序列
        • 处理哈希冲突的方法：线性探测再散列
        • 向后找空位遇到第一个空位，填入
        • 空位子比较也算一次比较
• 第九章排序
  • 选择填空大题都考
  • L.r0+1]=L.r[0]; 例1.已知初始序列为(49，38，13，5.65.2797)，写出直接插入排序每一趟排序的结果。 三、希尔排序 (Shell) 直接插入排序在记录较少的时候，或在待排序列基本有序的情况下效果不错，正是基干 这两点，希尔提出了直接插入排序的改进方案希尔排序。 希尔排序的主要思想是，把待排的序列分割成若干个子序列，对这些子序列分别进行直 接插入排序。如此反复分割若干次，待整个序列变得基本有序时，再对所有记录进行一次直 接插入排序。 116
  • 排序分类
    • 外部排序和内部排序
  • 关键字递增叫做正序序列
    • 不特别声明就是正序序列
  • 关键字递减叫做逆序序列
  • 1）直接插入排序法
    • 相关结论： 1)直接插入排序法的时间复杂度为O(n2)。 2)直接插入排序法的最好时间复杂度为O(n)(序列原本有序)。 3)直接插入排序法的空间复杂度为O(1)。 4)直接插入排序法是稳定的排序方法。 5）直接插入排序法在序列基本有序或n较小时具有较好性能。
    • 有n个记录需要排序，需要n-1趟
    • 用在记录比较少的时候
  • 2）希尔排序
    • 先把序列分成若干部分，对这些片序列进行直接插入排序，在分割，在排序，最后整体排序
    • 重点如何分割
      • 设计一个递减的增量序列————增量序列最后一个必须是1
      • 增量序列有几个数代表排序几趟
    • 3)希尔排序是不稳定的排序算法。
  • 3）交换排序
    • 冒泡排序
      • 最好情况（原本有序）：比较次为数n-1，交换次数为0，最好时间复杂度为O(n）。 最坏情况（原本逆序）：比较次数=交换次数=（n-1）+(n-2)+.…+2+1=n(n-1)/2.最坏时间复杂度为O(n2)，综上所述冒泡排序法的平均时间复杂度为O(n2)。 冒泡排序法是一个稳定的排序算法
    • 快速排序
      • 选择第一个元素作为标尺，小于它的放在左边，大于它的数放在右边
      • 然后得到两个区间，【小于它的和它】，【大于它的和它】
      • 这个过程称为快速排序的第一次划分
      • 在这两个区间里再次分别选取区间第一个数做标尺，
        • 小于它的再放在左边，大于它的再数放在右边
      • 不断重复，直到之后每个区间只剩一个元素为止
      • 标尺叫做枢轴
      • 相关总结： 1)快速排序的平均时间为O(nlog2n)，最坏时间复杂度为O(n²)，实际应用表明，就平均时间而言，快速排序被认为是最好的内部排序方法。 2）当待排序列基本有序时，快速排序就蜕化为冒泡排序 3)快速排序是不稳定的排序算法。 →此明快排放本最低 4)与其他排序法相比，快速排序需要额外的栈空间，空间复杂度为O(log2n)。
  • 4）选择排序
    • 直接拍下，冒泡排序，简单选择排序都是简单排序法
    • 1. 简单选择排序
      • 有n个记录需要排序，需要n-1趟
      • 相关总结： 1）简单选择排序无论有序、逆序还是乱序都需要n-1躺处理。 2)简单选择排序需要交换n-1次记录，需要比较n(n-1)/2次。 因此，该算法的时间复杂度为O(n2)。 3)简单选择排序的空间复杂度为O(1)，是不稳定的排序算法。
    • 2.堆排序
      • 是一种特殊的数据结构
      • 英文单词heap
      • 考点：1）判断序列是否为堆 2）调整堆
      • 相关总结： 1)堆排序的时间复杂度为O(nlog2n) 3)快速排序是不稳定的排序算法。