数据结构第四章剖析.ppt

广义表的基本运算 （1）求表头GetHead(L)：非空广义表的第一个元素，可以是一个单元素，也可以是一个子表 （2）求表尾GetTail(L)：非空广义表除去表头元素以外其它元素所构成的表。表尾一定是一个表 练习 A=( ) 　　　　　　　 GetHead和GetTail均无定义　　　　　　　 A=(a,b) 　　　　　　　 GetHead(A)=a GetTail(A)=(b) 　　　　　　　 A=(a) 　　　　　　　 GetHead(A)=a GetTail(A)=( ) 　　　　　　　 A=((a)) 　　　　　　　 GetHead(A)=(a) GetTail(A)=( ) 　　　　　　　 GetHead(GetTail(GetHead(GetTail(GetTail(A))))) 　　　　　　　 A=(a,b,(c,d),(e,(f,g))) 　　　　　　　 d 有次序性 有长度 有深度 可递归 可共享 一个直接前驱和一个直接后继 ＝表中元素个数 ＝表中括号的重数 自己可以作为自己的子表 可以为其他广义表所共享 广义表的特点 E=(a,E)=(a,(a,E))= (a,(a,(a,…….)))，E为递归表 1）A =( ) 2）B = ( e ) 3）C =( a ,( b , c , d ) ) 4）D=( A , B ,C ) 5）E=(a, E) n=0，因为A是空表 n=1，表中元素e是原子 n=2，a 为原子，(b,c,d)为子表 n=3，3个元素都是子表 n=2，a 为原子，E为子表 D=(A,B,C)=(( ),(e),(a,(b,c,d)))，共享表 练习：求下列广义表的长度 4.6 案例分析与实现 案例4.1 ：病毒感染检测 【案例分析】 因为患者的DNA和病毒DNA均是由一些字母组成的字符串序列，要检测某种病毒DNA序列是否在患者的DNA序列中出现过，实际上就是字符串的模式匹配问题。 可以利用BF算法，也可以利用更高效的KMP算法。 但与一般的模式匹配问题不同的是，此案例中病毒的DNA序列是环状的。 这样需要对传统的BF算法或KMP算法进行改进。 【案例实现】 对于每一个待检测的任务，假设病毒DNA序列的长度是m，因为病毒DNA序列是环状的，为了线性取到每个可行的长度为m的模式串，可将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次。 然后循环m次，依次取得每个长度为m的环状字符串，将此字符串作为模式串，将人的DNA序列作为主串，调用BF算法进行模式匹配。 只要匹配成功，即可中止循环，表明该人感染了对应的病毒；否则，循环m次结束循环时，可通过BF算法的返回值判断该人是否感染了对应的病毒。 【算法步骤】 ① 从文件中读取待检测的任务数num。 ② 根据num个数依次检测每对病毒DNA和人的DNA是否匹配，循环num次，执行以下操作： 从文件中分别读取一对病毒DNA序列和人的DNA序列； 设置标志性变量flag，用来标识是否匹配成功，初始为0，表示未匹配； 病毒DNA序列的长度是m，将存储病毒DNA序列的字符串长度扩大为2m，将病毒DNA序列连续存储两次； 循环m次，重复执行以下操作： 依次取得每个长度为m的病毒DNA环状字符串； 将此字符串作为模式串，将人的DNA序列作为主串，调用BF算法进行模式匹配，将匹配结果返回赋值给flag； 若flag非0，表示匹配成功，中止循环，表明该人感染了对应的病毒。 退出循环时，判断flag的值，若flag非0，输出“YES”，否则，输出“NO”。 1. 了解串的存储方法，理解串的两种模式匹配算法，重点掌握BF算法。 2. 明确数组和广义表这两种数据结构的特点，掌握数组地址计算方法，了解几种特殊矩阵的压缩存储方法。 3.掌握广义表的定义、性质及其GetHead和GetTail的操作。 小结 * * * * * 北京林业大学信息学院 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算法设计思想 将主串的第pos个字符和模式的第一个字符比较， 若相等，继续逐个比较后续字符； 若不等，从主串的下一字符起，重新与模式的第一个字符比较。 直到主串的一个连续子串字符序列与模式相等 。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。 否则，匹配失败，返回值 0 BF算法设计思想 Index(S,T,pos) int Ind