计算机上的非数值处理的对象基本上都是字符串数据.ppt

Date 计算机上的非数值处理的对象基本上都是字符串数据。 例：学生管理系统中，学生学号、姓名、性别、院系等； 图书管理系统中，图书编号、书名、作者、简介等； Date 字符串常量 字符串变量 + 一系列字符串操作 = 一种新的数据类型串类型 由于硬件结构的特点，决定了处理字符串数据时要比 数值数据复杂的多。 (1) 字符串是由一个个字符组成的，需要对每个字符分别处理 (2) 字符串需要先转化为数值后再进行处理 ASC(A) ASC(a) = 65 = 97 Date 4.1 串类型的定义 1. 基本概念 串: 由零个或多个字符组成的有限序列。 s = a1a2 an ( n0) s串名 a1a2 an 串值 |s|串的长度，即串中字符的数目。 零个字符的串称为空串，计作 = 。 | = 0 ai为字符 Date 串中任意个连续的字符组成的子序列称为该串的子串。 包含子串的串相应的称为主串。 例，串 eij 是串 beijing 的子串， beijing 称为主串。 字符在序列中的序号称为该字符在串中的位置。 子串在主串中的位置定义为子串的第一个字符在主串 中的位置。 例，字符 n 在串 beijing 中的位置为 6 。 例，子串 eij 在串 beijing 中的位置为 。2 Date 两个串相等，当且仅当这两个串的值相等。 例，串 bei jing 与串 beijing 不相等 。 串值必须用一对单引号括起来，但单引号本身不属 于串，只起界定作用。 由一个或多个空格组成的串称为空格串。 Date 串的基本操作和线性表区别很大。 线性表: 大多以“单个元素”为操作对象 串: 通常以“串的整体”为操作对象 例:查找某个元素；插入某个元素；删除某个元素 例: 查找某个子串；截取某个子串； 在某个位置插入、删除某个子串 串的逻辑结构和线性表相似，故看作一种线性表。 s = a1a2 an ( n0) Date 2. 串的抽象数据类型的定义 ClearString( HString num ； char itemMaxLineLen ； int length ； # define MaxBookNum 1000 # define MaxLineLen 500 typedef struct char * ch ； int length ； HString ； Date a an of the 常用词 方便查找 采用顺序结构 # define MaxWordLen 10 Typedef struct char chMaxWordLen ； int length ； ; # define MaxWordNum 100 Date 关键词键词书书号索引 Analysis Computer Data Introduction Numerical Structure 067 005 005，010 010 067 005，010 方便插入 采用链式结构 Typedef struct LNode LinkNode; HString keyword ； LinkIdxList bnolist ； Struct Node * next ； # define MaxKeyNum 2500 Typedef struct LinkList ； LinkNode * head ； Int length ； Date 串的模式匹配 模式匹配是指子串的的定位运算，又称串匹配，是串中 常用且应用广泛的一种操作，一般将主串称为目标串S，子串 称为模式串t，如果在目标串S中找到模式串t，则模式匹配成 功。常用的算法如下： 一、简单模式匹配： 算法的基本思想：从目标串S=“S0S1S2SN-1的第一个字符 开始和模式串t=“t0t1t2.tm-1”中的第一个字符比较，若相 等，则继续逐个比较后续字符，否则从目标串的第二个字符 开始重新与模式串t的第一个字符进行比较，依次类推，若匹 配成功，则返回模式串t中第一个字符在目标串s 中的位置， 否则匹配失败。 Date 最坏情况下，每次比较都在最后出现不等，最多比较n-m+1趟， 总比较次数为m(n-m+1),最坏情况下的时间复杂度为: O（n m) 例如：s=“aaaaaaaaaaaab” t=“aab” 简单模式匹配算法如下： int index (Sstring s, Sstring t,int pos) i=pos;j=1; while (i= t0)return i- t0; else return 0; Date 二、模式匹配的一种改进算法（KMP) 简单模式匹配算法的比较次数较大，原因在于目标串的检测指 针需要回溯。 KMP算法的改进在于：每一趟匹配过程中出现字符比较时， 不需回溯I指针而是利用已经得到的部分匹配的结果将模式向 右“滑动”尽可能远的一段距离，继续进行比较。 Date 例： i =3 第一趟：a b a b c a b c a c b a b a b c j=3 第二趟：a b a b c a b c a c b a b i i =7 a b c a c j=5 第三趟：a b a b c a b c a c b a b i i =11 (a) b c a c j=2 j=6 Date 一般情况下若令nextj=k，则nextj表明当模式中第j个字符与 主串中相应字符失配时，在模式中需重新和主串中该字符进行 比较的字符的位置。 nextj定义如下： nextj= 0 当j=1时 Maxk|1T0) return I-T0; Else return 0 Date 例： i =2 第一趟：a c a b a a b a a b c a c a a b c a b j=2 next2=1 第三趟 a c a b a a b a a b c a c a a b c i =2 a j=1 i =3 i =8 a b a a b c j=1j=6 next1=0 第二趟 a c a b a a b a a b c a c a a b c next6=3 Date 三、Next函数求值 Next函数只与模式串有关，与主串无关。用递推法求得。 Next1=0 设nextj=k,若tk=tj,则nextj+1=nextj+1=k+1; 否则把计算nextj+1的值看作模式匹配问题，将模式串向右 滑动至k=nextk(0kk)若tj=pk,则nextj+1=k+1=nextk+1, 若tj pk，则继续右滑到k”=nextk,依次类推，直到某次匹配 成功或最后失败，则失败时next0+1=-1+1=0 例： j 1 2 3 4 5 6 7 8 模式 a b a a b c a c nextj 0 1 1 2 2 3 1 2 (a b a) Date j 1 2 3 4 5 6 7 8 模式 a b a a b c a c nextj 0 1 1 2 2 3 1 2 (a b a) Next1=0; Next2=next1+1=1; Next3=next2+1=1 /next2=1(k) , p1 p2 ,k=nextk=next1=0 Next4=next3+1=2 / next3=1 ,p1=p3 ,next3+1=k+1=1+1=2; Next5=next4+1 /next4=2(k);p2p4 ,k=nextk=next2=1,p1=p4 Next5 =next4+1=k+1=1+1=2; Date Next6=next5+1 =3/ next5=2 ,p2=p5 =2+1=3 next1=0 Next7=next6+1=1 / next6=3,p3 p6 ,k=nextk=next3=1,next1=0,next7=0+1=1 Date 求next 函数值的算法： Get _next (Sstring T ,int next1=0; j=0; while(iT0) if(j= =0| T i = =Tj) + i; + j ; nexti=j; else j=nextj; Date Nextvalj= Nextk nextj=k 且tj=tk Nextj 其它 例：已知s1=aaab,s2=abcabaa, 分别求出它们的Next函数和Nextval 函数值 j1234 s1aaab Nextj 0123 Nextvalj 0003 四、Next的 修正值Nextval Date