第二章---串

#include <stdio.h> 
#include <typeinfo.h>
#define MAXN 100

typedef enum{
	fail,
	success
} status;



//1.求出串s的长度,strlen(s)的值是一个非负整数。若s是一个空串，则strlen(s)=0 
int strlen(char s[])
{
	int i;
	i=0;
	
	//while(s[i++]!='\0');//注意区别 i的长度包括了 '/0' 
	
	for(i=0;s[i]!='\0';i++); //i的长度不包括'/0' 

	return i;
}

//2.strcat(s1,s2) 把串s2加到s1的末尾
status strcat(char s1[],char s2[])
{
	int i,j,k;
	
	if((i=strlen(s1))+(j=strlen(s2))>=MAXN)
	      return fail;
	      
	for(k=0;k<=j;k++)
	      s1[i+k]=s2[k];
	      
	return success;    
}
 

//3.strsub(s1,i,j,s2) 把串s1中位置i开始取长度为j的子串构成串2l
status strsub(char s1[],int i,int j,char s2[])
{
	int m,k;
	
	if(i<0||i>=(m=strlen(s1)))
		 return(fail);
    if(j<0||i+j>m)
         return fail;

	for(k=0;k<j;k++)
		 s2[k]=s1[k+i];
		 
	s2[k]='\0';
	return success;  
}

//4. strins(s1,i,s2) 把串s2插在串s1的位置i上
status strins(char s1[],int i,char s2[])
{
	int m,n,k;
	if(i<0|| i>(m=strlen(s1)) || m+(n=strlen(s2))>MAXN)
	     return fail;
	for(k=m;k>=i;k--)
	  s1[k+n]=s1[k];          //后移
	
	for(k=0;k<n;k++)
		s1[i+k]=s2[k];
	   
	return success;       
}

//5. strdel(s,i,j) 把从s中位置i开始，删除j个字符。如果字符个数不足j，则全删除
status strdel(char s1[],int i,int j)
{
	int n,m;
	if(i<0||i>(n=strlen(s1)))
	   return fail;
	if(i+j>=n)
	   s1[i]='\0';
	else   
	    for(m=0;m<=n-i-j;m++)
	        s1[i+m]=s1[i+j+m];
	return success;        
}

//6. strequ(s1,s2)   判断s1和s2是否相同
bool strequ(char s1[],char s2[])
{
	int i=0;
	while(s1[i]==s2[i] && s1[i]!='\0'&&s2[i]!='\0')
	      i++;
	if(s1[i]=='\0' && s2[i]=='\0')
	    return true;
	else
	    return false;
}

//7. strstr(s1,s2)   s2首字符在s1中的位置 


//8. 简单匹配算法
int simple_match(char t[],char p[],int n,int m)
{
	int i,j,k;
	for(i=0;i<=n-m;i++){
		for(j=0,k=i;j<m&&t[k]==p[j];j++,k++)
		    ;
		if(j==m) return i;	
	}
	return -1;
}

//kmp 失败数组 
void faillink(char p[],int flink[],int m)
{
	int j,k;
	flink[0]=-1;
	j=1;
	while(j<m){
		k=flink[j-1];
		while(k!=-1&&p[k]!=p[j-1])
		    k=flink[k];
		
		flink[j]=k+1;
		j++;
	}
}

//kmp 算法
int flink[100];
int kmp_match(char t[],char p[],int n,int m)
{
	int i,j;
	i=j=0;
	while(i<n){
		while(j!=-1&&p[j]!=t[j])
		     j=flink[j];
		if(j==m-1)   return (i-m+1);
		
		i++;
		j++;
	}
	return -1;
}


//bm 算法  d数组
void df(char p[],int d[],int m)
{
	int i;
	for(i=0;i<26;i++)
	   d[i]=m;
	for(i=0;i<m-1;i++)
	   d[p[i]-'a']=m-i-1;
}

int d[26];
//bm
int bm_match(char t[],char p[],int n,int m) 
{
	int i,j,k;
	i=m-1;
	do{
		j=m-1;
		k=i;
		while(j>=0&&p[j]==t[k]){
			j--;
			k--;
		}
		if(j<0) return(i-m+1);
		i=i+d[t[i]-'a'];
	}while(i<n);
	
	return -1;
}


//2.1 假设s和t分别具有m和n个字符，寻找s和t中最大公共子串 

//2.1.1 暴力破解
int constring_1(char s[],char t[],int m,int n)
{
	int i,j,k,max;
	int index,length;
	i=index=length=0;
	
	while(i<n){
		j=0;
		while(j<m){
			if(s[i]==t[j]){
				max=1;
				for(k=1;s[i+k]==t[j+k];k++)
				     max++;
				     
				if(max>length){
					index=i;
					length=max;
				}
			}
			
			j++;
			
		} //end j<m
		
		i++;
	}//end i<n
	
	printf("最大公共子串:");
	for(i=0;i<length;i++)
	      printf("%c",s[index+i]);
}

