经典算法题目

《经典算法题目》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一部分经典的算法1KMP1.1分析ＫＭＰ算法的思路：假设从源字符串第i-j个字符开始比较，当比较到j个元素时不相等，也就是说s[i-j,j]=d[0,j-1],一般的算法是从源字符串s的i-j+1开始比较，但是KMP不是，他让i的位置不变，即源字符串还是从i的位置开始比较，而变化j的位置，j=k，其中d[0,k-1]=d[j-k,j-1],从比较过程和上面的图可以知道，实际上已经知道了d[j-k,j-1]=s[i-k,i-1]=s[0,k-1],也就是说s[0,k-1]=d[j-k,j-1],他们不用比

2、较了，直接从k开始比较就可以了。所以求出状态数组next[],next[j]表示要查找字符串中d的第j位字符不匹配时，下一个j从next[j]开始比较，即令j=next[j];所以关键是对要查找字符串d求出其状态数组next[];1.2Kmp算法的正确性分析实际上前缀数组=后缀数组是正确的，因为不存在下面的情况：因为如果d[0-k-1]=d[j-k,j-m],而d[k]!=d[j-m+1]的话，那么就不用往下面比较了。所以一定是找一个最长后缀数组=前缀数组。1.3源码KMP思想：在匹配过程中，若发生不匹配

3、的情况，如果next[j]>=0;则目标指针i不变，将模式串的指针j移动到next[j]的位置继续进行匹配；若next[j]=-1,则将i右移一位，并将j置0，继续进行比较。//返回的小标是从0开始算起的intKMPMatch(constchar*source,constchar*matchStr){assert(source!=NULL&&matchStr!=NULL);intmatchSize=strlen(matchStr);intsourceSize=strlen(source);intKMPNe

4、xt[matchSize];inti=0,j=0;getKMPNext(source,KMPNext);while(i

5、

6、source[i]==matchStr[j])//j==-1表示第一个字符不匹配{i++;j++;}elsej=KMPNext[j];if(j==matchSize)returni-j;}return-1;}求next[]数组，递推法：首先初始化next[0]=-1表示第一个字符就不匹配，假设next[j]=k,即p[0,k-1]==p[j-k

7、,j-1]1)若p[j]=p[k]则有p[0,k]==p[j-k,k]很显然next[j+1]=next[j]+1=k+1;2)若p[j]!=p[k],则可以把它看做匹配失败的时候，k值如何移动，显然k=next[k]实际上，上面就是一个动态规划过程，//递推法，实际上也是动态规划算法voidgetKMPNext(constchar*str,intKMPNext[]){assert(str!=NULL&&KMPNext!=NULL);KMPNext[0]=-1;intj=0,k=-1;intstrSize

8、=strlen(str);while(j

9、

10、str[j]==str[k]){j++;k++;KMPNext[j]=k;//注意这个时候KMPNext[j]=k不一定等于KMPNext[j-1]+1}elsek=KMPNext[k];}}第二部分基本的算法1树的三种非递归遍历1.1前序遍历voidpreOrder(TreeNode*head){assert(head!

11、=NULL);statcks;s.push(head);while(!s.empty()){TreeNode*node=s.top();s.pop();visit(node);if(node->right!=NULL)s.push(node->right);if(node->left!=NULL)s.push(node->left);}}1.2中序遍历voidinOrder(TreeNode*head){assert(head!=NULL);statcks;Tr

12、eeNode*current=head;while(!s.empty()

13、

14、current!=NULL){if(current!=NULL){s.push(current);current=current->left;}else{current=s.top();s.pop();visit(current);current=current->right;}}}1.3后序遍历voidpostOrder(TreeNode*head)