资源预览内容
第1页 / 共58页
第2页 / 共58页
第3页 / 共58页
第4页 / 共58页
第5页 / 共58页
第6页 / 共58页
第7页 / 共58页
第8页 / 共58页
第9页 / 共58页
第10页 / 共58页
亲,该文档总共58页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
2019年7月1日,第4章 串、数组和广义表,4.1 串 4.2 数组 4.3 广义表,教学内容,2019年7月1日,1. 掌握串的存储方法,理解串的两种模式匹配算法; 2. 明确数组和广义表这两种数据结构的特点,掌握数组存储时地址计算方法,了解几种特殊矩阵的压缩存储方法。,教学目标,1. 了解串的存储方法,理解串的两种模式匹配算法,重点掌握BF算法。 2. 明确数组和广义表这两种数据结构的特点,掌握数组地址计算方法,了解几种特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和GetTail的操作。,2019年7月1日,4.1 串,串(String)-零个或多个字符组成的有限序列,串名,串值,串长,n,空串,n=0,2019年7月1日,a=BEI, b=JING c=BEIJING d=BEI JING,子串,字符位置,主串,子串位置,串相等,空格串,2019年7月1日,数据对象:,数据关系:,基本操作:,(1) StrAssign (&T,chars) /串赋值 (2) StrCompare (S,T) /串比较 (3) StrLength (S) /求串长 (4) Concat(&T,S1,S2) /串联,ADT String ,串的抽象数据类型,2019年7月1日,北京林业大学信息学院,(5) SubString(&Sub,S,pos,len) /求子串 (6) StrCopy(&T,S) /串拷贝 (7) StrEmpty(S) /串判空 (8) ClearString (&S) /清空串 (9) Index(S,T,pos) /子串的位置 (11) Replace(&S,T,V) /串替换 (12) StrInsert(&S,pos,T) /子串插入 (12) StrDelete(&S,pos,len) /子串删除 (13) DestroyString(&S) /串销毁 ADT String,2019年7月1日,顺序存储 链式存储,串的存储结构,2019年7月1日,typedef struct char *ch; /若串非空,则按串长分配存储区, /否则ch为NULL int length; /串长度 HString;,顺序存储表示,2019年7月1日,链式存储表示,2019年7月1日,可将多个字符存放在一个结点中,以克服其缺点,优点:操作方便 缺点:存储密度较低,链式存储表示,2019年7月1日,#define CHUNKSIZE 80 /可由用户定义的块大小 typedef struct Chunk char chCHUNKSIZE; struct Chunk *next; Chunk; typedef struct Chunk *head,*tail; /串的头指针和尾指针 int curlen; /串的当前长度 LString;,链式存储表示,2019年7月1日,算法目的:,确定主串中所含子串第一次出现的位置(定位) 即如何实现教材P72 Index(S,T,pos)函数,串的模式匹配算法,2019年7月1日,S : a b a b c a b c a c b a b T : a b c,i,j,S : a b a b c a b c a c b a b T : a b c,S : a b a b c a b c a c b a b T : a b c,i指针回溯,BF算法设计思想,2019年7月1日,将主串的第pos个字符和模式的第一个字符比较, 若相等,继续逐个比较后续字符; 若不等,从主串的下一字符起,重新与模式的第一个字符比较。,直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号,即匹配成功。 否则,匹配失败,返回值 0,BF算法设计思想,Index(S,T,pos),2019年7月1日,int Index(Sstring S,Sstring T,int pos) i=pos; j=1; while (iT 0 ) return iT0; else return 0; ,BF算法描述(算法4.1),2019年7月1日,若n为主串长度,m为子串长度,最坏情况是,BF算法时间复杂度,主串前面n-m个位置都部分匹配到子串的最后一位,即这n-m位各比较了m次 最后m位也各比较了1次,总次数为:(n-m)*m+m(n-m+1)*m 若mn,则算法复杂度O(n*m),例: S=0000000001,T=0001,pos=1,2019年7月1日,利用已经部分匹配的结果而加快模式串的滑动速度, 且主串S的指针i不必回溯!亲!可提速到O(n+m)哦!,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,S=a b a b c a b c a c b a b,T=a b c a c,a b a,a b c,KMP算法设计思想(了解),KMP算法的时间复杂度可以达到O(m+n),当 Si Tj 时,已经得到的结果: Si-j+1i-1 = T1j-1 若已知 T1k-1 = Tj-k+1j-1 则有 Si-k+1i-1 = T1k-1,三、KMP(D.E.Knuth, V.R.Pratt, J.H.Morris) 算法,定义:模式串的next函数,int Index_KMP(SString S, SString T, int pos) / 1posStrLength(S) i = pos; j = 1; while (i T0) return i-T0; / 匹配成功 else return 0; / Index_KMP,这实际上也是一个匹配的过程, 不同在于:主串和模式串是同一个串,求next函数值的过程是一个 递推过程,分析如下:,已知:next1 = 0;,假设:nextj = k;又 Tj = Tk,则: nextj+1 = k+1,若: Tj Tk 则需往前回朔,检查 Tj = T ?,void get_next(SString / get_next,还有一种特殊情况需要考虑: 例如: S = aaabaaabaaabaaabaaab T = aaaab nextj= 01234,nextvalj=00004,void get_nextval(SString / get_nextval,模式串t=abcaabbca,该模式串的next数组的值是( ),nextval数组的值是( ) A. 0 1 1 1 2 2 1 1 1 B. 0 1 1 1 2 1 2 1 1 C. 0 1 1 1 0 0 1 3 1 D. 0 1 1 1 2 2 3 1 1 E. 0 1 1 0 0 1 1 1 0 F. 0 1 1 0 2 1 3 1 0,D,F,j=1 2 3 4 5 6 7 8 9 a b c a a b b c a,nextj=0,1,1,1,2,2,3,1,1,nextvalj=0,1,1,1,0,2,2,1,3,1,1,0,每空200经验值,2019年7月1日,串操作应用举例文本编辑,文本可被看作一个字符串,称为文本串 页则是文本串的子串 行又是页的子串。,进阶任务 (完成每任务加经验值100),请把下面名词术语翻译成英文,并大声读与拼写出来: 串 空串 空格串 子串 主串 存储密度 穷举 数组 矩阵 对称矩阵 三角矩阵 对角矩阵 稀疏矩阵 广义表,string,Null string,Blank string,Substring,Masterstring,Storage density,Brute-Force,Array,Matrix,Symmetric matrix,Triangular matrix,Diagonal matrix,Sparse matrix,Generalized List,进阶任务(每任务200经验值),1.数组的逻辑特征是什么?一般数组能否做数据元素的插入或删除操作? 2.矩阵是什么?与数组有什么关系? 3.什么叫特殊矩阵?什么叫稀疏矩阵?,多维线性特征,即每一维均有线性特征。数组可采用递归方法定义,即数组表中的数据元素均是同维与等长的数组。,在数学名词中,矩阵用来表示统计数据等方面的各种有关联的数据。通常在编程时,采用二维数组来存储矩阵元。,特殊矩阵是矩阵元分布有特殊规律的矩阵,如对称矩阵、三角矩阵。 矩阵中非零值元素非常少的矩阵称之为稀疏矩阵。,进阶任务(每任务200经验值),什么叫广义表?它和线性表有和相同和不同之处? 什么是广义表的表头、表尾、表长、表深? P9192选择题,综合应用题(1)(3)(4)(5)。,广义表LS = ( 1, 2, , n )是递归定义的线性结构, 其中:i 或为原子 或为广义表。而在线性表中i只能为原子。,当广义表LS = ( 1, 2, , n )非空,第一个元素1称为表头,剩余元素(2, , n )组成的子表称为表尾。 长度为最外层包含元素个数。深度为所含括弧的重数。,2019年7月1日,本节所讨论的数组与高级语言中的数组区别: 高级语言中的数组是顺序结构; 而本章的数组既可以是顺序的,也可以是链式结构,用户可根据需要选择。,4.2 数组,2019年7月1日,数组的抽象数据类型,数据对象:,数据关系:,ADT Array ,2019年7月1日,基本操作:,(1) InitArray (&A,n,bound1, boundn) /构造数组A (2) DestroyArray (&A) / 销毁数组A (3) Value(A,&e,index1,indexn) /取数组元素值 (4) Assign (A,&e,index1,indexn) /给数组元素赋值,ADT Array,2019年7月1日,一维数组,35 27 49 18 60 54 77 83 41 02,0 1 2 3 4 5 6 7 8 9,l l l l l l l l l l,LOC(i) = LOC(i-1)+l = a+i*l,LOC(i) =,LOC(i-1)+l = a+i*l, i 0,a, i = 0,a+i*l,a,2019年7月1日,二维数组,2019年7月1日,以行序为主序,C, PASCAL,数组的顺序存储,2019年7月1日,以列序为主序,FORTRAN,2019年7月1日,anm,设数组开始存放位置 LOC( 0, 0 ) = a LOC ( j, k ) = a + j * m + k,二维数组的行序优先表示,2019年7月1日,设有二维数组A10,20,其每个元素占两个字节, A00
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号