2019-04-29 20:28:34 qq_37998081 阅读数 38
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3320 人正在学习 去看看 佟刚

大话数据结构之串与模式匹配KMP

坚持用blog记录学习之路,加油

2019.4.29

音乐陈百强《偏偏喜欢你》

typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */
// init
Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
			T[i]=*(chars+i-1);
		return OK;
	}
}

//strcopy
Status StrCopy(String T,String S)
{ 
	int i;
	for(i=0;i<=S[0];i++)
		T[i]=S[i];
	return OK;
}

//empty?
Status StrEmpty(String S)
{ 
	if(S[0]==0)
		return TRUE;
	else
		return FALSE;
}

//strcompare
//clear
//length
//strcat
// substring
//index
//insert
//sredelete
//replace
  • 模式匹配
//朴素模式匹配
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
	int j = 1;				/* j用于子串T中当前位置下标值 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
	{
		if (S[i] == T[j]) 	/* 两字母相等则继续 */
      	{
			++i;
         	++j; 
      	} 
      	else 				/* 指针后退重新开始匹配 */
      	{  
         	i = i-j+2;		/* i退回到上次匹配首位的下一位 */
         	j = 1; 			/* j退回到子串T的首位 */
      	}      
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

//KMP
//getnext
void get_next(String T, int *next) 
{
	int i,j;
  	i=1;
  	j=0;
  	next[1]=0;
  	while (i<T[0])  /* 此处T[0]表示串T的长度 */
 	{
    	if(j==0 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符,T[j]表示前缀的单个字符 */
		{
      		++i;  
			++j;  
			next[i] = j;
    	} 
		else 
			j= next[j];	/* 若字符不相同,则j值回溯 */
  	}
}

//kmp
int Index_KMP(String S, String T, int pos) 
{
	int i = pos;		/* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
	int j = 1;			/* j用于子串T中当前位置下标值 */
	int next[255];		/* 定义一next数组 */
	get_next(T, next);	/* 对串T作分析,得到next数组 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
	{
		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续,与朴素算法增加了j=0判断 */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* 指针后退重新开始匹配 */
      	 	j = next[j];/* j退回合适的位置,i值不变 */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}



2017-11-20 11:09:22 zjiang1994 阅读数 117
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3320 人正在学习 去看看 佟刚

大话数据结构笔记-串

串(string)是有零个或多个字符组成的有限序列,有名叫字符串。

  • 串中字符数目为串的长度
  • 零个字符的串称为空串

字符串比较,先比较位数,位数多的大,再从高位比较到低位(ASCII)。

模式匹配算法

朴素的模式匹配算法
子串的定位操作通常称作串的模式匹配。

最蠢:主串大循环

KMP模式匹配算法

大大避免重复遍历的情况,具体的自己慢慢研究。

2018-08-24 23:30:46 qq_36770641 阅读数 387
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3320 人正在学习 去看看 佟刚

串这一节在大一学数据结构时老师并没有着重讲解,只让我们会求一个字符串的next数组就行了,这次学习的时候认真看了下,也花了挺长时间的,好好总结一下:

1、串的匹配是串的基础同时也非常重要的操作,最初人们用朴素的模式匹配算法,即:

int Index(String S, String T, int pos){    //在主串S中找到从pos开始与子串T相匹配的第一个字符的位置
    int i=pos;
    int j=1;
    while(i<=S[0]&&j<=T[0]){    // 注意i<=S[0]和j<=T[0]要同时满足
        if(S[i]==T[j]){    //匹配一致,则均后移继续匹配
            i++;
            j++;
        }
        else{        //匹配不一致,则主串下标后移一位,子串下标置1
            i=i-j+2;
            j=1;
        }
    }
    if(j>T[0])    //j>T[0]说明子串全部比较完且与主串中某一部分一致
        return i-T[0];	// 注意i才是主串的下标,i-T[0]返回开始匹配的位置
    else
        return 0;
}

主要特征是当匹配不一致时,主串的下标会后移一位,而子串下标直接置1从头开始比较。

这种方法有什么不好呢?来看一个极端情况:

主串为S="00000000000000000000000000000000000000000000000001",而要匹配的子串为T="0000000001",前者是有49个“0”和1个“1”的主串,后者是9个“0”和1个“1”的子串。在匹配时,每次都得将T中字符循环到最后一位才发现:哦,原来它们是不匹配的。这样等于T串需要在S串的前40个位置都需要判断10次,并得出不匹配的结论,如图5-6-6所示。

直到最后第41个位置,因为全部匹配相等,所以不需要再继续进行下去,如图5-6-7所示。如果最终没有可匹配的子串,比如是T="0000000002",到了第41位置判断不匹配后同样不需要继续比对下去。因此最坏情况的时间复杂度为O((n-m+1)*m)。

如何改进?

 

2、KMP模式匹配算法发现了朴素算法的不足,主要特点是:

   1)、待匹配串某几位互不相等,而它们又在主串中有对应的子串,当后一位匹配失败时,待匹配串中的这几位不必再与主串中明显与自己不相等的字符去比较;

   2)、待匹配串中存在回文相等,且它们在主串中有对应的子串,当后一位匹配失败时,待匹配串中回文串的前几位不必再与主串中明显与自己相等的字符去比较。

