《穷举的模式匹配》由会员分享，可在线阅读，更多相关《穷举的模式匹配（2页珍藏版）》请在金锄头文库上搜索。
1、（穷举的模式匹配）算法思想：分别用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置。从主串S的第pos个字符起和模式的第一个字符比较，若相等，则继续逐个比较后继字符；否则从主串的下一个字符起再重新和模式的字符比较。依次类推，直至模式T中的每个字符依次和主串S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序号。否则称匹配不成功函数值为0。子串：串中任意连续的字符组成的子序列称为该串的子串主串：包含子串的串称为该子串的主串模式匹配：子串的定位运算称为串的模式匹配，是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串，子串称为模式
2、。穷举的模式匹配过程：第1趟STabbabaaba第2趟SabbabaTaba第3趟SabbabaTaba第4趟SabbabaTaba最小生成树的基本概念无向连通图的生成树不一定唯一迪杰斯特拉（Dijkstra）算法基本思想：设置两个顶点集S和T,S中存放已确定最短路径的顶点，T中存放待确定最短路径的顶点。（1）初始时S中仅有一个源点，T中含除源点外其余顶点，此时各顶点的当前最短长度为源点到该顶点的弧上的权值。（2）选取T中当前最短路径长度最小的一个顶点v加入S；（3）修改T中剩余顶点的当前最短路径长度，修改原则是：当v的最短路径长度与v到T中顶点之间的权值之和小于该顶点的当前最短路径长度时，
3、用前者替换后者。重复（2）、（3），直到S中包含所有顶点为止。折半查找的基本思想：在有序表中，取中间元素作为比较对象，若给定值与中间元素的关键字相等，则查找成功；若给定值小于中间元素的关键字，则在中间元素的左半区继续查找；若给定值大于中间元素的关键字，则在中间元素的右半区继续查找。不断重复上述查找过程，直到查找成功，或所查找的区域无数据元素，查找失败算法实现：设表长为n，low，high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。初始时，令low=1,high=n,mid=_（low+high）/2让k与mid指向的记录比较：若k=rmid.key，则查找成功；若krmid
4、.key，贝Vlow=mid+1重复上述操作，直至lowhigh时，查找失败Ad12345678%J91011J537|56647刁8088|921和DW12345mid678910high115I13192137話1冷80921rOW12mid34high5679101L5192137566488921FTTowmidhigh#defineM500typedefstructintkey;floatinfo;JD；intbinsrch(JDr,intn,intk)intlow,high,mid,found;low=1;high=n;found=0;/found为找到标志。值为0表示未找到。wh
5、ile(lowrmid.key)low=mid+1;elseif(k=rmid.key)found=1;elsehigh=mid-1;if(found=1)/如果已找到return(mid);/找到的记录的下标肯定为midelsereturn(0);2.二叉树的性质性质1:一棵非空二叉树的第i层上最多有2-1个结点(i第1性质2：深度为k的二叉树中，最多具有2k-1个结点。定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树完全二叉树定义：深度为k,有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点对应时，称为完全二叉树。叶子结点只可能在层次最大的两层上出现
6、。对任一结点，若其右分支下子孙的最大层次为L,则其左分支下子孙的最大层次必为L或L+1性质3:民有幷个结点的完全二叉树的深度为L10g2性质4：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(4_n)，有若i=1，则序号为i的结点是根结点。若i1,则序号为i的结点的父结点的序号为i/2。若2iv=n,则序号为i的结点的左孩子结点的序号为2i。若2in，则序号为i的结点无左孩子。若2i+1n，则序号为i的结点无右孩子贝Vn=n2+1性质5:对任何一棵二叉树T,如果其终端结点数为no,度为2的结点数为应,哈夫曼(Haffman)树：一种带权路径长度最小的二叉树，也称最优二叉树循环队列操作总结判队空：Q.front=Q.rear判队满：Q.front=(Q.rear+1)%MAXLEN入队：Q.rear=(Q.rear+1)%MAXLEN出队：Q.front=(front+1)%MAXLEN求队长:(+MAXLEN)%MAXLEN
