4.2 串的表示和实现
4.2 串的表示和实现
如果在程序设计语言中，串只是作为输入或输出的常量出现，则只需存储此串值，即字符序列即可。但在多数非数值处理的程序中，串也以变量的形式出现。串是一种特殊的线性表。串最常用的存储结构是静态分配的定长字符数组或动态分配的地址连续的存储单元。采用这两种存储方法在实现时并无太大的差别。
假如采用链表存放串，若每一个节点仅存放一个字符，由于节点的指针域所占空间一般是字符域所占空间的4倍，故存储空间利用率十分低。为了节省空间，可使每一个节点存放若干个字符。这种存储结构称为块链结构。例如，在采用块链结构的文本编辑系统中，一个块节点可存放80个字符。操作系统中字符I/O缓冲池也采用了块链结构。
串有3种机内表示方法，分别介绍如下。
4.2.1 定长顺序存储表示
串是一种特殊的线性表，它的每个节点仅由一个字符组成，因此可以用存储线性表的一般方法来存储串。存储串最常用的方式是采用顺序存储结构，即把串字符顺序地存储在内存一片相邻的空间内，称为顺序串。如图4-1所示是C/C++中以字符数组方式（顺序串）存储串"abcdefgh"的存储形式，以空格符'\0'标识串结束。
|
a |
b |
c |
d |
e |
f |
g |
h |
\0 |
图4-1 顺序串"abcdefgh"的存储形式
顺序串的类型定义如下：
#define MaxSize /*最多字符个数*/
typedef struct
{
char ch[MaxSize]; /*存放串字符*/
int len; /*存放串的实际长度*/
} SqString; /*顺序串类型*/
其中，ch域用来存储字符串；len域用来存储字符串的实际长度；MaxSize常量表示允许所存储字符串的最大长度。
在顺序串上实现串的基本运算如下。
1．串赋值运算算法
将一个C/C++的字符数组t赋给串s。
void Assign(SqString &s,char t[])
{
int i=0;
while (t[i]!='\0')
{
s.ch[i]=t[i];
i++;
}
s.len=i;
}
2．串复制运算算法
将一个串t赋给串s。
void StrCopy(SqString &s,SqString t)
{
int i;
for(i=0;i<t.len;i++)
s.ch[i]=t.ch[i];
s.len=t.len;
}
3．求串长运算算法
返回串s的长度，即串中包含的字符个数。
int StrLength(SqString s)
{
return(s.len);
}
4．判断串相等运算算法
串相等是指两个串的长度及对应位置的字符完全相同。串s和串t相等时返回1；否则返回0。
int StrEqual(SqString s,SqString t)
{
int i=0;
if(s.len!=t.len) /*串长不同时返回0*/
return(0);
else
{ for(i=0;i<s.len;i++)
if (s.ch[i]!=t.ch[i]) /*有一个对应字符不同时返回0*/
return(0);
return(1);
}
}
5．串连接运算算法
将串t连接到串s之后，返回连接后的结果串。
SqString Concat(SqString s,SqString t)
{
SqString r;
int i,j;
for(i=0;i<s.len;i++) /*将s复制到r*/
r.ch[i]=s.ch[i];
for (j=0;j<t.len;j++) /*将t复制到r*/
r.ch[s.len+j]=t.ch[j];
r.len=i+j;
return(r); /*返回r*/
}
6．求子串运算算法
返回串s的第i个位置开始的j个字符组成的串。
SqString SubStr(SqString s,int i,int j)
{
SqString t;
int k;
if(i<1 || i>s.len || j<1 || i+j>s.len+1)
t.len=0; /*参数错误时返回空串*/
else
{
for(k=i-1;k<i+j;k++)
t.ch[k-i+1]=s.ch[k];
t.len=j;
}
return(t);
}
7．查找子串位置运算算法
返回子串t在主串s中的位置。若串t不在串s中则返回-1。
int Index(SqString s,SqString t)
{
int i=0,j=0,k; /*i和j分别扫描主串s和子串t*/
while(i<s.len && j<t.len)
{
if(s.ch[i]==t.ch[j]) /*对应字符相同时，继续比较下一对字符*/
{
i++;j++;
}
else /*否则，主子串指针回溯重新开始下一次匹配*/
{
i=i-j+1;j=0;
}
}
if(j>=t.len)
k=i-t.len+1; /*求出第一个字符的位置*/
else
k=-1; /*置特殊值-1*/
return(k);
}
8．子串插入运算算法
将子串t插入到串s的第i个位置。
int InsStr(SqString &s,int i,SqString t)
{
int j;
if(i>s.len+1)
return(0); /*位置参数值错误*/
else
{
for (j=s.len;j>=i-1;j--) /*将s.ch[i-1]-s.ch[s.len-1]后移t.len个位置*/
s.ch[j+t.len]=s.ch[j];
for(j=0;j<t.len;j++)
s.ch[i+j-1]=t.ch[j];
s.len=s.len+t.len; /*修改s串长度*/
return(1);
}
}
9．子串删除运算算法
删除串s中从第i个位置开始的j个字符。
int DelStr(SqString &s,int i,int j)
{
int k;
if(i<1 || i>s.len || j<1 || i+j>s.len+1)
return(0); /*位置参数值错误*/
else
{
for (k=i+j-1;k<s.len;k++) /*将s的第i+j位置之后的字符前移j位*/
s.ch[k-j]=s.ch[k];
s.len=s.len-j; /*修改s的长度*/
return(1);
}
}
10．子串替换运算算法
将串s中所有出现的子串s1均替换成s2。
SqString RepStrAll(SqString s,SqString s1,SqString s2)
{
int i;
i=Index(s,s1);
while(i>=0)
{
DelStr(s,i,s1.len); /*删除*/
InsStr(s,i,s2); /*插入*/
i=Index(s,s1);
}
return(s);
}
11．输出串运算算法
显示串s的所有字符。
void DispStr(SqString s) /*输出串运算*/
{
int i;
for(i=0;i<s.len;i++)
printf("%c",s.ch[i]);
printf("\n");
}
当顺序串的基本运算设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会顺序串各种操作的实现过程。
void main()
{
SqString s1,s2,s3,s4,s5,s6,s7; /*定义多个顺序串*/
Assign(s1,"abcd"); /*将字符串abcd赋值给串s1*/
printf("s1:");DispStr(s1); /*显示串s1的所有字符*/
printf("s1的长度:%d\n",StrLength(s1)); /*返回串s1包含的字符个数*/
printf("s1=>s2\n");
StrCopy(s2,s1); /*将串s1赋给串s2*/
printf("s2:");DispStr(s2); /*显示串s2的所有字符*/
/*判断两个串s1和s2是否相同*/
printf("s1和s2%s\n",(StrEqual(s1,s2)==1?"相同":"不相同"));
Assign(s3,"12345678"); /*将字符串"12345678"赋值给串s3*/
printf("s3:");DispStr(s3); /*显示串s3的所有字符*/
printf("s1和s3连接=>s4\n");
s4=Concat(s1,s3); /*串s4是串s3连接到s1后所得的新串*/
printf("s4:");DispStr(s4); /*显示串s4的所有字符*/
printf("s3[2..5]=>s5\n");
s5=SubStr(s3,2,4); /*s3的一个子串赋给串s5*/
printf("s5:");DispStr(s5); /*显示串s5的所有字符*/
Assign(s6,"567"); /*将字符串"567"赋值给串s6*/
printf("s6:");DispStr(s6); /*显示串s6的所有字符*/
printf("s6在s3中位置:%d\n",Index(s3,s6)); /*返回串s6在串s3中的位置*/
printf("从s3中删除s3[3..6]字符\n");
DelStr(s3,3,4); /*删除串s3中从第3个位置开始的6个字符*/
printf("s3:");DispStr(s3); /*显示串s3的所有字符*/
printf("从s4中将s6替换成s1=>s7\n");
s7=RepStrAll(s4,s6,s1); /*将串s4中串s6替换成串s1，将新串赋给s7*/
printf("s7:");DispStr(s7); /*显示串s7的所有字符*/
}
上述程序的执行结果如下：
s1:abcd
s1的长度:4
s1=>s2
s2:abcd
s1和s2相同
s3:12345678
s1和s3连接=>s4
s4:abcd12345678
s3[2..5]=>s5
s5:2345
s6:567
s6在s3中位置:5
从s3中删除s3[3..6]字符
s3:1278
从s4中将s6替换成s1=>s7
s7:abcd1234abcd8
4.2.2 堆分配存储表示
堆分配存储表示的特点是：仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc()和free()来管理。利用函数malloc()为每个新产生的串分配一块实际串长所需的存储空间，若分配成功，则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结构的一部分。串的堆分配存储表示为：
typedef struct
{
char *ch; /*若是非空串，则按串长分配存储区，否则ch为NULL*/
int length; /*串长度*/
}HString;
这种存储结构表示时的串操作仍是基于“字符序列的复制”进行的。由于堆分配存储结构的串既有顺序存储结构的特点，处理方便，操作中对串长又没有任何限制，更显灵活，因此在串处理的应用程序中也常被选用。其基本操作的算法描述如下。
1．串赋值运算算法
Status StrAssign(HString &T, char *chars) /*生成一个其值等于串常量chars的串T*/
{
if(T.ch) free(T.ch); /*释放原有的串空间*/
int len;char *c;
for(len=0,c=chars;*c;++len,++c); /*求chars的长度i*/
if(!len)
{T.ch=NULL; T.length=0;
}
else{
if(!(T.ch=(char *) malloc(len*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<len;i++)
T.ch[i] = chars[i];
T.ch[i]='\0'; /*结尾加上\0*/
T.length=len;
}
return OK;
}
2．求串长运算算法
int StrLength(HString s)
{
return s.length; /*返回串长度*/
}
3．串比较运算算法
int StrCompare(HString s,HString t)
{
/*比较s,t，若s>t则返回值>0；若s=t则返回值=0；若s<t则返回值<0*/
for(int 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;
}
4．串清空运算算法
Status ClearString(HString &s) /*清空s*/
{
if(s.ch)
{
free(s.ch);
s.ch=NULL;
}
s.length =0;
return OK;
}
5．串连接运算算法
/*用t返回由s1和s2连接而成的新串*/
Status Concat(HString &t, HString s1, HString s2)
{
if(t.ch) free(t.ch);
if(!(t.ch=(char *)malloc((s1.length+s2.length)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s1.length;i++) t.ch[i]=s1.ch[i];
for(i=0;i<s2.length;i++) t.ch[i+s1.length]=s2.ch[i];
t.ch[s1.length+s2.length]='\0';
t.length=s1.length+s2.length;
return OK;
}
6．求子串运算算法
Status SubString(HString &sub, HString s, int pos, int len)
{
/*用sub返回串S的第pos个字符起长度为len的子串*/
if(pos<1 || pos>s.length || len<0 )
return ERROR;
/*如果所取长度超过实际长度，输出实际长度*/
if( len>s.length-pos+1 ) len=s.length-pos+1;
if(sub.ch) free(sub.ch);
if(!len){ sub.ch=NULL; sub.length=0; }
else{
if(!(sub.ch=(char *) malloc(len*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<len;i++)
sub.ch[i]=s.ch[pos+i-1];
sub.ch[i]='\0'; /*结尾加上\0*/
sub.length = len;
}
return OK;
}
7．串复制运算算法
Status StrCopy(HString &t,HString s)
{
if(!(t.ch=(char *)malloc((s.length)*sizeof(char))))
exit(OVERFLOW);
for(int i=0;i<s.length;i++)
t.ch[i]=s.ch[i];
t.ch[s.length]='\0';
t.length=s.length;
return OK;
}
4.2.3 串的链存储表示
串也可以采用链式存储结构，即用带头节点的单链表形式存储串，称为链串。链串中节点的类型定义如下：
typedef struct node
{
char data; /*存放字符*/
struct node *next; /*指针域*/
} LinkString;
其中data域用来存储组成字符串的字符，next域用来指向下一个节点。每个字符对应一个节点。如图4-2所示是链式串"abcd"的存储形式。
图4-2 链式串"abcd"的存储形式
链式串中串的基本运算算法如下。
1．串赋值运算算法
将一个C/C++字符数组t赋给串s。
void Assign(LinkString *&s,char t[])
{
int i=0;
LinkString *q,*tc;
s=(LinkString *)malloc(sizeof(LinkString)); /*建立头节点*/
s->next=NULL;
tc=s; /*tc指向s串的尾节点*/
while(t[i]!='\0')
{
q=(LinkString *)malloc(sizeof(LinkString));
q->data=t[i];
tc->next=q;tc=q;
i++;
}
tc->next=NULL; /*将尾节点的next置NULL*/
}
2．串复制运算算法
将一个串t赋给串s。
void StrCopy(LinkString *&s,LinkString *t) /*t=>s*/
{
LinkString *p=t->next,*q,*tc;
s=(LinkString *)malloc(sizeof(LinkString));/*建立头节点*/
s->next=NULL;
tc=s; /*tc指向s串的尾节点*/
while(p!=NULL) /*复制t的所有节点*/
{
q=(LinkString *)malloc(sizeof(LinkString));
q->data=p->data;
tc->next=q;tc=q;
p=p->next;
}
tc->next=NULL; /*将尾节点的next置NULL*/
}
3．求串长运算算法
返回串s的长度，即串中包含的字符个数。
int StrLength(LinkString *s)
{
int n=0;
LinkString *p=s->next;
while(p!=NULL) /*扫描串s的所有节点*/
{
n++;p=p->next;
}
return(n);
}
4．判断串相等运算算法
串相等是指两个串的长度及对应位置的字符完全相同。串s和串t相等时返回1；否则返回0。
int StrEqual(LinkString *s,LinkString *t)
{
LinkString *p=s->next,*q=t->next;
while(p!=NULL && q!=NULL) /*比较两串的当前节点*/
{
if(p->data!=q->data) /*data域不等时返回0*/
return(0);
p=p->next;q=q->next;
}
if(p!=NULL || q!=NULL) /*两串长度不等时返回0*/
return(0);
return(1);
}
5．串连接运算算法
将串t连接到串s之后，返回其结果。
LinkString *Concat(LinkString *s,LinkString *t)
{
LinkString *p=s->next,*q,*tc,*str;
str=(LinkString *)malloc(sizeof(LinkString)); /*建立头节点*/
str->next=NULL;
tc=str; /*tc总是指向新链表的尾节点*/
while(p!=NULL) /*将s串复制给str*/
{
q=(LinkString *)malloc(sizeof(LinkString));
q->data=p->data;
tc->next=q;tc=q;
p=p->next;
}
p=t->next;
while(p!=NULL) /*将t串复制给str*/
{
q=(LinkString *)malloc(sizeof(LinkString));
q->data=p->data;
tc->next=q;tc=q;
p=p->next;
}
tc->next=NULL;
return(str);
}
6．求子串运算算法
返回串s的第i个位置开始的j个字符组成的串。
LinkString *SubStr(LinkString *s,int i,int j)
{
int k=1;
LinkString *p=s->next,*q,*tc,*str;
str=(LinkString *)malloc(sizeof(LinkString)); /*建立头节点*/
str->next=NULL;
tc=str; /*tc总是指向新链表的尾节点*/
while (k<i && p!=NULL)
{
p=p->next;k++;
}
if (p!=NULL)
{
k=1;
while (k<=j && p!=NULL) /*复制j个节点*/
{
q=(LinkString *)malloc(sizeof(LinkString));
q->data=p->data;
tc->next=q;tc=q;
p=p->next;
k++;
}
tc->next=NULL;
}
return(str);
}
7．查找子串位置运算算法
返回子串t在主串s中的位置。
int Index(LinkString *s,LinkString *t)
{
LinkString *p=s->next,*p1,*q,*q1;
int i=0;
while(p!=NULL) /*循环扫描s的每个节点*/
{
q=t->next; /*子串总是从第一个字符开始比较*/
if (p->data==q->data) /*判定两串当前字符相等*/
{ /*若首字符相同，则判定串s中其后字符是否与t串的依次相同*/
p1=p->next;q1=q->next;
while(p1!=NULL && q1!=NULL && p1->data==q1->data)
{
p1=p1->next;
q1=q1->next;
}
if(q1==NULL) /*若都相同,则返回相同子串的起始位置*/
return(i);
}
p=p->next;i++;
}
return(-1); /*若不是子串,返回-1*/
}
8．子串插入运算算法
将子串t插入到串s的第i个位置。
int InsStr(LinkString *&s,int i,LinkString *t)
{
int k;
LinkString *q=s->next,*p,*str;
StrCopy(str,t); /*将t复制到str*/
p=str;str=str->next;
free(p); /*删除str的头节点*/
for(k=1;k<i;k++) /*在s中找到第i-1个节点，由p指向它，q指向下一个节点*/
{
if(q==NULL) /*位置参数i错误*/
return(0);
p=q;
q=q->next;
}
p->next=str; /*将str链表链接到*p之后*/
while(str->next!=NULL) /*由str指向尾节点*/
str=str->next;
str->next=q; /*将*q链接到*str之后*/
return(1);
}
9．子串删除运算算法
删除串s中从第i个位置开始的j个字符。
int DelStr(LinkString *&s,int i,int j)
{
int k;
LinkString *q=s->next,*p,*t;
for(k=1;k<i;k++) /*在s中找到第i-1个节点，由p指向它，q指向下一个节点*/
{
if (q==NULL) /*位置参数i错误*/
return(0);
p=q;
q=q->next;
}
for(k=1;k<=j;k++) /*删除*p之后的j个节点，并由q指向下一个节点*/
{
if (q==NULL) /*长度参数j错误*/
return(0);
t=q;
q=q->next;
free(t);
}
p->next=q;
return(1);
}
10．子串替换运算算法
将串s中出现的子串s1均替换成s2。
LinkString *RepStrAll(LinkString *s,LinkString *s1,LinkString *s2)
{
int i;
i=Index(s,s1);
while(i>=0)
{
DelStr(s,i+1,StrLength(s1)); /*删除串s1*/
InsStr(s,i+1,s2); /*插入串s2*/
i=Index(s,s1);
}
return(s);
}
11．输出串运算算法
显示串s的所有字符。
void DispStr(LinkString *s)
{
LinkString *p=s->next;
while (p!=NULL)
{ printf("%c",p->data);
p=p->next;
}
printf("\n");
}
当链串的基本运算设计好后，给出以下程序调用这些基本运算函数，读者可以对照程序执行结果进行分析，进一步体会链串各种操作的实现过程。
void main()
{
LinkString *s1,*s2,*s3,*s4,*s5,*s6,*s7;
Assign(s1,"abcd"); /*将字符串"abcd"赋给串s1*/
printf("s1:");DispStr(s1); /*显示串s1的所有字符*/
printf("s1的长度:%d\n",StrLength(s1)); /*返回串s1中包含的字符个数*/
printf("s1=>s2\n");
StrCopy(s2,s1); /*将串s1赋给串s2*/
printf("s2:");DispStr(s2); /*显示串s2的所有字符*/
/*判断串s1和s2是否相同*/
printf("s1和s2%s\n",(StrEqual(s1,s2)==1?"相同":"不相同"));
Assign(s3,"12345678"); /*将字符串"12345678"赋给串s3*/
printf("s3:");DispStr(s3); /*显示串s3的所有字符*/
printf("s1和s3连接=>s4\n");
s4=Concat(s1,s3); /*将串s3连接到串s1后赋给新串s4*/
printf("s4:");DispStr(s4); /*显示串s4的所有字符*/
printf("s3[2..5]=>s5\n");
s5=SubStr(s3,2,4); /*s5为串s3的第2个位置开始的4个字符组成的串*/
printf("s5:");DispStr(s5); /*显示串s5的所有字符*/
Assign(s6,"567"); /*将字符串"567"赋给串s6*/
printf("s6:");DispStr(s6); /*显示串s6的所有字符*/
printf("s6在s3中位置:%d\n",Index(s3,s6));/*返回子串s6在主串s3中的位置*/
printf("从s3中删除s3[3..6]字符\n");
DelStr(s3,3,4); /*删除串s3中从第3个位置开始的4个字符*/
printf("s3:");DispStr(s3); /*显示串s3的所有字符*/
printf("从s4中将s6替换成s1=>s7\n");
s7=RepStrAll(s4,s6,s1); /*将串s4中出现的子串s6均替换成s1，赋给串s7*/
printf("s7:");DispStr(s7); /*显示串s7的所有字符*/
}
上述程序执行结果与顺序串对应主程序的执行结果相同。