string.cpp

数据结构经典课件(附带各章的经典算法) 具体代码是使用C语言编写的

#include <stdlib.h>
#define MaxSize 20
typedef struct
{  char data[MaxSize];
   int  len;
}SqString;

bool StrAssign(SqString &S,char cstr[])
{
   int i=0;
   char *sp=cstr;
   while((*sp)!='\0' && i<=MaxSize)
   {S.data[i]=*sp;
    i++;sp++;
   }
   if(i>MaxSize)
	   return false;
   else
   {S.len=i;
    return true;
   }
}
void StrCopy(SqString &S,SqString T)
{
  int i;
  for(i=0;i<T.len;i++)
	  S.data[i]=T.data[i];
  S.len=T.len;
}
SqString ConCat(SqString S,SqString T)
{
	SqString str;
	int i;
	str.len=S.len +T.len ;
	for(i=0;i<S.len;i++)
		str.data[i]=S.data[i];
	for(i=0;i<T.len;i++)
		str.data[S.len+i]=T.data[i];
	return str;
}

int Index(SqString S,SqString T)
{    
	int i=0,j=0;
	while(i<S.len  && j<T.len )
	   if(S.data[i]==T.data[j])
		   {i++; j++;}
	   else
		   {i=i-j+1;j=0;}
	if(j>=T.len)
		return i-T.len;
	else
		return -1;
}

typedef struct snode
{ char data;
  struct snode *next;
}LiString;

void StrAssign_L(LiString *&S,char cstr[])
{   LiString *r,*p;
    char *sp=cstr;
    S=(LiString *)malloc(sizeof(LiString));
    r=S;
    while((*sp)!='\0')
      {  p=(LiString *)malloc(sizeof(LiString));
	     p->data=*sp;
	     r->next=p;
	     r=p;
	     sp++;
      }
	r->next=NULL;
}
bool StrEqual(LiString *S,LiString *T)
{
  LiString *p,*q;
  p=S->next;q=T->next;
  while(p!=NULL && q!=NULL)
	  if(p->data==q->data)
	  {p=p->next ;
	   q=q->next ;
	  }
	  else
		return false;
  if(p==NULL && q==NULL)
	  return true;
  else
	  return false;
}

LiString *Index_L(LiString *S,LiString *T)
{ 
  LiString *first,*sptr,*tptr;
  
  first=S->next;
  sptr=first;
  tptr=T->next;
  while(sptr!=NULL && tptr!=NULL)
     if(sptr->data ==tptr->data )
	{sptr=sptr->next;
	 tptr=tptr->next;
	}
     else
	{first=first->next;
	 sptr=first;
	 tptr=T->next;
	}
   if(tptr==NULL)
      return(first);
   else
     return(NULL);
}
void GetNext(SqString t,int next[])
{
  int j,k;  
  j=0;k=-1;next[0]=-1;
  while(j<t.len-1)
  {  
  if(k==-1 || t.data[j]==t.data[k])
  {j++;k++;
   next[j]=k;
  }
  else
   k=next[k];
  }
}
int KMPIndex(SqString s,SqString t)
{
    int next[MaxSize],i=0,j=0;
	GetNext(t,next);
	while(i<s.len && j<t.len )
	{
		if (j==-1 || s.data[i]==t.data[j])
		{  i++;j++;}
		else
			j=next[j];
	}
	if(j>=t.len)
	  return (i-t.len );
	else
	  return -1;
}
void main()
{  
	SqString S,T;
	
    char  s1[]="ababcabcacbab",t1[]="xyabcabcde";
	bool  b=StrAssign(S,s1);
	b=StrAssign(T,t1);
	int k=KMPIndex(S,T);

	 k=Index(S,T);
	StrCopy(T,S);
	S=ConCat(S,T);
	
	LiString *SL,*TL,*p;
	StrAssign_L(SL,s1);
    StrAssign_L(TL,t1);
	p=Index_L(SL,TL);
	b=StrEqual(SL,TL);
}