计算机上的非数值处理的对象基本上都是字符串数据.ppt_第1页
计算机上的非数值处理的对象基本上都是字符串数据.ppt_第2页
计算机上的非数值处理的对象基本上都是字符串数据.ppt_第3页
计算机上的非数值处理的对象基本上都是字符串数据.ppt_第4页
计算机上的非数值处理的对象基本上都是字符串数据.ppt_第5页
已阅读5页,还剩45页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论