第四章串
第四章 串
串即字符串 ·是计算机非数值处理的主要对象之
• 串即字符串 • 是计算机非数值处理的主要对象之一
第一节串的类型定义 °串( string,或称字符串)是n个字符的有限 序列。通常记作 s=“a1a2…an"(n≥0) ·S是串的名 ·串中字符的数目n称为串的长度 含零个字符的串称为空串 null string) 由一个或多个空格组成的串称为空格串( blank string),用符号""表示"空格串
第一节 串的类型定义 • 串（string，或称字符串）是 n 个字符的有限 序列。通常记作 s = “a1 ,a2 … an " (n≥0) • S是串的名 • 串中字符的数目 n 称为串的长度 • 含零个字符的串称为空串(null string) • 由一个或多个空格组成的串称为空格串(blank string) ，用符号"Φ"表示"空格串"
串的抽象数据类型 ADT String i 数据对象:D={a1|a;∈ CharacterSet,i=1,2, n20} 数据关系:R1={|a1,a1∈D,i=2,,n} 基本操作 StrAssign(&T, chars 初始条件: chars是串常量。 操作结果:赋于串T的值为 chars。 StrCopy(&T, s 初始条件:串S存在 操作结果:由串S复制得串T
串的抽象数据类型 • ADT String { 数据对象：D＝{ ai | ai ∈CharacterSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ | ai-1 , ai ∈D, i=2,...,n } 基本操作： StrAssign (&T, chars) 初始条件：chars 是串常量。 操作结果：赋于串T的值为 chars。 StrCopy (&T, S) 初始条件：串 S 存在。 操作结果：由串 S 复制得串 T
Destroy String(&S) 初始条件:串S存在 操作结果:串S被销毁。 StrEmpty(s) 初始条件:串S存在。 操作结果:若S为空串,则返回TRUE, 否则返回 FALSE。 StrCompare(S, T) 初始条件:串S和T存在。 操作结果:若S>T,则返回值>0;若S=T, 则返回值=0;若S<T,则返回值<0
• DestroyString (&S) 初始条件：串 S 存在。 操作结果：串 S 被销毁。 StrEmpty (S) 初始条件：串 S 存在。 操作结果：若 S 为空串，则返回 TRUE， 否则返回 FALSE。 StrCompare (S, T) 初始条件：串 S 和 T 存在。 操作结果：若S>T，则返回值>0；若S=T， 则返回值=0；若S<T，则返回值<0
StrEngth(S) 初始条件:串S存在。 操作结果:返回串S序列中的字符 个数,即串的长度。 ClearString(&S 初始条件:串S存在。 操作结果:将S清为空串。 Concat( &T, S1, S2) 初始条件:串S1和S2存在。 操作结果:用T返回由S1和S2联 接而成的新串
• StrLength (S) 初始条件：串 S 存在。 操作结果：返回串 S 序列中的字符 个数，即串的长度。 ClearString (&S) 初始条件：串 S 存在。 操作结果：将 S 清为空串。 Concat (&T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联 接而成的新串
SubString(&Sub, S, pos, len) 初始条件:串S存在 1pos≤ StrEngth(s)且 oslensStrLength (s)-pos+1 操作结果:用Sub返回申S的第 pos个字符起长度为|en的子串。 Index(S, T, pos) 初始条件:串S和T存在,T是非空 串,1pos≤ StrEngth(S)。 操作结果:若主串S中存在和串T值 相同的子串,则返回它在主串S中第pos个 字符之后第一次出现的位置;否则函数值 为0
• 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相等的不重叠的子串。 StrlInsert ( &S, pos, T) 初始条件:串S和T存在, 1spossStrLength(s)+1 操作结果:在串S的第pos个字符 之前插入串T
• 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存在, 1spossStrLength(s)-len+1 操作结果:从串S中删除第pos个 字符起长度为len的子串。 3 ADT String °串赋值 StrAssign、串复制Strc。py、串比 较 StrCompare、求串长 StrEngth、串联 接 Concat以及求子串 SubString等6种操作 构成串类型的最小操作子集
• StrDelete (&S, pos, len) 初始条件：串 S 存在， 1≤pos≤StrLength(S)-len+1。 操作结果：从串 S 中删除第 pos 个 字符起长度为 len 的子串。 } ADT String • 串赋值StrAssign、串复制StrCopy、串比 较StrCompare、求串长StrLength、串联 接Concat以及求子串SubString等6种操作 构成串类型的最小操作子集
例如,可利用判等、求串长和求子串等操作实现串的定位 函数ndex(S,T,pos)和串的置换操作 Replace(S,T,v)。 int Index ( string s, String t, int pos) if(pos>0t n= StrEngth(S);m= StrEngth(T);∥求得串长 while(i<=n-m+1)i SubString(sub,S,,m);∥取得从第i个字符 起长度为m的子串 if (StrCompare sub, T)l=0)++ else return i ∥找到和T相等的子串 return 0, ∥s中不存在满足条件的子串
例如，可利用判等、求串长和求子串等操作实现串的定位 函数 Index(S,T,pos) 和串的置换操作 Replace(S,T,V)。 • int Index (String S, String T, int pos) { if (pos > 0) { n = StrLength(S); m = StrLength(T); // 求得串长 i = pos; while ( i <= n-m+1) { SubString (sub, S, i, m); // 取得从第 i 个字符 起长度为 m 的子串 if (StrCompare(sub,T) != 0) ++i ; else return i ; // 找到和 T 相等的子串 } } return 0; // S 中不存在满足条件的子串 }