chapter 4.ppt

第四章 串 主要内容 1、串的定义 举例 设有四个串，S1=’BEI’, S2=’JING’, S3 =’BEIJING’, S4=’BEI JING’ S1的串值为 ，长度为 。 S1, S2均是S3, S4的子串 S1在S3, S4的位置相同 S2在S3, S4的位置相同 串的抽象数据类型定义 StrEmpty (S)初始条件：串S存在。操作结果：若 S 为空串，则返回TRUE， 否则返回 FALSE。 ?? 表示空串，空串的长度为零。 Concat (T, S1, S2) 初始条件：串 S1 和 S2 存在。 操作结果：用 T 返回由 S1 和 S2 联接而成的新串。 例如： Concat( T, ?Good?, ?bye?) 求得 T = ?Goodbye? SubString (Sub, S, pos, len) 初始条件： 串 S 存在，1≤pos≤StrLength(S) 且0≤len≤StrLength(S)-pos+1。 操作结果： 用 Sub 返回串 S 的第 pos 个字符起 长度为 len 的子串。 子串为“串” 中的一个字符子序列 例如： SubString( sub, ?commander?, 4, 3) 求得 sub = ?man? ； SubString( sub, ?commander?, 1, 9) 求得 sub = ?commander?； SubString( sub, ?commander?, 9, 1) 求得 sub = ?r?； SubString(sub, ?commander?, 4, 7) sub = ? SubString(sub, ?beijing?, 7, 2) = ? sub = ? 起始位置和子串长度之间存在约束关系 SubString(sub, ?student?, 5, 0) = ?? 长度为 0 的子串为“合法”串 Index (S, T, pos)初始条件：串S和T存在，T是非空串， 1≤pos≤StrLength(S)。操作结果： 若主串 S 中存在和串 T 值相同 的子串, 则返回它在主串 S 中第pos个 字符之后第一次出现的位置； 否则函数值为0。 “子串在主串中的位置”意指子串中的第一个字符在主串中的位序。 例如：假设 S = ?abcaabcaaabc?, T = ?bca? 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的子串。 对于串的基本操作集可以有不同的定义方法，在使用高级程序设计语言中的串类型时，应以该语言的参考手册为准。 例如：C语言函数库中提供下列串处理函数： 串与线性表的共同点和区别 串的数据对象约束为字符集 串的基本操作和线性表不同,以串的整体作为操作的对象,而线性表大多以单个元素作为操作对象(如查找,插入等操作) 共同点：串的逻辑结构与线性表相似 2、串的表示和实现 2.1 定长顺序存储表示 2.2 堆分配存储表示 2.3 块链存储表示 2.1 定长顺序存储表示 用C语言实现串的定长存储结构： #define MAXSTRLEN 255 // 用户可在255以内定义最大串长 typedef unsigned char SString[MAXSTRLEN +