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

your family site your site here LOGO c LOGO NOIP基础数据结构 江涛 队列、栈、堆概念与应用 目录 栈 队列 堆 3 数组 1 2 4 目录 数组的特性 数组 数组(array)的元素(element)或项(item) 的类型是相同的 数组的大小是固定的、静态的、连续的 数组对某元素的存取是O(1)时间 数组的插入、删除操作是O(n)时间 “订制”数组 数组 由于数组通常的插入、删除操作是O(n)时间的，在某些特定的条件下就显得低效了.因此我们通过对数组元素操作的限制，来达到操作的高效---算法优化的突破点。 常见的“订制”数组有:栈、队列、堆等.它们操作的时间效率都很高。 注：虽然栈、队列、堆可以不用数组实现，但NOIP的实践中，用数组更简单实用。 栈(stack)的图示 栈 栈的特性 栈 信息学中的栈一般就是用数组实现 栈(stack)是后进先出(last-in-first-out,LIFO)或先进后出(FILO)的 栈有三个基本操作压入(push),弹出(pop),取数(getTop)操作都为O(1)时间 栈有一个计数器counter或栈顶指针 栈的实现样例Pascal代码 栈 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; 栈的实现样例C++代码 栈 const int maxn=1000; int stack[maxn], counter=0; void push(int x) //入栈 { stack[++counter]=x; } int pop() //出栈 { return stack[counter--]; } 栈的常见应用举例 栈 括号匹配--- 判断字符串({[]}(){({{[()]}})}是否括号匹配 运算表达式--- 计算表达式 3*(5-(2-3)*(6+5))+8*5 回溯的非递归写法 凸包的graham扫描算法 队列(queue)的图示 队列 队列的特性 队列 信息学中的队列一般也用数组实现 队列(queue)是先进先出(first-in-first-out,FIFO)或后进后出(LILO)的 队列有三个基本操作入队(push)、出队(pop)、取头(getHead)操作都为O(1)时间 队列有队头front和队尾back两个指针，一般也有个计数器counter const 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; 队列的实现样例Pascal代码 队列 const 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++代码 队列 由于front和back一直向后移动， 有可能counter不大，但back却超过maxn， 而引起数组越界。 数组实现队列的可能缺点 队列 ……… front back 在保证countermaxn情况下，可以用循环 数组利用的策略来充分利用数组空间。 通常方法为每次front:=front+1;后加上 if frontmaxn then front:=1; 同样的，