数据结构教程 第4章 数组、串与广义表.ppt

串的模式匹配 定义 在串中寻找子串（第一个字符）在串中的位置 词汇 在模式匹配中，子串称为模式，串称为目标。 示例 目标 T : “Beijing” 模式 P : “jin” 匹配结果 = 3 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 有次序性 有长度 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 结点类型 utype = 0, 附加头结点；= 1, 原子结点；= 2, 子表 值value utype=0时, 存放引用计数(ref)；utype=1时, 存放数据值(value)；utype=2时, 存放指向子表表头的指针(hlink) 尾指针tlink utype=0时, 指向该表第一个结点；utype?0时, 指向同一层下一个结点 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 这种存储结构的特点： 广义表中的所有表，不论是哪一层的子表，都带有一个附加头结点，空表也不例外。 所有位于同一层的表元素，在其存储表示中也在同一层。 最高一层的表结点个数（除附加头结点外）即为表的长度。 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) 4.5 广义表 (General Lists ) E B F 0 1 1 h 2 0 0 2 2 D ? ? 0 1 1 d 1 e 1 f ? 0 1 1 c 2 ? C ? 0 1 2 2 2 0 2 1 a D B B C A 1 b ? 0 1 A ? 4.5.2 广义表的存储结构的实现 templateclass T struct Items { //返回值的类结构定义 int utype; //＝0 / 1 / 2 union { //联合 int ref; T value; GenListNodeT* hlink; }info; Items( ): utpye(0), info.ref(0){ } //构造函数 Items(ItemT RL){utype=RL.utype;info=RL.info;} }; 4.5.2 广义表的存储结构的实现 返回值的类结构定义 templateclass T //广义表结点类定义 struct GenListNode{ public: GenListNode ( ) : utype (0), tlink (NULL), info.ref (0) { } GenListNode (GenListNodeT RL){utype=RL.utype, tlink =RL.tlink, info=RL.info; } private: int utype; GenListNodeT* tlink; union{ int ref; T value; GenListNodeT* hlink; }info; }; 广义表结点类定义 templateclass T //广义表结点类定义 class GenList { public: GenList( ) ; ~GenList( ); bool Head(Items x); bool Tail(GenListT It); GenListNodeT* First( ); GenListNodeT* Next(GenListNodeT* elem); void Copy(const GenListT R); int Length( ); int Depth( ); friend i