string.cpp

串的基本操作

//函数结果状态代码 
#define TRUE 1 
#define FALSE 0
#define OK 1 
#define ERROR 0 
#define INFEASIBLE -1 
#define OVERFLOW -2 
#define NOTEXIT -3
//Status 是函数的类型，其值是函数结果状态代码 
typedef int Status; 
//串的堆分配表示
#include <malloc.h>
#include <stdlib.h>
#include <stdio.h>




#include <string.h>
typedef struct 
{  
    char *ch; //若为非空串，则按串长度分配存储区，否则ch为NULL
    int length; //串长度
} HString;

 

Status StrAssign(HString &T,char *chars);//生成一个其值等于串常量chars的串T

Status StrLenth(HString S);//求串长

Status StrCompare(HString S,HString T);//串比较

Status InitString(HString &S);//初始化

Status ClearString(HString &S);//释放动态空间

Status Concat(HString &T,HString S1,HString S2);//串联接

HString SubString(HString S,int pos,int len);//求子串

Status IndexStr(HString S4,HString S5); //子串定位

 Status DispStr(HString S); //输出字符串

//以上为定义结构体及相关函数声明
Status StrAssign(HString &T,char *chars)
{
  if(T.ch) free(T.ch) ; //释放原有的空间
  int i; char *c;
  for ( i=0,c=chars; *c; ++i,++c); //求chars的长度
  if (!i) 
  {
   T.ch=NULL;
   T.length=0;
  }
  else 
  {
   if(!(T.ch=(char *)malloc(i*sizeof(char))))
            exit (OVERFLOW);
      for (int j=0;j<i;j++) 
    T.ch[j]=chars[j];
      T.length=i;
  }
  return OK;
} //生成一个其值等于串常量chars的串T

 

Status StrLenth( HString S )
{
  return S.length; 
} //返回S的元素个数，即串长度.

 

Status StrCompare( HString S,HString T )
{//若S>T,则返回值>0;
//若S=T,则返回值=0;
//若S<T,则返回值<0;
  for (int i=0;i< S.length && i< T.length;++i)
      if ( S.ch[i]!=T.ch[i] )
    return S.ch[i]-T.ch[i];
return S.length-T.length;
} //StringCompare

 

Status InitString( HString &S )
{ 
	S.ch=NULL; S.length=0; 
	return OK; 
} //将S.ch置成空指针，S的长度设为0

 

Status ClearString( HString &S )
{
  if(S.ch) 
  {
   free(S.ch);
   S.ch=NULL;
  }
  S.length=0;
  return OK;
} //将S清空为空串，并释放S所占的空间

Status Concat( HString &T, HString S1, HString S2 ) 
{
  if (T.ch) free(T.ch); //释放原有的空间
  if (!(T.ch=(char *)malloc((S1.length+S2.length)*sizeof(char))))
      exit(OVERFLOW);
   int i;
  for (i=0;i<S1.length;++i) 
   T.ch[i]=S1.ch[i];
  T.length=S1.length+S2.length;
  for (i=0;i<S2.length;++i) 
   T.ch[i+S1.length]=S2.ch[i];
  return OK;
} //用T返回值由S1和S2联接而成的新串

HString SubString(HString S,int pos,int len) 
{//1<=pos<=StrLenth(S)且0<=len<=StrLenth(S)-pos+1
  if (pos<1||pos>S.length||len<0||len>S.length-pos+1)
            exit(1);
 HString Sub;
  if (!len)
  {
   Sub.ch=NULL;
   Sub.length=0;
  } //空子串
  else 
  {
    Sub.ch=(char *)malloc(len*sizeof(char));
    for (int i=0;i<len;++i) 
  Sub.ch[i]=S.ch[pos+i-1];
    Sub.length=len;
   }
  return Sub;
} //返回串S的第pos个字符起长度为len的子串

 
Status DispStr(HString S) 
{  
	if (S.length==0) return ERROR;
	int i; 
	for (i=0;i< S.length;i++) 
		printf("%c",S.ch[i]);
	return OK;


} //输出字符串


Status IndexStr(HString S4,HString S5)
{
	int i,j,k;
	for (i=0;i< S5.length;i++)
	{
		for(j=i,k=0;S5.ch[j]==S4.ch[k];j++,k++)
			if( k ==S4.length-1 )
				return i;
	}
	return NOTEXIT ; 


} //字串定位（模式匹配）

 

//主程序

void main()
{
  HString S1,S2,S3,S4,S5;
  int j,k;
  InitString(S1);
  InitString(S2);
  InitString(S3);
  InitString(S4);
  InitString(S5); 
  StrAssign(S1,"Data Structure!");
  StrAssign(S2,"Computer Design!"); 
  printf("String S1 is :"); 
  DispStr(S1); 
  printf("\n"); 
  printf("String S2 is :");
  DispStr(S2);
  printf("\n"); 
  j=StrCompare(S1,S2);
  if(j>0)
   printf("串S1大于串S2\n");
  else if (j<0)
   printf("串S1小于串S2\n");
  else
   printf("串S1等于串S2\n");
  S3=SubString(S1,1,4);
  printf("String S3 is :");
  DispStr(S3); 
  printf("\n");
  S4=SubString(S2,4,3);
  printf("String S4 is :");
  DispStr(S4);
  printf("\n");
  Concat( S5,S3,S4 );
  printf("String S5 is :");
  DispStr(S5);
  printf("\n");
  k=IndexStr(S4,S5);
  printf("S4在S5中首次出现位置 is : %d \n",k);
  ClearString(S1);
  ClearString(S2);
  ClearString(S3); 
  ClearString(S4); 
  ClearString(S5); 
 }