str.cpp

这是本人精心搜集的关于常用图论算法的一套源码

#include<string.h>
#include"str.h"

ostream &operator<<(ostream& os,String &s)
   {  return os<<'"'<<s.c_str( )<<'"'<<"  ";  }
   
istream &operator>>(istream&input,String &s) 
// Post:read a String  from an istream parameter,store String object s.
 { char temp[80];
   input>>temp;   s = temp; 
   return input;
 } 
 
void write(ostream& out, String &s)
  {  out << s.c_str( ) << endl;  }
void String::setString(const char *copy)
{ length=strlen(copy);
  entries=new char[length+1];
  strcpy(entries, copy);
}
String::String (const char *in_string)
/* Pre: The pointer in_string references a C-string.
  Post: The String is initialized by the C-string in_string . */
{ setString(in_string);  }

String::String (const String& copy)
{ setString(copy.entries);  }

const char*String::c_str( ) const
/* Post: A pointer to a legal C-string object matching theString is returned. */
{  return (const char*) entries;  }

String  String::operator=(const String &copy) //overloaded assignment operator
{ if(&copy!=this) // avoid self assignment
    { if(length>0) delete[] entries;   // prevent memory leak
      setString(copy.entries); 
    } 
  else cout<<"Attempted assignment of a String to itself!\n";
  return  *this;       
}
String& String::operator=(const char*copy)
{ setString(copy);
  return *this;
}  
int String::Find(const String &pat)const
{ char *p = pat.entries, *s = entries;
  int i=0;
  if(*p && *s)
    while(i<= length-pat.length)
       if(*p++==*s++){ if(!*p) return i; }
       else { i++; s=entries+i; p=pat.entries;  }
  return -1;
}
 
bool operator==(const String &first, const String &second)
// Post: Return true if the String first agrees with String second. Else:Return false. 
{  return strcmp(first.c_str(), second.c_str())==0;  }
bool operator>(const String &first, const String &second)
// Post: Return true if the String first greater than String second. Else:Return false. 
{  return strcmp(first.c_str(), second.c_str())>0;  }
bool operator<(const String &first, const String &second)
// Post: Return true if the String first less than String second. Else:Return false. 
{  return strcmp(first.c_str(), second.c_str())<0;  }
bool operator>=(const String &first, const String &second)
// Post: Return true if the String first not less than String second. Else:Return false. 
{  return strcmp(first.c_str(), second.c_str())>=0;  }
bool operator<=(const String &first, const String &second)
// Post: Return true if the String first not greater than String second. Else:Return false. 
{  return strcmp(first.c_str(), second.c_str())<=0;  }
bool operator!=(const String &first, const String &second)
// Post: Return true if the String first not agrees with String second. Else:Return false. 
{  return strcmp(first.c_str(), second.c_str())!=0;  }
int strlen(String &s)
 {  return strlen( s.c_str() );   }
void strcat(String &add_to, const String &add_on)
// Post: The function concatenates String add_on onto the end of String add_to.
{ const char *cfirst = add_to.c_str( );
  const char *csecond = add_on.c_str( );
  char *copy = new char[strlen(cfirst)+ strlen(csecond)+1];
  strcpy(copy, cfirst);
  strcat(copy, csecond);
  add_to = copy;
  delete []copy;
}
void strcpy(String &copy, const String &original)
{ if(&copy!=&original) // avoid self copies
    { if(copy.length>0) delete[] copy.entries;   // prevent memory leak
      int n = original.length;
      copy.entries=new char[n+1];
      strcpy(copy.entries,original.entries);  
      copy.entries[n]='\0';  copy.length=n;
    } 
  else cout<<"Attempted copies a String to itself!\n";
}
void strncpy(String &copy, const String &original, int n)
{ if(&copy!=&original) // avoid self copies
    { if(copy.length>0) delete[] copy.entries;   // prevent memory leak
      int k = (original.length>n? n: original.length);
      copy.entries=new char[k+1];
      strncpy(copy.entries,original.entries,k);  
      copy.entries[k] = '\0';
      copy.length=k;
    } 
  else cout<<"Attempted copies a String to itself!\n";
}


void KMP_Fail(const String &pat,int *f)   // 计算模式串的失效函数
{ int lenP=strlen(pat.entries);
  f[0] = -1;
  for(int j=1; j<lenP; j++)  // 计算f[j]
   { int i = f[j-1];
     while (*(pat.entries+j)!=*(pat.entries+i+1) && i>=0 ) i=f[i];  // 递推计算f[j]
     if(*(pat.entries+j)==*(pat.entries+i+1)) f[j] = i+1;
     else f[j] = -1;
   }
} 

int KMP_Find(const String &tag,const String &pat)  
{ int posP=0, posT=0; 
  int f[80];                 // 在KMP算法存放模式串pat的失效函数的数组
  int lenP=strlen(pat.entries),  lenT=strlen(tag.entries);
  KMP_Fail(pat,f);     // 计算模式串的失效函数
  while(posP<lenP && posT<lenT)
    if(pat.entries[posP]==tag.entries[posT])
      { posP++;  posT++;  }
    else if(posP==0) posT++;
         else posP=f[posP-1]+1;
  if(posP<lenP ) return -1;  else return posT-lenP;
}         
int strstr(const String &text, const String &target)
{  return KMP_Find(text,target);  }