算法设计与分析 思政课件全套 清华 第1-9章 绪论、常用的数据结构及其应用-NP完全问题

《算法设计与分析》教材：《算法设计与分析基础》（C++语言描述），李春葆等清华大学出版社2022《算法设计与分析基础（C++语言描述）学习与实验指导》，李春葆等清华大学出版社20221/43第1章概论1.1算法的概念1.2算法分析CONTENTS提纲2/43算法（algorithm）是求解问题的一系列计算步骤，是一个由若干运算或指令组成的有限序列，用来将输入数据转换成输出结果。算法输入输出1.1.1什么是算法1.1算法的概念3/43算法的5大特性有穷性：在有限步之后结束。确定性：每一条指令必须有确切的含义，不会产生二义性。可行性：人们仅用笔和纸做有限次运算就能完成。输入：有零个或多个输入。输出：有一个或多个输出。4/43算法（有穷性、确定性、可行性）输入输出求解问题5/43【例1-1】有下列两段描述：

描述1：

描述2：voidexam1() voidexam2(){ intn; { intx,y; n=2; y=0; while(n%2==0) x=5/y; n=n+2; printf("%d,%d\n",x,y); printf("%d\n",n); }}违反有穷性违反可行性6/43算法设计要求正确性：对指定的每个输入实例都能输出正确的结果并停止。可使用性：用户友好性。可读性：算法逻辑清晰、简单和结构化。健壮性：容错性。高效率与低存储量：好的时空性能。7/431.1.2算法描述C/C++语言描述算法一般形式boolSum1(intn，ints){ if(n<=0)returnfalse; //参数错误时返回假 s=0; for(inti=1;i<=n;i++) s+=i; returntrue; //参数正确并计算出正确结果时返回真}算法的返回值：正确执行时返回真，否则返回假算法形参8/43Sum1错误：inta=10;b=0，调用Sum1(a,b)b=0。错误原因：s为输出参数，没有按输出参数设计。C++中增加了引用参数，一个参数名前面加上&就变为引用参数。引用参数在执行后会将结果回传给对应的实参。9/43boolSum2(intn，int&s){ if(n<=0)returnfalse; //参数错误时返回假 s=0; for(inti=1;i<=n;i++) s+=i; returntrue; //参数正确并计算出正确结果时返回真}算法的返回值：正确执行时返回真，否则返回假引用参数正确的算法10/43②①①①①intmain(){…

fun(a，b)…}intfun(intn,ints){

…}函数调用①：单向值传递

②：回传intmain(){

…

fun(a，b)…}intfun(intn,int&s){

…}引用和非引用参数的差别11/43intSum3(intn){ints=0;for(inti=1;i<=n;i++)s+=i;returns;}简单的算法：只有一个输出并且通过约束输入总能够得到正确结果时，可以直接用函数返回值表示输出。12/431.1.3算法和数据结构程序=数据结构+算法数据结构是算法设计的基础。算法的操作对象是数据结构。在设计算法时通常要构建适合这种算法的数据结构。13/431.1.4算法设计的基本步骤分析求解问题选择数据结构和算法设计策略描述算法证明算法正确性算法分析建立数学模型14/431.2算法分析1.2.1算法时间复杂度分析1.什么是算法时间复杂度分析事前分析估算法：认为算法的“运行工作量”的大小只依赖于问题规模n，或者说它是问题规模的函数。算法执行时间是算法中所有语句的执行时间之和，显然与算法中所有语句的执行次数成正比，可以简单地用算法中基本操作的执行次数来度量。算法中的基本操作是指最深层循环内的原操作，它对算法执行时间的贡献最大，是算法中最重要的操作。算法中所有基本操作的执行次数为f(n)。15/43算法时间复杂度分析是一种渐进分析，是指当问题规模n很大并趋于无穷大时对算法的时间性能分析，可表示为同时忽略低阶项和最高阶系数。16/43算法分析问题规模n，找出其中的基本语句，求出其运算次数f(n)用大O、大

或大

表示17/432.渐

进符号（O、

和

）定义1

f(n)=O(g(n))（读作“f(n)是g(n)的大O”），其含义是存在正常量c和n0，使得当n≥n0时，有0≤f(n)≤cg(n)也就是说f(n)的阶不高于g(n)的阶，称g(n)为f(n)的上界。cg(n)f(n)nf(n)=O(g(n))n0可以利用极限来证明，即如果=c并且c≠∞，则有f(n)=O(g(n))。18/43一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=O(nm)。例如3n+2=O(n)，因为

成立。10n2+4n+2=O(n4)，因为

成立。=c≠∞，则有f(n)=O(g(n))。19/43定义2

f(n)=

(g(n))（读作“f(n)是g(n)的大

”），其含义是存在正常量c和n0，使得当n≥n0时，f(n)≥cg(n)也就是说f(n)的阶不低于g(n)的阶，称g(n)为f(n)的下界。f(n)cg(n)nf(n)=

(g(n))n0可以利用极限来证明，即如果

