字符串串
字符串是非数值处理的基本对象
应用领域
– 信息检索系统
– 文字编辑程序
– 语言翻译系统
– … …
问题
– 如何有效地组织和存储字符串，并提供必要的操作
C语言中的字符串函数
头文件
– #include,string.h”
函数包括
– char * strcat(char *str1,char *str2);
– char * strchr(char *str,int ch);
//找出串 str中第一次出现字符 ch的位置
– int strcmp(char *str1,char *str2);
– char *strcpy(char *str1,char *str2);
– unsigned int strlen(char *str);
– Char * strstr(char *str1,char *str2);
//找出串 str2在串 str1中第一次出现的位置串的抽象类型定义
ADT String {
D = {ai | ai CharacterSet,i = 1,2,…n }
R = {<ai-1,ai> | ai-1,ai D,i = 2,…n}
P:
StrAssign(&T,chars) //串赋值,chars为一字符串常量
StrCopy(&T,S) //串拷贝
StrEmpty(S) //是否空串
StrCompare(S,T) //串比较，分 S>T情形,S=T情形和 S<T情形
StrLength(S) //取串长
ClearString(&S) //将串清空
Concat(&T,S1,S2) //两串联接
SubString(&Sub,S,pos,len) //从串 S中取出从 pos个位置起长为 len的子串
Index(S,T,pos) //若串 S中存在和 T相同的字串，返回起始位置
Replace(&S,T,V) //串替换，用 V替换 S中出现的所有字串 T
StrInsert(&S,pos,T) //在串 S的第 pos个字符前插入串 T
StrDelete(&S,pos,len) //从串 S中删除第 pos个字符起长度为 len的子串
DestroyString(&S) //销毁串 S
}ADT String
串的表示和实现
选用不同的存储结构，串操作的实现也各不相同，可选用的串的存储结构包括：
– 串的 定长顺序 存储表示
– 串的 堆分配 存储表示
– 串的 块链 存储表示串的表示和实现
串的定长顺序存储表示
– 按照预定义大小，为每个定义的串变量分配一个固定长度的存储区 (可用定长数组来描述 )
– 当串的实际长度超过预定义长度时，字符串将被截断
– 串操作均基于“字符序列的复制”
typedef struct
{ char data[MAXSIZE];
int curlen;
} SeqString;
定义一个串变量,SeqString s;
S
0 1 2 3 MAXSIZE
3 S U N
1,串联接,把两个串 s1和 s2首尾连接成一个新串 s,即,s<=s1+s2。
/*设串结束用 ‘ \0’ 来标识。 */
int StrConcat1(SeqString s1,SeqString s2,SeqString s)
char s1[],s2[],s[];
{ int i=0,j,len1,len2;
len1= StrLength(s1); len2= StrLength(s2)
if (len1+ len2>MAXSIZE-1) return 0 ; /* s长度不够 */
j=0;
while(s1[j]!=’\0’) { s[i]=s1[j];i++; j++; }
j=0;
while(s2[j]!=’\0’) { s[i]=s2[j];i++; j++; }
s[i]=’\0’; return 1;
}
O(n)
２,求子串
int StrSub (char *t,char *s,int i,int len)
/* 用 t返回串 s中第个 i字符开始的长度为 len
的子串 1≤i≤串长 */
{ int slen;
slen=StrLength(s);
if ( i<1 || i>slen || len<0 || len>slen-i+1)
{ printf(＂ 参数不对＂ ); return 0; }
for (j=0; j<len; j++)
t[j]=s[i+j-1];
t[j]=’\0’;
return 1;}
S
0
len
pos MAXSIZE
3
0
lenT
MAXSIZE
O(n)
串的表示和实现
串的堆分配存储表示
– 堆：一个自由存储区,C中用 malloc()和 free()来管理
– 该方法仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间在程序执行过程中动态分配而得
– 串操作仍基于“字符序列的复制”
typedef struct
{ int length; /*串长 */
int stradr; /*起始地址 */
} HString;
HString T,S;
T
0 1 2 3
S U Nstradr
length
设堆空间为：
char store[SMAX+1];
自由区指针,int free;
串的存储映象类型如右,
1,串常量赋值
void StrAssign(HString *s1,char *s2)
/*将一个字符型数组 s2中的字符串送入堆 store中,free是自由区的指针 */
{ int i=0,len;
len=StrLength(s2);
if (len<0||free+len-1＞ SMAX)
return 0;
else {for (i=0;i<len;i++)
store[frre+i] =s2[i];
s1.stradr=free;
s1.len.=len;
free=free+len;
}
}
2,赋值一个串
void StrCopy(Hstring *s1,Hstring s2)
/*该运算将堆 store中的一个串 s2复制到一个新串 s1中 */
{ int i;
if (free+s2.lengt-1>SMAX) return error ;
else { for(i=0; i<s2.length;i++)
store[free+i]=store[s2.atradr+i];
s1->length=s2.length;
s1->stradr=free;
free=free+s2.length;
}
}
3,求子串
void StrSub(Hstring *t,Hstring s,int i,int len)
/*该运算将串 s中第 i个字符开始的长度为 len 的子串送到一个新串 t中 */
{ int i;
if (i<0 || len<0 || len>s.len-i+1) return error ;
else { t->length=len;
t->stradr=s.stradr+i-1;
}
}
字符串是非数值处理的基本对象
应用领域
– 信息检索系统
– 文字编辑程序
– 语言翻译系统
– … …
问题
– 如何有效地组织和存储字符串，并提供必要的操作
C语言中的字符串函数
头文件
– #include,string.h”
函数包括
– char * strcat(char *str1,char *str2);
– char * strchr(char *str,int ch);
//找出串 str中第一次出现字符 ch的位置
– int strcmp(char *str1,char *str2);
– char *strcpy(char *str1,char *str2);
– unsigned int strlen(char *str);
– Char * strstr(char *str1,char *str2);
//找出串 str2在串 str1中第一次出现的位置串的抽象类型定义
ADT String {
D = {ai | ai CharacterSet,i = 1,2,…n }
R = {<ai-1,ai> | ai-1,ai D,i = 2,…n}
P:
StrAssign(&T,chars) //串赋值,chars为一字符串常量
StrCopy(&T,S) //串拷贝
StrEmpty(S) //是否空串
StrCompare(S,T) //串比较，分 S>T情形,S=T情形和 S<T情形
StrLength(S) //取串长
ClearString(&S) //将串清空
Concat(&T,S1,S2) //两串联接
SubString(&Sub,S,pos,len) //从串 S中取出从 pos个位置起长为 len的子串
Index(S,T,pos) //若串 S中存在和 T相同的字串，返回起始位置
Replace(&S,T,V) //串替换，用 V替换 S中出现的所有字串 T
StrInsert(&S,pos,T) //在串 S的第 pos个字符前插入串 T
StrDelete(&S,pos,len) //从串 S中删除第 pos个字符起长度为 len的子串
DestroyString(&S) //销毁串 S
}ADT String
串的表示和实现
选用不同的存储结构，串操作的实现也各不相同，可选用的串的存储结构包括：
– 串的 定长顺序 存储表示
– 串的 堆分配 存储表示
– 串的 块链 存储表示串的表示和实现
串的定长顺序存储表示
– 按照预定义大小，为每个定义的串变量分配一个固定长度的存储区 (可用定长数组来描述 )
– 当串的实际长度超过预定义长度时，字符串将被截断
– 串操作均基于“字符序列的复制”
typedef struct
{ char data[MAXSIZE];
int curlen;
} SeqString;
定义一个串变量,SeqString s;
S
0 1 2 3 MAXSIZE
3 S U N
1,串联接,把两个串 s1和 s2首尾连接成一个新串 s,即,s<=s1+s2。
/*设串结束用 ‘ \0’ 来标识。 */
int StrConcat1(SeqString s1,SeqString s2,SeqString s)
char s1[],s2[],s[];
{ int i=0,j,len1,len2;
len1= StrLength(s1); len2= StrLength(s2)
if (len1+ len2>MAXSIZE-1) return 0 ; /* s长度不够 */
j=0;
while(s1[j]!=’\0’) { s[i]=s1[j];i++; j++; }
j=0;
while(s2[j]!=’\0’) { s[i]=s2[j];i++; j++; }
s[i]=’\0’; return 1;
}
O(n)
２,求子串
int StrSub (char *t,char *s,int i,int len)
/* 用 t返回串 s中第个 i字符开始的长度为 len
的子串 1≤i≤串长 */
{ int slen;
slen=StrLength(s);
if ( i<1 || i>slen || len<0 || len>slen-i+1)
{ printf(＂ 参数不对＂ ); return 0; }
for (j=0; j<len; j++)
t[j]=s[i+j-1];
t[j]=’\0’;
return 1;}
S
0
len
pos MAXSIZE
3
0
lenT
MAXSIZE
O(n)
串的表示和实现
串的堆分配存储表示
– 堆：一个自由存储区,C中用 malloc()和 free()来管理
– 该方法仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间在程序执行过程中动态分配而得
– 串操作仍基于“字符序列的复制”
typedef struct
{ int length; /*串长 */
int stradr; /*起始地址 */
} HString;
HString T,S;
T
0 1 2 3
S U Nstradr
length
设堆空间为：
char store[SMAX+1];
自由区指针,int free;
串的存储映象类型如右,
1,串常量赋值
void StrAssign(HString *s1,char *s2)
/*将一个字符型数组 s2中的字符串送入堆 store中,free是自由区的指针 */
{ int i=0,len;
len=StrLength(s2);
if (len<0||free+len-1＞ SMAX)
return 0;
else {for (i=0;i<len;i++)
store[frre+i] =s2[i];
s1.stradr=free;
s1.len.=len;
free=free+len;
}
}
2,赋值一个串
void StrCopy(Hstring *s1,Hstring s2)
/*该运算将堆 store中的一个串 s2复制到一个新串 s1中 */
{ int i;
if (free+s2.lengt-1>SMAX) return error ;
else { for(i=0; i<s2.length;i++)
store[free+i]=store[s2.atradr+i];
s1->length=s2.length;
s1->stradr=free;
free=free+s2.length;
}
}
3,求子串
void StrSub(Hstring *t,Hstring s,int i,int len)
/*该运算将串 s中第 i个字符开始的长度为 len 的子串送到一个新串 t中 */
{ int i;
if (i<0 || len<0 || len>s.len-i+1) return error ;
else { t->length=len;
t->stradr=s.stradr+i-1;
}
}
