1. 广义表的创建文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
如图所示，广义表的每一个结点相互串联，有些结点存储原子数据，有些结点则存储另一份广义表数据，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
我们创建数据string ss = "(2,3,4, (1, (3, ( 7,8 ) ),2) )";其基本可以分成4层，每一个层中一个括号表示下一层，在数学表示中，我们也常用括号的级数表示广义表。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
因此，广义表的创建就需要进行连接，连接的方法是更具tag进行判断本结点中是Atom（原子）还是Node（结点），再根据其中的选择进行相对应的连接，可以由如下图可知。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
对于代码的书写，我们首先需要对传入的字符串进行切割，将每一组括号”()”进行分割，每一组括号其中就表示的一份新的广义表，我们需要找到括号并且与这个括号相互匹配的括号数进行对应，找到并切割掉，以此分离出表头串，方便我们进行后续的操作。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | void sever(string &str,string &hstr){ //将非空串str分割成两部分，hstr是表头 int n = str.size(); int i = -1; int k = 0; //k记录尚未配对的“(” 数 char ch; do{ //搜索最外层第一个( ++i; ch = str[i]; if(ch == '(') ++k; else if(ch == ')') --k; }while(i<n&&(ch != ','||k!=0)); if(i<n){ hstr =str.substr(0,i); str = str.substr(i+1,n-i-1); }else{ hstr = str.substr(0,str.size()); str.clear(); }} |
我们通过分割以后可以通过上文介绍的方法进行指针的相互指引，核心就是要注意tag的判断，以及Atom/Node域是使用共用体创建的，要注意两者的空间不可以重叠，严格使用if(){}else{}的语法结构不要乱套。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
void CreateGList(GList &L,string s){ //采用头尾链表存储结构，创建L if(s.compare(emp) == 0) L = NULL; else{ L = (GList)malloc(sizeof(GLNode)); if(!L) exit(0); if(s.size() == 1){ //单个元素，建立原子节点 L->tag = ATOM; L->atom = s[0]; }else{ //表节点 ,表尾 L->tag = LIST; GList p,q; p = L; //p是指向当前子表(表尾节点)的指针 string sub; sub = s.substr(1,s.size()-2); //去掉外层括号 string hsub; do{ //重复建立n个子表 sever(sub,hsub); //sub中分理出表头串hsub ，同时，sub去除了hsub CreateGList(p->ptr.hp,hsub); q = p; //记录p，下面sub不为空，要再建立一个表尾节点，q记录上一层的p，用以连接q->ptr.tp = q if(!sub.empty()) { p = (GList)malloc(sizeof(GLNode)); if(!p)exit(0); p -> tag = LIST; q -> ptr.tp = p; } }while(!sub.empty()); q -> ptr.tp = NULL; } }} |
2. 广义表的深度文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
我们只需要根据表的情况进行一个递归调用即可判断，当然需要特判一下空表的情况。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/25148.html
int GListDepth(GList L) { if(!L) return 1; //空表1 if(L->tag ==ATOM ) return 0; GList pp; //遍历同一层，递归下一层，取表尾，取表头，第一步先去一个表头 int max; for(max = 0, pp =L;pp!=NULL;pp = pp->ptr.tp){ int dep = GListDepth(pp->ptr.hp) ; if(dep > max) max = dep; //这一步比较，是比较同一层的depth } return max+1;} |