并且c≠0，则有f(n)=

(g(n))。20/43≠0，则有f(n)=

(g(n))。例如3n+2=

(n)，因为

成立。10n2+4n+2=

(n)，因为

成立。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。21/43c2g(n)c1g(n)f(n)n0nf(n)=

(g(n))定义3

f(n)=

(g(n))（读作“f(n)是g(n)的大

”），其含义是存在正常量c1、c2和n0，使得当n≥n0时，有

c1g(n)≤f(n)≤c2g(n)也就是说g(n)与f(n)的同阶，也称g(n)为f(n)的确界。可以利用极限来证明，即如果

并且0<c<∞，则有f(n)=

(g(n))。22/43，0<c<∞，则有f(n)=

(g(n))。例如3n+2=

(n)。10n2+4n+2=

(n2)。一般地，如果f(n)=amnm+am-1nm-1+…+a1n+a0（am>0），有f(n)=

(nm)。23/43大

符号比大O符号和大

符号都要精确，f(n)=

(g(n))隐含着f(n)=O(g(n))和f(n)=

(g(n))。目前国内大部分教科书中习惯使用大O符号，本书主要也采用这种表示形式。说明24/43【例1-2】分析以下算法的时间复杂度。voidfun(intn){ints=0,i,j,k;for(i=0;i<n;i++)for(j=0;j<i;j++)for(k=0;k<j;k++)

s++;}算法的基本操作是s++该算法的时间复杂度为O(n3)。解25/433.渐进符号的特性（1）传递性f(n)=O(g(n))，g(n)=O(h(n))

f(n)=O(h(n))f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))f(n)=

(g(n))，g(n)=

(h(n))

f(n)=

(h(n))（2）自反性f(n)=O(f(n))f(n)=

(f(n))f(n)=

(f(n))（3）对称性f(n)=

(g(n))

g(n)=

(f(n))26/434.算法的最好、最坏和平均情况分析定义4设一个算法的输入规模为n，Dn是所有输入的集合，任一输入I∈Dn，P(I)是I出现的概率，有P(I)=1，T(I)是算法在输入I下所执行的基本操作次数，则该算法的平均执行时间为A(n)=

I∈DnP(I)*T(I)对应的时间复杂度称为平均时间复杂度。平均时间复杂度反映算法的总体时间性能。27/43算法的最好情况为G(n)=minI∈DnT(I)，是指算法在所有输入I下所执行基本操作的最少执行次数。对应的时间复杂度称为最好时间复杂度，最好时间复杂度反映算法的最佳性能，即为算法的时间下界。算法的最坏情况为W(n)=maxI∈DnT(I)，是指算法在所有输入I下所执行基本操作的最大执行次数。对应的时间复杂度称为最怀时间复杂度，最怀时间复杂度为算法的时间上界。28/43【例1-4】设计一个尽可能高效的算法，在长度为n的一维整型数组a[0..n-1]中查找值最大的元素maxe和值最小的元素mine。并分析算法的最好、最坏和平均时间复杂度。解voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}29/43该算法的基本语句是元素比较。最好的情况是a中元素递增排列，元素比较次数为n-1，即G(n)=n-1=O(n)。voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}30/43最坏的情况是a中元素递减排列，元素比较次数为2(n-1)，即W(n)=2(n-1)=O(n)。voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}31/43平均情况下，a中有一半的元素比maxe大，a[i]>maxe比较执行n-1次，a[i]<mine比较执行(n-1)/2次，因此平均元素比较次数为3(n-1)/2，即A(n)=3(n-1)/2=O(n)。voidMaxMin(inta[],intn,int&maxe,int&mine){maxe=mine=a[0];for(inti=1;i<n;i++){if(a[i]>maxe)maxe=a[i];elseif(a[i]<mine)mine=a[i];}}32/43【例1-5】采用顺序查找方法，在长度为n的一维实数数组a[0..n-1]中查找值为x的元素，即从数组的第一个元素开始，逐个与被查值x进行比较。找到后返回true，否则返回false。boolFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)returntrue;elsereturnfalse;}回答以下问题：

（1）分析该算法在等概率情况下成功查找到值为x的元素的最好、最坏和平均时间复杂度。

（2）假设被查值x在数组a中的概率是p，不在数组a中的概率是1-p，求算法的平均时间复杂度。33/43

（1）算法的while循环中if语句是基本操作（用于元素比较）。a数组中有n个元素，当第一个元素a[0]等于x，此时基本操作仅执行一次，此时呈现最好的情况，即G(n)=1=O(1)。

当a中最后一个元素a[n-1]等于x，此时基本操作执行n次，此时呈现最坏的情况，即W(n)=n=O(n)。解boolFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)returntrue;elsereturnfalse;}34/43对于成功查找的平均情况，假设查找到每个元素的概率相同，则P(a[i])=1/n（0≤i≤n-1），而成功找到a[i]元素时基本操作正好执行i+1次，所以：boolFind(doublea[],intn,doublex){inti=0;while(i<n){if(a[i]==x)break;i++;}if(i<n)returntrue;elsereturnfalse;}35/43（2）这里是既考虑成功查找又考虑不成功查找的情况。

