数据结构-串、数组和广义表课件.pptVIP

广义表是一个多层次的线性结构。 例如：有A、B、C、D、E五个广义表的描述如下： A = () A是一个空表，它的长度为零 B = (e) 列表B只有一个原子e，B的长度为1 C = (a，(b，c，d)) 列表C的长度为2，两个元素分别为原子a和子表( b，c，d ) D = (A，B，C) 列表D的长度为3，三个元素都是列表,显然,将子表的值代入后，则有D =(( )，( e )，( a，( b，c，d ))) E = (a，E) 这是一个递归的表,它的长度为2，E相当于一个无限的列表E = ( a，( a，( a，...))) 广义表的结构特点： 1) 广义表中的数据元素有相对次序。 2) 广义表的长度定义为最外层包含的元素个数。 3) 广义表的深度定义为所含括弧的重数。 注意：“原子”的深度为“0”；“空表”的深度为1。 4) 表头可以是原子或列表；表尾必定是列表。 5) 广义表可以是一个递归的表；递归表的深度是无穷值，长度是有限值。 6) 任何一个非空广义表 LS = ( ?1，?2，…，?n ) 均可分解为表头Head( LS ) = ?1和表尾Tail( LS ) = ( ?2，…，?n ) 两部分。 广义表的基本运算 （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 求下列广义表操作的结果： （1）GetHead( ( a，b，c ) ) （2）GetTail( ( a，b，c，d ) ) （3）GetHead( ( ( a，b )，( d ) ) ) （4）GetTail( ( ( a，b )，( d ) ) ) （5）GetHead( GetTail( ( ( a，b )，( c，d ) ) ) ) （6）GetTail ( GetHead( GetTail( ( ( a，b )，( c，d ) ) ) ) ) （1）a （2）(b,c,d) （3）(a,b) （4）((d)) （5）(c,d) （6）(d) 例如： 已知广义表LS=（a，（b，c，d），c），运用GetHead和GetTail函数取出原子d的运算过程为： GetHead( GetTail( GetTail( GetHead( GetTail( LS ))))) 注意广义表（ ）和( ( ) )不同。前者是长度为0的空表，对其不能做求表头的和表尾的运算；而后者是长度为1的非空表（只不过该表中唯一的一个元素是空表）。对其可进行分解，得到表头和表尾均为空表（ ）。 5.5 广义表的表示方法 头、尾指针的链表结构 构造存储结构的两种分析方法: 有次序性 有长度 有深度 可递归 可共享 一个直接前驱和一个直接后继 ＝表中元素个数 ＝表中括号的重数 自己可以作为自己的子表 可以为其他广义表所共享 广义表的特点 小 结 串类型的定义 串的定义，特点，串的抽象数据类型定义 串的表示和实现 定长顺序存储表示 堆分配存储表示 块链存储表示 串的模式匹配定义 ?数组 定义，特点 数组元素存储位置的计算 广义表的定义，特点 * * * 利用已经部分匹配的结果而加快模式串的滑动速度？ 且主串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’ i i i k k a b a a b c k i i KMP算法设计思想（了解） 串操作应用举例－－文本编辑 文本可被看作一个字符串，称为文本串 页则是文本串