Anyview数据结构-6

Posted on | Post modified: | In
Words count in article: 372 | Reading time ≈ 2

-广工Anyview题解
-数据结构部分-6
-广义表部分

/**
【题目】试按依次对每个元素递归分解的分析方法重写求广义表的深度的递归算法。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode hp, tp;
} ptr;
}un;
} GList;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
int GListDepth(GList ls)
/* Return the depth of list */
{
    int h1,h2;
    if(ls==NULL)
        return 1;
    if(ls->tag==ATOM)
        return 0;
    h1=GListDepth(ls->un.ptr.hp)+1;
    h2=GListDepth(ls->un.ptr.tp);
    return h1>h2?h1:h2;
              
}

/**
【题目】试编写判别两个广义表是否相等的递归算法。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode hp, tp;
} ptr;
}un;
} GList;
*/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Status Equal(GList A, GList B)
/* 判断广义表A和B是否相等,是则返回TRUE,否则返回FALSE */
{
   if(A->tag==ATOM&&B->tag==ATOM)
        if(A->un.atom==B->un.atom)
            return TRUE;
        else 
            return FALSE;
   else if(A->tag==LIST&&B->tag==LIST)
        if(Equal(A->un.ptr.hp,B->un.ptr.hp)&&Equal(A->un.ptr.tp,B->un.ptr.tp))
            return TRUE;
        else
            return FALSE;    
}

/**
【题目】试编写递归算法，输出广义表中所有原子项及其所在层次。
广义表类型GList的定义：
typedef enum {ATOM,LIST} ElemTag;
typedef struct GLNode{
ElemTag tag;
union {
char atom;
struct {
GLNode hp, tp;
} ptr;
}un;
} GList;
*/

1
2
3
4
5
6
7
8
9
10
11
12
void OutAtom(GList A, int layer, void(*Out2)(char, int))
/* 递归地用函数Out2输出广义表的原子及其所在层次,layer表示当前层次 */
{
   if(A){
        if(A->tag==ATOM)
            Out2(A->un.atom,layer);
        else{
            OutAtom(A->un.ptr.hp,layer+1,Out2);
            OutAtom(A->un.ptr.tp,layer,Out2);
        }
   }         
}
Thanks for your reward！