对于成功查找，被查值x在数组a中的概率为p时，算法执行有n种成功情况，在等概率情况下元素a[i]被查找到的概率P(a[i])=p/n，成功找到a[i]元素时基本操作执行i+1次。

对于不成功查找，其概率为1-p，所有不成功查找基本操作都只执行n次，不妨看成一种情况。如果已知查找的x有一半的机会在数组中，此时p=1/2，则A(n)=[(n+1)/4]+n/2≈3n/4。36/434.平摊分析考虑这样一种算法，在算法中有一种操作反复执行时有这样的特性，其运行时间始终变动，如果这一操作在大多数时候运行很快，只是偶尔要花费大量时间，对这样的算法可以采用平摊分析。在平摊分析中，执行一系列数据结构操作所需要的时间是通过对执行的所有操作求平均而得出的。平摊分析可用来证明在一系列操作中，即使单一的操作具有较大的代价，通过对所有操作求平均后，平均代价还是很小的。37/43【例1-6】假设有一个可以存放若干个整数的整数表，其类型为List，data域是存放整数元素的动态数组，capacity域表示data的容量（data数组中能够存放的最多元素个数，初始容量为常数m），length域表示长度（data数组中存放的实际元素个数）。#definem2 //初始容量常数structList

//整数表的类型{ int*data; //动态数组 intlength; //长度 intcapacity; //容量};38/43整数表提供有这些运算：初始化Init，即设置初始容量、分配初始空间和将长度置为0。私有方法Expand()用于扩大容量，当长度达到容量时置新容量为两倍长度。Add(e)用于在表尾插入元素e。各个算法如下：voidInit(List&L) //初始化{ L.capacity=m; L.data=newint[L.capacity]; L.length=0;}39/43要求分析调用Add(e)算法的时间复杂度。voidExpand(List&L) //按长度两倍扩大容量{ int*p=L.data; L.capacity=2*L.length; //设置新容量 L.data=newint[L.capacity]; for(inti=0;i<L.length;i++) //复制全部元素 L.data[i]=p[i]; deletep;}voidAdd(List&L,inte) //添加e{ if(L.length==L.capacity)

Expand(L); L.data[L.length]=e; L.length++;}40/43Expand()算法中for循环执行n次（n为复制的元素个数），所以其时间复杂度为O(n)。Add(e)算法中可能会调用Expand(L)（调用一次称为一次扩容），那么其时间复杂度是不是也为O(n)呢？插入n个元素调用一次Expand(L)，调用Expand(L)的时间为O(n)，其他n-1次插入的时间为O(1)，平摊结果是解41/431.2.2算法空间复杂度分析一个算法的存储量包括形参所占空间和临时变量所占空间。在对算法进行存储空间分析时，只考察临时变量所占空间。空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模n的函数，以数量级形式给出，记作S(n)=O(g(n))、

(g(n))或

(g(n))，其中渐进符号的含义与时间复杂度中的含义相同。42/43intmax(inta[]，intn){ intmaxi=0; for(inti=1;i<n;i++) if(a[i]>a[maxi]) maxi=i;

returna[maxi];}函数体内分配的变量空间为临时空间，不计形参占用的空间，这里的仅计i、maxi变量的空间，其空间复杂度为O(1)。算法的临时空间43/4344/43思政案例第2章常用的数据结构及其应用2.1线性表2.3栈,队列和双端队列2.2字符串2.4二叉树和优先队列CONTENTS提纲2.5树和并查集2.6图2.7二叉排序树和平衡二叉树2.8哈希表2.9设计好的数据结构45/9146/912.1线性表2.1.1线性表的定义线性表是性质相同的n（n≥0）个元素的有限序列。每个元素有唯一的序号或者位置，也称为下标或者索引，通常下标是介于0到n-1之间。线性表中的n个元素从头到尾分别称为第0个元素，第1个元素，依此类推。47/91顺序表：线性表的顺序存储结构1.顺序表structSqList

//顺序表类型{ intdata[MaxSize]; //MaxSize为data数组的容量 intlength; //顺序表长度即实际元素个数 SqList():length(0){} //构造函数};整数顺序表类型48/91链表：线性表的链式存储结构2.链表struct

ListNode

//单链表结点类型{int

val; //结点值ListNode

*next; //后继结点的地址ListNode()

:

val(0),

next(NULL)

{} //默认构造函数ListNode(int

x)

:

val(x),

next(NULL)

{} //重载构造函数1ListNode(int

x,

ListNode

*next):val(x),

next(next)

{} //重载构造函数2};整数单链表结点类型49/91带头结点的单链表head…首结点尾结点头结点

