NOIP基础数据结构-栈、队、堆.ppt

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“ “订订制制制制” ”数数数数组组组组数数组•由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点•常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高•注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用your family siteyour site hereLOGO栈栈(stack)(stack)的的的的图图示示示示栈your family siteyour site hereLOGO栈栈的特性的特性的特性的特性栈•信息学中的栈一般就是用数组实现•栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的•栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间•栈有一个计数器counter或栈顶指针your family siteyour site hereLOGO栈栈的的的的实现样实现样例例例例PascalPascal代代代代码码栈const    maxn = 1000;var       stack:array[1..maxn] of integer;    counter:integer;Procedure push(x:integer); begin         //入栈  inc(counter); stack[counter] :=x;end;function pop():integer; begin              //出栈  pop:=stack[counter]; dec(counter);end;your family siteyour site hereLOGO栈栈的的的的实现样实现样例例例例C++C++代代代代码码栈const int maxn=1000;int stack[maxn],      counter=0;void push(int x)                 //入栈{   stack[++counter]=x;}int pop()                           //出栈{  return stack[counter--];}your family siteyour site hereLOGO栈栈的常的常的常的常见应见应用用用用举举例例例例栈•括号匹配--- 判断字符串({[]}(){({{[()]}})}是否括号匹配•运算表达式--- 计算表达式 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)时间•队列有队头front和队尾back两个指针，一般也有个计数器counteryour family siteyour site hereLOGOconst    maxn = 1000;var       queue:array[1..maxn] of integer;    front,back,counter:integer;   procedure push(x:integer); begin  inc(counter); inc(back);     //这样的话front,back初始化为1,0  queue[back] :=x;end;function pop():integer; begin  pop:=queue[front];   inc(front); dec(counter);end;队队列的列的列的列的实现样实现样例例例例PascalPascal代代代代码码队列列your family siteyour site hereLOGOconst int maxn=1000;int queue[maxn],counter=0,    front=0,back= -1 ;void push(int x){   queue[++back]=x;++counter;}int pop(){  --counter;  return queue[front++];}队队列的列的列的列的实现样实现样例例例例C++C++代代代代码码队列列your family siteyour site hereLOGO由于front和back一直向后移动，有可能counter不大，但back却超过maxn，而引起数组越界。

数数数数组实现队组实现队列的可能缺点列的可能缺点列的可能缺点列的可能缺点队列列………frontbackyour family siteyour site hereLOGO在保证countermaxn then front:=1;同样的，每次back:=back+1; 后加上   if back>maxn then back:=1;队队列的列的列的列的” ”循循循循环环数数数数组组” ”方案方案方案方案队列列your family siteyour site hereLOGO队队列的常列的常列的常列的常见应见应用用用用举举例例例例队列列1、宽度优先搜索（BFS）2、单调队列： a)有n(n<1000000)个数排成一行，找出一段长度为L(1

反之，称为大根堆your family siteyour site hereLOGO堆的特性堆的特性堆的特性堆的特性堆堆•堆的本质是完全二叉树,只是用数组实现时编程简单、方便•第 i 个节点的左孩子是第 2*i 个节点；右孩子是第 2*i+1个节点父节点i div 2•n个节点的堆，高度为 log2N.•堆有二个基本操作增加一个元素、删除最值都为O(logN)时间取最值为O(1)时间your family siteyour site hereLOGOconst    maxn = 1000;var       heap:array[1..maxn] of integer;    counter:integer;   procedure add(x:integer)；//增加一个元素值为x的过程var  i :integer;Begin     inc(counter); i:=counter;     heap[i]:=x; while (i<>1) and  (heap[i] < heap[i div 2]) do     //小根堆        begin swap(heap[i],heap[i div 2]); i:=I div 2; end;end;堆的堆的堆的堆的实现样实现样例例例例PascalPascal代代代代码码堆堆your family siteyour site hereLOGOprocedure down(i:integer)；//第i个元素被修改，维护堆过程Begin //小根堆 while (i*2<= counter)  do  begin //边界判断         i:=i*2;         if (i+1<=counter)  and (heap[i]>heap[i+1])  then i:=i+1;         if heap[i]

2、动态求最小(大)值： a)合并果子（NOIP2004提高组） b)黑匣子（见附录）3、Dijkstra算法的优化(类似的还有Prim算法)求01矩阵中最大的全零矩形your family siteyour site hereLOGO附附1(黑匣子黑匣子)黑匣子黑匣子（全国青少年信息学奥林匹克联赛培训教材（中学高级本））【试题描述】【试题描述】我们使用黑匣子的一个简单模型它能存放一个整数序列和一个特别的变量i在初始时刻，黑匣子为空且i等于0这个黑匣子执行一序列的命令有两类命令：ADD(x)：把元素x放入黑匣子；      GET：i增1的同时，输出黑匣子内所有整数中第i小的数牢记第i小的数是当黑匣子中的元素以非降序排序后位于第i位的元素      下面的表是一个11个命令的例子your family 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, 8your family siteyour site hereLOGO附附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)输出】【输出】输出黑匣子的处理结果your family siteyour site hereLOGO附附2( job )工作安排工作安排 [Richard Peng, 2008]Farmer John 有太多的工作要做啊！！！！！！！！为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。

他的工作日从0时刻开始，有1000000000个单位时间（！）在任一时刻，他都可以选择编号1~N的N(1 <= N <= 100000)项工作中的任意一项工作来完成因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有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.第2~N+1行：第i+1行有两个用空格分开的整数：D_i和P_i.样例输入样例输入 (job.in):32 101 51 7输出格式输出格式:输出一行，里面有一个整数，表示最大获利值样例输出样例输出 (job.out):17样例解释：样例解释：第1个单位时间完成第3个工作(1,7)，然后在第2个单位时间完成第1个工作(2,10)以达到最大利润your family siteyour site hereLOGOupdata。