字符串
维基百科，自由的百科全书
字符串或字串（String）是由零个或多个字符组成的有限序列。一般记为 s='a1a2•••an'(n>=0)。它是编程语言中表示文本的-{zh-cn:数据类型;zh-tw:資料型別}-。
通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。设p、q是两个串，求q在p中首次出现的位置的运算叫做模式匹配。串的两种最基本的存储方式是顺序存储方式和链接存储方式。
目录 |
[编辑] 编程语言中的表示法
一种常用的表示法是使用一个字符代码的数组，每个字符占用一个字节（如在ASCII代码中）或两个字节（如在unicode中）。它的长度可以使用一个结束符（一般是NUL，ASCII代码是0，在C编程语言中使用这种方法）。或者在前面加入一个整数值来表示它的长度（在Pascal语言中使用这种方法）。
这是一个用NUL结束的字符串的例子，它用10个byte存储，用ASCII表示法：
| F | R | A | N | K | k | f | f | w | |
| 46 | 52 | 41 | 4E | 4B | 00 | 6B | 66 | 66 | 77 |
上面的字符串的长度为5个字符，但注意它占用6个字节。结束符后的字符没有任何意义。
这是相同的Pascal字符串：
| F | R | A | N | K | k | f | f | w | |
| 05 | 46 | 52 | 41 | 4E | 4B | 6B | 66 | 66 | 77 |
当然，可能还有其它的表示法。使用树和列表可以使得一些字符串操作（如插入和删除）更高效。
[编辑] 定长顺序存储表示
[编辑] 存储结构
/* 串的定长顺序存储表示 */ #define MAX_STR_LEN 40 /* 用户可在255(1个字节)以内定义最大串长 */ typedef char SString[MAX_STR_LEN+1]; /* 0号单元存放串的长度 */
[编辑] 基本操作
/* 串采用定长顺序存储结构的基本操作(13个) */
/* SString是数组，故不需引用类型 */
#define DestroyString ClearString /* DestroyString()与ClearString()作用相同 */
Status StrAssign(SString T,char *chars)
{ /* 生成一个其值等于chars的串T */
int i;
if(strlen(chars)>MAX_STR_LEN)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
void StrCopy(SString T,SString S)
{ /* 由串S复制得串T */
int i;
for(i=0;i<=S[0];i++)
T[i]=S[i];
}
Status StrEmpty(SString S)
{ /* 若S为空串，则返回TRUE，否则返回FALSE */
if(S[0]==0)
return TRUE;
else
return FALSE;
}
int StrCompare(SString S,SString T)
{ /* 初始条件：串S和T存在。操作结果：若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0 */
int i;
for(i=1;i<=S[0]&&i<=T[0];++i)
if(S[i]!=T[i])
return S[i]-T[i];
return S[0]-T[0];
}
int StrLength(SString S)
{ /* 返回串S的元素个数 */
return S[0];
}
void ClearString(SString S)
{ /* 初始条件：串S存在。操作结果：将S清为空串 */
S[0]=0; /* 令串长为零 */
}
Status Concat(SString T,SString S1,SString S2) /* 算法4.2改 */
{ /* 用T返回S1和S2联接而成的新串。若未截断，则返回TRUE，否则FALSE */
int i;
if(S1[0]+S2[0]<=MAX_STR_LEN)
{ /* 未截断 */
for(i=1;i<=S1[0];i++)
T[i]=S1[i];
for(i=1;i<=S2[0];i++)
T[S1[0]+i]=S2[i];
T[0]=S1[0]+S2[0];
return TRUE;
}
else
{ /* 截断S2 */
for(i=1;i<=S1[0];i++)
T[i]=S1[i];
for(i=1;i<=MAX_STR_LEN-S1[0];i++)
T[S1[0]+i]=S2[i];
T[0]=MAX_STR_LEN;
return FALSE;
}
}
Status SubString(SString Sub,SString S,int pos,int len)
{ /* 用Sub返回串S的第pos个字符起长度为len的子串。算法4.3 */
int i;
if(pos<1||pos>S[0]||len<0||len>S[0]-pos+1)
return ERROR;
for(i=1;i<=len;i++)
Sub[i]=S[pos+i-1];
Sub[0]=len;
return OK;
}
int Index(SString S,SString T,int pos)
{ /* 返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0。 */
/* 其中，T非空，1≤pos≤StrLength(S)。算法4.5 */
int i,j;
if(1<=pos&&pos<=S[0])
{
i=pos;
j=1;
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;
}
else
return 0;
}
Status StrInsert(SString S,int pos,SString T)
{ /* 初始条件：串S和T存在，1≤pos≤StrLength(S)+1 */
/* 操作结果：在串S的第pos个字符之前插入串T。完全插入返回TRUE，部分插入返回FALSE */
int i;
if(pos<1||pos>S[0]+1)
return ERROR;
if(S[0]+T[0]<=MAX_STR_LEN)
{ /* 完全插入 */
for(i=S[0];i>=pos;i--)
S[i+T[0]]=S[i];
for(i=pos;i<pos+T[0];i++)
S[i]=T[i-pos+1];
S[0]+=T[0];
return TRUE;
}
else
{ /* 部分插入 */
for(i=MAX_STR_LEN;i>=pos+T[0];i--)
S[i]=S[i-T[0]];
for(i=pos;i<pos+T[0]&&i<=MAX_STR_LEN;i++)
S[i]=T[i-pos+1];
S[0]=MAX_STR_LEN;
return FALSE;
}
}
Status StrDelete(SString S,int pos,int len)
{ /* 初始条件：串S存在，1≤pos≤StrLength(S)-len+1 */
/* 操作结果：从串S中删除第pos个字符起长度为len的子串 */
int i;
if(pos<1||pos>S[0]-len+1||len<0)
return ERROR;
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) /* 此函数与串的存储结构无关 */
{ /* 初始条件：串S，T和V存在，T是非空串 */
/* 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串 */
int i=1; /* 从串S的第一个字符起查找串T */
Status k;
if(StrEmpty(T)) /* T是空串 */
return ERROR;
do
{
i=Index(S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */
if(i) /* 串S中存在串T */
{
StrDelete(S,i,StrLength(T)); /* 删除该串T */
k=StrInsert(S,i,V); /* 在原串T的位置插入串V */
if(!k) /* 不能完全插入 */
return ERROR;
i+=StrLength(V); /* 在插入的串V后面继续查找串T */
}
}while(i);
return OK;
}
void StrPrint(SString T)
{ /* 输出字符串T。另加 */
int i;
for(i=1;i<=T[0];i++)
printf("%c",T[i]);
printf("\n");
}
[编辑] 堆分配存储表示
[编辑] 存储结构
/* 串的堆分配存储 */
typedef struct
{
char *ch; /* 若是非空串，则按串长分配存储区，否则ch为NULL */
int length; /* 串长度 */
}HString;
[编辑] 基本操作
/* 串采用堆分配存储结构的基本操作(14个)*/
#define DestroyString ClearString /* DestroyString()与ClearString()作用相同 */
void StrAssign(HString *T,char *chars)
{ /* 生成一个其值等于串常量chars的串T */
int i,j;
if((*T).ch)
free((*T).ch); /* 释放T原有空间 */
i=strlen(chars); /* 求chars的长度i */
if(!i)
{ /* chars的长度为0 */
(*T).ch=NULL;
(*T).length=0;
}
else
{ /* chars的长度不为0 */
(*T).ch=(char*)malloc(i*sizeof(char)); /* 分配串空间 */
if(!(*T).ch) /* 分配串空间失败 */
exit(OVERFLOW);
for(j=0;jT，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0 */
int i;
for(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;
}
int StrLength(HString S)
{ /* 返回S的元素个数，称为串的长度 */
return S.length;
}
void ClearString(HString *S)
{ /* 将S清为空串 */
free((*S).ch);
(*S).ch=NULL;
(*S).length=0;
}
void Concat(HString *T,HString S1,HString S2)
{ /* 用T返回由S1和S2联接而成的新串 */
int i;
if((*T).ch)
free((*T).ch); /* 释放旧空间 */
(*T).length=S1.length+S2.length;
(*T).ch=(char *)malloc((*T).length*sizeof(char));
if(!(*T).ch)
exit(OVERFLOW);
for(i=0;i<S1.length;i++)
(*T).ch[i]=S1.ch[i];
for(i=0;i<S2.length;i++)
(*T).ch[S1.length+i]=S2.ch[i];
}
Status SubString(HString *Sub, HString S,int pos,int len)
{ /* 用Sub返回串S的第pos个字符起长度为len的子串。 */
/* 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1 */
int i;
if(pos<1||pos>S.length||len<0||len>S.length-pos+1)
return ERROR;
if((*Sub).ch)
free((*Sub).ch); /* 释放旧空间 */
if(!len) /* 空子串 */
{
(*Sub).ch=NULL;
(*Sub).length=0;
}
else
{ /* 完整子串 */
(*Sub).ch=(char*)malloc(len*sizeof(char));
if(!(*Sub).ch)
exit(OVERFLOW);
for(i=0;i<=len-1;i++)
(*Sub).ch[i]=S.ch[pos-1+i];
(*Sub).length=len;
}
return OK;
}
void InitString(HString *T)
{ /* 初始化(产生空串)字符串T。另加 */
(*T).length=0;
(*T).ch=NULL;
}
int Index(HString S,HString T,int pos) /* 算法4.1 */
{ /* T为非空串。若主串S中第pos个字符之后存在与T相等的子串，*/
/* 则返回第一个这样的子串在S中的位置，否则返回0 */
int n,m,i;
HString sub;
InitString(&sub);
if(pos>0)
{
n=StrLength(S);
m=StrLength(T);
i=pos;
while(i<=n-m+1)
{
SubString(&sub,S,i,m);
if(StrCompare(sub,T)!=0)
++i;
else
return i;
}
}
return 0;
}
Status StrInsert(HString *S,int pos,HString T) /* 算法4.4 */
{ /* 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T */
int i;
if(pos<1||pos>(*S).length+1) /* pos不合法 */
return ERROR;
if(T.length) /* T非空，则重新分配空间，插入T */
{
(*S).ch=(char*)realloc((*S).ch,((*S).length+T.length)*sizeof(char));
if(!(*S).ch)
exit(OVERFLOW);
for(i=(*S).length-1;i>=pos-1;--i) /* 为插入T而腾出位置 */
(*S).ch[i+T.length]=(*S).ch[i];
for(i=0;i<T.length;i++)
(*S).ch[pos-1+i]=T.ch[i]; /* 插入T */
(*S).length+=T.length;
}
return OK;
}
Status StrDelete(HString *S,int pos,int len)
{ /* 从串S中删除第pos个字符起长度为len的子串 */
int i;
if((*S).length<pos+len-1)
return ERROR;
for(i=pos-1;i<=(*S).length-len;i++)
(*S).ch[i]=(*S).ch[i+len];
(*S).length-=len;
(*S).ch=(char*)realloc((*S).ch,(*S).length*sizeof(char));
return OK;
}
Status Replace(HString *S,HString T,HString V) /* 此函数与串的存储结构无关 */
{ /* 初始条件：串S，T和V存在，T是非空串 */
/* 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串 */
int i=1; /* 从串S的第一个字符起查找串T */
if(StrEmpty(T)) /* T是空串 */
return ERROR;
do
{
i=Index(*S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */
if(i) /* 串S中存在串T */
{
StrDelete(S,i,StrLength(T)); /* 删除该串T */
StrInsert(S,i,V); /* 在原串T的位置插入串V */
i+=StrLength(V); /* 在插入的串V后面继续查找串T */
}
}while(i);
return OK;
}
void StrPrint(HString T)
{ /* 输出T字符串。另加 */
int i;
for(i=0;i<T.length;i++)
printf("%c",T.ch[i]);
printf("\n");
}
[编辑] 块链存储表示
[编辑] 存储结构
/* 串的块链存储表示 */
#define CHUNK_SIZE 4 /* 可由用户定义的块大小 */
typedef struct Chunk
{
char ch[CHUNK_SIZE];
struct Chunk *next;
}Chunk;
typedef struct
{
Chunk *head,*tail; /* 串的头和尾指针 */
int curlen; /* 串的当前长度 */
}LString;
[编辑] 基本操作
/* 串采用块链存储结构的基本操作(15个) */
#define DestroyString ClearString /* DestroyString()与ClearString()作用相同 */
void InitString(LString *T)
{ /* 初始化(产生空串)字符串T。另加 */
(*T).curlen=0;
(*T).head=(*T).tail=NULL;
}
Status StrAssign(LString *T,char *chars)
{ /* 生成一个其值等于chars的串T(要求chars中不包含填补空余的字符)。成功返回OK，否则返回ERROR */
int i,j,k,m;
Chunk *p,*q;
i=strlen(chars); /* i为串的长度 */
if(!i||strchr(chars,blank)) /* 串长为0或chars中包含填补空余的字符 */
return ERROR;
(*T).curlen=i;
j=i/CHUNK_SIZE; /* j为块链的结点数 */
if(i%CHUNK_SIZE)
j++;
for(k=0;k<j;k++)
{
p=(Chunk*)malloc(sizeof(Chunk)); /* 生成块结点 */
if(!p) /* 生成块结点失败 */
return ERROR;
for(m=0;m<CHUNK_SIZE&&*chars;m++) /* 给块结点的数据域赋值 */
*(p->ch+m)=*chars++;
if(k==0) /* 第一个链块 */
(*T).head=q=p; /* 头指针指向第一个链块 */
else
{
q->next=p;
q=p;
}
if(!*chars) /* 最后一个链块 */
{
(*T).tail=q;
q->next=NULL;
for(;m<CHUNK_SIZE;m++) /* 用填补空余的字符填满链表 */
*(q->ch+m)=blank;
}
}
return OK;
}
Status ToChars(LString T,char* *chars)
{ /* 将串T的内容转换为字符串，chars为其头指针。成功返回OK，否则返回ERROR。另加 */
Chunk *p=T.head; /* p指向第1个块结点 */
int i;
char *q;
*chars=(char*)malloc((T.curlen+1)*sizeof(char));
if(!chars||!T.curlen) /* 生成字符串数组失败或串T长为0 */
return ERROR;
q=*chars; /* q指向chars的第1个字符 */
while(p) /* 块链没结束 */
{
for(i=0;i<CHUNK_SIZE;i++)
if(p->ch[i]!=blank) /* 当前字符不是填补空余的字符 */
*q++=(p->ch[i]); /* 赋给q所指字符空间 */
p=p->next;
}
(*chars)[T.curlen]=0; /* 串结束符 */
return OK;
}
Status StrCopy(LString *T,LString S)
{ /* 初始条件：串S存在 */
/* 操作结果：由串S复制得串T，去掉填补空余的字符。成功返回OK，否则返回ERROR */
char *c;
Status i;
if(!ToChars(S,&c)) /* c为串S的内容 */
return ERROR;
i=StrAssign(T,c); /* 将串S的内容赋给T */
free(c); /* 释放c的空间 */
return i;
}
Status StrEmpty(LString S)
{ /* 初始条件：串S存在。操作结果：若S为空串，则返回TRUE，否则返回FALSE */
if(S.curlen) /* 非空 */
return FALSE;
else
return TRUE;
}
int StrCompare(LString S,LString T)
{ /* 若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0 */
char *s,*t;
Status i;
if(!ToChars(S,&s)) /* s为串S的内容 */
return ERROR;
if(!ToChars(T,&t)) /* t为串T的内容 */
return ERROR;
i=strcmp(s,t); /* 利用C的库函数 */
free(s); /* 释放s，t的空间 */
free(t);
return i;
}
int StrLength(LString S)
{ /* 返回S的元素个数，称为串的长度 */
return S.curlen;
}
void ClearString(LString *S)
{ /* 初始条件：串S存在。操作结果：将S清为空串 */
Chunk *p,*q;
p=(*S).head;
while(p)
{
q=p->next;
free(p);
p=q;
}
(*S).head=(*S).tail=NULL;
(*S).curlen=0;
}
Status Concat(LString *T,LString S1,LString S2)
{ /* 用T返回由S1和S2联接而成的新串(中间可能有填补空余的字符) */
LString a1,a2;
Status i,j;
InitString(&a1);
InitString(&a2);
i=StrCopy(&a1,S1);
j=StrCopy(&a2,S2);
if(!i||!j) /* 至少有1个串拷贝不成功 */
return ERROR;
(*T).curlen=S1.curlen+S2.curlen; /* 生成串T */
(*T).head=a1.head;
a1.tail->next=a2.head; /* a1,a2两串首尾相连 */
(*T).tail=a2.tail;
return OK;
}
Status SubString(LString *Sub, LString S,int pos,int len)
{ /* 用Sub返回串S的第pos个字符起长度为len的子串。 */
/* 其中，1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1 */
char *b,*c;
Status i;
if(pos<1||pos>S.curlen||len<0||len>S.curlen-pos+1) /* pos或len值不合法 */
return ERROR;
if(!ToChars(S,&c)) /* c为串S的内容 */
return ERROR;
b=c+pos-1; /* b指向串c中串Sub内容的首地址 */
b[len]=0; /* Sub结束处赋0(字符串结束符) */
i=StrAssign(Sub,b); /* 将串b的内容赋给Sub */
free(c);
return i;
}
int Index(LString S,LString T,int pos)
{ /* T为非空串。若主串S中第pos个字符之后存在与T相等的子串，*/
/* 则返回第一个这样的子串在S中的位置，否则返回0 */
int i,n,m;
LString sub;
if(pos>=1&&pos<=StrLength(S)) /* pos满足条件 */
{
n=StrLength(S); /* 主串长度 */
m=StrLength(T); /* 串T长度 */
i=pos;
while(i<=n-m+1)
{
SubString(&sub,S,i,m); /* sub为从S的第i个字符起，长度为m的子串 */
if(StrCompare(sub,T)) /* sub不等于T */
++i;
else
return i;
}
}
return 0;
}
Status StrInsert(LString *S, int pos,LString T)
{ /* 1≤pos≤StrLength(S)+1。在串S的第pos个字符之前插入串T */
char *b,*c;
int i,j;
Status k;
if(pos<1||pos>(*S).curlen+1) /* pos的值超出范围 */
return ERROR;
if(!ToChars(*S,&c)) /* c为串S的内容 */
return ERROR;
if(!ToChars(T,&b)) /* b为串T的内容 */
return ERROR;
j=(int)strlen(c); /* j为串S的最初长度 */
c=(char*)realloc(c,(j+strlen(b)+1)*sizeof(char)); /* 增加c的存储空间 */
for(i=j;i>=pos-1;i--)
c[i+strlen(b)]=c[i]; /* 为插入串b腾出空间 */
for(i=0;i<(int)strlen(b);i++) /* 在串c中插入串b */
c[pos+i-1]=b[i];
InitString(S); /* 释放S的原有存储空间 */
k=StrAssign(S,c); /* 由c生成新的串S */
free(b);
free(c);
return k;
}
Status StrDelete(LString *S,int pos,int len)
{ /* 从串S中删除第pos个字符起长度为len的子串 */
char *c;
int i;
Status k;
if(pos<1||pos>(*S).curlen-len+1||len<0) /* pos，len的值超出范围 */
return ERROR;
if(!ToChars(*S,&c)) /* c为串S的内容 */
return ERROR;
for(i=pos+len-1;i<=(int)strlen(c);i++)
c[i-len]=c[i]; /* c为删除后串S的内容 */
InitString(S); /* 释放S的原有存储空间 */
k=StrAssign(S,c); /* 由c生成新的串S */
free(c);
return k;
}
Status Replace(LString *S,LString T,LString V) /* 此函数与串的存储结构无关 */
{ /* 初始条件：串S，T和V存在，T是非空串 */
/* 操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串 */
int i=1; /* 从串S的第一个字符起查找串T */
if(StrEmpty(T)) /* T是空串 */
return ERROR;
do
{
i=Index(*S,T,i); /* 结果i为从上一个i之后找到的子串T的位置 */
if(i) /* 串S中存在串T */
{
StrDelete(S,i,StrLength(T)); /* 删除该串T */
StrInsert(S,i,V); /* 在原串T的位置插入串V */
i+=StrLength(V); /* 在插入的串V后面继续查找串T */
}
}while(i);
return OK;
}
void StrPrint(LString T)
{ /* 输出字符串T。另加 */
int i=0,j;
Chunk *h;
h=T.head;
while(i<T.curlen)
{
for(j=0;j<CHUNK_SIZE;j++)
if(*(h->ch+j)!=blank) /* 不是填补空余的字符 */
{
printf("%c",*(h->ch+j));
i++;
}
h=h->next;
}
printf("\n");
}
[编辑] 字符串实用程序
一些编程语言设计为编写字符串处理程序更容易编写。这是一些例子：
很多UNIX实用程序进行简单的字符串处理，并能用于简单地编写一些强大的字符串处理算法。文件和有限流可以像字符串一样查看。
一些新的编程语言，包括Perl、Python和Ruby，借助正则表达式来帮助文字处理。
[编辑] 字符串操作
一个简单的字符串操作是连接：也就是说先写一个字符串S，随后在后面再写一个T得到ST这样一个过程。 其它的常见操作包括在一个长字符串中搜索一个子串，排列一组字符串以及分析一个字符串。因为存在如此多的字符串应用方式，所以相应地有许多权衡了不同应用的相关算法。 高级的字符串算法通常使用包括后向树和有限状态机在内的复杂机制和数据结构。
[编辑] 算法
这是一些字符串处理算法，在字符串上进行不同的处理：
- 字符串查找算法
- 正则表达式算法
- 模式匹配
[编辑] 理论计算机科学中的字符串
在理论计算机科学中，一个非空有限集合的开始的字符串称为字母表；然后字符串就定义为字母表元素的一个有限序列，它包括空序列。使用一个给定字母表的所有字符串与拼接字符串一起，形成一个特异点，事实上是一个自由特异点。形式语言作为研究的中心对象被定义为这个特异点的一个子集。
