数据结构(3).ppt

数据结构数据结构长沙市一中长沙市一中 曹利国曹利国怎样授数据结构知识课怎样授数据结构知识课n把握数据结构的基本概念，要求学生领把握数据结构的基本概念，要求学生领会会“数据数据”和和“结构结构”的内涵的内涵n对问题不盲目地套某种数据结构，要学对问题不盲目地套某种数据结构，要学会根据数据的特点构造出自己的结构会根据数据的特点构造出自己的结构n数据结构和算法是紧密联系，没有离开数据结构和算法是紧密联系，没有离开算法的数据结构算法的数据结构n广泛地吸取新的知识点，掌握不同结构广泛地吸取新的知识点，掌握不同结构构造后的时空效率及其他特点构造后的时空效率及其他特点概述 数据结构是研究非数值计算的程序设数据结构是研究非数值计算的程序设计问题中的计算机的操作对象以及它们之计问题中的计算机的操作对象以及它们之间的关系和操作等等的学科。间的关系和操作等等的学科。相关定义n数据（数据（data）是对客观事物的符号的表示。例是对客观事物的符号的表示。例如数值、图像、声音都属于数据的范畴。如数值、图像、声音都属于数据的范畴。n数据元素（数据元素（data element）是数据的基本单是数据的基本单位位 n数据对象（数据对象（data object）是性质相同的数据是性质相同的数据元素的集合，是数据的一个子集。元素的集合，是数据的一个子集。n数据结构（数据结构（data structure）是相互之间存在是相互之间存在一种或多种特定关系的数据元素的集合。一种或多种特定关系的数据元素的集合。数据结构的内涵1.“操作操作”的对象：数据。的对象：数据。2.数据与数据间的关系。数据与数据间的关系。3.针对数据的基本操作。针对数据的基本操作。据此，数据结构可以形式定义为：据此，数据结构可以形式定义为：数据结构是一个二元组数据结构是一个二元组 Data_Structure=(D,S)存储结构n逻辑结构：数据元素之间的逻辑关系。逻辑结构：数据元素之间的逻辑关系。n物理结构：数据结构在计算机中的存储方式。物理结构：数据结构在计算机中的存储方式。n顺序存储结构：借助元素在存储器中的相对位置顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。逻辑上关联的来表示数据元素之间的逻辑关系。逻辑上关联的数据元素，物理存储结构中相邻。数据元素，物理存储结构中相邻。n链式存储结构链式存储结构：借助元素存储地址的指针：借助元素存储地址的指针（pointer）表示数据元素之间的逻辑关系表示数据元素之间的逻辑关系。逻。逻辑上关联的数据元素，物理存储结构中不一定相辑上关联的数据元素，物理存储结构中不一定相邻。邻。几种主要的数据结构n离散结构离散结构n线性结构线性结构n树形结构树形结构n图结构图结构四种数据结构类型线性结构n由由n个数据元素的有限序列个数据元素的有限序列n除头元素外，每个元素都有一个前趋除头元素外，每个元素都有一个前趋n除尾元素外，每个元素都有一个后继除尾元素外，每个元素都有一个后继线性表的两种存储方式n数组数组n连续存储连续存储n易于定位，不易于插入和删除易于定位，不易于插入和删除n链表链表n非连续存储非连续存储n易于插入和删除，不易于定位易于插入和删除，不易于定位链表与数组数组数组链表链表数组的插入与删除123456789 10 11 126.5数组的插入与删除均需要移动后面的元素数组的插入与删除均需要移动后面的元素插入：插入：删除：删除：123456789 10 11 121234567891011121234567891011 12链表的插入与删除无需移动任何元素无需移动任何元素有序线性表的二分查找13812 18 22 24 27 31312查找查找12 midmidmid812找到找到12了！了！lowlowhighhighlowhigh快速排序n递归思想：递归思想：n先选一个数，把比它小的放在它左边，先选一个数，把比它小的放在它左边，把比它大的放在它右边，再分别把它的把比它大的放在它右边，再分别把它的左边和右边排序左边和右边排序栈352栈顶栈顶一种一种“后进先出后进先出”的结构的结构加入一个数加入一个数4取出栈顶元素取出栈顶元素再取出栈顶元素再取出栈顶元素6栈的应用算术达式求值：算术达式求值：n输入一个表达式，该表达式含有输入一个表达式，该表达式含有“+”、“-”、“*”、“/”、“（”、“）”和操作数，输入以和操作数，输入以结束。结束。n构造两个栈构造两个栈opnd和和optr分别存放操作数分别存放操作数和操作符和操作符n构造操作符的构造操作符的优先关系表优先关系表算法框架Function exp_reduced:oprandtype;inistack(optr);push(optr,);inistack(opnd)read(w);while not(w=)and(gettop(optr)=)do If not w in op then push(opnd,w);read(w)else case predede(gettop(optr),w)of :theta:=pop(optr);b:=pop(opnd);a:=pop(opnd);push(opnd,operate(a,theta,b);endc return(gettop(opnd)endF使用栈进行算术表达式求值表达式：表达式：3 (5 2)+7 opndoptr3(523+975 2=33 3=97+9=16结果便是结果便是16！16队列n队列是一种先进先出队列是一种先进先出(FIFO)的线性表的线性表n队列的顺序存储结构和链式存储结构队列的顺序存储结构和链式存储结构n队列必须构造成循环队列的形式队列必须构造成循环队列的形式,否则会出现否则会出现“假溢出假溢出”const maxsize=队列最大容量；队列最大容量；m=maxsize-1;type cyclcquetp=record elem:array0.m of elemtp;rear,front:0.m;end;n基本操作基本操作1.插入插入（en_cycque）2.删除删除（dl_cycque）队列3265419队列头队列头队列尾队列尾串n以字符为元素类型的线性表以字符为元素类型的线性表n用于表示文本用于表示文本串的基本操作n串的连接串的连接（concat）n求子串求子串（substr-Pascal中的中的copy函数）函数）n插入函数（插入函数（insert）n删除函数（删除函数（delete）n定位函数定位函数（index-Pascal中的中的pos函数）函数）模式匹配算法n字串的定位操作通常称作串的模式匹配字串的定位操作通常称作串的模式匹配算法算法n常规算法常规算法枚举枚举+检验检验nKMP算法是常规算法的改进，利用字串算法是常规算法的改进，利用字串的前缀函数与已得到的匹配避免了不需的前缀函数与已得到的匹配避免了不需要的比较要的比较KMP的基本原理 假设主串为假设主串为s1s2sn,模式串为模式串为p1p2pm,当模式串发当模式串发生失配生失配(sipj)时时,模式串模式串”向右滑动向右滑动”可行距离有多远可行距离有多远?假设此时应与模式中的第假设此时应与模式中的第k(kj)个字符继续比较个字符继续比较,则模则模式中的前式中的前k-1个字必须与主串的前个字必须与主串的前k-1个字符相等个字符相等,有有 p1p2pk-1=s i-k+1si-k+2si-1由已经得到的部分匹配结果可知由已经得到的部分匹配结果可知 pj-k+1pj-k+2pj-1=s i-k+1si-k+2si-1所以有所以有 p1p2pk-1=pj-k+1pj-k+2pj-1由上式可知由上式可知,当主串第当主串第i个字符与模式串第个字符与模式串第j个字符不相等时候个字符不相等时候,仅需将模式串向右滑动到模式串中的第仅需将模式串向右滑动到模式串中的第k个字符和主串中的个字符和主串中的第第i个字符对齐个字符对齐,此时模式中的头此时模式中的头k-1个字符的子串肯定与主个字符的子串肯定与主串中第串中第i个字符之前的个字符之前的k-1个子串相等。个子串相等。KMP算法过程1.求求next函数函数2.通过通过next函数求解函数求解求next函数next1=0,设设nextj=k,表明表明,p1p2pk-1=pj-k+1pj-k+2pj-1(1)若若pk=pj,则在模式串中有则在模式串中有 p1p2pk=pj-k+1pj-k+2pj 显然显然 nextj+1=k+1(2)若若pk pj,则在模式串中有则在模式串中有 p1p2pk pj-k+1pj-k+2pj 则可将求则可将求next函数的问题看成整个模式串既是主串又是函数的问题看成整个模式串既是主串又是模式串的问题模式串的问题,应将模式串滑动到应将模式串滑动到nextk个字符和主串的第个字符和主串的第j个字符相比较个字符相比较.若若nextk=k,且且pj=pk,则说明在主串中第则说明在主串中第j+1个字符之前存在一个长度为个字符之前存在一个长度为k的最长子串的最长子串,和模式串中从和模式串中从首字符起长度为首字符起长度为k的子串相等的子串相等,即即 p1p2pk pj-k+1pj-k+2pj也就是说也就是说nextj+1=k+1=nextk+1求next算法nProc get_next(t:strtp)n next为全程变量为全程变量nj:=1;k:=0;next1:=0;nWhile jt.curlen do n if(k=0)or(t.chj=t.chk)n then j:=j+1;k:=k+1;nextj:=kn else k:=nextknendP求next函数过程模式串：模式串：next函数：函数：a b a b c a0 1 1 2 3 1a b a b c anext函数求解完成！函数求解完成！通过next函数求解a b c a b a b c aa b a b c a0 1 1 2 3 1模式串：模式串：主串：主串：next函数：函数：找到了！找到了！a b a b c a1 0例题分析例一例一求一个字符串中最长的重复子串。求一个字符串中最长的重复子串。例二例二一个一个M行行N列的整数矩阵，试确定列的整数矩阵，试确定起始列起始列S和终止列和终止列T，以及在列以及在列S、列列S+1，列列T1，列列T的每一列中的每一列中选取一个数，使这（选取一个数，使这（TS+1）个数的个数的和最大。设计算法求出最大和和最大。设计算法求出最大和Pmax(1M100，11，则双亲是则双亲是i/2n(2)如果如果2in，则结点则结点i无左孩子，否则左孩子无左孩子，否则左孩子为为2in(3)如果如果2i+1n，则结点则结点i无右孩子，否则右无右孩子，否则右孩子为孩子为2i+1树的遍历n多叉树的遍历多叉树的遍历n前序遍历前序遍历n后序遍历后序遍历n二叉树的遍历二叉树的遍历n前序遍历前序遍历n中序遍历中序遍历n后序遍历后序遍历多叉树转二叉树n用二叉树表示一棵树要比多叉树用二叉树表示一棵树要比多叉树简单些，而且多叉树都可以转换简单些，而且多叉树都可以转换成唯一的二叉树。成唯一的二叉树。n对于多叉树中的每个节点，可以对于多叉树中的每个节点，可以用两个指针分别指向它的第一个用两个指针分别指向它的第一个子节点和下一个相邻节点。子节点和下一个相邻节点。多叉转二叉的例子在下图中，在下图中，每个节点的每个节点的左子节点为左子节点为它原来的第它原来的第一个子节点，一个子节点，右子节点为右子节点为它的第一个它的第一个兄弟节点兄弟节点 748149316527481493165274814931652二叉排序树n二叉排序树的特征二叉排序树的特征每个节点每个节点的值，都比它的左子节点大，比的值，都比它的左子节点大，比他的右子节点小（或者反之）。他的右子节点小（或者反之）。n二叉排序树可用于动态查找二叉排序树可用于动态查找n二叉排序树的平衡二叉排序树的平衡二叉排序树用于动态查找12623381825195297查找查找7找到了找到了!二叉排序树的操作效率 二叉排序树不能总保持叶子节点二叉排序树不能总保持叶子节点深度基本相同，这对各项操作的时间深度基本相同，这对各项操作的时间复杂度影响很大，因此有需要进行平复杂度影响很大，因此有需要进行平衡操作。衡操作。AVL树nAVL树提供了一套平衡操作方法树提供了一套平衡操作方法nAVL树的平衡思想树的平衡思想当某项操当某项操作使得二叉排序树不平衡了（某作使得二叉排序树不平衡了（某个节点左右子树深度差个节点左右子树深度差大于大于1时）时），就进行操作使其恢复平衡，就进行操作使其恢复平衡LR式：式：62464135721 35 7RL式：式：26464735121 35 7AVL树的平衡操作3LL式：式：4215352141RR式：式：245133452哈夫曼编码与哈夫曼树n哈夫曼编码的由来哈夫曼编码的由来n哈夫曼编码的特点哈夫曼编码的特点 带权路径长度最小带权路径长度最小n构造二叉哈夫曼树构造二叉哈夫曼树n推广至多叉哈夫曼树推广至多叉哈夫曼树构造二叉哈夫曼树1.选取值最小的两个根选取值最小的两个根节点节点a和和b。创建一创建一个新节点，其权值就个新节点，其权值就是是a、b的权值之和，的权值之和，左右子树分别为左右子树分别为a、b这两个节点。这两个节点。2.重复重复1步骤，直至只步骤，直至只有一个根节点（即所有一个根节点（即所有节点都在同一棵树有节点都在同一棵树中）。中）。1249108371915344910819并查集n什么是并查集什么是并查集n并查集是多叉树并查集是多叉树n并查集是用树型结构实现的一种特殊的集合并查集是用树型结构实现的一种特殊的集合n并查集的操作并查集的操作n判断两个节点是否在同一个集合中判断两个节点是否在同一个集合中n合并两个集合合并两个集合n并查集有什么优势并查集有什么优势n两种操作的时效都非常高两种操作的时效都非常高n空间代价为空间代价为O(n)，每个节点保存其父节点每个节点保存其父节点并查集的操作1.判断两个节点是否在同一个集合中判断两个节点是否在同一个集合中2.合并两个集合合并两个集合并查集操作的关键并查集操作的关键维护并查集维护并查集1235648710判断判断5与与10是否在同一个集合中是否在同一个集合中第一步：上溯第一步：上溯11第二步：上调第二步：上调41087合并合并11和和10所在的集合所在的集合第一步：上溯第一步：上溯第二步：合并第二步：合并第三步：上调第三步：上调二叉堆n二叉堆是完全二叉树二叉堆是完全二叉树n任意父节点的值大于两个子节点的任意父节点的值大于两个子节点的值或任意父节点的值小于两个子节值或任意父节点的值小于两个子节点的值点的值n父父子，则堆顶元素值一定最大子，则堆顶元素值一定最大n父父子，则堆顶元素值一定最小子，则堆顶元素值一定最小堆排序堆排序的基础堆排序的基础选择排序选择排序堆排序的实质是利用二叉堆优化选择排序堆排序的实质是利用二叉堆优化选择排序堆排序步骤：堆排序步骤：n建堆。将所有节点布置成堆结构建堆。将所有节点布置成堆结构n取出堆顶节点，放入列表末尾取出堆顶节点，放入列表末尾n把堆尾的节点移动至顶部，调整此节点把堆尾的节点移动至顶部，调整此节点n跳转至跳转至2步骤，直至堆为空步骤，直至堆为空堆排序建堆3建堆开始6575231387715216 3613建堆完毕堆排序选择与维护13235537687取出堆顶节点7127 37288338 68一、取出二、调整堆排序算法nPROC shift(var r:listtype;k,m:integer);n i:=k.j:=2*I;x:=rk.key;finish:=false t:=rk;n while(j=m)and not finish do n if(jrj+1.key)then j:=j+1;n If x=rj.key then finish:=truen Else ri:=rj;i:=j;j:=2*I n nri:=tnendPnPROC heapsort(var r:listtype);nFor i:=n/2 downto 1 shift(r,I,n);nFor i:=n downto 2 do r1与与ri交换交换;n shift(r,1,i-1)nendP图结构n图结构包括：图结构包括：n点点n边边n图涉及到的概念图涉及到的概念n边的权边的权n点的度点的度图的储存结构n矩阵矩阵n邻接表邻接表n邻接多重表邻接多重表n十字链表十字链表123121323邻接多重表n邻接多重表是一种用于保存无向图邻接多重表是一种用于保存无向图的数据结构的数据结构n每条边只有一个节点是比起邻接表每条边只有一个节点是比起邻接表来最大的优势。它可以方便地对边来最大的优势。它可以方便地对边进行标记操作。进行标记操作。123112132323十字链表n十字链表与邻接多重表类似。十字链表与邻接多重表类似。123inout112outinnumfromto图的遍历n深度优先搜索深度优先搜索n递归过程递归过程ndfn值与时间戳值与时间戳n广度优先搜索广度优先搜索n扩展队列扩展队列图的连通性问题n有向图的强有向图的强连通子图连通子图n最小点基问题最小点基问题n生成树问题生成树问题强连通子图n有向图的强连通子有向图的强连通子图图n强连通子图中，人强连通子图中，人两个节点都直接或两个节点都直接或间接相连间接相连n以深度优先搜索为以深度优先搜索为基础的算法基础的算法14278536生成树问题n无向图的最小生成树（贪心思想）无向图的最小生成树（贪心思想）nPrim算法，适用于点少的图算法，适用于点少的图nKruskal算法，适用于边少的图算法，适用于边少的图n有向图的最小生成树有向图的最小生成树Prim算法1.将将1号节点置入集合号节点置入集合S中。中。2.找到所有连接找到所有连接S中的节点和中的节点和非非S中的节点的边中的权值中的节点的边中的权值最小的那一条，并标记这最小的那一条，并标记这条边，同时将连接的非条边，同时将连接的非S中中的节点加入的节点加入S集合。集合。3.重复重复2步骤，直到所有节点步骤，直到所有节点都在都在S中了。中了。1243561231231212Kruskal算法1.找到连接两个不同连通找到连接两个不同连通分量（由已标记的边构分量（由已标记的边构成的）的边中，权值最成的）的边中，权值最小的那一条，标记这条小的那一条，标记这条边。边。2.重复重复1步骤，直到所有步骤，直到所有节点都在同一连通分量节点都在同一连通分量中。中。1243561231231212图的拓扑结构n拓扑排序拓扑排序n顶点表示活动的网顶点表示活动的网AOV-网网n例如课程选择中课程之间的关系例如课程选择中课程之间的关系n关键路径关键路径n边表示活动的网边表示活动的网AOE-网网n求图中总长最长的路径求图中总长最长的路径n例如计算工程所需时间例如计算工程所需时间拓扑排序算法1.寻找入度为寻找入度为0的节点的节点2.将找到的节点放入队列中，删除所有将找到的节点放入队列中，删除所有这个节点引出的边这个节点引出的边3.重复重复1，直至没有度为，直至没有度为0的节点的节点4.如果有节点不在队列中，则说明原图如果有节点不在队列中，则说明原图中有环，否则无环。中有环，否则无环。1253647求关键路径算法n对给定的图进行拓扑排序对给定的图进行拓扑排序n按照拓扑排序的结果扩展和标记按照拓扑排序的结果扩展和标记12345687964511247924最短路问题n单源最短路单源最短路 Dijkstra算法算法n多源最短路多源最短路 Floyd-Warshall算法算法Dijkstra算法nDijkstra算法中心算法中心 +124331632+0Dist值值4321节点号节点号3 32 26 6 5 5 4 4选择选择标记标记扩展扩展任意顶点对之间的最短路假假设设求求从从vi到到vj的的最最短短路路径径,如如果果vi到到vj有有弧弧,则则它它们们的的路路径径为为costi,j,否否则则需需要要进进行行n次次试试探探,首首先先考考虑虑(vi v1 vj),比比较较它它与与(vi vj)的的大大小小,取取较较短短者者为为中中间间节节点点序序号号不不大大于于1的的最最短短路路径径,ji假假如如(vi,v2)和和(v2,vj)都都是是中中间间节节点点序序号号不不大大于于1的的最最短短路路径径,那那么么(vi,v2,vj)可可能能是是中中间间节节点点序序号号不不大大于于2的的最最短短路路径径.将将它它和和中中间间节节点点序序号号不不大大于于1的的最最短短路路相相比比较较,从从中中选选出出中中间间节节点点的的序序号号不不大大于于2的的最最短短路路径径之之后后,再再增增加加一一个个顶顶点点v3,继继续续进进行行试试探探.这这样样进进行行n次次试试探探后后,最最后后得得到到必然是必然是vi到到vj的最短路径。的最短路径。Floyd-Warshall算法过程dist数组的初始值为所有边的情况数组的初始值为所有边的情况For k:=1 To vtxnum Do 枚举中间点枚举中间点 For i:=1 To vtxnum Do 枚举起点枚举起点 For j:=1 To vtxnum Do 枚举终点枚举终点 If disti,k+distk,jdisti,j Then disti,j:=disti,k+distk,j最后的结果仍旧保存在最后的结果仍旧保存在dist数组中数组中网络流与匹配问题n网络最大流网络最大流n最小费用最大流最小费用最大流n二分图的最大匹配二分图的最大匹配n二分图的最佳匹配二分图的最佳匹配网络流算法n寻找增广链，并根据增广链修改流寻找增广链，并根据增广链修改流量。重复这一步骤，直到不再存在量。重复这一步骤，直到不再存在增广链。增广链。n如果需要在此基础上求最小费用最如果需要在此基础上求最小费用最大流，只需从增广链的选择上着手。大流，只需从增广链的选择上着手。二分图与匹配算法n二分图的匹配算法又称匈牙利算法二分图的匹配算法又称匈牙利算法n匈牙利算法的中心匈牙利算法的中心可增广轨可增广轨n不断寻找可增广轨，并根据可增广不断寻找可增广轨，并根据可增广轨修改匹配轨修改匹配n最佳匹配只是在选择可增广轨时，最佳匹配只是在选择可增广轨时，将匹配的权值作为选择的条件将匹配的权值作为选择的条件图中的链与回路n负权回路负权回路Bellman-Fordn欧拉路与欧拉回路欧拉路与欧拉回路n哈密顿回路哈密顿回路负权回路n判断图中是否存在负权回路判断图中是否存在负权回路nBellman-Ford算法的中心算法的中心迭迭代代思想思想n迭代的结束条件迭代的结束条件n重复了重复了2n轮依旧可以更新轮依旧可以更新有负权有负权回路回路n未完成未完成2n轮已经无法更新轮已经无法更新无负权无负权回路回路欧拉路与欧拉回路n问题的原型问题的原型边的无重复遍历边的无重复遍历n两个基本概念两个基本概念n奇点奇点度为奇数的点度为奇数的点n偶点偶点度为偶数的点度为偶数的点n欧拉路存在的条件欧拉路存在的条件2个奇点个奇点n欧拉回路存在的条件欧拉回路存在的条件0个奇点个奇点哈密顿回路n问题的原型问题的原型点的无重复遍历点的无重复遍历n搜索方法搜索方法哈希函数与哈希表n哈希函数就是关键字集合与地址哈希函数就是关键字集合与地址集合的映像集合的映像n哈希表常用于搜索过程中状态是哈希表常用于搜索过程中状态是否处理过的判断否处理过的判断（例如：八数码问题）（例如：八数码问题）例题选讲例一、合并果子例一、合并果子有许多果子，按不同种类分成了不同的堆。现在想把所有许多果子，按不同种类分成了不同的堆。现在想把所有的果子合成一堆。每一次合并，可以把两堆果子合并到一起，有的果子合成一堆。每一次合并，可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过经过n-1次合并之后，就只剩下一堆了。假定每个果子重量都次合并之后，就只剩下一堆了。假定每个果子重量都为为1，并且已知果子的种类数和每种果子的数目，你的任务是，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使耗费的总体力最少，并输出这个最设计出合并的次序方案，使耗费的总体力最少，并输出这个最小的体力耗费值。小的体力耗费值。例如有例如有3种果子，数目依次为种果子，数目依次为1，2，9。可以先将。可以先将1、2堆堆合并，新堆数目为合并，新堆数目为3，耗费体力为，耗费体力为3。接着，将新堆与原先的。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为第三堆合并，又得到新的堆，数目为12，耗费体力为，耗费体力为12。所。所以总共耗费体力以总共耗费体力=3+12=15。可以证明。可以证明15为最小的体力耗费为最小的体力耗费值。值。很显然，在这次选取中，每次选重量很显然，在这次选取中，每次选重量最小的两堆合并，可以使得总体力最小。最小的两堆合并，可以使得总体力最小。所以，应该有一个数据结构能够快速完成所以，应该有一个数据结构能够快速完成这两种操作：这两种操作：n取出最小的值取出最小的值n插入一个值插入一个值由于只需要这两种操作，相比之下，由于只需要这两种操作，相比之下，选用二叉堆既简单又快速。选用二叉堆既简单又快速。例二、八数码问题例二、八数码问题在在3*3的棋盘中放入的棋盘中放入1,2,3,8这这8个数字，个数字，给出一个初始状态和目标状态给出一个初始状态和目标状态(如下图如下图)，要求用最少的步数将初始状态移动到目标要求用最少的步数将初始状态移动到目标状态。移动时，任何一个与空格位置上下状态。移动时，任何一个与空格位置上下左右相邻的数字可以移动到空格位置。左右相邻的数字可以移动到空格位置。搜索中的判重：使用哈希表，用19!恰好对应每种状态。判重只需O(1)的时间。例三、营业额统计试题大意：输入n个正整数，输出每个正整数与其前面的正整数差的绝对值的最小值的和。即 （其中1ji-1）.本题需要进行插入和查找两种操作，采用AVL树，每次只需O(log n)的时间。n例四、银河英雄传说n杨威利将巴米利恩星域战场划分成30000列，每列依次编号为1,2,30000。之后，他把自己的战舰也依次编号为1,2,30000，让第i号战舰处于第i列(i=1,2,30000)，这是初始阵形。当进犯之敌到达时，杨威利会多次发布合并指令，将大部分战舰集中在某几列上，实施密集攻击。合并指令为M i j，含义为让第i号战舰所在的整个战舰队列，作为一个整体（头在前尾在后）接至第j号战舰所在的战舰队列的尾部。显然战舰队列是由处于同一列的一个或多个战舰组成的。合并指令的执行结果会使队列增大。n在杨威利发布指令调动舰队的同时，莱因哈特为了及时了解当前杨威利的战舰分布情况，也会发出一些询问指令：C i j。该指令意思是，询问电脑，杨威利的第i号战舰与第j号战舰当前是否在同一列中，如果在同一列中，那么它们之间布置有多少战舰。这道题需要用到集合的合并和判断，使用并查集。