《数据结构》读书笔记 第四章 堆分配存储串及基本操作

堆分配前天的普通串比有如下优点:

(1)节省空间,用多少,分配多少!

(2)struct结构体体积小,减少了位对齐的机会,提高了效率

缺点:

(1)用了new所以记得delete

(2)结构上字符串从0开始,这个下标是很折磨人的

HString.h

#include <iostream>

enum {OK=0,WRONG=-1};
typedef int Status;

struct HString
{
 char *chars;
 int len;
};

void StrInit(HString &S)
{
 S.chars=NULL;
 S.len=0;
}

Status StrAssign(HString &S,char *T)
{
 int i;
 int len=strlen(T);
 if(S.chars!=NULL)
  delete S.chars;
 S.chars=new char[len];
 if(S.chars==NULL)
  return WRONG;
 for(i=0;i<len;i++)
  S.chars[i]=T[i];
 S.len=len;
 return OK;
}

Status StrCopy(HString &S,HString T)
{
 int i;
 if(S.chars!=NULL)
  delete S.chars;
 S.chars=new char[T.len];
 if(S.chars==NULL)
  return WRONG;
 S.len=T.len;
 for(i=0;i<T.len;i++)
  S.chars[i]=T.chars[i];
 return OK;
}

bool StrEmpty(HString S)
{
 return S.chars==NULL&&S.len==0;
}

int StrCompare(HString H,HString T)
{
 int i=0;
 
 while(i<H.len&&i<T.len)
  if(H.chars[i]!=T.chars[i])
   return H.chars[i]-T.chars[i];
  else
   i++;
 
 return H.len-T.len;
}

int StrLen(HString S)
{
 return S.len;
}

void StrClear(HString &S)
{
 delete S.chars;
 S.chars=NULL;
 S.len=0;
}
Status StrConCat(HString &T,HString S1,HString S2)
{
 int i;
 if(T.chars!=NULL)
  delete T.chars;
 T.chars=new char[S1.len+S2.len];
 if(T.chars==NULL)
  return WRONG;
 T.len=S1.len+S2.len;
 for(i=0;i<S1.len;i++)
  T.chars[i]=S1.chars[i];
 for(i=0;i<S2.len;i++)
  T.chars[i+S1.len]=S2.chars[i];
 return OK;
}

Status StrSub(HString &Sub,HString S,int pos,int len)
{
 if(pos<1||pos>S.len||len<0||pos+len>S.len+1)
  return WRONG;
 int i;
 if(Sub.chars!=NULL)
  delete Sub.chars;
 
 if(len==0)
 {
  Sub.chars=NULL;
  Sub.len=0;
 }
 else
 {

  Sub.chars=new char[len];
  if(Sub.chars==NULL)
   return WRONG;
  for(i=0;i<len;i++)
   Sub.chars[i]=S.chars[pos-1+i];
  Sub.len=len;
 }
 return OK;
}

void GetNext(HString T,int *next)
{
 int i=0,j=-1;
 next[0]=-1;
 while(i<T.len-1)
  if(j==-1||T.chars[i]==T.chars[j])
  {
   i++;
   j++;
   next[i]=j;
  }
  else
   j=next[j];

}

int Index(HString S,HString T,int pos)
{
 int *next,i=pos-1,j=0;
 next=new int[T.len];
 GetNext(T,next);
 while(i<S.len&&j<T.len)
  if(j==-1||S.chars[i]==T.chars[j])
  {
   i++;
   j++;
  }
  else
   j=next[j];
 if(j>=T.len)
  return i-T.len+1;
 else
  return 0;
 
}

Status StrInsert(HString &S,HString T,int pos)
{
 int i;
 char *newchars;
 if(pos<1||pos>S.len+1)
  return WRONG;

 newchars=new char[S.len+T.len];
 if(newchars==NULL)
  return WRONG;
 memcpy(newchars,S.chars,sizeof(char)*S.len);
 delete S.chars;
 //一定注意这个循环,想想为什么从后往前拷贝呢?因为从前会错的!
 for(i=S.len-1;i>=pos-1;i–)
 {
  newchars[i+T.len]=newchars[i];
 }
 for(i=0;i<T.len;i++)
 {
  newchars[i+pos-1]=T.chars[i];
 }

 S.chars=newchars;
 S.len+=T.len;
 return OK;
}

Status StrDelete(HString &S,int pos,int len)
{
 int i;
 char *newchars;
 if(pos+len>S.len+1)
  return WRONG;

 newchars=new char[S.len-len];
 memcpy(newchars,S.chars,S.len*sizeof(char));
 for(i=pos-1;i<=S.len-1;i++)
  newchars[i]=S.chars[i+len];
 delete S.chars;
 S.chars=newchars;
 S.len-=len;
 return OK;
}

Status Replace(HString &S,HString T,HString V)
{
 int i=1;
 if(S.chars==NULL)
  return WRONG;
 while(i)
 {
  i=Index(S,T,i);
  if(i!=0)
  {
   StrDelete(S,i,T.len);
   StrInsert(S,V,i);
   i+=V.len;
  } 
 }
 return OK;
}

void StrPrint(HString S)
{
 int i;
 for(i=0;i<S.len;i++)
  std::cout<<S.chars[i];
 std::cout<<std::endl;
}

main.cpp

#include "HString.h"
using namespace std;
int main()
{
 HString S1,S2,S;
 StrInit(S1);
 StrInit(S2);
 StrInit(S);
 StrAssign(S1,"ab");
 cout<<"输出S1:";
 StrPrint(S1);
 StrAssign(S2,"x");
 cout<<"输出S2:";
 StrPrint(S2);
 StrAssign(S,"ababaabbbaaabbaa");
 cout<<"输出S:";
 StrPrint(S); 
 
 Replace(S,S1,S2);
 cout<<"把S中的S1用S2替换掉:";
 StrPrint(S);

 StrInsert(S1,S2,2);
 cout<<"把S2插入在S1的2位置:";
 StrPrint(S1);
 
 StrDelete(S1,2,1);
 cout<<"删除刚才的插入:";
 StrPrint(S1);

 cout<<"S2在S1的位置"<<Index(S1,S2,1)<<endl;
 cout<<"串2的大小:"<<StrLen(S2)<<endl; 
 cout<<"对S1与S2做比较:";
 if(StrCompare(S1,S2)>0)
  cout<<"串1大"<<endl;
 else
  cout<<"串2大"<<endl;
 //StrCopy(T,S);
 StrConCat(S,S1,S2);
 cout<<"把S1,S2连接起来到S,输出S:";
 StrPrint(S);
 if(StrSub(S,S1,2,5)==OK)
 {
  cout<<"截取S1的字符串,复制到S,输出:";
  StrPrint(S);
 }
 return 0;
}

Leave a Reply

Your email address will not be published.