哈工大数据结构4技术总结.ppt
文本预览下载声明
第4章 串;4.1 串类型的定义;1. 串的定义及术语;串的术语:;模式匹配:
子串的定位运算称为串的模式匹配,是一种求子串的第一个字符在主串中序号的运算。被匹配的主串称为目标串,子串称为模式。 ;2.串的输入与输出 ;gets( ) 函数:
格式为:gets(字符数组名); ;字符串输出: :;puts () 函数
格式为:puts (字符数组名);;3.串的抽象数据类型定义;ADT String {; 基本操作:; StrCompare( S,T )初始条件: 串 S 和 T 存在。操作结果: 若 S ? T,则返回值 ? 0 ; 若 S ? T,则返回值 ? 0 ; 若 S ? T,则返回值 ? 0 。; Concat(T,S1,S2)初始条件:串 S1 和 S2 存在。操作结果:用 T 返回由 S1 和 S2 联接而成的新串。; Replace(S,T,V)
初始条件:串S, T和 V 均已存在, 且 T 是非空串。操作结果:用 V 替换主串 S 中出??的所有与(模式串)T
相等的子串。; ;例: Concat( T, ?man?, ?kind?)
求得 T = ?mankind?;SubString(sub, ?commander?, 4, 7)
sub = ?
SubString(sub, ?beijing?, 7, 2) = ?
sub = ?
起始位置和子串长度之间存在约束关系
SubString(?student?, 5, 0) = ??
长度为 0 的子串为合法串;;;; 上述抽象数据类型定义的 13 种操作中:
串赋值 StrAssign
串复制 Strcopy
串比较 StrCompare
求串长 StrLength
串联接 Concat
求子串 SubString
等六种操作构成串类型的最小操作子集。
即:这些操作不可能利用其他串操作来实现,反之,其他串操作(除串清除 ClearString 和串销毁 DestroyString 外)可在这个最小操作子集上实现。; 例:可利用串比较、求串长和求子串等操作实现定位函数:
Index( S,T,pos ) ;int Index (String S, String T, int pos)
{ // T为非空串。
若主串S中第pos个字符之后存在与T 相等的子串,
则返回第一个这样的子串在S中的位置,否则返回 0
if ( pos 0 )
{ n = StrLength( S ) ; // n 为主串S的长度
m = StrLength( T ); // m 为被匹配的串T的长度
i = pos; // 从第 i 个字符起 ( i的初值为 pos )
while ( i = n-m+1) // 取到n-m+1,剩余的字符已不够子串T长度就不检验
{ SubString (sub, S, i, m); // 在主串S中从第i个位置起取长度为m的子串
给sub
if (StrCompare(sub,T) != 0) // 所取子串 sub与T比较,若不相等
++i ;
else
return i ;
}
}
return 0; // S 中不存在与 T 相等的子串
};4.2 串的表示和实现; 在程序设计语言中,串只是作为输入或输出的常量出现,则只需存储此串的串值,即字符序列即可。
但在多数非数值处理的程序中,串以变量的形式出现。;1.定长顺序存储表示; 字符在计算机中以其ASCII码方式表示,其长度为1个字节。
有符号字符型数取值范围为 -12
显示全部