a0an-1∧a1head结点序号01n-1…查找序号为i的结点插入序号为i的结点删除序号为i的结点基本运算50/912.1.2vector向量容器v[0]v[1]v[2]…v[n-1]空闲空间表头表尾长度为n容量为c51/911.vector的特点v容器相当于动态数组，用于存储具有相同数据类型的一组元素，其容量为c（容量表示最多存放的元素个数），长度为n。v容器具有随机存取特性。可以从v容器的末尾快速插入和删除元素，对应的时间复杂度为O(1)。在v容器的中间插入和删除元素速度较慢。v容器具有自动扩容功能。52/912.定义vector向量vector<int>v1; //定义元素为int的向量v1vector<int>v2(2);

//定义向量v2的容量和长度为2（2个元素均为int默认值0）vector<double>v3(2，1.2);

//定义向量v3的容量和长度为2（2个元素均为double值1.2）vector<int>v4(a，a+5);

//用数组a[0..4]共5个元素初始化向量v453/913.vector的成员函数类型成员函数功能说明容量empty()判断当前向量容器是否为空size()返回当前向量容器的长度reserve(c)为当前向量容器预分配c个元素的存储空间capacity()返回当前向量容器的容量resize(n)

调整当前向量容器的长度，使其能容纳n个元素访问元素back()返回当前向量容器的末尾元素front()返回当前向量容器的首元素[idx]返回指定下标idx的元素at[idx]同[idx]54/91类型成员函数功能说明更新push_back(e)在当前向量容器末尾添加了一个元素eemplace_back(e)同push_back(e)，采用原地构造对象再添加insert(pos,e)在pos位置插入元素e，即将元素e插入到迭代器pos指定元素之前emplace(pos,e)同insert(pos,e)，采用原地构造对象再插入erase()删除当前向量容器中某个迭代器或者迭代器区间指定的元素clear()删除当前向量容器中所有元素迭代器begin()返回当前向量容器中首元素的迭代器end()返回当前向量容器中末尾元素的后一个元素的迭代器rbegin()返回当前向量容器中末尾元素的迭代器rend()返回当前向量容器中首元素的前一个元素的迭代器55/914.vector的应用【例2-1】假设一个整数序列采用向量容器v存放，设计一个尽可能高效的算法删除v中所有的奇数元素，要求删除后v中元素的相对次序保持不变。56/91解法1：整体建表法。先将结果v看成是一个空表，用k表示结果v的元素个数（初始为0），用i遍历v，遇到偶数时重新插入到v中，遇到奇数时跳过。最后置v的长度为k。voiddelodd1(vector<int>&v) //解法1的算法{intk=0; //k记录结果v中的元素个数inti=0;while(i<v.size()){if(v[i]%2==0) //v[i]是偶数{v[k]=v[i]; //将v[i]重新插入到结果v中k++; //结果v的长度增1}i++;}v.resize(k); //设置v的长度为k}解57/91解法2：移动法。先将结果v看成是整个表，用k表示要删除的元素个数（初始为0），用i遍历v，遇到偶数时将v[i]前移k个位置，遇到奇数时将k增1。最后置v的长度为n-k。voiddelodd2(vector<int>&v) //解法2的算法{intk=0; //k记录删除的元素个数inti=0;while(i<v.size()){if(v[i]%2==0) //v[i]是偶数v[i-k]=v[i]; //将v[i]前移k个位置else //v[i]是奇数k++; //奇数元素个数增1i++;}v.resize(v.size()-k); //设置v的长度为n-k}58/91解法3：区间划分法。用v[0..k]（共k+1个元素）表示保留的元素区间（即偶数区间），初始时偶数区间为空，所以置k=-1。v[k+1..i-1]（共i-k-1个元素）表示删除的元素区间（即奇数区间），i从0开始遍历v，初始时奇数区间也为空。

vi

…vn-1偶数区间v0…vkvk+1

…vi-1奇数区间

①若v[i]为偶数，将其添加到偶数区间的末尾，再执行i++继续遍历。

②若v[i]为奇数，只需要执行i++扩大奇数区间，再继续遍历。

最后的结果v中仅保留所有偶数区间的k+1个元素，即置v的长度为k+1。59/91voiddelodd3(vector<int>&v) //解法3的算法{intk=-1; //v[0..k]表示偶数元素的区间inti=0;while(i<v.size()){if(v[i]%2==0) //v[i]是偶数{k++; //扩大偶数区间swap(v[k],v[i]); //v[k]和v[i]交换}i++;}v.resize(k+1); //设置v的长度为k+1}

vi

…vn-1偶数区间v0…vkvk+1

