每日一算法(链表逆序，子字符串等几个一起)

每天一算法(链表逆序，子字符串等几个一起)

（1）用一种算法来颠倒一个链接表的顺序。现在在不用递归式的情况下做一遍。

#include<iostream>
using namespace std;
struct node
{
	int x;
	node *next;
	node()
	{
		x = 0;
		next = NULL;
	};
};

void make(node *head)
{
	node *hea = head;
	for(int i = 0;i<10;i++)
	{
		node *x = new node;
		x->x= i;
		hea->next = x;
		hea = x;
	}
};

void reverse(node *&head)
{
	if(head->next == NULL)
		return;
	node *x = head;
	head = head->next;
	x->next = NULL;
	while(NULL !=head)
	{
		node *y = head;
		head = head->next;
		y->next = x;
		x = y;
	}
	head = x;
	int i ;
};

int main()
{
	node *head = new node;
	//head->x = 4;
	make(head);
	reverse(head);
	return 0;
}

而用递归方法实现的过程是：

node* reverse2(node *oldhead,node *newhead = NULL )
{
	node *next = oldhead->next;
	oldhead->next = newhead;
	newhead = oldhead;
	return (NULL == next) ? newhead:reverse2(next,newhead);
};

（2）用一种算法在一个循环的链接表里插入一个节点，但不得穿越链接表。

不明白什么叫穿越链接表，，如果是不循环的话，，只需要设置一个起始点就可以了，，但不知道往哪插入啊。。

（3）颠倒一个字符串。优化速度。优化空间

void reverseChar(char *str)
{
	char *start = str;
	int n = strlen(str);
	char *p = str+n-1;
	while(start < p)
	{
		char c = *start;
		*start = *p;
		*p=c;
		start++;
		p--;
  }
}

（4）找到一个子字符串。优化速度。优化空间。

利用的Sunday算法

int sunday(const char *src,const char *des)
{
	int i,j,pos=0;
	int len_s,len_d;
	int next[26]={0};                                //next数组，预处理初始化
	len_s=strlen(src);
	len_d=strlen(des);
	for(j=0;j<26;++j)                       //初始化next数组
		next[j]=len_d;
	for(j=0;j<len_d;++j)                        //设置next数组
		next[des[j]-'a']=len_d-j; 
	while( pos<(len_s-len_d+1) )               //遍历原串          
	{
		i=pos;
		for(j=0;j<len_d;++j,++i)              //比较
		{
			if(src[i]!=des[j])                //一旦不匹配，原串就按照next跳转
			{
				pos+=next[src[pos+len_d]-'a'];
				break;
			}
		}
		if(j==len_d)
			return pos;
	}
	return -1;                               //无子串则返回-1
}


int main()
{
	char src[]="abcdacdaahfacabcdabcdeaa";
	char des[]="abcde";
	cout<<sunday(src,des)<<endl;
	return 0;
}

每日一算法(链表逆序，子字符串等几个一起)

相关推荐