数据结构教程ppt第4章串的处理.pptVIP

第4章 串（String） 若干术语： 串的抽象数据类型定义（参见教材P71） 复习：C语言中常用的串运算 例1： 设 s =’I AM A STUDENT’, t =’GOOD’, q=’WORKER’。求： 例2：设 s =’I AM A STUDENT’, t =’GOOD’,求： Concat( SubString(s,6,2), Concat( t,SubString(s,7,8) ) ) ＝？ 串的特点： 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集； 串的基本操作和线性表差别很大 串的基本操作中，通常以“串的整体”作为操作对象。 4.2 串的表示和实现 定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。 例：用顺序存储方式编写求子串函数SubString(Sub,S,pos,len) 堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。 例1：编写建堆函数 (参见教材P76） 例2：用“堆”方式编写串插入函数 (参见教材P75) 链式存储特点 ：用链表存储串值，易插入和删除。 * * 4.1 串类型的定义 4.2 串的表示和实现 4.3 串的模式匹配算法 记为： s =‘ a1 a2 …….. an’ (n≥0 ) 串名 串值（用‘ ’ 括起来） 串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。 4.1 串类型的定义 隐含结束符‘\0’ ，即ASCII码NULL 为何要单独讨论“串”类型？ 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作） 2） 程序设计中，处理对象很多都是串类型。 串长：串中字符的个数（n≥0）. n=0 时称为空串 ? 。 空格串：由一个或多个空格符组成的串。 问：空串和空格串有无区别？ 答：有区别。 空串(Null String)是指长度为零的串； 而空格串(Blank String),是指包含一个或多个空白字符‘ ’(空格键)的字符串. 子串： 子串位置： 字符位置： 串相等： 例1：现有以下4个字符串： a =‘BEI’ b =‘JING’ c = ‘BEIJING’ d = ‘BEI JING’ 问：① 他们各自的长度？ a是c和d的子串，在c和d中的位置都是1 串S中任意个连续的字符序列叫S的子串; S叫主串。 子串的第一个字符在主串中的序号。 字符在串中的序号。 串长度相等，且对应位置上字符相等。 ② a是哪个串的子串？在主串中的位置是多少？ a =3，b =4，c = 7，d=8 “空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。” ——《数据结构与算法》中山大学出版社 ③ 空串是哪个串的子串？ a是不是自己的子串？ ADT String{ Objects: D={ai | ai∈CharacterSet, i=1, 2,…，n, n≥0} Relations: R1={ai-1,ai | ai-1,ai ∈D, i=2, …，n} functions: //至少有13种基本操作 StrAssign(T, chars) // 串赋值，生成值为chars的串T StrCompare(S,T) // 串比较，若ST，返回值大于0… StrLength(S) // 求串长，即返回串S中的元素个数 Concat(T, S1, S2) // 串连接，用T返回S1＋S2的新串 SubString(Sub, S, pos, len) // 求S中pos起长度为len的子串 StrCopy（T,S） //由串S复制得到T …… Index(S, T, pos) //子串定位函数（模式匹配），返回位置 Replace(S, T,V) // 用子串V替换子串T }ADT String 最小操作子集 C 串比较：int strcmp(char *s1,char *s2); 求串长：int strlen(char *s); 串连接：char strcat(char *to,char *fro