数据结构概论 第4章 串 董黎刚 浙江工商大学信电学院 2019年1月18日.

Presentation on theme: "数据结构概论 第4章 串 董黎刚 浙江工商大学信电学院 2019年1月18日."— Presentation transcript:

1 数据结构概论 第4章 串 董黎刚 浙江工商大学信电学院 2019年1月18日

2 1. 串的逻辑结构

3 4.1.1 背景 串(String)是一种逻辑结构，是一种特殊的线性表：数据元素为字符。换句话说，串是元素受限的线性表。
串在文字编辑、词法扫描、符号处理以及定理证明等许多领域得到越来越广泛的应用。 4.1 串的逻辑结构

4 4.1.2 串的定义 串是数据元素为字符的线性表, 一般记为：S=′a1a2...an′(n≥0)，引号本身不属于串，用双引号也可以。
什么是字符？计算机中使用的字母、数字、字和符号，包括：1、2、3、A、B、C、~！·#￥%…—*（）+等等。 1个汉字字符存储需要2个字节，1个英文字符存储需要1个字节。 4.1 串的逻辑结构

5 4.1.2 串的定义 空串与空格串的区别 n是串中字符的个数, 称为串的长度，n=0时的串称为空串(Null String)。
空格串(Blank String)是包含空格字符的串。 子串：串中任意个连续的字符组成的子序列。 空串是任意串的子串，任意串是其自身的子串。 包含子串的串相应地称为主串。 字符/子串在串中的序号（从1开始）称为该字符/子串在串中的位置。 4.1 串的逻辑结构

6 4.1.2 串的定义 串相等：两个串的长度相等, 并且每个对应位置的字符都相同时才相等。 字符串和串的区别
串是一个逻辑结构，而字符串是C语言中的一个数据类型，包含三要素（数据元素、结构关系、基本操作）。 上述概念差异导致的细节差异，比如： 下面定义的字符串的长度是5，但是从串的角度来看长度是6（因为字符串末尾默认还有一个结束符——‘\0’）。char a[10]=“hello”; C语言的字符串只能用双引号，而串用单或双引号均可 4.1 串的逻辑结构

7 4.1.2 串的定义 比如，"123"是数字字符串，它不同于常数123。 比如，"xl"是长度为2的字母字符串，而xl通常表示一个标识符。
假如有串A=′China Beijing′, B=′Beijing′, C=′China′, 则它们的长度分别为13、7和5。B和C是A的子串, B在A中的位置是7,C在A中的位置是1。 4.1 串的逻辑结构

8 4.1.3 串的操作 StrAssign(S, chars):生成一个值等于chars的串S
StrInsert(S, pos, T) :在串S的第pos个字符之前插入串T StrDelete(S, pos, len) :从串S中删除第pos个字符起长度为len的子串 StrCopy(S, T) :由串T复制得串S IsStrEmpty(S) :若串S为空串, 则返回TRUE, 否则返回FALSE StrCompare(S, T) :若S>T, 则返回值>0;如S=T, 则返回值=0;若S<T, 则返回值<0。 StrLength(S) : 返回串S的长度, 即串S中的元素个数。 4.1 串的逻辑结构

9 4.1.3 串的操作 StrClear(S) : 将S清为空串 StrCat(S, T) : 将串T的值连接在串S的后面。
SubString(Sub, S, pos, len) : 用Sub返回串S的第pos个字符起长度为len的子串。 StrIndex(S, T, pos) : 若串S中存在与串T相同的子串, 则返回它在串S中第pos个字符之后第一次出现的位置，否则返回0。 StrReplace(S, T, V) : 用V替换串S中出现的所有与T相等的不重叠的子串。 StrDestroy(S) : 销毁串S。 无法设计上述这些串操作，因为物理结构还没有定 4.1 串的逻辑结构

