第章串 41辛的基哔辘念 42串的存储结构 42/辛的顺序存储结构 422串的铖式存储结构 神4B辛的模式匹配
第四章 串 4.1 串的基本概念 4.2 串的存储结构 4.2.1 串的顺序存储结构 4.2.2 串的链式存储结构 ** 4.3 串的模式匹配
4.1串的基本概念 ●串 String):是由n个字符组成的有限序列。 记为:S=“ana2a3…,an”(n>=0) s是串名,用双引号括起来的字符序列是串的值; 串中字符个数n称为串的长度; >长度为0的串称为空串,用φ表示; 串中任意个连的字符组成的子序列称为该串的子 串;如若s1=“a2a3”就是的一个子串,s称为s的主串
启迪管理课程 2 ⚫串(String)：是由n个字符组成的有限序列。 记为： S=“a1a2a3…an ”（n>=0) 4.1 串的基本概念 ➢ s是串名，用双引号括起来的字符序列是串的值； ➢ 串中字符个数n称为串的长度； ➢ 长度为0的串称为空串，用ф表示； ➢ 串中任意个连续的字符组成的子序列称为该串的子 串；如若s1=“a2a3 ”就是s的一个子串，s称为s1的主串
4.1串的基本概念 判断题:如果一个串中的所有字符均在另一串中出 现,则说前者是后者的子串。() Sl=“ I have a sweet drean!” S1的串长=21 a在S1中的位置为4 注意区分: 和 前者是长度为1的空白串;后者是空串,长度为0。 3
启迪管理课程 3 判断题：如果一个串中的所有字符均在另一串中出 现，则说前者是后者的子串。（ ） S1=“I have a sweet dream!” S1的串长= a在S1中的位置为 21 4 注意区分： “ ”和“” 前者是长度为1的空白串；后者是空串，长度为0。 4.1 串的基本概念
4.1串的基本概念 的基本运算如下 (1) Strassign(s;cstr):将一个字符串常量赋给串s,即生 成一个其值等于cstr的串。如 StrAssign(s“abc”),则 S=“abc”。 (2) StrCopy(s,t):串复制:将串t赋给串s (3) Strequal(s,t):判串相等:若两个串s与等则返 回真;否则返回假。相等的条件? (4) Strength(s):求串长:返回串s中字符个数
启迪管理课程 4 (1)StrAssign(s,cstr): 将一个字符串常量赋给串s,即生 成一个其值等于cstr的串s。如StrAssign(s,“abc”),则 s=“abc”。 (2)StrCopy(s,t): 串复制:将串t 赋给串s。 (3)StrEqual(s,t): 判串相等:若两个串s与t相等则返 回真；否则返回假。 串的基本运算如下: 相等的条件？ (4)StrLength(s): 求串长:返回串s中字符个数。 4.1 串的基本概念
4.1串的基本概念 (5) Concat(s,t;/连接 返回由两个串和连接在一起形成的新串。如s=“xyz” t=“abc”,则 Concat(s,=“ xyzabc”注意: Concat(s,) Concat(t, s) (6) Substr(s,ij);/求子串 返回串中从第( SisStrlength③)个字符开始的、连 续(0≤ <Strength(S-计1个字符组成的子串。如 s=“ abcde”,i=2,则j的取值在0~4
启迪管理课程 5 (5)Concat(s,t); //串连接 返回由两个串s和t连接在一起形成的新串。如s=“xyz” t=“abc”,则Concat(s,t)=“xyzabc” 注意： Concat(s,t)!= Concat(t,s) (6)SubStr(s,i,j); //求子串 返回串s中从第i (1≤i≤StrLength(s)) 个字符开始的、连 续j (0≤j≤StrLength(s)-i+1)个字符组成的子串。如 s=“abcde”,i=2,则j的取值在0～4。 4.1 串的基本概念
4.1串的基本概念 (7) )InsTr((s1,s2);/将串s2插入到串s1的第 i( <isStrlength(s)+1)个字符中即将s2最为一个整 体插入到s的第个字符中并返回产生的新串。 (8) Destr(ij):从串s中删去从第i(1≤< StrEngth(s) 个字符开始的长度为的子串并返回产生的新串
启迪管理课程 6 (7)InsStr(s1,i,s2); //将串s2插入到串s1的第 i(1≤i≤StrLength(s)+1)个字符中,即将s2最为一个整 体插入到s1的第i个字符中,并返回产生的新串。 (8)DelStr(s,i,j):从串s中删去从第i(1≤i≤StrLength(s)) 个字符开始的长度为j的子串,并返回产生的新串。 4.1 串的基本概念
4.1串的基本概念 (9) Repstr(sit);/替换 在串s中将第(≤ isStrLength(s)个字符开始的 j个字符构成的子串用串替换并返回产生的新 串。如s=“ bbabbabba,=7j=3,←=“c”,结果为 “ bbabbac” (10 Dispstre(s);/串输出 输出串s的所有元素值
启迪管理课程 7 (9)RepStr(s,i,j,t); //替换 在串s中,将第i(1≤i≤StrLength(s))个字符开始的 j个字符构成的子串用串t替换,并返回产生的新 串。如s=“bbabbabba”,i=7,j=3,t=“c”, 结果为： s=“bbabbac” (10)DispStr(s); //串输出 输出串s的所有元素值。 4.1 串的基本概念
42串的存储结构--顺序串 421串的顺序存储结构——顺序串 版序:串中的字符被依次存放1001「A 在一组连续的存储单元里。1002B 根据每个存储单元中存放字符1000 数的不同,串的顺序存储份紧缩1004D 格式和非紧缩格式两类顺序串。 005E 1006 1001ABCD1007G 1002EFGH 1008H 1009 10031J 100a 紧缩格式 非紧缩格式 8
启迪管理课程 8 4.2 串的存储结构－－顺序串 4.2.1 串的顺序存储结构——顺序串 1001 A 1002 B 1003 C 1004 D 1005 E 1006 F 1007 G 1008 H 1009 I 100a J 1001 A B C D 1002 E F G H 1003 I J 紧缩格式 非紧缩格式 顺序串：串中的字符被依次存放 在一组连续的存储单元里。 根据每个存储单元中存放字符 数的不同，串的顺序存储份紧缩 格式和非紧缩格式两类顺序串
42串的存储结构--顺序串 o非紧缩各式的顺序存储结构 typedef struct char data[ MaxSize;/存放串的字符 int len;/肖前串的长度 3 Astring; 例:s=“ I have a sweat dream! maxsize-1 av e swe a t dre a m! en 9
启迪管理课程 9 4.2 串的存储结构－－顺序串 o 非紧缩各式的顺序存储结构 typedef struct { char data[MaxSize]; //存放串的字符 int len; //当前串的长度 } SqString; 例：s=“I have a sweat dream!” I h a v e a s w e a t d r e a m ! … … 0 1 maxsize-1 len-1
42串的存储结构--顺序串 顺序中实现串的基本运算如下 1. StrAssign(s, cstr) void StrAssign(sqstring &s, char striD 将一个字符常量给索s int for (i=0; cstr!=10; 1++) schi=cstr; 串常量怎样存放? s。en a c ■■■ ■■■ e 10 10
启迪管理课程 10 4.2 串的存储结构－－顺序串 顺序串中实现串的基本运算如下: 1. StrAssign(s,cstr) void StrAssign(SqString &s, char cstr[]) { //将一个字符串常量cstr赋给串s. int i; for (i=0;cstr[i]!='\0';i++) s.ch[i]=cstr[i]; s.len=i; } 串常量怎样存放？ a c … … e \0