第九週実践項目4—広義表算法庫及び応用(1)

/* 
Copyright (c)2015,               
All rights reserved. 
    ：  4-1.cbp 
      ：    
    ：2015 11 14  
     ：v1.0 
 
 
 
 
    ：（1）        ，  ： 
 
 
①   glist.h，      ，    ； 
②    glist.cpp，          ，      ： 
 
 
    int GLLength(GLNode *g);    //    g    
    int GLDepth(GLNode *g);     //    g    
    GLNode *CreateGL(char *&s); //          s           
    void DispGL(GLNode *g);     //     g 
 
 
③   main  ，          
    ：  
    ：     
*/  

glist.h    ：

<pre name="code" class="cpp">#ifndef GLIST_H_INCLUDED  
#define GLIST_H_INCLUDED  
  
  
#include <stdio.h>  
#include <malloc.h>  
typedef char ElemType;  
typedef struct lnode  
{  
    int tag;                    //        
    union  
    {  
        ElemType data;          //     
        struct lnode *sublist;  //         
    } val;  
    struct lnode *link;         //         
} GLNode;                       //           
  
  
int GLLength(GLNode *g);        //    g     
int GLDepth(GLNode *g);     //    g     
GLNode *CreateGL(char *&s);     //          s            
void DispGL(GLNode *g);                 //     g  
  
  
#endif // GLIST_H_INCLUDED  

 
 
<pre name="code" class="cpp">#include "glist.h"  
  
  
int GLLength(GLNode *g)     //    g     
{  
    int n=0;  
    GLNode *g1;  
    g1=g->val.sublist;      //g             
    while (g1!=NULL)  
    {  
        n++;                //        
        g1=g1->link;  
    }  
    return n;  
}  
  
  
int GLDepth(GLNode *g)      //    g     
{  
    GLNode *g1;  
    int max=0,dep;  
    if (g->tag==0)          //      0  
        return 0;  
    g1=g->val.sublist;      //g1         
    if (g1==NULL)           //      1  
        return 1;  
    while (g1!=NULL)        //            
    {  
        if (g1->tag==1)     //          
        {  
            dep=GLDepth(g1);    //             
            if (dep>max)    //max                   
                max=dep;  
        }  
        g1=g1->link;            // g1         
    }  
    return(max+1);          //        
}  
  
  
GLNode *CreateGL(char *&s)      //          s            
{  
    GLNode *g;  
    char ch=*s++;                       //       
    if (ch!='\0')                      //        
    {  
        g=(GLNode *)malloc(sizeof(GLNode));//         
        if (ch=='(')                    //           
        {  
            g->tag=1;                   //           
            g->val.sublist=CreateGL(s); //               
        }  
        else if (ch==')')  
            g=NULL;                     //  ')'  ,g     
        else if (ch=='#')               //  '#'  ，       
            g=NULL;  
        else                            //       
        {  
            g->tag=0;                   //           
            g->val.data=ch;  
        }  
    }  
    else                                 //   ,g     
        g=NULL;  
    ch=*s++;                            //        
    if (g!=NULL)                        //    ，          
    {  
        if (ch==',')                    //     ','  
            g->link=CreateGL(s);        //          
        else                            //     ,       NULL  
            g->link=NULL;  
    }  
  
  
    return g;                           //     g  
}  
  
  
void DispGL(GLNode *g)                  //     g  
{  
    if (g!=NULL)                        //        
    {  
        //   g     
        if (g->tag==0)                  //g         
            printf("%c", g->val.data);  //       
        else                            //g         
        {  
            printf("(");                //  '('  
            if (g->val.sublist==NULL)   //      
                printf("#");  
            else                        //        
                DispGL(g->val.sublist); //        
            printf(")");                //  ')'  
        }  
        if (g->link!=NULL)  
        {  
            printf(",");  
            DispGL(g->link);            //            
        }  
    }  
}  
  
main.cppファイルコード:
 
 
<pre name="code" class="cpp">#include "glist.h"  
int main()  
{  
    GLNode *g;  
    char *s="(b,(b,a,(#),d),((a,b),c((#))))";  
    g = CreateGL(s);  
    DispGL(g);  
    printf("     :%d
", GLLength(g));  
    printf("     :%d
", GLDepth(g));  
    return 0;  
}  
  
    ：
  
<img src="http://img.blog.csdn.net/20151115185231649" alt="" />