// 通过计算返回子串T的next数组
void get_next(String T, int *next){
    int i,j;
    i=1;
    j=0;
    next[1]=0;
    // 此处T[0]表示串T的长度
    while(i<T[0]){
        // T[i]表示后缀的单个字符
        // T[j]表示前缀的单个字符
        if(j==0 || T[i]==T[j]){
            ++i;
            ++j;
            next[i]=j;
        }
        else
            // 若字符不相同,则j值回溯
            j=next[j];
    }
}


// 返回子串T在主串S中第pos个字符之后的位置。
// 若不存在,则函数返回值为0
// T非空,1<=pos<=StrLength(S)
int Index_KMP(String S, String T, int pos){
    // i 用于主串S当前位置下标值,若pos不为1,则从pos位置开始匹配
    int i=pos;
    //j 用于子串T中当前位置下标值
    int j=1;
    // 定义next数组
    int next[255];
    
    // 对串T作分析,得到next数组
    get_next(T,next);
   
    // 若i小于S的长度且j小于T的长度时,循环继续
    while(i<=S[0] && j<=T[0]){
        // 两字母相等则继续,相对于朴素算法增加了
        // j=0 判断
        if(j==0||S[i]==T[j]){
            ++i;
            ++j;
        }
        // 指针后退重新开始匹配
        else{
            // j退回合适的位置,i值不变
            j=next[j];
        }
    }
    if(j>T[0]){
        return i-T[0];
    }
    else
        return 0;
}

简而言之就是,比较过的,明显不相等的,不用再比;比较过的,明显相等的,也不用再比。由此,效率大大提升。

若T的长度为m,因只涉及到简单的单循环,其时间复杂度为O(m),而由于i值的不回溯,使得KMP算法效率得到了提高,while循环的时间复杂度为O(n)。因此,整个算法的时间复杂度为O(n+m)。相较于朴素模式匹配算法的O((n-m+1)*m)来说,是要好一些。

这里也需要强调,KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势,否则两者差异并不明显。

 

3、KMP模式匹配算法的改进:

考虑这样一种情况:待匹配串的前i位均为同一字符,且与主串匹配成功,第i+1位仍为这个字符,而主串中则不是,此时匹配失败。这时如果用上述KMP算法,会发现next[i+1]=i,所以又从i位开始匹配,还是同样的失败——又从i-1位,i-2位,....,一直到第一位。我们会发现,这些比较是不必要的。因为前i+1位字符都相同,第i+1位不匹配,前i位肯定也不匹配。故对KMP算法作以下改进:(并引入nextval数组)

   1)、若当前字符与前缀字符不同,则当前的j为nextval在i位置的值;

   2)、若当前字符与前缀字符相同,则将前缀字符的nextval值赋值给nextval在i位置的值。

