数据结构课件串

《数据结构课件串》由会员分享，可在线阅读，更多相关《数据结构课件串（14页珍藏版）》请在装配图网上搜索。

1、数据结构数据结构North China Electric Power UniversityData Structure华北电力大学计算机科学与工程系华北电力大学计算机科学与工程系Dept. of Computer Science&Engineering of North China Electric Power University第五章第五章 串串 串的基本概念串的基本概念 串的基本操作串的基本操作 串的存储结构串的存储结构North China Electric Power University 关于串的几个算法关于串的几个算法串的基本概念串的基本概念North China Electri

2、c Power University华电华电计算机系计算机系例如例如: : S1= abc S2= FORTRAN_77 S3= = ( (空串空串) )S4= 由由4 4个空格组成的空格串个空格组成的空格串 串是由串是由n 0个字符组成的有限序列个字符组成的有限序列, , 通常记为通常记为 S = a1 a2 a3 an-1 an 其中其中, , S表示串名表示串名( (也称串变量也称串变量), ), 一对引号括起来的字一对引号括起来的字 符序列称为串值符序列称为串值, , ai可以是字母、数字或其他允许的字可以是字母、数字或其他允许的字 符。符。n 为串的长度为串的长度, , 长度为长度为

3、0的串称为空串。的串称为空串。一一. .串的定义串的定义North China Electric Power University华电计算机系华电计算机系 1. . 串值须用一对引号括起来，但引号不属于串值。串值须用一对引号括起来，但引号不属于串值。说明说明2. . 要区分空串与由空格字符组成的串的不同。要区分空串与由空格字符组成的串的不同。String = String North China Electric Power University华电华电计算机系计算机系1. . 子串：子串：串中若干个连续的字符组成的子序列串中若干个连续的字符组成的子序列。例如例如: : S= Beijing&

4、Shanghai T= jing 2. . 主串主串: : 包含子串的串包含子串的串。3. . 位置：位置： ( (2).).子串在主串中的位置子串在主串中的位置被定义为该被定义为该 字符在字符在 串中的序号。串中的序号。 例如例如: : S= Beijing&Nanjing&Shanghai T= jing 位置为位置为4 4二二. . 几个名词概念几个名词概念(1). 单个字符在主串中的位置单个字符在主串中的位置被定义为主串被定义为主串 中首次出现的该子串的第一个字符在主中首次出现的该子串的第一个字符在主 串中的位置。串中的位置。 North China Electric Power Un

5、iversity华电华电计算机系计算机系 的充分必要条件为两个字符串的长的充分必要条件为两个字符串的长度相等，并且对应位置上的字符相同。度相等，并且对应位置上的字符相同。4. . 两个字符串相等两个字符串相等 abcd bacd abcd = abcd North China Electric Power University华电华电计算机系计算机系 6.2 串的基本操作串的基本操作1. .给串变量赋值给串变量赋值 ASSIGN(S1,S2)strcpy(S2,S1)2. .判断两个串是否相等判断两个串是否相等 EQUAL(S1,S2)strcmp(S1,S2)3. .两个字符串连接两个字符串

6、连接 CONCAT(S1,S2)strcat(S1,S2)4. .求字符串的长度求字符串的长度 LEN(S)strlen(S)5. .求子串求子串 SUBSTR(S,i,k)6. .求子串在主串中的位置求子串在主串中的位置 INDEX(S1,S2)strstr(S1,S2)7. .串的替换串的替换 REPLACE(S,S1,S2)8. .串的复制串的复制 COPY(S1,S2)strcpy(S2,S1)9. .串的插入串的插入 INSERTS(S1,i,S2) C函数函数North China Electric Power University华电华电计算机系计算机系1. . 非紧缩格式非紧缩

7、格式( (设每个字有设每个字有4 4个字节个字节) )例如例如: : S = DATA STRUCTURE DASTRUCTATURED A T AS TRU C T UR E2. . 紧缩格式紧缩格式3. . 单字节方式单字节方式 6.3 串的存储结构串的存储结构一一. .串的顺序存储结构串的顺序存储结构A TSAT R UUTCDR ENorth China Electric Power UniversitySDATE 说说 明：明： 所谓链结点大小是指每个链结点的数据域中存放所谓链结点大小是指每个链结点的数据域中存放 的字符的个数。的字符的个数。DATA STRURE S二二. .串的链

8、式存储结构串的链式存储结构结点大小为结点大小为4 4的链表的链表结点大小为结点大小为1 1的链表的链表North China Electric Power University 6.4 串的几个算法串的几个算法一一. .串的定义串的定义Type string=record curlen:integer; ch:array1.maxlen of char; end;二二. .串的连接串的连接 假设假设r,s,t都是上面定义的都是上面定义的string型变量，且型变量，且r是是s与与t连接后连接后得到的串，则连接运算得到的串，则连接运算concat(r,s,t)是将是将s与与t的串值分别传送的串值

9、分别传送到到r相应的位置上。相应的位置上。North China Electric Power University华电华电计算机系计算机系1) s.curlen+t.curlenmaxlen，这时得到的串这时得到的串r r是连接所要求的是连接所要求的 正确结果；正确结果；2) s.curlen+t.curlenmaxlen，需要将需要将t t的一部分截断，得到的的一部分截断，得到的 串串r r只包含只包含s s和和t t的一个子串；的一个子串；3) s.curlenmaxlen，这时需要对这时需要对s s进行截断，得到的串进行截断，得到的串r r仅是仅是 s s的一个子串；的一个子串；Pro

10、cedure concat(var r,s,t:string; var p:boolean);Begin case s.curlen+t.curlenmaxlen and s.curlen=maxlen: p:=true; movch(r,s,1,1,maxlen); r.curlen:=maxlen; end caseEnd;Procedure movch(t,s,i,j,num);Begin for k:=0 to num 1 do ti+k:=sj+k;End;三三. .求子串的运算求子串的运算 求子串的过程求子串的过程sub(r,s,fir,length)也是移动字符序列的过程，也是移动字符序列的过程，它将串它将串s中从第中从第fir位置开始的长度为位置开始的长度为length的子串赋给的子串赋给r。Procedure sub(r,s,fir,lenth);Begin if(fir+length-1s.curlen) or (fir1) or(lengths.curlen) or (jt.curlen); if jt.curlen then ind:=i-t.curlen else ind:=0;End;North China Electric Power University