《第4章-串、数组和广义表》由会员分享，可在线阅读，更多相关《第4章-串、数组和广义表（58页珍藏版）》请在金锄头文库上搜索。
1、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)-零个或多个字符组成的有
2、限序列,串名,串值,串长,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) /求子串
3、(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; /若串非空,则按串长分配存
4、储区, /否则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; /串的当前长度 LStr
5、ing;,链式存储表示,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个字符和模式的第一个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符起，
6、重新与模式的第一个字符比较。,直到主串的一个连续子串字符序列与模式相等 。返回值为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次
7、最后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算法的时间复杂
8、度可以达到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,这实际上也是一个匹配的
9、过程， 不同在于：主串和模式串是同一个串,求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，该模式
10、串的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日,串操作应用举例文本编辑,文本可被看作一个字符串，称
11、为文本串 页则是文本串的子串 行又是页的子串。,进阶任务 （完成每任务加经验值100）,请把下面名词术语翻译成英文，并大声读与拼写出来： 串 空串 空格串 子串 主串 存储密度 穷举 数组 矩阵 对称矩阵 三角矩阵 对角矩阵 稀疏矩阵 广义表,string,Null string,Blank string,Substring,Masterstring,Storage density,Brute-Force,Array,Matrix,Symmetric matrix,Triangular matrix,Diagonal matrix,Sparse matrix,Generalized List,
12、进阶任务（每任务200经验值）,1.数组的逻辑特征是什么？一般数组能否做数据元素的插入或删除操作？ 2.矩阵是什么？与数组有什么关系？ 3.什么叫特殊矩阵？什么叫稀疏矩阵？,多维线性特征，即每一维均有线性特征。数组可采用递归方法定义，即数组表中的数据元素均是同维与等长的数组。,在数学名词中，矩阵用来表示统计数据等方面的各种有关联的数据。通常在编程时，采用二维数组来存储矩阵元。,特殊矩阵是矩阵元分布有特殊规律的矩阵，如对称矩阵、三角矩阵。 矩阵中非零值元素非常少的矩阵称之为稀疏矩阵。,进阶任务（每任务200经验值）,什么叫广义表？它和线性表有和相同和不同之处？ 什么是广义表的表头、表尾、表长、表
13、深？ 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日,数组的抽象数据类型,数据对象:,数据关系:,AD
14、T 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
