数据结构PPT教学课件-第5章 数组和广义表.ppt

第5章数组和广义表 5.2 稀疏矩阵的三元组存储 5.3 稀疏矩阵的十字链表存储 5.4 广义表 5.5 迷宫问题 5.4.4 广义表的输出 在5.4.1节曾提及, 任何一个非空广义表均可分解成表头和表尾, 反之, 一对确定的表头和表尾可唯一确定一个广义表。由此, 要输出一个广义表只要分别输出表头和表尾即可, 广义表的输出也是一个递归过程。设需输出的广义表为LS, 广义表输出操作的递归定义为:  基本项: 当LS为空表时, 输出一对空的圆括号。  当LS指向原子元素时, 输出原子元素。  归纳项: 当LS指向列表时, 先输出表头, 后输出表尾。  若广义表以图5.4的链表表示, 由此可写出广义表输出的递归算法如算法5.6所示。  算法 5.6 Status OutGList(Glist L, int k) /*采用头尾链表存储结构, 把广义表输出 */ { if (!L) printf(%s, ( )); if (L-tag==ATOM) printf(%s, L-atom); if (k=0) printf(%c, (); OutGList(L-ptr.hp, 0); if (!L-ptr.tp) printf(%c, )); else { printf(%c, , ); OutGList(L-ptr.tp, 1); } } //OutGList 5.4.5 建立广义表的存储结构 假设把广义表的书写形式看成是一个字符串S。 广义表字符串S可能有两种情况: ① S=′( ) ′(带括弧的空白串); ② S=( a1, a2, …, an), 其中 ai(i=1, 2, …, n)是S的子串。对应于第一种情况, S的广义表为空表, 对应于第二种情况, S的广义表中含有n个子表, 每个子表的书写形式即为子串 ai(i=1, 2, …, n)。 此时, 可类似于求广义表的深度, 分析由S建立的广义表和由 ai(i=1, 2, …, n)建立的子表之间的关系。 假设按图5.4所示结点结构来建立广义表的存储结构, 则含有n个子表的广义表中有n个表结点序列，第i(i=1, 2, …, n-1)个表结点中的表尾指针指向第i+1个表结点, 第n个表结点的表尾指针为NULL, 并且, 如果把原子也看成是子表的话, 则第i个表结点的表头指针hp指向ai(i=1, 2, …, n)建立的子表。 由此, 由S建立广义表的问题可转化为由 ai(i=1, 2, …, n)建立子表的问题。又有, ai可能的三种情况: ① 带括弧的空白串; ② 长度为1的单字符串; ③ 长度1的字符串。 显然, 前两种情况为递归的终结状态, 子表为空表或只含有一个原子结点, 后一种情况为递归调用。由此, 在不考虑输入字符串可能出错的前提下, 可得下列建立广义表链表存储结构的递归定义：  基本项: 置空广义表 当S为空表串时 建原子结点的子表 当S为单字符串时 归纳项: 假设sub为脱去S中最外层括弧的子串, 记为′s1, s2, …sn′, 其中si(i=1, 2, …, n)为非空字符串。对每一个si建立一个表结点, 并令其hp域的指针为由si建立的子表的头指针, 除最后建立的表结点的尾指针为NULL外, 其余表结点的尾指针均指向在它之后建立的表结点。  假定函数sever(str, hstr)的功能为, 从字符串str中取出第一个“,”之前的子串赋给hstr, 并使str成为删去子串hstr和“,”之后的剩余串, 若str中没有字符“,”, 则操作后的hstr即为操作前的str, 而操作后的str为空串NULL。 根据上述递归定义可得到建立广义表存储结构的递归函数, 如算法5.7所示。函数sever如算法5.8所示。 算法 5.7 ? Status CreateGList(Glist L, sstring S)  /*采用头尾链表存储结构, 由广义表的书写形式串S创建广义表L, 设emp=( )*/ { if(StrCompare(S,