考研408数据结构笔记汇总

这是一篇关于考研408数据结构笔记汇总思维导图，总结了绪论、线性表、栈、队列和数组、串、树和二叉树、图等知识点。

目录

• 第1章 绪论
• 第2章 线性表
• 第3章 栈、队列和数组
• 第4章 串
• 第5章 树和二叉树
• 第6章 图
• 第7章 查找
• 第8章 排序

第1章 绪论

• 基本概念
  • 数据
    • 数据：数据是信息的载体，是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
  • 数据元素、数据项
    • 数据元素、数据项：数据元素是数据的基本单位，通常作为一个整体进行考虑和处理。一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位（也是数据处理的最小单位）。
  • 数据对象、数据结构
    • 结构：各个元素之间的关系 数据结构、数据对象： 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 数据对象是具有相同性质的数据元素的集合，是数据的一个子集。
  • 数据类型、抽象数据类型
    • 数据类型、抽象数据类型： 数据类型是一个值的集合和定义在此集合上的一组操作的总称。 抽象数据类型（Abstract Data Type， ADT）是抽象数据组织及与之相关的操作（数据描述和操作声明）。
    • 1）原子类型
      • 原子类型：其值不可再分的数据类型。
    • 2）结构类型
      • 结构类型：其值可以再分解为若干成分(分量)的数据类型。
