三、建广义表的存储结构

　　和第6章讨论的建立二叉树和树的存储结构类似，算法取决于输入的方式。

　　假设以串s="(α1，α2，…，αn)"的形式输入广义表，其中αi 为第 i 个子表串，且设空表串为"( )"，单原子以单个小写字母表示。

　　仍以分治法的思想分析这个算法的基本思想：去除串s中首尾一对括弧之后，将它分割成 n 个子串，每个子串αi 定义一个子表，从而引出 n 个子问题，即分别由每个子串建立一个子表。若由串 s 求得指向广义表的头指针L，则由子串αi 求得指向第 i 个子表的头指针，通过 n 个表结点可将这 n 个子表组合成一个广义表。

　如上所述的从串 s 建立广义表的存储结构的大致过程可如下描述：
　　若串 s 为"空表串"，则返回"空指针"；
　　建表结点 *L，并令指针 p=L；
　　令脱去串s的外层括弧得到的子串名为 sub；
　　do{
　　　从串 sub 中分离出子串αi，并从 sub 中删除该子串；
　　　建立相应子表，其头指针为 p->ptr.hp；
　　　若剩余的串 sub "不是空串"，
　　　　则建表结点 p->ptr.tp，并令 p=p->ptr.tp；
　　}while(sub 为"空串")；
　　设置"空表尾"，即令 p->ptr.tp=NULL。

　其中建子表 p->ptr.hp 的操作过程为：
　　若（串αi 的长度为1）
　　则建原子结点，原子数据即为子串αi；
　　否则由串αi 递归建广义表；

算法8.3
　　Glist CreateGList( String S)
　{
　　// 建立由串 s 确定的广义表的存储结构，返回指向该广义表的头指针
　　if (StrCompare(s,"( )") return NULL;　// 创建空表
　　else {
　　　L = new GLNode;　　　　　　　　　　　　// 生成表结点
　　　L->tag=List; p=L; sub=SubString(S,2,StrLength(S)-1);
　　　　　　　　　　　　　　　　　　　　　 // 脱去串 S 的外层括弧
　　　do {

  

　　可见，这个算法的关键是找出广义表的头指针和各子表的头指针的关系。

　　假设从左至右自串 s 中先后分离出各个子表串，即按 i=1,2,…,n 的顺序建立各个子表，假设由串 s 建立的广义表的头指针为 L，则若该广义表为非空表的话，其第一个子表的头指针显然应该是L->ptr.hp。动画

　　而相邻两个子表之间需要通过"表结点"相链接。动画

　　通过例子看如何从串 s 逐个分离出子串建立子表的过程。动画		  
  　　　　sever(sub, hsub); 　　　　　　　　　　// 分离出子表串 hsub=αi
　　　　if (StrLength(hsub)==1) {
　　　　　p->ptr.hp=new GLNode;
　　　　　p->ptr.hp->tag=ATOM;
　　　　　p->ptr.hp->atom=hsub;　　　　　　　// 创建单原子结点
　　　　} // if
　　　　else p->ptr.hp = CreateGList(hsub);　// 递归建广义表
　　　　if (!StrEmpty(sub) {
　　　　　p->ptr.tp = newGLNode;　　　// 建下一个子表的表结点*(p->ptr.tp)
　　　　　p=p->ptr.tp;
　　　　}
　　　}
　　　while (!StrEmpty(sub));p->ptr.tp = NULL; // 设定表尾为空表
　　　　return L;
　　} // else
　} // CreateGList		   　函数server的说明：
　　若sub=2( ),(x,y),((x))2,
　　则函数server的运行结果为：
　　hsub=2( )2,sub=2(x,y)((x))2