数据结构NOIp

NOIp数据结构长沙市一中曹利国有序线性表的二分查找1381218222427313121812查找12midmidmid812找到12了！lowlowhighhighlowhigh快速排序递归思想：先选一个数，把比它小的放在它左边，把比它大的放在它右边，再分别把它的左边和右边排序proceduresort(l,r:longint);vari,j,x,y:longint;begini:=l;j:=r;x:=times[(l+r)shr1];whilei=jdobeginwhiletimes[i]xdoi:=i+1;whiletimes[j]xdoj:=j-1;ifi=jthenbeginy:=times[i];times[i]:=times[j];times[j]:=y;i:=i+1;j:=j-1;end;end;ifljthensort(l,j);ifirthensort(i,r);End;栈352栈顶一种“后进先出”的结构加入一个数4取出栈顶元素再取出栈顶元素6栈的应用算术达式求值：输入一个表达式，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数，输入以@结束。构造两个栈opnd和optr分别存放操作数和操作符构造操作符的优先关系表算法框架Functionexp_reduced:oprandtype;inistack(optr);push(optr,’@’);inistack(opnd)read(w);whilenot((w=‘@’)and(gettop(optr)=‘@’))doIfnotwinopthen[push(opnd,w);read(w)]elsecasepredede(gettop(optr),w)of‘‘:[push(optr,w);read(w)];‘=‘:[x:=pop(optr);read(w)];‘‘:[theta:=pop(optr);b:=pop(opnd);a:=pop(opnd);push(opnd,operate(a,theta,b))];endcreturn(gettop(opnd))endF使用栈进行算术表达式求值表达式：3×(5–2)+7@opndoptr3×(5–23+975–2=33×3=97+9=16结果便是16！16队列队列是一种先进先出(FIFO)的线性表队列的顺序存储结构和链式存储结构队列必须构造成循环队列的形式,否则会出现“假溢出”constmaxsize=队列最大容量；m=maxsize-1;typecyclcquetp=recordelem:array[0..m]ofelemtp;rear,front:0..m;end;基本操作1.插入（en_cycque）2.删除（dl_cycque）队列3265419队列头队列尾串以字符为元素类型的线性表用于表示文本串的基本操作串的连接（concat）求子串（substr---Pascal中的copy函数）插入函数（insert）删除函数（delete）定位函数（index---Pascal中的pos函数）模式匹配算法字串的定位操作通常称作串的模式匹配算法常规算法——枚举+检验KMP算法是常规算法的改进，利用字串的前缀函数与已得到的匹配避免了不需要的比较KMP的基本原理假设主串为s1s2…sn,模式串为p1p2…pm,当模式串发生失配(sipj)时,模式串”向右滑动”可行距离有多远?假设此时应与模式中的第k(kj)个字符继续比较,则模式中的前k-1个字必须与主串的前k-1个字符相等,有p1p2…pk-1=si-k+1si-k+2…si-1由已经得到的部分匹配结果可知pj-k+1pj-k+2…pj-1=si-k+1si-k+2…si-1所以有p1p2…pk-1=pj-k+1pj-k+2…pj-1由上式可知,当主串第i个字符与模式串第j个字符不相等时候,仅需将模式串向右滑动到模式串中的第k个字符和主串中的第i个字符对齐,此时模式中的头k-1个字符的子串肯定与主串中第i个字符之前的k-1个子串相等。KMP算法过程1.求next函数2.通过next函数求解求next函数next[1]=0,设next[j]=k,表明,p1p2…pk-1=pj-k+1pj-k+2…pj-1(1)若pk=pj,则在模式串中有p1p2…pk=pj-k+1pj-k+2…pj显然next[j+1]=k+1(2)若pkpj,则在模式串中有p1p2…pkpj-k+1pj-k+2…pj则可将求next函数的问题看成整个模式串既是主串又是模式串的问题,应将模式串滑动到next[k]个字符和主串的第j个字符相比较.若next[k]=k’,且pj=pk’,则说明在主串中第j+1个字符之前存在一个长度为k’的最长子串,和模式串中从首字符起长度为k’的子串相等,即p1p2…pk’pj-k’+1pj-k+2…pj也就是说next[j+1]=k’+1=next[k]+1求next算法Procget_next(t:strtp){next为全程变量}j:=1;k:=0;next[1]:=0;Whilejt.curlendoif(k=0)or(t.ch[j]=t.ch[k])then[j:=j+1;k:=k+1;next[j]:=k]elsek:=next[k]endP求next函数过程模式串：next函数：ababca011231ababcanext函数求解完成！通过next函数求解abcababcaababca011231模式串：主串：next函数：找到了！ababca10例题分析〖例一〗求一个字符串中最长的重复子串。〖例二〗一个M行N列的整数矩阵，试确定起始列S和终止列T，以及在列S、列S+1，…，列T－1，列T的每一列中选取一个数，使这（T－S+1）个数的和最大。设计算法求出最大和Pmax(1≤M≤100，1N≤20001)树形结构任意两个节点之间有且只有一条路径N个顶点,U,V之间有一条边的建树程序段readln(n);fori:=1tondobeginnew(g[i]);g[i]^.next:=nil;end;fori:=1ton-1dobeginreadln(u,v);new(q);q^.data:=v;q^.next:=g[u]^.next;g[u]^.next:=q;new(q);q^.data:=u;q^.next:=g[v]^.next;g[v]^.next:=q;end;二叉树二叉树就是最多只有两个子节点的树所有叶节点深度相同的二叉树为满二叉树深度为k且有n个节点的二叉树，当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时，称之为完全二叉树二叉树的性质在二叉树的第i层上最多有2i-1个结点深度为K的二叉树最多有2k-1个结点在二叉树中,叶子结点的总数总比为度数为2的结点多1有n个结点的完全二叉树的结点按层序编号,则对任意一结点i,有(1)如果i=1,则结点i是二查树的根，无双亲；如果i1，则双亲是[i/2](2)如果2in，则结点i无左孩子，否则左孩子为2i(3)如果2i+1n，则结点i无右孩子，否则右孩子为2i+1树的遍历多叉树的遍历前序遍历后序遍历二叉树的遍历前序遍历中序遍历后序遍历多叉树转二叉树用二叉树表示一棵树要比多叉树简单些，而且多叉树都可以转换成唯一的二叉树。对于多叉树中的每个节点，可以用两个指针分别指向它的第一个子节点和下一个相邻节点。多叉转二叉的例子在下图中，每个节点的左子节点为它原来的第一个子节点，右子节点为它的第一个兄弟节点748149316527481493165274814931652二叉排序树二叉排序树的特征——每个节点的值，都比它的左子节点大，比他的右子节点小（或者反之）。二叉排序树可用于动态查找二叉排序树的平衡二叉排序树用于动态查找12623381825195297查找7找到了!二叉排序树的操作效率二叉排序树不能总保持叶子节点深度基本相同，这对各项操作的时间复杂度影响很大，因此有需要进行平衡操作。AVL树AVL树提供了一套平衡操作方法AVL树的平衡思想——当某项操作使得二叉排序树不平衡了（某个节点左右子树深度差大于1时），就进行操作使其恢复平衡LR式：62464135721357RL式：26464735121357AVL树的平衡操作3LL式：4215352141RR式：245133452哈夫曼编码与哈夫曼树哈夫曼编码的由来哈夫曼编码的特点——带权路径长度最小构造二叉哈夫曼树推广至多叉哈夫曼树构造二叉哈夫曼树1.选取值最小的两个根节点a和b。创建一个新节点，其权值就是a、b的权值之和，左右子树分别为a、b这两个节点。2.重复1步骤，直至只有一个根节点（即所有节点都在同一棵树中）。1249108371915344910819并查集什么是并查集并查集是多叉树并查集是用树型结构实现的一种特殊的集合并查集的操作判断两个节点是否在同一个集合中合并两个集合并查集有什么优势两种操作的时效都非常高空间代价为O(n)，每个节点保存其父节点元素的合并图示13245合并1和2合并1和3合并5和4合并5和3判断元素是否属于同一集合用father[i]表示元素i的父亲结点，如刚才那个图所示12354faher[1]=1faher[2]=1faher[3]=1faher[4]=5faher[5]=3判断元素是否属于同一集合由此用某个元素所在树的根结点表示该元素所在的集合判断两个元素时候属于同一个集合的时候，只需要判断他们所在树的根结点是否一样即可也就是说，当我们合并两个集合的时候，只需要在两个根结点之间连边即可并查集的操作1.判断两个节点是否在同一个集合中2.合并两个集合并查集操作的关键——维护并查集1235648710判断5与10是否在同一个集合中第一步：上溯11第二步：上调41087合并11和10所在的集合第一步：上溯第二步：合并第三步：上调路径压缩上述的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见判断两个元素是否属于同一集合需要O(N)的时间，于是路径压缩产生了作用路径压缩实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点路径压缩示意图13245由此我们得到了一个复杂度只是O(1)的算法程序清单functiongetfather(v:integer):integer;beginif(father[v]=0)thengetfather:=velsebeginfather[v]:=getfather(father[v]);getfather:=father[v];end;end;程序清单functionjudge(x,y:integer):boolean;varfx,fy:integer;beginfx:=getfaher(x);fy:=gefather(y);Iffx=fythenjudge:=exit(true)elsejudge:=false;father[fx]:=fy;{合并两个集合}end;例1亲戚若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。例1亲戚数据输入：第一行：三个整数n,m,p，（n=5000,m=5000,p=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。以下m行：每行两个数Mi，Mj，1=Mi，Mj=N，表示Ai和Bi具有亲戚关系。接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。数据输出：P行，