//2 动态规划  待续 
void  constring(char s[],char t[],int m,int n)
{
  
}

//2.2假设所使用的串采用链接存储结构，每个节点可存放m（m=4） 个字符。编写strins(s1,i,s2)
//的c函数。为了减少移动字符的次数，节点中允许使用无效的特殊字符，但一个结点至少含有一个有效字符。 

/*
   算法步骤：
   1.通过i/4算出所在节点
   2.通过k=i%4 算出i在该节点中的位置
   3.开设一新节点，把该节点k后的字符赋值给新节点
   4.把该节点中赋值过的字符及新节点中未赋值的都置为无效字符‘*’ 
   5.使新节点指向该节点的后继，该节点指向s2首节点，并把s2的末节点中的‘\0’置成‘*’，末节点指向新节点 
    
	若 S1="ABCDEFGHI"  S2=“JML”i=6 则调用后为 ABCD EF** JML*GH**I
*/
#include <stdlib.h>

typedef struct node{
	char data[4];
	struct node *link;
} Node;

void strins(Node *s1,int i,Node *s2) 
{
	int j,k,l,m;
	Node *p,*q,*r;
	
	j=i/4;						//所在节点 
	k=i%4;						//所在节点位置
	p=s1;
	
	r=s2;
	while(r->link!=NULL)      //r指向最后一个节点 
	     r=r->link;      
	for(m=0;r->data[m]!='\0';m++);
	     r->data[m]='*';
	
	while(m<4)
	     r->data[++m]='*'; 	
	
	
	for(l=1;l!=j;l++) 
	     p=p->link;              //k=0的情况,p指向s2将插入的节点 
	
	if(k==0){
		q=p->link;
		p->link=s2;
		r->link=q;
		return; 
	}
	
	if(k!=0){					//k!=0 原节点分为两个节点，首尾分别填充* 
	    p=p->link;
		q=(Node*)malloc(sizeof(Node));
		
	   for(m=k;m<4&&p->data[m]!='\0';m++)
		{
			q->data[m-k]=p->data[m];
			p->data[m]='*'; 		//'*' is invalid char 
		}
		
	   if(p->data[m]=='\0'){
	   		q->data[m-k]='\0';      //p指向的节点不足4个 
	   		p->data[m]='*';
	   }         
	   else{
	    	for(l=k;l<4;l++)
		       q->data[l]='*';
		}
	
	}	
     
	     
	q->link=p->link;
	p->link=s2;
	r->link=q; 
	
}

//2.3 按照2.2题的要求，编一个实现strdel(Node *s,int i,int j)的c函数   从i开始删除j位字符 
/*
	1. 计算出S中节点的个数L
	2.通过 i/4  计算出其在S中的节点位置
	3.通过i%4计算出其在该节点中的位置
	4.若（i+j-1）/4>L  则置该位置为‘/0’
	 否则，将i位所在结点中的所在位及其后均置为‘*’
	 并将（i+j-1)/4所在结点中的所在位及其前均置为‘*';
	5.最后使i位所在结点指向（i+j-1）/4所在结点 
*/
void strdel(Node *s,int i,int j)
{
	int k,l,m,h;
	Node *q,*p;
	
	k=i/4;
	h=i%4;
	
	l=0;		//节点个数 
	q=p=s;
	
	if(i<0||j<0){
		printf("输入不符合格式");
		exit(1);
	}
	
	while(p->link!=NULL){
		p=p->link;
		l++;
	}

	p=s;					//p重置 
	for(m=0;m!=k;m++) 
			p=p->link;	    //p定位到i所在结点
			
	if((i+j-1)/4>l){	    //i后全删除 
		p->data[h]='\0';
		p->link=NULL;
	}else{
		for(m=0;m!=(i+j-1)/4;m++)
		        q=q->link;               //q定位到（i+j-1）所在结点 
		for(m=h;m<4;m++)
				p->data[m]='*';		   //i后置为‘*’ 
		for(m=(i+j-1)%4;m>=0;m--)
			    q->data[m]='*';         //'i+j-1'前置为‘*’
				 
	  if((i+j-1)/4==k) 
	          return;        //在同一个节点内 
	          
	   p->link=q;
	}
	     

	
}

int main()
{
	Node s1={{'A','B','C','D'},NULL};
	Node r={{'E','F','G'},NULL};

	s1.link=&r;
	Node s2={{'J','M','L'},NULL};
	
	Node*a=&s1;
	Node*b=&s2;
	
	
//	strins(a,5,b);
	
	strdel(a,3,6);

	int i=0;
	while(a){
		for(int i=0;i<4;i++)
		      printf("%c",a->data[i]);

		a=a->link;
	}

}