//KMP模式匹配算法的改进

// 求模式串T的next函数修正值并存入数组nextval
void get_nextval(String T,int *nextval){
    int i,j;
    i=1;
    j=0;
    nextval[1]=0;
    while(i<T[0]){
        if(j==0||T[i]==T[j]){
            i++;
            j++;
            // 若当前字符与前缀字符不同
            if(T[i]!=T[j])
                // 则当前的j为nextval在i位置的值
                nextval[i]=j;
            else
                //如果与前缀字符相同,则将前缀字符的nextval值赋值给nextval在i位置的值
                nextval[i]=nextval[j];
        }
        else
            //若字符不相同,则j值回溯
            j=nextval[j];
    }
}

关于串的KMP模式匹配算法的个人总结大致如上。

 

--------------------------------------------------------

 

以下是摘录自《大话数据结构》的详细讲解:

概念引入

如果主串S="abcdefgab",其实还可以更长一些,我们就省略掉只保留前9位,我们要匹配的T="abcdex",那么如果用前面的朴素算法的话,前5个字母,两个串完全相等,直到第6个字母,“f”与“x”不等,如图5-7-1的①所示。

接下来,按照朴素模式匹配算法,应该是如图5-7-1的流程②③④⑤⑥。即主串S中当i=2、3、4、5、6时,首字符与子串T的首字符均不等。

似乎这也是理所当然,原来的算法就是这样设计的。可仔细观察发现。对于要匹配的子串T来说,“abcdex”首字母“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说,既然“a”不与自己后面的子串中任何一字符相等,那么对于图5-7-1的①来说,前五位字符分别相等,意味着子串T的首字符“a”不可能与S串的第2位到第5位的字符相等。在图5-7-1中,②③④⑤的判断都是多余。

注意这里是理解KMP算法的关键。如果我们知道T串中首字符“a”与T中后面的字符均不相等(注意这是前提,如何判断后面再讲)。而T串的第二位的“b”与S串中第二位的“b”在图5-7-1的①中已经判断是相等的,那么也就意味着,T串中首字符“a”与S串中的第二位“b”是不需要判断也知道它们是不可能相等了,这样图5-7-1的②这一步判断是可以省略的,如图5-7-2所示。

同样道理,在我们知道T串中首字符“a”与T中后面的字符均不相等的前提下,T串的“a”与S串后面的“c”、“d”、“e”也都可以在①之后就可以确定是不相等的,所以这个算法当中②③④⑤没有必要,只保留①⑥即可,如下图所示。

之所以保留⑥中的判断是因为在①中T[6]≠S[6],尽管我们已经知道T[1]≠T[6],但也不能断定T[1]一定不等于S[6],因此需要保留⑥这一步。

有人就会问,如果T串后面也含有首字符“a”的字符怎么办呢?

我们来看下面一个例子,假设S="abcababca",T="abcabx"。对于开始的判断,前5个字符完全相等,第6个字符不等,如图5-7-4的①。此时,根据刚才的经验,T的首字符“a”与T的第二位字符“b”、第三位字符“c”均不等,所以不需要做判断,图5-7-4的朴素算法步骤②③都是多余。

因为T的首位“a”与T第四位的“a”相等,第二位的“b”与第五位的“b”相等。而在①时,第四位的“a”与第五位的“b”已经与主串S中的相应位置比较过了,是相等的,因此可以断定,T的首字符“a”、第二位的字符“b”与S的第四位字符和第五位字符也不需要比较了,肯定也是相等的——之前比较过了,还判断什么,所以④⑤这两个比较得出字符相等的步骤也可以省略。

也就是说,对于在子串中有与首字符相等的字符,也是可以省略一部分不必要的判断步骤。如图5-7-5所示,省略掉右图的T串前两位“a”与“b”同S串中的4、5位置字符匹配操作。