…vi-1奇数区间60/912.1.3STL通用算法1.常用的通用算法类型函数功能说明非更新的序列操作find在指定的[beg，end)范围内查找指定值的元素find_if在指定的[beg，end)范围内查找满足指定条件的元素count在指定的[beg，end)范围内查找指定值出现的次数count_if在指定的[beg，end)范围内查找满足指定条件的次数更新的序列操作copy复制指定的[beg，end)范围内的元素swap交换replace将指定的[beg，end)范围内的所有值替换为新值replace_if将指定的[beg，end)范围内满足条件的所有值替换为新值remove删除指定的[beg，end)范围内的所有指定的值remove_if删除指定的[beg，end)范围内的所有满足指定条件的值unique删除相邻重复的值（并非真正删除，仅仅将保留的值前移）reverse将指定的[beg，end)范围内的所有值翻转61/91类型函数功能说明排序sort非稳定的排序stable_sort稳定的排序is_sorted检测有序性有序序列的二分查找lower_bound在[beg，end)内查找第一个大于等于指定值的元素upper_bound在[beg，end)内查找第一个大于指定值的元素binary_search在指定[beg，end)范围内查找指定值的元素合并merge合并两个有序序列set_union求两个有序序列的并集set_intersection求两个有序序列的交集set_difference求两个有序序列的差集数学min求两个值的最小值max求两个值的最大值min_element求一个序列中的最小值max_element求一个序列中的最大值accumulate求指定的[beg，end)范围内的值之和其他next_permutation产生下一个排列prev_permutation产生前一个排列62/912.sort的使用方法使用对象：像vector或者数组等具有随机存取特性的容器。1）内置数据类型的排序如果vector中元素是内置数据类型的数据，sort()默认是以less<T>（小于关系仿函数）作为比较函数实现递增排序的。为了实现递减排序，需要改为greater<T>（大于关系仿函数）。63/91【例2-2】假设一个含n个整数的序列采用向量容器v存放，设计一个算法求第k（1≤k≤n）大的整数（不是第k个不同的整数）。解法1：将v中整数元素递增排序，那么排序后的v[n-k]就是原来v中第k大的整数。inttopk1(vector<int>&v,intk) //解法1的算法{sort(v.begin(),v.end()); //将v中所有元素递增排序returnv[v.size()-k];}64/91解法2：将v中整数元素递减排序，那么排序后的v[k-1]就是原来v中第k大的整数。inttopk2(vector<int>&v,intk) //解法2的算法{sort(v.begin(),v.end(),greater<int>()); //将v中所有元素递减排序returnv[k-1];}65/912）自定义数据类型的排序在声明结构体类型中重载<运算符，以实现按指定成员的递增或者递减排序。如sort(v.begin(),v.end())调用默认<运算符对v容器的所有元素实现排序。自己定义包含关系比较函数()的结构体Cmp，在关系比较函数()中实现按指定成员的递增或者递减排序。如sort(v.begin(),v.end(),Cmp())调用Cmp的()运算符对v容器的所有元素实现排序。自己定义关系比较函数myfun，关系比较函数myfun中实现按指定成员的递增或者递减排序。如sort(v.begin(),v.end(),myfun)调用myfun函数对v容器的所有元素实现排序。66/91【例2-3】假设一个非空向量容器v中存放若干学生信息，每个学生包含学号、姓名、分数和名次，初始时名次为空。

设计一个算法求出每个学生的名次（名次从1开始，相同分数的名次相同。67/91解structStud

//学生元素类型{ intno; //学号 stringname; //姓名 intscore; //分数 intrank; //名次 Stud(intno1,stringname1,intscore1) //构造函数 { no=no1; name=name1; score=score1; rank=0; }

booloperator<(constStud&s)const

//方式①：重载<运算符 { returnscore>s.score; //用于按score递减排序 }};68/91structCmp //方式②：Cmp中重载()运算符{ booloperator()(Stud&s,Stud&t)