• 数据结构（三要素）
  • 同“数据结构的研究内容”
  • 逻辑结构
    • 数据元素之间的逻辑关系
    • 无结构（集合）
      • 各个元素同属一个集合，别无其他关系
    • 线性结构
      • 线性表、栈、队列 数据元素之间是一对一的关系。 除了第一个元素，所有元素都有唯一前驱;除了最后一个元素,所有元素都有唯一后继
    • 树状结构
      • 数据元素之间是一对多的关系。
    • 图状结构（网状）
      • 数据元素之间是多对多的关系。
  • 存储结构（物理结构）
    • 一个数据结构在计算机中的映像称为存储结构，数据的物理结构包括数据元素的表示和数据关系的表示 用计算机表示数据元素的逻辑关系 1.若采用顺序存储，则各个数据元素在物理上必须是连续的；若采用非顺序存储，则各个数据元素在物理上可以是离散的。 2.数据的存储结构会影响存储空间分配的方便程度。 3.数据的存储结构会影响对数据运算的速度
    • 顺序存储
      • 顺序存储：把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。
    • 链式存储
      • 链式存储：逻辑上相邻的元素在物理位置上可以不相邻，借助指示元素存储地址的指针来表示元素之间的逻辑关系。
    • 数据结构常考
    • 索引存储
      • 索引存储：在存储元素信息的同时，还建立附加的索引表。索引表中的每项称为索引项。索引项的一般形式是（关键字,地址）
    • 散列存储
      • 散列存储：根据元素的关键字直接计算出该元素的存储地址，又称哈希(Hash）存储
    • 特殊用途
  • 难点：区分逻辑结构和存储结构
  • 数据的运算
    • 数据的运算：施加在数据上的运算包括运算的定义和实现。运算的定义是针对逻辑结构的，指出运算的功能，运算的实现是针对存储结构的，指出运算的具体操作步骤。
• 算法的基本概念
  • 算法定义
    • 算法：算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 程序=数据结构＋算法
  • 五个特征
    • 五个特征：有穷性、确定性、可行性、输入、输出
      • 有穷性：一个算法必须总在执行有穷步之后结束，且每一步都可在有穷时间内完成。注：算法必须是有穷的，而程序可以是无穷的。 确定性：算法中每条指令必须有确切的含义，对于相同的输入只能得出相同的输出。 可行性：算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入：一个算法有零个或多个输入，这些输入取自于某个特定的对象的集合。 输出：一个算法有一个或多个输出，这些输出是与输入有着某种特定关系的量。
  • “好”算法的特征
    • 1）正确性
      • 正确性：算法应能够正确地解决求解问题。
    • 2）可读性
      • 可读性：算法应具有良好的可读性，以帮助人们理解。
    • 3）健壮性
      • 健壮性：输入非法数据时，算法能适当地做出反应或进行处理，而不会产生莫名其妙的输出结果。
    • 4）高效率与低存储量需求
  • 效率的度量（算法评价
    • 程序性能
      • 程序性能：运行一个程序所需要的内存大小和时间。
    • 时间复杂度（重点）
      • 时间复杂度：运行完程序所需要的时间，取决于问题的规模和待处理数据的初态
      • 如何估算算法时间复杂度
        • 一个算法由控制结构（顺序、分支和循环三种）和基本操作构成，则算法时间取决于两者的综合效果 算法的执行时间=基本操作(i)的执行次数×基本操作(i)的执行时间 算法的执行时间与基本操作执行次数之和成正比。 通常，我们只关注起决定性作用的基本操作，一般是最深层循环内的语句。 因此，近似地；算法的时间复杂度用该算法中起决定性作用的基本操作的执行次数估算。
        • ①找到一个基本操作（最深层循环）
        • ②分析该基本操作的执行次数x与问题规模n的关系
        • ③x的数量级O(x)就是算法时间复杂度T(n)
      • 常用技巧
        • 公式
          • a）加法公式
            • T(n)= T1(n) + T2(n)= O(f(n))+ O(g(n)) = O(max(f(n), g(n)))
          • b）乘法公式
            • T(n) = T1(n)×T2(n)= O(f(n))×O(g(n)) = O(f(n)×g(n))
        • 常见的渐进时间复杂度
          • O(1)< O(log n)< O(n)< O(nlog n)< O(n²)< O(n³)< o(2ⁿ)< O(n!)< O(nⁿ)
      • 三种复杂度
        • 最坏时间复杂度
          • 最坏时间复杂度：最坏情况下算法的时间复杂度
        • 平均时间复杂度
          • 平均时间复杂度：所有输入示例等概率出现的情况下，算法的期望运行时间
        • 最好时间复杂度
          • 最好时间复杂度：最好情况下算法的时间复杂度
    • 空间复杂度
      • 空间复杂度：运行完一个程序所需要的临时内存大小。 空间复杂度是算法所需存储空间的量度。 所需存储空间包括： ①存储程序本身所占用的存储空间。 ②程序中的输入和输出数据所占用的存储空间。 ③程序在运行过程中临时占用的存储空间。 一般情况下，①②与算法本身是无关的。 因此，空间复杂度重点讨论的是运行过程中临时占用的存储空间。 若临时空间相对于输入数据量是常数，则称此算法为原地工作或就地工作，即空间复杂度是O(1)
      • 如何计算
        • 普通程序
          • ①找到所占空间大小与问题规模相关的变量
          • ②分析所占空间x与问题规模n的关系
          • ③x的数量级O(x）就是算法空间复杂度S(n)
        • 递归程序
          • ①找到递归调用的深度x与问题规模n的关系
          • ②x的数量级O(x)就是算法空间复杂度S(n)
      • 常用技巧
        • 公式
          • a）加法公式
            • T(n)= T1(n) + T2(n)= O(f(n))+ O(g(n)) = O(max(f(n), g(n)))
          • b）乘法公式
            • T(n) = T1(n)×T2(n)= O(f(n))×O(g(n)) = O(f(n)×g(n))
        • 常见的渐进时间复杂度
          • O(1)< O(log n)< O(n)< O(nlog n)< O(n²)< O(n³)< o(2ⁿ)< O(n!)< O(nⁿ)
    • 考研41题三部曲
      • 1）思想
      • 2）代码（C、C++）
      • 3）度量（T(n)、S(n)）
• 刷题笔记
  • 前缀码
    • 前缀码，是在有效字符前加的通用型代码。任何一个字符的编码都不能是其他字符编码的前缀，此即前缀码特性。具有前缀码特性的编码即为前缀码。
  • 抽象数据类型的定义
    • 抽象数据类型可以用数据对象、数据关系和基本操作来定义。
  • 逻辑结构与存储结构的关系
    • 逻辑结构独立于存储结构
  • 排序算法的时间复杂度
    • 通过元素比较和交换来进行排序的排序算法的时间复杂性下界为O(nlog n) 插入排序、快速排序、希尔排序的时间复杂度为O(n²)，选择排序分为直接选择和堆排序，其中堆排序时间复杂度为O(nlog n)
  • 散列存储的特征
    • 结点的存储地址与其关键字之间存在某种映射关系
  • 稀疏矩阵的快速转置算法
  • 微机中的信息单位
    • 在微机中，作为一个整体存储，传送和处理的数据信息单位是字节
  • 哈希表的开放定址法
    • 开放定址法： Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1) 其中m为表长，di为增量序列 如果di值可能为1,2,3,..,m-1，称线性探测再散列。 如果di取值可能为1²,-1²,2²,-2²,3²,-3²,4²,-4²,...k²,-k²(k<=m/2)，称二次探测再散列。
  • 基数排序算法
  • 图状结构的邻接表
  • 稳定排序和不稳定排序
    • 稳定排序：排序前后两个相等的数相对位置不变，则算法稳定 不稳定排序：排序前后两个相等的数相对位置发生了变化，则算法不稳定 稳定排序算法包括：冒泡排序、鸡尾酒排序、插入排序、桶排序、计数排序、合并排序、基数排序、二叉排序树排序 不稳定排序包括：选择排序、希尔排序、组合排序、堆排序、平滑排序、快速排序
  • B树（平衡查找树）
  • 二叉树的遍历方法
    • 先序遍历、中序遍历、后序遍历、层次遍历
  • 哈希表的冲突处理
    • 开放定址法（线性探测法、平方探测法、伪随机探测法）、再哈希法、链地址法
  • 逻辑文件
    • 用户把观察到的且可以处理的信息根据使用要求构造成文件，这种构造方式称为文件的逻辑结构，又叫逻辑文件，逻辑文件包括流式文件和记录式文件
  • 递归出口和递归体
  • 多维数组的存储方式
    • 对于二维数组或多维数组，分为按行优先顺序和按列优先顺序两种不同的存储方式存储。
  • 表达式的基本运算分量
    • 常量、变量、数组、指针
  • 值参数与变量参数
    • 与值参数对应的实在参数是值实在参数，与变量参数对应的实在参数是变量实在参数
  • 指针类型的定义
    • 指针类型是由指针及变量组成的集合
  • 函数副作用
    • 指当调用函数时，除了返回函数值之外，还对主调用函数产生附加的影响
  • 常用的数据模型
    • 层次模型、网状模型、关系模型
  • 形式参数与实在参数
    • 若需要利用形参直接访问实参，则应把形参变量说明为引用参数。
  • 记录的定义
    • 记录：是与一个公共标志有关的数据项的集合。

第2章 线性表

• 线性表的定义和基本操作
  • 定义
    • 线性表： （1）n(>=0)个数据元素的有限序列，记作()，其中a是线性表中的数据元素，n是表的长度（n=0为空表，即表中不含任何元素）。 （2）是线性表中的“第i个”元素线性表中的位序（注意：位序从1开始数组下标从0开始）。 逻辑特征（n>0） 存在唯一的一个被称做“第一个”的数据元素（如） 存在唯一的一个被称做“最后一个”的数据元素（如） 除第一个数据元素外，其他元素均只有一个直接前驱 除最后一个数据元素外，其他元素均只有一个直接后继 
    • 值得注意的特性
      • 数据元素同类型、有限、有序
    • 重要术语
      • 表长、空表
      • 表头、表尾
      • 前驱、后继
      • 数据元素的位序
  • 基本操作
    • ①对数据的操作（记忆思路）——创销、增删改查 ②C语言函数的定义——<返回值类型>函数名(<参数1类型>参数1, <参数2类型>参数2, ...... ③实际开发中，可根据实际需求定义其他的基本操作 ④函数名和参数的形式、命名都可改变（Reference：严蔚敏版《数据结构》） ⑤什么时候要传入引用“&”——对参数的修改结果需要“带回来”
    • 创销、增删改查
      • lnitList( &L )
        • //构造一个空的线性表L &：传递引用，能直接将形参值返回给实参
      • DestroyList( &L )
        • //销毁L
      • ClearList( &L )
        • //将L置为空表
      • PriorElem( L, cur_e, &pre_e )
        • //求前驱的值
      • NextElem( L, cur_e, &next_e )
        • //求后继的值
      • GetElem( L, i, &e )
        • //取i位置数据元素的值
      • LocateElem( L, e, equal( ) )
        • //在线性表中查找e
      • Listlnsert( &L, i, e )
        • //在i位置插入值为e的数据元素
      • ListDelete( &L, i, &e )
        • //删除i位置的数据元素
    • 判空、判长、打印输出
      • ListEmpty( L )
        • //判断L是否空
      • ListLength( L )
        • //求L的长度
      • ListTraverse( L, visit( ) )
        • //遍历线性表
    • 其他值得注意点
      • 理解什么时候要传入参数的引用“&” 函数命名要有可读性
• 顺序存储
  • 顺序表
    • 顺序表： 用顺序存储的方式实现线性表顺序存储。把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中，元素之间的关系由存储单元的邻接关系来体现。  优点：可随机存取,存储密度高 缺点：要求大片连续空间，改变不方便
    • 静态分配
      • 静态分配 #define MAX 100 ElemType elem[MAX]; // 表 int n; // 数据元素个数n<MAX 没有反映元素个数n和表的内在联系 静态分配 用结构体将顺序表的相关信息封装起来 #define MAX 100 //最大元素个数 typedef struct { ElemType elem[MAX]; int length; //元素个数，即表长 }Sqlist; 给各个数据元素分配连续的存储空间,大小为MaxSize*sizeof(ElemType)
    • 动态存储
      • 动态存储 #define LIST_INIT_SIZE 100 //存储空间的初始分配量 #define LISTINCREMENT 10 //分配增量 typedef struct { ElemType *elem; //存储区域的基址 int length; //当前表的长度 int listsize; //当前已分配的存储容量 }SqList; //顺序表类型 注意事项： （1）动态申请和释放内存空间 （2）C——malloc、free函数 L.data =(ElemType *) malloc (sizeof(ElemType) * InitSize) (3）C++——new、delete关键字
    • 顺序表的基本操作（重难点）
      • 初始化顺序表
        • 初始化顺序表InitList_Sq ( &L ) 操作结果：构造一个空的顺序表L Status InitList_Sq ( sqList &L ) //构造一个空的顺序表L { L.elem= (ElemType*) malloc(LIST_INIT_SIZE*sizeof(ElemType)); if (!L.elem) exit (OVERFLOW); // 存储空间分配失败 L.length=0; L.listsize=LIST_INIT_SIZE; return OK; } //InitList_Sq Status：整型int的宏定义 本算法的时间复杂度为O(1)。
      • 求表的长度
        • 求表的长度：L.length
      • 销毁顺序表
        • 销毁顺序表DestroyList_Sq (&L)释放L占用的内存空间。 void DestroyList_sq (sqList &L) { free(L.elem); L.elem=NULL; L.length=0; L.listsize=0; } free：仅仅将指针L.elem释放，并没有释放顺序表原来的各元素所占用的空间
      • 判定是否为空表
        • 判定是否为空表ListEmpty_Sq(L) 若L为空表，则返回1，否则返回0。 int ListEmpty_Sq (SqList L) { return ( L.length = =0 ); }
      • 输出顺序表
        • 输出顺序表DispList_Sq (L) 当L不为空时，顺序显示L中各元素的值。 status DispList_Sq (sqList L) { if ( ListEmpty_Sq(L) ) return ERROR; for (i=0; i<L.length; i++) printf ( L.elem[i] ); return OK; }
      • 插入数据元素
        • 插入数据元素Listlnsert_Sq (&L, i, e) 在顺序表L的第i个位置(1≤i≤L.length+1)前插入新元素e。 Status ListInsert_Sq( SqList &L, int i, ElemType e) { //在顺序表L中第i个位置之前插入数据元素e if (i<1 || i>L.length+1) return ERROR; //i值不合法 if(L.Length>=L.listsize){ //上溢时，增加空间 newbase=(ElemType*)realloc(L.elem, (L.listsize + LISTINCREMENT)*sizeof(ElemType)); if ( !newbase) exit( OVERFLOW ); //存储分配失败 L.elem=newbase; L.listsize+=LISTINCREMENT; } //if for ( j=L.length; j>=i; j-- ) L.elem[j]= L.elem[j-1]; //元素后移(从最后一个元素开始) L.elem[i-1]=e; //在位置i处插入元素e(注意位序与elem下标) ++L.length; //顺序表长度增1 return OK; }
        • 时间复杂度
          • 关注最深层循环语句的执行次数与问题规模n的关系问题规模n = L.length（表长） 最好情况：新元素插入到表尾，不需要移动元素i = n+1，循环0次； 最好时间复杂度=O(1) 最坏情况：新元素插入到表头，需要将原有的n个元素全都向后移动i =1，循环n次； 最坏时间复杂度=O(n); 平均情况：假设新元素插入到任何一个位置的概率相同，则长度为n的线性表中插入一个结点时，所需节点的移动次数为：  平均时间复杂度=O(n)
      • 删除数据元素
        • 删除数据元素ListDelete_Sq ( &L, i, &e) 删除顺序表L中的第i(1≤i≤L.length)个元素。 Status ListDelete_Sq (SqList &L, int i, ElemType &e) { if (i<1 || i>L.length ) return ERROR; //合法位置? e=L.elem[i-1]; for ( j=i; j<L.length;j++ ) L.elem[j-1]=L.elem[j]; //元素前移（从第i+1个位置开始） --L.length; //顺序表长度减1 return OK; }
        • 时间复杂度
          • 关注最深层循环语句的执行次数与问题规模n的关系问题规模n = L.length（表长） 最好情况：删除表尾元素，不需要移动其他元素i =n，循环0次； 最好时间复杂度=O(1) 最坏情况：删除表头元素，需要将后续的n-1个元素全都向前移动i = 1，循环n-1次； 最坏时间复杂度=O(n)； 平均情况：假设删除任何一个元素的概率相同，则长度为n的线性表中插入一个结点时，所需节点的移动次数为：  平均时间复杂度=O(n)
      • GetElem(L,i)
        • GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。 #define Initsize 10 //顺序表的初始长度 typedef struct{ ElemType *data; //指示动态分配数组的指针 int Maxsize; //顺序表的最大容量 int length; //顺序表的当前长度 } SeqList; ElemType GetElem(SeqList L, int i) { return L.data[i-1]; } 时间复杂度：O(1) 由于顺序表的各个数据元素在内存中连续存放，因此可以根据起始地址和数据元素大小立即找到第i个元素——“随机存取”特性
      • LocateElem(L,e)
        • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。 #define Initsize 10 //顺序表的初始长度 typedef struct{ ElemType *data; //指示动态分配数组的指针 int Maxsize; //顺序表的最大容量 int length; //顺序表的当前长度 } SeqList; //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SeqList L,ElemType e) { for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; //数组下标为i的元素值等于e，返回其位序i+1 return 0; //退出循环，说明查找失败 }
        • 时间复杂度
          • //在顺序表L中查找第一个元素值等于e的元素，并返回其位序 int LocateElem(SeqList L,ElemType e) { for(int i=0;i<L.length;i++) if(L.data[i]==e) return i+1; //数组下标为i的元素值等于e，返回其位序i+1 return 0; //退出循环，说明查找失败 } 关注最深层循环语句的执行次数与问题规模n的关系问题规模n = L.length（表长） 最好情况：目标元素在表头 循环1次；最好时间复杂度=O(1) 最坏情况：目标元素在表尾 循环n次；最坏时间复杂度= O(n)； 平均情况：假设目标元素出现在任何一个位置的概率相同，则在长度为n的线性表中查找值为e的元素所需的平均次数为：  平均时间复杂度= O(n)
      • 代码要点
        • 代码中注意位序i和数组下标的区别 算法要有健壮性，注意判断i的合法性 移动元素时，是靠前的元素开始，还是从表尾开始? 分析代码，理解为什么有的参数需要加"&"引用
• 链式存储
  • 单链表（重点）
    •  优点：不需要大片连续空间，改变容量方便 缺点：不能随机存取，要耗费一定空间存放指针
    • 定义单链表
      • typedef struct LNode{ //定义单链表节点类型 ElemType data; //数据域 struct LNode *next; //指针域 }LNode,*LinkList; struct LNode * p =(struct LNode *) malloc(sizeof(struct LNode)) 增加一个新的结点：在内存中申请一个结点所需空间，并用指针p指向这个结点 typedef 关键字——数据类型重命名 要表示一个单链表时，只需声明一个头指针L，指向单链表的第一个结点 Lnode * L; //声明一个指向单链表第一个结点的指针 LinkList L; //声明一个指向单链表第一个结点的指针
      • 无头结点单链表
        • 空表时，head为NULL。第1个结点只能由head指针变量指向，其余结点是直接前驱结点的指针域所指向的结点。即…->next。 
        • 定义一个不带头结点的单链表
          • typedef struct LNode{ //定义单链表节点类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个空的单链表 bool InitList(LinkList &L) { L= NULL; return true; } //判断单链表是否为空 bool Empty(LinkList L) { if (L== NULL) return true; else return false; }
      • 有头结点（便于插入/删除的实现）
        • 空表时，head指向一个结点，即头结点。 除头结点外其余结点均是直接前驱结点的指针域所指向的结点。即…->next。 
        • 定义一个带头结点的单链表
          • typedef struct LNode{ //定义单链表节点类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode,*LinkList; //初始化一个单链表（带头结点） bool InitList(LinkList &L) { L = ( LNode *) malloc(sizeof(LNode)); //分配一个头结点 if (L==NULL) //内存不足，分配失败 return false; L->next = NULL; //头结点之后暂时还没有节点 return true; } //判断单链表是否为空（带头结点） bool Empty(LinkList L) { if (L->next== NULL) return true; else return false; }
    • 单链表的基本操作（重难点）
      • 单链表按位序插入（带头结点）
        • Listlnsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e 找到第i-1个结点，将新结点插入其后 Status ListInsert (LinkList &L, int i, ElemType e) { //将值为e的结点插入到第i个位置 p=L; j=0; while( j<i-1 && p!=NULL ) //遍历到第i-1个结点或到表尾 { j++; p=p->next; //遍历 } //end of while if (p==NULL ll j>i-1) return ERROR; //i>表长加1或i<1 s=(LinkList)malloc(sizeof(LNode)); //创建新结点s if (s ==NULL) exit( OVERFLOW ); //存储分配失败 s->data=e; //将s的数据域置为e s->next=p->next; //将s插入到p之后 p->next=s; return OK; }//ListInsert 最好时间复杂度T(n)=O(1) 最坏时间复杂度T(n)=O(n) 平均时间复杂度T(n)=O(n)
      • 单链表按位序插入(不带头结点)
        • ListInsert(&L,i,e)：插入操作。在表L中的第i个位置上插入指定元素e 找到第i-1个结点，将新结点插入其后 int ListInsert (LinkList &L, int i, ElemType e) { if (i==1) {//对i为1的插入位置特殊处理 s=(LinkList) malloc ( sizeof(LNode) ); //建新结点s if (s==NULL) exit(OVERFLOW); s->data=e; s->next=L; //插入结点s L=s; //修改头指针 } //end of if else { p=L; j=1; ..... //与有头结点的类似 } return OK; } 结论：不带头结点写代码更不方便，推荐用带头结点 注意：考试中带头、不带头都有可能考察，注意审题
      • 单链表的删除（带头结点）
        • ListDelete(&L,i,&e)：删除操作。删除表L中第i个位置的元素，并用e返回删除元素的值。 找到第i-1个结点，将其指针指向第i+1个结点，并释放第i个结点 int ListDelete (LinkList &L, int i, ElemType &e) { //设L带头结点 j=0; p=L; while (j<i-1 && p->next) //遍历到第i-1个结点或遍历到表尾 { j++; p=p->next; } if( !(p->next)|lj>i-1)) return ERROR; //位置不合理 q=p->next; //q指向要删除的结点 e=q->data; //用e将被删除元素带回到主调函数中 p->next=q->next; //从单链表中删除q结点 free(q); //释放q结点 return OK; }
      • 单链表的查找（带头结点）
        • 按位查找
          • GetElem(L,i)：按位查找操作。获取表L中第i个位置的元素的值。 求表L中指定位置的某个数据元素GetElem( L, i,&e ) 在单链表L中从头开始找到第i个结点，若存在第i个结点，则将其data域值赋给变量e。 int GetElem ( LinkList L, int i, ElemType &e) { p=L->next; j=1; while( j<i && p!=NULL ) //判断是否找到指定位置或者表尾 { j++; p=p->next; } if( j>i ll p==NULL ) return 0; //不存在第i个结点 //存在第i个结点 e=p->data; return 1; } 平均时间复杂度：O(n)
        • 按值查找
          • LocateElem(L,e)：按值查找操作。在表L中查找具有给定关键字值的元素。 按元素值查找LocateElem( L, e) 在单链表L中从头开始找第1个值域与e相等的结点，若存在，则返回位置，否则返回0。 int LocateElem ( LinkList L,ElemType e ) { p=L->next; n=1; while( p!=NULL && p->data!=e ) //判断是否找到或者遍历到表尾 { p=p->next; n++; } if(p==NULL) return 0; else return n; } 时间复杂度：O(n)
      • 单链表的建立
        • 本节探讨带头结点的情况
        • 尾插法
          • 尾插法——新结点插入到最后一个结点之后。 ①建立新结点s ②向新结点s中添入内容 ③将新结点s链入链尾：r->next=s ④改变尾指针：r=s void CreateList_LR (LinkList &L, int n) { //尾插法创建 L=(LinkList ) malloc (sizeof(LNode)); //创建头结点 L->next=NULL; //将头结点next域置空 r=L; //r始终指向尾结点 for ( i=o; i<n; i++ ) { s=(LinkList)malloc(sizeof(LNode)); //创建新结点 scanf ( &s->data ); r->next=s; //将s插入r之后 r=s; //r指向新尾结点 } r->next=NULL; //尾结点next域置为NULL }
        • 头插法
          • 头插法——新结点插入到链表中第1个数据结点之前，即头结点之后。 ①建立新结点s ②向新结点s中添入内容 ③使新结点s的指针域指向第1个数据结点：s->next=L->next ④改变头结点指针域：L->next=s void CreateList_LF (LinkList &L, int n) { //建立链表，含n个数据元素 L = (LinkList)malloc(sizeof(LNode)); //创建头结点 L->next = NULL; //将头结点的next域置空 for(i=0; i<n; i++) //创建n个数据结点 { //创建新结点s s = (LinkList) malloc (sizeof(LNode) ); scanf (&s->data); //将s插在第1个数据结点之前，即紧跟头结点后 s->next = L->next; L->next = s; } } 插入一个结点需时间为：O(1) 头插法创建单链表的时间复杂度：T(n)=O(n)
  • 双链表
    • 为什么要使用双链表
      • 单链表：无法逆向检索，有时候不太方便 双链表：可进可退，存储密度更低
    • 双链表的定义
      • 采用类似于单链表的类型定义，具体如下： typedef struct DNode //定义双向链表结点类型 { ElemType data; struct DNode *prior; struct DNode *next; }DNode,*DLinkList;
    • 双链表的插入
      • 双链表的插入：在p结点之后插入s ①找到插入位置的前驱p; ②创建新结点s; ③s->data = x; ④s->prior =p; ⑤s->next = p->next; ⑥p->next = s; ⑦s->next->prior = s;
    • 双链表的删除
      • 双链表的删除：删除第i个结点 ①找到将被删除结点p; ②p->prior ->next = p->next; ③p->next ->prior = p->prior; ④free(p);
    • 双链表的遍历
      • 后向遍历 while (p!=NULL) {//对结点p做相应处理，如打印 p= p->next; } 前向遍历 while (p!=NULL) {//对结点p做相应处理 p =p->prior; } 前向遍历（跳过头结点） while (p-> prior != NULL) {//对结点p做相应处理 p = p->prior; } 双链表不可随机存取，按位查找、按值查找操作都只能用遍历的方式实现。时间复杂度O(n)
  • 循环链表
    • 循环链表的特点是表中最后一个结点的指针域不再是空，而是指向表头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到链表中其他结点。
    • 定义循环单链表
      • typedef struct LNode{ //定义单链表结点类型 ElemType data; //每个节点存放一个数据元素 struct LNode *next; //指针指向下一个节点 }LNode，*LinkList; //初始化一个循环单链表 bool InitList(LinkList &L) { L = (LNode *) malloc(sizeof(LNode)); //分配一个头结点 if (L==NULL) //内存不足，分配失败 return false; L->next = L; //头结点next指向头结点 return true; } //判断结点p是否为循环单链表的表尾结点 bool isTail(LinkList L, LNode *p){ if (p->next==L) return true; else return false; } //判断循环单链表是否为空 bool Empty( LinkList L) { if (L->next == L) return true; else return false; }
    • 定义循环双链表
      • typedef struct DNode{ ElemType data; struct DNode *prior,*next; }DNode, *DLinklist; //初始化空的循环双链表 bool InitDLinkList(DLinklist &L){ L = (DNode *) malloc(sizeof( DNode)); //分配一个头结点 if (L==NULL) //内存不足，分配失败 return false; L->prior = L; //头结点的 prior指向头结点 L->next = L; //头结点的 next指向头结点 return true; } //判断结点p是否为循环单链表的表尾结点 bool isTail(DLinklist L, DNode *p){ if (p->next==L) return true; else return false; } //判断循环双链表是否为空 bool Empty(DLinklist L) { if(L->next == L) return true; else return false; }
  • 静态链表
    • 静态链表可借用一维数组来描述。 数组元素（元素的值、指示器）表示结点。 指示器（游标cur，即伪指针）代替指针以指示结点在数组中的相对位置。数组中的第0个分量可看成头结点，其指针域指示静态链表的第1个结点。需要预先分配一个较大空间，但是在进行插入和删除操作时不需要移动元素，仅需要修改“指针”，因此仍具有链式存储结构的主要优点。  
    • 静态链表初始化
      • 把a[0]的next设为-1 把其他结点的next设为一个特殊值用来表示结点空闲，如-2 typedef struct { //静态链表结构类型的定义 ElemType data; //存储数据元素 int next; //下一个元素的数组下标 }SLinkList [MaxSize];
    • 静态链表的基本操作
      • （1）查找：从头结点出发挨个往后遍历结点 （2）插入位序为i的结点： ①找到一个空的结点，存入数据元素 ②从头结点出发找到位序为i-1的结点 ③修改新结点的next ④修改i-1号结点的next （3）删除某个结点： ①从头结点出发找到前驱结点 ②修改前驱结点的游标 ③被删除结点next设为-2
  • 顺序表和链表的比较
    •  1.基于时间的考虑 1）顺序表可随机存取元素，而链表中元素都需从头指针开始遍历链表才能访问到。 2）在链表中任何位置上插入、删除都只要修改指针，而顺序表需要移动表中将近一半的元素。尤其是对于结点信息量较大的表，开销很大。 3）对于只进行访问型操作的线性表，宜采用顺序存储，对于加工型的线性表，则考虑使用链表。 2.基于空间的考虑 1）顺序表的存储空间在程序执行之前必须明确规定，若表的变化较大，则存储规模难以确定。（估计过大则容易造成浪费，估计太小，则使得存储扩充增多）。 2）链表的存储空间动态分配，只要内存空间尚有空闲，就不会溢出，适合于表长变化较大的情况。 
• 刷题笔记
  • 合并两个循环单链表的时间复杂度
    • 若将长度为n的循环单链表链接在长度为m的循环单链表之后，其算法时间复杂度为O(m+n)。 根据题目的描述属于“尾插法”。 1.将长度为m的单链表头部固定，设立一个指针进行向尾部搜索，找到尾部的时间复杂度为O(m) 2.搜索长度为n单链表的头结点，时间复杂度为O(1) 3.由于是循环单链表，故还需遍历一下长度为n单链表，把最后一个结点的指针指向头节点 4.所以总的时间复杂度为O(m+n)
  • 单链表删除运算时的指针修改
    • 链队列中删除元素一般仅修改队头指针，但只有一个元素时，出队后队空，此时还要修改队尾指针。
  • O(1)时间内在单链表表尾插入新结点的方法
    • 采用带表头结点的单循环链表，一个链表指针指向表头结点，结点插入方法为：在表头结点和第一个元素中间插入一个新的表头结点，原来的表头结点改为让在表尾插的新结点。这样就可以形成在表尾插入新结点，并且时间复杂度为O(1)。
  • 顺序表插入结点的平均移动次数
    • n个元素，则下标为0~n-1，可插入的位置有n+1个 当元素插在第n号位置时，需要移动0个元素； 当元素插在第n-1号位置时，需要移动1个元素； 当元素插在第n-2号位置时，需要移动2个元素； 以此类推...... 当元素插在第0号位置时，需要移动n个元素所以，平均需要移动(0+1+2+3+......+n)/(n+1) = n/2
  • 升序链表合并为降序链表的时间复杂度
    • m、n是两个升序链表，长度分别为m和n。在合并过程中，最坏的情况是两个链表中的元素依次进行比较，直到两个链表都到表尾，即每个元素都经过比较，时间复杂度为O(m+n)=O(max(m,n))。
  • 模式匹配
    • 子串的定位操作通常称作串的模式匹配，是各种串处理系统中最重要的操作之一，算法的基本思想是：从主串的开始字符起，与模式的第一个字符比较，若相等，则继续比较后续字符，否则从主串的下一个字符起再重新与模式的字符比较，依次类推，直至模式中的每一个字符依次和主串中的一个连续的字符序列相等，称匹配成功，否则称匹配不成功。
  • 单链表链接的时间复杂度
    • 将长度为n的单向链表链接在长度为m的单向链表之后的算法的时间复杂性为O(m)，链接两个单链表，需要找到长度为m的链表的尾结点
  • 广义表head与tail运算
  • 串的next数组值和nextval数组值
  • 存储密度
    • 存储密度=单链表数据项所占空间/结点所占空间 结点所占空间=数据项所占空间+存放后继结点地址的链域。
  • 折半插入排序法
    • 基本思想：在插入第i个元素时，对前面0~i-1元素进行折半，先跟他们中间的那个元素比较，如果小了，则对前半再进行折半，否则对后半部分进行折半处理，直到left>right，然后再把第i个元素与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。
  • 循环队列的存储结构
    • 循环队列是顺序存储结构
  • 均匀哈希函数
    • 在构建哈希表时，为了尽量减少冲突，要求构建的哈希函数尽量是均匀的，就是将随机来的关键字按照等概率均匀分配到存储空间中。
  • 顺序文件
    • 顺序文件的最佳应用场合，是在对诸记录进行批量存取时，即每次要读或写一大批记录。如果存取第i个记录，必须从头开始进行存取。因此需要先存取前i-1条记录。
  • 广义表的存储
    • 由于广义表的数据元素可以是原子或广义表，因此难以用顺序存储结构表示，通常采用链式存储结构。
  • 栈与数组操作的特殊性
    • 栈不能查找，数组不能删除
  • 有序表和无序表查找失败时的查找长度
    • 查找失败的情况下，无序表查找需要更长， 举例： 有序：1235678无序：3215678 当查找4时，有序表只要查到5就可以退出查找，而无序表则需全部遍历
  • 索引顺序文件
    • 索引顺序文件是一种特殊的顺序文件，只能放在磁盘上

第3章 栈、队列和数组

• 操作受限的线性表
  • 栈
    • 栈的基本概念
      • 定义
        • （1）线性表是具有相同数据类型的n（n≥0）个数据元素的有限序列，其中n为表长，当n =0时线性表是一个空表。若用L命名线性表，则其一般表示为  （2）栈是一种只能在一端进行插入、删除操作的线性表。 （1）允许进行插入、删除操作的一端称为栈顶，另一端称为栈底。 （2）栈顶的当前位置是动态的，该位置由一个称为栈顶指针的指示器指示。 （3）栈的插入操作称为进栈或入栈,删除操作称为退栈或出栈。 （4）不含元素的栈称为空栈。 （5）栈是一种“后进先出”结构（LIFO），操作不具有随机性。  进栈顺序：a1 a2 a3 a4 a5 出栈顺序：a5 a4 a3 a2 a1
      • 基本操作
        • InitStack(&S)：初始化栈。构造一个空栈S，分配内存空间。 DestroyStack(&S)：销毁栈。销毁并释放栈S所占用的内存空间。 push(&S,x)：进栈，若栈S未满，则将x加入使之成为新栈顶。 Pop(&S,&x)：出栈，若栈s非空，则弹出栈顶元素，并用x返回。 GetTop(S,&x)：读栈顶元素。若栈S非空，则用x返回栈顶元素 其他常用操作： StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false。
      • 公式
        • n个不同元素进栈，出栈元素不同排列的个数为 上述公式称为卡特兰（Catalan）数，可采用数学归纳法证明（不要求掌握）。
    • 顺序栈
      • 利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，并指示出栈顶位置。
      • 顺序栈的实现
        • #define MaxSize 10 // 定义栈中元素的最大个数 typedef struct{ ElemType data[MaxSize]; // 静态数组存放栈中元素 int top; // 栈顶指针 } SqStack;
      • 初始化栈InitStack(&S)
        • // 初始化栈 void InitStack(SqStack &S){ S.top=-1; // 初始化栈顶指针 } 
      • 判断栈是否为空StackEmpty(S)
        • //判断栈空 bool StackEmpty(SqStack S){ if(S.top==-1) // 栈空 return true; else // 不空 return false; } 栈S为空的条件是s.top==s.base int StackEmpty( sqstack s ) { return( s.top = = s.base ); } 要看清题目中top指针指向的是最后一个元素还是指向下一个可以插入的位置
      • 进栈Push(&s,e)
        • // 新元素入栈 bool Push(SqStack &S,ElemType x){ if(S.top==MaxSize-1) // 栈满，报错 return false; S.top = S.top + 1; // 指针先加1 s.data[s.top]=x; // 新元素入栈 return true; }
      • 出栈Pop(&s,&e)
        • // 出栈操作 bool Pop(SqStack &S,ElemType &x){ if(S.top==-1) // 栈空，报错 return false; x=S.data[s.top]; // 栈顶元素先出栈 S.top = S.top - 1; // 指针再减1 return true; }
      • 取栈顶元素GetTop(s)
        • // 读栈顶元素 bool GetTop(SqStack S,ElemType &x){ if(S.top==-1) // 栈空，报错 return false; x=S.data[s.top]; // x记录栈顶元素 return true; }
    • 链栈
      • 采用链式存储的栈称为链栈，是运算受限的单链表，只能在链表头部进行操作。 typedef struct stacknode { SElemType data; // 数据域 struct Stacknode *next; // 指针域 }StackNode，*Linkstack;
      • 特点
        • （1）不存在栈满(上溢)的情况。 （2）栈顶指针就是链表头指针，右图是链栈S。 （3）头插法建立单链表相当于进栈 （4）单链表的删除相当于出栈
    • 共享栈
      •  栈满的条件：top0 + 1 == top1 #define MaxSize 10 // 定义栈中元素的最大个数 typedef struct{ ElemType data [MaxSize]; // 静态数组存放栈中元素 int top0; // 0号栈栈顶指针 int top1; // 1号栈栈顶指针 } ShStack; // 初始化栈 void InitStack(ShStack &S){ S.top0=-1; // 初始化栈顶指针 s.top1=MaxSize; }
  • 队列
    • 队列的基本概念
      • 定义
        • 队列（Queue）是只允许在一端进行插入，在另一端删除的线性表  队列的特点：先进先出
      • 基本操作
        • lnitQueue(&Q)：初始化队列，构造一个空队列Q。 DestroyQueue(&Q)：销毁队列。销毁并释放队列Q所占用的内存空间。 EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾。 DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回。 GetHead(Q,&x)：读队头元素，若队列Q非空，则将队头元素赋值给x。 其他常用操作： QueueEmpty(Q)：判队列空，若队列Q为空返回true，否则返回false。
    • 队列的顺序存储
      • 假设队列的元素个数最大不超过整数MAXSIZE，所有的元素都具有同一数据类型QElemType，则顺序队列类型SqQueue定义如下： #define MaxSize 10 // 定义队列中元素的最大个数 typedef struct{ ElemType data [MaxSize]; // 用静态数组存放队列元素 int front,rear; // 队头指针和队尾指针 } SqQueue;
      • 初始化队列InitQueue(SqQueue &Q)
        • // 初始化队列 void InitQueue(SqQueue &Q){ // 初始时队头、队尾指针指向0 Q.rear=Q.front=0; }
      • 判断队列是否为空QueueEmpty(SqQueue Q)
        • // 判断队列是否为空 bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front) // 队空条件 return true; else return false; } 
      • 入队EnQueue(&Q,x)
        • 入队，若队列Q未满，将x加入，使之成为新的队尾。 //入队 bool EnQueue(SqQueue &Q,ElemType x){ if (队列已满) return false; // 队满则报错 Q.data[Q.rear]=x; // 将x插入队尾 Q.rear=Q.rear+1; // 队尾指针后移 return true; }
    • 循环队列
      • （1）有front==rear成立，该条件可作为队空的条件。 （2）能否用rear==MAXSIZE作为队满的条件呢？ 不能，在图（a）中，队列不满，但却满足该条件。这时入队会出现“上溢出”，这种溢出并不是真正的溢出，队列仍存在可存放元素的空位置，所以这种情况是假溢出。 （3）为充分使用顺序队列中的存储空间，把顺序队列的首尾相连接，形成一个环，即循环队列。
      • 入队EnQueue(&Q,x)
        • 入队，若队列Q未满，将x加入，使之成为新的队尾。 //入队 bool EnQueue(SqQueue &Q,ElemType x){ if (队列已满) return false; // 队满则报错 Q.data[Q.rear]=x; // 将x插入队尾 Q. rear=(Q.rear+1)%max; // 队尾指针后移 return true; }
      • 循环队列基本操作的实现
        • （1）初始化空队：Q.front=Q.rear=O; （2）入队：Q.rear=(Q.rear+1)%MAXSIZE; （3）出队：Q.front=(Q.front+1)%MAXSIZE; （4）队空条件 Q.front==Q.rear // 由于出队Q.front追上了Q.rear （5）队满条件 Q.front==Q.rear // 由于入队Q.rear追上了Q.front 队空、队满判断条件一样，怎么办？ 如何区分循环队列的队空、队满？ （1）在入队时少用一个数据元素空间，以队尾指针加1等于队头指针判断队满，即队满条件为： (Q.rear+1)%MAXSIZE==Q.front 队空条件仍为： Q.rear==Q.front 队列元素个数：(rear+MaxSize-front)%MaxSize （2）增设表示元素个数的数据成员。 队空的条件Q.size==0 队满的条件Q.size==MaxSize （3）增设tag数据成员,以区分队满还是队空。 tag=0时，若因删除导致Q.rear==Q.front，则为队空 tag=1时，若因插入导致Q.rear==Q.front，则为队满
        • 初始化队列InitQueue(&Q)
          • Status InitQueue(SqQueue &Q) { Q.base=(QElemType *)malloc(MAXSIZE*sizeof(QElemtype)); if( !Q.base) exit(OVERFLOW) ; Q.front=Q.rear=0; // 初始时均为0 return OK; }
        • 求队列长度QueueLength(Q)
          • int QueueLength(SqQueue Q) { return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; }
        • 入队列EnQueue(&Q, e)
          • // 判断队列是否为空 bool QueueEmpty(SqQueue Q){ if(Q.rear==Q.front) // 队空条件 return true; else return false; } // 入队 bool EnQueue(SqQueue &Q,ElemType x){ if((Q.rear+1)%MaxSize==Q.front) return false; // 队满则报错 Q.data[Q.rear]=x; // 新元素插入队尾 Q.rear=(Q.rear+1)%MaxSize; // 队尾指针加1取模 return true; }
        • 出队列DeQueue(&Q,&e)
          • int DeQueue(SqQueue &Q，QElemType &e) { if(Q.front==Q.rear) return ERROR; // 队空 e=Q.base[Q.front]; Q.front=(Q.front+1)%MAXSIZE; // 队头位置发生变化 return OK; }
    • 链式队列
      • 链队列——链式存储实现的队列 typedef struct LinkNode{ // 链式队列结点 ElemType data; struct LinkNode *next; }LinkNode; typedef struct{ // 链式队列 LinkNode *front,*rear; // 队列的队头和队尾指针 }LinkQueue; 
      • 初始化队列InitQueue(&Q) // 带头结点
        • // 初始化队列(带头结点) void InitQueue(LinkQueue &Q){ // 初始时front、rear都指向头结点 Q.front=Q.rear=(LinkNode*)malloc(sizeof(LinkNode)); Q.front->next=NULL; }
        • 判断队列是否为空IsEmpty(LinkQueue Q)
          • // 判断队列是否为空 bool IsEmpty(LinkQueue Q){ if(Q.front==Q.rear) return true; else return false; }
      • 初始化队列InitQueue( &Q) // 不带头结点
        • // 初始化队列(不带头结点) void InitQueue(LinkQueue &Q){ // 初始时front、rear都指向NULL Q.front=NULL; Q.rear=NULL; }
        • 判断队列是否为空（不带头结点）IsEmpty(LinkQueue Q)
          • // 判断队列是否为空（不带头结点） bool IsEmpty(LinkQueue Q){ if(Q.front==NULL) return true; else return false; }
      • 入队列EnQueue(&Q, e) // 带头结点
        • // 新元素入队（带头结点） void EnQueue(LinkQueue &Q,ElemType x){ LinkNode *s=(LinkNode *)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; Q.rear->next=s; // 新结点插入到rear之后 Q.rear=s; // 修改表尾指针 } 
      • 入队列EnQueue(&Q, e) // 不带头结点
        • // 新元素入队（不带头结点） void EnQueue(LinkQueue &Q,ElemType x){ LinkNode*s=( LinkNode *)malloc(sizeof(LinkNode)); s->data=x; s->next=NULL; if (Q.front ==NULL){ // 在空队列中插入第一个元素 Q.front = s; // 修改队头队尾指针 Q.rear=s; }else { Q.rear->next=s; // 新结点插入到rear结点之后 Q.rear=s; // 修改rear指针 } } 
      • 出队列DeQueue(&Q, e) // 带头结点
        • bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==Q.rear) return false; // 空队 LinkNode *p=Q.front->next; x=p->data; Q.front->next=p->next; // 修改头结点的 next指针 if(Q.rear==p) // 此次是最后一个结点出队 Q.rear=Q.front; // 修改rear指针 free(p); // 释放结点空间 return true; } 
      • 出队列DeQueue(&Q, e) // 不带头结点
        • // 队头元素出队（不带头结点） bool DeQueue(LinkQueue &Q,ElemType &x){ if(Q.front==NULL) return false; // 空队 LinkNode *p=Q.front; // p指向此次出队的结点 x=p->data; // 用变量x返回队头元素 Q.front=p->next; // 修改front指针 if(Q.rear==p){ // 此次是最后一个结点出队 Q.front = NULL; // front指向NULL Q.rear = NULL; // rear指向 NULL } free(p); // 释放结点空间 return true; }  链式存储――一般不会队满，除非内存不足
    • 双端队列
      • 双端队列
        • 只允许从两端插入、两端删除的线性表 
      • 输入受限的双端队列
        • 只允许从一端插入、两端删除的线性表 
      • 输出受限的双端队列
        • 只允许从两端插入、一端删除的线性表 
  • 栈和队列的应用
    • 括号匹配思想
      • 1）初始设置一个空栈，顺序读入括号。 2）若是右括号，则或者使置于栈顶的最急迫期待得以消解，或者是不合法的情况（括号序列不匹配，退出程序）。 3）若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的在栈中的所有未消解的期待的急迫性降了一级。算法结束时，栈为空，否则括号序列不匹配。
    • 表达式求值的三种方法
      • 设Exp = S1 OP S2 则称OP S1 S2 为前缀表示法 S1 OP S2 为中缀表示法 S1 S2 OP 为后缀表示法
      • 中缀表达式
        • 运算符位于两个操作数中间的表达式称为中缀表达式。例如1+2*3 中缀表达式是最常用的一种表达式的表示方法。对中缀表达式的运算遵循“先乘除，后加减，从左到右计算，先括号内，后括号外”的规则。因此，中缀表达式不仅要依赖运算符优先级，而且还要处理括号。 
        • 用栈实现中缀表达式的计算
          • 初始化两个栈，操作数栈和运算符栈 若扫描到操作数，压入操作数栈 若扫描到运算符或界限符，则按照“中缀转后缀”相同的逻辑压入运算符栈（期间也会弹出运算符，每当弹出一个运算符时，就需要再弹出两个操作数栈的栈顶元素并执行相应运算，运算结果再压回操作数栈）
      • 后缀表达式
        • 运算符在操作数的后面，如1+2*3的后缀表达式为1 2 3 *+。（' '代表空格，将多个数值隔开） 注：在后缀表达式中已考虑了运算符的优先级，没有括号，只有操作数和运算符。
        • 后缀表达式求值过程
          • 从左到右读入后缀表达式，若读入的是一个操作数，则将它入操作数栈，若读入的是一个运算符op，就从操作数栈中连续出栈两元素（两个操作数），设为x1和x2，计算x2 op x1值，并将计算结果入操作数栈；整个后缀表达式读入结束时，栈顶元素就是计算结果。（只需一个栈，用于放操作数）
      • 中缀表达式转换为后缀表达式的方法
        • 初始化一个栈，用于保存暂时还不能确定运算顺序的运算符。从左到右处理各个元素，直到末尾。可能遇到三种情况： ①遇到操作数。直接加入后缀表达式。 ②遇到界限符。遇到“(”直接入栈：遇到“)”则依次弹出栈内运算符并加入后缀表达式，直到弹出“(”为止。注意：“(”不加入后缀表达式。 ③遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符，并加入后缀表达式，若碰到“(”或栈空则停止。之后再把当前运算符入栈。
    • 栈在递归中的应用
      •  函数调用的特点：最后被调用的函数最先执行结束（LIFO） 函数调用时，需要用一个栈存储： ①调用返回地址 ②实参 ③局部变量
      • 适合用“递归”算法解决
        • 可以把原始问题转换为属性相同，但规模较小的问题 （1）计算正整数的阶乘n! （2）求斐波那契数列
    • 队列在层次遍历中的应用
      • 求层次遍历具体过程 过程的简单描述如下： ①根结点入队。 ②若队空（所有结点都已处理完毕），则结束遍历；否则重复③操作。 ③队列中第一个结点出队，并访问之。若其有左孩子，则将左孩子入队；若其有右孩子，则将右孩子入队，返回②。
    • 队列在计算机系统的中的应用
      • Eg：CPU资源的分配 像进程切换、线程切换的本质原因就是为了提高CPU的有效利用率。比如有A,B,C三个任务，但是每个任务中间都有IO请求，这样三个进程（或线程）排成一个队列（当然了实际的处理机调度是很复杂的，但是我们这儿可以简化为A先执行，遇到IO换B，依次循环执行，直到所有任务结束），这个过程中，我们看到需要处理机的任务也是一个队列的概念。还有实时交互系统，就是所有任务也是可以简化看作在一个队列中，比如按照时间片去执行这个队列，在用户端呈现出一种实时的多人操作的感官。 Eg：打印数据缓冲区 主机输出数据的速度远远大于打印机的打印速度，所以需要建立一个打印数据缓冲区，主机将数据缓冲区写满了可以去做其他的事情，而这个数据缓冲区就是一个队列。
• 推广
  • 数组
    • 一维数组
      • ElemType a[10]; // ElemType型一维数组  各数组元素大小相同，且物理上连续存放。 数组元素a[i]的存放地址=LOC +i * sizeof(ElemType) 注：除非题目特别说明，否则数组下标默认从0开始
    • 二维数组
      • ElemType b[2][4]; // 2行4列的二维数组  M行N列的二维数组b[M][N]中，若按行优先存储，则 b[i][j]的存储地址=LOC+ (i*N + j) * sizeof(ElemType)
    • 多维数组
      • 对称矩阵的压缩存储
        • 若n阶方阵中任意一个元素都有= ap则该矩阵为对称矩阵 普通存储：n*n二维数组 压缩存储策略：只存储主对角线+下三角区 （或主对角线+上三角区）  策略：只存储主对角线+下三角区 按行优先原则将各元素存入一维数组中 
      • 三角矩阵的压缩存储
        •  策略：只存储主对角线+上三角区 按行优先原则将各元素存入一维数组中 
      • 三对角矩阵的压缩存储
        • 三对角矩阵，又称带状矩阵：   压缩存储策略： 按行优先（或列优先）原则，只存储带状部分  k=2i+j
      • 稀疏矩阵的压缩存储
        • 稀疏矩阵：非零元素远远少于矩阵元素的个数 压缩存储策略：顺序存储——三元组<行，列，值>  稀疏矩阵的三元组既可以采用数组存储，也可以采用十字链表法存储
• 刷题笔记
  • 三元组存储稀疏矩阵的存储空间
    • 用三元组表示稀疏矩阵，t是非零元素个数，三元组的存储空间是3(t+1)。 因为用三元组表示稀疏矩阵，除了要存储非零元素之外，还要多出一行来存储①非零元素的个数、②稀疏矩阵的行数、③稀疏矩阵的列数。
  • 图的广度优先遍历的辅助数据结构
    • 广度优先使用队列进行辅助，当一个节点被加入队列时，要标记为已遍历，遍历过程中，对于队列第一个元素，遍历其所有能够能一步达到的节点，如果是标记未遍历的，将其加入队列，从第一个元素出发所有能一步直接达到的节点遍历结束后将这个元素出列。
  • 十字链表存储稀疏矩阵
  • 单循环赛制
    • 单循环赛制，是指所有参赛队在竞赛中均能相遇一次，最后按各队在竞赛中的得分多少、胜负场次来排列名次。
  • 需要栈支持的线索树遍历
    • 前序遍历（中左右）、中序遍历（左中右）的最后访问的节点都是左或右叶节点，叶节点是没有子树的，所以两个指针域空出来了，可以存放线索指针用于回溯。但是后序遍历（左右中），最后访问的是子树的根节点，子树根节点的两个指针域都指向子树了，所以不能空出来存放线索信息，只能借助栈存储。
  • 栈在进制转换中的应用
    • 栈的应用中就包含了二进制，十进制，八进制，十六进制之间的转换，利用栈的先进后出的原理进行弹栈，高位先弹出来，依次进行输出就得到相应的八进制了。
  • 栈底在数组中的最佳位置
    • 放0则栈向上生长，放n-1栈向下生长。但是栈大小未知，放n-1处不方便追加容量。
  • 模式匹配算法KMP
  • 快速排序算法
    • 快速排序算法通过多次比较和交换来实现排序，其排序流程如下： （1）首先设定一个分界值，通过该分界值将数组分成左右两部分。 （2）将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。 （3）然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。 （4）重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
  • 飞机登机仿真用的数据结构
    • 老幼病残乘客，头等舱乘客会优先上飞机，优先下飞机，故采用FIFO队列
  • 按层次遍历二叉树的辅助数据结构
    • 在按层次遍历二叉树的算法中，需要借助的辅助数据结构是队列。用到队列先进先出的特性。而二叉树的先序、中序、后序遍历的非递归实现需要借助栈这一数据结构实现。
  • 递归表、再入表、纯表和线性表的关系
    • 递归表、再入表、纯表、线性表之间的关系为。
  • 消除递归是否一定要使用栈
    • 如尾递归可将其转换成递推（用循环语句来实现）而不需要栈。
  • n个元素进栈后出栈算法时间复杂度
    • 设栈采用顺序存储结构，若己有n个元素进栈，则出栈算法的时间复杂度为O(1)，因为n为固定数

第4章 串

• 串的定义和存储
  • 基本概念
    • 串就是一种特殊的线性表 串就是拓展的线性表
    • 串的定义
      • 串（或字符串）：由零个或多个字符组成的有限序列，S='a₁a₂…an' S表示串名 C语言中，将一个串表示成"a₁a₂…an"的形式（不同的地方可能使用不同）。 最外边的引号本身不是串的内容，是串的标志，以便将串与标识符（如变量名等）加以区别。 每个ai(1≤i≤n)代表一个字符，可以是字母、数字或者其他字符（ASCii）。
      • 空串
        • 空串：含零个字符的串，用Φ表示（和空格串不同） S=""
    • 主串
      • 主串：包含子串的串。
      • 字符在主串中的位置
        • 字符在主串中的位置：某个字符在主串中的序号（位序从1开始） S="408150"，那么'1'在主串中的位置是5
    • 子串
      • 子串：一个串中任意个连续字符组成的子序列（含空串）称为该串的子串。 S="408 150"，那么T="150"就是S的子串，S也是T的主串
      • 子串在主串中的位置
        • 子串在主串中的位置：子串在主串中的位置（疑问），和数组类似，我们会用子串的第一个字符的位置来表示子串，在主串中的位置 S="408 150"，T="150"在主串中的位置就是5
    • 串长
      • 串长：串中所含字符的个数（空串长度为0）。 S="408 150"，那么S串长为7
    • 串相等
      • 串相等：当且仅当两个串的长度相等，且各对应位置上的字符也相等时 "408 150"=="408 150" "408 150"≠"150 408"
    • 线性表与串对比
      • 
  • 基本操作
    • 假设s="408 150"，t=""，sub="150"，m="985211"
    • (1)StrAssign(&s,chars)
      • 将一个字符串常量赋给串s，即生成一个其值寺于chars的串s StrAssign(&s,"l love 408"),s="I love 408"
    • (2)StrCopy(&s,t)
      • 串复制，将串s赋给串t StrCopy(&t,s),s="408 150"
    • (3)StrEqual(s,t)
      • 判串相等，若两个串s与t相等则返回真；否则返回假 StrEqual(s,s)=1 StrEqual(s,t)=0
    • (4)StrLength(s)
      • 求串长，返回串s中字符个数 StrLength(s)=7
    • (5)Concat(&t,s1,s2)
      • 串连接，返回由两个串s1和s2连接在一起形成的新串t Concat(&t,sub,m),t="150985211”
    • (6)SubString(&sub,s,pos,len)
      • 返回串s中从第pos(1≤pos≤StrLength(s))个字符起、长度为len的子串 SubString(&t,s,5,3),t=150
    • (7)Index(s,t,pos)
      • 返回子串t在主串s中第pos(1≤pos≤StrLength(s))个字符后第一次出现的位置 Index(s,sub,1)=5Index(s,sub,6)=0
    • (8)StrInsert(&s,pos,t)
      • 将串t插入到串s的第pos(1≤pos≤StrLength(s)+1)个字符前 StrInsert(&s,4,sub)="408150 150"
    • (9)StrDelete(&s,pos,len)
      • 从串s中删去从第pos(1≤pos≤StrLength(s))个字符开始的长度为len的子串 StrDelete(&s,4,4)="408"
    • (10)Replace(&s,t,v)
      • 用v替换主串s中出现的所有与t相等的不重叠的子串 Replace(&s,sub,"149")="408 149"
    • StrCompare(S,T)
      • 比较操作 若S>T，返回值大于0 若S==T，返回值就是0 若S<T，返回值小于0 比较原则：1从第一个字符开始往后依次对比，先出现更大字符的串就更大 2短串如果是长串的前缀，那么长串就更大 3只有完全相等的时候才相等
    • 补充
      • C/C++传参方式
        • SubString(String sub,s,pos,len)传值：形参改变，不会影响到实参 SubString(String *sub,s,pos,len)传地址：形参改变，会影响实参 SubString(String &sub,s,pos,len)传引用：形参改变，会影响实参
  • 存储结构
    • 什么是串的顺序存储 串是一种特殊的线性表，它的每个结点仅由一个字符组成，因此，存储串的方法和存储线性表方法类似。 最常采用顺序存储，即把串中字符依次存储在一片相邻的内存空间中，这称为顺序串。
    • 定长分配存储
      • typedef struct { char ch[MaxLen]; int length; }SString 【补充】存储方案： typedef struct { char ch[MaxLen]; int length; }SString  优点：字符的位序和数组的下标相同 length的范围更大
      • 定长顺序串基本操作
        • (1) void StrAssign ( SString &s, char t[ ])//将一个字符串常量t赋给串s { for (i=0, j=1; t[i]!='\0'; i++,j++) s[j]=t[i]; s .length=j; //length存放长度 } (2) StrCopy(s, t) //将串t复制给串s void StrCopy (SString &s,SString t) { for (i=1; i<=t.length; i++) s[i]=t[i]; s.length=t.length; //length存放长度 }
        • (1)StrAssign(&s,chars)
          • void StrAssign ( SString &s, char t[ ])//将一个字符串常量t赋给串s { for (i=0, j=1; t[i]!='\0'; i++,j++) s[j]=t[i]; s .length=j; //length存放长度 }
        • (2)StrCopy(&s,t)
          • //将串t复制给串s void StrCopy (SString &s,SString t) { for (i=1; i<=t.length; i++) s[i]=t[i]; s.length=t.length; //length存放长度 }
        • (3)StrEqual(s,t)
          • //判断两个串是否相等：若两个串s与t相等返回1；否则返回0。 int StrEqual (SString s, SString t) { same=1; if (s.length!=t.length) same=0;//长度不相等时，返回0 else for (i=1; i<=s.length; i++) if (s[i]!=t[i]) //有一个对应字符不相同时，返回0 { same=0; break; } return same; }
        • (4)SubStr(&sub,s,pos,len)
          • //返回串s中从第pos(1≤pos<s[0])个字符起长度为len的子串。 SString SubStr(SString &sub, SString s, int pos, int len) { for(i = pos,j=1; i<pos+len; i++,j++) subStr.ch[j++]= S.ch[i]; sub.length=len; }
        • (5)Index(s,t,pos)
          • //返回子串t在主串s中第pos(1≤pos≤s[0])个字符后第一次出现的位置。 { if (pos>0){ //pos的合法性 i=pos; while(i<= s.length-t.length+1) { SubStr( sub, s, i, t.length ); if(StrEqual(sub,t)==0)i++; else return i; }//while }//if return 0; //s中不含t }
        • (6)StrCompare(S,T)
          • int StrCompare (Hstring S, Hstring T){ for(i= 0; i<S.length&&i<T.length; i++){ if (S.ch[i]!=T.ch[i]) return S.ch[i]-T.ch[i]; } return S.length-T.length; } 
    • 变长顺序存储（堆分配存储）
      • typedef struct { char *ch; int length; }HString; ch=(char *)malloc (MaxLen*sizeof(char))
    • 块链存储
      • typedef struct StringNode{ char ch;//每个结点1B struct StringNode *next;//指针大小和计算机寻址范围相关，比如32位地址空间需要4B }StringNode,*String;  typedef struct StringNode{ char ch[N];//每个结点存储N个字符 struct StringNode *next;//指针大小和计算机寻址范围相关，比如32位地址空间需要4B }StringNode,*String;  typedef struct { StringNode*head, *tail; int length;//串长 }LString;
    • 三种存储方式的对比
      • 定长顺序存储： 串长超出最大长度时，需截掉尾部 串长过小，则串空间浪费较大 堆分配： 基于动态存储管理，处理方便 链式存储： 联接操作等处理有一定的方便 总体来说，占用存储容量大且操作复杂，没有上述两种结构灵活
• 串的模式匹配
  • 模式匹配概念
    • 主串
    • 子串
    • 模式串
      • 想要在主串中找到的某个子串
    • 串的模式匹配
      • 设有主串s和子串t，子串t的定位就是要在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串，把子串t称为模式串，模式串在子串中的定位称作模式匹配 模式匹配成功是指：在目标串s中找到一个模式串t 不成功则指：目标串s中不存在模式串t
  • 简单模式匹配（暴力匹配法）
    • 基本思路是：从目标串s='s₁s₂.…sn'的第1个字符开始和模式串t='t₁t₂…tm'中的第1个字符比较： 若相等，则继续逐个比较后续字符； 否则，从目标串下一个字符开始重新与模式串t的第1个字符进行比较 
    • 模式匹配算法
      • //简单模式匹配 int Index(SString S,SString T){ int k=1; int i=k,j=1; while(i<=S.length && j<=T.length){ if(S.ch[i]==T.ch[j]){ ++i; ++j;//继续比较后继字符 }else{ k++;//检查下一个子串 i=k; j=1; } } if(j>T.length) return k; else return 0; } int Index(SString S,SString T){ int i=k,j=1; while(i<=S.length && j<=T.length){ if(S.ch[i]==T.ch[j]){ ++i; ++j;//继续比较后继字符 }else{ i=i-j+2; j=1;//指针后退重新开始匹配 } } if(j>T.length) return k; else return 0; }
    • 性能分析
      • 假设主串s长度为n，模式串长度为m，进行简单模式匹配 最好情况：匹配成功，时间复杂度为O(m)  最好情况：匹配失败，时间复杂度为O(n-m+1)  最坏情况：匹配成功，比较(n-m+1)*m次，时间复杂度为O(mn)  最坏情况：匹配失败，比较(n-m+1)*m次，时间复杂度为O(mn) 
  • KMP算法
    • 假设S为'abaabaabaabaabc'，模式串t为'abaabc' 简单模式匹配，每次失配后都是一格一格往后移动，所以指针i经常回溯 能不能让主串i不回溯，只让j回溯？ KMP算法思路： 该算法较回溯法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有了某种程度的提高。在每趟匹配过程中，当发生字符比较不相等时，不回溯i指针，而是利用已经得到的部分匹配结果将模式串向右滑动尽可能远的一段距离后，继续进行比较。
    • 部分匹配值表格
      • 
    • next数组
      • next数组求法： 首先要弄清楚几个概念：前缀、后缀和部分匹配值。 前缀：指除最后一个字符以外，字符串的所有头部子串； 后缀：指除第一个字符外，字符串的所有尾部子串； 公共前后缀：前缀和后缀相等的部分； 最大公共前后缀：前缀和后缀的最长相等前后缀长度； 部分匹配值：最大公共前后缀长度； next数组值：当前位置之前子串的部分匹配值+1，next[1]默认为0 
    • 匹配过程
      • //求模式串T的next数组 void get_next(SString T,int next[]){ int i=1,j=0; next[1]=0; while(i<T.length){ if(j==0| |T.ch[i]==T.ch[j]){ ++i;++j;//若pi=pj，则 next[j+1]=next[j]+1 next[i]=j; } else//否则令j=next[j]，循环继续 j=next[j]; } } //KMP算法 int Index_KMP(SString S,SString T,int next[]){ int i=1,j=1; while(i<=S.length&&j<=T.length){ if(j==0| |S.ch[i]==T.ch[j]){ ++i; ++j;//继续比较后继字符 } else j=next [j];//模式串向右移动 if(j>T.length)//匹配成功 return i-T.length; else return 0; }
  • 改进的KMP
    • nextval数组
      • nextval数组求法： 判断当前i位置元素与next[i]比较： 若相同，则nextval[i]=nextval[next[i]];//相当于nextval数组保存实际需要比较开始的位置 若不同，则nextval[i]=next[i].  //nextval数组的求法：先算出next数组先令nextval[1]=0 void get_nextval(SString T,int next[]){ for(int j=2;j<=T.length;j++){ if(T.ch[next[j]]==T.ch[j]]) nextval[j]=nextval[next[j]];//跳到实际要开始比较的地方 else nextval[j]=next[j]; } }
    • 匹配过程

第5章 树和二叉树

• 树的基本概念
  • 树型结构是一类非常重要的非线性结构。树型结构特征： 分支关系 一对多 层次结构
  • 树的基本概念
    • 树的定义
      • 树（Tree）是n（n≥0）个结点的有限集合T，若n=0时称为空树，否则： （1）有且只有一个特殊的称为树的根（Root）结点； （2）若n>1时，其余的结点被分为m（m>0）个互不相交的子集T₁,T₂,T₃…Tm，其中每个子集本身又是一棵树，称其为根的子树。  这是树的递归定义，即用树来定义树，而只有一个结点的树必定仅由根组成，如图所示。 
    • 树的基本术语
      • 
      • 结点（node）
        • 一个数据元素及其若干指向其子树的分支。
      • 结点的度（degree）、树的度
        • 结点所拥有的子树的棵数称为结点的度。树中结点度的最大值称为树的度。 图（b）中结点A的度是3，结点B的度是2，结点M的度是0，树的度是3。
      • 叶子（leaf）节点、非叶子节点
        • 树中度为0的结点称为叶子结点（或终端结点）。相对应地，度不为0的结点称为非叶子结点（或非终端结点或分支结点）。除根结点外，分支结点又称为内部结点。如图b中结点H、l、J、K、L、M、N是叶子结点，而所有其它结点都是分支结点。
      • 孩子结点、双亲结点、兄弟结点
        • 一个结点的子树的根称为该结点的孩子结点（child）或子结点；相应地，该结点是其孩子结点的双亲结点（parent）或父结点。 如图b中结点B、C、D是结点A的子结点，而结点A是结点B、C、D的父结点； 结点E、F是结点B的子结点，结点B是结点E、F的父结点。 同一双亲结点的所有子结点互称为兄弟结点。如图b中结点B、C、D是兄弟结点； 结点E、F是兄弟结点。
      • 结点层次
        • 从根开始定义起，根为第一层，根的孩子为第二层，以此类推  若某结点在第l（l≥1）层，则其子结点在第l+1层。
      • 堂兄弟结点
        • 双亲结点在同一层上的所有结点（不互为兄弟）互称为堂兄弟结点。如图b中结点E、F、G、H、l、J。
      • 结点的层次路径、祖先、子孙
        • 从根结点开始，到达某结点p所经过的所有结点成为结点p的层次路径（有且只有一条）。 结点p的层次路径上的所有结点（p除外）称为p的祖先（ancester）。以某一结点为根的子树中的任意结点称为该结点的子孙结点（descent）。
      • 树的深度（depth）
        • 树中结点的最大层次值，又称为树的高度，如图b中树的高度为4。
      • 有序树和无序树
        • 对于一棵树，若其中每一个结点的子树（若有）具有一定的次序，则该树称为有序树，否则称为无序树。 
      • 森林（forest）
        • 是m（m≥0）棵互不相交的树的集合。显然，若将一棵树的根结点删除，剩余的子树就构成了森林。 
  • 树的性质
    • 性质1
      • 树中的结点个数等于所有结点的度之和加1。 
    • 性质2
      •  
    • 性质3
      • 
    • 性质4
      • 
    • 性质5
      •   若：给定高度为h，则当每层结点数最多时，则总的结点数最多；反之最少。 若总的结点数为n，则当每层节点最多时，其高度最小，反之最高。
  • 树的存储结构
    • 双亲表示法（顺序结构存储）
      • 用一组连续的存储空间来存储树的结点，同时在每个结点中附加一个指示器（整数域），用以指示双亲结点的位置（下标值）。数组元素及数组的类型定义如下： #define MAX_SIZE 100 typedef struct PTNode { int data; int parent; }PTNode; typedef struct { PTNode Nodes[MAX_SIZE]; int root; /*根结点位置*/ int num; /*结点数*/ }Ptree; 图所示是一棵树及其双亲表示的存储结构。这种存储结构利用了任一结点的父结点唯一的性质。可以方便地直接找到任一结点的父结点，但求结点的子结点时需要扫描整个数组。 
    • 孩子链表表示法
      • 树中每个结点有多个指针域，每个指针指向其一棵子树的根结点。有两种结点结构。
      • 定长结点结构
        • 指针域的数目就是树的度。 其特点是：链表结构简单，但指针域的浪费明显。结点结构如图所示。在一棵有n个结点，度为k的树中必有n(k-1)+1空指针域。 
      • 不定长结点结构
        • 树中每个结点的指针域数量不同，是该结点的度，如图所示。没有多余的指针域，但操作不便。 
    • 孩子兄弟表示法
      • 以二叉链表作为树的存储结构，其结点形式如图所示。两个指针域：分别指向结点的第一个子结点和下一个兄弟结点。结点类型定义如下： typedef struct Csnode { ElemType data ; struct CSnode *firstchild,*nextsibing; } CSNode; 
• 二叉树的概念和性质
  • 二叉树的定义
    • 二叉树（Binary tree）是n（n≥0）个结点的有限集合。若n=0时称为空树，否则： （1）有且只有一个特殊的称为树的根(Root)结点； （2）若n>1时，其余的结点被分成为二个互不相交的子集T₁，T₂，分别称之为左、右子树，并且左、右子树又都是二叉树。 
  • 二叉树的基本形态
    • 二叉树有5种基本形态，如图所示。 
  • 二叉树的性质
    • 性质1
      •  证明：用数学归纳法证明。 
    • 性质2
      •  证明：深度为k的二叉树的最大的结点数为二叉树中每层上的最大结点数之和。 
    • 性质3
      • 
    • 性质4
      • 结点个数等于所有结点的度之和加1。
  • 满二叉树
    •  如图是一棵深度为4的满二叉树。  基本特点是每一层上的结点数总是最大结点数。 满二叉树的所有的支结点都有左、右子树。 可对满二叉树的结点进行连续编号，若规定从根结点开始，从1开始，按“自上而下、自左至右”的原则进行。
  • 完全二叉树
    • 完全二叉树（Complete Binary Tree）：如果深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应（不跳号），该二叉树称为完全二叉树。 
    • 性质1
      • 
    • 性质2
      • 
    • 性质3
      • 
    • 性质4
      • 
    • 性质5
      • 深度为k的满二叉树中编号从1到n的前n个结点构成了一棵深度为k的完全二叉树。 其中 完全二叉树是满二叉树的一部分，而满二叉树是完全二叉树的特例。
    • 性质6
      • 若完全二叉树的深度为k，则所有的叶子结点都出现在第k层或k-1层。
    • 性质7
      • 对于任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为l或l+1。
    • 性质8
      • 
    • 性质9
      • 
    • 性质10
      • 对于一个棵完全二叉树，度为1的节点个数是1或0。
  • 二叉树的其他类型
    • BST
    • AVL
    • 折半树
    • 第7章：查找
    • 堆
      • 第8章：排序
• 二叉树的存储
  • 顺序存储结构
    • 二叉树存储结构的类型定义： #define MAX_SIZE 100 typedef int sqbitree[MAX_SIZE]; 用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i的分量中，如图所示。  对于一般的二叉树，将其每个结点与完全二叉树上的结点相对照，存储在一维数组中。  最坏的情况下，一个深度为k且只有k个结点的单支树需要长度为2^k-1的一维数组。 只有完全二叉树才采用顺序结构
  • 链式存储结构
    • 设计不同的结点结构可构成不同的链式存储结构。
    • 二叉链表结点
      • 结点的类型及其定义
        • 有三个域：一个数据域，两个分别指向左右子结点的指针域，如图所示。 typedef struct BTNode { int data; struct BTNode *Lchild,*Rchild ; }BTNode ; 
      • 二叉树的链式存储形式
        • 例有一棵一般的二叉树，如图所示。二叉链表方式存储的结构图如图所示。 
    • 三叉链表结点
      • 结点的类型及其定义
        • 除二叉链表的三个域外，再增加一个指针域，用来指向结点的父结点，如图所示。 typedef struct BTNode_3 { ElemType data; struct BTNode_3 *Lchild,*Rchild,*parent; } BTNode_3; 
      • 二叉树的链式存储形式
        • 例有一棵一般的二叉树，如图所示。三叉链表方式存储的结构图如图所示。 
• 二叉树的遍历
  • 遍历二叉树的概念
    • 遍历二叉树（Traversing Binary Tree）：是指按指定的规律对二叉树中的每个结点访问一次且仅访问一次。 所谓访问是指对结点做某种处理。如：输出信息、修改结点的值等。二叉树是一种非线性结构，每个结点都可能有左、右两棵子树，因此，需要寻找一种规律，使二叉树上的结点能排列在一个线性序列上，从而实现遍历。  二叉树的基本组成∶根结点、左子树、右子树。若能依次遍历这三部分，就是遍历了二叉树。 若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。 规定先左后右，则只有前三种情况三种情况，分别是： DLR——先（根）序遍历。 LDR——中（根）序遍历。 LRD——后（根）序遍历。
  • 先序遍历
    • 前序遍历就是从二叉树的根结点出发，当第一次到达结点时就输出结点数据，按照先向左在向右的方向访问。  typedef struct BTNode { int data; struct BTNode *Lchild,*Rchild; }BTNode; //递归先序遍历 void PreorderTraversal(BTNode * root) { if (root != null) { printf(root->data); PreorderTraversal(root->left); PreorderTraversal(root->right); } }
  • 中序遍历
    • 中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左在向右的方向访问。  typedef struct BTNode { int data; struct BTNode *Lchild, *Rchild; }BTNode; //递归中序遍历 void inOrderTraversal(BTNode * root){ if (root != null) { inOrderTraversal(root->left); printf(root->data); inOrderTraversal(root->right); } }
  • 后序遍历
    • 后序遍历就是从二叉树的根结点出发，当第三次到达结点时就输出结点数据，按照先向左再向右的方向访问。  typedef struct BTNode { int data; struct BTNode *Lchild, *Rchild; }BTNode; //递归后序遍历 void postOrderTraversal(BTNode *root) { if (root != null) { postOrderTraversal(root->left); postOrderTraversal(root->right); printf(root->data); } }
  • 层次遍历
    • 层次遍历二叉树，是从根结点开始遍历，按层次次序“自上而下，从左至右”访问树中的各结点。  #define MAX_NODE 50 void levelorder(BTNode*T){ BTNode *Queue[MAX_NODE],*p=T; int front=0, rear=0; if(p!-NULL){ Queue[rear++]=p; while(front < rear){ p=Queue[front++]; printf(p->data); if(p->Lchild!=NULL) Queue[rear++]=p->Lchild; if(p->Rchild!=NULL) Queue[rear++]=p->Rchild; } } }
  • 遍历小结
    • 1）先序遍历，中序遍历，后续遍历使用栈【系统栈或者用户栈】 2）层次遍历使用队列 3）遍历过程中，叶子结点的相对顺序是不变的 4）中序遍历＋层次遍历 中序遍历＋后序遍历 中序遍历＋先序遍历 5）根左右 左右根 左根右
  • 二叉树构造
    • 中序遍历＋层次遍历 中序遍历＋后序遍历 唯一确定一棵二叉树 中序遍历＋先序遍历
• 线索二叉树
  • 线索二叉树的引入
    • 回顾二叉树中序遍历 中序遍历就是从二叉树的根结点出发，当第二次到达结点时就输出结点数据，按照先向左再向右的方向访问。 遍历本质上来讲是：把非线性结构线性化的操作  设一棵二叉树有n个结点，则有n-1条边（指针连线），而n个结点共有2n个指针域(（Lchild和Rchild），显然有n+1个空闲指针域未用。则可以利用这些空闲的指针域来存放结点的直接前驱和直接后继信息。 
  • 线索二叉树的定义
    • 对结点的指针域做如下规定： 若结点有左孩子，则Lchild指向其左孩子，否则，指向其直接前驱； 若结点有右孩子，则Rchild指向其右孩子，否则，指向其直接后继； 为避免混淆，对结点结构加以改进，增加两个标志域，如图所示。  线索二叉树的结点结构  
  • 线索二叉树的构造
    • 线索化二叉树：二叉树的线索化指的是依照某种遍历次序使二叉树成为线索二叉树的过程。 线索化的过程就是在遍历过程中修改空指针使其指向直接前驱或直接后继的过程。   
  • 后序遍历找后继？？？
    • 对于后序遍历的线索树中找结点的直接后继依然困难，可分以下三种情况： 若结点是二叉树的根结点：其直接后继为空； 若结点是其父结点的左孩子或右孩子且其父结点没有右子树：直接后继为其父结点； 若结点是其父结点的左孩子且其父结点有右子树：直接后继是对其父结点的右子树按后序遍历的第一个结点。
• 树和二叉树的转换
  • 树转化为二叉树
    • 详细步骤
      • 对于一般的树，可以方便地转换成一棵唯一的二叉树与之对应。将树转换成二叉树在“孩子兄弟表示法”中已给出，其详细步骤是： （1）加虚线。在树的每层按从“左至右”的顺序在兄弟结点之间加虚线相连。 （2）去连线。除最左的第一个子结点外，父结点与所有其它子结点的连线都去掉。 （3）旋转。将树顺时针旋转45°，原有的实线左斜。 （4）整型。将旋转后树中的所有虚线改为实线，并向右斜。 
    • 转换后二叉树的特点
      • 这样转换后的二叉树的特点是： 二叉树的根结点没有右子树，只有左子树； 左子结点仍然是原来树中相应结点的左子结点，而所有沿右链往下的右子结点均是原来树中该结点的兄弟结点。
    • 树与二叉树的对应关系
      • 由于二叉树和树都可用二叉链表作为存储结构，对比各自的结点结构可以看出，以二叉链表作为媒介可以导出树和二叉树之间的一个对应关系。 从物理结构来看，树和二叉树的二叉链表是相同的，只是对指针的逻辑解释不同而已。 从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树一定为空。 
  • 二叉树转换成树
    • 
  • 森林转换成二叉树
    • ①将F={T1,T2,…,Tn}中的每棵树转换成二叉树。 ②按给出的森林中树的次序，从最后一棵二叉树开始，每棵二叉树作为前一棵二叉树的根结点的右子树，依次类推，则第一棵树的根结点就是转换后生成的二叉树的根结点，如图所示。 
  • 二叉树转换成森林
    • 上述转换规则是递归的，可以写出其递归算法。以下给出具体的还原步骤。 ①去连线。将二叉树B的根结点与其右子结点以及沿右子结点链方向的所有右子结点的连线全部去掉，得到若干棵孤立的二叉树，每一棵就是原来森林F中的树依次对应的二叉树，如图（b）所示。 ②二叉树的还原。将各棵孤立的二叉树按二叉树还原为树的方法还原成一般的树，如图（c）所示。 
  • 树的遍历
    • 由树结构的定义可知，树的遍历有二种方法。 （1）先序遍历：先访问根结点，然后依次先序遍历完每棵子树。如图的树，先序遍历的次序是：ABCDEFGIJHK （2）后序遍历：先依次后序遍历完每棵子树，然后访问根结点。如图的树，后序遍历的次序是：CDBFIJGHEKA  树的先序遍历实质上与将树转换成二叉树后对二叉树的先序遍历相同。树的后序遍历实质上与将树转换成二叉树后对二叉树的中序遍历相同。
• 哈夫曼树
  • 最优二叉树（Huffman树）
    • 
    • 节点路径
      • 从树中一个结点到另一个结点的之间的分支构成这两个结点之间的路径。
    • 路径长度
      • 路径长度：结点路径上的分支数目称为路径长度。
    • 权（值）
      • 各种开销、代价、频度等的抽象称呼。
    • 结点的带权路径长度
      • 从该结点的到树的根结点之间的路径长度与结点的权（值）的乘积。
    • 树的路径长度
      • 从树根到每一个结点的路径长度之和。
    • 树的带权路径长度
      • 树中所有叶子结点的带权路径长度之和，记做：  其中：n为叶子结点的个数；wi为第i个结点的权值；li为第i个结点的路径长度。
    • Huffman树
      • 具有n个叶子结点（每个结点的权值为wi）的二叉树不止一棵，但在所有的这些二叉树中，必定存在一棵WPL值最小的树，称这棵树为Huffman树（或称最优树）。 如图是权值分别为2、3、6、7，具有4个叶子结点的二叉树，它们的带权路径长度分别为： （a）WPL=2x2+3x2+6×2+7×2=36； （b）WPL=2x1+3x2+6x3+7×3=47； （c）WPL=7x1+6×2+2x3+3x3=34。 其中（c）的WPL值最小，可以证明是Huffman树。 
  • Huffman树的构造
    • ①根据n个权值{w₁,w₂,…,wn}，构造成n棵二叉树的集合F={T₁,T₂,…,Tn}，其中每棵二叉树只有一个权值为wi的根结点，没有左、右子树； ②在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和； ③在F中删除这两棵树，同时将新得到的树加入F中； ④重复②、③，直到F只含一颗树为止。 图是权值集合W={8,3,4,6,5,5}构造Huffman树的过程。所构造的Huffman树的WPL是：WPL=6×2+3x3+4x3+8×2+5x3+5x3=79   构造Huffman树时，为了规范，规定F={T₁,T₂,…,Tn}中权值小的二叉树作为新构造的二叉树的左子树，权值大的二叉树作为新构造的二叉树的右子树；在取值相等时，深度小的二叉树作为新构造的二叉树的左子树，深度大的二叉树作为新构造的二叉树的右子树。
  • Huffman编码方法
    • 由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的Huffman编码不可能是另一个字符的Huffman编码的前缀。 以字符集C作为叶子结点，次数或频度集W作为结点的权值来构造Huffman树。规定Huffman树中左分支代表“0”，右分支代表“1”。 从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该叶子结点所对应的编码，称之为Huffman编码。 若字符集C={a,b,c,d,e,f}所对应的权值集合为W={8,3,4,6,5,5}，如图所示，则字符a,b, c,d,e,f所对应的Huffman编码分别是：10,010,011,00,110,111。 
  • 赫夫曼树小结
    • 哈夫曼树只有0度结点和2度结点 哈夫曼树的WPL值最小 哈夫曼树不唯一，因为哈夫曼树的左右子树可以交换，但是WPL值唯一 哈夫曼树本质上不属于二叉树，但是考试中我们认为哈夫曼树是二叉树 哈夫曼树的上层结点权值不小于下层结点的权值 哈夫曼编码只讨论叶子的编码
• 并查集
  • 定义
    • 并查集（Union-find Sets）是一种非常精巧而实用的数据结构，他主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的Kruskal算法和求最近公共祖先（Least Common Ancestors，LCA）等。 使用并查集时，首先会存在一组不相交的动态集合S={S1,S2,...,Sk}一般都会使用一个整数表示集合中的一个元素。 每个集合可能包含一个或多个元素，并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的，具体选择哪个元素作为代表一般也是不关心的。我们关心的是，对于给定的元素，可以很快的找到这个元素所在的集合（的代表），以及合并两个元素所在的集合，而且这些操作的时间复杂度都是常数级的。
  • 操作
    • 并查集的基本操作有三个。
    • 并查集的实现原理
      • 并查集的实现原理也比较简单，就是使用树来表示集合，树的每个节点就表示集合中的一个元素，树根对应的元素就是该集合的代表，如下图所示，  图中有两棵树，分别对应两个集合，其中第一个集合为{a,b,c,d},代表元素是a；第二个集合为{e,f,g}，代表元素是e。 树的节点表示集合中的元素，指针表示指向父节点的指针，根节点的指针指向自己，表示其没有父节点。沿着每个节点的父节点不断向上查找，最终就可以找到该树的根节点，即该集合的代表元素。
    • 1）makeSet(s)
      • 建立一个新的并查集，其中包含s个单元素集合。 假设使用一个足够长的数组来存储树节点，那么makeSet要做的就是构造出如下图的森林，其中每个元素都是一个单元素集合，即父节点是其自身。 
    • 2）unionSet(x,y)
      • 把元素x和元素y所在的集合合并，要求x和y所在的集合不相交，如果相交则不合并。 并查集的合并也非常简单，就是将一个集合的树根指向另一个集合的树根，如图所示。  这里应用一个简单的启发式策略——按秩合并。该方法使用秩来表示树高度的上界，在合并时，总是将具有较小秩的树根指向具有较大秩的树根。简单的说，就是总是将比较矮的树作为子树，添加到较高的树中。 除了按秩合并，并查集还有一种常见的策略，就是按集合中包含的元素个数（或者说树中的节点树）合并，将包含节点较少的树根，指向包含节点较多的树根。
    • 3）find(x)
      • 找到元素x所在的集合的代表，该操作也可以用于判断两个元素是否位于同一个集合，只要将他们各自的代表比较一下就可以了。 如果每次都沿着父节点向上查找，那时间复杂度就是树的高度，完全不可能达到常数级。这里需要应用一种非常简单而有效的策略——路径压缩。路径压缩，就是在每次查找时，令查找路径上的每个节点都直接指向根节点，如下图： 
• 刷题笔记
  • 不属于树的存储形式
    • 顺序存储表示法。
  • 二叉树和度为2的树的区别
    • 度为2的树是指树的最大结点的度为2，二叉树可以为空树。
  • 并查集查找元素复杂度
    • 并查集是一种树形的数据结构，用于处理不交集的合并（union）及查询（find）问题，查找一个元素所属集合的算法的时间复杂度与树的高度有关。
  • 线索二叉树属于什么结构
    • 线索二叉树是由二叉链存储结构变化而来的，所以属存储结构或物理结构。
  • 交换所有分支结点左右子树的最合适遍历方式
    • 先交换其所有分支节点左、右子树的位置，再交换根节点的左、右子树。所以应为后序遍历。
  • 用孩子链表示树的优点
    • 在树的孩子链存储结构中，每个节点有指向所有孩子节点的指针，所以很容易计算其孩子节点个数（度数）。
  • 二叉排序树
    • 二叉排序树：—棵空树，或者是具有下列性质的二叉树 （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值 （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值 （3）左、右子树也分别为二叉排序树 （4）没有键值相等的结点。
  • 平衡二叉树上的平衡因子
    • 平衡二叉树上所有结点的平衡因子只可能是-1，0或1。
  • B-树的关键字数目
    • 根据定义，m阶B树每个结点至多含有m-1个关键字。除根结点外，m阶B树中的每个非叶结点至少有┌m/2┐-1个关键字，根结点至少有一个关键字，所以总共包含的关键字最少个数=(n-1)(┌m/2┐-1)+1。
  • 堆的性质
    • 堆是—种特殊的完全二叉树，如：堆总是满足下列性质：堆中某个节点的值总是不大于或不小于其父节点的值；堆总是一棵完全二叉树。最终得到的正是一个从任一结点出发到根的路径上所经过的结点序列按其关键字有序的树状结构。
  • 平衡二叉树AVL的本质
    • 平衡二叉树是由前苏联的两位数学家G.M.Adelse-Velskil和E.M.Landis提出，因此一般也称作AVL树，AVL树本质还是一棵二叉查找树，只是在其基础上增加了“平衡 ”的要求。所谓平衡是指，对AVL树的任意结点来说，其左子树与右子树的高度之差的绝对值不超过1，其中左子树与右子树的高度因子之差称为平衡因子。故平衡二叉树是二叉查找树。所以中序遍历“左根右”之后得到的是一个非递减的有序序列。
  • 树的多重链表表示法
    • 对于树的多重链表表示法：trie树，是用树的多重链表来表示树的。每个节点有d个指针域。若从键树中的某个节点到叶子节点的路径上每个节点都只有一个孩子，则可以把路径上的所有节点压缩成一个叶子节点，且在叶子节点中存储关键字以及根关键字相关的信息。当节点的度比较大时，选择Trie树，要比双链表树更为合适。
  • 最小二叉平衡树节点公式
    • 最小二叉平衡树的节点的公式如下：F(n)=F(n-1)+F(n-2)+1或者说深度为n的平衡二叉树，至少有F(n)个结点。 Fibonacci（斐波那契）数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。注意：F(0)=0，F(1)=1。
  • 平衡树叶子节点插入删除的后果
    • 平衡二叉树叶子节点的插入、删除操作可能会引起树的旋转（为了保持树的平衡性），所以T1与T3可能不相同。
  • 平衡二叉树最大元素特征
    • 树中最大元素一定无左子树（可能有右子树）。
  • 哈夫曼树的三叉树推广
    • 将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为0的虚叶结点，对于严格的三叉树(n0-1)%(3-1)=u=1≠0，需要添加m-u-1=3-1-1个叶结点，说明7个叶结点刚好可以构成一个严格的三叉树。
  • 引入线索二叉树的目的
    • 以二叉链表作为存储结构时，只能得到节点的左右孩子信息，结点的任意序列中的前驱和后继信息只能在遍历的动态过程中才能得到，为了查找结点的前驱或后继，引入线索二叉树。
  • Kruskal算法与Prim算法的时间复杂度
    • kruskal复杂度O(mlog(m))适合稀疏图，prim复杂度O(n²)适合稠密图。
  • 路径长度最短的二叉树
    • 树的路径长度是从树根到树中每—结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
  • 用堆分类方法建立堆的过程
    • 建立堆的过程就是对完全二叉树从下往上反复筛选的过程。因为完全二叉树的最后一个非叶结点的编号为(n/2-1)，所以筛选只需从编号(n/2-1)的结点开始。按照筛选法将完全二叉树调整成满足堆的定义，则得出来的就是初始堆。
  • 红黑树
  • B-树的性质
    • （1）树中每个结点至多有m个子树 （2）若根结点不是叶子结点，则至少有两个子树 （3）除根结点以外所有非叶子结点至少有[m/2]（上限符号）个子树 （4）所有非终端结点包含以下信息： n,A0,K1,A1,K2,A2......Kn,An。其中，Ki是关键字，Ai是指向子树根结点的指针 （5）所有叶子结点都出现在同一层次上，且不带信息 （6）各结点内关键字均升序或降序排列
  • 堆的定义
  • 败者树k路平衡归并效率与k是否有关
    • 对于K路平衡归并中，若不使用败者树，则对每个数据需要比较K-1次，总共n个数据，每一趟归并共需要(n-1)(K-1)次比较。若有m个归并初始段，归并趟数为logk(m)，总共比较次数为log-k(m)(n-1)(k-1)。引入败者树后每个数据的比较次数为log2(k)（二叉树只要需要跟父节点比较），总共的比较次数为logk(m)(n-1)(log2k)，简化后为log2(m)(n-1)。可以见引入败者树后比较次数与K无关，减少了归并和比较的次数，提高归并算法的效率。
  • 平衡二叉树的调整
  • 二叉树是否属于树
    • 树和二叉树是两种不同的树形结构，二叉树不是树。
  • 树的数组表示法
    • 树的数组表示法是指除根结点外，每个结点只有一个指向其父结点的链域。每个结点只有其双亲在数组中的位置，而与它的兄弟结点无关，要判断用这种方法存储树时兄弟结点编号是否连续，就要看存储数据时的元素访问顺序，如果按层序序列进行存放，兄弟结点编号就是连续的，如果按前序，后序遍历序列进行存放，兄弟结点编号就有可能不连续。
  • 向B-树插入元素引起根结点分裂时新树的高度
    • 对高度为h的m阶B树，新结点一般是插在第h层。通过检索可以确定关键码应插入的结点位置。然后分两种情况讨论： 1.若该结点中关键码个数小于m-1，则直接插入即可。 2.若该结点中关键码个数等于m-1，则将引起结点的分裂。以中间关键码为界将结点一分为二，产生一个新结点，并把中间关键码插入到父结点（h-1层）中 3.重复上述工作，最坏情况一直分裂到根结点，建立一个新的根结点，整个B树增加一层。
  • B树、B-树、B+树支持的检索方式
    • B树只支持随机搜索，B+树支持随机和顺序搜索。B-树和B+树都可用于文件的索引结构。B-树和B+树都能有效地支持随机检索。
  • B+树的特征
    • 考查B+树的特征，B+树中所有叶子结点都处在同一层次上，但是每个叶子结点中关键字个数不一定相等。

第6章 图

• 图的基本概念
  • 1.图的基本概念
    • 一个图(G)定义为一个偶对(V,E)，记为G=(V,E)。其中：V是顶点（Vertex）的非空有限集合，记为V(G)；E是无序集V&V的一个子集，记为E(G)，其元素是图的弧（Arc）。其形式化定义为： G=(V,E) V={v|v∈data object } E={<v,w>|v,w∈V∧p(v,w)} P(v,w)表示从顶点v到顶点w有一条直接通路。 设有有向图G1和无向图G2，形式化定义分别是： G1=(V1,E1) V1={a,b,c,d,e} E1={<a,b>,<a,c>,<a,e>,<c,d>,<c,e>,<d,a>,<d,b>,<e,d>} G2=(V2,E2) V2={a,b,c,d} E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)} 它们所对应的图如图所示。 
    • 边（Arc）
      • 表示两个顶点v和w之间存在一个关系，用顶点偶对<v,w>表示。通常根据图的顶点偶对将图分为有向图和无向图。
    • 有向图（Digraph）
      • 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是有序的，称图G是有向图。 在有向图中，若<v,w>∈E(G)，表示从顶点v到顶点w有一条弧。其中：v称为弧尾或始点，w称为弧头或终点。 
    • 无向图（Undigraph）
      • 若图G的关系集合E(G)中，顶点偶对<v,w>的v和w之间是无序的，称图G是无向图。 在无向图中，若<v,w>∈E(G)，有<w,v>∈E(G)，即E(G)是对称，则用无序对(v,w)表示v和w之间的一条边（Edge），因此(v,w)和(w,v)代表的是同一条边。 
    • 简单图
      • 既不含平行边也不包含自环的图称为简单图。
    • 完全无向图
      • 对于无向图，若图中顶点数为n ，用e表示边的数目，则e∈[0,n(n-1)/2]。具有n(n-1)/2条边的无向图称为完全无向图。 完全无向图另外的定义是：  即图中任意两个不同的顶点间都有一条无向边，这样的无向图称为完全无向图。 
    • 完全有向图
      • 对于有向图，若图中顶点数为n ，用e表示弧的数目，则e∈[0,n(n-1)]。具有n(n-1)条边的有向图称为完全有向图。 完全有向图另外的定义是：  即图中任意两个不同的顶点间都有一条弧，这样的有向图称为完全有向图。 
    • 稀疏图与稠密图
      • 有很少边或弧的图（e<nlogn）的图称为稀疏图，反之称为稠密图。
    • 子图
      •  
    • 生成子图
      •  
    • 顶点的邻接（Adjacent）
      • 对于无向图G=(V,E)，若边(v,w)∈E，则称顶点v和w互为邻接点，即v和w相邻接。边(v,w)依附（incident）于顶点v和w。 对于有向图G=(V,E)，若有向弧<v,w>∈E，则称顶点v“邻接到”顶点w，顶点w“邻接自”顶点v，弧<v,w>与顶点v和w“相关联”。
    • 顶点的度、入度、出度
      •  在无向图中，所有顶点度的和是图中边的2倍。即  i=1,2,...,n,e为图的边数。 
    • 路径（Path）
      • 对无向图G=(V,E)，若从顶点vi经过若干条边能到达vj，称顶点vi和vj是连通的，又称顶点vi到vj有路径。 对有向图G=(V,E)，从顶点vi到vj有有向路径，指的是从顶点vi经过若干条有向边（弧）能到达vj。 路径是图G中连接两顶点之间所经过的顶点序列。即  路径上边或有向边（弧）的数目称为该路径的长度。
      • 简单路径
        • 在一条路径中，若没有重复相同的顶点，该路径称为简单路径。
      • 回路（环）
        • 第一个顶点和最后一个顶点相同的路径称为回路（环）。
      • 简单回路（简单环）
        • 在一个回路中，若除第一个与最后一个顶点外，其余顶点不重复出现的回路称为简单回路（简单环）。
    • 连通图和非连通图
      •  
      • 图的连通分量
        • 若G是非连通图，则极大的连通子图称为G的连通分量。 “极大”的含义：指的是对子图再增加图G中的其它顶点，子图就不再连通。 
    • 强连通图和非强连通图及其连通分量
      • 对有向图G=(V,E)，若对于任意<vi,vj >∈V，都有以vi为起点，vj为终点以及以vj为起点，vi为终点的有向路径，称图G是强连通图，否则称为非强连通图。若G是非强连通图，则极大的强连通子图称为G的强连通分量。  
    • 生成树
      • 一个连通图（无向图）的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树，如图所示。 
      • 关于无向图的生成树的几个结论
        • 一棵有n个顶点的生成树有且仅有n-1条边； 如果一个图有n个顶点和小于n-1条边，则是非连通图；如果多于n-1条边，则一定有环； 有n-1条边的图不一定是生成树。
      • 有向图的生成森林
        • 有向树只有一个顶点的入度为0，其余顶点的入度均为1的有向图，如图。 有向图的生成森林是这样一个子图，由若干棵有向树组成，含有图中全部顶点。 
    • 网（带权图）
      • 每个边（或弧）都附加一个权值的图，称为带权图。带权的连通图（包括弱连通的有向图）称为网或网络。网络是工程上常用的一个概念，用来表示一个工程或某种流程，如图所示。 
    • 抽象数据类型
      • ADT Graph{ 数据对象V：具有相同特性的数据元素的集合，称为顶点集。 数据关系R：R={VR} VR={<v,w>|<v,w>| v,weV∧p(v,w),<v,w>表示从v到w的弧，P(v,w)定义了弧<v,w>的信息} 基本操作P： Create_Graph()：图的创建操作。 初始条件：无。 操作结果：生成一个没有顶点的空图G。 GetVex(G,v)：求图中的顶点v的值。 初始条件：图G存在，v是图中的一个顶点。 操作结果：生成一个没有顶点的空图G。 DFStraver(G,V)：从v出发对图G深度优先遍历。 初始条件：图G存在。 操作结果：对图G深度优先遍历，每个顶点访问且只访问一次。 BFStraver(G,V)：从v出发对图G广度优先遍历。 初始条件：图G存在。 操作结果：对图G广度优先遍历，每个顶点访问且只访问一次。 }ADT Graph
• 图的存储
  • 图的存储结构比较复杂，其复杂性主要表现在： 任意顶点之间可能存在联系，无法以数据元素在存储区中的物理位置来表示元素之间的关系。 图中顶点的度不一样，有的可能相差很大，若按度数最大的顶点设计结构，则会浪费很多存储单元，反之按每个顶点自己的度设计不同的结构，又会影响操作。 图的常用的存储结构有：邻接矩阵、邻接链表。
  • 邻接矩阵
    • 1.邻接矩阵(数组)表示法
      • 基本思想：对于有n个顶点的图，用一维数组vexs[n]存储顶点信息，用二维数组A[n][n]存储顶点之间关系的信息。该二维数组称为邻接矩阵。 在邻接矩阵中，以顶点在vexs数组中的下标代表顶点，邻接矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系的信息。
    • 2.无向图邻接矩阵
      • （1）无权图的邻接矩阵
        • 无向无权图G=(V,E)有n(n≥1)个顶点，其邻接矩阵是n阶对称方阵，如图所示。其元素的定义如下：  
      • （2）带权图的邻接矩阵
        • 无向带权图G=(V,E)的邻接矩阵如图所示。其元素的定义如下：  
      • （3）无向图邻接矩阵的特性
        • 邻接矩阵是对称方阵； 邻接矩阵是唯一的； 对于顶点vi，其度数是第i行的非0元素的个数； 无向图的边数是上（或下）三角形矩阵中非0元素个数。
    • 3.有向图邻接矩阵
      • （1）无权图的邻接矩阵
        • 若有向无权图G=(V,E)有n(n≥1)个顶点，则其邻接矩阵是n阶对称方阵，如图所示。元素定义如下：  
      • （2）带权图的邻接矩阵
        • 有向带权图G=(V,E)的邻接矩阵如图所示。其元素的定义如下：  
      • （3）有向图邻接矩阵的特性
        • 对于顶点vi，第i行的非0元素的个数是其出度OD(vi)；第i列的非0元素的个数是其入度ID(vi)。 邻接矩阵中非0元素的个数就是图的弧的数目。
    • 4.邻接矩阵的特性
      • 给定图，邻接矩阵唯一； 邻接矩阵所占的空间开销是O(N²)，其中N是定点个数，与边的个数无关； 邻接矩阵适合于稠密图，不适合于稀疏图； 计算度通过遍历行或者列来实现。
    • 5.邻接矩阵的基本操作
      • 存储结构形式定义
        • 定义两个数组分别存储顶点信息（数据元素）和边或弧的信息（数据元素之间的关系）。其存储结构形式定义如下： #define INFINITY MAX_VAL /*最大值∞*/ #define MAX_VEX 30 /*最大顶点数目*/ typedef enum {DG,AG,WDG,WAG} GraphKind ; /*{有向图,无向图,带权有向图,带权无向图}*/ typedef struct ArcType { int vex1,vex2; /*弧或边所依附的两个顶点*/ ArcValType ArcVal; /*弧或边的权值*/ ArcInfoType ArcInfo; /*弧或边的其它信息*/ } ArcType ; /*弧或边的结构定义*/ typedef struct { GraphKind kind; /*图的种类标志*/ int vexnum,arcnum; /*图的当前顶点数和弧数*/ int vexs[MAX_VEX]; /*顶点向量*/ int adj[MAX_VEX][MAX_VEX]; /*邻接矩阵*/ } MGraph; /*图的结构定义*/
      • （1）图的创建
        • AdjGraph *Create_Graph(MGraph * G) { printf("请输入图的种类标志："); scanf("%d",&G->kind); G->vexnum=0; /*初始化顶点个数*/ return(G); }
      • （2）图的顶点定位
        • 图的顶点定位操作实际上是确定一个顶点在vexs数组中的位置（下标），其过程完全等同于在顺序存储的线性表中查找一个数据元素。算法实现： int LocateVex(MGraph *G,int *vp) { int k ; for (k=0;k<G->vexnum;k++) if(G->vexs[k]==*vp) return(k); return(-1); /*图中无此顶点*/ } 
      • （3）向图中增加顶点
        • 向图中增加一个顶点的操作，类似在顺序存储的线性表的末尾增加一个数据元素。 int AddVertex(MGraph *G,int *vp) { int k , j; k=G->vexnum ; G->vexs[G->vexnum++]=*vp; if (G->kind==DG||G->kind==AG)/*是不带权的有向图或无向图*/ for (j=0 ; j<G->vexnum ; j++) G->adj[i][k].ArcVal=G->adj[k][i].ArcVal=0 ; else /*是带权的有向图或无向图*/ for (j=0 ; j<G->vexnum ; j++) G->adj[i][k].ArcVal=G->adj[k][j].ArcVal=INFINITY return(k) ;}
      • （4）向图中增加一条弧
        • 根据给定的弧或边所依附的顶点，修改邻接矩阵中所对应的数组元素。  int AddArc(MGraph *G,ArcType *arc) { int k , j ; k=LocateVex(G, &arc->vex1) ; j=LocateVex(G，&arc->vex1) ; if(G->kind==DG || G->kind==WDG){/*是有向图或带权的有向图*/ G->adj[k][i].ArcVal=arc->ArcVal; G->adj[k][j].ArcInfo=arc->ArcInfo; }else { /*是无向图或带权的无向图,需对称赋值*/ G->adj[k][j].ArcVal=arc->ArcVal ; G->adj[j][k].ArcVal=arc->ArcVal ; G->adj[k][j].ArcInfo=arc->ArcInfo ; G->adj[j][k].ArcInfo=arc->ArcInfo ; } return(1); }
  • 邻接表
    • 1.邻接表概述
      • 基本思想
        • 对图的每个顶点建立一个单链表，存储该顶点所有邻接顶点及其相关信息。每一个单链表设一个表头结点。 第i个单链表表示依附于顶点V的边（对有向图是以顶点V为头或尾的弧）。  在图的邻接链表表示中，所有顶点结点用一个向量以顺序结构形式存储，可以随机访问任意顶点的链表，该向量称为表头向量（表向量），向量的下标指示顶点的序号。 
    • 2.邻接表结点结构
      • 链表中的结点称为表结点，每个结点由三个域组成，如图（a）所示。其中邻接点域（adjvex）指示与顶点V邻接的顶点在图中的位置（顶点编号），链域（nextarc）指向下一个与顶点V邻接的表结点，数据域（info）存储和边或弧相关的信息，如权值等。对于无权图，如果没有与边相关的其他信息，可省略此域。 每个链表设一个表头结点（称为顶点结点），由两个域组成，如图（b）所示。链域（firstarc）指向链表中的第一个结点，数据域（data）存储顶点名或其他信息。  
    • 3.无向图的邻接表
      • 头插法，尾插法 
    • 4.有向图的邻接表
      • 有向图的正向邻接表
        • 头插法、尾插法 
      • 有向图的逆向邻接表
        • 头插法、尾插法 
    • 5.邻接表的特点
      • 表头向量中每个分量就是一个单链表的头结点，分量个数就是图中的顶点数目； 在边或弧稀疏的条件下，用邻接表表示比用邻接矩阵表示节省存储空间； 在无向图，顶点Vi的度是第i个链表的结点数； 对有向图可以建立正邻接表或逆邻接表。正邻接表是以顶点Vi为出度（即为弧的起点）而建立的邻接表；逆邻接表是以顶点Vi为入度（即为弧的终点）而建立的邻接表； 在有向图中，第i个链表中的结点数是顶点Vi的出（或入）度；求入（或出）度，须遍历整个邻接表； 在邻接表上容易找出任一顶点的第一个邻接点和下一个邻接点；
    • 6.邻接表的操作
      • 1）结点及其类型定义
        • typedef struct ArcType { int vex1, vex2 ; /*弧或边所依附的两个顶点*/ lnfoTypeinfo ; //与边或弧相关的信息，如权值 }ArcType ; /*弧或边的结构定义*/ typedef struct { GraphKind kind ; /*图的种类标志*/ int vexnum ; VexNode AdjList[MAX_VEX]; }ALGraph ; /*图的结构定义*/  #define MAX_VEX 30 /*最大顶点数*/ typedef enum {DG, AG, WDG,WAG} GraphKind ; typedef struct LinkNode { int adjvex ; // 邻接点在头结点数组中的位置（下标） lnfoType info ; // 与边或弧相关的信息，如权值 struct LinkNode *nextarc ; //指向下一个表结点 }LinkNode ; /*表结点类型定义*/
      • 2）图的创建
        • ALGraph *Create_Graph(ALGraph * G){ printf("请输入图的种类标志："); scanf("%d",&G->kind); G->vexnum=0; /*初始化顶点个数*/ return(G); }
      • 3）图的顶点定位
        • 图的顶点定位实际上是确定一个顶点在AdjList数组中的某个元素的data域内容。 算法实现： int LocateVex(ALGraph *G, int *vp) { int k; for (k=0; k<G->vexnum; k++) if (G->AdjList[k].data==*vp) return(k) ; return(-1); /*图中无此顶点*/} 
      • 4）向图中增加顶点
        • 向图中增加一个顶点的操作，在AdjList数组的末尾增加一个数据元素。 算法实现： int AddVertex(ALGraph *G, VexType *vp) { int k,j; G->AdjList[G->vexnum].data=*vp ; G-> AdjList[G->vexnum].degree=0 ; G->AdjList[G->vexnum].firstarc=NULL ; k=++G->vexnum ; return(k) ; }
      • 5）向图中增加一条弧
        • 根据给定的弧或边所依附的顶点，修改单链表：无向图修改两个单链表；有向图修改一个单链表。 算法实现： int AddArc(ALGraph *G , ArcType *arc) { int k,j; LinkNode *p,*q; k=LocateVex(G,&arc->vex1) ; j=LocateVex(G,&arc->vex2) ; p=(LinkNode *)malloc(sizeof(LinkNode)) ; p->adjvex=arc->vex1 ; p->info=arC->info ; p->nextarc=NULL; /*边的起始表结点赋值*/ q=(LinkNode *)malloc(sizeof(LinkNode)) ; q-> adjvex=arc->vex2 ; q-> info=arc->info ; q-> nextarc=NULL; /* 边的末尾表结点赋值*/ /*是无向图，用头插入法插入到两个单链表*/ if (G->kind==AG||G->kind==WAG) { q->nextarc=G->adjlist[k].firstarc ; G->adjlist[k].firstarc=q ; p->nextarc=G->[adjlistj].firstarc ; G->adjlist[j].firstarc=p ; }else { /*建立有向图的邻接链表，用头插入法*/ q->nextarc=G->adjlist[k].firstarc; G->adjlist[k].firstarc=q; /*建立正邻接链表用*/ } return(1); }
• 深度优先遍历
  • 1.图的遍历（Travering Graph）
    • 从图的某一顶点出发，访遍图中的其余顶点，且每个顶点仅被访问一次。图的遍历算法是各种图的操作的基础。
    • 复杂性
      • 图的任意顶点可能和其余的顶点相邻接，可能在访问了某个顶点后，沿某条路径搜索后又回到原顶点。
    • 解决办法
      • 在遍历过程中记下已被访问过的顶点。设置一个辅助向量Visited[1...n]（n为顶点数），其初值为0，一旦访问了顶点vi后，使Visited[i]为1或为访问的次序号。 图的遍历算法有深度优先搜索算法和广度优先搜索算法。采用的数据结构是（正）邻接链表。
  • 2.深度优先搜索（DFS）
    • 深度优先搜索（Depth First Search--DFS）遍历类似树的先序遍历，是树的先序遍历的推广。
    • 1）算法思想
      • 设初始状态时图中的所有顶点未被访问，则： （1）：从图中某个顶点vi出发，访问vi；然后找到vi的一个邻接顶点vi₁； （2）：从vi₁出发，深度优先搜索访问和vi₁相邻接且未被访问的所有顶点； （3）：转（1），直到和vi相邻接的所有顶点都被访问为止 （4）：继续选取图中未被访问顶点vj作为起始顶点，转（1） ，直到图中所有顶点都被访问为止。
    • 2）算法实现
      • 由算法思想知，这是一个递归过程。因此，先设计一个从某个顶点（编号）为v0开始深度优先搜索的函数，便于调用。 在遍历整个图时，可以对图中的每一个未访问的顶点执行所定义的函数。  对无向图进行DFS遍历调用DFS函数的次数=连通分量数 对于连通图，只需调用1次DFS
    • 3）算法分析
      • 遍历时，对图的每个顶点至多调用一次DFS函数。其实质就是对每个顶点查找邻接顶点的过程，取决于存储结构。 当图有e条边，其时间复杂度为O(e)，总时间复杂度为O(n+e)。 当图有n个顶点，最复杂的情况，是栈中存有所有顶点，故而O(n)。
    • 4）深度优先生成树
      • 
    • 5）深度优先生成森林
      • 
• 广度优先遍历
  • 1.广度优先搜索（BFS）
    • 广度优先搜索（Breadth First Search-- BFS）遍历类似树的按层次遍历的过程。
    • 1）算法思想
      • 设初始状态时图中的所有顶点未被访问，则： （1）从图中某个顶点vi出发，访问vi； （2）访问vi的所有相邻接且未被访问的所有顶点vi₁,vi₂,...,vim； （3）以vi₁,vi₂,...,vim的次序，以vij（1≤j≤m）依此作为vi，转（1）； （4）继续选取图中未被访问顶点vk作为起始顶点，转（1），直到图中所有顶点都被访问为止。
    • 2）算法实现
      • 由算法思想知，先设计一个从某个顶点（编号）为v0开始广度优先搜索的函数便于调用。 在遍历整个图时，可以对图中的每一个未访问的顶点执行所定义的函数。   对无向图进行BFS遍历调用BFS函数的次数=连通分量数 对于连通图，只需调用1次BFS。
    • 3）算法分析
      • 遍历时，对图的每个顶点至多调用一次BFS函数。 其实质就是对每个顶点查找邻接顶点的过程，取决于存储结构。 当图有e条边，其时间复杂度为O(e)，总时间复杂度为O(n+e)。 当图有n个顶点，最复杂的情况，是队列中存有所有顶点，故而O(n)。
    • 4）广度优先生成树
      • 
    • 5）广度优先生成森林
      • 
• 比较
  • 用广度优先搜索算法遍历图与深度优先搜索算法遍历图的唯一区别是邻接点搜索次序不同，因此，广度优先搜索算法遍历图的总时间复杂度为O(n+e)。 图的遍历可以系统地访问图中的每个顶点，因此，图的遍历算法是图的最基本、最重要的算法，许多有关图的操作都是在图的遍历基础之上加以变化来实现的。 关于图的遍历： 1.深度优先遍历使用栈这种数据结构，广度优先遍历使用队列这种数据结构； 2.每个连通分量调用一次遍历算法，那么调用遍历算法的次数等于连通分量的数量； 3.使用邻接矩阵的遍历结果是唯一的；使用邻接表时，由于邻接表不是唯一的，所以遍历结果不是唯一的，但是一旦给定邻接表，遍历结果唯一，即必须按照邻接表的顺序遍历； 4.使用邻接矩阵的时间复杂度是O(n^2)，使用邻接表的时间复杂度是O(n+e)； 5.两种遍历算法会得到深度优先遍历树和广度优先遍历树。 特别说明： 使用邻接矩阵的遍历结果是唯一的； 使用邻接表时，由于邻接表不是唯一的，所以遍历结果不是唯一的，但是一旦给定邻接表，遍历结果唯一，即必须按照邻接表的顺序遍历。
• 最小生成树
  • 1.生成树的概念
    • 一个连通图（无向图）的生成树是一个极小连通子图，它含有图中全部n个顶点和只有足以构成一棵树的n-1条边，称为图的生成树，如图所示。  
    • 关于无向图的生成树的几个结论
      • 一棵有n个顶点的生成树有且仅有n-1条边； 如果一个图有n个顶点和小于n-1条边，则是非连通图；如果多于n-1条边，则一定有环； 有n-1条边的图不一定是生成树。
    • 最小生成树
      • 设图的顶点表示城市，边表示两个城市之间的高铁线路，边的权值指的是两个城市之间的高铁费用。n个城市之间最多可以建n×(n-1)/2条线路，如何选择其中的n-1条，使总的建造费用最低？  如果连通图是一个带权图，则其生成树中的边也带权，生成树中所有边的权值之和称为生成树的代价。最小生成树（Minimum Spanning Tree，MST）：带权连通图中代价最小的生成树称为最小生成树。 如下特点： 一棵有n个顶点的生成树有且仅有n-1条边； 这n-1条边使这n个顶点相联通； n-1条边的权值之和最小； 基本思想是： 尽可能选取权值最小的边，但不能构成回路； 选择n-1条边构成最小生成树。 
  • 2.最小生成树的性质
    • 最小生成树的边数=顶点数-1。砍掉一条则不连通，增加一条边则会出现回路； 如果一个连通图本身就是一棵树，则其最小生成树就是它本身； 只有连通图才有生成树，非连通图只有生成森林； 这n-1条边使这n个顶点相联通； 这n-1条边的权值之和最小； 最小权值一定包含在最小生成树中； MST树形可能不唯一。  MST的如下性质： 设G=(V,E)是一个带权连通图，U是顶点集V的一个非空子集。若u∈U，v∈V-U，且(u,v)是U中顶点到V-U中顶点之间权值最小的边，则必存在一棵包含边(u,v)的最小生成树。 证明：用反证法证明。 设图G的任何一棵最小生成树都不包含边(u,v)。设T是G的一棵生成树，则T是连通的，从u到v必有一条路径(u,...,v)，当将边(u,v)加入到T中时就构成了回路。则路径(u,...,v)中必有条边(u',v')，满足u'∈U，v'∈V-U。删去边(u',v')便可消除回路，同时得到另一棵生成树T'。 由于(u,v)是U中顶点到V-U中顶点之间权值最小的边，故(u,v)的权值不会高于(u',v')的权值，T'的代价也不会高于T，T'是包含(u,v) 的一棵最小生成树，与假设矛盾。
  • 3.普里姆（Prim）算法
    • 从连通网N=(U,E)中找最小生成树T=(U,TE)。
    • 1）算法思想
      • （1）若从顶点v0出发构造，U={v0}，TE={}； （2）先找权值最小的边(u,v)，其中u∈U且v∈V-U，并且子图不构成环，则U=U∪{v}，TE=TE∪{(u，v)}； （3）重复（2），直到U=V为止。则TE中必有n-1条边，T=(U,TE)就是最小生成树。
    • 2）构造过程
      • 按prim算法从v2出发构造最小生成树的过程  设置一个一维数组closedge[n]，用来保存V-U中各顶点到U中顶点具有权值最小的边。数组元素的类型定义是： struct { int adjvex; /* 边所依附于U中的顶点*/ int lowcost; /* 该边的权值*/ } closedge[MAX_ EDGE] ; 例如：closedge[j].adjvex=k，表明边(vj,vk)是V-U中顶点vj到U中权值最小的边，而顶点vk是该边所依附的U中的顶点。closedge[j].lowcost存放该边的权值。
    • 3）思想实现
      •  
    • 4）算法分析
      • 设带权连通图有n个顶点，则算法的主要执行是二重循环：求closedge中权值最小的边，频度为n-1；修改closedge数组，频度为n。因此，整个算法的时间复杂度是O(n²)，与边的数目无关。 适合于稠密图；
  • 4.克鲁斯卡尔（Kruskal）算法
    • 1）算法思想
      • 设G=(V,E)是具有n个顶点的连通网，T=(U,TE)是其最小生成树。初值：U=V,TE={}。 对G中的边按权值大小从小到大依次选取。 （1）选取权值最小的边(vi,vj)，若边(vi,vj)加入到TE后形成回路，则舍弃该边（边(vi,vj)）；否则，将该边并入到TE中，即TE=TE∪{(vi,vj)}。 （2）重复（1），直到TE中包含有n-1条边为止。
    • 2）构造过程
      • 
    • 3）算法分析
      • 设带权连通图有n个顶点，e条边，则算法的主要执行的是： Vset数组初始化：时间复杂度是O(n)； 边表按权值排序：若采用堆排序或快速排序，时间复杂度是O(eloge)； 适合于稀疏图；
  • 5.考试的破圈法和加边法
    • 普利姆和克鲁斯卡尔算法：加边法
      • 
    • 破圈法
      • 将每个环的最大边去掉直到没有环 
  • 6.MST唯一性讨论
    • ①当带权图中，权重均不相等时，MST是唯一的，反之不成立；  ②当图中存在环时，且环上相等权重较大时，MST一般不唯一，反之不成立。
  • 最小权重问题
    • ①最小权重不一定会出现在所有的MST中； ②最小权重一定会出现在某棵MST中。
• 最短路径
  • 1.问题引入
    • 若用带权图表示交通网，图中顶点表示地点，边代表两地之间有直接道路，边上的权值表示路程（或所花费用或时间）。从一个地方到另一个地方的路径长度表示该路径上各边的权值之和。  问题： 两地之间是否有通路？ 在有多条通路的情况下，哪条最短？ 考虑到交通网的有向性，直接讨论的是带权有向图的最短路径问题，但解决问题的算法也适用于无向图。 将一个路径的起始顶点称为源点，最后一个顶点称为终点。
  • 2.单源点最短路径
    • 对于给定的有向图G=(V,E)及单个源点Vs，求Vs到G的其余各顶点的最短路径。 针对单源点的最短路径问题，Dijkstra提出了一种按路径长度递增次序产生最短路径的算法，即迪杰斯特拉（Dijkstra）算法。
    • 1）基本思想
      • 从图的给定源点到其它各个顶点之间客观上应存在一条最短路径，在这组最短路径中，按其长度的递增次序，依次求出到不同顶点的最短路径和路径长度。即按长度递增的次序生成各顶点的最短路径，即先求出长度最小的一条最短路径，然后求出长度第二小的最短路径，依此类推，直到求出长度最长的最短路径。 设给定源点为Vs , S为已求得最短路径的终点集，开始时令S={Vs}。当求得第一条最短路径(Vs,Vi)后, S为{Vs,Vi}。根据以下结论可求下一条最短路径。设下一条最短路径终点为Vj，则Vj只有： 源点到终点有直接的弧<Vs,Vj>； 从Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中。即只有这条最短路径的最后一条弧才是从S内某个顶点连接到S外的顶点Vj。
    • 2）算法步骤
      • ①令S={Vs}，用带权的邻接矩阵表示有向图，对图中每个顶点Vi按以下原则置初值：  ②选择一个顶点Vj，使得：dist[j]=Min{ dist[k] l Vk属于V-S } Vj就是求得的下一条最短路径终点，将Vj并入到S中，即S=S∪{Vj}。 ③对V-S中的每个顶点V ，修改dist[k]，方法是：若dist[j]+Wjk<dist[k]，则修改为：  ④重复②，③，直到S=V为止。
    • 3）算法实例
      • 用带权的邻接矩阵表示有向图， 设数组pre[n]保存从Vs到其它顶点的最短路径。若pre[i]=k，表示从Vs到Vi的最短路径中，Vi的前一个顶点是Vk，即最短路径序列是(V,...,Vk,V)。 设数组final[n]，标识一个顶点是否已加入S中。  源点到终点有直接的弧<Vs,Vj>； 从Vs出发到Vj的这条最短路径所经过的所有中间顶点必定在S中 
    • 4）算法实现
      • BOOLEAN final[MAX_VEX]; int pre[MAX_VEX], dist[MAX_VEX]; void Dijkstra_path (AdjGraph *G, int v) { /*从图G中的顶点v出发到其余各顶点的最短路径*/ int j, k, m, min ; for ( j=0; j<G->vexnum; j++) { pre[j]=v ; final[j]=FALSE ; dist[j]=G->adj[v][j]; } /*各数组的初始化*/ dist[v]=0; final[v]=TRUE; /*设置S={v}*/ for ( j=0; j<G->vexnum-1; j++){ /*其余n-1个顶点*/ m=0 ; while (final[m]) m++; /*找不在S中的顶点vk */ Min = INFINITY ; for ( k=0; k<G->vexnum; k++){ if (!final[k] && dist[m]<min){ min=dist[k]; m=k ; } } /*求出当前最小的dist[k]值*/ final[m]=TRUE; /*将第k个顶点并入S中*/ for ( j=0; j<G->vexnum; j++) /*修改dist和pre数组的值*/ if ( !final[j] && (dist[m]+G->adj[m][j]<dist[])) { dist[j]=dist[m]+G->adj[m][j] ; pre[j]=m; } } /*找到最短路径*/ }
    • 5）算法分析
      • Dijkstra算法的主要执行是： 数组变量的初始化：时间复杂度是O(n)； 求最短路径的二重循环：时间复杂度是O(n²)； 因此，整个算法的时间复杂度是O(n²)。
    • 6）负边和负回路
      •   Dijkstra算法目光短浅的，只会关心局部的最优解问题，这是贪心算法的问题。 Dijkstra算法不适用于有负权值的带权图 Dijkstra算法不适用于有负回路的带权图
    • 7）Prim和Dijkstra
      • 
  • 3.每一对顶点间的最短路径
    • 用Dijkstra算法也可以求得有向图G=(V,E)中每一对顶点间的最短路径。方法是：每次以一个不同的顶点为源点重复Dijkstra算法便可求得每一对顶点间的最短路径，时间复杂度是O(n³)。 弗罗伊德（Floyd）提出了另一个算法，其时间复杂度仍是O(n³) ，但算法形式更为简明，步骤更为简单，数据结构仍然是基于图的邻接矩阵。
    • 1）算法思想
      • 设顶点集S（初值为空），用数组A的每个元素A[i][j]保存从Vi只经过S中的顶点到达Vj的最短路径长度，其思想是： ①初始时令S={}，A[i][j]的赋初值方式是：  ②将图中一个顶点Vk加入到S中，修改A[i][j]的值，修改方法是： A[i][i]=Min{A[i][j],(A[i][k]+A[k][j])} 从Vj只经过S中的顶点（Vk）到达Vj的路径长度可能比原来不经过Vk的路径更短。 ③重复②，直到G的所有顶点都加入到S中为止。
    • 2）算法实现
      • 定义二维数组Path[n][n]（n为图的顶点数），元素Path[i][j]保存从Vi到Vj的最短路径所经过的顶点。 若Path[i][i]=k：从Vi到Vj经过Vk，最短路径序列是(Vi,...,Vk,...,Vj)，则路径子序列：(Vi ， ...Vk)和(Vk,...,Vj)一定是从Vi到Vk和从Vk到Vj的最短路径。从而可以根据Path[i][k]和Path[k][j]的值再找到该路径上所经过的其它顶点，...依此类推。   根据上述过程中Path[i][j]数组，得出： V0到V₁：最短路径是{0,1}，路径长度是2； V0到V₂：最短路径是{0,1,2}，路径长度是6； V₁到V0：最短路径是{1,2,0}，路径长度是9； V₁到V₂：最短路径是{1,2}，路径长度是4； V₂到V0：最短路径是{2,0}，路径长度是5； V₂到V₁：最短路径是{2,0,1}，路径长度是7；
    • 3）算法分析
      • 时间复杂度，O(N³) 空间复杂度为O(N²)
    • 4）进一步分析
      •  Floyd算法不能解决带有“负权回路”的图（有负权值的边组成回路），这种图有可能没有最短路径
• 拓扑排序
  • 1.有向无环图及其应用
    • 有向无环图
      • 是图中没有回路（环）的有向图。是一类具有代表性的图，主要用于研究工程项目的工序问题、工程时间进度问题等。
    • 对工程的活动加以抽象
      • 图中顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为顶点表示活动的网（Activity On VertexNetwork，AOV网）。
  • 2.拓扑排序
    • 由某个集合上的一个偏序得到该集合上的一个全序的操作。 即偏序是指集合中仅有部分元素之间可以比较，而全序是指集合中任意两个元素之间都可以比较。 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序： ①每个顶点出现且只出现一次。 ②若顶点A在序列中排在顶点B的前面，则在图中不存在从顶点B到顶点A的路径。  在AOV网中，若有有向边<i,j>，则是j的直接前驱，j是i的直接后继；推而广之，若从顶点i到顶点j有有向路径，则是j的前驱，j是i的后继。 在AOV网中，不能有环，否则，某项活动能否进行是以自身的完成作为前提条件。 检查方法：对有向图的顶点进行拓扑排序，若所有顶点都在其拓扑有序序列中，则无环。
    • 有向图的拓扑排序
      • 构造AOV网中顶点的一个拓扑线性序列(v'1,v'2,...,v'n)，使得该线性序列不仅保持原来有向图中顶点之间的优先关系，而且对原图中没有优先关系的顶点之间也建立一种（人为的）优先关系。
    • 1）算法思想
      • ①在AOV网中选择一个没有前驱的顶点且输出； ②在AOV网中删除该顶点以及从该顶点出发的（以该顶点为尾的弧）所有有向弧（边） ； ③重复①、②，直到图中全部顶点都已输出（图中无环）或图中不存在无前驱的顶点（图中必有环）。
    • 2）算法实例
      • 有向图的拓扑过程 
    • 3）算法实现说明
      • 采用正邻接链作为AOV网的存储结构； 设立堆栈，用来暂存入度为0的顶点； 删除顶点以它为尾的弧：弧头顶点的入度减1。
      • （1）统计各项顶点入度的函数
        • void count_ indegree(ALGraph *G) { int k; LinkNode *p ; for (k=0; k<G->vexnum; k++) G->adjlist[k].indegree=0; /* 顶点入度初始化*/ for (k=0; k<G->vexnum; k++) { p=G-> adjlist[k]firstarc ; while (p!=NULL) /* 顶点入度统计*/ { G->adjlist[p->adjvex].indegree++ ; p=p->nextarc ; } } }
      • （2）拓扑排序算法
        • int Topologic_Sort(ALGraph *G, int topol[]) /*顶点的拓扑序列保存在一维数组topol中*/ { int k, no, vex_ no, top=0, count=0, boolean=1 ; int stack[MAX_VEX]; /* 用作堆栈*/ LinkNode *p; count indegree(G); /*统计各顶点的入度*/ for (k=0; k<G->vexnum; k+ +) if (G->adjlist[k].indegree==0) stack[++top]=G->adjlist[k].data; do{ if (top==0) boolean=0 ; else{ no=stack[top--]; /* 栈顶元索出栈*/ topl[++count]=no; /* 记绿顶点序列*/ p=G->adjlist[no].firstarc ; while (p!=NULL) /*删除以顶点为尾的弧*/ { vex_ no=p->adjvex ; G->adjlist[vex_ no].indegree-- ; if (G->adjlist[vex_ no].indegree==0) stack[++top]=vex_no ; p=p->nextarc ; } } } while(boolean==0) ; if (count<G->vexnum) return(-1) ; else return(1) ; }
    • 4）算法分析
      • 设AOV网有n个顶点，e条边，则算法的主要执行是： 统计各顶点的入度：时间复杂度是O(n+e)； 入度为0的顶点入栈：时间复杂度是O(n)； 排序过程：顶点入栈和出栈操作执行n次，入度减1的操作共执行e次，时间复杂度是O(n+e)； 因此，整个算法的时间复杂度是O(n+e)。
    • 5）拓扑排序唯一性问题
      •  
    • 5）拓扑排序遇到有环图
      •  入度为零的不存在  入度为零的存在但是存在环
• 关键路径
  • 1.有向无环图及其应用
    • 有向无环图
      • 是图中没有回路（环）的有向图。是一类具有代表性的图，主要用于研究工程项目的工序问题、工程时间进度问题等。
    • 对工程的活动加以抽象
      • 图中顶点表示活动，有向边表示活动之间的优先关系，这样的有向图称为顶点表示活动的网（Activity On VertexNetwork，AOV网）。
  • 2.关键路径（Critical Path）
    • AOE（Activity On Edge），是边表示活动的有向无环图。如图所示。图中顶点表示事件（Event），每个事件表示在其前的所有活动已经完成，其后的活动可以开始；弧表示活动，弧上的权值表示相应活动所需的时间或费用。  一个工程（project）都可分为若干个称为活动（active）的子工程（或工序），各个子工程受到一定的条件约束：某个子工程必须开始于另一个子工程完成之后；整个工程有一个开始点（起点）和一个终点。人们关心： 工程能否顺利完成？影响工程的关键活动是什么？ 估算整个工程完成所必须的最短时间是多少？
    • 与AOE有关的研究问题
      • 完成整个工程至少需要多少时间？ 从起点到终点的最长路径长度（路径上各活动持续时间之和）。 长度最长的路径称为关键路径。 如何找关键路径？挨个数  该AOE网的关键路径是：(v0, v2, v4, v7, v8)和(v0, v2, v5, v7, v8)。 哪些活动是影响工程进度（费用）的关键？ 关键路径上的活动称为关键活动。关键活动是影响整个工程的关键。 关键路径活动是：<v0,v2>,<v2,v4>,<v2,v5>,<v4,v7>,<v5,v7>,<v5,v8>。
  • 3.求AOE中关键路径和关键活动
    • 最早发生时间：从左→右，正推法，当存在多条路径，取max； 最晚发生时间：从右→左，倒推法，当存在多条路径，取min。   两者之差叫做松弛量，松弛量为0的均为关键活动。
    • 事件的最早发生时间ve(i)
      • 表示事件vi的最早发生时间，即从起点到顶点vi的最长路径长度。
    • 事件的最晚发生时间vl(i)
      • 表示事件vi的最晚发生时间。
  • 4.关键路径和工程工期
    • 若关键活动耗时增加，则整个工程的工期将增长； 缩短关键活动的时间，可以缩短整个工程的工期。 若有多条关键路径，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
• 刷题笔记
  • 判断有向图是否存在回路的方法
    • （1）利用拓扑排序算法可以判定有向图中是否存在回路。如果拓扑排序的结果只得到了部分顶点的拓扑有序序列，则该有向图中存在回路。 （2）利用深度优先遍历算法可以判定图G中是否存在回路。对于无向图来说，若深度优先遍历过程中遇到了回边则必定存在环；对于有向图来说，这条回边可能是指向深度优先森林中另一棵生成树上顶点的边；但是，如果从有向图上的某个顶点v出发进行深度优先遍历，若在DFS(v)结束之前出现一条从顶点u到顶点v的回边，因u在生成树上是v的孙子，则有向图必定存在包含顶点v和顶点u的环。
  • 邻接矩阵表示图时深度优先遍历时间复杂度
    • 因为在邻接矩阵上遍历，一般至少需要将矩阵中元素—半给过一下，由于矩阵元素个数为n²，因此时间复杂度就是O(n²)。
  • 生成树概念的应用范围
    • 生成树是建立在无向图中的，对于有向图，则没有生成树的概念。
  • DFS遍历无环图退栈打印顶点的输出序列
    • 深度优先遍历使用栈，在退栈时打印结点，栈的特点是先进后出，所以形成逆拓扑序列。
  • 求有向图顶点入边性能最好的描述方式
    • 十字链表容易求得任意顶点的出边和入边，专用于有向图的操作。
  • 用有向无环图描述表达式的方法
    • 先将该表达式转换成有向二叉树，注意到该二叉树中有些顶点时重复的，为了节省存储空间，可以去除重复的顶点（使顶点个数达到最少），将有向二叉树去重转换成有向无环图。
  • Floyd算法使用的设计算法技术
    • Floyd-Warshall是动态规划算法。
  • 邻接多重表和邻接表的区别
    • 邻接多重表与邻接表的差别，仅仅在于同一条边在邻接表中用两个节点表示，在邻接多重表中只用一个节点，邻接多重表的话，不会用重复的表。
  • Dijkstra算法稠密图单源最短路径保存候选最短路径性能最好的数据结构
    • 求单源最短路径的Dijkstra算法，对于稠密图，采用无序线性表保存候选最短路径耗费，性能最好。
  • 完全二叉树是否一定是平衡二叉树
    • 从平衡因子定义看，完全二叉树任一结点的平衡因子的绝对值确实是小于等于1。但是，平衡二叉树本质上是二叉排序树，完全二叉树不一定是排序树。故不能说完全二叉树是平衡二叉树。
  • 稀疏AOE图求解关键路径性能最优的描述方法
    • 稀疏AOE图的非零节点不多，所以选用邻接表效率高，性能最优。
  • 对稀疏矩阵的压缩存储方法
    • 对稀疏矩阵的压缩存储，一般包括三元组和十字链表两种基本方法。
  • 对邻接表求逆邻接表的时间复杂度
    • 由邻接表求逆邻接表对每个节点都要遍历其入度情况，因此需要O(n*e)。

第7章 查找

• 查找的基本概念
  • 查找/检索（Searching）
    • 根据给定的K值，在查找表中确定一个关键字等于给定值的记录或数据元素。 查找表中存在满足条件的记录：查找成功；结果：所查到的记录信息或记录在查找表中的位置。 查找表中不存在满足条件的记录：查找失败。 
  • 查找表（Search Table）
    • 相同类型的数据元素（对象）组成的集合，每个元素通常由若干数据项构成。
  • 关键字（Key，码）
    • 数据元素中某个（或几个）数据项的值，它可以标识一个数据元素。若关键字能唯一标识一个数据元素，则关键字称为主关键字：将能标识若干个数据元素的关键字称为次关键字。
  • 查找有两种基本形式
    • 静态查找（Static Search）
      • 在查找时只对数据元素进行查询或检索，查找表称为静态查找表。
    • 动态查找（Dynamic Search）
      • 在实施查找的同时，插入查找表中不存在的记录，或从查找表中删除已存在的某个记录，查找表称为动态查找表。
  • 根据存储结构分类
    • 顺序表的查找
      • 将给定的K值与查找表中记录的关键字进行比较，找到要查找的记录。
    • 链表的查找
      • 将给定的K值与查找表中记录的关键字逐个进行比较，找到要查找的记录。
    • 散列表的查找
      • 根据给定的K值直接访问查找表，从而找到要查找的记录。
    • 索引表的查找
      • 首先根据索引确定待查找记录所在的块，然后再从块中找到要查找的记录
  • 查找方法评价指标
    • 查找过程中主要操作是关键字的比较，查找过程中关键字的平均比较次数（平均查找长度ASL：Average Search Length）作为衡量一个查找算法效率高低的标准。ASL定义为：  
• 顺序查找
  • 查找思想
    • 从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，查找成功；否则，若扫描完整个表仍然没有找到相应的记录，则查找失败。 
  • 查找过程
    • 比较次数： 查找第1个元素：1 ...... 查找第i个元素：i 查找第n个元素：n 查找失败：n＋1
  • 查找实现
    • #define MAX_SIZE 100 typedef struct SSTable { RecType elem[MAX_SIZE]; /*顺序表*/ int length; /*实际元素个数*/ }SSTable ; int Seq_Search(SSTable ST , KeyType key){ int p ; for (p=0; !EQ(ST.elem[p].key, key) && p < ST.length; p++) return(p); }
  • 算法分析
    • 不失一般性，设查找每个记录成功的概率相等，即Pi=1/n；查找第i个元素成功的比较次数Ci=i； 查找成功时的平均查找长度ASL：  不失一般性，设查找每个记录成功的概率相等，即Pi=1/n；查找第i个元素成功的比较次数Ci=i；包含查找不成功时：查找失败的比较次数为n+1， 若成功与不成功的概率相等，对每个记录的查找概率为Pi=1/(2n)，则平均查找长度ASL: 
  • 顺序查找的适用场景
    •  顺序表和链表都适用
• 折半查找
  • 再谈顺序查找
    • 从表的一端开始逐个将记录的关键字和给定K值进行比较，若某个记录的关键字和给定K值相等，查找成功；否则，若扫描完整个表，仍然没有找到相应的记录，则查找失败。 
  • 折半查找
    • 折半查找又称为二分查找，是一种效率较高的查找方法。假设查找表中的所有记录是按关键字有序（升序或降序）。 查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围（每次将待查记录所在区间缩小一半），直到找到或找不到记录为止。
  • 折半查找算法思想
    • 前提条件：查找表中的所有记录是按关键字有序（升序或降序）。 查找过程中，先确定待查找记录在表中的范围，然后逐步缩小范围（每次将待查记录所在区间缩小一半），直到找到或找不到记录为止。 用Low、High和Mid表示待查找区间的下界、上界和中间位置指针，初值为Low=1，High=n。 （1）取中间位置Mid：Mid=└ow+High)/2┘； （2）比较中间位置记录的关键字与给定的K值： ①相等：查找成功； ②大于：待查记录在区间的前半段，修改上界指针：High=Mid-1，转（1）；③小于：待查记录在区间的后半段，修改下界指针：Low=Mid+1，转（1）； 直到越界（Low>High），查找失败。
  • 折半查找实例
    • （a）查找成功示例  （b）查找不成功示例 
  • 折半查找代码实现
    • int Bin_Search(int [] ST,int n , int key){ int Low=0 ,High=n-1, Mid ; while (Low < High) { Mid=(Low+High)/2; if (a[Mid] == key)) return(Mid); else if(a[Mid]< key)) Low=Mid+1; else High=Mid-1 ; } return(-1); /*查找失败*/ }
  • 折半查找ASL分析
    •  若每次均以mid为根，以小于mid为左子树，以大于mid为右子树，可以构建二叉树。  
  • 折半树的构造
    •  （默认情况）左少右多     （一般情况）左多右少 
  • 折半查找的复杂度
    • 折半查找的判定树中，只有最下面的层是不满的。因此，元素个数为n时树高h=┌log₂(n + 1)┐，因此复杂度是O(h)。
  • 折半查找的进一步思考
    • 折半查找的判定树中，只有最下面的层是不满的。因此，元素个数为n时树高h=┌log₂(n + 1)┐，因此复杂度是O(h)。 我们可以得到，复杂度只和元素的个数n有关，而与元素的值无关。 也就说只要是n个元素，树形一样，ASL一样。
  • 折半查找和顺序查找谁快？
    • 看具体元素在哪里？
• 二叉排序树（BST）
  • 动态查找
    • 当查找表以线性表的形式组织时，若对查找表进行插入、删除或排序操作，就必须移动大量的记录，当记录数很多时，这种移动的代价很大。 利用树的形式组织查找表，可以对查找表进行动态高效的查找。
  • 二叉排序树（BST）
    • 二叉排序树（Binary Sort Tree或Binary Search Tree）的定义为：二叉排序树或者是空树，或者是满足下列性质的二叉树。 （1）若左子树不为空，则左子树上所有结点的值（关键字）都小于根结点的值； （2）若右子树不为空，则右子树上所有结点的值（关键字）都大于根结点的值； （3）左、右子树都分别是二叉排序树。 如图所示。  结论：若按中序遍历一棵二叉排序树，所得到的结点序列是一个递增序列。 BST可以用二叉链表来存储， 结点类型定义如下： typedef struct Node { KeyType key; /*关键字域*/ struct Node *Lchild , *Rchild ; } BSTNode ;
  • BST树的查找
    • 查找思想
      • 首先将给定的K值与二叉排序树的根结点的关键字进行比较：若相等，则查找成功； ①给定的K值小于BST的根结点的关键字：继续在该结点的左子树上进行查找； ②给定的K值大于BST的根结点的关键字：继续在该结点的右子树上进行查找。
    • 代码实现
      • 递归算法
        • BSTNode *BST_Serach(BSTNode *T, KeyType key) { if (T==NULL) return(NULL); else { if (T->key == key) return(T); else if ( key < T->key) return(BST_Serach(T->Lchild, key)); else return(BST_Serach(T->Rchild, key)) ; } }
      • 非递归算法
        • BSTNode *BST_Serach(BSTNode *T, KeyType key) { BSTNode p=T; while (p!=NULL&&(p->key != key)) { if ( key < p->key ) p=p->Lchild ; else p=p->Rchild ; } if (p->key == key ) return(p); else return(NULL); }
  • BST树的插入
    • 在BST树中插入一个新结点，要保证插入后仍满足BST的性质。
    • 插入思想
      • 在BST树中插入一个新结点x时，若BST树为空，则令新结点x为插入后BST树的根结点；否则，将结点x的关键字与根结点T的关键字进行比较： ①若相等：不需要插入； ②若x.key<T->key：结点x插入到T的左子树中； ③若x.key>T->key：结点x插入到T的右子树中。 每次插入的新结点都是BST树的叶子结点，即在插入时不必移动其它结点，仅需修改某个结点的指针。  
    • 算法实现
      • 递归算法
        • void Insert_BST (BSTNode *T, int key) { BSTNode *x ; x=(BSTNode *)malloc(sizeof(BSTNode)) ; X->key=key; x->Lchild=x->Rchild=NULL; if (T==NULL) T=x ; else{ if (T->key == x->key) return ;/*已有结点*/ else if (x->key <T->key) lnsert_BST(T->Lchild, key); else lnsert_BST(T->Rchild, key); }
      • 非递归算法
        • void Insert_BST (BSTNode *T , KeyType key) { BSTNode *x,*p,*q ; x=(BSTNode *)malloc(sizeof(BSTNode)); X->key=key; x->Lchild=x->Rchild=NULL; if (T==NULL) T=x ; else { p=T; while (p!=NULL) { if (p->key == x->key ) return ; q=p; /*q作为p的父结点*/ if (x->key < p->key ) p=p->Lchild ; else p=p->Rchild ; } if (x->key < q->key) q->Lchild=x ; else q->Rchild=x ; } }
  • BST树的删除
    • 从BST树上删除一个结点，仍然要保证删除后满足BST的性质。设被删除结点为p，其父结点为f，删除情况如下： ①若p是叶子结点：直接删除p，如图所示。  ②若p只有一棵子树（左子树或右子树）：直接用p的左子树（或右子树）取代p的位置而成为f的一棵子树。即原来p是f的左子树，则p的子树成为f的左子树；原来p是f的右子树，则p的子树成为f的右子树，如图（c）、（d）所示。  ③若p既有左子树又有右子树：处理方法有以下两种，可以任选其中一种。 用p的直接前驱结点代替p。即从p的左子树中选择值最大的结点s放在p的位置（用结点s的内容替换结点p内容），然后删除结点s。s是p的左子树中的最右边的结点且没有右子树，对s的删除同②，如图所示。  用p的直接后继结点代替p。即从p的右子树中选择值最小的结点s放在p的位置（用结点s的内容替换结点p内容），然后删除结点s。s是p的右子树中的最左边的结点且没有左子树，对s的删除同②，如图所示。 
  • BST树的构造
    • 利用BST树的插入操作，可以从空树开始逐个插入每个结点，从而建立一棵BST树，算法如下： BSTNode *create_BST(){ KeyType key ; BSTNode *T=NULL; scanf("%d" ,&key) ; while (key!=65535) { lnsert_BST(T, key); scanf("%d" , &key); } return(T); } 按照序列str={50,6,60,36，24，29,76,66}建立BST   按照序列str={6,24,29,36,50 ,60 ,66,76}建立BST  按照序列str={76,66,60,50,36,29,24,6}建立BST 
  • BST树ASL
    •  ASL： 最坏情况：每个结点只有一个分支，树高h=结点数n。平均查找长度=O(n)  ASL： 最好情况：n个结点的二叉树最小高度为log₂n+1。平均查找长度=O(log₂n) BST是一种查找效率比较高的组织形式，但其平均查找长度受树的形态影响较大，形态比较均匀时查找效率很好，形态明显偏向某一方向时其效率就大大降低。
• 平衡二叉树（AVL）
  • AVL树的引入
    • BST是一种查找效率比较高的组织形式，但其平均查找长度受树的形态影响较大，形态比较均匀时查找效率很好，形态明显偏向某一方向时其效率就大大降低。 有更好的二叉排序树，其形态总是均衡的，查找时能得到最好的效率，这就是平衡二叉排序树。 平衡二叉排序树（Balanced Binary Tree或Height-Balanced Tree）是在1962年由Adelson-Velskii和Landis提出的，又称AVL树。
  • AVL树的定义
    • 平衡二叉树或者是空树，或者是满足下列性质的二叉树。 （1）：左子树和右子树深度之差的绝对值不大于1； （2）：左子树和右子树也都是平衡二叉树。 如果一棵二叉树既是二叉排序树又是平衡二叉树，称为平衡二叉排序树（Balanced Binary Sort Tree）。 
    • 平衡因子（Balance Factor）
      • 二叉树上结点的左子树的深度减去其右子树深度称为该结点的平衡因子。 因此，平衡二叉树上每个结点的平衡因子只可能是-1、0和1，否则，只要有一个结点的平衡因子的绝对值大于1，该二叉树就不是平衡二叉树。
    • 结点类型定义
      • typedef struct BNode { KeyType key ; /*关键字域*/ int Bfactor ; /*平衡因子域*/ struct BNode *Lchild , *Rchild ; }BSTNode ;
  • AVL树的查找
    • 在平衡二叉排序树上执行查找的过程与二叉排序树上的查找过程完全一样，则在AVL树上执行查找时，和给定的K值比较的次数不超过树的深度。 在平衡二叉排序树上进行查找的平均查找长度和log₂n是一个数量级的，平均时间复杂度为O(log₂n)。
  • AVL树的平衡化旋转
    • 一般的二叉排序树是不平衡的，若能通过某种方法使其既保持有序性，又具有平衡性，就找到了构造平衡二叉排序树的方法，该方法称为平衡化旋转。 在对AVL树进行插入或删除一个结点后，通常会影响到从根结点到插入（或删除）结点的路径上的某些结点，这些结点的子树可能发生变化。    
    • 层次路径
      • 指的是从根到叶子的一条路径，新插入的点会影响到叶子的层次路径。 沿着插入结点上行到根结点，会遇到第一个不平衡的点，这样的结点称为失衡结点。 从第一个不平衡的点，画一条到新插入叶子的路径，首先经过的三个点就是要调整的点。
  • AVL树的结点个数和树高的关系
    • 设深度为h的平衡二叉排序树所具有的最少结点数为Nh，则由平衡二叉排序树的性质知： N0=0, N1=1, N2=2,...,Nh=Nh-1+Nh-2+ 1 含有n个结点的平衡二叉树的最大深度为O(log2n)，平衡二叉树的平均查找长度为O(log2n)
• 红黑树
  • 红黑树的引入
    • 前面我们已经学了AVL树，AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)，但是AVL树的左右子树高度差绝对值不超过1，插入或者删除后重新调整平衡可能需要多达O(logn)次旋转，频繁地调整平衡导致全树整体拓扑结构的变化。而红黑树在AVL树“适度平衡”的基础上，加了一些约束条件︰红黑树的左右子树高度差不超过两倍，本质上说，红黑树也是一种平衡二叉搜索树。
  • 红黑树的定义
    • R-B Tree，全称是Red-Black Tree，又称为“红黑树”，它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色，可以是红（Red）或黑（Black）。通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。  红黑树的查找和BST、AVL数的查找过程一样。
    • 红黑树的特性
      • （1）每个节点是黑色，或红色。 （2）根节点是黑色。 （3）每个叶子节点（NULL）是黑色，叶结点即指树尾端NULL结点。 （4）如果一个节点是红色的，则它的子节点必须是黑色的。（注意：如果结点是黑色的，他的子节点可以是黑色，也可以是红色的） （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点，且将从某节点（不包含该节点）到叶子的任意一条路径上黑色节点的个数称为该节点的黑高。
    • 定理
      • 一棵含有n个节点的红黑树的高度至多为2log(n+1)。
• B-树查找
  • 索引查找的引入
    • 索引技术是组织大型数据库的重要技术，索引结构的基本组成是索引表和数据表两部分，如图所示。  平衡二叉排序树便于动态查找，因此用平衡二叉排序树来组织索引表是一种可行的选择。当用于大型数据库时，所有数据及索引都存储在外存，因此，涉及到内、外存之间频繁的数据交换，这种交换速度的快慢成为制约动态查找的瓶颈。 若以二叉树的结点作为内、外存之间数据交换单位，则查找给定关键字时对磁盘平均进行log2n次访问是不能容忍的，因此，必须选择一种能尽可能降低磁盘I/O次数的索引组织方式。树结点的大小尽可能地接近页的大小。 R.Bayer和E.Mc Creight在1972年提出了一种多路平衡查找树，称为B-树（其变型体是B+树）。
    • 数据表
      • 存储实际的数据记录。
    • 索引表
      • 存储记录的关键字和记录（存储）地址之间的对照表，每个元素称为一个索引项。
  • B-树（B树）定义
    • B-树主要用于文件系统中，在B-树中，每个结点的大小为一个磁盘页，结点中所包含的关键字及其孩子的数目取决于页的大小。一棵度为m的B-树称为m阶B-树，其定义是： 一棵m阶B-树，或者是空树，或者是满足以下性质的m叉树： （1）根结点或者是叶子，或者至少有两棵子树，至多有m棵子树； （2）除根结点外，所有非终端结点至少有┌m/2┐棵子树，至多有m棵子树； （3）所有叶子结点都在树的同一层上，且不包含关键字； 如图是一棵包含13个关键字的4阶B-树。  （4）每个结点应包含如下信息： (n, A0, K1, A1, K2, A2, ... , Kn, An) 其中Ki(1≤i≤n)是关键字，且Ki<Ki+1(1≤i≤n-1)；Ai(i=0, 1,...,n)为指向孩子结点的指针，且Ai-1所指向的子树中所有结点的关键字都小于Ki，Ai所指向的子树中所有结点的关键字都大于Ki；n是结点中关键字的个数，且└m/2┘-1≤n≤m-1，n+1为子树的棵数。 （5）每个结点应包含的关键字： (n, A0, K1, A1, K2, A2, ... , Kn, An) n是结点中关键字的个数，且└m/2┘-1≤n<m-1，n+1为子树的棵数。
  • B-树（B树）查找
    •   从树的根结点T开始，在T所指向的结点的关键字向量key[1...keynum]中查找给定值K（用折半查找）： 若key[i]=K(1<i<keynum)，则查找成功，返回结点及关键字位置；否则，转②； ②将K与向量key[1..keynum]中的各个分量的值进行比较，以选定查找的子树： 若K<key[1]：T=T->ptr[0]; 若key[i]<K<key[i+1](i=1,2,...keynum-1)： T=T->ptr[i]; 若K>key[keynum]：T=T->ptr[keynum]; 转①，直到T是叶子结点且未找到相等的关键字，则查找失败。
  • B-树（B树）查找分析
    • B-树的查找次数等价于树高，含有n个关键字，m阶B-树高的范围是： logm(n+1)<= h<= log┌m/2┐((n+1)/2)+1 （1）总关键字数目n =每个节点的关键字数*总的节点数，所以n最大可取：   所以： 这是h的最小值；每层结点达到最大值。  （2）树中的除根之外的非叶节点最少有┌m/2┐棵子树，而根结点若不是叶子结点，则至少有两棵子树。于是： B-树的查找次数等价于树高，含有n个关键字，m阶B-树高的范围是： logm(n+1)<= h<= log┌m/2┐((n+1)/2)+1  
  • B-树（B树）的插入
    • B-树的生成也是从空树起，逐个插入关键字。插入时不是每插入一个关键字就添加一个叶子结点，而是首先在最低层的某个叶子结点中添加一个关键字，然后有可能“分裂”。 利用m阶B-树的插入操作，可从空树起，将一组关键字依次插入到m阶B-树中，从而生成一个m阶B-树。  设定B-树的阶为5。用关键字序列{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}来构建一棵B-树。因为树的阶为5，那么，每个节点最多有5个子节点，每个节点内的关键字个数为2~4个。 （1）第一步是插入1，2，6，7作为一个节点。  （2）然后插入11，得到1，2，6，7，11。因为节点个数超过4，所以需要对该节点进行拆分。选取中间节点6，进行提升，提升为父节点，于是得到  （3）新插入的节点总是出现在叶子节点上，接着插入4，8，13，直接插入即可，得到  （4）然后插入10。得到  （5）然后插入5，17，9，16，得到如下  （6）之后插入20，插入20后，最右下节点内元素个数为5个，超过最大个数4个，所以，需要把16进行提升，形成如下结构  （7）之后插入3后，需要进行裂变，形成如下结构。  （8）插入12、14、18、19，后形成如下结构。  （9）然后插入15，会导致13提升到根节点，这时，根节点会有5个节点，那么，根节点中的10会再次进行提升，形成如下结构。 
    • 插入思想
      • ①在B-树中查找关键字K，若找到，表明关键字已存在，返回；否则，K的查找操作失败于某个叶子结点，转②； ②将K插入到该叶子结点中，插入时，若： 叶子结点的关键字数<m-1：直接插入； 叶子结点的关键字数=m-1：将结点“分裂”。
    • 结点“分裂”方法
      • 设待“分裂”结点包含信息为： (m, A0, K1, A1, K2, A2, ..., Km，Am)，从其中间位置分为两个结点：(┌m/2┐-1，A0，K1，A1，... , K┌m/2┐-1, A┌m/2┐-1)(m-┌m/2┐，A┌m/2┐，K┌m/2┐+1 ，A┌m/2┐+1,... ，Km，Am) 并将中间关键字K┌m/2┐插入到p的父结点中，以分裂后的两个结点作为中间关键字K┌m/2┐的两个子结点。 当将中间关键字K┌m/2┐插入到p的父结点后，父结点也可能不满足m阶B-树的要求（分枝数大于m），则必须对父结点进行“分裂”，一直进行下去，直到没有父结点或分裂后的父结点满足m阶B-树的要求。 当根结点分裂时，因没有父结点，则建立一个新的根，B-树增高一层。
  • B-树（B树）的删除
    • 在B-树上删除一个关键字K，首先找到关键字所在的结点N，然后在N中进行关键字K的删除操作。 若N不是叶子结点，设K是N中的第i个关键字，则将指针Ai-1所指子树中的最大关键字（或指针Ai所指子树中的最小关键字）K'放在(K)的位置，然后删除K'，而K'一定在叶子结点上。删除关键字h，用关键字g代替h的位置，然后再从叶子结点中删除关键字g。  从叶子结点中删除一个关键字的情况是： （1）若结点N中的关键字个数>┌m/2┐-1：在结点中直接删除关键字K。 （2）若结点N中的关键字个数=┌m/2┐-1：若结点N的左（右）兄弟结点中的关键字个数>┌m/2┐-1，则将结点N的左（或右）兄弟结点中的最大（或最小）关键字上移到其父结点中，而父结点中大于（或小于）且紧靠上移关键字的关键字下移到结点N。 （3）若结点N和其兄弟结点中的关键字数=┌m/2┐-1：删除结点N中的关键字，再将结点N中的关键字、指针与其兄弟结点以及分割二者的父结点中的某个关键字Ki，合并为一个结点，若因此使父结点中的关键字个数<┌m/2┐-1，则依此类推. （1）自己够，就从自己中删除，树不做调整变化。 （2）若自己不够，就找左兄弟，或者右兄弟借结点。 （3）若自己不够，将自己，左兄弟或者右兄弟，根合并在一起，再调整。 树的阶为5，那么，每个节点最多有5个子节点，每个节点内的关键字个数为2~4个。依次删除8、16、15、4这4个元素。  （1）删除8，因为删除8后，不破坏树的性质，所以直接删除即可。  （2）删除16，这导致该节点只剩下一个13节点，不满足节点内元素个数为2~4个的要求了。所以需要调整。这里可以向孩子借节点，把17提升上来即可，得到下图。这里不能和兄弟节点借节点，因为从3，6节点中把6借走后，剩下的3也不满要求了。另外，也不能把孩子中的15提升上来，那样会导致剩下的14不满足要求。  （3）然后删除15，删除15后同样需要调整。调整的方式是，18上升，17下降到原来15的位置，得到下图。  （4）然后删除元素4，删除4后该节点只剩下5，需要调整。可是它的兄弟节点也都没有多余的节点可借，所以需要进行节点合并。节点合并时，方式会有多种，我们选择其中的一种即可。这里，我们选择父节点中的3下沉，和1，以及5进行合并，如下图。  但这次调整，导致6不符合要求了。另外，6非根节点，但只有2个孩子，也不符合要求。需要继续调整。调整的方式是，将10下沉，和6，以及13，18合并为根节点，如下图。 
• 索引查找（B+树）
  • B+树定义
    • 在实际的文件系统中，基本上不使用B-树，而是使用B-树的一种变体，称为m阶B+树。它与B-树的主要不同是叶子结点中存储记录。在B+树中，所有的非叶子结点可以看成是索引，而其中的关键字是作为“分界关键字”，用来界定某一关键字的记录所在的子树。一棵m阶B+树与m阶B-树的主要差异是： （1）若一个结点有n棵子树，则必含有n个关键字； （2）所有叶子结点中包含了全部记录的关键字信息以及这些关键字记录的指针，而且叶子结点按关键字的大小从小到大顺序链接； （3）所有的非叶子结点可以看成是索引的部分，结点中只含有其子树的根结点中的最大（或最小）关键字。 如图是一棵3阶B+树。 由于B+树的叶子结点和非叶子结点结构上的显著区别，因此需要一个标志域加以区分，结点结构定义如下： 
  • B+树的查找
    • 在B+树上进行随机查找时，若非叶子结点的关键字等于给定的K值，并不终止，而是继续向下直到叶子结点（只有叶子结点才存储记录）即无论查找成功与否，都走了一条从根结点到叶子结点的路径。 与B-树相比，对B+树可以从最小关键字起，按叶子结点的链接顺序进行顺序查找。
  • B+树VS B-树：两类树均是m阶
    • 
• 散列（Hash）查找
  • 散列查找的引入
    •  10 0000 0000用户 二叉树：log210 0000 0000 B-树：logm10 0000 0000
    • 基本思想
      • 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法。 
  • 基本概念
    • 哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；当冲突发生时，应该有处理冲突的方法。设计一个散列表应包括： ①散列表的空间范围，即确定散列函数的值域； ②构造合适的散列函数，使得对于所有可能的元素（记录的关键字），函数值均在散列表的地址空间范围内，且出现冲突的可能尽量小； ③处理冲突的方法。即当冲突出现时如何解决。
    • 哈希函数
      • 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象。可写成：addr(ai)=H(ki)，其中i是表中一个元素，addr(ai)是a的地址，ki是a的关键字。
    • 哈希表
      • 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表。
    • 冲突
      • 对于不同的关键字ki、kj，若ki≠kj，但H(ki)=H(kj)的现象叫冲突（collision）。
    • 同义词
      • 具有相同函数值的两个不同的关键字，称为该哈希函数的同义词。
    • 哈希查找（又叫散列查找）
      • 利用哈希函数进行查找的过程叫哈希查找。
  • 哈希函数的构造
    • 哈希函数是一种映象，其设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。哈希函数“好坏”的主要评价因素有： 散列函数的构造简单； 能“均匀”地将散列表中的关键字映射到地址空间。所谓“均匀”（uniform）是指发生冲突的可能性尽可能最少。
    • 直接定址法
      • 取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b（a,b为常数） 特点：直接定址法所得地址集合与关键字集合大小相等，不会发生冲突，但实际中很少使用。
    • 除留余数法
      • 取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p(p≤m)是一种简单、常用的哈希函数构造方法。 其中p是不大于表长m的最大素数。
    • 给定法
      • 题目中告知散列函数。
  • 冲突处理的方法
    • 冲突处理
      • 当出现冲突时，为冲突元素找到另一个存储位置。
    • 开放定址法
      • 基本方法：当冲突发生时，形成某个探测序列；按此序列逐个探测散列表中的其他地址，直到找到给定的关键字或一个空地址（开放的地址）为止，将发生冲突的记录放到该地址中。散列地址的计算公式是： Hi(key)=(H(key)+di)MOD m , i=1，2,... k(k≤m-1) 其中：H(key)：哈希函数；m：散列表长度； di：第i次探测时的增量序列； Hi(key)：经第i次探测后得到的散列地址。
      • 线性探测法
        • 将散列表T[0 ...m-1]看成循环向量。当发生冲突时，从初次发生冲突的位置依次向后探测其他的地址。 增量序列为：di=1, 2, 3, ..., m-1 设初次发生冲突的地址是h，则依次探测T[h+1], T[h+2], ..., 直到T[m-1]时又循环到表头，再次探测T[0], T[1], ..., 直到T[h-1]。探测过程终止的情况是： 探测到的地址为空：表中没有记录。若是查找则失败；若是插入则将记录写入到该地址； 探测到的地址有给定的关键字：若是查找则成功；若是插入则失败； 直到T[h]：仍未探测到空地址或给定的关键字，散列表满。 设散列表长为7，记录关键字组为：15,14, 28, 26, 56, 23, 散列函数：H(key)=key MOD 7，冲突处理采用线性探测法。 解：H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突H2(28)=2 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突 H2(56)=2 又冲突 H3(56)=3 H(23)=23 MOD 7=2 冲突 H1(23)=3 又冲突 H1(23)=4  线性探测法的特点 优点：只要散列表未满，总能找到一个不冲突的散列地址； 缺点：每个产生冲突的记录被散列到离冲突最近的空地址上，从而又增加了更多的冲突机会（这种现象称为冲突的“聚集”）。
      • 二次探测法
        • 增量序列为：di=1²,-1²,2²,-2²,3²,......±k²(k≤└m/2┘) 设散列表长为7，记录关键字组为：15,14,28,26,56,23，散列函数：H(key)=key MOD 7，上述例题若采用二次探测法进行冲突处理，则： H(15)=15 MOD 7=1 H(14)=14 MOD 7=0 H(28)=28 MOD 7=0 冲突 H1(28)=1 又冲突 H2(28)=6 H(26)=26 MOD 7=5 H(56)=56 MOD 7=0 冲突 H1(56)=1 又冲突 H2(56)=6又冲突 H3(56)=4 H(23)=23 MOD 7=2  二次探测法的特点 优点：探测序列跳跃式地散列到整个表中，不易产生冲突的“聚集”现象； 缺点︰不能保证探测到散列表的所有地址。
    • 再哈希法
      • 构造若干个哈希函数，当发生冲突时，利用不同的哈希函数再计算下一个新哈希地址，直到不发生冲突为止。即：Hi=RHi(key) i=1,2,..., k RHi：—组不同的哈希函数。第一次发生冲突时，用RH1计算，第二次发生冲突时，用RH2计算...依此类推直到得到某个Hi不再冲突为止。 优点：不易产生冲突的“聚集”现象； 缺点：计算时间增加。
    • 链地址法
      • 方法：将所有关键字为同义词（散列地址相同）的记录存储在一个单链表中，并用一维数组存放链表的头指针。 设散列表长为m，定义一个一维指针数组： RecNode *linkhash[m]，其中RecNode是结点类型，每个分量的初值为空。凡散列地址为k的记录都插入到以linkhash[k]为头指针的链表中，插入位置可以在表头或表尾或按关键字排序插入。 已知一组关键字(19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79)，哈希函数为：H(key)=key MOD 13，用链地址法处理冲突，如图所示。 
  • 哈希查找分析
    • 从哈希查找过程可见：尽管散列表在关键字与记录的存储地址之间建立了直接映象，但由于“冲突”，查找过程仍是一个给定值与关键字进行比较的过程，评价哈希查找效率仍要用ASL。 哈希查找时关键字与给定值比较的次数取决于： 哈希函数； 处理冲突的方法； 哈希表的填满因子α。填满因子α的定义是： 
• 刷题笔记
  • 伪随机探测再散列法
    • 设哈希函数是H(key)=key%13 所谓伪随机探测再散列： 设伪随机数组为R[1...k]，关键字为V 当出现冲突时，则下一个哈希地址为Hi=(V+R[i])%13
  • 线性探测冲突解决注意事项
    • 线性探测解决冲突的办法指一旦目标空间被占有，则探测相邻的下一个空间，如果空闲则插入，否则继续向下一个探测，如果到了队列末尾则返回队列头探测，一旦全部空间都被占据则无法插入。 这种类型题目要注意问的是探测还是线性探测。线性探测用于解决产生的冲突：查找散列表中离冲突单元最近的空闲单元，并且把新的键插入这个空闲单元。即第一次探测不是线性探测，而产生冲突之后的探测才是线性探测。
  • 分块查找
  • 堆查找的时间复杂度
    • 在堆中，查找操作的时间复杂度是O(n)，因为堆并不保证子节点之间的相对顺序，所以无法利用二分查找等高效算法来进行查找。
  • 次索引及其别称
    • 倒排表由属性（字段、关键字）的值确定记录的位置，这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址，由于不是由记录来确定属性值，而是有属性值来确定记录的位置，因而叫倒排索引。
  • 哈希表查找失败的平均查找长度
  • B+树的适用场合
    • B+树是应文件系统所需而产生的B-树的变形，前者比后者更加适用于实际应用中的操作系统的文件索和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。
  • ISAM和VSAM组织文件的文件类型
    • ISAM（Indexed Sequential Access Methed，索引顺序存取方法）是一种专为磁盘存取文件设计的文件组织方式，采用静态索引结构。 VSAM（Virtual Storage Access Method，虚拟存储存取方法）也是一种索引顺序文件的组织方式，采用B+树作为动态索引结构。
  • 静态查找表和动态查找表的区别
    • 静态查找表只进行以下2个操作： 1.查找某个“特定”数据元素是否在查找表中 2.查找某个“特定”数据元素的各种属性 有序表、分块有序表、线性链表都是静态查找表 性能分析：平均查找长度：（当查找关键字等概率时）ASL = 1/(n+1) 动态查找表：表结构是在查找过程中动态生成的，通俗解释，对于给定key，若表中存在某关键字与key相等则查找成功返回，若未找到则插入关键字等于key的记录。二叉排序树、平衡二叉树、B树、B+树都是动态查找。
  • 平方取中法
    • 平方取中法：将关键字先平方，然后截取中间x位作为存储位置。适合用于不知道关键词分布，且位数不长的情况。
  • 排序连续顺序文件
  • 既能快速查找又能适应动态变化的查找方法
    • 如果既要保持对线性表的查找具有较快的速度，又要能够满足表元素动态变化的要求，则可采用分块查找的方法。
  • 链地址法解决冲突的哈希表与ASL直接相关的因素
    • 装填因子=表中的记录数/哈希表的长度，如果装填因子越小，表明表中还有很多的空单元，则发生冲突的可能性越小；而装填因子越大，则发生冲突的可能性就越大，在查找时所耗费的时间就越多。因此，Hash表的平均查找长度和装填因子有关。
  • 适于查找动态查找表的组织结构
    • 适于对动态查找表进行高效率查找的组织结构是三叉排序树。
  • 散列查找的平均查找长度
    • 在散列表中，平均查找长度与装填因子α直接相关，表的查找效率不直接依赖于表中已有表项个数n或表长m。若散列表中存放的记录全部是某个地址的同义词，则平均查找长度为O(n)而非O(1)。
  • 装填因子直接反映的性质
    • 装填因子，一个表的装满程度。装填因子越大，则说明装填的记录就越满，发生冲突的可能性就越大，反之，发生冲突的可能性越小。
  • 评价哈希函数好坏的标准
    • 计算简便、哈希函数取值是否均匀。
  • 分块查找的线性表存储方法
    • 分块查找，又称索引顺序查找，先根据索引查找它所在的块，再在块内进行直接查找，所以线性表必须采用索引存储。
  • 移位折叠法哈希函数
    • 移位折叠指将分割后的每一个部分的最低位对齐，然后相加求和。 例如，设关键字为45207379603，散列地址为3位。因为散列地址为3位，因此将关键字每3位划分一块，叠加后将进位舍去，移位叠加得到的散列地址为324。 
  • 折半查找平均查找长度的近似值
    • log2(n+1)-1
  • KMP算法的思想
    • KMP算法时解决字符串匹配问题的很高效的一种算法，设计思想是当在某一个位置出现不匹配的字符时，应尽量向右移动尽可能大的距离，避免重复比较。具体过程：从主串和模式串（带匹配字符串）的第一个字符开始，依次进行比较，当出现不匹配的字符时，模式串位置向后移动一位，在从模式串的第一个字符开始依次与对应的主串字符比较。重复这个过程直到匹配成功或者未找到匹配位置。
  • 引入B-树的最根本原因
    • 为了减少外搜索的磁盘访问次数，为修改过程提供简单的平衡算法。
  • 查找n个元素的m阶B-树最多外存访问次数
    • 在具有n个关键码的m阶B树中进行搜索时，从根结点到关键码所在结点的路径上所涉及的结点数最多等于树的高度h=1十log┌m/2┐((n十1)/2)，而每访问一个结点最多读1次磁盘，因此读盘次数最多为h。
  • 用静态数组表示串的缺点是
    • 串的最大长度受到限制
  • 索引文件在存储器上的分区
    • 索引文件在存储器上分为索引区和数据区，索引区存放索引表，数据区存放主文件。
  • 带有岗哨的顺序表
    • 带有岗哨的顺序表是一种数据结构，其中“岗哨”是一个特殊的元素或标记，用于指示顺序表的开始或结束。这个岗哨元素通常用于简化某些操作，如插入和删除元素。 在顺序表中，插入和删除操作通常需要移动多个元素以保持表的连续性。然而，通过使用岗哨元素，我们可以在某些情况下避免这种移动。例如，当我们在顺序表的末尾插入一个元素时，我们可以简单地将元素放在岗哨元素之前，而不必移动其他元素。类似地，当我们从顺序表的开头删除一个元素时，我们可以简单地将岗哨元素向前移动一位，同样不需要移动其他元素。 需要注意的是，虽然岗哨元素可以简化某些操作，但它也会增加一些额外的空间开销，因为需要为岗哨元素分配存储空间。此外，使用岗哨元素也需要特别注意边界条件和错误处理，以避免出现意外情况。 总的来说，带有岗哨的顺序表是一种优化数据结构的方法，可以在某些情况下提高插入和删除操作的效率，但也需要权衡空间开销和边界条件处理等因素。
  • 完全避免散列堆积现象的方法
    • 采用直接定址法，直接取关键字的某个线性函数值为散列地址，不会产生冲突，可以完全避免堆积现象。
  • 哈希函数均匀的含义
    • 就是将随机来的关键字按照等概率均匀分配到存储空间中。 实际中，除非知道关键字集合的分布，一般很难到达这个理想状况，只是相对比较均匀一些。
  • 二叉排序树查找失败落在哪种结点
    • 查找失败一定落在外部节点上。
  • 顺序存储器的顺序文件能否进行折半查找
    • 顺序查找法可以在顺序存储结构和链式存储结构上进行，而折半查找只能在可以进行随机存取的存储结构上进行。
  • 分块查找是否适应动态查找
    • 静态查找只查找在查找表中的关键字，若不成功，不插入，动态查找则要插入。分块查找只适合静态查找。 分块查找是一种改进的查找方法，它结合了折半查找和顺序查找的特点。在分块查找中，数据被分成多个块，块内的数据元素可以无序，但块与块之间按照关键字有序排列。这种结构使得分块查找在节点动态变化的情况下具有较好的适应性。 当节点增加或减少，或者节点的关键码发生改变时，只需要将该节点调整到其所在的块即可，而不需要对整个数据集进行重新排序。这种灵活性使得分块查找能够适应动态变化的情况。 然而，虽然分块查找在单个块的更新上具有较好的性能，但如果整个数据集频繁更新，重新划分块可能会导致额外的开销。这是因为每次重新划分块都需要对索引表进行更新和维护，这可能会增加查找操作的复杂性。 因此，虽然分块查找能够适应动态变化的要求，但在整个数据集频繁更新的情况下，其性能可能会受到影响。因此，在某些情况下，分块查找可能不适用于动态查找。
  • m阶B+树每个结点的最少关键字数目
    • m阶B+树除根结点外，每个结点至少应有┌m/2┐个关键字，至多有m个关键字。
  • 倒排文件的作用及其与多重链表文件的区别
    • 倒排文件也是多关键字的多重链表结构，与多重链表文件的主要区别在于次关键字的链表指针信息不是加在数据文件中的每个记录上，而是在每个关键字的索引表中。
  • 分块查找效率最高的方法
    • 设顺序表长度为n，为使查找效率最高，每个索引块的大小应为√(n)，对索引项和索引块内部都采用折半查找，则查找效率最高，比较次数为2┌log₂(√(n)+1)┐。
  • 在散列表中删除元素的注意事项
    • 在开放定址的情况下，不能简单地直接将该元素删除，否则可能导致搜索路径被中断。
  • 采用链地址算法的哈希表插入新数据项的时间如何确定
    • 插入新数据项的时间随装载因子线性增长。
  • 受哈希冲突聚集现象直接影响的性质
    • 降低查找效率，间接影响存储效率，直接影响平均查找长度。

第8章 排序

• 基本概念
  • 排序的引入
    • 在信息处理过程中，最基本的操作是查找。从查找来说，效率最高的是折半查找，折半查找的前提是所有的数据元素（记录）是按关键字有序的。需要将一个无序的数据文件转变为一个有序的数据文件。 将任一文件中的记录通过某种方法整理成为按（记录）关键字有序排列的处理过程称为排序。 排序是数据处理中一种最常用的操作。
  • 排序的概念
    • 排序是将一批（组）任意次序的记录重新排列成按关键字有序的记录序列的过程，其定义为： 给定一组记录序列：{R1, R2, ..., Rn},，其相应的关键字序列是{K1, K2,..., Kn}。确定1,2.... n的一个排列p1, p2, pn，使其相应的关键字满足如下非递减（或非递增）关系：Kp1≤Kp2≤...≤Kpn的序列{Kp1, Kp2, ...,Kpn}，这种操作称为排序。 
  • 排序的基本操作
    • 比较两个关键字的大小； 存储位置的移动：从一个位置移到另一个位置。 第一种操作是必不可少的；而第二种操作却不是必须的，取决于记录的存储方式，具体情况是： ①记录存储在一组连续地址的存储空间：记录之间的逻辑顺序关系是通过其物理存储位置的相邻来体现，记录的移动是必不可少的； ②记录采用链式存储方式：记录之间的逻辑顺序关系是通过结点中的指针来体现，排序过程仅需修改结点的指针，而不需要移动记录；
  • 排序的稳定性
    • 若记录序列中有两个或两个以上关键字相等的记录：Ki=Kj（i≠j, i, j=1, 2, ..., n），且在排序前Ri先于Rj(i<j)，排序后的记录序列仍然是Ri先于Rj，称排序方法是稳定的，否则是不稳定的。 
  • 排序的类型
    • 待排序的记录数量不同，排序过程中涉及的存储器的不同，有不同的排序分类。 ①待排序的记录数不太多：所有的记录都能存放在内存中进行排序，称为内部排序； ②待排序的记录数太多：所有的记录不可能存放在内存中，排序过程中必须在内、外存之间进行数据交换，这样的排序称为外部排序。
  • 排序的性能
    • 评价排序算法的标准有： 执行时间（时间复杂度） 所需的辅助空间（空间复杂度） 算法的稳定性
• 插入类排序
  • 采用的是以“玩桥牌者”的方法为基础的。即在考察记录Ri之前设以前的所有记录R1,R2, ...,Ri-1已排好序，然后将Ri插入到已排好序的诸记录的适当位置。
  • 直接插入排序
    • 排序思想
      • 将待排序的记录Ri，插入到已排好序的记录表R1, R2, ...,Ri-1中，得到一个新的、记录数增加1的有序表。直到所有的记录都插入完为止。 设待排序的记录顺序存放在数组R[1...n]中，在排序的某一时刻，将记录序列分成两部分: R[1...i-1]：已排好序的有序部分； R[i...n]：未排好序的无序部分。 显然，在刚开始排序时，R[1]是已经排好序的。
    • 算法过程
      • 设有关键字序列为：7, 4, -2, 19, 13, 6，直接插入排序的过程如下图所示： 
    • 算法实现
      • void straight_insert_sort(Sqlist *L) { int i, j ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; j=i-1; /*设置哨兵*/ while(L->R[0].key <L->R[ij].key ) { L->R[j+1]=L->R[j]; j--; } /*查找插入位置*/ L->R[j+1]=L->R[0]; /*插入到相应位置*/ }
    • 算法说明
      • 算法中的R[0]开始时并不存放任何待排序的记录，引入的作用主要有两个： ①不需要增加辅助空间：保存当前待插入的记录R[i]，R[i]会因为记录的后移而被占用； ②保证查找插入位置的内循环总可以在超出循环边界之前找到一个等于当前记录的记录，起“哨兵监视”作用，避免在内循环中每次都要判断j是否越界。
    • 算法分析
      • 最好情况
        • 若待排序记录按关键字从小到大排列（正序），算法中的内循环无须执行，则一趟排序时：关键字比较次数1次，记录移动次数2次（R[i]→R[0]，R[0]→R[j+1]）。 则整个排序的关键字比较次数和记录移动次数分别是： 比较次数： 移动次数：
      • 最坏情况
        • 若待排序记录按关键字从大到小排列（逆序），则一趟排序时：算法中的内循环体执行i-1，关键字比较次数i次，记录移动次数i+1。 则就整个排序而言： 比较次数： 移动次数： 一般地，认为待排序的记录可能出现的各种排列的概率相同，则取以上两种情况的平均值，作为排序的关键字比较次数和记录移动次数，约为n²/4，则复杂度为O(n²)。
  • 折半插入排序
    • 当将待排序的记录R[i]插入到已排好序的记录子表R[1...i-1]中时，由于R1, R2, ..., Ri-1已排好序，则查找插入位置可以用“折半查找”实现，则直接插入排序就变成为折半插入排序。
    • 算法过程
      • 设有一组关键字30,13,70,85,39,42,6,20，采用折半插入排序方法排序的过程如图所示： 
    • 算法实现
      • void Binary_insert_sort(Sqlist *L) { int i, j, low, high, mid ; for (i=2; i<=L->length; i++) { L->R[0]=L->R[i]; /*设置哨兵*/ low=1 ; high=i-1 ; while (low< =high) { if (L->R[0].key < L->R[mid].key) high=mid-1 ; else low=mid+1 ; } /*查找插入位置*/ for (j=i-1; j>=high+1; j--) L->R[j+1]=L->R[j]; L->R[high+1]=L->R[0]; /*插入到相应位置 } }
    • 算法分析
      • 从时间上比较，折半插入排序仅仅减少了关键字的比较次数，却没有减少记录的移动次数，故时间复杂度仍然为O(n²)。 要求采用顺序存储
  • 希尔排序（Shell Sort，又称缩小增量法）
    • 是一种分组插入排序方法
    • 排序思想
      • ①先取一个正整数d1(d1<n)作为第一个增量，将全部n个记录分成d1组，把所有相隔d1的记录放在一组中，即对于每个k(k=1,2,...,d1),R[k],R[d1+k], R[2d1+k], ...分在同一组中，在各组内进行直接插入排序。这样次一分组和排序过程称为一趟希尔排序； ②取新的增量d2<d1，重复①的分组和排序操作；直至所取的增量di=1为止，即所有记录放进一个组中排序为止。
    • 排序示例
      • 设有10个待排序的记录，关键字分别为9,13,8,2,5,13,7,1,15,11，增量序列是5,3,1，希尔排序的过程如图所示。 
    • 希尔排序分析
      • 希尔排序特点 子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列。 每一组内采用直接插入排序方法 增量序列取法 无除1以外的公因子； 最后一个增量值必须为1。 ①元素越有序，直接插入排序越快 ②希尔排序是一种分组排序 ③直到最后一个元素排好之前，可能所有元素均未排好。
• 交换类排序
  • 基于交换的排序，系统地交换反序的记录的偶对，直到不再有这样一来的偶对为止。每趟排序必须排好一个元素。
  • 冒泡排序
    • 排序思想
      • 依次比较相邻的两个记录的关键字，若两个记录是反序的（即前一个记录的关键字大于后前一个记录的关键字），则进行交换，直到没有反序的记录为止。 ①首先将L->R[1]与L->R[2]的关键字进行比较，若为反序（L->R[1]的关键字大于L->R[2]的关键字），则交换两个记录；然后比较L->R[2]与L->R[3]的关键字，依此类推，直到L->R[n-1]与L->R[n]的关键字比较后为止，称为一趟冒泡排序，L->R[n]为关键字最大的记录。 ②然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作。 一般地，第i趟冒泡排序是对L->R[1... n-i+1]中的记录进行的，因此，若待排序的记录有n个，则要经过n-1趟冒泡排序才能使所有的记录有序。
    • 排序过程
      • 设有9个待排序的记录，关键字分别为23 38 41 45 23 67 31 15 22，冒泡排序的过程如图所示。 
    • 算法实现
      • void Bubble_Sort(Sqlist *L) { int j ,k , flag ; for (j=0; j<L->length; j++) /*共有n-1趟排序*/ { flag=TRUE; for (k=1; k<=L->length-j; k++) /*一趟排序*/ if (L->R[k+1].key < L->R[k].key ) { flag=FALSE ; L->R[0]=L->R[k]; L->R[k]=L->R[k+1]; L->R[k+1]=L->R[0] ; } if (flag==TRUE) break ; }
    • 算法分析
      • 时间复杂度 最好情况（正序）：比较次数：n-1；移动次数：0； 最坏情况（逆序）： 比较次数： 移动次数： 时间复杂度：T(n)=O(n²) 空间复杂度：S(n)=O(1)
  • 快速排序
    • 排序思想
      • 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，再分别对这两部分记录进行下一趟排序，以达到整个序列有序。
    • 排序过程
      • 设待排序的记录序列是R[s...t]，在记录序列中任取一个记录（一般取R[s]）作为参照（又称为基准或枢轴），以R[s].key为基准重新排列其余的所有记录，方法是： 所有关键字比基准小的放R[s]之前； 所有关键字比基准大的放R[s]之后。 以R[s].key最后所在位置i作为分界，将序列R[s.….t]分割成两个子序列，称为一趟快速排序。
    • —趟快速排序方法
      • 从序列的两端交替扫描各个记录，将关键字小于基准关键字的记录依次放置到序列的前边；而将关键字大于基准关键字的记录从序列的最后端起，依次放置到序列的后边，直到扫描完所有的记录。 设置指针low , high，初值为第1个和最后一个记录的位置。 设两个变量i, j, 初始时令i=low, j=high，以R[low].key作为基准（将R[low]保存在R[0]中）。 ①从j所指位置向前搜索：将R[0].key与R[i].key进行比较： 若R[0].key≤R[j].key：令j=j-1，然后继续进行比较，直到i=j或R[0].key>R[j].key为止； 若R[0].key>R[j].key：R[j]→R[i]，腾空R[j]的位置，且令i=i+1； ②从i所指位置起向后搜索：将R[0].key与R[i].key进行比较： 若R[0].key≥R[i].key：令i=i+1，然后继续进行比较，直到i=j或R[0].key<R[i].key为止； 若R[0].key<R[i].key：R[i]→R[j]，腾空R[i]的位置，且令j=j-1； ③重复①、②，直至i=j为止，i就是R[0]（基准）所应放置的位置。
    • 一趟排序示例
      • 设有6个待排序的记录，关键字分别为29,38,22,45,23,67,31，一趟快速排序的过程如图所示。 
    • 算法实现
      • 一趟快速排序算法的实现
        • int quick_one_pass(Sqlist *L, int low, int high) { int i=low,j=high ; L->R[0]=L->R[i]; /* R[O]作为临时单元和哨兵 */ do { while (L->R[0].key <L->R[lj].key && (j>i)) j--; if (j>i) { L->R[i]=L->R[j] ; i++; } while (L->R[i].key < L->R[0].key && (j>i)) i++; if (j>i) { L->R[j]=L->R[i];j--; } } while(i!=j); /* i=j时退出扫描*/ L->R[i=L->R[0] ; return(i); }
      • 非递归算法
        • #define MAX_STACK 100 void quick_Sort(Sqlist *L ,int low, int high) { int k, stack[MAX_STACK], top=0; do { while (low<high) { k=quick_one_pass(L,low,high); stack[++top]=high ; stack[++top]=k+1 ; /* 第二个子序列的上,下界分别入栈*/ high=k-1 ; } if (top!=0) { low=stack[top--] ; high=stack[top--]; } }while (top!=0&&low<high);}
    • 算法分析
      •  快排的趟数=树高，而且每趟排好的数据，恰好是每层的元素。 2 3 4 5 6 7 8 9 10  单支树 树高=结点数 快速排序的主要时间是花费在划分上，对长度为k的记录序列进行划分时关键字的比较次数是k-1。设长度为n的记录序列进行排序的比较次数为C(n)，则C(n)=n-1+C(k)+C(n-k-1)。 最好情况：每次划分得到的子序列大致相等，则 C(n)≤n+2×C(n/2)+C(n-k-1) ≤n+2×[n/2+ 2×C((n/2)/2)≤ 2n+4×C(n/4) ≤... ≤h×n+2^h×C(n/2^h)，当n/2^h=1时排序结束。即C(n)≤n×log2n+n×C(1)，C(1)看成常数因子，即C(n)≤O(n×log2n)； 最坏情况：每次划分得到的子序列中有一个为空，另一个子序列的长度为n-1。即每次划分所选择的基准是当前待排序序列中的最小（或最大）关键字。 比较次数：  趟数为n，趟内也为n 对于快排来说，元素越有序，其性能越差。 从所需要的附加空间来看，快速排序算法是递归调用，系统内用堆栈保存递归参数，当每次划分比较均匀时，栈的最大深度为[log2n]+1。 其时间、空间与切割是否均匀有关，与处理的先后顺序无关。 当每次划分只能划出一个元素时，所需的栈大小是O(n) 但是呢，平均接近于最好情况 ∴快速排序的空间复杂度是：S(n)=O(log2n)
      • 快速排序中的“趟”
        • 对所有尚未确定最终位置的所有元素进行一遍处理称为“一趟”排序，给定关键字的集合为{20,15,14,18,21,36,40,10} 
• 选择类排序
  • 选择排序（Selection Sort）的基本思想是：每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。
  • 简单选择排序
    • 算法思想
      • 简单选择排序（Simple Selection Sort，又称为直接选择排序）的基本操作是：通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录，然后和第i个记录进行交换，i=1,2,... n-1。 
    • 排序示例
      • 设有关键字序列为：7,4,-2,19,13,6，直接选择排序的过程如下图所示。 
    • 代码实现
      • void simple_selection_sort(Sqlist*L) {int m, n , k; for (m=1; m<L->length; m++) { k=m ; for (n=m+1; n<=L->length; n++) if ( LT(L->R[n].key,L->R[k].key) ) k=n ; if (k!=m) /*记录交换*/ { L->R[0]=L->R[m]; L->R[m]=L->R[k]; L->R[k]=L->R[0]; }}}
    • 算法分析
      • 整个算法是二重循环：外循环控制排序的趟数，对n个记录进行排序的趟数为n-1趟；内循环控制每一趟的排序。 进行第i趟排序时，关键字的比较次数为n-i，则： 比较次数： ∴时间复杂度是：T(n)=O(n²) 空间复杂度是：S(n)=O(1) 从排序的稳定性来看，直接选择排序是不稳定的。
  • 堆排序
    • 堆的定义
      • 是n个元素的序列H={k1, k2, ...,kn}，满足：  由堆的定义知，堆是一棵以k1为根的完全二叉树。若对该二叉树的结点进行编号（从上到下，从左到右），得到的序列就是将二叉树的结点以顺序结构存放，堆的结构正好和该序列结构完全一致。
    • 堆的性质
      • ①堆是一棵采用顺序存储结构的完全二叉树，k1是根结点； ②堆的根结点是关键字序列中的最小（或最大）值，分别称为小（或大）根堆； ③从根结点到每一叶子结点路径上的元素组成的序列都是按元素值（或关键字值）非递减（或非递增）的； ④堆中的任一子树也是堆。 利用堆顶记录的关键字值最小（或最大）的性质，从当前待排序的记录中依次选取关键字最小（或最大）的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。
    • 堆排序思想
      • ①对一组待排序的记录，按堆的定义建立堆； ②将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的； ③堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整（排除）出无序区 ④重复上述步骤，直到全部记录排好序为止。 结论：排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。
      • 堆排序的关键
        • ①如何由一个无序序列建成一个堆？ ②如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？
    • 堆的调整——筛选
      • 输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选”，如图所示。 
    • 复杂度分析
      • 堆排序的比较次数的数量级为：T(n)=O(nlog2n)；而附加空间就是交换时所用的临时空间，故空间复杂度为：S(n)=O(1)。
• 归并类排序
  • 归并（Merging）
    • 是指将两个或两个以上的有序序列合并成一个有序序列。若采用线性表（无论是哪种存储结构）易于实现，其时间复杂度为O(m+n)。
  • 归并思想实例
    • 两堆扑克牌，都已从小到大排好序，要将两堆合并为一堆且要求从小到大排序。 将两堆最上面的抽出（设为C1，C2）比较大小，将小者置于一边作为新的一堆（不妨设C1<C2）；再从第一堆中抽出一张继续与C2进行比较，将较小的放置在新堆的最下面； 重复上述过程，直到某一堆已抽完，然后将剩下一堆中的所有牌转移到新堆中。
  • 排序思想
    • ①初始时，将每个记录看成一个单独的有序序列，则n个待排序记录就是n个长度为1的有序子序列； ②对所有有序子序列进行两两归并，得到n/2个长度为2或1的有序子序列——一趟归并； ③重复②，直到得到长度为n的有序序列为止。 上述排序过程中，子序列总是两两归并，称为2-路归并排序。 其核心是如何将相邻的两个子序列归并成一个子序列。设相邻的两个子序列分别为： {R[k], R[k+1], ..., R[m]}和{R[m+1], R[m+2],..., R[h]}，将它们归并为一个有序的子序列： {DR[l], DR[l+1],..., DR[m], DR[m+1], ...,DR[h] }
  • 归并过程
    • 设有9个待排序的记录，关键字分别为23,38,22,45,23,67,31,15,41,归并排序的过程如图所示。 
    • —趟归并排序
      • 一趟归并排序都是从前到后，依次将相邻的两个有序子序列归并为一个，且除最后一个子序列外，其余每个子序列的长度都相同。设这些子序列的长度为d，则一趟归并排序的过程是： 从j=1开始，依次将相邻的两个有序子序列R[j...j+d-1]和R[j+d...j+2d-1]进行归并；每次归并两个子序列后，j后移动2d个位置，即j=j+2d；若剩下的元素不足两个子序列时，分以下两种情况处理： ①剩下的元素个数>d：再调用一次上述过程，将一个长度为d的子序列和不足d的子序列进行归并； ②剩下的元素个数≤d：将剩下的元素依次复制到归并后的序列中。
  • 算法分析
    • 具有n个待排序记录的归并次数是log2n，而一趟归并的时间复杂度为O(n)，则整个归并排序的时间复杂度无论是最好还是最坏情况均为O(nlog2n)。 在排序过程中，使用了辅助向量DR，大小与待排序记录空间相同则空间复杂度为O(n)。 归并排序是稳定的。
• 基数类排序
  • 基数排序概述
    • 基数排序（Radix Sorting）又称为桶排序或数字排序：按待排序记录的关键字的组成成分（或“位”）进行排序。 基数排序和前面的各种内部排序方法完全不同，不需要进行关键字的比较和记录的移动。借助于多关键字排序思想实现单逻辑关键字的排序。
  • 多关键字排序
    • 
  • 多关键字排序思想
    • 先按第一个关键字K1进行排序，将记录序列分成若干个子序列，每个子序列有相同的K1值；然后分别对每个子序列按第二个关键字K2进行排序，每个子序列又被分成若干个更小的子序列；如此重复，直到按最后一个关键字Kd进行排序。 最后，将所有的子序列依次联接成一个有序的记录序列，该方法称为最高位优先（Most Significant Digit first）。 另一种方法正好相反，排序的顺序是从最低位开始，称为最低位优先（Least Significant Digit first）。
  • 链式基数排序（实现）
    • LSD方法讨论链式基数排序。
    • 排序思想
      • （1）首先以静态链表存储n个待排序记录，头结点指针指向第一个记录结点 （2）一趟排序的过程是： ①分配：按Kd值的升序顺序，改变记录指针，将链表中的记录结点分配到r个链表（桶）中，每个链表中所有记录的关键字的最低位（Kd）的值都相等，用f[i]、e[i]作为第i个链表的头结点和尾结点； ②收集：改变所有非空链表的尾结点指针，使其指向下一个非空链表的第一个结点，从而将r个链表中的记录重新链接成一个链表； （3）如此依次按Kd-1，Kd-2,...K1分别进行，共进行d趟排序后排序完成。
    • 排序示例
      • 设有关键字序列为1039, 2121, 3355, 4382, 66, 118的一组记录，采用链式基数排序的过程如下图所示。  ①升序序列：桶间从小→大回收，桶内按队列回收； ②降序序列：桶间从大→小回收，桶内按队列回收。   
    • 算法分析
      • 设有n个待排序记录，关键字位数为d，每位有r种取值。则排序的趟数是d；在每一趟中： 链表初始化的时间复杂度：O(r)； 分配的时间复杂度：O(n)； ◆分配后收集的时间复杂度：O(r)； 则链式基数排序的时间复杂度为：O(d(n+r)) 在排序过程中使用的辅助空间是：2r个链表指针，n个指针域空间，则空间复杂度为：O(n+r) 基数排序是稳定的。
• 主要内部排序算法的性能
  • 
• 刷题笔记
  • 不同方法排序结果可能不同
    • 使用不同排序方法导致两个相同元素位置不同，亦视为排序结果不同。
  • 能选出一个元素放在最终位置的排序方法
    • 堆排序执行一趟可以直接确定最大值/最小值； 冒泡排序执行一趟可以直接确定最大值/最小值； 直接插入排序不一定会位于最终的位置，因为不确定后面插入的元素对于前面的元素是否产生影响； 快速排序执行一趟可以直接确定枢轴位置。
  • 待排数据已有序反而费时最多的排序法
    • 快速排序的时间复杂度主要取决于枢轴的选取，枢轴越靠近区间中位数，则效率越高。在在待排序的数据已经为有序时，选区的枢轴为区间最小值，效率最低。
  • 排序前已经有序的顺序表比较次数最少的排序方法
    • 直接插入排序的时间主要取决于：新元素与前一个元素比较，新元素较小，则新元素不断前移，产生时间消耗。 而在基本有序的顺序表中，每当接收一个新元素时，新元素都是最大的那一个，不会产生前移耗时。所以在这种情况下，直接插入排序的比较次数极少，耗时极短。
  • 堆排序如何构造初始堆
    • 堆的调整方法，从序列末尾开始向前遍历。
  • 基于比较的排序算法最优情况下的时间复杂度下界
    • 对于n个待排序元素，在未比较时，可能的正确结果有n!种。 在经过一次比较后，其中两个元素的顺序被确定，所以可能的正确结果剩余n!/2种（确定之前两个元素的前后位置的情况是相同，确定之后相当于少了一半的可能性）。 依次类推，直到经过m次比较，剩余可能性n!/(2^m)种。直到n!/(2^m)<=1时，结果只剩余—种。根据斯特灵公式，此时的比较次数m为o(nlogn)次。
  • 对10TB文件排序采用的方法
    • 外部排序指待排序文件较大，内存一次性放不下，需存放在外部介质中。外部排序通常采用归并排序法。
  • 倒排文件的主要优点
    • 通过倒排索引，可以根据单词快速获取包含这个单词的文档列表，大大提高基于非关键码数据项的查找速度。
  • 败者树k路平衡归并外部排序算法总效率与k是否有关
    • 败者树是完全二叉树，因此数据结构可以采用一维数组。其元素个数为k个叶子结点、k-1个比较结点、1个冠军结点共2k个。ls[0]为冠军结点，ls[1]--ls[k-1]为比较结点，Is[k]--ls[2k-1]为叶子结点（同时用另外一个指针索引b[0]--b[k-1]指向）。另外bk为一个附加的辅助空间，不属于败者树，初始化时存着MINKEY的值。其总的归并效率与k无关。
  • 序列建堆调整的起点
    • 必须从N/2开始建堆。
  • 快速排序最易发挥长处的情形
    • 快速排序适用于无序的数据，数据越无序，划分子序列越平均，效率越高。
  • 折半搜索与二叉搜索树的性能对比
    • 折半查找复杂度恒定是log₂(n)，但二叉排序树是最优时间复杂度是log₂(n)，只有平衡二叉树才是恒定的log₂(n)。二叉排序树只有在最优的时候才和折半查找的时间复杂度—样。
  • 快速排序如何减少递归深度
    • 在快速排序中，需要使用递归来分别处理左右子段，递归深度可以理解为系统栈保存的深度，先处理短的分段再处理长的分段，可以减少时间复杂度；如果按长的递归优先的话，那么短的递归会一直保存在栈中，直到长的处理完。短的优先的话，长的递归调用没有进行，他是作为一个整体保存在栈中的，所以递归栈中的保留的递归数据少一些。
  • 部分排序算法的可并行性
    • 基数排序：不需要比较关键字的大小，它是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。不可以并行执行。 快速排序：它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分：分割点左边都是比它小的数，右边都是比它大的数。然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。与归并排序思想有相似之处，可以并行执行。 冒泡排序：它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。不可用并行执行。 堆排序： 1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。可以并行执行。
  • 折半插入和直接插入的主要区别
    • 折半插入排序与直接插入排序都是将待插入元素插入前面的有序子表，区别是：确定当前记录在前面有序子表中的位置时，直接插入排序是采用顺序查找法，而折半插入排序是采用折半查找法。排序的总趟数取决于元素个数n，两者都是n-1趟。元素的移动次数都取决于初试序列，两者相同。使用辅助空间的数量也都是O(1)。折半插入排序的比较次数与序列初态无关，为O(nlog₂n)；而直接插入排序的比较次数与序列初态有关，为O(n)~O(n²)。
  • 外排序归并法的两个阶段
    • ①根据内存缓冲区大小，将外存上的文件分成若干长度为l的子文件，依次读入内存并利用内部排序方法对它们进行排序，并将排序后得到的有序子文件重新写回外存，称这些有序子文件为归并段或顺串。 ②对这些归并段进行逐趟归并，使归并段逐渐由小到大，直至得到整个有序文件为止。
  • 基数排序的两个子过程的名称
    • 基数排序是根据关键字中各位的值，通过对排序的N个元素进行若干趟“分配”与“收集”来实现排序的。基数排序又分为最高位优先（MSD）排序和最低位优先（LSD）排序，LSD的基数排序适用于位数小的数列。设排序的基数为r，那么排序所需要的辅助存储空间为r。
  • 关键字比较次数与初始排列无关的排序算法
    • 在排序算法中，关键字比较次数与初始序列无关的有：简单选择排序、折半插入排序和归并排序。在直接插入排序和冒泡排序中，如果n个序列已经有序，则只需比较n-1次；在快速排序中，如果n个序列基本有序或基本逆序，得到在最坏情况下的时间复杂度O(n²)。
  • 堆排序中对任意分支结点进行筛选运算的时间复杂度
    • 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为O(log₂n)。在正式排序时，n个结点的完全二叉树的深度为└log2 n┘+1，并且有n个数据则需要取n-1次调整成大顶堆的操作，每次调整成大顶堆的时间复杂度为O(log₂n)。因此，重建堆的时间复杂度可近似看做：O(nlog₂n)。
  • 堆排序中构建堆的时间复杂度
    • 堆排序的时间复杂度由构建堆和调整堆两部分组成，总的时间复杂度为O(nlog(n))，构建堆的复杂度为O(n)，故而调整堆的复杂度为O(nlog(n))。
  • 希尔排序优于简单插入排序的原因
    • 希尔排序的每一趟排序都会使整个序列变得更加有序，等整个序列基本有序了，再来一趟直接插入排序，这样会使排序效率更高。
  • 堆采用顺序存储结构的主要原因
    • 顺序存储的特点就是可以随机存取。
  • 采用快速排序算法时对序列进行洗牌操作的目的
    • 防止原始序列接近有序。
  • 直接插入排序算法中监视哨的作用
    • 直接插入排序中，设置监视哨，可以免去判断数组下标是否越界的过程。
  • 磁带文件的两种分类方法
    • 磁带文件分类方法包括平衡归并分类和多阶段归并分类。
  • 堆的存储表示
    • 堆实际上是—种完全二叉树，可以是顺序存储，也可以是链式存储的。
  • 外部排序的选择树方法
    • 利用选择树选择出来后就是将两个长度相当序列合并成一个序列，初始序列长度为m，那么合并之后的平均长度为2m。
  • 外部排序减少归并段的方法与选择树的目的
    • 在外部排序中，为了减少归并段数，采用置换-选择排序进行构建生成初始归并段；而使用选择树法，是为了优化归并，减少I/O次数。
  • 倒排文件和多重表文件的区别
    • 倒排文件和多重表文件的区别在于次关键字索引的结构不同。通常，称倒排文件中的次关键字索引为倒排表，具有相同次关键字的记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这些记录的物理记录号。
  • 堆排序的适用条件
    • 堆排序方法对记录数较少的文件并不值得提倡，但对n较大的文件还是很有效的。因为其运行时间主要耗费在建初始堆和调整建新堆时进行的反复“筛选”上。