我们把T串各个位置的j值的变化定义为一个数组next,那么next的长度就是T串的长度。于是我们可以得到下面的函数定义:

 

next数组推导

具体如何推导出一个串的next数组值呢,我们来看一些例子。

1.T="abcdex"

      j          123456
模式串T    abcdex
next[j]        011111
1)当j=1时,next[1]=0;

2)当j=2时,j由1到j-1就只有字符“a”,属于其他情况next[2]=1;

3)当j=3时,j由1到j-1串是“ab”,显然“a”与“b”不相等,属其他情况,next[3]=1;

4)以后同理,所以最终此T串的next[j]为011111。

 

2.T="abcabx"

      j          123456
模式串T    abcabx
next[j]       011123
1)当j=1时,next[1]=0;

2)当j=2时,同上例说明,next[2]=1;

3)当j=3时,同上,next[3]=1;

4)当j=4时,同上,next[4]=1;

5)当j=5时,此时j由1到j-1的串是“abca”,前缀字符“a”与后缀字符“a”相等(前缀用下划线表示,后缀用斜体表示),因此可推算出k值为2(由‘p1...pk-1’=‘pj-k+1...pj-1’,得到p1=p4)因此next[5]=2;

6)当j=6时,j由1到j-1的串是“abcab”,由于前缀字符“ab”与后缀“ab”相等,所以next[6]=3。

我们可以根据经验得到如果前后缀一个字符相等,k值是2,两个字符k值是3,n个相等k值就是n+1。

 

4.T="aaaaaaaab"

      j          123456789
模式串T    aaaaaaaab
next[j]       012345678

1)当j=1时,next[1]=0;

2)当j=2时,同上next[2]=1;

3)当j=3时,j由1到j-1的串是“aa”,前缀字符“a”与后缀字符“a”相等,next[3]=2;

4)当j=4时,j由1到j-1的串是“aaa”,由于前缀字符“aa”与后缀“aa”相等,所以next[4]=3;

5)……

6)当j=9时,j由1到j-1的串是“aaaaaaaa”,由于前缀字符“aaaaaaa”与后缀“aaaaaaa”相等,所以next[9]=8。

 

KMP算法的优化

后来有人发现,KMP还是有缺陷的。比如,如果我们的主串S="aaaabcde",子串T="aaaaax",其next数组值分别为012345,在开始时,当i=5、j=5时,我们发现“b”与“a”不相等,如图5-7-6的①,因此j=next[5]=4,如图中的②,此时“b”与第4位置的“a”依然不等,j=next[4]=3,如图中的③,后依次是④⑤,直到j=next[1]=0时,根据算法,此时i++、j++,得到i=6、j=1,如图中的⑥。

我们发现,当中的②③④⑤步骤,其实是多余的判断。由于T串的第二、三、四、五位置的字符都与首位的“a”相等,那么可以用首位next[1]的值去取代与它相等的字符后续next[j]的值,这是个很好的办法。因此我们对求next函数进行了改良。

 

nextval数组值推导

改良后,我们之前的例子nextval值就与next值不完全相同了。比如:

1.T="ababaaaba"

      j             123456789
模式串T       ababaaaba
next[j]          011234223
nextval[j]     010104210
先算出next数组的值分别为011234223,然后再分别判断。

1)当j=1时,nextval[1]=0;

2)当j=2时,因第二位字符“b”的next值是1,而第一位就是“a”,它们不相等,所以nextval[2]=next[2]=1,维持原值。

3)当j=3时,因为第三位字符“a”的next值为1,所以与第一位的“a”比较得知它们相等,所以nextval[3]=nextval[1]=0;如图5-7-7所示。

4)当j=4时,第四位的字符“b”next值为2,所以与第二位的“b”相比较得到结果是相等,因此nextval[4]=nextval[2]=1;如图5-7-8所示。

5)当j=5时,next值为3,第五个字符“a”与第三个字符“a”相等,因此nextval[5]=nextval[3]=0;

