当前位置： 云海天教程网 > 技术新闻 > 编程语言 > 正文

双向队列,KMP算法,线索二叉树

  • 作者： 佚名     来源： 网络转载
  • 时间：2019-12-06
  1. 双向队列的插入删除

    • 插入

      • 先对新节点赋值 
        	New->pre = My;
	New->next = My->next;
      • 再对前后节点修改 
        	My->next->pre = New;
	My->next = New;

      New->next = My->next;和My->next->pre = New;可以换位置。

      这就变成先该前置节点，再改next。

    • 删除

      	if ( NULL != My->next )
	{
	    temp = My->next;
	    My->next = My->next->next;
		temp->next = NULL;
		delete temp;//free(temp)
	}
  2. 字符串匹配算法

    • KMP

      主要是对子串进行优化搜索，提高子串substr在匹配时的工作效率，辅助作用。

      算法里面的next指的是:在i处发现不匹配，则该到next[i]处开始对照。

      next[i]对应的值表示,在substr+i-next[i]处，有next[i]个与substr相同的前缀。

      i的值由前面一个的字符计算后决定。

      对于如果所示的一个子串。对于任何一个next的值大于0，说明存在周期。或前置相同。

      i str introduction value
      0 a 最前面,没有相同，错误 -1
      1 b i<2 0
      2 a a!=b 0
      3 b a==a 1
      4 a ab==ab 2
      5 a aba==aba 3
      6 a abab!=abaa,aba!=baa,ab!=aa,a==a 1
      7 b ab!=aa,a==a 1
      8 a ab==ab 2
      9 x aba==aba,因为i==len,所以没有这个值。value表示前面有n个相同 3
    • KMP优化版

      在前面的基础上去掉冗余。

      转换逻辑

      对于有重复的，值可以理解f(x)=f(x-r),r为周期。

      值可以分为两类,-1或非-1.

      -1表示如果在当前发现不同,那么前面的可以不用看了,str和substr的下标都可以同时++,因为在子串中不存在周期长度为currentindex的子串。

      非-1表示,前面必有n个相同，但是在我(currentIndex)这儿开始有不同的

      比如下面的5的值为3，说明有三个相同，但是在我这儿不相同，不相同的第一个在下标为3的地方。相同为aba==aba但有abab!=abaa。

      对于0是因为，j==-1,next是前者关系而定，j==-1表示都重新开始。

      j==0和-1相比，是因为没有前者，而且当前不形成循环也不相等。出于起始状态。

      对于i==1,没有前者，是由共同前进一步的来，判断当前a!=b则就有了,next[1]==0,如果str[1]==a,那么b==-1.因为对于某段出于周期函数，出现相同，则可以前移n倍周期，形成图形重叠。

      i next[i] j introduction next[++j] next[++i]
      0 -1 -1 j==-1,a!=b j==0,value==-1 i==1,value==0
      1 0 0 a!=b,回溯 j==0,value==-1
      1 0 -1 j==-1,a==a j==0,value==-1 i==2,value==-1
      2 -1 0 a==a,b==b j==1,value==0 i==3,value=0
      3 0 1 b==b,a==a j==2,value==-1 i==4,value==-1
      4 -1 2 a==a,b!=a j==3,value==0 i==5,value=j=3
      5 3 3 b!=a,回溯 j==0,value==-1
      5 3 0 a==a,b!=a j==1,value==0 i==6,value=j=1
      6 1 1 b!=a,回溯 j==0,value==-1
      6 1 0 a==a,b!=a j==1,value==0 i==7,value==0
      7 0 1 b==b,a==a j==2,value==-1 i==8,value==-1
    • 源代码 
      	#include<stdio.h>
	#include<string.h>

	void get_KMP_Next(const char * src,int len,int *next)
	{
		int i,j;
		next[0] = j = -1;
		i = 0;
		while( i < len )
		{
			if( j == -1 || src[i] == src[j] )
			{
				i++;
				j++;
				next[i] = j ;
				//表示i的位置如果不匹配就需要将起始匹配地址移动到j的位置。
			}
			else
			{
				j = next[j];
			}
		}
	}

	void get_KMP_NextValue(const char * src,int len,int *next)
	{
		int i,j;
		next[0] = j = -1;
		i = 0;
		while( i < len )
		{
			if( j == -1 || src[i] == src[j] )
			{
				i++;
				j++;
				if ( src[i] != src[j] )
				{
					//对于不相等，说明了重复已经停止。
					next[i] = j;
				}
				else
				{
					next[i] = next[j];
					//连续相等说明了某个子串重复率高。
					// abcabcabcabc或者aaaaaa,这种重复率才会很高.
					// aaaa abab abcabc abcdabcd abcdeabcde abcdefabcdef abcdefgabcdefg都是。
					//对于这种重复率高的
					//对于aaaaa型，只需要第一个就可以了。
					//对于ababa周期型字符串,用j的next就可以了。
					//可以总结成数学的周期性函数,比如tan(x),可重复率高。
				}
			}
			else
			{
				j = next[j];
			}
		}
	}

	void (*getNext)(const char*,int,int*) = get_KMP_NextValue;
	//改进版和非改进版之间切换只需复制对应的方法名就可以了。
	int searchSub(const char * src,int srclen ,const char* sub,int sublen)
	{
		int next[255]={0},i,j;
		getNext(sub,sublen,next);
		for(i = 0 ; i < sublen ; i++ )
		{
			printf(i<sublen-1?"%d ":"%d
",next[i]);
		}
		j = i = 0 ;
		while( i < srclen && j < sublen )
		{
			if( j == -1 || src[i] == sub[j] )
			{
				i++;
				j++;
			}
			else
			{
				j = next[j];
			}
		}
		if ( j == sublen )
		{
			return i - sublen;
		}
		else
		{
			return -1;
		}
	}

	void testSub()
	{
		char src[] = "abcdabcdexabcde";
		char sub[] = "abcdex";
		int srclen = strlen(src),sublen=strlen(sub);
		int ret = searchSub(src,srclen,sub,sublen);
		if ( ret != -1 )
		{
			printf("%s
",src + ret);
		}
		else
		{
			printf("error
");
		}
	}

	void printNext()
	{
		char sub[] = "ababaaaba";
		int next[255]={0},sublen=strlen(sub),i;
		getNext(sub,sublen,next);
		printf("i   ");
		for( i = 0 ; i < sublen ; i++ )
		{
			printf("%3d",i);
		}
		printf("
str ");
		for( i = 0 ; i < sublen ; i++ )
		{
			printf("  %c",sub[i]);
		}
		printf("
next");
		for( i = 0 ; i < sublen ; i++ )
		{
			printf("%3d",next[i]);
		}
		printf("
");
	}

	int main()
	{
		printNext();
		return 0;
	}

  3. 线索二叉树

    成员,头结点，记录相关信息，成员[lchild,islchild,data,isrchild,rchild]

    • lchild 存放前驱或者左子树
    • islchild 区分是前驱还是子节点。
    • 其他的同理。 变成了双向链表，节省空间。