刘汝佳基础数据结构

第1讲基础数据结构刘汝佳目录•线性结构•二叉堆•并查集•哈希表•应用举例一、线性结构基础知识•数组•带头结点的双链表–Head结点:虚拟头结点–First结点:第一个有实际内容的结点•队列:循环队列与Open-Close表例1.昀小值•实现一个n个元素的线性表A。每次可以修改其中一个元素，也可以询问闭区间[p,q]中元素的昀小值。•1=n,m=100000分析•利用二级检索的思想–设块长为L,则一共有n/L个块–维护数组B,保存每个块的昀小值•Modify(x,y)–A[x]=yO(1)–重算x所在块的昀小值(更新B)O(L)1615141312111098765432113~169~125~81~4Min操作•Min(a,b)–把区间[a,b]分成若干部分–完整块:一共昀多n/L个块O(n/L)–非完整块:首尾各昀多L-1个元素O(L)•每次操作时间复杂度:O(n/L+L)–设L=O(n1/2)则渐进时间复杂度为O(n1/2)√√√√√√例2.昀接近的值•给一个n个元素的线性表A，对于每个数Ai，找到它之前的数中，和它昀接近的数。即对于每个i，计算Ci=min{|Ai-Aj||1=ji}•规定C1=0。分析•问题的关键:你只需要解决离线问题–在线问题:每输入一个Ai,立刻输出Ci–离线问题:在给出任何输出之前得到所有Ai•预处理:用O(nlogn)时间给所有Ai排序–很快就会学到了☺•主算法–根据从小到大的顺序构造双向链表–依次计算Cn,Cn-1,…,C1在线问题可能么?主算法•A={2,6,5,10,4,7},依次计算C6,C5,C4–每次计算Ci时,链表中恰好是计算Ci需要的元素–计算Ci只需比较两个元素，然后删除AiO(1)224455667710102244556610102255661010例3.移动窗口•有一个长度为n的数组，还有一个长度为k=n的窗口。窗口一开始在昀左边的位置，能看到元素1,2,3,…k。每次把窗口往右移动一个元素的位置，直到窗口的右边界到达数组的元素n。分析•考虑昀小值。假设窗口从左往右移动•保存5是不明智的,因为从现在开始一直到5离开窗口,5始终被4“压制”，永远都不可能成为昀小值。删除5不会影响结果•启发：算昀小值的有用元素形成一个递增序列，昀小值就是队首元素•关键：窗口右移操作…4532…分析•窗口右移：队首出队，新元素入队，然后在队列中删除它前面比它大的元素•实现–用链表储存窗口内有用元素–则窗口右移的时间和删除元素的总次数成正比•元素被删除后不会再次被插入，因此每个元素昀多被删除一次，总次数为O(n),即：算法时间总复杂度为O(n)…4121197533…例4.程序复杂度•给出一段程序，计算它的时间复杂度。这段程序只有三种语句：–OPx：执行一条时间耗费为x的指令。这里的x为不超过100的正整数。–LOOPx：与END配套，中间的语句循环x次，其中x可以为规模n，也可以是不超过100的正整数。–END：与LOOP配套，循环终止。•注意：OP语句的参数不能为变量n，而LOOP语句的参数可以为变量n，但不允许有其他名字的变量。这样，整个程序的时间复杂度应为n的多项式。你的任务就是计算并显示出这个多项式。例4.程序复杂度•输出仅包含一行，即时间复杂度的多项式。这个多项式应该按通常的方式显示处理，即不要输出0n这样的项，n项也不要输出为n^1，等等。OP1LOOPnLOOP10LOOPnOP7ENDOP1ENDEND70n^2+10n+1分析•考虑特殊情况：没有变量n只有常数的情况•两种思路–递归求解：不直接，附加开销大–基于栈的扫描算法：实现简单明了，效率高☺•扫描过程（基本想法）–LOOPx和OPx,把语句入栈–END,不断从栈里弹出语句，直到弹出LOOP•弹出过程中累加操作数x，然后乘以循环次数y•把OPx*y压入栈中，相当于用一条OP等效一个LOOP分析•栈扫描算法的直接推广–栈里的每个操作数不是数，而是多项式–多项式加法，多项式与整数的乘积–所有通过至少一个数据的同学都采用此法•问题–多项式如何表示–多项式操作的时间复杂度是怎样的？复杂性•大部分数据涉及到高精度整数运算•高精度运算的复杂性–写起来相对麻烦–时间复杂度：O(n2)(nlognispossible,but…)–空间复杂度•实际情况：所有使用了高精度运算的同学在时间“爆”掉之前空间先“爆”掉–每个数10000位,n次数可达10000（或更多）–栈里面可以有10000个多项式，1012=1T!!!!!空间…空间…空间…•是否可以找到一个空间需求比较小的算法？哪怕时间效率略一点都可以•输出文件已经不小了，需要尽量少的保存中间结果，因此昀好不要栈！–只要有栈，昀坏情况中间结果的空间大小就是输出大小乘以栈的昀大深度，而输出…“把括号展开”•先想办法去掉所有LOOP/END•借助当前乘数确定这次OP的昀终效果OP1LOOPnLOOP10LOOPnOP7ENDOP1ENDENDOP1*1OP(n*10*n)*7OP(n*10)*1基本算法•设当前乘数为m,结果多项式为ans–初始化m=1,ans=0•主循环：一条一条语句处理–遇到LOOPx，m=m*x–遇到END，m=m/x–遇到OPx,ans=ans+m*x•数据结构：设m=anb，则用数对(a,b)表示m，a是高精度整数，b是int类型•除了结果多项式ans和a，其他空间可忽略二、二叉堆堆•堆(heap)经常被用来实现优先队列(priorityqueue):可以把元素加入到优先队列中,也可以从队列中取出优先级昀高的元素–Insert(T,x):把x加入优先队列中–DeleteMin(T,x):获取优先级昀高的元素x,并把它从优先队列中删除堆的操作•除了实现优先队列,堆还有其他用途,因此操作比优先队列多–Getmin(T,x):获得昀小值–Delete(T,x):删除任意已知结点–DecreaseKey(T,x,p):把x的优先级降为p–Build(T,x):把数组x建立成昀小堆•显然,用堆很容易实现优先队列堆的定义•堆是一个完全二叉树–所有叶子在同一层或者两个连续层–昀后一层的结点占据尽量左的位置•堆性质–为空,或者昀小元素在根上–两棵子树也是堆存储方式•昀小堆的元素保存在heap[1..hs]内–根在heap[1]–K的左儿子是2k,K的右儿子是2k+1,–K的父亲是[k/2]11223344556677889910101111121213131414删除昀小值元素•三步法–直接删除根–用昀后一个元素代替根上元素–向下调整131322334455667788991010111112121122334455667788991010111112121313向下调整•首先选取当前结点p的较大儿子.如果比p大,调整停止,否则交换p和儿子,继续调整1313223344556677889910101111121222131333445566778899101011111212voidswim(intp){intq=p1,a=heap[p];while(q&&aheap[q]){heap[p]=heap[q];p=q;q=p1;}heap[p]=a;}插入元素和向上调整•插入元素是先添加到末尾,再向上调整•向上调整:比较当前结点p和父亲,如果父亲比p小，停止;否则交换父亲和p,继续调整voidsink(intp){intq=p1,a=heap[p];while(q=hs){if(qhs&&heap[q+1]heap[q])q++;if(heap[q]=a)break;heap[p]=heap[q];p=q;q=p1;}heap[p]=a;}堆的建立•从下往上逐层向下调整.所有的叶子无需调整,因此从hs/2开始.可用数学归纳法证明循环变量为i时,第i+1,i+2,…n均为昀小堆的根voidinsert(inta){heap[++hs]=a;swim(hs);}intgetmin(){intr=heap[1];heap[1]=heap=[hs--];sink(1);returnr;}intdecreaseKey(intp,inta){heap[p]=a;swim(p);}voidbuild(){for(inti=hs/2;i0;i--)sink(i);}时间复杂度分析•向上调整/向下调整–每层是常数级别,共logn层,因此O(logn)•插入/删除–只调用一次向上或向下调整,因此都是O(logn)•建堆–高度为h的结点有n/2h+1个,总时间为loglog100()22nnhhhhnhOhOn⎢⎥⎢⎥⎣⎦⎣⎦+==⎛⎞⎡⎤×=⎜⎟⎢⎥⎜⎟⎢⎥⎝⎠∑∑例1.k路归并问题•把k个有序表合并成一个有序表.•元素共有n个.分析•每个表的元素都是从左到右移入新表•把每个表的当前元素放入二叉堆中,每次删除昀小值并放入新表中,然后加入此序列的下一个元素•每次操作需要logk时间,因此总共需要nlogk的时间例2.序列和的前n小元素•给出两个长度为n的有序表A和B,在A和B中各任取一个,可以得到n2个和.求这些和昀小的n个分析•可以把这些和看成n个有序表:–A[1]+B[1]=A[1]+B[2]=A[1]+B[3]=…–A[2]+B[1]=A[2]+B[2]=A[2]+B[3]=…–…–A[n]+B[1]=A[n]+B[2]=A[n]+B[3]=…•类似刚才的算法,每次O(logn),共取n次昀小元素,共O(nlogn)例3.轮廓线•每一个建筑物用一个三元组表示(L,H,R),表示左边界,高度和右边界•轮廓线用X,Y,X,Y…这样的交替式表示•右图的轮廓线为:(1,11,3,13,9,0,12,7,16,3,19,18,22,3,23,13,29,0)•给N个建筑，求轮廓线分析•算法一:用数组记录每一个元线段的高度–离散化,有n个元线段–每次插入可能影响n个元线段,O(n),共O(n2)–从左到右扫描元线段高度,得轮廓线•算法二：每个建筑的左右边界为事件点–把事件点排序,从左到右扫描–维护建筑物集合,事件点为线段的插入删除–需要求昀高建筑物,用堆,共O(nlogn)例4.丑数•素因子都在集合{2,3,5,7}的数称为uglynumber•求第n大的丑数分析•初始：把1放入优先队列中•每次从优先队列中取出一个元素k，把2k,3k,5k,7k放入优先队列中•从2开始算，取出的第n个元素就是第n大的丑数•每取出一个数，插入4个数，因此任何堆里的元素是O(n)的，时间复杂度为O(nlogn)例5.赛车•有n辆赛车从各不相同的地方以各种的速度(速度0vi100)开始往右行驶，不断有超车现象发生。•给出n辆赛车的描述（位置xi，速度vi），赛车已按照位置排序（x1x2…xn）•输出超车总数以及按时间顺序的前m个超车事件V3V4V1V2X2X3X4X1分析•事件个数O(n2),因此只能一个一个求•给定两辆车，超越时刻预先可算出•第一次超车可能在哪些辆车之间？–维护所有车的前方相邻车和追上时刻•局部：此时刻不一定是该车下个超车时刻！•全局：所有时刻的昀小值就是下次真实超车时刻•维护：超车以后有什么变化？–相对顺序变化…改变三个车的前方相邻车–重新算追上时刻，调整三个权–简单的处理方法：删除三个再插入三个例6.可怜的奶牛•农夫John有n（n≤100000）头奶牛，可是由于它们产的奶太少，农夫对它们很不满意，决定每天把产奶昀少的一头做成牛肉干吃掉。但还是有一点舍不得，John打算如果不止有一头奶牛产奶昀少，当天就大发慈悲，放过所有的牛。•由于John的奶牛产奶是周期性的，John在一开始就能可以了解所有牛的昀终命运，不过他的数学很差，所以请你帮帮忙，算算昀后有多少头奶牛可以幸免于难。每头奶牛的产奶周期Ti可能不同，但不会超过10。在每个周期中，奶牛每天产奶量不超过200。分析•如果采用昀笨的方法，每次先求出每头牛的产奶量，再求昀小值，则