敦黎 串、数组和广义表 程序设计—数据结构 基本概念及应用 ClearString(&S) 初始条件：串S已存在 操作结果：将串S清为空串 Concat(&T,S1,S2) 初始条件：串S1和S2存在 操作结果：用T返回由S1和S2联接而成的新串 SubString(&Sub,S,pos,len) 初始条件：串S存在，l≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+l 操作结果：用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≤StrLength(S)+1 操作结果：在串S的第pOs个字符之前插入串T StrDelete(&S,pos,len) 初始条件：串S存在，1≤pos≤StrLength(S)-len+l 操作结果：从串S中删除第pos个字符起长度为len的子串 DestroyString(&S)) 初始条件：串$存在 操作结果：串S被销毁 ADT String 5、串的基本操作 1)赋值操作 StrAssign(&T,chars) 2)比较函数 StrCompare(T,S) 3)求串长函数StrLength(S) 4)联接函数 Concat(&T,S1,S2) 5)求子串函数SubString(&Sub,S,pos,len) 其他操作可在此最小操作集上实现。 6、定位函数ndex(S,T,pos)的实现 利用求串长函数、求子串函数和比较函数。 参数：S主串，T子串，pos查找的起始位置 返回值：T在S中第pos个字符后第一次出现的位置 步骤： I)pos的合法性判断： if pos<=0)return 0; 2)n=StrLength(S);m=StrLength(T); 3)for (i=pos,i<=n-m+1;i+){ SubString(sub,S,i,m) if (StrCompare(sub,T)==0)return i; 4)return0;/体未找到*/ 文档编号 完成时间 完成人张昱 修改时间 第3页程序设计——数据结构 串、数组和广义表 基本概念及应用 文档编号 文 档 编号 完 成 人 完 成 人 张 昱 张 昱 完成时间 完 成 时间 修改时间 修 改 时间 第 3 页 第 3 页 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 ≤ StrLength(S)+1 操作结果：在串 S 的第 pos 个字符之前插入串 T StrDelete(&S, pos, len) 初始条件：串 S 存在，1 ≤ pos ≤ StrLength(S)-len+1 操作结果：从串 S 中删除第 pos 个字符起长度为 len 的子串 DestroyString(&S)) 初始条件：串 S 存在 操作结果：串 S 被销毁 }ADT String 5、串的基本操作 1) 赋值操作 StrAssign(&T, chars) 2) 比较函数 StrCompare(T, S) 3) 求串长函数 StrLength(S) 4) 联接函数 Concat(&T, S1, S2) 5) 求子串函数 SubString(&Sub, S, pos, len) 其他操作可在此最小操作集上实现。 6、定位函数 Index(S, T, pos)的实现 利用求串长函数、求子串函数和比较函数。 参数：S 主串, T 子串, pos 查找的起始位置 返回值：T 在 S 中第 pos 个字符后第一次出现的位置 步骤： 1) pos 的合法性判断： if ( pos<=0 ) return 0; 2) n=StrLength(S); m=StrLength(T); 3) for ( i = pos; i <=n-m+1; i ++ ){ SubString(sub, S, i, m) if ( StrCompare(sub, T)==0) return i; } 4) return 0; /* 未找到 */