第5章 数组和广义表(3学时)解析.ppt

int GlistDepth(Glist L) { // 返回指针L所指的广义表的深度 for (max=0, pp=L; pp; pp=pp-ptr.tp){ dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; } return max + 1; } // GlistDepth if (!L) return 1; if (L-tag == ATOM) return 0; 1 1 1 L … ? for (max=0, pp=L; pp; pp=pp-ptr.tp){ dep = GlistDepth(pp-ptr.hp); if (dep max) max = dep; } 例如: pp pp-ptr.hp pp pp pp-ptr.hp pp-ptr.hp 例二 复制广义表 新的广义表由新的表头和表尾构成 可以直接求解的两种简单情况为： 空表复制求得的新表自然也是空表; 原子结点可以直接复制求得。 将广义表分解成表头和表尾两部分，分别(递归)复制求得新的表头和表尾 若 ls= NIL 则 newls = NIL 否则 构造结点 newls, 由 表头ls-ptr.hp 复制得 newhp 由 表尾 ls-ptr.tp 复制得 newtp 并使 newls-ptr.hp = newhp, newls-ptr.tp = newtp 复制求广义表的算法描述如下: Status CopyGList(Glist T, Glist L) { if (!L) T = NULL; // 复制空表 else { if ( !(T = (Glist)malloc(sizeof(GLNode))) ) exit(OVERFLOW); // 建表结点 T-tag = L-tag; if (L-tag == ATOM) T-atom = L-atom; // 复制单原子结点 else { } } // else return OK; } // CopyGList 分别复制表头和表尾 CopyGList(T-ptr.hp, L-ptr.hp); // 复制求得表头T-ptr.hp的一个副本L-ptr.hp CopyGList(T-ptr.tp, L-ptr.tp); // 复制求得表尾T-ptr.tp 的一个副本L-ptr.tp 语句 CopyGList(T-ptr.hp, L-ptr.hp); 等价于 CopyGList(newhp, L-ptr.tp); T-ptr.hp = newhp; 例三 创建广义表的存储结构 对应广义表的不同定义方法相应地有不同的创建存储结构的算法。 假设以字符串 S = ?(?1, ?2, ???, ?n )? 的形式定义广义表 L，建立相应的存储结构。 由于S中的每个子串?i定义 L 的一个子表，从而产生 n 个子问题，即分别由这 n个子串 (递归)建立 n 个子表，再组合成一个广义表。 可以直接求解的两种简单情况为： 由串?( )?建立的广义表是空表； 由单字符建立的子表只是一个原子结点。 如何由子表组合成一个广义表？ 首先分析广义表和子表在存储结构中的关系。 先看第一个子表和广义表的关系: 1 L 指向广义表 的头指针 指向第一个 子表的头指针 再看相邻两个子表之间的关系: 1 1 指向第i+1个 子表的头指针 指向第i个 子表的头指针 可见，两者之间通过表结点相链接。 若 S = ?( )? 则 L = NIL； 否则，构造第一个表结点 *L， 并从串S中分解出第一个子串?1，对应创建第一个子广义表 L-ptr.hp； 若剩余串非空，则构造第二个表结点 L-ptr.tp，并从串S中分解出第二个子串 ?2，对应创建第二个子广义表 ……； 依次类推，直至剩余串为空串止。 void CreateGList(Glist L,