哈工大数据结构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