数据结构4串.ppt
第4 4章 串（StringString）2023-3-214.1 4.1 串类型的定义串类型的定义4.2 4.2 串的表示和实现串的表示和实现4.3 4.3 串的模式匹配算法串的模式匹配算法2023-3-22记为：记为： s = a1 a2 . an (n0 ) 串名串名串值（用串值（用 括起来）括起来）串即字符串，是由零个或多个字符组成的有限序列，是数据串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。元素为单个字符的特殊线性表。4.1 4.1 串类型的定义串类型的定义隐含结束符隐含结束符00 ，即，即ASCIIASCII码码NULLNULL为何要单独讨论为何要单独讨论“串串”类型？类型？1 1） 字符串操作比其他数据类型更复杂（如拷贝、连接操作）字符串操作比其他数据类型更复杂（如拷贝、连接操作）2 2） 程序设计中，处理对象很多都是串类型。程序设计中，处理对象很多都是串类型。若干术语：若干术语：2023-3-23串长：串长：串中字符的个数（串中字符的个数（n0n0）. n=0 . n=0 时称为空串时称为空串 。空格串：空格串：由一个或多个空格符组成的串。由一个或多个空格符组成的串。问：空串和空格串有无区别？问：空串和空格串有无区别？答：答：有区别。有区别。空串空串(Null String)(Null String)是指长度为零的串；是指长度为零的串；而空格串而空格串(Blank String),(Blank String),是指包含一个或多个空白字是指包含一个或多个空白字符符 ( (空格键空格键) )的字符串的字符串. .2023-3-24 子串：子串：子串位置：子串位置：字符位置：字符位置： 串相等：串相等：例例1：现有以下现有以下4个字符串：个字符串：a =BEI b =JING c = BEIJING d = BEI JING问：问： 他们各自的长度？他们各自的长度？a是是c和和d的子串，在的子串，在c和和d中的位置都是中的位置都是1串串S S中任意个连续的字符序列叫中任意个连续的字符序列叫S S的子串的子串; S; S叫叫主串主串。子串的第一个字符在主串中的序号。子串的第一个字符在主串中的序号。字符在串中的序号。字符在串中的序号。串长度相等，且对应位置上字符相等。串长度相等，且对应位置上字符相等。 a是哪个串的子串？在主串中的位置是多少？是哪个串的子串？在主串中的位置是多少？a =3，b =4，c = 7，d=8“空串是任意串的子串；任意串空串是任意串的子串；任意串S S都是都是S S本身的子串，除本身的子串，除S S本身本身外，外，S S的其他子串称为的其他子串称为S S的的真子串真子串。” 数据结构与算法数据结构与算法中山大学出版社中山大学出版社 空串是哪个串的子串？空串是哪个串的子串？ a是不是自己的子串？是不是自己的子串？串的抽象数据类型定义（参见教材P71）2023-3-25C语言中已有类似串运算函数！语言中已有类似串运算函数！ADT StringObjects: D=ai | aiCharacterSet, i=1, 2,，n, n0Relations: R1= | ai-1,ai D, i=2, ，nfunctions: /至少有至少有1313种基本操作种基本操作StrAssign(&T, chars) / 串赋值串赋值，生成值为，生成值为charschars的串的串T TStrCompare(S,T) / 串比较串比较，若，若STST，返回值大于，返回值大于0 0 StrLength(S) / 求串长求串长，即返回串，即返回串S S中的元素个数中的元素个数 Concat(&T, S1, S2) / 串连接串连接，用，用T T返回返回S1S1S2S2的新串的新串 SubString(&Sub, S, pos, len) / 求求S S中中pospos起长度为起长度为lenlen的的子串子串 StrCopyStrCopy（&T,S&T,S） /由串由串S S复制得到复制得到T T Index(S, T, pos) /子串定位函数（模式匹配），子串定位函数（模式匹配），返回位置返回位置 Replace(&S, T,V) / / 用子串用子串V V替换替换子串子串T TADT String最最小小操操作作子子集集复习：复习：C C语言中常用的串运算语言中常用的串运算2023-3-26 C C串比较串比较：int strcmp(char *s1,char *s2); 求串长：求串长：int strlen(char *s); 串连接：串连接：char strcat(char *to,char *from) 子串子串T T定位：定位：char strchr(char *s,char *c);参考参考C语言书语言书注：用注：用C处理字符串时，要调用标准库函数处理字符串时，要调用标准库函数 #include 类类CStrCompare(S,T) StrLength(S)Concat(&T, S1, S2)Index(S, T, pos)2023-3-27例如：例如：可利用串比较、求串长和求子串等操作实现定位函数可利用串比较、求串长和求子串等操作实现定位函数Index(S,T, pos).算法基本思想：算法基本思想：在主串在主串S中取从第中取从第i（i=pos）个字符起，）个字符起，取长度和串取长度和串T相等的子串和串相等的子串和串T比较，比较，若相等，则返回值为若相等，则返回值为i否则否则i+，直到，直到S中不存在和中不存在和T相等的子串为止。相等的子串为止。StrCompare（SubString（S，i，StrLength（T），T）=？02023-3-28Int Index（String S，String T，int pos） /T为非空串，若主串为非空串，若主串S中第中第pos个字符之后存在与个字符之后存在与T相等的子串，相等的子串， /则返回第一个这样的子串在则返回第一个这样的子串在S中的位置，否则返回中的位置，否则返回0；if（pos0） n=StrLength（S）；m=StrLength（T）；i=pos； while(i=n-m+1) if (StrCompare (SubString (S,i,m), T)!=0) +i; else return i; /while /if/Index()subsubSnmmi=posn-m+1subiTTT例1 1： 设设 s =I AM A STUDENT, t s =I AM A STUDENT, t =GOOD, q=WORKER=GOOD, q=WORKER。求：。求：2023-3-29Replace(&S, T,V) / / 用子串用子串V V替换子串替换子串T T StrLength(s) StrLength(t) SubString(&sub, s, 8, 7)= SubString(&sub, t, 2, 1)= Index(s, A)= Index(s, t)=Replace( &s, STUDENT, q )=14 /参见参见P714STUDENTO30 （ s中没有中没有t=GOOD ！）！）Index(S, T, pos) / / 返回子串返回子串T T在在pospos之后的位置之后的位置I AM A WORKER例2：设 s =I AM A STUDENT, t =GOOD,求： Concat( SubString(s,6,2), Concat( t,SubString(s,7,8) ) ) ？2023-3-210解：因为解：因为SubString(s,6,2)A ；SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT所以：所以：Concat(,SubString(s,6,2), Concat(t,SubString(s,7,8)A GOOD STUDENT串的特点：串的逻辑结构和线性表极为相似，区别串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集；仅在于串的数据对象约束为字符集；串的基本操作和线性表差别很大串的基本操作和线性表差别很大 串的基本操作中，通常以串的基本操作中，通常以“串的整体串的整体”作为操作对象。作为操作对象。2023-3-2114.24.2串的表示和实现2023-3-212定长顺序存储表示定长顺序存储表示用一组地址连续的存储单元存储串值的字符序用一组地址连续的存储单元存储串值的字符序列，属静态存储方式。列，属静态存储方式。堆分配存储表示堆分配存储表示用一组地址连续的存储单元存储串值的字符序用一组地址连续的存储单元存储串值的字符序列列, ,但存储空间是在程序执行过程中动态分配而得。但存储空间是在程序执行过程中动态分配而得。串的块链存储表示串的块链存储表示链式方式存储链式方式存储首先强调：串与线性表的运算有所不同，是以首先强调：串与线性表的运算有所不同，是以“串的整体串的整体”作为作为操作对象，例如查找某子串，在主串某位置上插入一个子串等。操作对象，例如查找某子串，在主串某位置上插入一个子串等。串有三种机内表示方法：串有三种机内表示方法：顺序顺序存储存储链式链式存储存储定长顺序存储特点：用一组连续的存储单元来存放串，直接使用定长的字符数组来定义，数组的上界预先给出，故称为静态存储分配。2023-3-213例如：例如：#define Maxstrlen 255 /用户可用的最大串长用户可用的最大串长 typedef unsigned char SString Maxstrlen1 ; /P73 SString s; /s 是一个可容纳是一个可容纳255个字符的顺序串。个字符的顺序串。注：注：一般用一般用SString0来存放串长信息（如来存放串长信息（如pascal语言）；语言）；C语言约定在串尾加结束符语言约定在串尾加结束符 0，以利操作加速，但不计入串，以利操作加速，但不计入串长长若字符串超过若字符串超过Maxstrlen 则自动截断（因为静态数组存不则自动截断（因为静态数组存不 进进去）。去）。 例：用顺序存储方式编写求子串函数SubString(&Sub,S,pos,len) 2023-3-214Status SubString(SString &sub, SString S, int pos, int len ) if(posS0 | lenS0-pos+1) return ERROR; /若若pospos和和lenlen参数越界，则告警参数越界，则告警 Sub1len=Spospos+len-1; Sub0=len; return OK;将串将串S S中从第中从第pospos个字符开始、长度为个字符开始、长度为lenlen的字符序列复制到串的字符序列复制到串SubSub中。中。（注：考虑到函数的通用性，应当让串（注：考虑到函数的通用性，应当让串SubSub的预留长度与的预留长度与S S一样）一样）子串长度子串长度s = a1 a2 . anposlenSub 讨论：想存放超长字符串怎么办？讨论：想存放超长字符串怎么办？改用动态分配的一维数组改用动态分配的一维数组堆堆堆分配存储特点：仍用一组连续的存储单元来存放串，但存储空间是在程序执行过程中动态分配而得。2023-3-215思路：思路：利用利用mallocmalloc函数合理预设串长空间。函数合理预设串长空间。特点：特点： 若在操作中串值改变，还可以利用若在操作中串值改变，还可以利用reallocrealloc函数函数按新串长按新串长度度增加空间增加空间（即动态数组概念）（即动态数组概念） 。Typedef struct char *ch; /若非空串若非空串, ,按串长分配空间按串长分配空间; ; 否则否则ch=NULLch=NULL int length; /串长度串长度HString堆堆T T的存储结构描述：的存储结构描
