一、串定义
串（或字符串），是由零个或多个字符组成的有限序列。一般记为：
s='a1a2...an'(n>=0)
其中s是串的名，用单引号括起来的字符序列是串的值；串中字符的数目n称为串的长度。零个字符的串称为空串，它的长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称字符在序列中的称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
例：a='BEI',b='JING',c='BEIJING',d='BEI JING'
串长分别为3,4,7,8,且a,b都是c,d的子串。
称两个串是相等的，当且仅当这两个串的值相等。
二、串的抽象数据类型的定义：
ADT String{
数据对象：D={ai|ai(-CharacterSet,i=1,2,...,n,n>=0}
数据关系：R1={<ai-1,ai>|ai-1,ai(-D,i=2,...,n}
基本操作：
StrAssign(&T,chars)
chars是字符常量。生成一个其值等于chars的串T。
StrCopy(&T,S)
串S存在则由串S复制得串T
StrEmpty(S)
串S存在则若S为空串,返回真否则返回假
StrCompare(S,T)
串S和T存在,若S>T,则返回值大于0,若S=T,则返回值=0,若S<T,则返回值<0
StrLength(S)
串S存在返回S的元素个数称为串的长度.
ClearString(&S)
串S存在将S清为空串
Concat(&T,S1,S2)
串S1和S2存在用T返回由S1和S2联接而成的新串
SubString(&Sub,S,pos,len)
串S存在,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
Index(S,T,pos)
串S和T存在,T是非空,1<=pos<=StrLength(S),若主串S中存在和串T值相同的子串,则返回它在主串S中第pos个字符之后第一次出现的位置,否则函数值为0
Replace(&S,T,V)
串S,T和V存在,T是非空串,用V替换主串S中出现的所有与T相等的不重叠的子串
StrInsert(&S,pos,T)
串S和T存在,1<=pos<=StrLength(S)+1,在串S的第pos个字符之前插入串T
StrDelete(&S,pos,len)
串S存在,1<=pos<=StrLength(S)-len+1从串中删除第pos个字符起长度为len的子串
DestroyString(&S)
串S存在,则串S被销毁
}ADT String
三、串操作应用举例:
1文字处理中常用的:串的查找(比较,定位)与替换
在TC集成环境中可用^QF快速查找变量 在WORD中可用搜索与替换批量改变文本
2串的截断与连接
可用求子串及串连接的方法进行文字处理
四. 源代码
#include <stdio.h>
#define MAXLEN 100
typedef struct{
char vec[MAXLEN];
int len;
}Str;
void ConcatStr(Str *s1,Str *s2)
{ int i;
printf("s1=%s s2=%s\n",s1->vec,s2->vec);
if(s1->len+s2->len>MAXLEN)
printf("\n\t\t两个串太长，溢出！\n");
else
{ for(i=0;i<s2->len;i++)
s1->vec[s1->len+i]=s2->vec[i];
s1->vec[s1->len+i]='\0';
s1->len=s1->len+s2->len;
}
}
void SubStr(Str *s,int i,int j)
{
int k;
Str a;
Str *s1=&a;
if(i+j-1>s->len)
{
printf("\n\t\t子串超界!\n");
return;
}
else
{ for(k=0;k<j;k++)
s1->vec[k]=s->vec[i+k-1];
s1->len=j;
s1->vec[s1->len]='\0';
}
printf("\n\t\t取出字符为：");
puts(s1->vec);
}
void DelStr(Str *s,int i,int j)
{ int k;
if(i+j-1>s->len)
printf("\n\t\t所要删除的子串超界！\n");
else
{ for(k=i+j;k<s->len;k++,i++)
s->vec[i]=s->vec[k];
s->len=s->len-j;
s->vec[s->len]='\0';
}
}
Str *InsStr(Str *s,Str *s1,int i)
{ int k;
if(i>=s->len||s->len+s1->len>MAXLEN)
printf("\n\t\t不能插入!\n");
else
{ for(k=s->len-1;k>=i;k--)
s->vec[s1->len+k]=s->vec[k];
for(k=0;k<s1->len;k++)
s->vec[i+k]=s1->vec[k];
s->len=s->len+s1->len;
s->vec[s->len]='\0';
}
return s;
}
int IndexStr(Str *s,Str *s1)
{ int i,j,k;
for(i=0;s->vec[i];i++)
for(j=i,k=0;s->vec[j]==s1->vec[k];j++,k++)
if(!s1->vec[k+1])
return i;
return -1;
}
int LenStr(Str *s)
{ int i=0;
while(s->vec[i]!='\0')
i++;
return i;
}
Str *CseateStr(Str *s)
{ gets(s->vec);
s->len=LenStr(s);
return s;
}
int EqualStr(Str *s1,Str *s2)
{
int i;
for(i=0;s1->vec[i]==s2->vec[i]&&s1->vec[i];i++);
return s1->vec[i]-s2->vec[i];
}
void main() // 串子系统主函数
{ Str a,b,c,d;
Str *s=&a,*s1;
s->vec[0]='\0';
char choice,p;
int i,j,ch=1;
while(ch!=0)
{ printf("\n");
printf("\n");
printf("\n");
printf("\n");
printf("\n\t\t\t\t串 子 系 统 \n");
printf("\n\t\t***************************************");
printf("\n\t\t* 1----------输 入 字 串 *");
printf("\n\t\t* 2----------连 接 字 串 *");
printf("\n\t\t* 3----------取 出 子 串 *");
printf("\n\t\t* 4----------删 除 子 串 *");
printf("\n\t\t* 5----------插 入 子 串 *");
printf("\n\t\t* 6----------查 找 子 串 *");
printf("\n\t\t* 7----------比 较 串 大 小 *");
printf("\n\t\t* 8----------显 示 字 串 *");
printf("\n\t\t* 0----------返 回 *");
printf("\n\t\t***************************************");
printf("\n\t\t请输入菜单号(0--8)：");
scanf("%c",&choice);getchar();
printf("\n");
printf("\n");
if (choice=='1')
{ printf("\n\t\t请输入一个字符串:");
gets(s->vec);
s->len=LenStr(s);
}
else if (choice=='2')
{printf("\n\t\t请输入所要连接的串：");
s1=CseateStr(&b);
ConcatStr(s,s1);
}
else if (choice=='3')
{ printf("\n\t\t请输入从第几个字符开始：");
scanf("%d",&i);getchar();
printf("\n\t\t请输入取出的连续字符数：");
scanf("%d",&j);getchar();
SubStr(s,i,j);
}
else if (choice=='4')
{ printf("\n\t\t请输入从第几个字符开始：");
scanf("%d",&i);getchar();
printf("\n\t\t请输入删除的连续字符数：");
scanf("%d",&j);getchar();
DelStr(s,i-1,j);
}
else if (choice=='5')
{ printf("\n\t\t请输入在第几个字符前插入：");
scanf("%d",&i);getchar();
printf("\n\t\t请输入所要插入的字符串：");
s1=CseateStr(&b);
InsStr(s,s1,i-1);
}
else if (choice=='6')
{ printf("\n\t\t请输入所要查找的字符串：");
s1=CseateStr(&b);
i=IndexStr(s,s1);
if(i!=-1)
printf ("\n\t\t第一次出现的位置是第%d个。\n",i+1);
else
printf ("\n\t\t该子串不在其中！\n");
}
else if(choice=='7')
{ printf("\n\t\t请输入第一个串：");
gets(c.vec);
printf("\n\t\t请输入第二个串：");
gets(d.vec);
int k=EqualStr(&c,&d);
if(k>0)
printf("\n\t\t第一个串大！");
else if(k<0)
printf("\n\t\t第二个串大！");
else
printf("\n\t\t一样大！");
}
else if (choice=='8')
{ printf ("\n\t\t该串值为：");
if(s->vec[0]=='\0')
printf("空！");
else
puts(s->vec);
}
else if (choice=='0')
break;
else
printf ("\n\t\t\t***请注意：输入有误！***\n");
if (choice!='X'&&choice!='X')
{ printf ("\n\n\t\t按回车键继续,按任意键返回主菜单.\n");
p=getchar();
if(p!='\xA')
{getchar();
break;}
}
}
}
