《NOIP基础数据结构-栈、队、堆》由会员分享，可在线阅读，更多相关《NOIP基础数据结构-栈、队、堆（27页珍藏版）》请在金锄头文库上搜索。
1、cLOGONOIP基基础数数据据结构构 江江涛涛队列、列、栈、堆、堆概概念念与与应用用your family siteyour site hereLOGO目目录录栈栈栈栈队队队队列列列列堆堆堆堆3数数数数组组组组124目录目录your family siteyour site hereLOGO数数数数组组组组的的的的特性特性特性特性数数组数组(array)的元素(element)或项(item) 的类型是相同的数组的大小是固定的、静态的、连续的数组对某元素的存取是O(1)时间数组的插入、删除操作是O(n)时间your family siteyour site hereLOGO“ “订订制制制制
2、” ”数数数数组组组组数数组由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效-算法优化的突破点。常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高。注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用。your family siteyour site hereLOGO栈栈(stack)(stack)的的的的图图示示示示栈your family siteyour site hereLOGO栈栈的特性的特性的特性的特性栈信息学中的栈一般就是用数组实现栈(stack)是后进先出(las
3、t-in-first-out,LIFO)或先进后出(FILO)的栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间栈有一个计数器counter或栈顶指针your family siteyour site hereLOGO栈栈的的的的实现样实现样例例例例PascalPascal代代代代码码栈constmaxn=1000;varstack:array1.maxnofinteger;counter:integer;Procedurepush(x:integer);begin /入栈inc(counter);stackcounter:=x;end;functio
4、npop():integer;begin /出栈pop:=stackcounter;dec(counter);end;your family siteyour site hereLOGO栈栈的的的的实现样实现样例例例例C+C+代代代代码码栈const intmaxn=1000;intstackmaxn,counter=0;voidpush(intx)/入栈stack+counter=x;intpop()/出栈returnstackcounter-;your family siteyour site hereLOGO栈栈的常的常的常的常见应见应用用用用举举例例例例栈括号匹配- 判断字符串()()
5、是否括号匹配运算表达式- 计算表达式 3*(5-(2-3)*(6+5)+8*5 回溯的非递归写法凸包的graham扫描算法your family siteyour site hereLOGO队队列列列列(queue)(queue)的的的的图图示示示示队列列your family siteyour site hereLOGO队队列的特性列的特性列的特性列的特性队列列信息学中的队列一般也用数组实现队列(queue)是先进先出(first-in-first-out,FIFO)或后进后出(LILO)的队列有三个基本操作入队(push)、出队(pop)、取头(getHead)操作都为O(1)时间队列有队
6、头front和队尾back两个指针，一般也有个计数器counteryour family siteyour site hereLOGOconst maxn=1000;varqueue:array1.maxnofinteger;front,back,counter:integer;procedurepush(x:integer);begininc(counter);inc(back);/这样的话front,back初始化为1,0queueback:=x;end;functionpop():integer;beginpop:=queuefront;inc(front);dec(counter);e
7、nd;队队列的列的列的列的实现样实现样例例例例PascalPascal代代代代码码队列列your family siteyour site hereLOGOconst intmaxn=1000;intqueuemaxn,counter=0,front=0,back=-1;voidpush(intx)queue+back=x;+counter;intpop()-counter;returnqueuefront+;队队列的列的列的列的实现样实现样例例例例C+C+代代代代码码队列列your family siteyour site hereLOGO由于front和back一直向后移动，有可能coun
8、ter不大，但back却超过maxn，而引起数组越界。数数数数组实现队组实现队列的可能缺点列的可能缺点列的可能缺点列的可能缺点队列列frontbackyour family siteyour site hereLOGO在保证countermaxnthenfront:=1;同样的，每次back:=back+1;后加上ifbackmaxnthenback:=1;队队列的列的列的列的” ”循循循循环环数数数数组组” ”方案方案方案方案队列列your family siteyour site hereLOGO队队列的常列的常列的常列的常见应见应用用用用举举例例例例队列列1、宽度优先搜索（BFS）。2、
9、单调队列： a)有n(n1000000)个数排成一行，找出一段长度为L(1L=n)的连续一段，其中的最大值a与最小值b之差(a-b)是最大(小）的。求这个最大值。 b)求01矩阵中最大的全零矩形(也可用栈做)3、SPFA算法（循环数组队列）。求01矩阵中最大的全零矩形your family siteyour site hereLOGO堆堆堆堆(heap)(heap)的的的的图图示示示示堆堆堆是以数组存储的完全二叉树，数组下标对应的节点关系如左图所示如果每个节点的左、右节点的值都不比它的值小，则称为小根堆。反之，称为大根堆。your family siteyour site hereLOGO堆的
10、特性堆的特性堆的特性堆的特性堆堆堆的本质是完全二叉树,只是用数组实现时编程简单、方便。第 i 个节点的左孩子是第 2*i 个节点；右孩子是第 2*i+1个节点。父节点i div 2n个节点的堆，高度为 log2N.堆有二个基本操作增加一个元素、删除最值都为O(logN)时间。取最值为O(1)时间。your family siteyour site hereLOGOconst maxn=1000;varheap:array1.maxnofinteger;counter:integer;procedure add(x:integer)；/增加一个元素值为x的过程vari:integer;Begin
11、inc(counter);i:=counter;heapi:=x; while (i1)and(heapiheapidiv2)do/小根堆beginswap(heapi,heapidiv2);i:=Idiv2;end;end;堆的堆的堆的堆的实现样实现样例例例例PascalPascal代代代代码码堆堆your family siteyour site hereLOGOprocedure down(i:integer)；/第i个元素被修改，维护堆过程Begin /小根堆 while (i*2=counter)dobegin /边界判断i:=i*2;if(i+1heapi+1)theni:=i+1
12、; if heapiheapidiv2thenswap(heapi,heapidiv2)elsebreak;end;end;Proceduredel_min;Begin /删除最小值（小根堆）swap(heap1,heapcounter);dec(counter);down(1);End;堆的堆的堆的堆的实现样实现样例例例例PascalPascal代代代代码码堆堆your family siteyour site hereLOGO堆的常堆的常堆的常堆的常见应见应用用用用举举例例例例堆堆1、堆排序。2、动态求最小(大)值： a)合并果子（NOIP2004提高组） b)黑匣子（见附录）3、Dijk
13、stra算法的优化(类似的还有Prim算法)。求01矩阵中最大的全零矩形your family siteyour site hereLOGO附附1(黑匣子黑匣子)黑匣子黑匣子（全国青少年信息学奥林匹克联赛培训教材（中学高级本）【试题描述】【试题描述】我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子执行一序列的命令。有两类命令：ADD(x)：把元素x放入黑匣子；GET：i增1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素以非降序排序后位于第i位的元素下面的表是一个11个命令的例子your family
14、siteyour site hereLOGO附附1(黑匣子黑匣子)编编 号号命令命令i黑匣子内容黑匣子内容输出输出1ADD(3)032GET1333ADD(1)11,34GET21,335ADD(-4)2-4,1,36ADD(2)2-4,1,2,37ADD(8)2-4,1,2,3,88ADD(-1000)2-1000,-4,1,2,3,89GET3-1000,-4,1,2,3,8110GET4-1000,-4,1,2,3,8211ADD(2)4-1000,-4,1,2,2,3,8your family siteyour site hereLOGO附附1(黑匣子黑匣子)现需要一个有效的算法处理给
15、定的一系列命令。ADD和GET命令的总数至多有3*104个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面的两个整数序列描述命令序列：A(1),A(2),A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2*106的整数。例如在上例中A=(3,1,-4,2,8,-1000,2)。u(1),u(2),u(N)：u(i)表示第i个GET命令在第u(i)个ADD命令之后，例如在上例中，u=(1,2,6,6)。你可以在假定自然数序列u(1),u(2),u(N)以非降序排列，N=M，且对于每一个p（1=p=N）有p=u(p)=M。【输入】【输入】输入文件名为blackbox.in，
16、其中第一行存放M和N的值，第二行存放A(1),A(2),A(M)，第三行存放u(1),u(2),u(N)。【输出】【输出】输出黑匣子的处理结果。your family siteyour site hereLOGO附附2( job )工作安排工作安排 RichardPeng,2008FarmerJohn有太多的工作要做啊！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1N的N(1=N=100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截
17、止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个截止时间D_i(1=D_i=1000000000)，如果他可以完成这个工作，那么他可以获利P_i(1=P_i=1000000000).your family siteyour site hereLOGO附附2( job )在给定的工作利润和截止时间下，FJ能够获得的利润最大为多少呢？答案可能会超过32位整型。输入格式输入格式第1行：一个整数N.第2N+1行：第i+1行有两个用空格分开的整数：D_i和P_i.样例输入样例输入 (job.in):32101517输出格式输出格式:输出一行，里面有一个整数，表示最大获利值。样例输出样例输出 (job.out):17样例解释：样例解释：第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润your family siteyour site hereLOGOupdata
