本文共 2927 字,大约阅读时间需要 9 分钟。
串(string)(或者字符串)是由零个或多个字符组成的有限序列,一般记为
s=‘a1a2…an’ (n>=0) 其中,s是串的名,用单引号括起来的字符序列是串的值;ai(1<=i<=n)可以是字母、数字或者其他字符;串中字符的数目n称为串的长度。零个字符的串称为空串,它的长度为零。 串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常称子串在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串的位置来表示。 称两个串是相等的,当且仅当这两个串的值相等。也就是说,只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等。 值得一提的是,串值必须用一对单引号括起来,但单引号本身不属于串,它的作用只是为了避免与变量名或数的常量混淆而已。串的抽象数据类型的定义如下:
ADT String{ 数据对象:D = { ai | ai ∈ CharacterSet, i = 1,2,...,n,n>=0 } 数据关系:R1 = { < a(i-1), ai> | a(i-1), ai ∈ D, i = 2,...,n } 基本操作: StrAssign (&T, chars) 初始条件:chars 是字符串常量。 操作如果:生成一个其值等于chars的串T。 StrCopy(&T,S) 初始条件:串S存在。 操作结果:由串S复制得串T。 StrEmpty(S) 初始条件:串S存在。 操作结果:若S为空串,则返回TRUE,否则返回FALSE。 StrCompare(S,T) 初始条件:串S和T存在。 操作结果:若S>T,则返回值>0;若S=T,则返回值=0;若S<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。 操作结果:用 Sub 返回串S的第pos个字符起长度为len的子串。 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<=SreLength(S) - len + 1。 操作结果:在串S的第pos个字符之前插入串T。 StrDelete(&S, pos, len) 初始条件:串S存在,1<=pos<=StrLength(S) - len + 1。 操作结果:从串S中删除第pos个字符起长度为len的子串。 DestroyString(&S) 初始条件:串S存在。 操作结果:串S被销毁。} ADT String
// ======== ADT String 的表示与实现 ======// -------- 串的堆分配存储表示 --------typedef struct { char * ch; // 若是非空串,则按串长分配存储区,否则ch为NULL int length; // 串长度} HString;// -------- 基本操作的函数原型说明 --------Status StrAssign(HString &T, char * chars); // 生成一个其值等于串常量 chars 的串Tint StrLength(HString S); // 返回S的元素个数,称为串的长度。int StrCompare(HString S, HString T) // 若S>T,则返回值>0,若S=T,则返回值=0,若S<0Status ClearString(HString &S) // 将S清为空串,并释放S所占空间。Status Concat(HString &T, HString S1, HString S2); // 用T返回由S1和S2联接而成的新串。HString SubString(HString S, int pos, int len); // 1<=pos<=StrLength(S) 且 0<=len<=StrLength(S) - pos + 1。 // 返回串S的第pos个字符起长度为len的子串。 // ------ 基本操作的算法描述 ------Status StrAssign(HString &T, char * chars) { // 生成一个其值等于串常量chars的串T if(T.ch) free(T.ch); // 释放T原有空间 for (i=0, c=chars; *c; ++i, ++c); // 求chars的长度i if (!i) { T.ch = NULL; T.Length = 0; } else { if (! (T,ch = (char *) malloc(i* sizeof(char)))) exit (OVERFLOW); T.ch[0..i-1]=chars[0..i-1]; T.length = i; } return OK;} // StrAssignint StrLength(HString S) { // 返回S的元素个数,称为串的长度。 return S.length;} // StrLengthint StrCompare(HString S, HString T){ // 若S>T,则返回值>0,若S=T,则返回值=0,若S <0 for (i=0,;i 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)); Sub.ch[0..len-1] = S.ch[pos-1..pos+len-2]; Sub.length = len; } return OK;} // SubString
转载地址:http://atvrn.baihongyu.com/