10 4.1.4 字符串函数 字符串的使用很重要，因此C语言中提供了大量函数，比如： 函数名 功能 字符串分割 字符串查找 字符查找（最早出现）
strtok 字符串分割 strstr 字符串查找 strchr 字符查找（最早出现） strrchr 字符查找（最后出现） index 字符查找(返回首次出现的位置，包括\0) rindex 字符查找(返回最后一次出现位置，包括\0) strspn 字符查找(两个字符串中有几个字符相同) strcspn 字符查找(两个字符串中有几个字符不同) strpbrk 定位前个字符串中首次出现后个字符串中的字符 strcat 字符串连接 strncat 字符串连接（连接一部分） strlen 字符串长度计算 strcpy 复制字符串 strncpy 复制字符串（复制一部分） 函数名 功能 strcmp 字符串比较 stricmp 字符串比较(忽略大小写) strcoll 字符串比较(可按照特定语言环境次序) strncasecmp 字符串比较(忽略大小写，比较前 n 个字符) toupper 字符串转换(小写转大写) tolower 字符串转换(大写转小写) toascii 将整数转换成合法的ASCII码字符 gcvt 将浮点型数转换为字符串(四舍五入) strtoul 将字符串转换成无符号长整型数（可指定进制） strtol 将字符串转换成长整型数（可指定进制） atol 将字符串转换成长整型数 atoi 将字符串转换成整型数 strtod，atof 将字符串转换成浮点数 4.1 串的逻辑结构

11 2. 串的物理结构 ——顺序串

12 4.2.1 背景 因为串是特殊的线性表，故其存储结构与线性表的存储结构类似。只不过由于组成串的结点是单个字符，所以存储时有一些特殊的情况。
串的存储方式有定长顺序串（静态顺序表）、堆串（动态顺序表）和块链串。 4.2 串的物理结构——顺序串

13 4.2.2 定义 定长顺序串 （静态：Static） 堆（Heap）串 typedef struct { char ch[MAXLEN];
int len; } SString; char *ch； int len； } HString； 与静态顺序表相比，堆串更节省空间。 4.2 串的物理结构——顺序串

14 4.2.2 定义 定长顺序串和堆串的动画 4.2 串的物理结构——顺序串

15 4.2.3 操作的实现 定长顺序串 堆串 StrInsert(s, pos, t) 考虑插入后三种情况：
（1）串长和小于MAXLEN, s和t都无需舍弃字符 （2）s需舍弃字符 （3）t需舍弃字符 temp=malloc(s->len + t.len); s,t赋值到temp（不会发生舍弃字符的情况） s->ch=temp; StrDelete(s, pos, len) for(i=pos+len;i<s->len;i++) s->ch[i-len]=s->ch[i]; s->len=s->len - len; 用temp临时存放剩余的字符 StrCopy(s, t) for(i=0;i<t.len;i++) s->ch[i]=t.ch[i]; 给s分配空间 其他同左 4.2 串的物理结构——顺序串

16 4.2.3 操作的实现 定长顺序串 堆串 StrClear(s) s->len=0; if(s->ch! =NULL)
free(s->ch); s->ch=NULL; StrCat(s, t) 考虑连接后三种情况： （1）串长和小于MAXLEN，s和t都无需舍弃字符 （2）串长和大于MAXLEN，t舍弃字符 （3）串s的长度等于MAXLEN，t全部舍弃 temp=(char *)malloc(s->len + t.len); s,t赋值到temp（不会发生舍弃字符的情况） s->ch=temp; 4.2 串的物理结构——顺序串

17 4.2.3 操作的实现 定长顺序串 堆串 IsStrEmpty(s) return(s.len==0) 同左
SubString(sub, s, pos, len) for(i=0;i<len;i++) sub->ch[i]=s.ch[i+pos]; sub->len=len; StrLength(s) return(s.len); StrCompare(s, t) for(i=0;i<s.len&&i<t.len;i++) if(s.ch[i]!=t.ch[i]) return(s.ch[i] - t.ch[i]); StrAssign(s,t) StrAssign和StrCopy的区别是：前者是字符串赋给串，后者是串赋给串 for(i=0;t[i]!='\0';i++) s->ch[i]=t[i]; 先释放s空间，再分配s空间，最后赋值 4.2 串的物理结构——顺序串

