数据结构第4章 串.ppt

【课前思考】 1. “串就是线性表”的结论是否正确? 2. 串和线性表的主要差别是什么? 第四章串串:即字符串,是计算机非数值处理的主要对象之一。早期:输入和输出的常量。后来:编程语言增加了串类型,对“串变量”进行操作。现今:硬件结构没提供对串操作的指令,用软件实现。第四章串 串的类型定义 串( string ,或称字符串) 是 n 个字符的有限序列。通常记作 s = ‘ a1a2 … an ’(n≥ 0) 空串(null string) :含零个字符的串, n=0 。空格串(blank string) :由一个或多个空格组成的串。如 s= “”, n=5 ,长度为串中空格字符的个数。串名串值串长串的抽象数据类型定义如下: ADT String { 数据对象: D= {ai|ai ∈ CharacterSet, i=1,2,...,n, n ≥ 0 } 数据关系: R1 = { <ai-1 ,ai> |ai-1 ,ai ∈ D, i=2,...,n } 基本操作: StrAssign (&T, chars) 初始条件: chars 是串常量。 操作结果:赋于串 T的值为 chars 。 StrCopy (&T, S) 初始条件:串 S 存在。 操作结果:由串 S 复制得串 T。 DestroyString (&S) 初始条件:串 S 存在。 操作结果:串 S 被销毁。 StrEmpty (S) 初始条件:串 S 存在。 操作结果:若 S 为空串,则返回 TRUE , 否则返回 FALSE 。 pare (S, T) 初始条件:串 S 和 T 存在。 操作结果:若 S>T ,则返回值>0 ; 若 S=T ,则返回值=0 ; 若 S<T ,则返回值<0 。 StrLength (S) 初始条件:串 S 存在。 操作结果:返回串 S 序列中的字符个数,即串长。 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 的子串。} ADT String 在上述抽象数据类型定义的 13 种操作中, 串赋值 StrAssign 、串比较 pare 、求串长 StrLength 、串联接 Concat 求子串 SubString 5 种操作构成串类型的最小操作子集。例如, (pare) 、 (StrLength) 、(SubString) Index(S,T,pos) 和串的置换操作 Replace(S, T, V) 。 Index (S, T, pos) 算法的基本思想: 从主串 S中取“第 i 个字符起、长度和串 T相等的子串”和串 T比较, 若相等,则求得函数值为 i, 否则 i 值增 1直至找到和串 T相等的子串或者串 S中不存在和 T相等的子串为止。即求使下列等式