《NOIP基础数据结构栈、队、堆ppt课件.ppt》由会员分享，可在线阅读，更多相关《NOIP基础数据结构栈、队、堆ppt课件.ppt（27页珍藏版）》请在三一办公上搜索。
1、NOIP基础数据结构,江涛,队列、栈、堆概念与应用,目录,栈,队列,堆,3,数组,1,2,4,目录,数组的特性,数组,数组(array)的元素(element)或项(item) 的类型是相同的数组的大小是固定的、静态的、连续的数组对某元素的存取是O(1)时间数组的插入、删除操作是O(n)时间,“订制”数组,数组,由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效-算法优化的突破点。常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高。注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用
2、。,栈(stack)的图示,栈,栈的特性,栈,信息学中的栈一般就是用数组实现栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间栈有一个计数器counter或栈顶指针,栈的实现样例Pascal代码,栈,const maxn = 1000;var stack:array1.maxn of integer; counter:integer;Procedure push(x:integer); begin /入栈 inc(counter); stackcounter
3、 :=x;end;function pop():integer; begin /出栈 pop:=stackcounter; dec(counter);end;,栈的实现样例C+代码,栈,const int maxn=1000;int stackmaxn, counter=0;void push(int x) /入栈 stack+counter=x;int pop() /出栈 return stackcounter-;,栈的常见应用举例,栈,括号匹配- 判断字符串()()是否括号匹配运算表达式- 计算表达式 3*(5-(2-3)*(6+5)+8*5 回溯的非递归写法凸包的graham扫描算法,队
4、列(queue)的图示,队列,队列的特性,队列,信息学中的队列一般也用数组实现队列(queue)是先进先出(first-in-first-out,FIFO)或后进后出(LILO)的队列有三个基本操作入队(push)、出队(pop)、取头(getHead)操作都为O(1)时间队列有队头front和队尾back两个指针，一般也有个计数器counter,const maxn = 1000;var queue:array1.maxn of integer; front,back,counter:integer; procedure push(x:integer); begin inc(counter)
5、; inc(back); /这样的话front,back初始化为1,0 queueback :=x;end;function pop():integer; begin pop:=queuefront; inc(front); dec(counter);end;,队列的实现样例Pascal代码,队列,const int maxn=1000;int queuemaxn,counter=0, front=0,back= -1 ;void push(int x) queue+back=x;+counter;int pop() -counter; return queuefront+;,队列的实现样例C
6、+代码,队列,由于front和back一直向后移动，有可能counter不大，但back却超过maxn，而引起数组越界。,数组实现队列的可能缺点,队列,front,back,在保证countermaxn then front:=1;同样的，每次back:=back+1; 后加上 if backmaxn then back:=1;,队列的”循环数组”方案,队列,队列的常见应用举例,队列,1、宽度优先搜索（BFS）。2、单调队列： a)有n(n1000000)个数排成一行，找出一段长度为L(1L=n)的连续一段，其中的最大值a与最小值b之差(a-b)是最大(小）的。求这个最大值。 b)求01矩阵中
7、最大的全零矩形(也可用栈做)3、SPFA算法（循环数组队列）。求01矩阵中最大的全零矩形,堆(heap)的图示,堆,堆是以数组存储的完全二叉树，数组下标对应的节点关系如左图所示如果每个节点的左、右节点的值都不比它的值小，则称为小根堆。反之，称为大根堆。,堆的特性,堆,堆的本质是完全二叉树,只是用数组实现时编程简单、方便。第 i 个节点的左孩子是第 2*i 个节点；右孩子是第 2*i+1个节点。父节点i div 2n个节点的堆，高度为 log2N.堆有二个基本操作增加一个元素、删除最值都为O(logN)时间。取最值为O(1)时间。,const maxn = 1000;var heap:array
8、1.maxn of integer; counter:integer; procedure add(x:integer)；/增加一个元素值为x的过程var i :integer;Begin inc(counter); i:=counter; heapi:=x; while (i1) and (heapi heapi div 2) do /小根堆 begin swap(heapi,heapi div 2); i:=I div 2; end;end;,堆的实现样例Pascal代码,堆,rocedure down(i:integer)；/第i个元素被修改，维护堆过程Begin /小根堆 while
9、(i*2heapi+1) then i:=i+1; if heapiheap i div 2 then swap(heapi,heapi div 2) else break; end;end;Procedure del_min; Begin /删除最小值 （小根堆） swap(heap1, heapcounter); dec(counter); down(1);End;,堆的实现样例Pascal代码,堆,堆的常见应用举例,堆,1、堆排序。2、动态求最小(大)值： a)合并果子（NOIP2004提高组） b)黑匣子（见附录）3、Dijkstra算法的优化(类似的还有Prim算法)。求01矩阵中最
10、大的全零矩形,附1(黑匣子),黑匣子（全国青少年信息学奥林匹克联赛培训教材（中学高级本）【试题描述】我们使用黑匣子的一个简单模型。它能存放一个整数序列和一个特别的变量i。在初始时刻，黑匣子为空且i等于0。这个黑匣子执行一序列的命令。有两类命令：ADD(x)：把元素x放入黑匣子； GET：i增1的同时，输出黑匣子内所有整数中第i小的数。牢记第i小的数是当黑匣子中的元素以非降序排序后位于第i位的元素 下面的表是一个11个命令的例子,附1(黑匣子),附1(黑匣子),现需要一个有效的算法处理给定的一系列命令。ADD和GET命令的总数至多有3*104个。定义ADD命令的个数为M个，GET命令的个数为N个
11、。我们用下面的两个整数序列描述命令序列：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，其中第一行存放M和N的值，第二行存放A(1),A(2),A(M)，第三行存放u(1),u(2),u(N)。【输出】输
12、出黑匣子的处理结果。,附2( job ),工作安排 Richard Peng, 2008Farmer John 有太多的工作要做啊！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有1000000000个单位时间（！）。在任一时刻，他都可以选择编号1N的N(1 = N = 100000)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个截止时间D_i(1 = D_i = 1000000000)，如果他可以完成这个工作，那么他可以获利P_i( 1=P_i=1000000000 ).,附2( job ),在给定的工作利润和截止时间下，FJ能够获得的利润最大为多少呢？答案可能会超过32位整型。输入格式第1行：一个整数N.第2N+1行：第i+1行有两个用空格分开的整数：D_i和P_i.样例输入 (job.in):32 101 51 7输出格式:输出一行，里面有一个整数，表示最大获利值。样例输出 (job.out):17样例解释：第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润,updata,
