ICPC教材课程.pptVIP

* ACM/ICPC程序设计竞赛知识点综述（一） 石 雷合肥工业大学计算机与信息学院 内 容 ICPC竞赛没有纲； 教练只是领路人。 内 容 基本的数据结构； 排序、递归、有哪些信誉好的足球投注网站； 图论及其中的各种算法； 计算几何学； 组合数学，动态规划，模拟题等等。 基本的数据结构 一、基本的数据结构 栈； 队列； 链表； Hash表； 并查集。 一、基本的数据结构——栈 栈：在表尾进行插入或删除操作的线性表。 主要算法：初始化； 进栈算法； 出栈算法； 判断满/空。 一、基本的数据结构——队列 队列：特殊的线性表。只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作。 主要算法：初始化；入队算法；出队算法；判断满/空。 一、基本的数据结构——链表 链表：一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。 主要算法：插入、删除、查找等。 一、基本的数据结构——HASH表 哈希表/散列表：若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 主要算法：哈希表的构造、查找等。 应用：数字签名、网络安全。 一、基本的数据结构——并查集 并查集：并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。 主要算法：查找、合并等。 排序、递归、有哪些信誉好的足球投注网站 二、排序、递归、有哪些信誉好的足球投注网站——排序算法 插入排序：（1）建立有序列表；（2）从原数列中取出一个数，将其插入“有序列表”中，使其仍旧保持有序状态；（3）重复步骤2，直到完成。 冒泡排序：比较第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。 选择排序、快速排序、堆排序、归并排序、基数排序、希尔排序…… 二、排序、递归、有哪些信誉好的足球投注网站——递归算法 递归算法：一个过程或函数在其定义或说明中又直接或间接调用自身的一种方法，它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。递归的能力在于用有限的语句来定义对象的无限集合。 二、排序、递归、有哪些信誉好的足球投注网站——有哪些信誉好的足球投注网站算法 深度优先有哪些信誉好的足球投注网站算法：为了求得问题的解，先选择某一种可能情况向前（子结点）探索，在探索过程中，一旦发现原来的选择不符合要求，就回溯至父亲结点重新选择另一结点，继续向前探索，如此反复进行，直至求得最优解。 二、排序、递归、有哪些信誉好的足球投注网站——有哪些信誉好的足球投注网站算法 广度优先有哪些信誉好的足球投注网站算法：首先访问初始点Vi，并将其标记为已访问过，接着访问Vi的所有未被访问过可到达的邻接点Vi1、Vi2……Vit，并均标记为已访问过，然后再按照Vi1、Vi2……Vit的次序，访问每一个顶点的所有未被访问过的邻接点，并均标记为已访问过，依此类推，直到图中所有和初始点Vi有路径相通的顶点都被访问过为止。 对有哪些信誉好的足球投注网站算法的优化：如A*、剪枝、遗传算法、模拟退火算法等。 * * *