{ returns.score>t.score; //用于按score递减排序 }};boolmyfun(Stud&s,Stud&t)

//方式③：自己定义比较函数myfun{ returns.score>t.score; //用于按score递减排序}69/91voidgetrank(vector<Stud>&v) //求所有学生的名次{ sort(v.begin(),v.end()); //方式①：将v中元素按分数递减排序

//sort(v.begin(),v.end(),Cmp()); //方式②：将v中元素按分数递减排序 //sort(v.begin(),v.end(),myfun); //方式③：将v中元素按分数递减排序 v[0].rank=1; for(inti=1;i<v.size();i++) //求名次 { if(v[i].score==v[i-1].score) v[i].rank=v[i-1].rank; else v[i].rank=i+1; }}70/912.1.4list链表容器a0a1…an-1表头表尾71/911.list的特点ls容器采用带头结点的循环双链表实现。ls容器可以在任何地方快速插入与删除，对应的时间复杂度均为O(1)。ls容器中每个结点单独分配空间，不存在空间不够的情况。ls容器不具有随机存取特性，查找序号为i（0≤i≤n-1）的元素值的时间复杂度为O(n)。72/912.定义list容器list<int>l1; //定义元素为int的链表l1list<int>l2(10); //指定链表l2的初始大小为10个int元素list<double>l3(10，1.23); //指定l3的10个初始元素的初值为1.23list<int>l4(a，a+5); //用数组a[0..4]共5个元素初始化l473/913.list的成员函数类型成员函数功能说明容量empty()判断链表容器是否为空size()返回链表容器的长度访问元素back()返回链表容器的末尾元素front()返回链表容器的首元素更新push_back(e)在链表尾部插入元素eemplace_back(e)同push_back(e)，采用原地构造对象再添加push_front(e)在链表首部插入元素eemplace_front(e)同push_front(e)，采用原地构造对象再添加insert(pos,e)在pos位置插入元素einsert(pos,n,e)在pos位置插入n个元素einsert(pos,pos1,pos2)在迭代器pos处插入[pos1,pos2)的元素pop_back()删除链表容器的末尾元素pop_front()删除链表容器的首元素。erase()从链表容器中删除一个或几个元素clear()删除链表容器中所有的元素74/91类型成员函数功能说明操作remove()删除链表容器中所有指定值的元素remove_if(cmp)删除链表容器中满足条件的元素unique()删除链表容器中相邻的重复元素merge()合并两个有序链表容器中的元素reverse()反转当前链表容器的所有元素sort()对链表容器中的元素排序迭代器begin()返回当前链表容器中首元素的迭代器end()返回当前链表容器中末尾元素的后一个元素的迭代器rbegin()返回当前链表容器中末尾元素的迭代器rend()返回当前链表容器中首元素的前一个元素的迭代器STL提供的sort()排序算法仅支持具有随机存取特性的容器，而list容器不支持随机访问，为此，list链表容器提供了sort()成员函数用于元素排序，类似的还有unique()、reverse()、merge()等成员函数。说明75/912.2字符串2.2.1字符串的定义字符串简称为串，是字符的有限序列，可以看成元素类型是字符的线性表。一个串s中若干连续的字符构成的串t称为s的子串。空串是任何串的子串。两个串相等当且仅当它们的长度相同并且对应位置的字符均相同。76/911.顺序串structSqString

//顺序串类型{ chardata[MaxSize]; //MaxSize为data数组的容量 intlength; //顺序串长度即实际元素个数 SqList():length(0){} //构造函数};77/912.链串struct

SNode

//链串的结点类型{ char

val; //结点值 ListNode

*next; //后继结点的地址 ListNode()

:

val(0),

next(NULL)

{} //默认构造函数 ListNode(char

x)

:

val(x),

next(NULL)

{} //重载构造函数1 ListNode(char

x,

SNode

*next):val(x),

next(next)

