数据结构4-串.pdfVIP

第四章 字符 / (string) ”的学习目标 q熟悉 的有关概念， 和线性表的关系。 q掌握 的各种存储结构，比较它们的优、缺点。 q熟练掌握串的七种基本运算，并能利用这些基本运算 实现 的其它各种运算。 1 4.1 的定义与操作 1.术语 (1)串：由零个或多个字符组成的有限序列。 n个字符C1,C2,...,Cn组成的串记作： s=C C ...C n=0 1 2 n 其中: s为串名， C C ...C 为串值， n为串长 1 2 n 例 PASCA语言: s1=data1234 s2=123*abc C语言: s1=data1234 s2=123*abc A’为字符 A为字符 %c为字符格式 %s为字符串格式 2 (2)空串：不含字符的 /长度为零的串。 PASCA语言: s= C语言: s= (3)空格串：仅含空格字符’ ’的串。 例 s1=F s2=FF s1= s2= (4)子串： s中任意个连续的字符组成的子序列称为 s 的子串。 主 含某个子 的串。 例 st=ABC123A123CD s1=ABC s3=123A s4=ABCA s2=ABC12 s5=ABCE s6=321CBA 3 特别地：空 是任意 的子 ，任意 是其自身的子串。 (5)子串的位置： 子 t 在主 s 中的位置是指主 s 中第一个与t 相同的子 的首字母在主串中的位置; 首字母 例：s= ababcabcac” , t= abc”，子 t 在主 s 中的位置为3 (6) 相等： 两个 相等，当且仅当两个串长度相同，并且各个对应位 置的字符都相同。 4 v 是一种特殊的线性表 v 串与一般线性表的区别： 串的数据元素约束为字符集； 串的基本操作通常针对串的整体或串的一个部分进行。 v 为何要单独讨论 ”类型？ 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 程序设计中，处理对象很多都是 类型。 5 串的抽象数据类型定义 AD T String{ 数据对象：D＝{a |a ∈CharacterSet,i＝1,2,…,n;n≥0} i i 数据关系：S＝{ a , a | a ，a ∈D, i ＝2,…,n} i-1 i i-1 i 基本操作： StrAssign(T,chars) Index(S, T,pos) StrLength(S)