/*字符串编程，将字符串S中出现的子串T1用字符串T2替代
ahebhechedhe
he
hello!
ahello!bhello!chello!dhello!
*/
/*静态数组实现*/
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#define MAXSTRLEN 255
typedef unsigned char SString[MAXSTRLEN + 1];
typedef int Status;
void StrAssign(SString &S,char *chars)
{//串赋值
int length = 0;
unsigned char * Sclient = S + 1;
while(*(chars))
{
*Sclient = *chars;
chars++;
Sclient++;
length++;
}
*Sclient = '\0';
S[0] = length;
}
void Display_String(SString S)
{//串显示
cout<<S + 1<<endl;
}
int Index(SString S, SString T, int Pos)
{//在串S中扫描子串T的位置值，如不存在子串T返回0
unsigned char *Sclient = S + 1;
int clientLen = 0;
if (Pos > S[0])
return -1;
T++;
while (*(Sclient))
{
while(*(T) == *(Sclient + Pos))
{
T++;
if (!*T)
return Pos;
clientLen++;
Sclient++;
}
Sclient = Sclient - clientLen;
Pos++;
}
return -1;
}
void Delete(SString &S, int pos, int len)
{//在串S中删去从pos位置开始的len个字符
S[0] -= len;
unsigned char * Sclient = S + 1;
while (*(Sclient + len + pos))
{
*(Sclient + pos) = *(Sclient + pos +len);
Sclient++;
}
*(Sclient + pos) = '\0';
}
void Insert(SString &S,int &pos,SString T)
{//在串S的pos位置插入子串T
int i;
if(pos != S[0])
{
for (i = 0; i < S[0] - pos; i++)
{
*(S + S[0] + T[0] - i) = *(S + S[0] - i);
}
}
for(i = 0; i < T[0]; i++)
{
S[pos + i + 1] = T[i + 1];
}
S[0] += T[0];
*(S + S[0] + 1) = '\0';
pos += T[0];
}
void Replace_SubString(SString &S, SString T1, SString T2)
{//通过对Index、Delete和Insert函数的调用，完成将串S中出现的子串T1用串T2替代
int pos = 0;
int posFlag = -1;
while (1)
{
pos = Index(S, T1, pos);
if (pos < posFlag)
break;
posFlag = pos;
Delete(S, pos, T1[0]);
Insert(S, pos, T2);
}
}
void main( void )
{
SString S, T1,T2;
StrAssign(S, "ahebhechedhe");
Display_String(S);
StrAssign(T1,"he");
Display_String(T1);
StrAssign(T2,"HELLO!");
Display_String(T2);
Replace_SubString(S,T1,T2);
Display_String(S);
}
/*用动态链表实现：*/
#include <stdio.h>
#include <stdlib.h>
#define MAXSTRLEN 255
typedef struct
{
char *ch;
int length;
} HString;
void StrAssign(HString &S, char *chars)
{
//串赋值
char* c;
int i, j;
if (!S.ch)
free(S.ch);
for (i = 0, c = chars; *c; c++, i++ );
if (!i)
{
S.ch = NULL;
S.length = 0;
}
else
{
if (!(S.ch = (char*)(malloc(sizeof(char) * i))))
return;
for (j = 0; j < i; j++)
S.ch[j] = chars[j];
}
S.length = i;
}
void Display_String(HString S)
{//串显示
if (S.ch == NULL)
return;
int i;
for(i = 0; i < S.length; i++)
printf("%c", S.ch[i]);
printf("\n");
}
int Index(HString S, HString T,int Pos)
{//在串S中扫描子串T的位置值，如不存在子串T返回0
int clientLen = 0;
char * Tclient = T.ch;
if (Pos >= S.length)
return -1;
char * Sclient = S.ch;
while ((Sclient - S.ch) <= S.length)
{
while(*(Tclient) == *(Sclient + Pos))
{
if ((Tclient - T.ch) < S.length)
return Pos;
Tclient++;
clientLen++;
Sclient++;
}
Sclient = Sclient - clientLen;
Pos++;
}
return -1;
}
void Delete(HString &S,int pos,int len)
{//在串S中删去从pos位置开始的len个字符
int i;
for (i = 0; i < (S.length - pos); i++)
S.ch[pos + i] = S.ch[pos + i + len];
S.length -= len;
}
void Insert(HString &S,int &pos,HString T)
{//在串S的pos位置插入子串T
S.ch = (char *)realloc(S.ch, T.length + S.length);
S.length += T.length;
int i;
if(pos != S.length)
{
for (i = 0; i < S.length - pos; i++)
{
*(S.ch + S.length + T.length-1 - i) = *(S.ch + S.length -1- i);
}
}
for(i = 0; i < T.length; i++)
{
S.ch[pos + i] = T.ch[i];
}
pos += T.length;
}
void Replace_SubString(HString &S, HString T1,HString T2)
{// 通过对Index、Delete和Insert函数的调用，完成将串S中出现的子串T1用串T2替代
int pos = 0;
int posFlag = -1;
while (1)
{
pos = Index(S, T1, pos);
if (pos < posFlag)
break;
posFlag = pos;
Delete(S, pos, T1.length);
Insert(S, pos, T2);
}
}
void main()
{
HString S, T1, T2;
StrAssign(S, "ahebhechedhe");
Display_String(S);
StrAssign(T1, "he");
Display_String(T1);
StrAssign(T2, "hello!");
Display_String(T2);
Replace_SubString(S,T1,T2);
Display_String(S);
}
