扫码获取更多资源

●创建广义表的头尾链表

算法设计

①假设把广义表的书写形式看成是一个字符序列S,那么S可能有下面两种情况：

S=()(带括号的空串)；

S=(a” a2,…，冬)，其中a；(i=l, 2,…，n)是S的子串。

对应于第一种情况，S的广义表为空表；对应于第二种情况，S的广义表中含有n个子 表，每个子表的书写形式即为子串aj(i=l, 2,…，n),此时可以类似于求广义表深度的操 作，分析由S建立的广义表和由ai(i=l, 2,…，n)建立的子表之间的关系。

如果创建广义表的头尾链表，则含有n个子表的广义表中有n个表结点序列。第i（i = 1, 2,…，n-1）个表结点中的表尾指针tp指向第i + 1个表结点；第n个表结点的表尾指 针tp为NULL0并且，如果把原子也看成是子表的话，则第i个表结点的表头指针hp指向 由a;（i=l, 2,…，n）建立的子表。因此，由S建立广义表头尾链表的问题就可以转化为由 a,（i=l, 2,…，n）建立子表的问题。

算法描述

在一般情况下使用的广义表大多数既不是递归表，也不为其他表所共享。对广义表可 以这样来理解，广义表中的一个数据元素可以是另一个广义表，一个m元多项式的表示就 是广义表的这种应用的典型实例。在第2章中讨论了一元多项式，一个一元多项式可以用 一个长度为m且数据元素有两个数据项（系数项和指数项）的线性表来表示。 将讨论如何表示m元多项式。

链式存储结构实现

联系我们：