18 4.2.4 定长顺序串和堆串的区别 定长顺序串StrCat(s,t)实例 开始是 串t连到串s后，得到（串s空间不够，超出部分被截去）：
4.2 串的物理结构——顺序串

19 4.2.4 定长顺序串和堆串的区别 堆串在被赋值前，要释放空间 没有maxlen限制，但是用malloc后要判断空间是否分配成功
if(s->ch! =NULL) free(s->ch); if(temp=(char *)malloc(s->len + t.len)==NULL) return(0); 4.2 串的物理结构——顺序串

20 4.2.5 串操作函数实例 StrInsert(SString *s, int pos, SString t) { int i;
/*在串s中下标为pos(注意：下标从零开始，等于位置减1)的字符之前插入串t */ StrInsert(SString *s, int pos, SString t) { int i; if (pos<0 || pos>s->len) return(0); // 插入位置不合法 if (s->len+t.len <= MAXLEN) { //插入后串长≤MAXLEN for (i=s->len + t.len-1; i>=t.len+pos; i--) s->ch[i] = s->ch[i - t.len]; for (i=0;i<t.len;i++) s->ch[i+pos] = t.ch[i]; s->len=s->len+t.len; } 4.2 串的物理结构——顺序串

21 4.2.5 串操作函数实例 //插入后串长>MAXLEN, 但串t的字符序列可以全部插入
else if (pos+t.len <= MAXLEN) { for (i=MAXLEN-1; i>t.len+pos-1; i--) s->ch[i] = s->ch[i-t.len]; for (i=0;i<t.len;i++) s->ch[i+pos] = t.ch[i]; s->len=MAXLEN; }else { // 串t的部分字符序列要舍弃 for (i=0; i<MAXLEN-pos; i++) } return(1); 4.2 串的物理结构——顺序串

22 4.2.5 串操作函数实例 /* 在串s中删除从下标pos起len个字符 */
StrDelete(SString *s, int pos, int len) { int i; if (pos<0 || pos>(s->len-len)) return(0); for (i=pos+len; i<s->len; i++) s->ch[i-len] = s->ch[i]; s->len = s->len - len; return(1); } 4.2 串的物理结构——顺序串

23 4.2.5 串操作函数实例 /* 将串t的值复制到串s中 */ StrCopy(SString * s, SString t) {
int i; for (i=0;i<t.len;i++) s->ch[i]=t.ch[i]; s->len=t.len; } 4.2 串的物理结构——顺序串

24 4.2.5 串操作函数实例 /* 若串s为空(即串长为0), 则返回1, 否则返回0 */ IsStrEmpty(SString s) {
if (s.len==0) return(1); else return(0); } 4.2 串的物理结构——顺序串

25 4.2.5 串操作函数实例 //逐个比较字符，若不等则返回字符的ASCII差；若串s和t完全相同, 则返回0；如长度不等，则返回长度差。
StrCompare(SString s, SString t) { int i; for (i=0; i<s.len&&i<t.len; i++){ if (s.ch[i] != t.ch[i]) return(s.ch[i] - t.ch[i]); } return(s.len - t.len); 4.2 串的物理结构——顺序串

26 4.2.5 串操作函数实例 /* 将串t连接在串s的后面 */ StrCat(SString *s, SString t) {
int i, flag; if (s->len+t.len <= MAXLEN){ /* 连接后串长小于MAXLEN */ for (i=s->len; i<s->len + t.len; i++) s->ch[i] = t.ch[i - s->len]; s->len+=t.len; flag=1; } 4.2 串的物理结构——顺序串

27 4.2.5 串操作函数实例 /* 连接后串长大于MAXLEN, 但串s的长度小于MAXLEN，即连接后串t的部分字符序列被舍弃 */
else if (s->len < MAXLEN) { for (i=s->len; i<MAXLEN; i++) s->ch[i] = t.ch[i-s->len]; s->len = MAXLEN; flag=0; } else flag=0; /* 串s的长度等于MAXLEN, 串t不被连接 */ return(flag); 4.2 串的物理结构——顺序串

28 4.2.5 串操作函数实例 /* 将串s中下标pos起len个字符复制到sub中 */
SubString(SString *sub, SString s, int pos, int len) { int i; if (pos<0 || pos>s.len || len<1 || len>s.len-pos){ sub->len=0; return(0); }else { for (i=0;i<len;i++) sub->ch[i] = s.ch[i+pos]; sub->len=len; return(1); } 4.2 串的物理结构——顺序串

29 4.2.5 串操作函数实例 /*求串t在串s中的位置 */ StrIndex(SString s, int pos, SString t)
{ int i, j; if (t.len == 0) return(0); i=pos; j=0; while (i<s.len && j<t.len){ if (s.ch[i] == t.ch[j]){i++; j++;} else { i=i-j+1; j=0;} } if (j >= t.len) return(i - j); else return(-1); 4.2 串的物理结构——顺序串

30 4.2.5 串操作函数实例 串匹配动画 4.2 串的物理结构——顺序串

31 3. 串的操作 ——串匹配

32 4.3.1 背景 串匹配，又称串定位或串的模式匹配，其实就是串中的查找操作。
串匹配有基本的匹配方法（Brute-Force，BF）和改进的串匹配算法（比如，KMP算法）。 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth与V.R.Pratt和J.H.Morris同时发明（1977年），因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法） 4.3 串的操作——串匹配

33 4.3.1 背景 高德纳（Donald Ervin Knuth，1938年-），美国著名计算机科学家，被誉为算法分析之父，是The Art of Computer Programming的作者以及TeX排版软件的发明人。 4.3 串的操作——串匹配

34 4.3.2 相关概念 在串匹配中，一般将主串称为目标（串），子串称为模式（串）。 假设S 为目标串，T为模式串，不妨设：
S="s1s2s3…sm"  T="t1t2t3…tn"(0＜n≤m) 4.3 串的操作——串匹配

35 4.3.2 相关概念 串匹配就是对于合法的位置（又称合法的位移）0<i≤m-n+1，依次将目标串中的子串“sisi+1…si+n-1”和模式串“t1t2t3…tn”进行比较。 若"sisi+1…si+n-1"＝"t1t2t3…tn"，则称从位置i开始的匹配成功，或称i为有效位移。 若"sisi+1…si+n-1"≠"t1t2t3…tn"，则称从位置i开始的匹配失败，或称i为无效位移。 4.3 串的操作——串匹配

36 4.3.3 BF匹配算法 例如：在串S=“abcabcabcabda”中查找T=“abcabd”:
第一次位移。先是比较S[1]和T[1]是否相等，然后比较S[2] 和T[2]是否相等…我们发现一直比较到S[6] 和T[6]才不等。如图： 4.3 串的操作——串匹配

37 4.3.3 BF匹配算法 当这样一个失配发生时，进行第二次位移。T下标回溯到开始（即1），S下标回溯的长度与T相同，然后S下标增1,然后再次比较。如图： 由上图可见，T只往后移动一位 4.3 串的操作——串匹配

38 4.3.3 BF匹配算法 这次立刻发生了失配，进行第三次位移。T下标又回溯到开始（即1），S下标增1(即变为3),然后再次比较。如图：
4.3 串的操作——串匹配

39 4.3.3 BF匹配算法 按照每次位移移动一位的方式，一边位移一边比较匹配情况,直到最后的状态是： 4.3 串的操作——串匹配

40 4.3.3 BF匹配算法 BF匹配算法的最后一次比较是sm-n+1 … sm和t1t2t3…tn 比较：
S="s1s2s3…sm-n+1…sm"  T="t1t2t3…tn"(0＜n≤m) BF匹配算法的最坏时间复杂度是O( (m-n+1)n) 而KMP算法的时间复杂度为O(m+n) 4.3 串的操作——串匹配

41 4.3.4 KMP匹配算法 KMP算法的核心技巧在于观察T中是否有重复模式，以便减少重复比较。
比如在下面的串T中，“d”（下标为6）之前的“ab”和“c”（下标为3）开始的“ab”是一致的，这个现象可以用模式函数表示：nextval(6)=3。 4.3 串的操作——串匹配

42 4.3.4 KMP匹配算法 仍然用上面的例子。第一次位移与基本的串匹配算法一样，从位置1开始： 4.3 串的操作——串匹配

43 4.3.4 KMP匹配算法 当失配发生时，进行第二次位移。因为T[6]和S[6]发生失配，根据nextval[6]=3，T[6]未匹配成功的位置用T[3]来代替，即开始比较S[6]和T[3]是否相等，… 可见，不同于BF算法，每次位移中，KMP算法不仅移动位数较多，而且比较次数减少 4.3 串的操作——串匹配

44 4.3.4 KMP匹配算法 当失配发生时，进行第三次位移。
因为T[6]和S[9]发生失配，根据nextval[6]=3， T[6]未匹配成功的位置用T[3]来代替， 即开始比较S[9]和T[3]是否相等，… 4.3 串的操作——串匹配

45 4.3.5 模式函数的计算 模式函数有两种计算方式 next数组，算法稍微简单 nextval数组，算法性能更好 4.3 串的操作——串匹配

46 4.3.5 模式函数的计算 next数组 next [1]= 0。这意味着接下来用T[0]和S中当前失配元素比较,因为没有T[0],所以实际上是T[1]和S下标增1后的元素进行比较。 next [2]= 1 next [j]=k+1, 模式串中下标为j的字符，如果j的前面k个字符与开头的k个字符相等。即T[1]T[2]…T[k]==T[j-k]T[j-k+1]…T[j-1]（1≤k<j-1）。简单地说，根据其前紧邻的与起始位置开始匹配的最长序列长度加1 举例：abaabcac的next数组是 4.3 串的操作——串匹配

47 4.3.5 模式函数的计算 next数组的缺点 例如模式串‘aaaaa’在和目标串‘aaabaaaab’匹配时，当i=4（目标串）、j=4（模式串）时不匹配，需要进行多余的三次比较（i=4,j=3;i=4,j=2;i=4,j=1） 实际上，因为模式串第1、2、3个字符和目标串第4个字符都相等，因此不再需要和目标串中第4个字符进行比较，而可以将模式串滑动4个字符的位置直接进行i=5、j=1的字符比较。 4.3 串的操作——串匹配

48 4.3.5 模式函数的计算 nextval数组 nextval[1]= 0
nextval[j]= 0, 模式串中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符全部都对应不等（即：T[1]!=T[j-1], T[1..2]!=T[j-2..j-1],...,T[1..k]!=T[j-k..j-1]）（或者相等但T[k+1]==T[j]）（1≤k<j）。如：T=”abCabCad” 则 nextval [7]=0，因T[4]=T[7]。 4.3 串的操作——串匹配

49 4.3.5 模式函数的计算 nextval数组 nextval [j]=k+1, 模式串中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k+1] （1≤k<j）。即T[1]T[2]…T[k]==T[j-k]T[j-k+1]…T[j-1]且T[k+1] !=T[j]（1≤k<j）; 其他，nextval [j]=1   4.3 串的操作——串匹配

50 4.3.5 模式函数的计算 nextval数组——总结 nextval[1]= 0 －－－这点与next相同
nextval[j]= 0, 模式串中下标为j的字符，如果与首字符相同，且j的前面的1—k个字符与开头的1—k个字符全部都对应不等（1≤k<j）。 nextval [j]=k+1, 模式串中下标为j的字符，如果j的前面k个字符与开头的k个字符相等，且T[j] != T[k+1] （1≤k<j）; －－－这点与next类似 其他nextval [j]=1, next [2]= 1   实例：abaabcac的nextval数组是 abaabcac的next数组是 4.3 串的操作——串匹配

51 4. 串的物理结构 ——块链串

52 4.4.1 背景 串可以采用链式存储。比如： 由于串的特殊性（每个元素只有一个字符），为提高效率，每个结点往往存放多个字符——块链串。
4.5 串的物理结构——块链串

53 4.4.2 定义 块链串的定义与一般单链表的区别是： 块链串中的每个结点不是存放1个数据元素（即1个字符），而是存放多个字符。比如：
每个结点称为块，整个链表称为块链结构，为了便于操作，再增加一个尾指针。 4.5 串的物理结构——块链串

54 4.4.3 C语言定义 ＃define BLOCK_SIZE <每个结点存放的字符个数>
typedef struct Block { char ch[BLOCK_SIZE]; //定义数据域 struct Block *next; //定义指针域 }Block; //定义块链串中的“块” typedef struct Block *head; //定义头指针 Block *tail; //定义尾指针 int length; }BLString; //定义块链串 4.5 串的物理结构——块链串

55 4.4.4 评价 虽然提高结点的大小使得存储密度增大，但是做插入、删除运算时，可能会引起大量字符的移动（假如要求各个块存储相同个数的字符的话），给运算带来不便。 比如，如果插入“my”，要移动后面的“world”五个字符 4.5 串的物理结构——块链串

56 4.4.4 评价 思考：如何解除“各个块存储相同个数的字符”的限制？ 答案在下一节。 4.5 串的物理结构——块链串

57 5. 串的应用

58 4.5.1 背景 文本编辑软件用于文本的输入和修改。常用的文本编辑软件有WPS、Word等。
WPS之父——求伯君，1964年11月26日出生于浙江新昌县，毕业于国防科技大学，有“中国第一程序员“之称，1988年开始开发WPS。 4.5 串的应用

59 4.5.1 背景 文本编辑软件的实质是修改字符数据的内容和格式，虽然各个文本编辑软件的功能不同，但基本操作是一样的，都包括串的查找、插入和删除等。 4.5 串的应用

60 4.5.2 文本编辑软件的算法思路 我们把文本当作一个字符串，称为文本串。
为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。页是文本串的子串，行是页的子串。 可以采用堆串或块链串来存储文本 设立页指针、行指针和字符指针，分别指向当前操作的页、行和字符。 建立页表和行表存储每一页、每一行的起始位置和长度。 4.5 串的应用

61 4.5.3 文本编辑软件的应用实例 把下面的程序存放在一个堆串中。 在堆串中存放上述程序的方式如右所示： 说明：“↙”是换行符
FUNC max(x，y：integer)：integer; VAR z：integer; BEGIN IF x>y THEN z: =x; ELSE z: =y; RETURN(z); END; 在堆串中存放上述程序的方式如右所示： 说明：“↙”是换行符 4.5 串的应用

62 4.5.3 文本编辑软件的应用实例 页表 为方便访问该程序中的某一页和某一行，需要同时建立右边的页表和行表。
当编辑程序时，就要修改页表或行表。比如，如果行内插入字符，在行表中要修改长度，如果删掉一行，在行表中也要删掉一行。 页表 行表 4.5 串的应用

63 4.5.3 文本编辑软件的应用实例 如何使用块链串来开发文本编辑软件？ 4.5 串的应用

64 总结