6)当j=6时,next值为4,第六个字符“a”与第四个字符“b”不相等,因此nextval[6]=4;

7)当j=7时,next值为2,第七个字符“a”与第二个字符“b”不相等,因此nextval[7]=2;

8)当j=8时,next值为2,第八个字符“b”与第二个字符“b”相等,因此nextval[8]=nextval[2]=1;

9)当j=9时,next值为3,第九个字符“a”与第三个字符“a”相等,因此nextval[9]=nextval[3]=0。

 

2.T="aaaaaaaab"

      j           123456789
模式串T     aaaaaaaab
next[j]        012345678
nextval[j]    000000008
先算出next数组的值分别为012345678,然后再分别判断。

1)当j=1时,nextval[1]=0;

2)当j=2时,next值为1,第二个字符与第一个字符相等,所以nextval[2]=nextval[1]=0;

3)同样的道理,其后都为0……;

4)当j=9时,next值为8,第九个字符“b”与第八个字符“a”不相等,所以nextval[9]=8。

 

总结改进过的KMP算法,它是在计算出next值的同时,如果a位字符与它next值指向的b位字符相等,则该a位的nextval就指向b位的nextval值,如果不等,则该a位的nextval值就是它自己a位的next的值。

 

2017-12-18 23:02:44 qq_38140099 阅读数 214
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3320 人正在学习 去看看 佟刚

1.模板:

#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int next[1010];
char s[1000],p[1000];
void GetNextval()
{
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen - 1)
    {
        //p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++j;
            ++k;
            //较之前next数组求法,改动在下面4行
            if (p[j] != p[k])
                next[j] = k;   //之前只有这一行
            else
                //因为不能出现p[j] = p[ next[j ]],所以当出现时需要继续递归,k = next[k] = next[next[k]]
                next[j] = next[k];
        }
        else
        {
            k = next[k];
        }
    }
}
int KmpSearch()
{
    int i = 0;
    int j = 0;
    int sLen = strlen(s);
    int pLen = strlen(p);
    while (i < sLen && j < pLen)
    {
        //①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
        if (j == -1 || s[i] == p[j])
        {
            i++;
            j++;
        }
        else
        {
            //②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
            //next[j]即为j所对应的next值
            j = next[j];
        }
    }
    if (j == pLen)
        return i - j;
    else
        return -1;
}
int main()
{
    cout<<"输入文本串s:"<<endl;
    gets(s);
    cout<<"输入模式串p:"<<endl;
    gets(p);
    GetNextval();
    cout<<"模式串第一次出现的位置:"<<endl;
    cout<<KmpSearch();
    return 0;
}

2.单就next数组来说:

#include<iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
int next[1000010];
char p[1000010];
int pLen;
void GetNext()
{
     pLen = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < pLen )//这里原本是j<pLen-1
    {
        //p[k]表示前缀,p[j]表示后缀
        if (k == -1 || p[j] == p[k])
        {
            ++k;
            ++j;
            next[j] = k;
        }
        else
        {
            k = next[k];
        }
    }
}

