杭州哪家网站建设好,网站开发月薪多少钱,行业网站方案,跨境电商平台网站建设广州数据结构知识
绪论
数据结构在学什么 如何用程序代码把现实世界的问题信息化 如何用计算机高效地处理这些信息从而创造价值
数据结构的基本概念
什么是数据#xff1a;
数据是信息的载体#xff0c;是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序…数据结构知识
绪论
数据结构在学什么 如何用程序代码把现实世界的问题信息化 如何用计算机高效地处理这些信息从而创造价值
数据结构的基本概念
什么是数据
数据是信息的载体是描述客观事物属性的数、字符及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据是计算机程序加工的原料。
现代计算机处理的数据 现代计算机——经常处理非数值型问题 对于非数值型的问题 我们关心每个个体的具体信息 我们还关心个体之间的关系
数据元素
数据元素是数据的基本单位通常作为一个整体进行考虑和处理。
数据项
一个数据元素可由若干数据项组成数据项是构成数据元素的不可分割的最小单位。
数据对象
数据对象是具有相同性质的数据元素的集合是数据的一个子集
数据结构 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 数据结构这门课着重关注的是数据元素之间的关系和对这些数据元素的操作而不关心具体的数据项内容。
数据结构的三要素
三要素 逻辑结构 集合结构各个元素同属一个集合别无其他关系 线性结构一对一顺序关系 树状结构一对多 图状结构多对多 数据的运算针对某种逻辑结构结合实际需求定义基本运算增删改查 物理结构储存结构如何用计算机实现这种数据结构 顺序存储把逻辑上相邻的元素存储在物理位置上也相邻的储存单元中元素之间的关系由储存单元的邻接关系来体现 链式存储把逻辑上相邻的元素存储在物理位置上可以不相邻借助指示元素存储地址的指针来表示元素之间的逻辑关系。 索引存储在储存元素信息的同时还简历附加的索引表。索引表中的每项成为索引项索引项的一般形式是关键字地址 散列存储根据元素的关键字直接计算出该元素的存储地址又称哈希存储
总结 若采用顺序存储则各个数据元素在物理上必须是连续的若采用非顺序存储则各个数据元素在物理上可以是离散的 数据的数据结构会影响存储空间分配的方便程度 数据的存储结构会影响对数据运算的速度 运算的定义是针对逻辑结构的指出运算的功能 运算的实现是针对存储结构的指出运算的具体步骤
数据类型
数据类型是一个值的集合和定义在此集合上的一组操作的总称 原子类型其值不可再分的数据类型bool、int等 结构类型其值可以再分解为若干分量的数据类型struct等
抽象数据类型ADT
是抽象数据组织及其相关的操作定义了一个ADT就是在定义一种数据结构
算法的基本概念
什么是算法 程序数据结构算法 算法Algorithm是对特定问题求解步骤的一种描述它是指令的有限序列其中的每条指令表示一个或多个操作
算法的特征 算法必须拥有以下特性否则不能被称为算法 有穷性一个算法必须总在执行有穷步之后结束且每一步都可在有穷时间内完成。 确定性算法中每条指令必须有确切的含义对于相同的输入只能得出相同的输出。 可行性算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。 输入一个算法有零个或多个输入这些输入取自于某个特定的对象的集合。 输出一个算法有一个或多个输出这些输出是与输入有着某种特定关系的量。
好算法的特质 正确性算法应能够正确地解决求解问题。 可读性算法应具有良好的可读性以帮助人们理解。 健壮性输入非法数据时算法能适当地做出反应或进行处理而不会产生莫名其妙的输出结果。 高效率 花的时间少时间复杂度低 低存储量需求费内存空间复杂度低
算法的时间复杂度
定义 事前预估算法时间开销T(n)与问题规模n的关系T表示“time”
规则 加法规则T(n) T1(n) T2(n) O(f(n)) O(g(n)) O(max(f(n), g(n))) 多项相加只保留最高阶的项且系数变为1 乘法规则T(n) T1(n)×T2(n) O(f(n))×O(g(n)) O(f(n)×g(n))多项相乘都保留 算法好坏O(1) O(log2n) O(n) O(nlog2n) O(n^2) O(n^3) O(2^n) O(n!) O(n^n)口诀常对幂指阶 数量级仅需考虑循环内最深层嵌套的部分 最坏时间复杂度最坏情况下算法的时间复杂度 平均时间复杂度所有输入示例等概率出现的情况下算法的期望运行时间 最好时间复杂度最好情况下算法的时间复杂度 一般只考虑最坏和平均复杂度
算法的空间复杂度
定义空间开销内存开销S(n)与问题规模n之间的关系
算法原地工作 算法所需内存空间为常量
规则 只需关注存储空间大小与问题规模相关的变量 加法规则、乘法规则、算法好坏判定与时间复杂度一样 递归调用的大多数情况空间复杂度递归调用的深度
线性表
线性表的定义和基本操作
定义 线性表(Linear List)是具有相同数据类型的nn≥0个数据元素的有限序列其中n为表长当n 0时线性表是一个空表 若用L命名线性表则其一般表示为L (a1, a2, … , ai, ai1, … , an) a1是表头元素 an是表尾元素 除第一个元素外每个元素有且仅有一个直接前驱 除最后一个元素外每个元素有且仅有一个直接后继
基本操作 InitList(L)初始化表。构造一个空的线性表L分配内存空间。 DestroyList(L)销毁操作。销毁线性表并释放线性表L所占用的内存空间。 ListInsert(L,i,e)插入操作。在表L中的第i个位置上插入指定元素e。 ListDelete(L,i,e)删除操作。删除表L中第i个位置的元素并用e返回删除元素的值。 LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素。 GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值。 Length(L)求表长。返回线性表L的长度即L中数据元素的个数。 PrintList(L)输出操作。按前后顺序输出线性表L的所有元素值。 Empty(L)判空操作。若L为空表则返回true否则返回false。 什么时候要传入参数的引用“” 对参数的修改结果需要“带回来”是引用类型而不是值类型
顺序表的定义
定义
用顺序存储的方式实现线性表顺序存储把逻辑上相邻的元素存储在物理位置上也相邻的存储单元中元素之间的关系由存储单元的邻接关系来体现。
如何知道一个数据元素大小
C语言sizeof(ElemType)
顺序表的实现-静态分配 如果“数组”存满了怎么办
可以放弃治疗顺序表的表长刚开始确定后就无法更改存储空间是静态的同时如果提前初始化太多的空间而不用又会造成资源的浪费因此动态分配应运而生。
动态申请和释放内存空间 Cmalloc、free函数 L.data (ElemType *) malloc (sizeof(ElemType) * InitSize); malloc函数返回一个指针 空间需要强制转型为你定义的数据元素类型指针 malloc函数的参数指明要分配多大的连续内存空间 C new、delete关键字
顺序表的实现-动态分配 顺序表的实现 随机访问即可以在O(1)时间内找到第i个元素。 存储密度高每个结点只存储数据元素 拓展容量不方便即便采用动态分配的方式实现拓展长度的时间复杂度也比较高 插入、删除操作不方便需要移动大量元素
顺序表的插入、删除
顺序表的基本操作-插入 增加i的合法性判断 顺序表的基本操作-删除 插入和删除的时间复杂度 最好时间复杂度 O(1) 最坏时间复杂度 O(n) 平均时间复杂度 O(n)
顺序表的查找
顺序表的按位查找 正是如此在初始化顺序表时候malloc需要强制转换为与数据元素的数据类型相对应的指针 时间复杂度 O(1) 随机存取由于顺序表的各个数据元素在内存中连续存放因此可以根据起始地址和数据元素大小立即找到第i个元素
顺序表的按值查找 结构类型的数据元素也能用 比较吗不能C可以用 的重载来实现 更好的办法定义一个函数 依次对比各个分量来判断两个结构体是否相等 最好时间复杂度 O(1) 最坏时间复杂度 O(n) 平均时间复杂度 O(n)
单链表的定义
顺序表 每个结点中只存放数据元素 优点可随机存取存储密度高 缺点要求大片连续空间改变容量不方便
单链表 每个结点除了存放数据元素外还要存储指向下一个结点的指针 优点不要求大片连续空间改变容量方便 缺点不可随机存取要耗费一定空间存放指针
定义一个单链表 typedef关键字数据类型重命名 typedef 数据类型 别名 typedef struct LNode LNode; 之后可以用LNode代替struct LNode 不带头结点的单链表 带头结点的单链表 区别 不带头结点写代码更麻烦 对第一个数据结点和后续数据结点的处理需要用不同的代码逻辑 对空表和非空表的处理需要用不同的代码逻辑 我们一般使用的都是带头结点的单链表
单链表的插入、删除
按位序插入带头结点
ListInsert(L,i,e) 插入操作在表L中的第i个位置上插入指定元素e 找到第i-1个结点将新结点插入其后 若带有头结点插入更加方便头结点可以看作“第0个”结点直接做上面的操作即可 若i插在表中则与插在表头一样进行操作可以插入成功 若i插在表尾则s-next为NULL在表的定义时规定的可以插入成功 若i插在表外iLengh则p指针指向NULLWhile循环一直指向p-next不能插入成功 最好时间复杂度 O(1) 最坏时间复杂度 O(n) 平均时间复杂度 O(n)
按位序插入不带头结点
ListInsert(L,i,e) 插入操作在表L中的第i个位置上插入指定元素e 不存在“第0个”结点因此i1时需要特殊处理 找到第i-1个结点将新结点插入其后 若i!1则处理方法和带头结点一模一样 值得注意的是int j 1而非带头结点的0带头结点的头结点为第0个结点 结论不带头结点写代码更不方便推荐用带头结点
指定结点的后插操作 这一段代码是按位序插入中插入的那一部分代码 也可以直接调用InsertNextNode来执行 封装代码以此提高代码复用性让代码更容易维护
指定结点的前插操作 因为仅知道指定结点的信息和后继结点的指向因此无法直接获取到前驱结点 方法1获取头结点然后再一步步找到指定结点的前驱 方法2将新结点先连上指定结点p的后继接着指定结点p连上新结点s将p中元素复制到s中将p中元素覆盖为要插入的元素e 方法1 方法2
按位序删除带头结点
ListDelete(L,i,e) 删除操作删除表L中第i个位置的元素并用e返回删除元素的值。 找到第i-1个结点将其指针指向第i1个结点并释放第i个结点 指定结点的删除 删除结点p需要修改其前驱结点的next指针和指定结点的前插操作一样 方法1传入头指针循环寻找p的前驱结点 方法2偷天换日类似于结点前插的实现 方法2
如果要删除的结点p是最后一个结点 只能从表头开始依次寻找p的前驱时间复杂度O(n) 这就体现了单链表的局限性无法逆向检索有时候不太方便 单链表的查找
按位查找 GetElem(L,i)按位查找操作。获取表L中第i个位置的元素的值。 实际上单链表的插入中找到i-1部分就是按位查找i-1个结点如下图 因此查找第i个结点如下图 如果i0则直接不满足ji则指针p直接返回头结点L 如果i超界则当时p指向了NULL指针p返回NULL 平均时间复杂度O(n)
按值查找
LocateElem(L,e)按值查找操作。在表L中查找具有给定关键字值的元素。 能找到的情况p指向了e值对应的元素返回该元素 不能找到的情况p指向了NULL指针p返回NULL 平均时间复杂度O(n)
求表的长度 平均时间复杂度O(n)
单链表的建立
尾插法 每次插入元素都插入到单链表的表尾 方法1套用之前学过的位序插入每次都要从头开始往后面遍历时间复杂度为O(n^2) 方法2增加一个尾指针r每次插入都让r指向新的表尾结点时间复杂度为O(n) 头插法 每次插入元素都插入到单链表的表头 头插法和之前学过的单链表后插操作是一样的可以直接套用 L-nextNULL;可以防止野指针 总结 头插法、尾插法核心就是初始化操作、指定结点的后插操作 注意设置一个指向表尾结点的指针 头插法的重要应用链表的逆置
双链表
为什么要要使用双链表 单链表无法逆向检索有时候不太方便 双链表可进可退但是存储密度更低一丢丢 双链表的初始化带头结点 双链表的插入 小心如果p结点为最后一个结点产生的空指针问题因此循环链表应运而生详见后面的循环链表插入删除 注意指针的修改顺序
双链表的删除 双链表的遍历 循环链表
循环单链表与单链表的区别
单链表 表尾结点的next指针指向NULL 从一个结点出发只能找到后续的各个结点
循环单链表 表尾结点的next指针指向头结点 从一个结点出发可以找到其他任何一个结点
循环单链表初始化 从头结点找到尾部时间复杂度为O(n) 如果需要频繁的访问表头、表尾可以让L指向表尾元素插入、删除时可能需要修改L 从尾部找到头部时间复杂度为O(1)
循环双链表与双链表的区别
双链表 表头结点的prior指向NULL 表尾结点的next指向NULL
循环双链表 表头结点的prior指向表尾结点 表尾结点的next指向头结点
循环双链表的初始化 循环链表的插入 对于双链表来说如果p结点为最后一个结点因为next结点为nullp-next-priors会产生的空指针问题 循环链表规避因为最后结点的next结点为头结点因此不会发生问题 循环链表的删除
与循环链表的插入相同。 注意点
写代码时候注意以下几点以此规避错误 如何判空 如何判断结点p是否是表尾/表头元素后向/前向遍历的实现核心 如何在表头、表中、表尾插入/删除一个结点
静态链表
什么是静态链表 分配一整片连续的内存空间各个结点集中安置 每个结点由两部分组成data数据元素和next游标 0号结点充当“头结点”不具体存放数据 游标为-1表示已经到达表尾 游标充当“指针”表示下个结点的存放位置下面举一个例子 每个数据元素4B每个游标4B每个结点共8B设起始地址为addre1的存放地址为addr 8*2游标值
定义静态链表
方法1 方法2 基本操作
初始化 把a[0]的next设为-1 把其他结点的next设为一个特殊值用来表示结点空闲如-2
插入位序为i的结点 找到一个空的结点存入数据元素设为一个特殊值用来表示结点空闲如-2 从头结点出发找到位序为i-1的结点 修改新结点的next 修改i-1号结点的next
删除某个结点 从头结点出发找到前驱结点 修改前驱结点的游标 被删除结点next设为-2
总结 静态链表用数组的方式实现的链表 优点增、删操作不需要大量移动元素 缺点不能随机存取只能从头结点开始依次往后查找容量固定不可变 适用场景①不支持指针的低级语言②数据元素数量固定不变的场景如操作系统的文件分配表FAT
顺序表和链表的比较
逻辑结构
都属于线性表都是线性结构
存储结构
顺序表 优点支持随机存取、存储密度高 缺点大片连续空间分配不方便改变容量不方便
链表 优点离散的小空间分配方便改变容量方便 缺点不可随机存取存储密度低
基本操作
顺序表 创建 需要预分配大片连续空间。 若分配空间过小则之后不方便拓展容量 若分配空间过大则浪费内存资源 静态分配静态数组实现容量不可改变 动态分配动态数组malloc、free实现容量可以改变但需要移动大量元素时间代价高 销毁 修改Length 0 静态分配静态数组系统自动回收空间 动态分配动态数组malloc、free需要手动free 增删 插入/删除元素要将后续元素都后移/前移 时间复杂度O(n)时间开销主要来自移动元素 若数据元素很大则移动的时间代价很高 查 按位查找O(1) 按值查找O(n)若表内元素有序可在O(log2n)时间内找到
链表 创建 只需分配一个头结点也可以不要头结点只声明一个头指针之后方便拓展 销毁 依次删除各个结点free 增删 插入/删除元素只需修改指针即可 时间复杂度O(n)时间开销主要来自查找目标元素 查找元素的时间代价更低 查 按位查找O(n) 按值查找O(n)
用哪个 表长难以预估、经常要增加/删除元素——链表 表长可预估、查询搜索操作较多——顺序表
开放式问题的解题思路
问题 请描述顺序表和链表的bla bla bla…实现线性表时用顺序表还是链表好
答案 顺序表和链表的逻辑结构都是线性结构都属于线性表。 但是二者的存储结构不同顺序表采用顺序存储…(特点带来的优点缺点)链表采用链式存储…特点、导致的优缺点。 由于采用不同的存储方式实现因此基本操作的实现效率也不同。 当初始化时…当插入一个数据元素时…当删除一个数据元素时…当查找一个数据元素时…
栈和队列
栈的基本概念
栈的定义 栈Stack是只允许在一端进行插入或删除操作的线性表 逻辑结构与普通线性表相同 数据的运算插入、删除操作有区别 栈顶允许插入和删除的一端对应元素被称为栈顶元素 栈底不允许插入和删除的一端对应元素被称为栈底元素 特点后进先出Last In First OutLIFO
栈的基本操作 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数可采用数学归纳法证明
栈的顺序存储结构
顺序栈的定义和初始化 进栈操作 出栈操作 读取栈顶元素 注意也可以让栈顶指针top先指向0每次进栈S.top出栈–S.top
共享栈 使用静态数组要求提前规定好栈的大小容易造成内存资源的浪费因此共享栈应运而生 两个栈共享同一片空间0、1号栈朝着同一方向进栈 栈满的条件top0 1 top1 栈的链式存储结构
栈的链式存储实质 进栈头插法建立单链表也就是对头结点的后插操作 出栈单链表的删除操作对头结点的“后删”操作 推荐使用不带头结点的链栈 创销增删查的操作参考链表
链栈的定义 队列的基本概念
队列的定义 栈Stack是只允许在一端进行插入或删除操作的操作受限的线性表 队列Queue是只允许在一端进行插入在另一端删除的线性表 队头允许删除的一端对应的元素被称为队头元素 队尾允许插入的一端对应的元素被称为队尾元素 队列的特点先进先出First In First OutFIFO
队列的基本操作 InitQueue(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。
队列的顺序存储结构
队列的定义和初始化 入队操作 通过取余操作只要队列不满就可以一直利用之前已经出队了的空间逻辑上实现了循环队列的操作 于是队列已满的条件队尾指针的再下一个位置是队头即(Q.rear1)%MaxSizeQ.front 代价牺牲了一个存储单元因为如果rear和front相同与判空的条件相同了
出队操作 实际上获取队头元素的值就是出队操作去掉队头指针后移的代码
判断队列已满/已空
方案1 使用前面讲的牺牲一个存储空间的方式来解决 初始化时rearfront0 队列元素个数(rearMaxSize-front)%MaxSize 队列已满的条件队尾指针的再下一个位置是队头即(Q.rear1)%MaxSizeQ.front 队空条件Q.rearQ.front
方案2 不牺牲一个存储空间在结构体中多建立一个变量size 初始化时rearfront0size 0; 队列元素个数 size 插入成功size删除成功size–; 此时队满条件sizeMaxSize 队空条件size 0;
方案3 不牺牲一个存储空间在结构体中多建立一个变量tag 初始化时rearfront0tag 0; 因为只有删除操作才可能导致队空只有插入操作才可能导致队满因此 每次删除操作成功时都令tag0 每次插入操作成功时都令tag1 队满条件frontrear tag 1 队空条件frontrear tag 0 队列元素个数(rearMaxSize-front)%MaxSize
队列的链式存储结构
初始化带头结点 初始化不带头结点 入队带头结点 入队不带头结点 出队带头结点 出队不带头结点 队列满的条件 顺序存储预分配的空间耗尽时队满 链式存储一般不会队满除非内存不足 因此一般不用考虑队满
双端队列
定义 双端队列只允许从两端插入、两端删除的线性表 输入受限的双端队列只允许从一端插入、两端删除的线性表 输出受限的双端队列只允许从两端插入、一端删除的线性表 不管是怎么样的双端队列实际都是栈和队列的变种
考点 判断输出序列合法性 在栈中合法的输出序列在双端队列中必定合法
栈在括号匹配中的应用
括号匹配问题 若有括号无法被匹配则出现编译错误 遇到左括号就入栈 遇到右括号就“消耗”一个左括号
代码实现 栈在表达式求值中的应用
算数表达式 由三个部分组成操作数、运算符、界限符 我们平时写的算术表达式都是中缀表达式 如何可以不用界限符也能无歧义地表达运算顺序 Reverse Polish notation逆波兰表达式后缀表达式 Polish notation波兰表达式前缀表达式
中缀、后缀、前缀表达式 中缀转后缀的方法手算 确定中缀表达式中各个运算符的运算顺序 选择下一个运算符按照「左操作数右操作数运算符」的方式组合成一个新的操作数 如果还有运算符没被处理就继续第二步 注意运算顺序不唯一因此对应的后缀表达式也不唯一 “左优先”原则只要左边的运算符能先计算就优先算左边的保证手算和机算是一致的 中缀表达式转后缀表达式机算用栈实现 初始化一个栈用于保存暂时还不能确定运算顺序的运算符。 从左到右处理各个元素直到末尾。可能遇到三种情况 遇到操作数。直接加入后缀表达式。 遇到界限符。遇到“(”直接入栈遇到“)”则依次弹出栈内运算符并加入后缀表达式直到弹出“(”为止。注意“(”不加入后缀表达式。 遇到运算符。依次弹出栈中优先级高于或等于当前运算符的所有运算符并加入后缀表达式若碰到“(”或栈空则停止。之后再把当前运算符入栈。 按上述方法处理完所有字符后将栈中剩余运算符依次弹出并加入后缀表达式。
后缀表达式的计算手算 从左往右扫描每遇到一个运算符就让运算符前面最近的两个操作数执行对应运算合体为一个操作数 注意两个操作数的左右顺序 特点最后出现的操作数先被运算LIFO后进先出可以使用栈来完成这个步骤 “左优先”原则只要左边的运算符能先计算就优先算左边的
后缀表达式的计算机算用栈实现 从左往右扫描下一个元素直到处理完所有元素 若扫描到操作数则压入栈并回到第一步否则执行第三步 若扫描到运算符则弹出两个栈顶元素执行相应运算运算结果压回栈顶回到第一步 注意先出栈的是“右操作数” 若表达式合法则最后栈中只会留下一个元素就是最终结果 后缀表达式适用于基于栈的编程语言stack-orientedprogramming language如Forth、PostScript
中缀表达式转前缀表达式手算 确定中缀表达式中各个运算符的运算顺序 选择下一个运算符按照「运算符左操作数右操作数」的方式组合成一个新的操作数 如果还有运算符没被处理就继续第二步 “右优先”原则只要右边的运算符能先计算就优先算右边的
中缀表达式的计算机算用栈实现 中缀表达式的计算中缀转后缀后缀表达式求值两个算法的结合 用栈实现中缀表达式的计算 初始化两个栈操作数栈和运算符栈 若扫描到操作数压入操作数栈 若扫描到运算符或界限符则按照“中缀转后缀”相同的逻辑压入运算符栈期间也会弹出运算符每当弹出一个运算符时就需要再弹出两个操作数栈的栈顶元素并执行相应运算运算结果再压回操作数栈
栈在递归中的应用
函数调用的特点 最后被调用的函数最先执行结束LIFO 函数调用时需要用一个栈函数调用栈存储里面包含以下信息 调用返回地址 实参 局部变量 适合用“递归”算法解决可以把原始问题转换为属性相同但规模较小的问题
栈在递归中的应用 计算正整数的阶乘n! 求斐波那契数列 …
栈在递归中过程 递归调用时函数调用栈可称为“递归工作栈” 每进入一层递归就将递归调用所需信息压入栈顶 每退出一层递归就从栈顶弹出相应信息 缺点 太多层递归可能会导致栈溢出 可能包含很多重复计算
队列的应用 树的层次遍历 图的广度优先遍历 操作系统中的应用 多个进程争抢着使用有限的系统资源时FCFSFirst Come First Service先来先服务是一种常用策略。可以用队列实现 CPU资源的分配 打印数据缓冲区
特殊矩阵的压缩储存
一维数组的存储结构 起始地址LOC 各数组元素大小相同且物理上连续存放。 数组元素a[i]的存放地址 LOC i * sizeof(ElemType)
二维数组的存储结构 分为行优先和列优先本质就是把二维的逻辑视角转换为内存中的一维储存 M行N列的二维数组b[M][N]中若按行优先存储则b[i][j]的存储地址 LOC (i*N j) * sizeof(ElemType) M行N列的二维数组b[M][N]中若按列优先存储则b[i][j]的存储地址 LOC ( j*M i ) * sizeof(ElemType) 二维数组也有随机存储的特性
普通矩阵的存储 可用二维数组存储 注意描述矩阵元素时行、列号通常从1开始而描述数组时通常下标从0开始 某些特殊矩阵可以压缩存储空间比如对称矩阵
对称矩阵的压缩存储 若n阶方阵中任意一个元素ai,j都有ai,j aj,i则该矩阵为对称矩阵 普通存储n*n二维数组 压缩存储策略只存储主对角线下三角区或主对角线上三角区按行优先原则将各元素存入一维数组中 数组大小应为多少(1n)*n/2 站在程序员的角度对称矩阵压缩存储后怎样才能方便使用可以实现一个“映射”函数矩阵下标-一维数组下标 按行优先的原则ai,j是第几个元素 三角矩阵的压缩存储 下三角矩阵除了主对角线和下三角区其余的元素都相同 上三角矩阵除了主对角线和上三角区其余的元素都相同 压缩存储策略按行优先原则将橙色区元素存入一维数组中并在最后一个位置存储常量c 下三角矩阵按行优先的原则ai,j是第几个元素 上三角矩阵按行优先的原则ai,j是第几个元素 三对角矩阵的压缩存储 三对角矩阵又称带状矩阵当|i - j|1时有ai,j 0 1≤ i, j ≤n 压缩存储策略按行优先或列优先原则只存储带状部分 按行优先的原则ai,j是第几个元素 稀疏矩阵的压缩存储 稀疏矩阵非零元素远远少于矩阵元素的个数 压缩存储策略1顺序存储——三元组i行j列v值失去了数组随机存储的特性 压缩存储策略2链式存储十字链表法 串
串的定义和基本操作
定义 串即字符串String是由零个或多个字符组成的有限序列。一般记为S ‘a1a2······an’ n ≥0 其中S是串名单引号括起来的字符序列是串的值ai可以是字母、数字或其他字符串中字符的个数n称为串的长度。n 0时的串称为空串用∅表示。 有的地方用双引号如Java、C有的地方用单引号如Python 例如S”HelloWorld!”T‘iPhone 11 Pro Max?’ 子串串中任意个连续的字符组成的子序列。Eg’iPhone’’Pro M’是串T的子串 主串包含子串的串。EgT是子串’iPhone’的主串 字符在主串中的位置字符在串中的序号。Eg’1’在T中的位置是8(第一次出现) 子串在主串中的位置子串的第一个字符在主串中的位置。Eg’11 Pro’在T中的位置为8 每个空格字符占1B不是空串 串的位序从1开始而不是从0开始 串是一种特殊的线性表数据元素之间呈线性关系 串的数据对象限定为字符集如中文字符、英文字符、数字字符、标点字符等 串的基本操作如增删改查等通常以子串为操作对象因为人类的语言通常要多个字符组成的序列才有现实意义
串的基本操作 假设有串T“”S”iPhone 11 Pro Max?”W“Pro” StrAssign(T,chars)赋值操作。把串T赋值为chars。 StrCopy(T,S)复制操作。由串S复制得到串T。 StrEmpty(S)判空操作。若S为空串则返回TRUE否则返回FALSE。 StrLength(S)求串长。返回串S的元素个数。 ClearString(S)清空操作。将S清为空串。 DestroyString(S)销毁串。将串S销毁回收存储空间。 Concat(T,S1,S2)串联接。用T返回由S1和S2联接而成的新串 SubString(Sub,S,pos,len)求子串。用Sub返回串S的第pos个字符起长度为len的子串。 Index(S,T)定位操作。若主串S中存在与串T值相同的子串则返回它在主串S中第一次出现的位置否则函数值为0。 StrCompare(S,T)比较操作。若ST则返回值0若ST则返回值0若ST则返回值0。 从第一个字符开始往后依次对比先出现更大字符的串就更大 长串的前缀与短串相同时长串更大 只有两个串完全相同时才相等
字符集编码 任何数据存到计算机中一定是二进制数。 需要确定一个字符和二进制数的对应规则这就是“编码” “字符集”英文字符ASCII字符集中英文Unicode字符集 基于同一个字符集可以有多种编码方案如UTF-8UTF-16 注采用不同的编码方式每个字符所占空间不同考研中只需默认每个字符占1B即可
串的储存结构
顺序存储 方案一一个数组来储存字符一个int变量length储存实际长度 方案二数组的ch[0]来充当length优点字符的位序和数组下标相同 方案三没有Length变量以字符’\0’表示结尾对应ASCII码的0缺点获取字符串长度需要遍历时间复杂度高 方案四数组的ch[0]废弃不用从看开始储存字符外加一个int变量length储存实际长度
链式存储 推荐使用第二种方式存储密度较高ch数组未必一定是4个字符也可以比4多
基本操作的实现使用第四种方案 朴素模式匹配算法
字符串模式匹配 在主串中找到与模式串相同的子串并返回其所在位置。 子串主串的一部分一定存在 模式串不一定能在主串中找到 要掌握朴素模式匹配算法、KMP算法两种方法
朴素模式匹配算法两种实现方法 将主串中所有长度为m的子串依次与模式串对比直到找到一个完全匹配的子串或所有的子串都不匹配为止。 主串长度为n模式串长度为 m最多对比 n-m1 个子串 上节讲的index定位操作就是朴素模式匹配算法中其中一种实现方法 也可以使用两个指针i和j来进行匹配。若当前子串匹配失败则主串指针 i 指向下一个子串的第一个位置模式串指针 j 回到模式串的第一个位置即i i - j 2; j 1; 若 j T.length则当前子串匹配成功返回当前子串第一个字符的位置即i - T.length 设主串长度为 n模式串长度为 m则最坏时间复杂度 O(n*m)最好时间复杂度 O(n)
KMP算法的概念 由D.E.KnuthJ.H.Morris和V.R.Pratt提出因此称为 KMP算法 是对朴素模式匹配算法的优化 优化的原理就是减少了i指针的回溯通过已经计算好的next指针提高算法的整体运行效率 next数组记录了当第几个元素匹配失败时候j的取值例如 对于模式串 T ‘abaabc’ 当第6个元素匹配失败时可令主串指针 i 不变模式串指针 j3 当第5个元素匹配失败时可令主串指针 i 不变模式串指针 j2 当第4个元素匹配失败时可令主串指针 i 不变模式串指针 j2 当第3个元素匹配失败时可令主串指针 i 不变模式串指针 j1 当第2个元素匹配失败时可令主串指针 i 不变模式串指针 j1 当第1个元素匹配失败时匹配下一个相邻子串令 j0, i, j next数组只和短短的模式串有关和长长的主串无关重要 之所以只和模式串有关是因为如果在哪里匹配失败同时说明在这之前的部分主串和模式串是相同的 KMP算法最坏时间复杂度 O(mn)其中求 next 数组时间复杂度 O(m)模式匹配过程最坏时间复杂度 O(n) KMP算法精髓利用好已经匹配过的模式串的信息 步骤 根据模式串T求出 next 数组 利用next数组进行匹配主串指针不回溯 KMP算法之求next数组
next数组的作用
当模式串的第 j 个字符失配时从模式串的第 next[j] 的继续往后匹配
next数组的求法 任何模式串都一样第1个字符不匹配时只能匹配下一个子串因此next[1]都无脑写 0if(j0) {i; j;} 任何模式串都一样第2个字符不匹配时应尝试匹配模式串的第1个字符因此next[2]都无脑写 1 每一个模式串不一样对于第3个字符及之后的字符串在不匹配的位置前边划一根美丽的分界线模式串一步一步往后退直到分界线之前“能对上”此时 j 指向哪儿next数组值就是多少
KMP算法之求nextval数组
定义
nextval数组是对next数组的优化用nextval替代next数组减少了无意义的对比
nextval数组的求法 先根据上面的方法算出next数组 先令nextval[1]0 再根据下面代码算出后面的nextval数组
for(int j 2; j T.length; j) { //让第next值个元素的值和当前元素比较 if(T.ch[next[j]] T.ch[j]) { //若相等则让第next值个元素的nextval值复制给当前元素的nextval值 nextval[j] nextval[next[j]]; } else { //若不等则让当前元素的next值赋值给当前元素的nextval值 nextval[j] next[j]; } }
树
树的定义和基本术语
空树
结点数为0的树
非空树的特性 有且仅有一个根结点 没有后继的结点称为“叶子结点”或终端结点 有后继的结点称为“分支结点”或非终端结点 除了根结点外任何一个结点都有且仅有一个前驱 每个结点可以有0个或多个后继
树的定义 树是nn≥0个结点的有限集合n 0时称为空树这是一种特殊情况。 在任意一棵非空树中应满足 有且仅有一个特定的称为根的结点。 当n 1时其余结点可分为mm 0个互不相交的有限集合T1, T2,…, Tm其中每个集合本身又是一棵树并且称为根结点的子树。
结点之间的关系描述 什么是祖先结点比自己深度低的结点 什么是子孙结点比自己深度高的结点 什么是双亲结点父结点自己的根结点 什么是孩子结点自己作为根结点的儿子 什么是兄弟结点与自己拥有相同父结点结点 什么是堂兄弟结点与自己同一层的结点 什么是两个结点之间的路径能从上往下前往的两个结点被称为有路径 什么是路径长度经过几条边
结点、树的属性描述 结点的层次深度从上往下数默认从1开始 结点的高度从下往上数 树的高度深度总共多少层 结点的度有几个孩子分支 树的度各结点的度的最大值
有序数和无序树 有序树逻辑上看树中结点的各子树从左至右是有次序的不能互换 无序树逻辑上看树中结点的各子树从左至右是无次序的可以互换 是否是什么具体看你用树存什么是否需要用结点的左右位置反映某些逻辑关系
树和森林 森林是mm≥0棵互不相交的树的集合 考点树和森林的相互转换
树的性质 树的总结点数树的总度数1 度数为m的树和m叉树的区别 度为m的树第i 层至多有m^i-1 个结点i≥1 m叉树第i 层至多有m^i-1 个结点i≥1 高度为h的m叉树至多有((m^h)-1)/m-1个结点 高度为h的m叉树至少有h 个结点 高度为h、度为m的树至少有hm-1 个结点 具有n个结点的m叉树的最小高度为logm(n(m - 1) 1) 高度最小的情况所有结点都有m个孩子
二叉树的定义和基本术语
定义 二叉树是nn≥0个结点的有限集合 或者为空二叉树即n 0。 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。 特点 每个结点至多只有两棵子树 左右子树不能颠倒二叉树是有序树
二叉树的五种状态 空二叉树 只有左子树 只有右子树 只有根结点 左右子树都有
几个特殊的二叉树 满二叉树一棵高度为h且含有2^h - 1个结点的二叉树 特点 只有最后一层有叶子结点 不存在度为1 的结点 按层序从1 开始编号结点i 的左孩子为2i右孩子为2i1结点i 的父结点为/2 如果有的话 完全二叉树当且仅当其每个结点都与高度为h的满二叉树中编号为1n的结点一一对应时称为完全二叉树 特点 只有最后两层可能有叶子结点 最多只有一个度为1的结点 按层序从1 开始编号结点i 的左孩子为2i右孩子为2i1结点i 的父结点为/2 如果有的话 i≤ n/2 为分支结点 i n/2 为叶子结点 如果某结点只有一个孩子那么一定是左孩子 是满二叉树一定是完全二叉树是完全二叉树不一定是满二叉树 二叉排序树一棵二叉树或者是空二叉树或者是具有如下性质的二叉树 左子树上所有结点的关键字均小于根结点的关键字 右子树上所有结点的关键字均大于根结点的关键字 左子树和右子树又各是一棵二叉排序树 二叉排序树可用于元素的排序、搜索 平衡二叉树树上任一结点的左子树和右子树的深度之差不超过1。 平衡二叉树能有更高的搜索效率 又宽又胖的树
各种二叉树的性质
二叉树的性质 设非空二叉树中度为0、1和2的结点个数分别为n0、n1和n2则n0 n2 1叶子结点比二分支结点多一个 二叉树第i 层至多有2^(i-1)个结点i≥1 高度为h的2叉树至多有(2^h)-1个结点满二叉树
完全二叉树的性质 具有n个n0结点的完全二叉树的高度h为log2(n 1) 或[log2n] 1 对于完全二叉树可以由的结点数n 推出度为0、1和2的结点个数为n0、n1和n2突破点完全二叉树最多只会有一个度为1的结点
二叉树的储存结构
顺序存储 常用的基本操作 i的左孩子2i i的右孩子2i1 i的父结点⌊i/2⌋ i所在的层次⌈log2(n1)⌉或者⌊log2n⌋1
若完全二叉树中共有n个结点则 判断i是否有左孩子2i ≤ n ? 判断i是否有右孩子2i1 ≤ n ? 判断i是否是叶子/分支结点i ⌊n/2⌋ ?
储存非完全二叉树 二叉树的链式存储
定义和初始化 这样的方法可以很简单的找到p结点的左右孩子但是只能通过从根开始遍历查找找到结点p的父结点 可以通过多定一个父结点的指针来方便的查找父结点三叉链表 n个结点的二叉链表共有n1 个空链域可以用来构建线索二叉树
二叉树的先中后序遍历
遍历 遍历按照某种次序把所有结点都访问一遍 层序遍历基于树的层次特性确定的次序规则 先/中/后序遍历基于树的递归特性确定的次序规则
二叉树的遍历 二叉树的递归特性 要么是个空二叉树 要么就是由“根结点左子树右子树”组成的二叉树 先序遍历根左右NLR 中序遍历左根右LNR 后序遍历左右根LRN 先序遍历代码 中序遍历代码 后序遍历代码 二叉树遍历总结 空间复杂度为O(h)h为树的高度 每个结点都会被路过3次
求树的深度 是后序遍历的变种 先后访问左右儿子得出对应深度返回左右儿子深度更高的那个就是树的深度
二叉树的层序遍历
层序遍历
基于树的层次特性确定的次序规则
算法思想 初始化一个辅助队列 根结点入队 若队列非空则队头结点出队访问该结点并将其左、右孩子插入队尾如果有的话 重复第三步直至队列为空
代码实现 由遍历序列构造二叉树
结论 一个前/中/后/层序遍历序列可能对应多种二叉树形态 只有至少同时拥有两种遍历序列才能确定二叉树的形态 结论前序、后序、层序序列的两两组合无法唯一确定一科二叉树
通过两种遍历序列确定二叉树
前序中序 中序后序 层序中序 线索二叉树的概念
中序遍历的问题 如何找到指定结点p在q 中序遍历序列中的前驱 如何找到p的中序后继 能否从一个指定结点开始中序遍历 完成上述需求的思路 从根结点出发重新进行一次中序遍历指针q记录当前访问的结点指针pre记录上一个被访问的结点 当q p时pre为前驱 当pre p时q为后继 缺点找前驱、后继很不方便 操作必须从根开始
中序线索二叉树 线索二叉树的存储结构 先/中/后序线索二叉树同理
三种线索二叉树的对比 二叉树的线索化
通过头结点找到中序前驱 中序二叉树线索化 先序二叉树线索化 由于先序遍历先遍历根结点然后再遍历左结点若左孩子为空通过线索化后会指回前驱结点他的根结点 这时在此访问左孩子时候会又访问回根结点因此需要增加一个判断来确定左孩子不是真正的左孩子而是线索化后的前驱结点 因此PreThread函数需要优化为 后序二叉树线索化 在线索二叉树中找前驱后驱
中序线索二叉树找中序前驱后继 在中序线索二叉树中找到指定结点*p的中序后继next 若p-rtag 1则next p-rchild 若p-rtag 0说明p必定有右孩子next p的右子树中最左下的结点 在中序线索二叉树中找到指定结点*p的中序前驱pre 若p-ltag 1则pre p-lchild 若p-ltag 0说明p必定有左孩子pre p的左子树中最右下的结点 先序线索二叉树找先序前驱后继 在先序线索二叉树中找到指定结点*p的先序后继next 若p-rtag 1则next p-rchild 若p-rtag 0说明p必定有右孩子 若p有左孩子则先序后继为左孩子 若p没有左孩子则先序后继为右孩子 在先序线索二叉树中找到指定结点*p的先序前驱pre 若p-ltag 1则pre p-lchild 若p-ltag 0说明p必定有左孩子 先序遍历中左右子树中的结点只可能是根的后继不可能是前驱 方法1用土办法从头开始先序遍历 方法2可以改用三叉链表以找到父结点 后序线索二叉树找后序前驱后继 在后序线索二叉树中找到指定结点*p的后序前驱pre 若p-ltag 1则pre p-lchild 若p-ltag 0说明p必有左孩子 若p有右孩子则后序前驱为右孩子 若p没有右孩子则后序前驱为左孩子 在后序线索二叉树中找到指定结点*p的后序后继next 若p-rtag 1则next p-rchild 若p-rtag 0说明p必定有右孩子 后序遍历中左右子树中的结点只可能是根的前驱不可能是后继 方法1用土办法从头开始先序遍历 方法2可以改用三叉链表以找到父结点 树的储存结构
双亲表示法顺序存储 每个结点中保存指向双亲的“指针”dataparrent 根结点固定存储在0-1表示没有双亲 新增数据元素无需按逻辑上的次序存储只需说明新增元素的dataparrent即可 删除数据元素 方案1把要删除的数据元素data设为空parent设为-1 方案2将数组尾部的数据元素覆盖要删除的数据元素 查询数据元素 优点查指定结点的双亲很方便 缺点查指定结点的孩子只能从头遍历
孩子表示法顺序链式存储 孩子兄弟表示法链式存储 规则 左指针指向第一个孩子 右指针指向自己的第一个兄弟
森林和二叉树的转换 本质用二叉链表存储森林 规则 各个树的根结点视为兄弟关系 左指针指向第一个孩子 右指针指向自己的第一个兄弟
树和森林的遍历
树的先根遍历 先根遍历若树非空先访问根结点再依次对每棵子树进行先根遍历。 树的先根遍历序列与这棵树相应二叉树的先序序列相同。 树的后根遍历 后根遍历若树非空先依次对每棵子树进行后根遍历最后再访问根结点 树的后根遍历序列与这棵树相应二叉树的中序序列相同 也被称为深度优先遍历 树的层次遍历 用队列实现又被称为广度优先遍历 步骤 若树非空则根结点入队 若队列非空队头元素出队并访问同时将该元素的孩子依次入队 重复第二步直到队列为空
森林的先序遍历 若森林为非空则按如下规则进行遍历 访问森林中第一棵树的根结点。 先序遍历第一棵树中根结点的子树森林。 先序遍历除去第一棵树之后剩余的树构成的森林。 效果等同于依次对各个树进行先根遍历 用孩子兄弟表示法转换为二叉树效果等同于依次对二叉树的先序遍历
森林的中序遍历 若森林为非空则按如下规则进行遍历 中序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点。 中序遍历除去第一棵树之后剩余的树构成的森林。 效果等同于依次对各个树进行后根遍历 用孩子兄弟表示法转换为二叉树效果等同于依次对二叉树的中序遍历
二叉排序树BST
定义 二叉排序树又称二叉查找树BSTBinary Search Tree 一棵二叉树或者是空二叉树或者是具有如下性质的二叉树 左子树上所有结点的关键字均小于根结点的关键字 右子树上所有结点的关键字均大于根结点的关键字 左子树和右子树又各是一棵二叉排序树 即左子树结点值 根结点值 右子树结点值 进行中序遍历可以得到一个递增的有序序列 二叉排序树可用于元素的有序组织、搜索
BST的查找 若树非空目标值与根结点的值比较 若相等则查找成功 若小于根结点则在左子树上查找否则在右子树上查找。 查找成功返回结点指针 查找失败返回NULL 递归实现的最坏空间复杂度为O(h),普通实现的最坏空间复杂度为O(1) BST的插入 若原二叉排序树为空则直接插入结点 否则若关键字k小于根结点值则插入到左子树若关键字k大于根结点值则插入到右子树 递归实现的最坏空间复杂度为O(h) 二叉排序树的构造 注意不同的关键字序列可能得到同款二叉排序树也可能得到不同款二叉排序树
二叉排序树的删除 先搜索找到目标结点 若被删除结点z是叶结点则直接删除不会破坏二叉排序树的性质。 若结点z只有一棵左子树或右子树则让z的子树成为z父结点的子树替代z的位置。 若结点z有左、右两棵子树则令z的直接后继或直接前驱替代z然后从二叉排序树中删去这个直接后继或直接前驱这样就转换成了第一或第二种情况。 z的后继z的右子树中最左下结点是右子树最小的结点该结点一定没有左子树 z的前驱z的左子树中最右下结点是左子树中最大的结点该结点一定没有右子树
查找效率分析 查找长度在查找运算中需要对比关键字的次数称为查找长度反映了查找操作时间复杂度 查找成功的平均查找长度ASLAverage Search Length各层层数*层结点个数相加/总结点个数 最坏情况每个结点只有一个分支树高h结点数n。平均查找长度O(n) 最好情况n个结点的二叉树最小高度为(log2n) 1。平均查找长度 O(log2n)
平衡二叉树AVL
定义 平衡二叉树Balanced Binary Tree简称平衡树AVL树——树上任一结点的左子树和右子树的高度之差不超过1 结点的平衡因子左子树高-右子树高 平衡二叉树结点的平衡因子的值只可能是−1、0或1 只要有任一结点的平衡因子绝对值大于1就不是平衡二叉树
平衡二叉树的插入 在二叉排序树中插入新结点后如何保持平衡 查找路径上的所有结点都有可能受到影响 从插入点往回找到第一个不平衡结点调整以该结点为根的子树 每次调整的对象都是“最小不平衡子树” 在插入操作中只要将最小不平衡子树调整平衡则其他祖先结点都会恢复平衡 插入操作导致“最小不平衡子树”高度1经过调整后高度恢复 调整最小不平衡子树 调整最小不平衡子树 只有假设所有子树的高度都是H才能保证出现最小不平衡子树恒定 目标 恢复平衡 保持二叉排序树特性 二叉排序树的特性左子树结点值 根结点值 右子树结点值 LL平衡旋转右单旋转 由于在结点A的左孩子L的左子树L上插入了新结点A的平衡因子由1增至2导致以A为根的子树失去平衡需要一次向右的旋转操作 将A的左孩子B向右上旋转代替A成为根结点将A结点向右下旋转成为B的右子树的根结点而B的原右子树则作为A结点的左子树 RR平衡旋转左单旋转 由于在结点A的右孩子R的右子树R上插入了新结点A的平衡因子由-1减至-2导致以A为根的子树失去平衡需要一次向左的旋转操作 将A的右孩子B向左上旋转代替A成为根结点将A结点向左下旋转成为B的左子树的根结点而B的原左子树则作为A结点的右子树 右旋和左旋的代码实现思路 LR平衡旋转先左后右双旋转 由于在A的左孩子L的右子树R上插入新结点A的平衡因子由1增至2导致以A为根的子树失去平衡需要进行两次旋转操作先左旋转后右旋转 先将A结点的左孩子B的右子树的根结点C向左上旋转提升到B结点的位置然后再把该C结点向右上旋转提升到A结点的位置 RL平衡旋转先右后左双旋转 由于在A的右孩子R的左子树L上插入新结点A的平衡因子由-1减至-2导致以A为根的子树失去平衡需要进行两次旋转操作先右旋转后左旋转 先将A结点的右孩子B的左子树的根结点C向右上旋转提升到B结点的位置然后再把该C结点向左上旋转提升到A结点的位置 查找效率分析 若树高为h则最坏情况下查找一个关键字最多需要对比h次即查找操作的时间复杂度不可能超过O(h) 平衡二叉树——树上任一结点的左子树和右子树的高度之差不超过1 假设以nh表示深度为h的平衡树中含有的最少结点数。 则有n0 0, n1 1, n2 2并且有nh n(h−1) n(h−2) 1 可以证明含有n个结点的平衡二叉树的最大深度为O(log2n) 平衡二叉树的平均查找长度为O(log2n)
哈夫曼树
带权路径长度 结点的权有某种现实含义的数值如表示结点的重要性等 结点的带权路径长度从树的根到该结点的路径长度经过的边数与该结点上权值的乘积 树的带权路径长度树中所有叶结点的带权路径长度之和WPL, Weighted Path Length
哈夫曼树的定义
在含有n个带权叶结点的二叉树中其中带权路径长度WPL最小的二叉树称为哈夫曼树也称最优二叉树 哈夫曼树的构造 给定n个权值分别为w1, w2,…, wn的结点构造哈夫曼树的算法描述如下 将这n个结点分别作为n棵仅含一个结点的二叉树构成森林F。 构造一个新结点从F中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。 从F中删除刚才选出的两棵树同时将新得到的树加入F中。 重复步骤2和3直至F中只剩下一棵树为止。 每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大 哈夫曼树的结点总数为2n − 1 哈夫曼树中不存在度为1的结点。 哈夫曼树并不唯一但WPL必然相同且为最优 哈夫曼编码 固定长度编码每个字符用相等长度的二进制位表示 可变长度编码允许对不同字符用不等长的二进制位表示 若没有一个编码是另一个编码的前缀则称这样的编码为前缀编码如果没有前缀编码容易出现歧义 由哈夫曼树得到哈夫曼编码字符集中的每个字符作为一个叶子结点各个字符出现的频度作为结点的权值根据之前介绍的方法构造哈夫曼树
并查集
定义
并查集Disjoint Set是逻辑结构集合的一种具体实现只进行“并”和“查”两种基本操作
并查集的基本操作 Find查操作确定一个指定元素所属集合 Union并操作将两个不相交的集合合并为一个
初始化 S[]实际上就是树的双亲表示法里面的值就是自己对应根结点的下标
并、查 时间复杂度分析 Find操作最坏时间复杂度O(n) Union操作时间复杂度O(1)
Union操作的优化 在每次Union操作构建树的时候尽量让树不长高 用根结点的绝对值表示树的结点总数根结点从-1改成-树的总结点 Union操纵让小树合并到大树 该方法构造的树高不超过[log2n]1 Find最坏时间复杂度变为O(log2n) 并查集的压缩路径 核心想法就是让树越来越“矮” Find操作先找到根结点再将查找路径上所有结点都挂到根结点下 这样的操纵可以让树的告诉不超过O(α(n)) O(α(n))是一个增长很缓慢的函数对于常见的n值O(α(n))通常4 因此优化后的并查集Find、Union操作时间开销都很低
图
图的基本概念
定义 图G由顶点集V和边集E组成记为G (V, E)其中V(G)表示图G中顶点的有限非空集 E(G)表示图G中顶点之间的关系边集合。 若V {v1, v2, … , vn}则用|V|表示图G中顶点的个数也称图G的阶E {(u, v) | u∈V, v∈V}用|E|表示图G中边的条数。 注意线性表可以是空表树可以是空树但图不可以是空即V一定是非空集
无向图、有向图
无向图 若E是无向边简称$的有限集合时则图G为无向图。 边是顶点的无序对记为(v, w)或(w, v)因为(v, w) (w, v)其中v、w是顶点。可以说顶点w和顶点v互为邻接点。 边(v, w)依附于顶点w和v或者说边(v, w)和顶点v、w相关联。
有向图 若E是有向边也称!的有限集合时则图G为有向图。 弧是顶点的有序对记为v, w其中v、w是顶点v称为弧尾w称为弧头v, w称为从顶点v到顶点w的弧也称v邻接到w或w邻接自v。 注意v, w ≠ w, v
简单图、多重图
数据结构课程只探讨“简单图”
简单图 不存在重复边 不存在顶点到自身的边
多重图
图G中某两个结点之间的边数多于一条又允许顶点通过同一条边和自己关联则G为多重图
顶点的度、入度、出度 对于无向图 顶点v的度是指依附于该顶点的边的条数记为TD(v)。 在具有n个顶点、e条边的无向图中无向图的全部顶点的度的和等于边数的2倍 对于有向图 入度是以顶点v为终点的有向边的数目记为ID(v) 出度是以顶点v为起点的有向边的数目记为OD(v)。 顶点v的度等于其入度和出度之和即TD(v) ID(v) OD(v)。
顶点-顶点的关系描述 路径顶点vp到顶点vq之间的一条路径是指顶点序列 回路第一个顶点和最后一个顶点相同的路径称为回路或环 简单路径在路径序列中顶点不重复出现的路径称为简单路径。 简单回路除第一个顶点和最后一个顶点外其余顶点不重复出现的回路称为简单回路。 路径长度路径上边的数目 点到点的距离从顶点u出发到顶点v的最短路径若存在则此路径的长度称为从u到v的距离。若从u到v根本不存在路径则记该距离为无穷∞。 无向图中若从顶点v到顶点w有路径存在则称v和w是连通的 有向图中若从顶点v到顶点w和从顶点w到顶点v之间都有路径则称这两个顶点是强连通的
连通图、强连通图 若图G中任意两个顶点都是连通的则称图G为连通图否则称为非连通图。 对于n个顶点的无向图G 若G是连通图则最少有n-1条边 若G是非连通图则最多可能有 条边 若图中任何一对顶点都是强连通的则称此图为强连通图。 对于n个顶点的有向图G 若G是强连通图则最少有n条边形成回路
研究图的局部——子图 设有两个图G (V, E)和G¢ (V’, E’)若V¢是V的子集且E’是E的子集则称G’是G的子图 若有满足V(G’) V(G)的子图G’则称其为G的生成子图 注意并非任意挑几个点、几条边都能构成子图
连通分量 无向图中的极大联通子图称为连通分量 子图必须连通且包含尽可能多的顶点和边
强连通分量 有向图中的极大强联通子图成为有向图的强连通分量 子图必须强连通同时保留尽可能多的边
生成树 连通图的生成树是包含图中全部顶点的一个极小连通子图 边尽可能的少但要保持连通 若图中顶点数为n则它的生成树含有n-1条边。对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路。
生成森林
在非连通图中连通分量的生成树构成了非连通图的生成森林。
边的权、带权图/网 边的权在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。 带权图/网——边上带有权值的图称为带权图也称网。 带权路径长度——当图是带权图时一条路径上所有边的权值之和称为该路径的带权路径长度
几种特殊形态的图 无向完全图无向图中任意两个顶点之间都存在边 有向完全图有向图中任意两个顶点之间都存在方向相反的两条弧 边数很少的图称为稀疏图 反之称为稠密图 没有绝对的界限一般来说|E| |V|log|V|时可以将G视为稀疏图 树不存在回路且连通的无向图 有向树一个顶点的入度为0、其余顶点的入度均为1的有向图称为有向树 n个顶点的树必有n-1条边。 n个顶点的图若|E|n-1则一定有回路
邻接矩阵法
定义 无向图 第i个结点的度第i行或第i列的非零元素个数 有向图 第i个结点的出度第i行的非零元素个数 第i个结点的入度第i列的非零元素个数 第i个结点的度第i行、第i列的非零元素个数之和 邻接矩阵法求顶点的度/出度/入度的时间复杂度为O(|V|)
邻接矩阵法存储带权图网 邻接矩阵法的性能分析 空间复杂度O(|V|^2) ——只和顶点数相关和实际的边数无关 适合用于存储稠密图 无向图的邻接矩阵是对称矩阵可以压缩存储只存储上三角区/下三角区
邻接矩阵法的性质 邻接表法
为什么要使用邻接表 邻接矩阵是使用数组实现的顺序存储空间复杂度高不适合存储稀疏图 邻接表是顺序链式存储
定义 其实这和树的孩子表示法是类似的孩子表示法顺序存储各个结点每个结点中保存孩子链表头指针 边结点的数量是2|E|整体空间复杂度为O(|V| 2|E|) 边结点的数量是|E|整体空间复杂度为O(|V| |E|) 只要确定了顶点编号图的邻接矩阵表示方式唯一图的邻接表表示方式并不唯一
邻接矩阵和邻接表的对比 十字链表、邻接多重表
关系 十字链表储存有向图 邻接多重表储存无向图
十字链表存储有向图 空间复杂度O(|V||E|) 如何找到指定顶点的所有出边顺着绿色线路找 如何找到指定顶点的所有入边顺着橙色线路找
邻接矩阵、邻接表存储无向图 邻接表每条边对应两份冗余信息删除顶点、删除边等操作时间复杂度高 临接矩阵空间复杂度高O(|V|2)
临接多重表储存无向图 空间复杂度O(|V||E|) 删除边、删除结点等操作很方便只需要让各指针指向下一个对应的指向即可
总结 图的基本操作 Adjacent(G,x,y)判断图G是否存在边x, y或(x, y)。 Neighbors(G,x)列出图G中与结点x邻接的边。 InsertVertex(G,x)在图G中插入顶点x。 DeleteVertex(G,x)从图G中删除顶点x。 AddEdge(G,x,y)若无向边(x, y)或有向边x, y不存在则向图G中添加该边。 RemoveEdge(G,x,y)若无向边(x, y)或有向边x, y存在则从图G中删除该边。 FirstNeighbor(G,x)求图G中顶点x的第一个邻接点若有则返回顶点号。若x没有邻接点或图中不存在x则返回-1。 NextNeighbor(G,x,y)假设图G中顶点y是顶点x的一个邻接点返回除y之外顶点x的下一个邻接点的顶点号若y是x的最后一个邻接点则返回-1。 Get_edge_value(G,x,y)获取图G中边(x, y)或x, y对应的权值。 Set_edge_value(G,x,y,v)设置图G中边(x, y)或x, y对应的权值为v。 注意上面的操作都只针对邻接矩阵和邻接表
图的广度优先遍历BFS
树和图的广度优先遍历 树的广度优先遍历通过根结点可以找到下一层的结点234.通过234又可以找到再下一层的结点5678 若树非空则根结点入队 若队列非空队头元素出队并访问同时将该元素的孩字依次入队 重复第二步直到队列为空 图的广度优先遍历类似于树的广度优先遍历层序遍历 区别 树不存在“回路”搜索相邻的结点时不可能搜到已经访问过的结点 图搜索相邻的顶点时有可能搜到已经访问过的顶点
代码实现 找到与一个顶点相邻的所有顶点 FirstNeighbor(G,x)求图G中顶点x的第一个邻接点若有则返回顶点号。若x没有邻接点或图中不存在x则返回-1。 NextNeighbor(G,x,y)假设图G中顶点y是顶点x的一个邻接点返回除y之外顶点x的下一个邻接点的顶点号若y是x的最后一个邻接点则返回-1。 使用上面两个基本操作 标记哪些顶点被访问过 都初始化为false 需要一个辅助队列 遍历序列的可变性 同一个图的邻接矩阵表示方式唯一因此广度优先遍历序列唯一 同一个图邻接表表示方式不唯一因此广度优先遍历序列不唯一
算法存在的问题和解决方案
如果是非连通图则无法遍历完所有结点 空间复杂度最坏情况辅助队列大小为 O(|V|) 邻接矩阵存储的图 访问 |V| 个顶点需要O(|V|)的时间 查找每个顶点的邻接点都需要O(|V|)的时间而总共有|V|个顶点 时间复杂度 O(|V|^2) 邻接表存储的图 访问 |V| 个顶点需要O(|V|)的时间 查找各个顶点的邻接点共需要O(|E|)的时间 时间复杂度 O(|V||E|)
广度优先生成树 广度优先生成树由广度优先遍历过程确定。 由于邻接表的表示方式不唯一因此基于邻接表的广度优先生成树也不唯一 对非连通图的广度优先遍历可得到广度优先生成森林
图的深度优先遍历DFS
树和图的深度优先遍历 树的深度优先遍历先根、后根 从根结点出发能往更深处走就尽量往深处走。 每当访问一个结点的时候要检查是否还有与当前结点相邻的且没有被访问过的结点如果有的话就往下一层钻。 图的深度优先遍历类似于树的先根遍历。 图的深度优先遍历是递归实现的广度优先办理是队列实现的
图的深度优先遍历 算法存在的问题和解决方案
如果是非连通图则无法遍历完所有结点 复杂度分析 空间复杂度 来自函数调用栈最坏情况递归深度为O(|V|) 最好情况O(1) 时间复杂度 时间复杂度访问各结点所需时间探索各条边所需时间 邻接矩阵存储的图 访问 |V| 个顶点需要O(|V|)的时间 查找每个顶点的邻接点都需要O(|V|)的时间而总共有|V|个顶点 时间复杂度 O(|V|^2) 邻接表存储的图 访问 |V| 个顶点需要O(|V|)的时间 查找各个顶点的邻接点共需要O(|E|)的时间 时间复杂度 O(|V||E|)
深度优先序列 和图的邻接表是一个原理树中各个孩子结点在邻接表中出现的顺序是可变的 因此如果采用这种数据结构存储树那么可能会有不同的遍历序列
深度优先生成树 同一个图的邻接矩阵表示方式唯一因此深度优先遍历序列唯一深度优先生成树也唯一 同一个图邻接表表示方式不唯一因此深度优先遍历序列不唯一深度优先生成树也不唯一 对无向图进行BFS/DFS遍历
图的遍历与图的连通性 调用BFS/DFS函数的次数连通分量数 对于连通图只需调用1次 BFS/DFS 对有向图进行BFS/DFS遍历 调用BFS/DFS函数的次数要具体问题具体分析若起始顶点到其他各顶点都有路径则只需调用1次BFS/DFS 函数 对于强连通图从任一结点出发都只需调用1次 BFS/DFS
最小生成树
生成树 连通图的生成树是包含图中全部顶点的一个极小连通子图。 若图中顶点数为n则它的生成树含有n-1条边。对生成树而言若砍去它的一条边则会变成非连通图若加上一条边则会形成一个回路
最小生成树最小代价树 对于一个带权连通无向图G (V, E)生成树不同每棵树的权即树中所有边上的权值之和也可能不同 设R为G的所有生成树的集合若T为R中边的权值之和最小的生成树则T称为G的最小生成树Minimum-Spanning-Tree, MST 最小生成树可能有多个但边的权值之和总是唯一且最小的 最小生成树的边数 顶点数 - 1 砍掉一条则不连通增加一条边则会出现回路 如果一个连通图本身就是一棵树则其最小生成树就是它本身 只有连通图才有生成树非连通图只有生成森林
Prim 算法普里姆
算法思想 从某一个顶点开始构建生成树 每次将代价最小的新顶点纳入生成树直到所有顶点都纳入为止。 时间复杂度O(|V|^2)适合用于边稠密图
数据结构 实现步骤 从V0开始总共需要 n-1 轮处理 循环遍历所有个结点找到lowCost最低的且还没加入树的顶点isJoin对应结点标记为true 再次循环遍历更新还没加入的各个顶点的lowCost值 重复上面步骤直到所有结点都加入树生成的树即为最小生成树
Kruskal 算法克鲁斯卡尔
算法思想 每次选择一条权值最小的边使这条边的两头连通原本已经连通的就不选 直到所有结点都连通 时间复杂度O( |E|log2|E| )适合用于边稀疏图
数据结构 让各条边按照权值顺序排序
实现步骤 共执行 e 轮每轮判断两个顶点是否属于同一集合 检查第e条边的两个顶点是否连通是否属于同一个集合 若不联通则连起来 若联通则不操作 重复上面的步骤直到所有边都被遍历过
最短路径问题之BFS算法
介绍 无权图可以视为一种特殊的带权图只是每条边的权值都为1 BFS一般只适用于无权图的最短路径问题
代码实现 d数组表示u到各个结点的最短路径 path数组表示该结点回到u结点的最短前驱结点 由此生成的生成树同时也反应了起点到任意结点的距离
最短路径问题之Dijkstra算法
BFS算法的局限性 带权路径长度——当图是带权图时一条路径上所有边的权值之和称为该路径的带权路径长度 BFS算法求单源最短路径只适用于无权图或所有边的权值都相同的图
算法思想 初始从V0开始初始化三个数组信息 循环遍历所有结点找到还没确定最短路径且dist 最小的顶点Vi令final[i]ture。 检查所有邻接自 Vi 的顶点若其 final 值为false则更新 dist 和 path 信息 重复上述步骤知道所有结点的final都标记为true
代码实现思路 初始 若从V0开始令 final[0]ture; dist[0]0; path[0]-1。 n-1轮处理 循环遍历所有顶点找到还没确定最短路径且dist 最小的顶点Vi令final[i]ture。 并检查所有邻接自Vi 的顶点对于邻接自Vi 的顶点 Vj 若 final[j]false 且 dist[i]arcsi dist[j]则令 dist[j]dist[i]arcsi; path[j]i。 注arcsi表示Vi 到Vj 的弧的权值 时间复杂度O(n2)即O(|V|2)
用于负权值带权图
Dijkstra 算法不适用于有负权值的带权图
最短路径问题之Floyd算法
算法思想 Floyd算法求出每一对顶点之间的最短路径 使用动态规划思想将问题的求解分为多个阶段 对于n个顶点的图G求任意一对顶点 Vi — Vj 之间的最短路径可分为如下几个阶段 初始不允许在其他顶点中转最短路径是 0若允许在 V0 中转最短路径是 1若允许在 V0、V1 中转最短路径是 2若允许在 V0、V1、V2 中转最短路径是 … n-1若允许在 V0、V1、V2 …… Vn-1 中转最短路径是
实现步骤 代码实现 注意点 Floyd算法可以用于负权图 Floyd 算法不能解决带有“负权回路”的图有负权值的边组成回路这种图有可能没有最短路径每走一圈路径越小
总结 有向无环图DAG图的描述表达式
定义
若一个有向图中不存在环则称为有向无环图简称DAG图Directed Acyclic Graph
例子
转换前 转换后 解题方法 把各个操作数不重复地排成一排 标出各个运算符的生效顺序先后顺序有点出入无所谓 按顺序加入运算符注意“分层” 从底向上逐层检查同层的运算符是否可以合体
拓扑排序
AOV网 AOV网(Activity On Vertex NetWork用顶点表示活动的网) 用DAG图有向无环图表示一个工程。顶点表示活动有向边Vi, Vj表示活动Vi必须先于活动Vj进行
拓扑排序 拓扑排序在图论中由一个有向无环图的顶点组成的序列当且仅当满足下列条件时称为该图的一个拓扑排序 每个顶点出现且只出现一次。 若顶点A在序列中排在顶点B的前面则在图中不存在从顶点B到顶点A的路径。 或定义为 拓扑排序是对有向无环图的顶点的一种排序它使得若存在一条从顶点A到顶点B的路径则在排序中顶点B出现在顶点A的后面。 每个AOV网都有一个或多个拓扑排序序列。 简单来说拓扑排序就是找到做事的先后顺序 拓扑排序的实现 从AOV网中选择一个没有前驱入度为0的顶点并输出。 从网中删除该顶点和所有以它为起点的有向边。 重复前面的步骤直到当前的AOV网为空或当前网中不存在无前驱的顶点为止。
代码实现 时间复杂度O(|V||E|) 若采用邻接矩阵则需O(|V|^2)
逆拓扑排序 对一个AOV网如果采用下列步骤进行排序则称之为逆拓扑排序 从AOV网中选择一个没有后继出度为0的顶点并输出。 从网中删除该顶点和所有以它为终点的有向边。 重复上面步骤直到当前的AOV网为空。 用邻接表实现会更简单一些 使用逆邻接表邻接表的顶点对应储存的信息是指向该顶点的边的信息 使用深度优先算法实现逆拓扑排序顶点输出的序列就是逆拓扑排序序列 DFS实现逆拓扑排序在顶点退栈前输出
关键路径
AOE网 在带权有向图中以顶点表示事件以有向边表示活动以边上的权值表示完成该活动的开销如完成活动所需的时间 称之为用边表示活动的网络简称AOE网 (Activity On Edge NetWork) AOE网具有以下两个性质 只有在某顶点所代表的事件发生后从该顶点出发的各有向边所代表的活动才能开始 只有在进入某顶点的各有向边所代表的活动都已结束时该顶点所代表的事件才能发生。 另外有些活动是可以并行进行的 关键路径 从源点到汇点的有向路径可能有多条所有路径中具有最大路径长度的路径称为关键路径而把关键路径上的活动称为关键活动 完成整个工程的最短时间就是关键路径的长度若关键活动不能按时完成则整个工程的完成时间就会延长 事件vk的最早发生时间ve(k)决定了所有从vk开始的活动能够开工的最早时间 活动ai的最早开始时间e(i)指该活动弧的起点所表示的事件的最早发生时间 事件vk的最迟发生时间vl(k)它是指在不推迟整个工程完成的前提下该事件最迟必须发生的时间。 活动ai的最迟开始时间l(i)它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。 活动ai的时间余量d(i)l(i)-e(i)表示在不增加完成整个工程所需总时间的情况下活动ai可以拖延的时间 若一个活动的时间余量为零则说明该活动必须要如期完成d(i)0即l(i) e(i)的活动ai是关键活动 由关键活动组成的路径就是关键路径
求关键路径的步骤 求所有事件的最早发生时间 ve( ) 按拓扑排序序列依次求各个顶点的 ve(k): ve(源点) 0 ve(k) Max{ve(j) Weight(vj, vk)}, vj为vk 的任意前驱 求所有事件的最迟发生时间 vl( ) 按逆拓扑排序序列依次求各个顶点的 vl(k): vl(汇点) ve(汇点) vl(k) Min{vl(j) - Weight(vk, vj)} , vj为vk的任意后继 求所有活动的最早发生时间 e( ) 若边vk, vj表示活动ai则有e(i) ve(k) 求所有活动的最迟发生时间 l( ) 若边vk, vj表示活动ai则有l(i) vl(j) - Weight(vk, vj) 求所有活动的时间余量 d( ) d(i) l(i) - e(i) d(i)0的活动就是关键活动, 由关键活动可得关键路径
关键活动、关键路径的特性 若关键活动耗时增加则整个工程的工期将增长 缩短关键活动的时间可以缩短整个工程的工期 当缩短到一定程度时关键活动可能会变成非关键活动 可能有多条关键路径只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。
查找
查找的基本概念 查找 在数据集合中寻找满足某种条件的数据元素的过程称为查找 查找表查找结构用于查找的数据集合称为查找表它由同一类型的数据元素或记录组成 关键字 数据元素中唯一标识该元素的某个数据项的值使用基于关键字的查找查找结果应该是唯一的。
对查找表的常见操作 查找符合条件的数据元素 静态查找表 仅关注查找速度即可 插入、删除某个数据元素 动态查找表 除了查找速度也要关注插/删操作是否方便实现
查找算法的评价指标 查找长度在查找运算中需要对比关键字的次数称为查找长度 平均查找长度ASL, Average Search Length 所有查找过程中进行关键字的比较次数的平均值 ASL的数量级反应了查找算法的时间复杂度 评价一个查找算法的效率时通常考虑查找成功、查找失败两种情况的ASL 顺序查找
定义
顺序查找又叫“线性查找”通常用于线性表。
算法思想从头到尾依次往后找
顺序查找的实现 顺序查找的实现哨兵 优点无需判断是否越界效率更高 顺序查找的优化对有序表 用查找判定树分析ASL 一个成功结点的查找长度 自身所在层数 一个失败结点的查找长度 其父结点所在层数 默认情况下各种失败情况或成功情况都等概率发生
顺序查找的优化被查概率不相等 折半查找
算法思想
折半查找又称“二分查找”仅适用于有序的顺序表。
查找成功
注意下面的mid向下取整 查找失败 代码实现 查找效率分析 折半查找判定树的构造 如果当前low和high之间有偶数个元素则 mid 分隔后左半部分比右半部分少一个元素 如果当前low和high之间有奇数个元素则 mid 分隔后左右两部分元素个数相等 折半查找的判定树中,mid [(low high)/2]则对于任何一个结点必有右树结点数-左子树结点数0或1 折半查找的判定树一定是平衡二叉树 折半查找的判定树中只有最下面一层是不满的因此元素个数为n时树高h [log2(n 1)] 判定树结点关键字左中右满足二叉排序树的定义 失败结点n1个等于成功结点的空链域数量 折半查找的时间复杂度 O(log2n)
分块查找
算法思想 特点块内无序、块间有序 分块查找又称索引顺序查找算法过程如下 在索引表中确定待查记录所属的分块可顺序、可折半 在块内顺序查找
用折半查找查索引
若查找目标与索引表值相同 若查找目标与索引值不同 若索引表中不包含目标关键字则折半查找索引表最终停在 lowhigh要在low所指分块中查找 原因最终low左边一定小于目标关键字high右边一定大于目标关键字。而分块存储的索引表中保存的是各个分块的最大关键字
查找失败的例子 查找效率分析 B树
m叉查找树 实际上就是二叉查找树的拓展结点多少有多少个分叉就是多少叉查找树 每个结点关键字的查找可以用顺序查找也可以用折半查找 如何保证查找效率 若每个结点内关键字太少导致树变高要查更多层结点效率低 策略m叉查找树中规定除了根结点外任何结点至少有⌈m/2⌉个分叉即至少含有⌈m/2⌉ − 1 个关键字 为什么不能保证根结点至少有⌈m/2⌉个分叉如果整个树只有1个元素根结点只能有两个分叉 不够“平衡”树会很高要查很多层结点 策略m叉查找树中规定对于任何一个结点其所有子树的高度都要相同。
B树的定义 B树又称多路平衡查找树B树中所有结点的孩子个数的最大值称为B树的阶通常用m表示。一棵m阶B树或为空树或为满足如下特性的m叉树 树中每个结点至多有m棵子树即至多含有m-1个关键字。 若根结点不是终端结点则至少有两棵子树。 除根结点外的所有非叶结点至少有⌈m/2⌉棵子树即至少含有 ⌈m/2⌉-1个关键字。 所有非叶结点的结构如下 其中Kii 1, 2,…, n为结点的关键字且满足K1 K2 … KnPii 0, 1,…, n为指向子树根结点的指针且指针Pi-1所指子树中所有结点的关键字均小于KiPi所指子树中所有结点的关键字均大于Kin⌈m/2⌉- 1≤n≤m - 1为结点中关键字的个数。 所有的叶结点都出现在同一层次上并且不带信息可以视为外部结点或类似于折半查找判定树的查找失败结点实际上这些结点不存在指向这些结点的指针为空。
B树的高度 最大高度的另一种推导方法 B树的插入删除
B树的插入 新元素一定是插入到最底层“终端结点”用“查找”来确定插入位置 在插入key后若导致原结点关键字数超过上限则从中间位置⌈m/2⌉将其中的关键字分为两部分 左部分包含的关键字放在原结点中右部分包含的关键字放到新结点中中间位置⌈m/2⌉的结点插入原结点的父结点 若此时导致其父结点的关键字个数也超过了上限则继续进行这种分裂操作直至这个过程传到根结点为止进而导致B树高度增1。
B树的删除 若被删除关键字在终端结点则直接删除该关键字要注意结点关键字个数是否低于下限 ⌈m/2⌉ − 1 若被删除关键字在非终端结点则用直接前驱或直接后继来替代被删除的关键字 直接前驱当前关键字左侧指针所指子树中“最右下”的元素 直接后继当前关键字右侧指针所指子树中“最左下”的元素 若被删除关键字所在结点删除前的关键字个数低于下限且与此结点右或左兄弟结点的关键字个数还很宽裕则需要调整该结点、右或左兄弟结点及其双亲结点父子换位法 当右兄弟很宽裕时用当前结点的后继比当前结点大一位、后继的后继比当前结点大两位来填补空缺 当左兄弟很宽裕时用当前结点的前驱比当前结点小一位、前驱的前驱比当前结点小两位来填补空缺 若被删除关键字所在结点删除前的关键字个数低于下限且此时与该结点相邻的左、右兄弟结点的关键字个数均⌈m/2⌉ − 1则将关键字删除后与左或右兄弟结点及双亲结点中的关键字进行合并
B树
定义和性质 一棵m阶的B树需满足下列条件 每个分支结点最多有m棵子树孩子结点。 非叶根结点至少有两棵子树其他每个分支结点至少有⌈m/2⌉棵子树。 可以理解为要追求“绝对平衡”即所有子树高度要相同 结点的子树个数与关键字个数相等。 所有叶结点包含全部关键字及指向相应记录的指针叶结点中将关键字按大小顺序排列并且相邻叶结点按大小顺序相互链接起来。 所有分支结点中仅包含它的各个子结点中关键字的最大值及指向其子结点的指针。
B树的查找
B树中无论查找成功与否最终一定都要走到最下面一层结点因为只有叶子结点才有关键字对应的记录
B树和B树区别 典型应用关系型数据库的“索引”如MySQL 在B树中非叶结点不含有该关键字对应记录的存储地址。 可以使一个磁盘块可以包含更多个关键字使得B树的阶更大树高更矮读磁盘次数更少查找更快
散列哈希查找
定义 散列表Hash Table又称哈希表 是一种数据结构特点是数据元素的关键字与其存储地址直接相关 通过哈希函数建立关键字和存储地址的联系 若不同的关键字通过散列函数映射到同一个值则称它们为“同义词” 通过散列函数确定的位置已经存放了其他元素则称这种情况为“冲突”
处理冲突的方法——拉链法 用拉链法又称链接法、链地址法处理“冲突”把所有“同义词”存储在一个链表中 最理想情况散列查找时间复杂度可到达O(1) “冲突”越多查找效率越低 实际上就是顺序表和链表的结合结合两者优点比如顺序表的随机存取然后用链表的解决冲突问题又规避了顺序表的一系列缺点 在插入新元素时保持关键字有序可微微提高查找效率
常见的散列函数 散列函数的设计目的 让不同关键字的冲突尽可能的少 散列查找是典型的“用空间换时间”的算法只要散列函数设计的合理则散列表越长冲突的概率越低。 除留余数法H(key) key % p 散列表表长为m取一个不大于m但最接近或等于m的质数p 质数又称素数。指除了1和此整数自身外,不能被其他自然数整除的数 用质数取模分布更均匀冲突更少。参见《数论》 注意散列函数的设计要结合实际的关键字分布特点来考虑不要教条化 直接定址法 H(key) key 或 H(key) a*key b 其中a和b是常数。这种方法计算最简单且不会产生冲突。它适合关键字的分布基本连续的情况若关键字分布不连续空位较多则会造成存储空间的浪费。 例如存储同一个班级的学生信息 数字分析法选取数码分布较为均匀的若干位作为散列地址 设关键字是r进制数如十进制数而r个数码在各位上出现的频率不一定相同可能在某些位上分布均匀一些每种数码出现的机会均等 而在某些位上分布不均匀只有某几种数码经常出现此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合若更换了关键字则需要重新构造新的散列函数。 例如以“手机号码”作为关键字设计散列函数 平方取中法取关键字的平方值的中间几位作为散列地址。 具体取多少位要视实际情况而定。 这种方法得到的散列地址与关键字的每位都有关系因此使得散列地址分布比较均匀适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。 例如要存储整个学校的学生信息以“身份证号”作为关键字设计散列函数
处理冲突的方法——开放定址法 所谓开放定址法是指可存放新表项的空闲地址既向它的同义词表项开放又向它的非同义词表项开放。其数学递推公式为 Hi (H(key) di) % m i 0, 1, 2,…, kk≤m - 1m表示散列表表长di为增量序列 i 可理解为“第i次发生冲突” 线性探测法 di 0, 1, 2, 3, …, m-1即发生冲突时每次往后探测相邻的下一个单元是否为空为空则可以插入数值 查找也是类似先通过公式得到Hi再依次往后查找若遇到空的位置则说明查找失败所以越早遇到空位置就可以越早确定查找失败 删除结点不能简单地将被删结点的空间置为空否则将截断在它之后填入散列表的同义词结点的查找路径可以做一个“删除标记”进行逻辑删除 线性探测法由于冲突后再探测一定是放在某个连续的位置很容易造成同义词、非同义词的“聚集堆积”现象严重影响查找效率 平方探测法 当di 0^2, 1^2, -1^2, 2^2, -2^2, …, k^2, -k^2时称为平方探测法又称二次探测法其中k≤m/2 比起线性探测法更不易产生“聚集堆积”问题 注意负数的模运算(-3)%27 24而不是3 模运算的规则a MOD m (akm) MOD m , 其中k为任意整数 散列表长度m必须是一个可以表示成4j 3的素数才能探测到所有位置 伪随机序列法 di 是一个伪随机序列如 di 0, 5, 24, 11, …
处理冲突的方法——再散列法 除了原始的散列函数 H(key) 之外多准备几个散列函数 当散列函数冲突时用下一个散列函数计算一个新地址直到不冲突为止 Hi RHi(Key) i1,2,3….,k
排序
排序的基本概念
定义 排序Sort就是重新排列表中的元素使表中的元素满足按关键字有序的过程。 输入n个记录R1, R2,…, Rn对应的关键字为k1, k2,…, kn。 输出输入序列的一个重排R1ʹ, R2ʹ,…, Rnʹ使得有k1ʹ≤k2ʹ≤…≤knʹ也可递减
排序算法的评价指标 时间复杂度 空间复杂度 算法的稳定性 若待排序表中有两个元素Ri和Rj其对应的关键字相同即keyi keyj且在排序前Ri在Rj的前面 若使用某一排序算法排序后Ri仍然在Rj的前面 则称这个排序算法是稳定的否则称排序算法是不稳定的。
排序算法的分类 内部排序数据都在内存中关注如何使算法时、空复杂度更低 外部排序数据太多无法全部放入内存还要关注如何使读/写磁盘次数更少
插入排序
算法思想
每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列中直到全部记录插入完成。
代码实现 算法效率分析 空间复杂度O(1) 时间复杂度主要来自对比关键字、移动元素若有 n 个元素则需要 n-1 趟处理 最好时间复杂度O(n) 共n-1趟处理每一趟只需要对比关键字1次不用移动元素 最坏时间复杂度O(n^2) 共n-1趟处理每一趟都需要从尾移到到头全部逆序 算法稳定性稳定
优化——折半插入排序
思路 先用折半查找找到应该插入的位置再移动元素 当 lowhigh 时折半查找停止应将 [low, i-1] 内的元素全部右移并将 A[0] 复制到 low 所指位置 当 A[mid]A[0] 时为了保证算法的“稳定性”应继续在 mid 所指位置右边寻找插入位置
代码实现 比起“直接插入排序”比较关键字的次数减少了但是移动元素的次数没变整体来看时间复杂度依然是O(n^2)
对链表进行插入排序 使用链表不需要对序列进行依次友谊移动元素的次数变少了 但是关键字对比的次数依然是O(n^2) 数量级整体来看时间复杂度依然是O(n^2)
希尔排序
算法思想 先追求表中元素部分有序再逐渐逼近全局有序 先将待排序表分割成若干形如 L[i, i d, i 2d,…, i kd] 的“特殊”子表对各个子表分别进行直接插入排序。缩小增量d重复上述过程直到d1为止。 代码实现 算法性能分析 空间复杂度O(1) 时间复杂度 和增量序列 d1, d2, d3… 的选择有关目前无法用数学手段证明确切的时间复杂度 最坏时间复杂度为 O(n2)当n在某个范围内时可达O(n1.3) 稳定性不稳定 适用性仅适用于顺序表不适用于链表
冒泡排序
交换排序分类 冒泡排序 选择排序
算法思想 从后往前或从前往后两两比较相邻元素的值若为逆序即A[i-1]A[i]则交换它们直到序列比较完 这样过程称为“一趟”冒泡排序 第n趟结束后最小的n个元素会“冒”到最前边 若某一趟排序没有发生“交换”说明此时已经整体有序。 可以从后往前冒泡也可以冲前往后冒泡
代码实现 算法性能分析 空间复杂度O(1) 时间复杂度 最好情况有序O(n) 最坏情况逆序O(n^2) 平均情况O(n^2) 稳定性稳定 适用性顺序表、链表都可以
快速排序
算法思想 在待排序表L[1…n]中任取一个元素pivot作为枢轴或基准通常取⾸元素 通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k1…n] 使得L[1…k-1]中的所有元素小于pivotL[k1…n]中的所有元素大于等于pivot 则pivot放在了其最终位置L(k)上这个过程称为一次“划分” 然后分别递归地对两个子表重复上述过程直至每部分内只有一个元素或空为止即所有元素放在了其最终位置上
代码实现 算法性能分析 n个结点的二叉树 最小高度 ⌊log2n⌋ 1 最大高度 n 时间复杂度O(n*递归层数) 最好时间复杂度O(nlog2n) 每次选的枢轴元素都能将序列划分成均匀的两部分 最坏时间复杂度O(n^2) 若序列原本就有序或逆序则时、空复杂度最高可优化尽量选择可以把数据中分的枢轴元素。 空间复杂度O(递归层数) 最好空间复杂度O(log2n) 最坏空间复杂度O(n) 若每一次选中的“枢轴”将待排序序列划分为很不均匀的两个部分则会导致递归深度增加算法效率变低 若初始序列有序或逆序则快速排序的性能最差因为每次选择的都是最靠边的元素 快速排序算法优化思路尽量选择可以把数据中分的枢轴元素。 选头、中、尾三个位置的元素取中间值作为枢轴元素 随机选一个元素作为枢轴元素 快速排序是所有内部排序算法中平均性能最优的排序算法 稳定性不稳定
简单选择排序
选择排序分类 简单选择排序 堆排序
算法思想
每一趟在待排序元素中选取关键字最小或最大的元素每一趟待排序序列长度-1加入有序子序列每一趟有序序列长度1
代码实现 算法性能分析 无论有序、逆序、还是乱序一定需要 n-1 趟处理 总共需要对比关键字 (n-1)(n-2)…1[n(n-1)]/2次 元素交换次数 n-1 空间复杂度O(1) 时间复杂度O(n^2) 稳定性不稳定 适用性既可以用于顺序表也可用于链表
堆排序
堆的定义 若n个关键字序列L[1…n] 满足下面某一条性质则称为堆Heap 若满足L(i)≥L(2i)且L(i)≥L(2i1) 1 ≤ i ≤n/2 则为大根堆大顶堆 即完全二叉树中任意根≥左、右 若满足L(i)≤L(2i)且L(i)≤L(2i1) 1 ≤ i ≤n/2 则为小根堆小顶堆 即完全二叉树中任意根≤左、右
建立大根堆 把所有非终端结点都检查一遍是否满足大根堆的要求如果不满足则进行调整 在顺序存储的完全二叉树中非终端结点编号 i≤⌊n/2⌋ 检查当前结点是否满足 根≥左、右若不满足将当前结点与更大的一个孩子互换 i的左孩子2i i的右孩子2i1 i的父结点⌊i/2⌋ 若元素互换破坏了下一级的堆则采用相同的方法继续往下调整小元素不断“下坠”
建立大根堆代码 基于大根堆进行排序 选择排序每一趟在待排序元素中选取关键字最大的元素加入有序子序列 堆排序每一趟完成以下工作 将堆顶元素就是最大的元素加入有序子序列与待排序序列中的最后一个元素交换 并将待排序元素序列再次调整为大根堆小元素不断“下坠” 注意大根堆获得的排序序列是递增序列小跟堆相反获得的是递减序列
代码实现大根堆排序 堆排序的效率分析 建堆的过程关键字对比次数不超过4n建堆时间复杂度O(n) 堆排序的时间复杂度 O(n) O(nlog2n) O(nlog2n) 堆排序的空间复杂度 O(1) 稳定性不稳定
堆的插入删除
基本操作 i的左孩子2i i的右孩子2i1 i的父结点⌊i/2⌋
在堆中插入新元素 对于小根堆新元素放到表尾与父节点对比若新元素比父节点更小则将二者互换。 新元素就这样一路“上升”直到无法继续上升为止
在堆中删除元素 被删除的元素用堆底元素替代 然后让该元素不断“下坠”直到无法下坠为止
关键字对比次数 每次“上升”调整只需对比关键字1次 每次“下坠”调整可能需要对比关键字2次也可能只需对比1次
归并排序
算法思想 把两个或多个已经有序的序列合并成一个 对于两个有序序列将i、j指针指向序列的表头选择更小的一个放入k所指的位置 ki/j指向更小元素的指针 只剩一个子表未合并时可以将该表的剩余元素全部加到总表 m路归并每选出一个小的元素需要对比关键字m-1次 核心操作把数组内的两个有序序列归并为一个 代码实现 low是数组中第一个有序序列的开始 mid是数组中第一个有序序列的结尾 high是数组中第二个有序序列的结尾 辅助数组B临时存放这两段有序序列
算法效率分析 2路归并的“归并树”形态上就是一棵倒立的二叉树 二叉树的第h层最多有2 ^ (h-1)个结点若树高为h则应满足n 2 ^ (h-1)即h − 1 ⌈log2n⌉ n个元素进行2路归并排序归并趟数⌈log2n⌉ 每趟归并时间复杂度为O(n)则算法时间复杂度O(nlog2n) 空间复杂度O(n)来自于辅助数组B 稳定性稳定
基数排序
算法思想 基数排序得到递减序列的过程如下 初始化 设置 r 个空队列Qr-1, Qr-2,…, Q0 按照各个 关键字位 权重递增的次序个、十、百对 d 个关键字位分别做“分配”和“收集” 分配顺序扫描各个元素若当前处理的关键字位x则将元素插入 Qx 队尾 收集把 Qr-1, Qr-2,…, Q0 各个队列中的结点依次出队并链接
基数排序得到递增序列的过程如下 初始化 设置 r 个空队列Q0, Q1,…, Qr−1 按照各个 关键字位 权重递增的次序个、十、百对 d 个关键字位分别做“分配”和“收集” 分配顺序扫描各个元素若当前处理的关键字位x则将元素插入 Qx 队尾 收集把 Q0, Q1,…, Qr−1 各个队列中的结点依次出队并链接
算法效率分析 需要r个辅助队列空间复杂度 O® 一趟分配O(n)一趟收集O®总共 d 趟分配、收集总的时间复杂度O(d(nr) 稳定性稳定
基数排序的应用 例如 某学校有10000名学生将学生信息按照年龄递减排序 给十亿人的身份证号排序 基数排序擅长解决的问题 数据元素的关键字可以方便地拆分为 d 组且 d 较小 每组关键字的取值范围不大即 r 较小 数据元素个数 n 较大
外部排序
外存、内存的数据交换 外存 操作系统以“块”为单位对磁盘存储空间进行管理 如每块大小 1KB各个磁盘块内存放着各种各样的数据 内存 磁盘的读/写以“块”为单位 数据读入内存后才能被修改 修改完了还要写回磁盘
外部排序原理 数据元素太多无法一次全部读入内存进行排序 使用“归并排序”的方法最少只需在内存或只能怪分配3块大小的缓冲区即可对任意一个大文件进行排序 ”归并排序“要求各个子序列有序每次读入两个块的内容进行内部排序后写回磁盘
构造初始“归并段” 若有N个记录内存工作区可以容纳L个记录则初始归并段数量rN/L
第一趟归并 第二趟归并 第三趟归并 时间开销分析
外部排序时间开销读写外存的时间内部排序所需时间内部归并所需时间
优化思路 多路归并 采用多路归并可以减少归并趟数从而减少磁盘I/O(读写)次数 对 r 个初始归并段做k路归并则归并树可用 k 叉树表示若树高为h则归并趟数 h-1 ⌈logkr⌉ 推导k叉树第h层最多有k^(h−1) 个结点则r ≤ kh−1 (h-1)最小 ⌈logkr⌉ k越大r越小归并趟数越少读写磁盘次数越少 多路归并带来的负面影响 k路归并时需要开辟k个输入缓冲区内存开销增加 每挑选一个关键字需要对比关键字k-1次内部归并所需时间增加可使用败者树优化 减少初始归并段数量 生成初始归并段的“内存工作区”越大初始归并段越长
败者树
定义 可视为一棵完全二叉树多了一个头头 k个叶结点分别是当前参加比较的元素非叶子结点用来记忆左右子树中的“失败者”而让胜者往上继续进行比较一直到根结点。 即失败者留在这一回合胜利者进入下一回合比拼
败者树在多路平衡归并中的应用 败者树的存储结构 置换-选择排序 使用置换-选择排序可以让每个初始归并段的长度超过内存工作区大小的限制 设初始待排文件为FI初始归并段输出文件为FO内存工作区为WAFO和WA的初始状态为空WA可容纳w个记录。 置换-选择算法的步骤如下 从FI输入w个记录到工作区WA。 从WA中选出其中关键字取最小值的记录记为MINIMAX记录。 将MINIMAX记录输出到FO中去。 若FI不空则从FI输入下一个记录到WA中。 从WA中所有关键字比MINIMAX记录的关键字大的记录中选出最小关键字记录作为新的MINIMAX记录。 重复35直至在WA中选不出新的MINIMAX记录为止由此得到一个初始归并段输出一个归并段的结束标志到FO中去。 重复26直至WA为空。由此得到全部初始归并段。
最佳归并树
引子 归并过程中磁盘I/O次数归并树的WPL*2 因此要让磁盘I/O次数最小就要使归并树的WPL最小即构建一个哈夫曼树
m叉最佳归并树的构造 注意对于k叉归并若初始归并段的数量无法构成严格的k叉归并树 则需要补充几个长度为0的“虚段”再进行k叉哈夫曼树的构造
增加虚段的数量 若初始归并段数量 -1% k-1 0说明刚好可以构成严格k叉树此时不需要添加虚段 若初始归并段数量 -1% k-1 u ≠ 0则需要补充 (k-1) - u 个虚段 数据结构算法
1.数组
1.1.将一个数组前后翻转 bool Delete_Min(int A[], n, min) {if (!n) return false; //数组长度为0返回falseint temp INT_MAX, m; //INT_MAX为int类型的最大值for (int i 0; i n; i) { //遍历数组找到数组当前的最小元素if (A[i] temp) {temp A[i]; //更新数组最小值m i; //记录数组下标}}min temp; //min保存最小值A[m] A[n - 1]; //m用数组中最后一个元素替换return true;
}1.2.删除数组中值为x的元素 int DeleteX(int A[], x, n){int i 0, j 0;for (i 0; i n; i) {if (A[i] ! x) { //当前元素的值不为xA[j] A[i]; //将其保存到数组下标为j的元素中j;}}n j; return n; //返回删除x后的数组元素个数
}1.3.将两个有序数组合并成一个有序数组 int* Merge(int A[], B[], lenA, lenB) {int *C (int*)malloc((lenA lenB) * sizeof(int));int a 0, b 0, c 0;for (c 0; a lenA b lenB; c) { //选择两个数组中的较小值放入数组C中if (A[a] B[b]) C[c] A[a];else C[c] B[b];}while (a lenA) C[c] A[a]; //将剩余数组放入C中while (b lenB) C[c] B[b];return C;
}1.4.真题 void ans(int A[], n, p){int B[n], i, j;for (i 0, j p; j n; i, j) B[i] A[j]; //数组后部分前移for (j 0; j p; i, j) B[i] A[j]; //数组前部分后移for (i 0; i n; i) cout B[i]; //输出循环前移后的数组
}int res(int A[], int B[], int n){int i, j, k, mid;for (i 0, j 0, k 0; k n; k){if (A[i] B[j]) { //当前A数组的元素小保存A[i]mid A[i];i; } else { //当前B数组的元素小保存B[j]mid B[j];j;}}return mid;
}void Qsort(int A[], L, R){if (L R) return; //当前数组区间 1返回随机选择数组中一个元素和A[L]交换 //快速排序优化使得基准元素的选取随机int key A[L], i L, j R; //选择A[L]作为基准元素i和j分别为左右指针while(i j) {while (i j key A[j]) j--;while (i j A[i] key) i;if (i j) swap(A[i], A[j]); //交换A[i]和A[j]}swap(A[i], A[L]);Qsort(A, L, i - 1); //递归排序左区间Qsort(A, i 1, R); //递归排序右区间
}int ans(int A[], int B[], int n) {int C[2n], i, j;for (i 0; i n; i) C[i] A[i]; //复制数组A和数组B的元素for (j 0; j n; i, j) C[i] B[j];Qsort(C, 0, 2n - 1); //对数组C进行快速排序return C[n - 1]; //返回中位数
}int ans(int A[], n){int count[n];for (int i 0; i n; i) count[i] 0; //初始化count数组//遍历A数组其元素的值作为count数组下标的元素1表示该元素在A数组中出现次数for (int i 0; i n; i) count[A[i]]; for (int i 0; i n; i) { //当前元素出现次数符合主元素定义if (count[i] n / 2) return i; //返回i即该元素的值}return -1; //没有元素符合主元素定义
}int ans(int A[], n) {bool B[n 2]; //B用来标记数组中出现的正整数for (int i 0; i n; i) B[i] false; //初始化B数组int count 0;for (int i 0; i n; i) {if (A[i] 0 A[i] n){ //当前数组元素为正并且在数组B的下标范围内count A[i];B[count] true;} }for (int i 1; i n; i) {if (B[i] false) return i; //返回数组B中第一个false的元素下标}
}void Qsort(int A[], L, R) {if (L R) return; //数组区间 1返回随机选择数组中一元素和A[L]交换;//快排优化使得基准元素的选取随机int key A[L], i L, j R; //A[L]为基准元素ij为左右指针while (i j) {while (i j key A[j]) j--;while (i j A[i] key) i;if (i j) Swap(A[i], A[j]); //交换A[i]和A[j]}Swap(A[L], A[i]);Qsort(A, L, i - 1); //递归排序左区间Qsort(A, i 1, R); //递归排序右区间
}int ans(int A[], n) {Qsort(A, 0, n - 1); //快速排序int i 0;while (A[i] 0) i; //找到数组中第一个大于0的元素if (n i) return 1; //数组中没有元素大于0返回1else {if (A[i] ! 1) return 1; //第一个整数不是1则返回1else { //第一个整数为1找到数组中正整数第一个间断点int j i 1;while (j n) {if (a[j] a[j - 1]) j; //相邻元素相等else if (a[j] a[j - 1] 1) j; //相邻元素是连续数else return A[j - 1] 1; //相邻元素是间断点}//while}//else}//else
}int Dis(int a, b, c){int res abs(a - b) abs(a - c) abs(b - c); //计算绝对值return res;
}int Ans(int A[], int B[], int C[], int n1, int n2, int n3){int min INT_MAX, i, j, k, temp; //min取整型的最大值for (int i 0; i n1; i) { //循环遍历数组Afor (int j 0; j n2; j) { //循环遍历数组Bfor (int k 0; k n3; k) { //循环遍历数组Ctemp Dis(A[i], B[j], C[k]);if (temp min) min temp; //当前元素之间的距离更小更新最小距离}//for}//for}//forreturn min; //返回最小距离
}2.链表
2.1.链表的数据结构定义
2.1.1.单链表
typedef struct LNode {struct LNode *next;int data;
}LNode, *LinkList;2.1.2.双链表
typedef struct LNode {struct LNode *prior, *next;int data;
}LNode, *LinkList;2.2.链表的操作
2.2.1.头插法插入到链表头
void HeadInsert(LinkList L, int key) {LNode *p (LNode*)malloc(sizeof(LNode));p-data key;p-next L-next;L-next q;
}2.2.2.尾插法插入到链表尾
void TailInsert(LinkList L, int key) {LNode *q (LNode*)malloc(sizeof(LNode);q-data key;q-next NULL;LNode *p L-next, *pre L;while (!p) {pre p;p p-next;}pre-next q;
}2.2.3.链表逆置头插法实现
void Reverse(LinkList L) {LNode *p L-next, *q NULL;L-next NULL; //将L表断开while (!p) {q p-next; //q指向p的下一个结点p-next L-next; //头插法L-next p;p q;}
}2.2.4.链表的遍历
LNode *p L-next;
while (!p) {visit(p);p p-next;
}2.2.5.链表的删除
void Delete(LinkList L, int key) {LNode *p L-next, *pre L;移动p和pre到指定结点 //pre指向p的前驱结点key p-data; //key保存p的data领pre-next p-next; //pre的next指针指向p的后继节点free(p);
}2.3.链表算法题
2.3.1.删除值为x的结点
void DeleteX(LinkList L, int x){LNode *p L-next, *pre L;while (p) {if (p-data x) { //当前元素值为xpre-next p-next;free(p);p pre-next;} else { //当前元素值非xp和pre向后移动p p-next;pre pre-next;}}
}2.3.2.单链表就地逆置 void reverse(LinkList L){LNode *p L-next, *q;L-next NULL; //断链while (p) {q p-next; //q指向p的下一个结点p-next L-next; //头插法L-next p;p q;}
}2.3.3.将链表排序 LNode *Sort(LinkList L) {LNode* p (LNode*)malloc(sizeof(Lnode));p-next NULL;LNode* t L-next, * tpre L, *min, *minpre, *r p;int m INT_MAX;while (t) {while (t) { //遍历链表if (t-data m) { //更新最小值结点min t;minpre tpre;m t-data;}//iftpre t;t t-next;}//whileminpre-next min-next; //将min从L中删除r-next min; //将min插入pr min; //r后移m INT_MAX; //重新初始化t L-next;tpre L;}//whiler-next NULL;return p;
}2.3.4.拆分链表 LNode* (LinkList L) {LNode *p (LNode*)malloc(sizeof(LNode);p-next NULL; //p为新链的头结点LNode *q L-next, *t NULL, *r L;r-next NULL; //r结点始终指向L的最后一个结点while (q) {t q-next;r-next q; //奇数结点尾插法r q;q t;t q-next;q-next p-next; //偶数节点头插法p-next q;q t;}r-next NULL; //将r的next指针置空return p;
}2.3.5.删除链表中的重复元素 void Delete(LinkList L) {LNode *p L-next;while (p) {LNode *post p-next; //post指向p的下一个结点while (post post-data p-data) { //post存在并且值和p相等时LNode *temp post; //temp指向postpost post-next; //post向后移动p-next post; //将p的下一个结点修改为postfree(temp);}p p-next;}
}2.3.6.将两个递增链表合并成一个递减链表 void Merge(LinkList L1, LinkList L2) {LNode *p L1-next, *q L2-next, *temp;L1-next NULL; //L1断链while (p q) {if (p-data q-data) { //当前p指向的元素更小temp p-next; //temp指向p的下一个结点p-next L1-next; //将p用头插法插入L1L1-next p;p temp; //p指向temp} else { //当前q指向的元素更小temp q-next;q-next L1-next;L1-next q;q temp;}}//whilewhile (p) { //将剩余节点插入L1temp p-next;p-next L1-next;L1-next p;p temp;}while (q) {temp q-next;q-next L1-next;L1-next q;q temp;}return;
}2.3.7.将两个递增链表合并为一个递增链表
LNode *Merge(LinkList L1, LinkList L2) {LNode *p L1-next, *q L2-next, *r, *temp;LNode *L (LNode*)malloc(sizeof(LNode));L-next NULL;r L;while (p q) {if (p-data q-data) { //当前p指向的结点小于等于qtemp p-next;r-next p; //p尾插法插入L中r p;p temp;} else {temp q-next;r-next q;r q;q temp;}}while (p) { //插入剩余结点temp p-next;r-next p;r p;p temp;}while (q) {temp q-next;r-next q;r q;q temp;}r-next NULL; //将r的next指针置空return L;
}2.3.8.判断链表是否对称 bool ans(LinkList L) {LNode* post L-prior, * pre L-next; //前后指针//表中元素为奇数时终止条件为两者移动到同一结点//表中元素为偶数时终止条件为两者后指针的next指向前指针while (post ! pre post-next ! pre) { if (post-data ! pre-data) return false; //前后指针的指针域不相等pre pre-next; //前指针前移post post-prior; //后指针后移}//表对称return true;
}bool ans(LinkList L) {LNode* p L-next;int len 0; //记录表中的元素个数while (p ! L) {p p-next;len;}int a (int*)malloc(len * sizeof(int)); //定义跟链表结点个数相等的长度的数组len 0;p L-nextwhile (p ! L) { //遍历链表用数组保存链表中每个结点的值a[len] p-next;p p-next;}//遍历数组前后指针指向元素的值不相等返回falsefor (int i 0, j len - 1; i j; i, j--) {if (a[i] ! a[j]) return false;}return true;
}2.3.9.依次输出链表中结点值最小的元素 void DeleteMin(LinkList L) {LNode *p L-next, *ppre L-next, *min, *minpre;while (L-next ! L) {p L-next;ppre L;int tempMin INT_MAX; //当前最小值while (p ! L) {if (p-data tempMin) { //当前结点值更小更新最小结点min p;minpre ppre;} //p向后移动ppre p;p p-next;}cout min-data; //输出最小结点的值minpre-next min-next; //删除min结点free(min);}//whilefree(L); //删除头结点
}2.3.10.真题 void ans(LinkList L, int k){LNode *p L-link, *q L-link;for (int i 0; i k; i) p p-link; //p指针向后移动k个结点while (p) {p p-link;q q-link;}cout q-data;
}void ans(LinkList str1, LinkList str2) {LNode *p str1-next, *q str2-next;int len1 0, len2 0;while (p) { //遍历str1得到str1的长度len1;p p-next;}while (q) { //遍历str2得到str2的长度len2;q q-next;}int len abs(len1 - len2); //得到两表长度之差p str1-next; //重置pq指向第一个结点q str2-next;if (len1 len2) { //长表向前移动使得两表剩余元素相等for (int i 0; i len; i) p p-next;}else {for (int i 0; i len; i) q q-next;}while (p) { //遍历剩余结点找到两者指向的第一个共同结点if (p q) return p;p p-next;q q-next;}return NULL; //两者没有共同后缀
}void ans(LinkList L){bool A[n 1]; //长度为n 1的数组用来标记该数是否出现过for (int i 0; i n 1; i) A[i] false; //初始化A数组LNode *p head-next, *pre head;while (p) {int t abs(p-data); //取当前结点值的绝对值if (A[t]) { //该值出现过删除该结点LNode *r p-next;pre-next r;free(p);p r;} else { //该值没有出现过在数组A中标记该值p和pre向后移动A[t] true;pre p;p p-next;}}//while
}void ans(NODE *L) {NODE* p L-next, *f L-next, *s L-next, *q, *t;while (f-next-next f-next) { //找到前半链的最后一个结点f f-next-next; //快指针移动两个结点s s-next; //慢指针移动一个结点}q s-next; //q指向后半链的第一个结点s-next NULL; //前半链后半链断开LNode* post (NODE*)malloc(sizeof(NODE));post-next NULL;while (q) { //后半链逆置t q-next;q-next post-next;post-next q;q t;}q post-next; //q指向逆置后的后半链的第一个结点while (q) {r q-next; //r指向后半链的下一个结点t p-next; //t指向前半链下一个插入位置q-next p-next;p-next q;q r; //重置pqp t;}
}3.栈
3.1.栈的数据结构定义
3.1.1.顺序栈
#define MAXSIZE 100typedef struct Stack {int data[MAXSIZE];int top -1;
}Stack;3.1.2.链栈
typedef struct LStack {int data;struct LStack *next;
}SNode, *LStack;3.2.顺序栈的操作
3.2.1.栈的初始化
void InitStack (Stack S) {S.top -1;
}3.2.2.入栈
bool Push(Stack S, int key) {if (S.top MAXSIZE - 1) return false; //栈满S.data[top] key;return true;
}3.2.3.出栈
bool Pop (Stack S, int key) {if (S.top -1) return false; //栈空key S.data[top--];return true;
}3.2.4.判断栈空
bool IsEmpty (Stack S) {if (S.top -1) return true;else return false;
}3.3.链栈的基本操作
3.3.1.初始化
void InitStack (LStack S) {SNode *s (SNode*)malloc(Sizeof(SNode));S-next NULL;
}3.3.2.入栈
void Push (LStack S, int key) {SNode *p (SNode*)malloc(sizeof(SNode));p-data key;p-next S-next; //头插法S-next p;
}3.3.3.出栈
bool Pop (LStack S, int key) {if (S-next NULL) return false; //栈空SNode *p S-next;key p-data; //key保存栈顶元素的值S-next p-next;free(p);
}3.3.4.判断栈空
bool IsEmpty(LStack S) {if (S-next NULL) return true;else return false;
}4.队列
4.1.队列的数据结构定义
4.1.1.顺序队列
#define MAXSIZE 100
typedef struct Queue {int data[MAXSIZE];int front, rear;
}Queue;4.1.2.链式队列
typedef struct LNode{struct LNode *next;int data;
}LNode;typedef struct Queue{LNode *front, *rear;
}Queue;4.2.顺序队列的基本操作
4.2.1.初始化
void InitQueue(Queue Q){Q.front Q.rear 0;
}4.2.2.入队
bool EnQueue(Queue Q, int key){if (Q.front (Q.rear 1) % MAXSIZE) return false; //队满Q.data[rear] key;Q.rear (Q.rear 1) % MAXSIZE;return true;
}4.2.3.出队
bool DeQueue(Queue Q, int key){if (Q.rear Q.front) return false; //队空key Q.front;Q.front (Q.front 1) % MAXSIZE;return true;
}4.2.4.判断队空
bool IsEmpty(Queue Q){if (Q.front Q.rear) return true;else return false;
}4.3.链式队列的基本操作
4.3.1.初始化
void InitQueue(Queue Q){Q.front Q.rear (LNode*)maloc(sizeof(LNode));Q.front-next NULL;
}4.3.2.入队
void Queue(Queue Q, int key){LNode *p (LNode*)malloc(sizeof(LNode)); //申明一个新结点p-data key;p-next NULL;Q.rear-next p; //尾插法插入到rear后Q.rear p; //更新rear
}4.3.3.出队
bool DeQueue(Queue Q, int key){if (Q.front Q.rear) return false; //队空LNode *p Q.front-next;key p-data; //保存队首元素的数据Q.front-next p-next;if (Q.rear p) Q.rear Q.front; //队列中只有一个元素free(p);return true;
}4.3.4.判断队空
bool IsEmpty(Queue Q){if (Q.rear Q.front) return true;else return false;
}5.树
5.1.树的数据结构定义
5.1.1.二叉树的链式存储
typedef struct BiTree{sturct BiTree *lchild, *rchild; //左右孩子指针int value; //结点数据
}BiTNode, *BiTree;5.1.2.二叉树的顺序存储
#define MAXSIZE 100typedef struct TreeNode{int value; //结点数据bool IsEmpty; //该结点是否存在
}TreeNode;void InitTree(TreeNode T[], int len){for (int i 0; i len; i) T[i].IsEmpty true; //将该结点初始化为空结点
}int main(){TreeNode T[MAXSIZE]; //申明一个长度为MAXSIZE的TreeNode数组InitTree(T); //初始化树...
}5.1.3.双亲表示法
#define MAXSIZE 100 //树中最多结点数typedef struct TreeNode{int data; //结点数据int parent; //该结点的双亲结点在数组的下标
}TreeNode;typedef struct Tree{TreeNode T[MAXSIZE]; //长度为MAXSIZE的TreeNode类型的数组int treeNum; //结点数
}Tree;5.1.4.孩子表示法
#define MAXSIZE 100//孩子结点
typedef struct Child{int index; //该结点的编号struct Child *next; //指向该结点的下一个孩子结点的指针
}Child;//结点信息
typedef struct TreeNode{Child *firstTNode; //指向该结点的第一个孩子结点的指针int data; //该结点数据
}TreeNode;TreeNode T[MAXSIZE]; //定义一个长度为MAXSIZE的树5.1.5.孩子兄弟表示法
#define MAXSIZE 100typedef struct CSNode{struct CSNode *firstChild, *nextSibling; //指向第一个孩子和右兄弟节点int data; //该结点数据
}CSNode;5.1.6.线索二叉树
typedef struct ThreadNode{struct ThreadNode *lchild, *rchild; //左右孩子指针int ltag, rtag; //左右线索标志int data; //结点数据
}ThreadNode, *ThreadTree;5.2.二叉树的基本操作
5.2.1.先序遍历
void PreOrder(BiTree T){if (T) {visit(T);PreOrder(T-lchild);PreOrder(T-rchild);}
}5.2.2.中序遍历
void InOrder(BiTree T){if (T) {InOrder(T-lchild);visit(T);InOrder(T-rchild);}
}5.2.3.后序遍历
void PostOrder(BiTree T){if (T) {PostOrder(T-lchild);PostOrder(T-rchild);visit(T);}
}typedef struct Stack{BiTNode *Node[MAXSIZE];int top;
}Stack;void PostOrder(BiTree T){Stack S;InitStack(S);BiTNode *p, *pre;while (p || !IsEmpty(S){if (p) { //往左下走到尽头Push(p); //p入栈p p-lchild; //进入其左子树} else {GetTop(S, p); //查看栈顶元素//栈顶元素的右孩子存在并且不是上一个访问的结点if (p-rchild p-rchild ! pre) {p p-rchild; //进入栈顶元素的右子树Push(p); //该结点入栈p p-lchild; //进入该结点左子树} else { //栈顶元素的右孩子被访问过Pop(S, p); //弹出栈顶元素visit(p); //访问该结点pre p; //用pre标记该结点p NULL; //将p置空}//if}//if}//whil
}5.2.4.层次遍历
void LevelOrder(BiTree T){InitQueue(Q);EnQueue(Q, T);BiTNode *p;while (!IsEmpty(Q)) {DeQueue(Q, p);visit(p);if (p-lchild) EnQueue(Q, p-lchild);if (p-rchild) EnQueue(Q, p-rchild);}
}5.3.并查集
5.3.1.并查集的定义和初始化
#define MAXSIZE 100
int UFSet[MAXSIZE]; //并查集通过数组表示void InitSet(int S[]){for(int i 0; i MAXSIZE; i) S[i] -1;
}5.3.2.FIND操作
//FIND操作用于查找该结点的所属集合
int Find(int S[], int x) {while (S[x] 0) x S[x]; //递归寻找直到该结点的值为负数该树的根节点return x;
}5.3.3.UNION操作
void Union(int S[], root1, root2) {//要求root1和root2是不同的集合if (root1 root2) return;//将root2合并到root1中S[root2] root1;
}5.3.4.FIND优化——压缩路径
//先找到根节点然后进行压缩路径
int Find(int S[], x) {int root x;while (S[root] 0) root S[root]; //循环找到当前结点的根节点while (x ! root) { //循环直到x指向根节点int temp S[x]; //用temp保存x的父结点S[x] root; //将结点x的父节点修改为根节点x temp; //x更新为原父节点}
}5.3.5.UNION优化——小树合并大树
//数组中根节点的值为其集合中结点的总数
void Union(int S[], root1, root2){if (root1 root2) return;if (root1 root2) { //root1的结点数更多或者二者相等S[root1] S[root2]; //更新root1的结点数为root1和root2的总和S[root2] root1; //将root2合并到root1中} else { //root2的结点数更多S[root2] S[root1];S[root1] root2;}
}5.4.二叉树算法题
5.4.1.计算二叉树中双分支结点的个数 int count 0; //双分支结点个数void PreOrder(BiTree T){if (T) {//当前结点的左右孩子都存在countif (T-lchild T-rchild) count;if (T-lchild) PreOrder(T-lchild); //递归遍历左子树if (T-rchild) Preorder(T-rchild); //递归遍历右子树
}void ans(BiTree T) {PreOrder(T); //先序遍历该树cout count; //输出双分支结点个数
}5.4.2.交换二叉树中所有左右子树 void PostOrder(BiTree T){if (T) {PostOrder(T-lchild);PostOrder(T-rchild);BiTNode *t T-lchild;T-lchild T-rchild;T-rchild t;}
}void ans(BiTree T){Post(Order(T));return;
}5.4.3.求先序遍历第k个元素 int t 0;
int res 0;void PreOrder(BiTree T) {if (T) {t--;if (t 0) res T-data; //第k个结点用res保存当前结点的值PreOrder(T-lchild); //递归访问左子树PreOrder(T-rchild); //递归访问右子树}
}void ans(BiTree T, int k) {t k;PreOrder(T);cout res; //输出第k个结点的值
}5.4.4.删去值为x的子树 int k;void Delete(BiTree T){ //后序遍历的方式删除结点if (T) {DeleteX(T-lchild);DeleteX(T-rchild);free(T);}
}void PreOrder(BiTree T) {if (T) {BiTNode *t;if (T-lchild-data k) { //左子树的值为x删除左子树t T-lchild;T-lchild NULL;Delete(t);}if (T-rchild-data k) { //右子树的值为x删除右子树t t-rchild;T-rchild NULL;Delete(t);}if (T-lchild) PreOrder(T-lchild); //递归遍历左子树if (T-rchild) PreOrder(T-rchild); //递归遍历右子树}//if
} void ans(BiTree T, int x){k x;if (T-data x) { //根节点的值为x删除整个树并返回Delete(T);return;} else PreOrder(T); //先序遍历x
}void Delete(BiTree T) { //后序遍历并删除结点if (T) {Delete(T-lchild);Delete(T-rchild);free(T);}
}void LevelOrder(BiTree T, int x){if (T-data x) { //根节点的值为x删除整个树并返回Delete(T);return;}Queue Q;InitQueue(Q); //初始化队列BiTNode *p T;EnQueue(Q, p); //根节点入队while (!IsEmpty(Q)) {DeQueue(Q, p);if (p-lchild) {if (p-lchild-data x) {BiTNode *q p-lchild;p-lchild NULL; //左孩子指针置空Delete(q); //以q为根节点的子树} else EnQueue(Q, p);}if (p-rchild) { {}if (p-rchild-data x) {BiTNode *q p-rchild;p-rchild NULL;Delete(q);} else EnQueue(Q, p);}}//while
}5.4.5.查找二叉树中两个结点的公共祖先结点 BiTNode *ans(BiTree ROOT, BiTNode *p, BiTNode *q) {Stack S, Sp, Sq; //Sp和Sq分别用来保存p和q的祖先结点S.top -1; //初始化队列BiTNode* t ROOT, *pre NULL;while (t || S.top 0) {if (t) { //t结点非空S.data[S.top] t; //t结点入队t t-lchild; //进入t的左子树}else { //t结点为空t S.data[S.top]; //查看栈顶元素//t的右子树存在并且上一个访问的并不是其右子树if (t-rchild t-rchild ! pre) { t t-rchild; //进入右子树S.data[S.top] t; //入栈该结点t t-rchild; //进入左子树}else { //右子树不存在或者存在但是上一个访问的是右子树S.top--; //出栈该结点并访问if (t p) { //当前结点为p保存栈中内容即其所有祖先结点for (int i 0; i S.top; i) Sp.data[i] S.data[i];Sp.top S.top;}if (t q) { //当前结点为q保存栈中内容即其所有祖先结点for (int i 0; i S.top; i) Sq.data[i] S.data[i];Sq.top S.top;}}//if}//if}//while//自栈顶到栈顶分别遍历Sp和Sq找到最接近栈顶的相同祖先结点for (int i Sp.top; i 0; i--) { for (int j Sq.top; i 0; j--) {if (Sp.data[i] Sq.data[j]) return Sp.data[i];}}return NULL; //无相同祖先顶点
}5.4.6.求二叉树的宽度 typedef struct Queue{BiTNode *data[MAXSIZE]; //足够大的数组int front, rear;
}Queue;int ans(BiTree T){if (!T) return 0; //空树返回0BiTNode *p T;Queue Q;InitQueue(Q); //初始化队列EnQueue(Q, p); //将p入队//rear指向当前层的最后一个结点count记录当前层的结点数max记录最大结点数int last Q.rear, count 0, max INT_MIN; while (!IsEmpty(Q) {DeQueue(Q, p);count; //结点数1if (p-lchild) EnQueue(Q, p-lchild); //p的左子树存在左子树入队if (p-rchild) EnQueue(Q, p-rchild); //p的右孩子存在右孩子入队if (last Q.front) { //当前结点是本层的最后一个节点last Q.rear; //last指向下一层的最后一个结点if (count max) max temp; //更新最大结点数count 0; //结点数归零}}//whilereturn max;
}typedef struct Queue { //足够大的非循环数组BiTNode *data[MAXSIZE]; //结点数组保存每个结点int level[MAXSIZE]; //层数数组记录每个结点的层数int front, rear; //头尾指针
}Queue;int ans(BiTree T) {BiTNode* p T;Queue Q;Q.rear Q.front 0; //初始化队列if (T) {Q.data[Q.rear] T; //根节点入队Q.level[Q.rear] 1;Q.rear;while (Q.front Q.rear) {p Q.data[Q.front]; //出队队首元素int level Q.level[Q.front]; //保存当前结点的层数Q.front;if (p-lchild) { //左孩子入队Q.data[Q.rear] p-lchild;Q.level[Q.rear] level 1;Q.rear;}if (p-rchild) { //右孩子入队Q.data[Q.rear] p-rchild;Q.level[Q.rear] level 1;Q.rear;}}//whileint max INT_MIN, i 0, level 1;while (i Q.rear) {int count 0; //记录当前层的结点数while (i Q.rear level Q.level[i]) {count;i;}if (count max) max count; //更新每层的最大结点数level Q.level[i]; //更新层数while循环结束时i指向下一层的第一个结点}//whilereturn max; //返回最大结点数}else return 0; //空树返回0
}5.4.7.求二叉树的高度
int Get_Heigh(BiTree T) {int front 0, rear 0; //前后指针BiTNode* p T;BiTNode *data[MAXSIZE]; //足够大的队列元素是二叉树结点data[rear] p; //根节点入队int last rear, level 0; //rear标记本层最后一个结点, level记录当前层数while (front rear) { //循环直到队空p data[front]; //出队队首结点if (p-lchild) data[Q.rear] p-lchild; //左右孩子入队if (p-rchild) data[Q.rear] p-rchild;if (last front) { //当前结点为本层的最后一个结点last rear; //标记下层的最后一个结点level; //层数1}}//whilereturn level;
}int Get_High(BiTree T){if (!T) return 0; //空树返回0else {int hl Get_High(T-lchild); //递归求左右子树高度int hr Get_High(T-rchild);int maxH max(hl, hr) 1; //树高等于左右子树更高的那个1return maxH;}
}5.4.8.排序二叉树的判定
int pre INT_MIN; //标记上一个结点的值初始值为INT类型的最小值int JudgeBST(BiTree T) {if (!T) return 1; //空树是排序二叉树else {int l JudgeBST(T-lchild); //判断左子树//当前值小于等于pre的值或左子树不满足排序二叉树定义返回0if (T-data pre|| l 0) return 0;pre T-data; //更新pre为当前结点值int r JudgeBST(T-rchild); //判断右子树return r;}
}int A[n]; //足够大的数组保存每个节点的值
int count 0; //记录结点个数void InOrder(BiTree T) {if (T) {InOrder(T-lchild); A[count] T-data; //记录当前结点值并且count1InOrder(T-rchild);}
}bool ans(BiTree T) {if (!T) return true; //空树为排序二叉树else if (!T-lchild !T-rchild) return true; //只有根节点是排序二叉树else {InOrder(T); //中序遍历二叉树并且记录每个结点的值for (int i 0; i count - 1; i) {if (A[i] A[i 1]) return false; //非排序二叉树}return true; //排序二叉树}
}5.4.9.平衡二叉树的判定
int Get_Height(BiTree T) {if (!T) return 0;else {int hl Get_Height(T-lchild); //递归求左子树高度int hr Get_Height(T-rchild); //递归求右子树高度int maxH max(hl, hr) 1; //树高为左右子树更高的那个 1return maxH; }
}bool JudgeBalance(BiTree T) {if (!T) return true; //空树为平衡二叉树else {int hl Get_Height(T-lchild); //左子树高度int hr Get_Height(T-rchild); //右子树高度//当前结点的左右平衡因子小于等于1递归判断其左右子树是否满足平衡二叉树if (abs(hl - hr) 1) {return JudgeBalance(T-lchild) JudgeBalance(T-rchild);}//当前节点左右平衡因子大于1则已不满足平衡二叉树无需判断左右子树返回falseelse return false;}
}5.4.10.完全二叉树的判定
①采用层次遍历的思想与一般层次遍历的区别是空结点也能入队
②当出队元素为空时设该结点为P进入内层循环即③逐一出队并检查该结点是否为空。
③若队中剩余元素有不为空的结点则说明P之后还有结点这个结点可能是与P同层或是P的下一层即不满足完全二叉树的定义若队中剩余元素皆为空结点说明P是该树的最后一个结点最底层的最右结点满足完全二叉树的定义
bool JudgeComplete(BiTree T) {BiTNode* data[MAXSIZE]; //足够大的队列int front 0, rear 0; //头尾指针BiTNode* p T; data[rear] T; //根节点入队while (front rear) { //循环直到队空p data[front]; //出队队首元素if (p) { //p结点存在入队左右孩子data[rear] p-lchild;data[rear] p-rchild;}else { //p结点不存在出队剩余元素while (front rear) {p data[front];if (p) return false; //当前元素为非空则为非完全二叉树}}}return true;
}5.4.11.真题 int WPL 0;void InOrder(BiTree T, int deep){if (T) {if (!T-left !T-right) { //叶子结点WPL WPL T.weight * deep; //更新WPL}if (T-left) InOrder(T-left, deep 1);if (T-right) InOrder(T-right, deep 1);}
}int ans(BiTree T){InOrder(T, 0);return WPL;
}int Get_WPL(BiTree root) {BiTNode* data[MAXSIZE]; //足够大的非循环数组BiTNode* p root;int f 0, r 0, level 0, WPL 0, last 0; data[r] p; //根节点入队last r; //last标记本层的最后一个元素while (f r) {p data[f]; //队首元素出队//该结点为叶子结点计算WPLif (!p-lchild !p-rchild) WPL WPL level * p-weight;if (p-lchild) data[r] p-left; //左右孩子入队if (p-rchild) data[r] p-right;if (last f) { //该结点为本层的最后一个结点last r; //更新last和levellevel;}}return WPL;
}void InOrder(BiTree T, int deep){if (T) {if (deep 1 (T-lchild || T-rchild)) cout (; //分支节点打印左括号if (T-lchild) InOrder(T-lchild, deep 1);cout T-data;if (T-rchild) InOrder(T-rchild, deep 1);if (deep 1 (T-lchild || T-rchild)) cout ); //分支节点打印右括号}
}void ans(BiTree T){InOrder(T, 1);
}6.图
6.1.图的数据结构定义
6.1.1.邻接矩阵
#define MAXVEX 100
typedef struct Graph {int data[MAXVEX]; //一维数组存放顶点数据int edge[MAXVEX][MAXVEX]; //二维数组存放边数据权值int vexNum, edgeNum; //顶点总数和边总数
}Graph;6.1.2.邻接表
#define MAXVEX 100
typedef struct edgeNode { //边struct edgeNode *next; //指向下一条邻接边的指针int weight; //该邻接边权值int adjVex; //该邻接边指向的顶点编号
}edgeNode;typedef struct vexNode { //顶点edgeNode *firstEdge; ///指向该顶点的第一条邻接边int vexData; //该顶点数据
}vexNode;typedef struct Graph { //图int vexNum, edgeNum; //顶点数边数vexNode vex[MAXVEX]; //vexNode类型的一维数组vex
}Graph;6.2.图的遍历
6.2.1.深度优先遍历
#define MAXVEX 100
bool visited[MAXVEX]; //visited数组记录该顶点是否被访问过void DFSTraverse (Graph G) {for (int i 0; i G.vexNum; i) {visited[i] false; //初始化visited数组}for (int i 0; i G.vexNum; i) {if (!visited[i]) DFS (G, i); //当前顶点未被访问过则访问}
}void DFS (Graph G, int v) {visit (v); //访问顶点v具体操作visited[v] true; //更新visited数组for (int w FirstNeighbor (G, v); w 0; w NextNeighbor (G, v, w)){if (!visited[w]) DFS(G, w); //递归调用DFS}
}6.2.2.广度优先遍历
#define MAXVEX 100
Queue Q;
bool visited[MAXVEX];void BFSTraverse (Graph G) {for (int i 0; i G.vexNum; i) { //初始化visited数组visited[i] false; }InitQueue Q; //初始化队列Qfor (int i 0; i G.vexNum; i) { //遍历图if (!visited[i]) BFS(G, i);}
}void BFS (Graph G, int v) {visit(v); //访问该顶点具体操作visited[v] true; //更新visited数组EnQueue(Q, v); //将v结点入队int w;while(!IsEmpty(Q)) {DeQueue(Q, v); //队首元素出队for (w FirstNeighbor(G, v); w 0; w NextNeighbor(G, v, w)) {if (!visited[w]) { //顶点未被访问过visit(w);visited[w] true;EnQueue(Q, w);}}//for}//while
}6.3.单源最短路径
#define MAXVEX 100
bool visited[MAXVEX];
int dis[MAXVEX];
Queue Q;void Min_Dis (Graph G, int v) {for (int i 0; i G.vexNum; i) { //初始化visited数组和dis数组visited[i] false;dis[i] INT_MAX;}visited[v] true;dis[v] 0;InitQueue(Q);EnQueue(Q, v);int w;while (!IsEmpty(Q)) {DeQueue(Q, v);for (w FisrtNeighbor(G, v); w 0; w NextNeighbor(G, v, w) {if (!visited[w]) {visited[w] true;dis[w] dis[v] 1;}}//for}//while
}6.4.真题 int IsExistEL(MGraph G){int count 0; //记录该图中度为奇数的顶点个数int i, j;for (i 0; i G.numVertices; i){ //行遍历邻接矩阵int degree 0;for (j 0; j G.numVertices; j){ //列遍历当前行if (Edge[i][j] 0) degree; //当前数组元素不为0则度1}if (degree % 2) count; //当前顶点的度为奇数count}if (count 0 || count 2) return 1; //奇数顶点个数为0或者2有EL路径else return 0; //奇数顶点个数不为0或者2没有EL路径
}7.快速排序
void QSort(int A[], L, R) { //快速排序if (L R) return; //当前数组长度 1返回随机选择数组中一元素和A[L]互换 //快排优化使得基准元素的选取随机int key A[L], i L, j R;while (i j) {while (i j key A[j]) j--;while (i j A[i] key) i;if (i j) swap (A[i], A[j]); //交换A[i]和A[j]}swap (A[i], A[L]);Qsort (A, L, i - 1); //递归处理左区间Qsort (A, i 1, R); //递归处理右区间
}8.折半查找
int Binary_Search (int A, L, R, key) {int mid;while (L R) { //L R时范围错误mid (L R) / 2; //选择中间数向下取整if (key A[mid]) R mid; //更新范围else L mid 1;}if (A[mid] key) return mid; //查找成功返回数组下标else return -1; //查找失败返回-1
}
