搜索
cLOGONOIP基础数据结构江涛队列、栈、堆概念与应用yourfamilysiteyoursitehereLOGO目录栈队列堆3数组124目录yourfamilysiteyoursitehereLOGO数组的特性数组•数组(array)的元素(element)或项(item)的类型是相同的•数组的大小是固定的、静态的、连续的•数组对某元素的存取是O(1)时间•数组的插入、删除操作是O(n)时间yourfamilysiteyoursitehereLOGO“订制”数组数组•由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点。•常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高。•注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用。yourfamilysiteyoursitehereLOGO栈(stack)的图示栈yourfamilysiteyoursitehereLOGO栈的特性栈•信息学中的栈一般就是用数组实现•栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的•栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间•栈有一个计数器counter或栈顶指针yourfamilysiteyoursitehereLOGO栈的实现样例Pascal代码栈constmaxn=1000;varstack:array[1..maxn]ofinteger;counter:integer;Procedurepush(x:integer);begin//入栈inc(counter);stack[counter]:=x;end;functionpop():integer;begin//出栈pop:=stack[counter];dec(counter);end;yourfamilysiteyoursitehereLOGO栈的实现样例C++代码栈constintmaxn=1000;intstack[maxn],counter=0;voidpush(intx)//入栈{stack[++counter]=x;}intpop()//出栈{returnstack[counter--];}yourfamilysiteyoursitehereLOGO栈的常见应用举例栈•括号匹配---判断字符串({[]}(){({{[()]}})}是否括号匹配•运算表达式---计算表达式3*(5-(2-3)*(6+5))+8*5•回溯的非递归写法•凸包的graham扫描算法yourfamilysiteyoursitehereLOGO队列(queue)的图示队列yourfamilysiteyoursitehereLOGO队列的特性队列•信息学中的队列一般也用数组实现•队列(queue)是先进先出(first-in-first-out,FIFO)或后进后出(LILO)的•队列有三个基本操作入队(push)、出队(pop)、取头(getHead)操作都为O(1)时间•队列有队头front和队尾back两个指针，一般也有个计数器counteryourfamilysiteyoursitehereLOGOconstmaxn=1000;varqueue:array[1..maxn]ofinteger;front,back,counter:integer;procedurepush(x:integer);begininc(counter);inc(back);//这样的话front,back初始化为1,0queue[back]:=x;end;functionpop():integer;beginpop:=queue[front];inc(front);dec(counter);end;队列的实现样例Pascal代码队列yourfamilysiteyoursitehereLOGOconstintmaxn=1000;intqueue[maxn],counter=0,front=0,back=-1;voidpush(intx){queue[++back]=x;++counter;}intpop(){--counter;returnqueue[front++];}队列的实现样例C++代码队列yourfamilysiteyoursitehereLOGO由于front和back一直向后移动，有可能counter不大，但back却超过maxn，而引起数组越界。数组实现队列的可能缺点队列………frontbackyourfamilysiteyoursitehereLOGO在保证countermaxn情况下，可以用循环数组利用的策略来充分利用数组空间。通常方法为每次front:=front+1;后加上iffrontmaxnthenfront:=1;同样的，每次back:=back+1;后加上ifbackmaxnthenback:=1;队列的”循环数组”方案队列yourfamilysiteyoursitehereLOGO队列的常见应用举例队列1、宽度优先搜索（BFS）。2、单调队列：a)有n(n1000000)个数排成一行，找出一段长度为L(1L=n)的连续一段，其中的最大值a与最小值b之差(a-b)是最大(小）的。求这个最大值。b)求01矩阵中最大的全零矩形(也可用栈做)3、SPFA算法（循环数组队列）。求01矩阵中最大的全零矩形yourfamilysiteyoursitehereLOGO堆(heap)的图示堆•堆是以数组存储的完全二叉树，数组下标对应的节点关系如左图所示•如果每个节点的左、右节点的值都不比它的值小，则称为小根堆。反之，称为大根堆。yourfamilysiteyoursitehereLOGO堆的特性堆•堆的本质是完全二叉树,只是用数组实现时编程简单、方便。•第i个节点的左孩子是第2*i个节点；右孩子是第2*i+1个节点。父节点idiv2•n个节点的堆，高度为log2N.•堆有二个基本操作增加一个元素、删除最值都为O(logN)时间。取最值为O(1)时间。yourfamilysiteyoursitehereLOGOconstmaxn=1000;varheap:array[1..maxn]ofinteger;counter:integer;procedureadd(x:integer)；//增加一个元素值为x的过程vari:integer;Begininc(counter);i:=counter;heap[i]:=x;while(i1)and(heap[i]heap[idiv2])do//小根堆beginswap(heap[i],heap[idiv2]);i:=Idiv2;end;end;堆的实现样例Pascal代码堆yourfamilysiteyoursitehereLOGOproceduredown(i:integer)；//第i个元素被修改，维护堆过程Begin//小根堆while(i*2=counter)dobegin//边界判断i:=i*2;if(i+1=counter)and(heap[i]heap[i+1])theni:=i+1;ifheap[i]heap[idiv2]thenswap(heap[i],heap[idiv2])elsebreak;end;end;Proceduredel_min;Begin//删除最小值（小根堆）swap(heap[1],heap[counter]);dec(counter);down(1);End;堆的实现样例Pascal代码堆yourfamilysiteyoursitehereLOGO堆的常见应用举例堆1、堆排序。2、动态求最小(大)值：a)合并果子（NOIP2004提高组）b)黑匣子（见附录）3、Dijkstra算法的优化(类似的还有Prim算法)。求01矩阵中最大的全零矩形yourfamilysiteyoursitehereLOGO附1(黑匣子)黑匣子（全国青少年信息学奥林匹克联赛培训教材（中学高级本））【试题描述】我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子执行一序列的命令。有两类命令：ADD(x)：把元素x放入黑匣子；GET：i增1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素以非降序排序后位于第i位的元素下面的表是一个11个命令的例子yourfamilysiteyoursitehereLOGO附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,8yourfamilysiteyoursitehereLOGO附1(黑匣子)现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多有3*10^4个。定义ADD命令的个数为M个，GET命令的个数为N个。我们用下面的两个整数序列描述命令序列：A(1),A(2),…,A(M)：加入黑匣子的元素序列。所有的数均为绝对值不超过2*10^6的整数。例如在上例中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，其中第一行存放M和N的值，第二行存放A(1),A(2),…,A(M)，第三行存放u(1),u(2),…,u(N)。【输出】输出黑匣子的处理结果。yourfamilysiteyoursitehereLOGO附2(job)工作安排[RichardPeng,2008]FarmerJohn有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1~N的N(1=N=100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个截止时间D_i(1=D_i=1000000000)，如果他可以完成这个工作，那么他可以获利P_i(1=P_i=1000000000).yourfamilysiteyoursitehereLOGO附2(job)在给定的工作利润和截止时间下，FJ能够获得的利润最大为多少呢？答案可能会超过32位整型。输入格式第1行：一个整数N.第2~N+1行：第i+1行有两个用空格分开的整数：D_i和P_i.样例输入(job.in):32101517输出格式:输出一行，里面有一个整数，表示最大获利值。样例输出(job.out):17样例解释：第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润yourfamilysiteyoursitehereLOGOupdata