int main()
{
    while(~scanf("%s",p)&&strcmp(p,".")!=0)
    {
        GetNext();
        for(int i=1;i<=strlen(p);i++)
            cout<<next[i];
    }

    return 0;
}
/*
ababab//输入
001234//输出
abcabcabc//输入
000123456//输出
ababcababababcabab//输入
001201234343456789//输出
*/
2017-08-07 09:36:40 wgf5845201314 阅读数 156
  • 图解Java数据结构和算法

    1.算法是程序的灵魂,优秀的程序在对海量数据处理时,依然保持高速计算,就需要高效的数据结构和算法支撑。2.网上数据结构和算法的课程不少,但存在两个问题: 1)授课方式单一,大多是照着代码念一遍,数据结构和算法本身就比较难理解,对基础好的学员来说,还好一点,对基础不好的学生来说,基本上就是听天书了 2)说是讲数据结构和算法,但大多是挂羊头卖狗肉,算法讲的很少。 本课程针对上述问题,有针对性的进行了升级  3)授课方式采用图解+算法游戏的方式,让课程生动有趣好理解 4)系统全面的讲解了数据结构和算法, 除常用数据结构和算法外,还包括程序员常用10大算法:二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法、马踏棋盘算法。可以解决面试遇到的最短路径、最小生成树、最小连通图、动态规划等问题及衍生出的面试题,让你秒杀其他面试小伙伴 3.如果你不想永远都是代码工人,就需要花时间来研究下数据结构和算法。教程内容: 本教程是使用Java来讲解数据结构和算法,考虑到数据结构和算法较难,授课采用图解加算法游戏的方式。内容包括: 稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、插入排序、快速排序、归并排序、希尔排序、基数排序(桶排序)、堆排序、排序速度分析、二分查找、插值查找、斐波那契查找、散列、哈希表、二叉树、二叉树与数组转换、二叉排序树(BST)、AVL树、线索二叉树、赫夫曼树、赫夫曼编码、多路查找树(B树B+树和B*树)、图、图的DFS算法和BFS、程序员常用10大算法、二分查找算法(非递归)、分治算法、动态规划算法、KMP算法、贪心算法、普里姆算法、克鲁斯卡尔算法、迪杰斯特拉算法、弗洛伊德算法马踏棋盘算法。 学习目标:通过学习,学员能掌握主流数据结构和算法的实现机制,开阔编程思路,提高优化程序的能力。

    3320 人正在学习 去看看 佟刚
#include "string.h"
#include "stdio.h"    
#include "stdlib.h"   
#include "io.h"  
#include "math.h"  
#include "time.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */

typedef int Status;		/* Status是函数的类型,其值是函数结果状态代码,如OK等 */
typedef int ElemType;	/* ElemType类型根据实际情况而定,这里假设为int */

typedef char String[MAXSIZE+1]; /*  0号单元存放串的长度 */

/* 生成一个其值等于chars的串T */
Status StrAssign(String T,char *chars)
{ 
	int i;
	if(strlen(chars)>MAXSIZE)
		return ERROR;
	else
	{
		T[0]=strlen(chars);
		for(i=1;i<=T[0];i++)
			T[i]=*(chars+i-1);
		return OK;
	}
}

Status ClearString(String S)
{ 
	S[0]=0;/*  令串长为零 */
	return OK;
}

/*  输出字符串T。 */
void StrPrint(String T)
{ 
	int i;
	for(i=1;i<=T[0];i++)
		printf("%c",T[i]);
	printf("\n");
}

/*  输出Next数组值。 */
void NextPrint(int next[],int length)
{ 
	int i;
	for(i=1;i<=length;i++)
		printf("%d",next[i]);
	printf("\n");
}

/* 返回串的元素个数 */
int StrLength(String S)
{ 
	return S[0];
}

