【大学数据结构课件】串.pptVIP

内容提要 5.1 串及其操作 串的定义 串的基本操作 5.2 串的表示和实现 顺序存储表示 串的块链存储表示 5.3 串的模式匹配算法 求子串位置的定位函数 模式匹配的一种改进算法 5.4串操作应用举例 文本编辑 建立词索引表 5.1 串及其操作 1、串的逻辑结构定义 串(String)(或字符串)：是由零个或多个字符组成的有限序列。一般记为：s=‘a1a2…an’ (n?0) 其中，s是串的名，用单引号括起来的字符序列是串的值；ai(1? i? n)可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串(null string)，它的长度为零。（空串与空格串的区别） 子串：串中任意个连续字符构成的子序列 串相等：当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符串都相等时才相等。 串及其操作(cont’d) 2. 串的基本操作 串的基本操作： 赋值 复制 比较 求长度 串连接 子串定位 取子串 串插入 串删除 串替换 5.2 串的表示和实现 1、字符串的存储表示 (1)顺序存储 利用静态数组存放字符串 (2)堆分配存储 利用动态分配的内存存放字符串 (3)链式存储 块链结构：#define N 5 //N决定存储密度 typedef struct strnode {char sdata[N]; struct strnode *next; }STRNODE; 串的表示和实现(cont’d) (3)链式存储 块链结构：#define N 5 //N决定存储密度 typedef struct strnode {char sdata[N]; struct strnode *next; }STRNODE; 串的表示和实现(cont’d) 2、字符串基本操作的实现 (1)串的联接 利用截尾法进行处理 (2) 求两个串的最长公共子串 串的表示和实现(cont’d) 5.3 串的模式匹配算法 1、字符串模式匹配 串的模式匹配算法(cont’d) 2. 字符串模式匹配的KMP算法 串的模式匹配算法(cont’d) 2. 字符串模式匹配的KMP算法 串的模式匹配算法(cont’d) 2. 字符串模式匹配的KMP算法 5.4 串操作应用举例 1、文本编辑 文本编辑程序是一个面向用户的系统服务程序，广泛用于源程序的输入和修改，甚至用于报刊和书籍的编辑排版以及办公室的公文书信的起草和润色。 文本编辑的实质是修改字符数据的形式或格式。 各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串的查找、插入和删除等基本操作。 文本编辑程序的设计：用户可以利用换页符和换行符把文本划分为若干页，每页有若干行。可以把文本看承是一个字符串，称为文本串，页则是文本串的子串，行又是页的子串。 2、建立词索引表 信息检索是计算机应用的重要领域之一。 主要操作是在大量的存放在磁盘上的信息中查询一个特定的信息，为了提高效率，一个重要的问题是建立一个好的索引系统。 * * 串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。 普通线性表操作的最基本单位是结点，而字符串操作的基本单位是串或子串 A B C D E F G H ^ 在D后面插入OOO后： A B C D O O O E F G H ^ void maxcomstr(char s[],char t[])//串采用顺序存储结构 {int index=0,lens,lent,length=0,length1,i=0,j,k; lens=strlen(s);lent=strlen(t); while(ilens)//当串s没完,i是串s的下标 {j=0; while(jlent)//当串t没完，j是串t的下标 {if(s[i]==t[j]) //遇到相等的字符,继续找相等字符构成子串 {length1=1; for(k=1;s[i+k]==t[j+k];k++)length1++; if(length1length){index=i;length=