| 数据结构（10）广义表的介绍与代码实现（c语言） | 您所在的位置：网站首页 › 用c语言编写线性表的结构定义 › 数据结构（10）广义表的介绍与代码实现（c语言） |
数据结构（10）广义表的介绍与代码实现（c语言）
|
文章目录
1.概念2.图解3.广义表的实现1. 广义表的结点类型2. 创建广义表3. 输出广义表运算算法4. 求广义表长度运算算法5. 求广义表深度运算算法6. 复制广义表运算算法7. 求表头运算算法8. 求表尾运算算法
1.概念
广义表是线性表的推广。广义表GL = (a1,a2,a3…,an)，如果ai是单个数据元素，则称ai是广义表的原子；如果ai也是一个广义表，则称ai是广义表的子表。在广义表中要求各原子具有相同的类型，但允许各子表具有不同的结构。 举一个广义表的例子：D=((a,b), ( c), d, ((e,f),g))，这个广义表D有4个元素，其中4表示广义表的长度。D中所包含括号的最大层数称为广义表的`深度``，D的深度 = 3。广义表的第一个元素称为广义表的表头（head(D) = (a,b)），除表头外，其余部分称之为表尾（tail(D)=(( c), d, ((e,f),g)）。原子和空表没有表头和表尾。 广义表通常使用链式存储结构（带头节点），链表中的每一个结点对应广义表中的一个元素。其中节点有不同的类型： 前面广义表D的存储结构如下图所示： 假定广义表中的元素类型DataType为char类型，每个原子的值被限定为英文字母。并假定广义表是一个表达式，其格式为：元素之间用一个逗号分割，表元素的起止符号分别为左，右括号，空表在其圆括号内不包含任何字符。 建立广义表存储结构的算法同样是一个递归算法。该算法使用一个具有广义表格式的字符串参数s，返回由他生成的广义表存储结构的头结点指针h。在算法的执行过程中，需要从头到尾扫描s的每一个字符。当碰到左括号时，表明它是一个表元素的开始，则应该建立一个由h指向的表结点，并由它的sublist作为子表的表头指针进行递归调用，来建立子表的存储结构；当碰到一个英文字母，表明它是一个原子，则应该建立一个由h指向的原子结点；当碰到一个右括号，表明它是一个空表，应该h置为空。当建立一个由h指向的结点后，接着碰到逗号字符时，表明存在后继结点，需要建立当前结点的后继表；否则表明当前所处理的表已经结束，应该置当前结点的link为空。 GLNode *CreatGL(char *&s) { GLNode *h; char ch; ch = *s; //取一个扫描字符 s++; //串指针向后移动一位 if ('\0' != ch) //串未结束标识 { h = (GLNode*)malloc(sizeof(GLNode)); //创建一个新结点 if ('(' == ch) //当前字符为左括号 { h->tag = 1; //新结点为表头结点 h->val.sublist = CreatGL(s); //递归构造子表并链接到表头节点上 } else if (')' == ch) //当前字符为右括号 { h = NULL; } else { h->tag = 0; //新结点为原子结点 h->val.data = ch; } } else //串结束，子表为空 h = NULL; ch = *s; s++; if (h != NULL) { if (',' == ch) { h->link = CreatGL(s); } else { h->link = NULL; } } return h; } 3. 输出广义表运算算法以h作为带节点附加节点的广义表的表头指针，打印输出该广义表时，需要对子表进行递归调用。当h结点为表元素结点时，应该首先输出一个左括号作为表的起始符号，然后再输出h->sublist为表头指针的表；当h结点为单元素结点时，则应该输出该元素的值。当以h->sublist为表头指针的表输出完毕时，应在其最后输出一个右括号作为结束标志。当h结点输出完毕后，若存在后继结点，则应该输出一个逗号作为分隔符，然后在递归输出由h->link指针所指向的后继表。 void DispGL(GLNode* g) { if (NULL != g)//表不为空 { if (1 == g->tag) //为表结点 { cout cout n++; g = g->link; } return n; } 5. 求广义表深度运算算法 int GLDepth(GLNode *g) { int max = 0, dep; if (0 == g->tag) { return 0; } g = g->val.sublist; if (NULL == g) { return 1; } while (g != NULL) { if (1 == g->tag) { dep = GLDepth(g); if (dep > max) max = dep; } g = g->link; } return (max + 1); } 6. 复制广义表运算算法复制一个广义表的过程如下：对于广义表的头结点*p，若为空，则返回空指针；若为表结点，则递归复制子表；否则，复制原子结点，然后再递归复制后续表。返回复制后的广义表链表的指针。 GLNode *GLCopy(GLNode *p) { GLNode *q; if (NULL == p) return NULL; q = (GLNode*)malloc(sizeof(GLNode)); q->tag = p->tag; if (1 == p->tag) q->val.sublist = GLCopy(p->val.sublist); else q->val.data = p->val.data; q->link = GLCopy(p->link); return q; } 7. 求表头运算算法空表和原子不能求表头；若表头结点为原子，则复制该节点并记为q；若表头结点是子表，则由于其link不一定为NULL，所以复制该表头结点产生t，并置t->link =NULL ，t称为虚拟表头结点。 GLNode *head(GLNode *g) { GLNode *p = g->val.sublist; GLNode *q, *t; if (NULL == p) { cout q = (GLNode*)malloc(sizeof(GLNode)); q->tag = 0; q->val.data = p->val.data; q->link = NULL; } else //为子表 { t = (GLNode*)malloc(sizeof(GLNode)); t->tag = 1; t->val.sublist = p->val.sublist; t->link = NULL; q = GLCopy(t); free(t); } return q; } 8. 求表尾运算算法空表和原子不能求表尾；否则创建一个虚拟表头结点t，并置t->val.sublist = h->val.sublist->link。 GLNode *tail(GLNode *g) { GLNode *p = g->val.sublist; GLNode *q, *t; if (NULL == g) { cout char s[] = "((a,b),(c),d,((e,f),g))"; char *ps =(char*)&s; char *&pps = ps; GLNode *gl = CreatGL(ps); cout |
【本文地址】
| 今日新闻 |
| 推荐新闻 |
| 专题文章 |