{} //重载构造函数2};78/912.2.2string字符串容器1.定义string容器string()：建立一个空的字符串。string(conststring&str)：用字符串str建立当前字符串。string(conststring&str,size_typeidx)：用字符串str起始于idx的字符建立当前字符串。string(conststring&str,size_typeidx,size_typenum)：用字符串str起始于idx的num个字符建立当前字符串。string(constchar*cstr)：用C-字符串cstr建立当前字符串。string(constchar*chars,size_typenum)：用C-字符串cstr开头的num个字符建立当前字符串。string(size_typenum,charc)：用num个字符c建立当前字符串。79/912.string的成员函数类型成员函数功能说明容量empty()判断当前字符串是否为空串size()返回当前字符串的长度length()与size()相同访问元素back()返回当前字符串容器的末尾元素front()返回当前字符串容器的首元素[idx]返回当前字符串位于idx位置的字符，idx从0开始at(idx)返回当前字符串位于idx位置的字符80/91类型成员函数功能说明更新append(str)在当前字符串的末尾添加一个字符串strpush_back(c)在当前字符串的末尾添加一个字符cinsert(size_typeidx,conststring&str)在当前字符串的idx序号处插入一个字符串strreplace(size_typeidx,size_typenum,conststring&str)将当前字符串中起始于idx的num个字符用一个字符串str替换replace(iteratorbeg,iteratorend,conststring&str)将[beg,end)区间的所有字符用字符串str替换pop_back()删除当前字符串的末尾字符erase()删除当前字符串中的所有的字符erase(size_typeidx)删除当前字符串的从idx开始的所有字符erase(size_typeidx,size_typenum)删除当前字符串的从idx开始的num个字符clear()删除当前字符串中的所有的字符81/91类型成员函数功能说明字符串操作find(string&s,size_typepos=0)在当前字符串中从pos位置（默认为0）开始向后查找字符串s的第一个位置rfind(string&s,size_typepos=npos)在当前字符串中从pos位置（默认为npos）开始向前查找字符串s的第一个位置substr(size_typeidx)返回当前字符串起始于idx的子串substr(size_typeidx,size_typenum)返回当前字符串起始于idx的长度为num的子串compare(conststring&str)返回当前字符串与字符串str的比较结果。在比较时，若两者相等则返回0，前者小于后者则返回-1，否则返回1迭代器begin()返回当前字符串容器中首元素的迭代器end()返回当前字符串容器中末尾元素的后一个元素的迭代器rbegin()返回当前字符串容器中末尾元素的迭代器rend()返回当前字符串容器中首元素的前一个元素的迭代器82/913.string的应用【例2-4】假设两个字符串s和t均采用string容器存储。设计一个算法利用string的成员函数求t在s中不重叠出现的次数。例如s="aaaaa"，t="aa"，结果为2。intCount(string&s,string&t){ intcnt=0; intpos=s.find(t,0); while(pos!=string::npos) //在s中找到t { cnt++; pos=s.find(t,pos+1); //继续在后续字符中查找 } returncnt;}解83/91【例2-5】假设有3个字符串str、s和t，均采用string容器存储。设计一个算法利用string的成员函数将str中所有的子串s用t串替换。例如str="ababcd"，s="ab"，t="123"，替换后str变为"123123cd"。voidReplaceall(string&str,string&s,string&t){ intm=s.size(); intpos=str.find(s,0); while(pos!=string::npos) //在str中找到s { str.replace(pos,m,t); //替换 pos=str.find(s,pos+1); //继续在后续字符中查找 }}解84/912.3栈、队列和双端队列2.3.1栈、队列和双端队列的定义栈是一种特殊的线性表，有前、后两个端点，规定只能在其中一端进行进栈和出栈操作。队列是一种特殊的线性表，有前、后两个端点，规定只能在一端进队元素，另外一端出队元素。双端队列是一种特殊的线性表，有前、后两个端点，每个端点都可以进队和出队元素。85/912.3.2deque双端队列容器前端后端前端进前端出后端进后端出86/91dq容器在实现上由若干个块构成，每个块中元素地址是连续的，块之间的地址是不连续的，系统有一个特定的机制将这些块构成一个整体并且维护相关操作。由于dq容器采用分块存放容器中的元素，所以空间的重新分配要比vector快，因为重新分配空间后，原有的元素不需要复制。dq容器提供了随机访问迭代器，但随机访问的时间不再是O(1)，也远好于O(n)。dq容器在前后端进队和出队除元素的时间复杂度均为O(1)，但在中间位置插入和删除元素速度较慢。dq容器不同于队列，它提供了遍历元素的迭代器成员函数，可以正向或者反向遍历其中的全部元素。1.deque的特点87/912.定义deque容器deque<int>dq1; //定义元素类型为int的空双端队列dq1deque<int>dq2(10); //指定dq2初始为10个int元素deque<double>dq3(10,1.23); //指定dq3的10个初始元素均为1.23deque<int>dq4(dq2.begin(),dq2.end()); //用dq2的所有元素初始化dq488/913.deque的成员函数类型成员函数功能说明容量empty()判断双端队列容器是否为空队size()返回双端队列的长度访问元素back()返回当前双端队列容器的末尾元素front()返回当前双端队列容器的首元素[idx]返回指定下标idx的元素at[idx]同[idx]89/91类型成员函数功能说明容量empty()判断双端队列容器是否为空队更新push_front(e)在队头插入元素epush_back(e)在队尾插入元素epop_front()出队一个队头元素pop_back()出队一个队尾元素insert()在双端队列容器中插入一个或几个元素erase()从双端队列容器中删除一个或几个元素clear()出队双端队列容器中所有元素迭代器begin()返回当前双端队列容器中首元素的迭代器end()返回当前双端队列容器中末尾元素的后一个元素的迭代器rbegin()返回当前双端队列容器中末尾元素的迭代器rend()返回当前双端队列容器中首元素的前一个元素的迭代器前端front后端backpush_frontpop_frontpush_backpop_back90/91deque容器在出队元素函数（pop_front、pop_back）中并不检测队空，所以在调用这些函数时务必保证容器是非空的，否则会导致程序停止正常工作。说明前端front后端backpush_frontpop_frontpush_backpop_back91/914.deque的应用【例2-6】给定一个含n个整数的序列

nums

和滑动窗口的大小

k（1≤k≤n），设计一个算法求出所有滑动窗口里的最大值。例如，nums=（4，3，5，4，3，3，6，7），k=3。nums:[4，3，5]，4，3，3，6，7

5nums:4，[3，5，4]，3，3，6，7

5nums:4，3，[5，4，3]，3，6，7

5nums:4，3，5，[4，3，3]，6，7

4nums:4，3，5，4，[3，3，6]，7

6nums:4，3，5，4，3，[3，6，7]

