《数据结构》读书笔记 第四章 串的基本操作


String.h:串的基本操作

#include <iostream>

enum {MSL=20,WRONG=-1,OK=0};
typedef char SString[MSL+1];
typedef int Status;

Status StrAssign(SString S,SString T)
{
 //一定注意长度不可以用T[0]表示!!
 int len=strlen(T);
 if(len<=len)
 {
  int i;
  for(i=1;i<=len;i++)
   S[i]=T[i-1];
  S[0]=len;
  return OK;
 }
 else
 {
  return WRONG;
 }
}

void StrCopy(SString S,SString T)
{
 int i;
 for(i=1;i<=T[0];i++)
  S[i]=T[i];
 //一定不要忘记标记长度!
 S[0]=T[0];
}

bool StrEmpty(SString S)
{
 if(S[0]==0)
  return true;
 else
  return false;
}

int StrCompare(SString S,SString T)
{
 int i=1;
 while(i<=S[0]&&i<=T[0])
 {
  if(S[i]==T[i])
   i++;
  else
   return S[i]-T[i];
 }
 return S[0]-T[0];

}

void StrClear(SString S)
{
 S[0]=0;
}

int StrLen(SString S)
{
 return S[0];
}

Status Concat(SString T,SString S1,SString S2)
{
 if(S1[0]+S2[0]>MSL)
 {
  int i;
  for(i=1;i<=S1[0]&&i<=MSL;i++)
   T[i]=S1[i];
  for(i=1;i<=S2[0]&&i<=MSL;i++)
   T[i+S1[0]]=S2[i];
  T[0]=MSL;
  return WRONG;
 }
 else
 {
  int i;
  for(i=1;i<=S1[0];i++)
   T[i]=S1[i];
  for(i=1;i<=S2[0];i++)
   T[i+S1[0]]=S2[i];
  T[0]=S1[0]+S2[0];
  return WRONG;
 }
}

Status SubStr(SString Sub,SString S,int pos,int len)
{
 int i;
 if(pos<1||pos>S[0]||len<0||len+pos>S[0]+1)
  return WRONG;
 for(i=0;i<len;i++)
  Sub[i+1]=S[pos+i];
 Sub[0]=len;
 return OK;
}

int Index(SString S,SString T,int pos)
{
 int i=1,j=1;
 if(pos<1||pos>S[0])
  return 0;
 while(i<=S[0]&&j<=T[0])
 {
  if(S[i]==T[j])
  {
   i++;
   j++;
  }
  else
  {
   i=i-j+2;
   j=1;
  }
 }
 if(j>T[0])
  return i-T[0];
 else
  return 0;
}

Status StrInsert(SString S,SString T,int pos)
{
 int i;
 if(pos<1||pos>S[0]+1)
  return WRONG;
 if(S[0]+T[0]<=MSL)
 {
  //这段“腾地方”的语句还是从后往前搬,不然玩不好就错了……
  for(i=S[0];i>=pos;i–)
   S[i+T[0]]=S[i];
  for(i=0;i<T[0];i++)
   S[pos+i]=T[i+1];
  S[0]+=T[0];
  return OK;
 }
 else
 {
  int len=MSL-S[0];
  //这段腾地方的方式和非截取有很大不同,要看仔细了!
  for(i=MSL;i>=pos+len;i–)
   S[i]=S[i-len];
  for(i=0;i<len;i++)
   S[i+pos]=T[i+1];

  S[0]=MSL;
  return WRONG;
 }
}

Status StrDelete(SString S,int pos,int len)
{
 int i;
 if(pos<1||len+pos>S[0]+1||len<0)
  return WRONG;
 //这段自己写的有问题,仔细检查一下!
 for(i=pos+len;i<=S[0];i++)
  S[i-len]=S[i];
 
 //for(i=pos+len;i<=S[0];i++)
  //S[i-len]=S[i];
 
 S[0]-=len;
 return OK;
}

Status Replace(SString S,SString T,SString V)
{
 int i=1;
 Status k;
 if(StrEmpty(S))
  return WRONG;
 while(i)
 {
  i=Index(S,T,i);
  if(i)
  {
   StrDelete(S,i,T[0]);
   k=StrInsert(S,V,i);
   //if(k==WRONG)
    //return WRONG;
   i+=V[0];
  }
 }
 return OK;
}

void StrPrint(SString S)
{
 int i;
 std::cout<<"打印字符串:";
 for(i=1;i<=S[0];i++)
 {
  std::cout<<S[i];
 }
 std::cout<<std::endl;
}

main.cpp:主函数

#include "String.h"

using namespace std;
int main()
{
 int tmp;
 SString S1,S2,S;
 StrAssign(S1,"me");
 cout<<"生成S1串,";
 StrPrint(S1);
 StrAssign(S2,"x");
 cout<<"生成S2串,";
 StrPrint(S2);
 StrAssign(S,"amxmeeeme");
 cout<<"生成S串,";
 StrPrint(S);
 
 Replace(S,S1,S2);
 cout<<"把S串中的所有S1替换为S2";
 StrPrint(S);
 cout<<"S1:";
  StrPrint(S1);
 cout<<"S2:";
 StrPrint(S2);
 StrDelete(S1,2,3);
 cout<<"删除S1自2起的三个字母,";
 StrPrint(S1);

 StrInsert(S1,S2,2);
 cout<<"在S1的第2个位置插入S2串,";StrPrint(S1);
 cout<<"S2在S1中的位置,"<<Index(S1,S2,1)<<endl;
 
 
 Concat(S,S1,S2);
 cout<<"把S2接在S1的后面作为新串S,";
 StrPrint(S);
 

 cout<<"从S1的第2个位置截取2个字符,";
 if(SubStr(S,S1,2,2)==OK)
  StrPrint(S);
 else
  cout<<"失败!"<<endl;
 //StrCopy(S2,S1);
 
 if(StrCompare(S1,S2)>0)
  cout<<"串S1,S2比较:S1串大!"<<endl;
 else
  cout<<"串S1,S2比较:S2串大!"<<endl;
 StrClear(S2);
 if(StrEmpty(S2)==true)
  cout<<"串为空!"<<endl;
 else
  cout<<"串不空!"<<endl;
 cout<<"串的长度为:"<<StrLen(S1)<<endl;
 return 0;
}

Leave a Reply

Your email address will not be published.