/* 朴素的模式匹配法 */
int Index(String S, String T, int pos) 
{
	int i = pos;	/* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
	int j = 1;				/* j用于子串T中当前位置下标值 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
	{
		if (S[i] == T[j]) 	/* 两字母相等则继续 */
      	{
			++i;
         	++j; 
      	} 
      	else 				/* 指针后退重新开始匹配 */
      	{  
         	i = i-j+2;		/* i退回到上次匹配首位的下一位 */
         	j = 1; 			/* j退回到子串T的首位 */
      	}      
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

/* 通过计算返回子串T的next数组。 */
void get_next(String T, int *next) 
{
	int i,j;
  	i=1;
  	j=0;
  	next[1]=0;
  	while (i<T[0])  /* 此处T[0]表示串T的长度 */
 	{
    	if(j==0 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符,T[j]表示前缀的单个字符 */
		{
      		++i;  
			++j;  
			next[i] = j;
    	} 
		else 
			j= next[j];	/* 若字符不相同,则j值回溯 */
  	}
}

/* 返回子串T在主串S中第pos个字符之后的位置。若不存在,则函数返回值为0。 */
/*  T非空,1≤pos≤StrLength(S)。 */
int Index_KMP(String S, String T, int pos) 
{
	int i = pos;		/* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
	int j = 1;			/* j用于子串T中当前位置下标值 */
	int next[255];		/* 定义一next数组 */
	get_next(T, next);	/* 对串T作分析,得到next数组 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
	{
		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续,与朴素算法增加了j=0判断 */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* 指针后退重新开始匹配 */
      	 	j = next[j];/* j退回合适的位置,i值不变 */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

/* 求模式串T的next函数修正值并存入数组nextval */
void get_nextval(String T, int *nextval) 
{
  	int i,j;
  	i=1;
  	j=0;
  	nextval[1]=0;
  	while (i<T[0])  /* 此处T[0]表示串T的长度 */
 	{
    	if(j==0 || T[i]== T[j]) 	/* T[i]表示后缀的单个字符,T[j]表示前缀的单个字符 */
		{
      		++i;  
			++j;  
			if (T[i]!=T[j])      /* 若当前字符与前缀字符不同 */
				nextval[i] = j;	/* 则当前的j为nextval在i位置的值 */
      		else 
				nextval[i] = nextval[j];	/* 如果与前缀字符相同,则将前缀字符的 */
											/* nextval值赋值给nextval在i位置的值 */
    	} 
		else 
			j= nextval[j];			/* 若字符不相同,则j值回溯 */
  	}
}

int Index_KMP1(String S, String T, int pos) 
{
	int i = pos;		/* i用于主串S中当前位置下标值,若pos不为1,则从pos位置开始匹配 */
	int j = 1;			/* j用于子串T中当前位置下标值 */
	int next[255];		/* 定义一next数组 */
	get_nextval(T, next);	/* 对串T作分析,得到next数组 */
	while (i <= S[0] && j <= T[0]) /* 若i小于S的长度并且j小于T的长度时,循环继续 */
	{
		if (j==0 || S[i] == T[j]) 	/* 两字母相等则继续,与朴素算法增加了j=0判断 */
      	{
         	++i;
         	++j; 
      	} 
      	else 			/* 指针后退重新开始匹配 */
      	 	j = next[j];/* j退回合适的位置,i值不变 */
	}
	if (j > T[0]) 
		return i-T[0];
	else 
		return 0;
}

int main()
{
	int i,*p;
	String s1,s2;
	
	StrAssign(s1,"abcdex");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"abcabx");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"ababaaaba");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"aaaaaaaab");
	printf("子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("Next为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"ababaaaba");
	printf("   子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("   Next为: ");
	NextPrint(p,StrLength(s1));
	get_nextval(s1,p); 
	printf("NextVal为: ");
	NextPrint(p,StrLength(s1));
	printf("\n");

	StrAssign(s1,"aaaaaaaab");
	printf("   子串为: ");
	StrPrint(s1);
	i=StrLength(s1);
	p=(int*)malloc((i+1)*sizeof(int));
	get_next(s1,p); 
	printf("   Next为: ");
	NextPrint(p,StrLength(s1));
	get_nextval(s1,p); 
	printf("NextVal为: ");
	NextPrint(p,StrLength(s1));

	printf("\n");

	StrAssign(s1,"00000000000000000000000000000000000000000000000001");
	printf("主串为: ");
	StrPrint(s1);
	StrAssign(s2,"0000000001");
	printf("子串为: ");
	StrPrint(s2);
	printf("\n");
	printf("主串和子串在第%d个字符处首次匹配(朴素模式匹配算法)\n",Index(s1,s2,1));
	printf("主串和子串在第%d个字符处首次匹配(KMP算法) \n",Index_KMP(s1,s2,1));
	printf("主串和子串在第%d个字符处首次匹配(KMP改良算法) \n",Index_KMP1(s1,s2,1));

	return 0;
}

kmp

阅读数 148

大话数据结构 - 串

阅读数 212

没有更多推荐了,返回首页