数据结构的培训教程

1、树和森林连通无回路的无向图树的递归定义一棵树要么为空，要么由根和它的子树组成森林树的集合二叉树左子树、右子树遍历前序遍历中序遍历后序遍历练习 前序遍历和中序遍历的序列，求后序遍历的序列思考：隔三遍历隔三遍历:即遍历得到的序列(a1,a2,.,an)满足:序列中任意两个相邻点在树上的距离小于或等于3.例如以下图的一个合法遍历为: 1 3 4 6 5 2 7隔三遍历算法:由于规模大,考虑进行构造而不是搜索.由于是一般的树,可以模仿二叉树遍历的方法.首先深度优先遍历无向图成为一棵多叉树,并标上深度(depth),然后对每个结点x，考虑它的深度depth：如果depth为奇数，那么对结点x进行先序遍历

2、；如果depth为偶数，那么对结点x进行后序遍历。用数学归纳法可以得证。完全二叉树除了底层，其他层都到达最大子节点个数自顶向下，同层从左往右编号0,1,2,n-1对任意序号ii的父节点是(i-1)/2i的左子节点i*2+1i的右子节点i*2+2堆以小根堆为例所有父节点的值都小于等于子节点的值向上维护(插入),O(logn)向下维护(删除),O(logn)一般用完全二叉树实现问题总共输入n(n1000000)个不同的数，每个数介于(0-1000000)之间，输入过程中会不定时修改某些数的大小，继续维持堆的性质。带HASH的堆根据题中数据范围以及两两不等。Ai代表元素大小为i的元素在堆中的位置这样

3、修改的复杂度降为O(1)修改后调整复杂度为O(log n)总修改的复杂度为O(log n)应用SPFA优先队列一般支持的操作：1.支持插入，删除元素间接说明支持修改2.支持查找最大或最小元素 *3.不支持合并操作，但左偏树等可并优先队列仍可以支持注意：所谓的支持的操作是指复杂度在线性以下可以完成，例如O(logN),O(1)，也有可以是O(N0.5)优先队列一般来说优先队列就是用堆例子dijkstra算法用优先队列优化O(n+m)logn)动态维护中位数问题，一个集合，要支持插入操作和求当前中位数的操作，容易想到的是编程极其复杂的平衡树，但用优先队列会比较方便哈夫曼树问题：给定104个数，每次

4、合并其中两个数a,b，合并代价为a+b,现在求合并代价总和的最小值Huffman树每次合并当前数组中最小的两个数Huffman树的由来一种贪心的思想暴力复杂度O(n2)用优先队列优化,复杂度为O(nlogn)排序算法插入排序O(n2)在已有有序序列中每次插入一个元素选择排序O(n2)给每个位置选择当前元素最大(最小)归并排序O(nlogn)把序列一分为二，对有序序列归并快速排序根本思想 任取一个数把数列分成两段它左边的数都比它小，它右边的数都比它大此时这个数就在目标序列中它的位置上对两个子段分别进行排序时间复杂度最坏O(n2)，期望O(nlogn)其他排序法堆排序O(nlogn)基数排序.稳定

5、性选择排序不稳定插入排序稳定快速排序不稳定归并排序稳定堆排序不稳定哈希表Hash table,也叫散列表是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。Hash函数字符串的hash函数int ELFhash(char *key) unsigned long h=0; while(*key) h=(h24; h &= g; return h % M;冲突return h % M;一般来说M是一个大质数冲突的解决开散列法闭散列法几个例子给一个学生信息的列表，根据姓名查询学生信息走迷宫的时候判断某个格子是否走过H

6、ash表推荐阅读2005年IOI国家集训队论文李羽修?Hash函数的设计优化?另外为图方便，C+里用map实际是红黑树来实现hash的映射编程上会比较方便并查集查找一个元素在哪个集合中合并两个集合用森林实现并查集，用树根表示集合查找查找某个元素所在树的树根，同时压缩路径合并较小的集合树根的父亲设为较大集合的根并查集时间效率O(m*f(m,n),f是Ackermann函数的某个反函数，一般认为小于5应用查找两个元素是否在同一个集合中poi9806相等的单词让二进制串a,b,c,d,e分别为长度为4，2，4，4，2的5个变量。考虑以下等式：1bad1=acbe。问有多少种变量取值使得等式成立poi

7、98061bad1=acbe位置组：(1,4,7,12),(2,5,9),(3,6,10),(8),(11)这个等式有16种不同的解答方案。排序二叉树又称二叉搜索树,二叉检索树具有以下性质对于任意一个父亲节点的值k它的左子树所有节点的值都=k根本操作插入、删除、查找平衡问题当排序二叉树的高度接近logn的时候，它是良态的，插入、删除、查找O(logn)当排序二叉树的高度接近n的时候，比较像一个链，O(n)自平衡树平衡树源自普通的排序二叉树(二叉排序树，BST)平衡树的纯手写版现今比赛比较少用没有用到高级功能的话一般用set或map代替，非常方便 ,甚至用来当作优先队列 如果要用到高级功能的话可

8、以尝试用线段树或树状数组代替手写版种类： RB-tree, AVL, splay, treap=tree+heap, SBT(推荐)平衡树旋转操作2007IOI国家集训队论文陈启峰 Size Balanced Tree平衡树平衡树常用根本功能：1.插入，删除2.求最大，最小，求排序后的前驱和后继平衡树不太常用的高级功能1.求第K大2.合并NOI2004郁闷的出纳员线段树线段树区间统计问题线段覆盖根本操作建树、插入或删除一条线段RMQ求数列任意区间的最大值、最小值离散化统计例子在数轴上进行一系列操作。每次操作有两种类型，一种是在线段a,b上涂上颜色，另一种将a,b上的颜色擦去。问经过一系列的操作

9、后，有多少条单位线段k,k+1被涂上了颜色。删除的改进一般来说线段树中线段的删除只能把已经放入的线段删掉改进的实现方法见IOI2004国家集训队论文薛矛?解决动态统计问题的两把利刃?推广这是一棵以矩形(1,1,4,3)为根的矩形树：(1,1)(4,3)(1,2)(2,3)(2,2)(4,3)(1,1)(2,2)(2,1)(4,2)(2,2)(3,3)(3,2)(4,3)(2,1)(3,2)(3,1)(4,2)树状数组相对于线段树而言： 局限性：修改操作必须针对点查询操作区间左端点必须是起点优点：编程复杂度巨低时空效率远高于线段树问题给定1000个字符串，每个长度不超过10000，现在请统计出现次数在前100次的字符串内容，并将其内容以及次数输出注：只有小写字母Trie字典树struct nodechar c;struct node *a26;考虑时间？考虑空间？时间复杂度1000*10000*对当前所有字符串取出前100个)加堆优化以后(1000*10000*log100)=7*1075S可以通过空间复杂度(最坏不到107)，实际中大大节省空间Trie树优化字符串查找，查找复杂度为字符