7结果是（5，5，5，4，6，7）92/91解vector<int>maxSlidingWindow(vector<int>&nums,intk){ intn=nums.size(); deque<int>dq; vector<int>ans; for(inti=0;i<k;i++) //处理nums前k个元素 { if(dq.empty()) //队空时将元素下标i进队尾 dq.push_back(i); else //队不空时 { while(!dq.empty()&&nums[i]>nums[dq.back()]) dq.pop_back(); //将队尾小于nums[i]的元素从队尾出队 dq.push_back(i); //将元素下标i进队尾 }}93/91 ans.push_back(nums[dq.front()]); //队头元素添加到ans中 for(inti=k;i<n;i++) //处理nums中剩余的元素 { if(dq.empty()) //队空时将元素下标i进队尾 dq.push_back(i); else //队不空时 { while(!dq.empty()&&nums[i]>nums[dq.back()]) dq.pop_back(); //将队尾小于nums[i]的元素从队尾出队 dq.push_back(i); //将元素下标i进队尾 } if(dq.front()<i-k+1) //将队头过期的元素从队头出队 dq.pop_front(); ans.push_back(nums[dq.front()]); //新队头元素添加到ans中 } returnans;}94/912.3.3queue队列容器1.queue的特点qu容器只能在队头出队（删除）、在队尾进队（插入）元素，不能在中间位置删除和插入元素，因此队中元素先进先出。qu容器具有自动扩容功能，不必考虑队满的情况。qu容器中的元素不允许顺序遍历，不支持begin()/end()和rbegin()/rend()迭代器函数。95/912.定义queue容器queue<int>qu1; //定义int类型的空队列qu1（底层容器是deque）list<int>ls(3,2);

//定义含3个元素值均为2的ls容器queue<int,list<int>>qu2(ls);

//由ls创建队列qu296/913.queue的成员函数成员函数功能说明empty()判断队列容器是否为空size()返回队列容器的长度front()返回队头元素back()返回队尾元素push(e)进队元素epop()出队一个元素queue容器在出队元素函数（pop）中并不检测队空，所以在调用该函数时务必保证容器是非空的，否则会导致程序停止正常工作。说明97/914.queue的应用【例2-7】给定一个含n（n>1）个整数的队列容器qu，设计一个算法出队其中序号为k（1≤k≤n）的元素（从队头开始数，队头元素的序号为1），并返回该元素。98/91intpopk(queue<int>&qu,intk){intn=qu.size(),x;for(inti=1;i<k;i++) //处理序号1到k-1的元素{x=qu.front();qu.pop(); //出队元素xqu.push(x); //将x进队}inte=qu.front();qu.pop(); //出队序号为k的元素efor(inti=k+1;i<=n;i++) //处理序号k+1到n的元素{x=qu.front();qu.pop(); //出队元素x

qu.push(x); //将x进队}returne; }解前端后端99/912.3.4stack栈容器1.stack的特点st容器只能在栈顶出栈（删除）和进栈（插入）元素，不能在中间位置删除和插入元素，因此栈中元素后进先出。st容器具有自动扩容功能，不必考虑栈满的情况。st容器中的元素不允许顺序遍历，不支持begin()/end()和rbegin()/rend()迭代器函数。100/912.定义stack容器stack<int>st1; //定义int类型的空栈st1（底层容器是deque）vector<int>v(2,10);

//定义含2个元素值均为10的v容器stack<int,vector<int>>st2(v);

//由v容器创建st2101/913.stack的成员函数成员函数功能说明empty()判断栈容器是否为空size()返回栈容器的长度push(e)进栈元素etop()返回栈顶元素pop()元素一个出栈stack容器在出栈元素函数（pop）中并不检测栈空，所以在调用该函数时务必保证容器是非空的，否则会导致程序停止正常工作。说明102/91【例2-8】给定一个含若干单词的字符串s，单词之间用一个或者多个空格分隔。设计一个算法将s中所有单词翻转并且返回翻转后的结果，结果字符串中两个单词之间只有一个空格。

例如s="theskyis

blue"翻转的结果t="blue

isskythe"。103/91stringReversewords(string&s){ stack<string>st; inti=0; while(i<s.length()) //遍历字符串s { while(i<s.length()&&s[i]=='')i++; //跳过空字符 stringtmp=""; while(i<s.length()&&s[i]!='') //提取单词tmp {tmp+=s[i];i++;} st.push(tmp); //将tmp进栈 } stringans=""; while(!st.empty()) //出栈所有单词连接成字符串ans { if(ans.length()==0) ans+=st.top(); else ans+=""+st.top(); st.pop(); } returnans;}解104/912.4二叉树和优先队列2.4.1二叉树1.二叉树的定义二叉树是有限的结点集合。这个集合或者是空，或者由一个根结点和两棵互不相交的称为左子树和右子树的二叉树组成。214356105/91在一棵二叉树中如果所有分支结点都有左、右孩子结点，并且叶子结点都集中在二叉树的最下一层，这样的二叉树称为满二叉树。在一棵二叉树中如果最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树。012543601243106/91满二叉树/完全二叉树层序编号：(i-1)/2i2i+12i+201243107/9121435(a)一棵二叉树53421403521(b)补齐为完全二叉树021124334NIL55(c)二叉树顺序存储结构2.二叉树的存储结构1）二叉树顺序存储结构108/912）二叉树链式存储结构root21∧3∧∧4∧5∧∧21435109/91整数二叉链结点类型TreeNodestruct

TreeNode

//二叉链结点类型{ int

val; //结点值 TreeNode

*left; //左孩子结点地址 TreeNode

*right; //右孩子结点地址 TreeNode()

:

val(0),

left(nullptr),

right(nullptr)

{} TreeNode(int

x)

:

val(x),

left(nullptr),

right(nullptr)

{} TreeNode(int

x,

TreeNode

*left,

TreeNode

*right)

: