基本概念
串(String)是由零个或多个字符组成的有限序列。它是线性表的特殊形式,其数据元素被限制为字符集。
抽象数据类型(ADT)
串的数据对象约束为字符集,数据关系与线性表类似:除第一个和最后一个元素外,其余元素有且仅有一个直接前驱和直接后驱。
主要基本操作包括:
StrAssign(*T, chars):生成一个值等于 chars 的串 T。StrCopy(*T, S):由串 S 复制得到串 T。StrEmpty(S):若串 S 为空串返回 TRUE,否则返回 FALSE。StrCompare(S, T):比较大小,S>T 返回 1,S=T 返回 0,S<T 返回 -1。StrLength(S):返回串 S 的元素个数。ClearString(*S):清空串 S。Contact(*T, S1, S2):用 T 返回由 S1 和 S2 联接而成的新串。SubString(Sub, S, pos, len):获取 S 中从第 pos 个字符起长度为 len 的子串。Index(S, T, pos):查找主串 S 中是否存在与 T 相同的子串,返回位置或 0。Replace(*S, T, V):用 V 替换 S 中所有与 T 相等的不重叠子串。StrInsert(*S, pos, T):在 S 的第 pos 个字符之前插入串 T。StrDelete(*S, pos, len):删除 S 中从第 pos 个字符起长度为 len 的子串。
顺序存储
串的顺序存储方式通常有两种:定长数组和堆分配存储。前者因数组长度固定,容易出现溢出问题;后者通过动态内存管理更为灵活。这里重点介绍基于堆分配的存储实现。
我们定义一个结构体 HString,包含指向存储基地址的指针 ch 和记录长度的 length。为了安全起见,申请空间时会多预留一个字节用于存放结束符 \0。
#include <stdlib.h>
#include <stdio.h>
#define ERROR 0
#define OK 1
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100
typedef struct {
char* ch; // 串的存储基地址
int length; // 串的长度
} HString;
// 新建串
{
i = ;
* c = chars;
(T->ch) (T->ch);
(*c) {
c++;
i++;
}
T->length = i;
(i == ) {
T->ch = ;
} {
(!(T->ch = (*)(()*(i+)))) ERROR;
(i = ; i < T->length; i++) {
T->ch[i] = chars[i];
}
T->ch[i] = ;
}
OK;
}
{
i = , j;
* c = S;
(*c) {
c++;
i++;
}
(T->ch) (T->ch);
(!(T->ch = (*)(()*i + ))) ERROR;
(j = ; j < i; j++) {
T->ch[j] = S[j];
}
T->length = i;
T->ch[j] = ;
OK;
}
{
(S.length == ) TRUE;
FALSE;
}
{
S.length;
}
{
(S->ch) {
(S->ch);
S->ch = ;
}
S->length = ;
OK;
}
{
i;
(i = ; i < S.length && i < T.length; i++) {
(S.ch[i] > T.ch[i]) ;
(S.ch[i] < T.ch[i]) ;
}
(S.length > T.length) ;
(S.length < T.length) ;
;
}
{
i, j;
(T->ch) (T->ch);
(!(T->ch = (*)(()*(S1.length + S2.length + )))) ERROR;
(i = ; i < S1.length; i++) T->ch[i] = S1.ch[i];
(j = ; j < S2.length; j++) T->ch[i+j] = S2.ch[j];
T->ch[i+j] = ;
T->length = S1.length + S2.length;
OK;
}
{
i;
(pos < || pos > S.length || len < || len > (S.length - pos + )) ERROR;
(Sub->ch) (Sub->ch);
(!(Sub->ch = (*)(()*(len+)))) ERROR;
(i = ; i < len; i++) {
Sub->ch[i] = S.ch[pos+i];
}
Sub->ch[i] = ;
Sub->length = len;
OK;
}
{
i, j;
(pos < || pos > S.length || T.length == ) ERROR;
(T.length > S.length) FALSE;
j = pos;
{
(i = ; i < T.length; i++) {
(S.ch[j+i] != T.ch[i]) {
j++;
;
}
}
} (i < T.length && j < S.length);
(i >= T.length) j - pos + ;
FALSE;
}
{
i, j = ;
HString s, Sub, str, S1;
s.ch = ; Sub.ch = ; str.ch = ; S1.ch = ;
s.length = ; Sub.length = ; str.length = ; S1.length = ;
(S->length == || T.length == ) ERROR;
i = Index(*S, T, j);
(i == ) FALSE;
(i != ) {
SubString(&Sub, *S, j, i - );
Contact(&s, Sub, V);
Contact(&str, S1, s);
StrCopy(&S1, str.ch);
j += i + T.length - ;
i = Index(*S, T, j);
}
(j <= S->length) {
SubString(&Sub, *S, j, S->length - j + );
Contact(&str, S1, Sub);
StrCopy(&S1, str.ch);
}
*S = S1;
OK;
}
{
HString Sub1, S1, Sub2;
Sub1.ch = ; S1.ch = ; Sub2.ch = ;
Sub1.length = ; S1.length = ; Sub2.length = ;
(pos < || pos > S->length + || T.length == ) ERROR;
SubString(&Sub1, *S, , pos - );
Contact(&S1, Sub1, T);
SubString(&Sub2, *S, pos, S->length - pos + );
Contact(S, S1, Sub2);
OK;
}
{
HString Sub1, Sub2;
Sub1.ch = ; Sub2.ch = ;
Sub1.length = ; Sub2.length = ;
(pos < || pos > S->length || len > S->length - pos + ) ERROR;
SubString(&Sub1, *S, , pos - );
SubString(&Sub2, *S, pos + len, S->length - pos - len + );
Contact(S, Sub1, Sub2);
OK;
}
{
HString S, T, Sub, V, S1, S2;
S.ch = ; T.ch = ; Sub.ch = ; V.ch = ; S1.ch = ; S2.ch = ;
s[MAXSIZE];
pos, choice, len;
{
();
(, &choice);
(choice) {
: { (, StrLength(S)); ; }
: {
(); (, &pos);
(); (, s);
StrAssign(&T, s); StrInsert(&S, pos, T);
(, S.ch); ;
}
: {
(); (, &pos);
(); (, &len);
StrDelete(S, pos, len); (, S.ch); ;
}
: {
(); (, &pos);
(); (, &len);
SubString(&Sub, S, pos, len); (, Sub.ch); ;
}
: { ClearString(&S); (, S.ch); ; }
: {
(); (, s);
StrAssign(&S, s); (, S.ch); ;
}
: {
(); (, &pos);
(); (, s);
StrAssign(&T, s); (, Index(S, T, pos)); ;
}
: { (, StrEmpty(S)); ; }
: {
(); (, s); StrAssign(&T, s);
(); (, s); StrAssign(&V, s);
Replace(&S, T, V); (, S.ch); ;
}
: {
(); (, s); StrAssign(&S1, s);
(); (, s); StrAssign(&S2, s);
Contact(&T, S1, S2); (, T.ch); ;
}
: {
(); (, s); StrAssign(&S1, s);
(); (, s); StrAssign(&S2, s);
(, StrCompare(S1, S2)); ;
}
: {
(); (, s);
StrCopy(&S, s); (, S.ch); ;
}
}
} (choice != );
;
}

