数据结构（C语言版）程海英-第4章.pptVIP

一般情况下,模式串的next函数的定义如下: 0 当j=1时 next[j]= max {k|1kj且“t1...tk-1”=“tj-k+1...tj-1”} 1 其他情况 由此定义可以推出下列模式串的next函数值： int Index_KMP(SString S, SString T, int pos) { //利用模式串T的next函数求T在主串S中第pos个字符之后 第一次出现的位置；否则返回0。 i = pos; j = 1; while(i=S[0] j = T[0]){ if(j == 0 || S[i] == T[j]){ ++i; ++j; } //继续比较后续字符 else j = next[j]; //模式串向后移 } if(j T[0]) return i-T[0]; //匹配成功 else return 0; //匹配不成功 } KMP算法 void get_next(Sstring T, int next[]){ // 求模式串的T的next函数值并存入数组next int j = 1; int next[1] = 0; int k=0; while(jT[0]) { if(k==0||T[j]==T[k]){ ++j; ++k; next[j]=k; } else k=next[k]; } } 求模式串的next函数值 4.5 本章小结 1）串是有限个字符组成的序列，长度为零的字符串称为空串。 2）串是一种特殊的线性表。 3）串的顺序存储有非紧凑格式和紧凑格式两种。 4）串的链式存储结构具有插入、删除方便的优点，但其存储密度很低。 5）串的堆分配存储是一种动态存储结构，存放各串的值，灵活性强。 6）串的基本运算包括串的连接、插入、删除、比较、替换、和模式匹配等。 * * * * 编译原理 数据结构 第4章 串 串的定义和基本运算 串的存储结构 串的运算实现 串的模式匹配算法 本章知识要点： 4.1.1 串的定义 4.1.2 串的基本操作 4.1 串的定义和基本运算 4.1.1 串的定义 1.串的定义 串是由零个或任意多个字符组成的有限序列。 一般记为：S=“a1a2…an ” (n≥0) 其中，S为串名，引号括起来的字符序列为串值，ai（1≤i≤n）可以是字母、数字或其他字符，n为串的长度。 2.串的相关术语 1）空串。不含任何字符的串称为空串，即串的长度n=0时的串为空串。 2）空格串。由一个或多个称为空格的特殊字符组成的串称为空格串，其长度是串中空格字符的个数。 3）子串。串中任意个连续的字符组成的子序列称为该串的子串。另外，空串是任意串的子串，任意串是自身的子串。 4）主串。包含子串的串称为该子串的主串。 5）串相等。两个串的长度相等且各个位置上对应的字符也都相同。 【例】 S1=“Welcome to Beijing!” S2=“Welcome to” S3=“Welcometo” S4=“Beijing” 则串长度及其之间的关系如何？ 4.1.2 串的基本操作 1）StrAsign(S,chars)// 串的赋值 2）StrCopy(S,T) //串的复制 3）StrLength(S)// 求串长度 4）StrCat(S,T)// 串的连接 5）SubString(Sub,S,pos,len)// 求子串 6）StrIndex(S,T)// 串的定位（也称模式匹配） 7）StrInsert(S,pos,T)// 串的插入 8）StrDelete(S,pos,len) //串的删除 9）StrReplace(S,T,V) //串的替换 10）StrEmpty(S) //判断串空 11）StrCompare(S,T) //串的比较 12）StrClear(S) //串的清空 13）DispStr(S) //输出串 4.2 串的存储结构 4.2.1 定长顺序存储 4.2.2 链式存储 4.2.3 堆存储 4.2.1 定长顺序存储 顺序串的类型定义与顺序表的定义相似，可以用一个字符型数组和一个整型变量表示，其中字符数组存储串，整型变量表示串的长度。 2.存储方式 1）非紧凑存储。设串S=“Hello boy”，用非紧凑格式一个地址只能存一个字符。其优点是运算处理简单，但缺点是存储空间十分浪费。 2）紧凑存储。用紧凑格式一个地址能存四个字符。紧凑存储的优点是空间利用率