数据结构：深入理解广义表常用的两种存储结构（头尾链，孩子兄弟链） |
您所在的位置：网站首页 › 钥匙链结构图 › 数据结构：深入理解广义表常用的两种存储结构（头尾链，孩子兄弟链） |
数据结构：深入理解广义表常用的两种存储结构（头尾链，孩子兄弟链）
|
目录 前言： 结点和定义结构体 头尾链（如图1）： 孩子兄弟链（如图3）： 广义表结构图 头尾链存储结构（如图5）： 孩子兄弟存储结构（如图6）： 当有空表的时候： 优缺点： 头尾链结构优点： 头尾链结构缺点： 孩子兄弟链结构优点： 孩子兄弟链结构缺点： 前言：广义表内的元素有两种：原子，广义表；很难顺序结构，因此通常都是链结构。 对于同一逻辑结构可以有不同的存储结构，(表)头(表)尾链，孩子兄弟链都是链式存储结构，但是其中的结点构成不一样，因此都是链式也不能说是相同的存储结构。 结点和定义结构体 头尾链（如图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
原子结点：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; 广义表结构图广义表：LS = (a,(b,(c),d)); 设B = (c); A = (b,(c),d) = (b,B,d);（如图4）
LS的表头：原子a，表尾：广义表(A),注意是(A)不是A；（A）的表头：广义表A，表尾：^；A的表头：原子a，表尾：广义表(B,d)；(B,d)的表头：广义表B，表尾广义表(d)；B的表头：原子c，表尾：^；(c)的表头：原子c，表尾^； 孩子兄弟存储结构（如图6）：
sulist指针会指向第一个孩子，剩下的孩子都靠前一个“哥哥”的link指针链接 当有空表的时候：弄一个刁钻的广义表：LS = ((),(((),(()))))；
在有空表的头尾链结构存储会破坏广义表的层次结构 优缺点：我学疏才浅，就我目前的知识储备也不是很清楚优缺点，可以后来再补充，就目前看到的： 头尾链结构优点：1.存储空间更独立 2.第一层数量即为长度 3.除空表外head指针不为空，为空也是有空表，所以head指针一直有意义 头尾链结构缺点：1.第一个表头缺少“表尾头节点”，结构与后续表尾的表头结构不同一 2.有空表的时候不方便观察层次 孩子兄弟链结构优点：1.层次结构清晰明了 2.结构同一性 孩子兄弟链结构缺点：这个我确实没想到，后续学到了再补充吧！！！ 会破坏树存储的层次结构（树中一个分叉为一层） 最后广义表因为结构具有同一性，在写对应算法的时候只需要对正在处理的广义表负责，剩下的交给递归即可。 |
【本文地址】