一个广义表的算法 最后两个有问题？？？？
8 [bold]广义表[/bold]具有可共享性，因此在遍历一个[bold]广义表[/bold]时必需为每一个结点增加一个标志域mark，以记录该结点是否访问过。一旦某一个共享的子表结点被作了访问标志，以后就不再访问它。(1) 试定义该[bold]广义表[/bold]的类结构；
(2) 采用递归的算法对一个非递归的[bold]广义表[/bold]进行遍历。
(3) 试使用一个栈，实现一个非递归算法，对一个非递归[bold]广义表[/bold]进行遍历。
【解答】
(1) 定义[bold]广义表[/bold]的类结构
为了简化[bold]广义表[/bold]的操作，在[bold]广义表[/bold]中只包含字符型[bold]原子结点[/bold]，并用除[bold]大写字母[/bold]外的字符表示数据，表头结点中存放用[bold]大写字母[/bold]表示的表名。这样，[bold]广义表[/bold]中结点类型三种：表头结点、[bold]原子结点[/bold]和子表结点。
class GenList; //GenList类的前视声明
class GenListNode { //[bold]广义表[/bold]结点类定义
friend class Genlist;
private:
int mark, utype; // utype ＝0 / 1 / 2, mark是访问标记, 未访问为0
GenListNode* tlink; //指向同一层下一结点的指针
union { //联合
char listname; // utype = 0, 表头结点情形：存放表名
char atom; // utype = 1, 存放[bold]原子结点[/bold]的数据
GenListNode* hlink; // utype = 2, 存放指向子表的指针
} value;
public:
GenListNode ( int tp, char info ) : mark (0), utype (tp), tlink (NULL) //表头或[bold]原子结点[/bold]构造函数
{ if ( utype == 0 ) value.listname = info; else value.atom = info; }
GenListNode (GenListNode* hp ) //子表构造函数
: mark (0), utype (2), value.hlink (hp) { }
char Info ( GenListNode* elem ) //返回表元素elem的值
{ return ( utype == 0 ) ? elem->value.listname : elem->value.atom; }
};
class GenList { //[bold]广义表[/bold]类定义
private:
GenListNode *first; //[bold]广义表[/bold]头指针
void traverse ( GenListNode * ls ); //[bold]广义表[/bold]遍历
void Remove ( GenListNode* ls ); //将以ls为表头结点的[bold]广义表[/bold]结构释放
public:
Genlist ( char& value ); //构造函数, value是指定的停止建表标志数据
~GenList ( ); //析构函数
void traverse ( ); //遍历[bold]广义表[/bold]
} (2) [bold]广义表[/bold]遍历的递归算法
void GenList :: traverse ( ) { //共有函数
traverse ( first );
}
#include <iostream.h>
void GenList :: traverse ( GenListNode * ls ) { //私有函数, [bold]广义表[/bold]的遍历算法
if ( ls != NULL ) {
ls->mark = 1;
if ( ls->utype == 0 ) cout << ls->value.listname << '('; //表头结点
else if ( ls->utype == 1 ) { //[bold]原子结点[/bold]
cout << ls->value.atom;
if ( ls->tlink != NULL ) cout << ',';
}
else if ( ls->utype == 2 ) { //子表结点
if ( ls->value.hlink->mark == 0 ) traverse( ls->value.hlink ); //向表头搜索
else cout << ls->value.hlink->value.listname;
if ( ls->tlink != NULL ) cout << ',';
}
traverse ( ls->tlink ); //向表尾搜索
}
else cout << ')';
}
对上图所示的[bold]广义表[/bold]进行遍历，得到的遍历结果为A(C(E(x, y), a), D(E, e) )。
(3) 利用栈可实现上述算法的非递归解法。栈中存放回退时下一将访问的结点地址。
#include <iostream.h>
#include "stack.h"
void GenList :: traverse ( GenListNode *ls ) {
Stack <GenListNode<Type> *> st;
while ( ls != NULL ) {
ls->mark = 1;
if ( ls->utype == 2 ) { //子表结点
if ( ls->value.hlink->mark == 0 ) //该子表未访问过
{ st.Push ( ls->tlink ); ls = ls->value.hlink; } //暂存下一结点地址, 访问子表
else {
cout << ls->value.hlink->value.listname; //该子表已访问过, 仅输出表名
if ( ls->tlink != NULL ) { cout << ','; ls = ls->tlink; }
}
}
else {
if ( ls->utype == 0 ) cout << ls->value.listname << '('; //表头结点
else if ( ls->utype == 1 ) { //[bold]原子结点[/bold]
cout << ls->value.atom;
if ( ls->tlink != NULL ) cout << ',';
}
if ( ls->tlink == NULL ) { //子表访问完, 子表结束处理
cout >> ')';
if ( st.IsEmpty( ) == 0 ) { //栈不空
ls = st.GetTop ( ); st.Pop ( ); //退栈
if ( ls != NULL ) cout << ',';
else cout << ')';
}
}
else ls = ls->tlink; //向表尾搜索
}
}
}
(4) [bold]广义表[/bold]建立操作的实现
#include <iostream.h>
#include <ctype.h>
#include "stack.h"
const int maxSubListNum = 20; //最大子表个数
GenList :: GenList ( char& value ) {
Stack <GenListNode* > st (maxSubListNum); //用于建表时记忆回退地址
SeqList <char> Name (maxSubListNum); //记忆建立过的表名
SeqList <GenListNode * > Pointr (maxSubListNum); //记忆对应表头指针
GenListNode * p, q, r; Type ch; int m = 0, ad, br; //m为已建表计数, br用于对消括号
cout << "[bold]广义表[/bold]停止输入标志数据value : "; cin >> value;
cout << "开始输入[bold]广义表[/bold]数据, 如A(C(E( x, y ), a ), D(E(x, y), e) )"
cin >> ch; first = q = new GenListNode ( 0, ch ); //建立整个表的表头结点
if ( ch != value ) { Name.Insert (ch, m); Pointr.Insert (q, m); m++; } //记录刚建立的表头结点
else return 1; //否则建立空表, 返回1
cin >> ch; if ( ch == '(' ) st.Push ( q ); //接着应是'(', 进栈
cin >> ch;
while ( ch != value ) { //逐个结点加入
switch ( ch ) {
case '(' : p = new GenListNode <Type> ( q ); //建立子表结点, p->hlink = q
r = st.GetTop( ); st.Pop( ); r->tlink = p; //子表结点插在前一结点r之后
st.Push( p ); st.Push( q ); //子表结点及下一表头结点进栈
break;
case ')' : q->tlink = NULL; st.pop( ); //子表建成, 封闭链, 退到上层
if ( st.IsEmpty ( ) == 0 ) q = st.GetTop( ); //栈不空, 取上层链子表结点
else return 0; //栈空, 无上层链, 算法结束
break;
case ',' : break;
default : ad = Name.Find (ch); //查找是否已建立, 返回找到位置
if ( ad == -1 ) { //查不到, 建新结点
p = q;
if ( isupper (ch) ) { //[bold]大写字母[/bold], 建表头结点
q = new GenListNode ( 0, ch );
Name.Insert (ch, m); Pointr.Insert (q, m); m++;
}
else q = new GenListNode ( 1, ch ); //非[bold]大写字母[/bold], 建[bold]原子结点[/bold]
p->tlink = q; //链接
}
else { //查到, 已加入此表
q = Pointr.Get (ad); p = new GenListNode (q); //建立子表结点, p->hlink = q
r = st.GetTop ( ); st.Pop ( ); r->tlink = p; st.Push (p); q = p;
br = 0; //准备对消括号
cin >> ch; if ( ch == '(' ) br++; //若有左括号, br加1
while ( br == 0 ) { //br为0表示括号对消完, 出循环
cin >> ch;
if ( ch == '(' ) br++; else if ( ch == ')' ) br--;
}
}
}
cin >> ch;
}
}
第３个 非递归的 if ( ls->tlink != NULL ) { cout << ','; ls = ls->tlink; }处有问题 假如它是已访问的子表 且在最末 则此处不进行任何操作 结果会无限循环
第４个 建立的 完全看不懂
哪位高人指点一下？
