NOIP 数据结构课件.pdf

发布时间：2022-06-22 发布人：admin 分类：说明书资料大小：2.80M 资料格式：pdf 举报版权申诉

第1页 / 共124页

第2页 / 共124页

第3页 / 共124页

第4页 / 共124页

第5页 / 共124页

第6页 / 共124页

第7页 / 共124页

第8页 / 共124页

数据结构 Caihua Li

目录 • 栈和队列 • 并查集 • 二叉堆 • 线段树 • 二叉搜索树 • 树状数组 • ST表 • 树上倍增 • 块状链表 • 字典树 • Hash • STL

栈和队列 • 栈：只在一端插入/删除/访问，后进先出 • 三种主要操作：push, pop, top • 队列：队首只删除/访问、队尾只插入，先进先出 • 三种主要操作：push, pop, fron

栈可以用STL，但一般还是自己写，因为真的很简单

例题 • 给定一个栈，维护五个操作。 • 1：将一个数x压入栈中。 • 2：求栈中数的最大值。 • 3：弹出栈顶的数。 • 4：求栈中的栈底开始的最大前缀和。 • 5：求栈中的栈顶开始的最大前缀和。 • Q<=1000。 • Q<=100000。

例题 • 给定一个数列，维护五个操作。 • 1：在光标的后面插入一个数字。 • 2：删除光标前的最后一个数字。 • 3：左移光标。 • 4：右移光标。 • 5：求前k个数的最大前缀和，保证k<=光标当前所在位置。 • Q<=1000。 • Q<=100000。

队列可以用STL，但一般还是自己写，还是因为真的很简单

例题 • 给定一个队列，维护三个操作。 • 1：将一个数x压入队列中。 • 2：求队列中数的最大值。 • 3：弹出队列尾的数。 • Q<=1000。 • Q<=100000。

分享到：

赞收藏

资料库