2022考研820数据结构复习

• 第四章 广义表
• • union共用体
  • 枚举型--enum
  • 广义表的数据结构
  • • 不带尾结点
    • 带尾结点
    • 求广义表深度

第四章 广义表

union共用体

union 共用体名{
    成员列表
};

struct和union的区别

• 结构体的各个成员占用不同的内存，互相之间没有影响；
• 共用体的成员列表占用同一段内存，分配内存时，以成员的最大内存分配；
• 共用体是内存覆盖，只能保存一个成员的值， 修改其中一个成员会影响其余所有成员。

枚举型–enum

代替#define对大量常数赋一个别名
一般定义方法

一般的定义方式如下：
typedef enum enum_type_name{
   ENUM_CONST_1,
   ENUM_CONST_2,
   ...
   ENUM_CONST_n
} enum__name;

• 第一个枚举成员的默认值为整型的0，后续枚举成员的值在前一个成员上加1
• 也可以给成员自定义值

广义表的数据结构

不带尾结点

typedef enum {ATOM, LIST} ElemTag;
typedef struct GLNode{
    ElemTag tag; //tag=0->Atom, tag=1->List
    union{
        int atom;
        struct{
            struct GLNode *hp, *tp;
        }ptr;
    };
} *GList;

带尾结点

typedef enum {ATOM, LIST} ElemTag;
typedef struct GLNode{
    ElemTag tag; //tag=0->Atom, tag=1->List
    union{
        int atom;
        struct GLNode *hp;
    };
    struct GLNode *tp; //原子结点的tp置为空
} *GList;

求广义表深度

递归思想

int GListDepth(GList L){
    if (!L) //空表
        return 1;  //空表深度为1
    if(L->tag == 0) //该表只有一个原子
        return 0; //原子深度为0
    int max = 0;
    GLNode *p = L;
    while(p){
        if(GListDepth(p->tp)>max) //求表尾深度
            max = GListDepth(p->tp);
        p = p->tp;
    }
    return max+1 ; //加这一层
}