数据结构：深入理解广义表常用的两种存储结构（头尾链，孩子兄弟链）

深入学习广义表的两种存储结构，还有遇到空表时候画图，主要将两种结构给放在一期进行比较；巩固学习知识，特别是表尾要注意加一层，还有头尾链空表时候破坏层次结构。最后写广义表的算法一定要掌握递归。

Leisure_水中鱼

6256人浏览 · 2023-05-05 17:35:05

Leisure_水中鱼 · 2023-05-05 17:35:05 发布

前言：

广义表内的元素有两种：原子，广义表；很难顺序结构，因此通常都是链结构。

对于同一逻辑结构可以有不同的存储结构，(表)头(表)尾链，孩子兄弟链都是链式存储结构，但是其中的结点构成不一样，因此都是链式也不能说是相同的存储结构。

结点和定义结构体

头尾链（如图1）：

原子结点：tag=0（表示此节点为原子型）data用于存放数据

表结点：tag=1（表示表结点）指针head用于指向表头，指针tail用于指向表尾

可以定义为两个结构体：不过我认为这样麻烦因为还是无法避免需要共用体,表头可以能是表，也可能是原子，更长用的是下面定义一个结构体

typedef char Elemtype;

typedef struct {
    int tag;
    Elemtype data;
} Atom;

typedef struct node {
    int tag;
    union {
        struct node * gl;
        Atom * atom;
    } head;
    struct node * tail;
} Glist;

定义一个结构体：

typedef char Elemtype; 

//广义表采用表头表尾链的方式存储
typedef struct Node{
	int tag;						//0表示原子，1表示广义表 
	union {
		Elemtype data;				//共用体，tag值0，存放原子数据 
		struct {			//tag值1 
			struct Node * head;		//指向表头的指针 
			struct Node * tail;		//指向表尾的指针 
		} Link;
	};
} GLNode, *Glist;

tag和一个共用体，data和结构体Link公用一段空间，结构体Link里包含head和tail指针，如图2

孩子兄弟链（如图3）：

原子结点：tag，data（存放元素），link（指向兄弟结点）

表结点：tag，sublist（存放子表），link

结构体的定义就是data和sublist共用体，就不放图了，看看代码：

typedef char Elemtype; 

//广义表采用孩子兄弟链的方式存储
typedef struct Node{
	int tag;						//0表示原子，1表示广义表 
	union {
		Elemtype data;				//共用体，tag值0，存放原子数据 
		struct Node * sublist;
	};
    struct Node * link;
} GLNode, *Glist;