数组矩阵习题课

模式串T= ‘abcaabbcabcaabdab’ , T的next数组值及nextval数组值为(01112231123456712和01102131011021701)

a b c a a b b c a b c a a b d a b
maxl
0 0 0 1 1 2 0 0 1 2 3 4 5 6 0 1 2
next
0 1 1 1 2 2 3 1 1 2 3 4 5 6 7 1 2
nextval
0 1 1 0 2 1 3 1 0 1 1 0 2 1 7 0 1

例子:
模式串 a b a a b c a c

  next值 0 1 1 2 2 3 1 2

  nextval值 0 1 0 2 1 3 0 2

  1.第一位的nextval值必定为0,第二位如果于第一位相同则为0,如果不同则为1。

  2.第三位的next值为1,那么将第三位和第一位进行比较,均为a,相同,则,第三位的nextval值为0。

  3.第四位的next值为2,那么将第四位和第二位进行比较,不同,则第四位的nextval值为其next值,为2。

  4.第五位的next值为2,那么将第五位和第二位进行比较,相同,第二位的next值为1,则继续将第二位与第一位进行比较,不同,则第五位的nextval值为第二位的next值,为1。

  5.第六位的next值为3,那么将第六位和第三位进行比较,不同,则第六位的nextval值为其next值,为3。

  6.第七位的next值为1,那么将第七位和第一位进行比较,相同,则第七位的nextval值为0。

  7.第八位的next值为2,那么将第八位和第二位进行比较,不同,则第八位的nextval值为其next值,为2。

总而言之,next和nextval数组的前两位一定是01;
next数组从第三位开始,取此位前一位next数组中的值,找字符串中此值作为序号的字符,与前一位字符进行比较。若相同,为前一位next值+1;若不同,重复上述步骤(这里是再往前取一位),直到序号1都不同的话,取next值为1.
nextva数组从第三位开始,取这一位next数组中的值,找字符串中此值作为序号的字符x,与这一位进行比较。不同,则这一位的next值就是其nextval值;若相同,重复上述步骤(这里是将x,与x的next值对应的序号字符比较),直到序号1都相同的话,nextval值为0.
两者特征可以简单记为:next求同最小为1;nextval求异最小为0

char s[6]=”Hello!”是不合法的。

忽略了字符串的大小要比字符串中的字符数多1这一点,会造成数组的越界

KMP算法的特点是在模式匹配时指示主串的指针不会变小。 

KMP匹配时,主串的指针当匹配时会递增,不匹配时会停住不动,也正是因为主串指针没有回滚,KMP的匹配效率才得以提升

设模式串的长度为m,目标串的长度为n,当n≈m且处理只匹配一次的模式时,朴素的匹配(即子串定位函数)算法所花的时间代价可能会更为节省

朴素的匹配只匹配一次,不用计算next数组,所以速度更快

有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组表示该矩阵时,所需的字节数是(66)

每个非零元素占3*2=6个字节,共10个非零元素,需6*10 = 60 个字节;

此外,还一般要用三个整数来存储矩阵的行数、列数和总元素个数,又需要3*2 = 6个字节;

总共:60 + 6 = 66 个字节。

假设以行序为主序存储二维数组A[1..100,1..100],设每个数据元素占两个存储单元,基地址为10,则LOC(A[5,5])=( 818  )。

注意基地址是第一个元素的地址,所以要-1

数组A[0..5,0..6]的每个元素占五个字节,将其按列优先次序存储在起始地址为1000的内存单元中,则元素A[5,5]的地址是(  1175    )。

与上一个题目的区别:数组从0开始算,所以这实际上是一个6行7列的数组;是列优先而不是习惯的行优先
综上,计算数组中某个元素地址时,要注意数组从0还是1开始,行优先还是列优先,基地址是第一个元素的地址要减一

理解下数据的结构

首先明确数据具有逻辑结构和存储结构。
逻辑结构指数据元素之间的逻辑关系,有四种关系:集合结构、一对一的线性结构、一对多的树型结构、多对多的图状结构。
存储结构指数据实际存放在计算机中的物理结构,只有两种形式:顺序存储、非顺序存储。
任何一种逻辑结构都可以使用顺序存储或者非顺序存储。

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据