第9週目プロジェクト4-広義表算法ライブラリ及び応用

/* 
 * Copyright (c).2014,           
 * All rights reserved. 
 *    :bomb.cpp 
 *      :    
 *    :2015  11  9  
 *     :v1.0 
 * 
 *    ：        
 *    ： 
 *    ：    
 */ 

問題およびコード:
1.ヘッダファイル:glist.h、一般化テーブルデータ構造を定義するコード、マクロ定義、アルゴリズムを実現する関数の宣言を含む.

#ifndef GLIST_H_INCLUDED
#define GLIST_H_INCLUDED

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

2.ソースファイル:glist.cpp,各種アルゴリズムを実現する関数の定義を含む

#include <stdio.h>
#include <malloc.h>
#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);            //          
        }
    }
}

3.main関数を作成し、関連するテスト作業を完了する.

#include <stdio.h>
#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;
}

実行結果: