[数据结构与算法]链表和广义表的习题

答案：

// 总的代码，包括存储结构、初始化创建、输出个数
#include<stdio.h>
#include<malloc.h>
//十字链表的存储结构
typedef struct OLNode{
    // 非零元素的行和列下标
    int i,j;  
    int e;
    // 非零元素所在行表列表的后继链域
    struct OLNode * right, *down;             
}OLNode,*OLink; 

typedef struct{
    //行、列链表的头指针向量基址
    OLink *rhead,*chead;
    //稀疏矩阵的行数、列数
    int  mu, nu;    
}CrossList; 
//创建链表
int CreateCrossList (CrossList * M){
    int m,n,t,i,j,e;
    OLink q;
    //采用十字链表存储结构，创建稀疏矩阵M  
    printf("输入M的行数,列数和非零元素的个数\n");
    scanf("%d %d %d",&m,&n,&t);  //输入M的行数,列数和非零元素的个数 
    M->mu=m;M->nu=n;
    if(!((OLink *)M->rhead=(OLink *)malloc((m+1)*sizeof(OLink)))) return 0; 
    if(!((OLink *)M->chead=(OLink *)malloc((n+1)*sizeof(OLink)))) return 0; 
    for(int i=0;i<=m;i++){
        M->rhead[i]=NULL;
    }
    for(int j=0;j<=n;j++){
        M->chead[j]=NULL;
    }   
    //初始化行、列头指针向量，各行、列链表为空的链表  
    printf("初始化行、列、数\n");
    printf("停止时需要输入行数为0\n");
    for(scanf("%d %d %d",&i,&j,&e);i!=0;scanf("%d %d %d",&i,&j,&e)){
        OLink p;
        if(!(p=(OLink)malloc(sizeof(OLNode)))) 
            return 0; 
        p->i=i;
        p->j=j;
        p->e=e;  //生成结点 
        p->right=NULL;
        p->down=NULL;
        if(M->rhead[i]==NULL)   
            M->rhead[i]=p; 
        else{  
            /*寻找行表中的插入位置*/ 
            for(q=M->rhead[i];q->right&&q->right->j<j;q=q->right){}
                p->right=q->right; q->right=p;  /*完成插入*/ 
        }
        if(M->chead[j]==NULL){
            M->chead[j]=p;
        }else{  /*寻找列表中的插入位置*/
            for(q=M->chead[j];q->down&&q->down->i<i;q=q->down){}
                p->down=q->down; q->down=p;   /*完成插入*/ 
        } 
    } 
} 
int NonzeroNumber(CrossList M){
    int i;
    int number=0;
    for(i=1;i<=M.nu;i++){
        if(M.chead[i]!=NULL){
            OLink q=M.chead[i];
            while(q){
                number++;
                q=q->down;
            }
        }   
    }
    return number;
}
int main(){
    CrossList M;
    CreateCrossList(&M);
    printf("OK2\n");
    int num=NonzeroNumber(M);
    printf("OK3\n");
    printf("%d\n",num);
    return 0;
}

?

广义表：

#include<stdio.h>
#include<malloc.h>
typedef enum{
    ATOM,// ATOM=0：单元素；
    LIST// LIST=1：子表 
}ELemtag;
typedef struct GLNode{
    ELemtag tag;// 标志域，用于区分元素结点和表结点  
    union{      // 元素结点和表结点的联合部分 
        char atom; // atom 是原子结点的值域
        struct GLNode *hp; // 表结点的表头指针 
    };
    struct GLNode *tp; // 指向下一个结点  

}Node,*GList;
//计算广义表的深度
int GListDepth(GList L){ // 返回指针L所指的广义表的深度
    // 定义变量
    int dep;
    int max=0;
    GList pp;
    // 如果空表的深度 = 1
    // 原子的深度 = 0
    // 遍历广义表，求得深度
    for(pp=L; pp; pp=pp->tp){
        // 如果是链表，进入递归
        if(pp->tag==LIST){
            // 计算每一层hp指针数量
            dep = GListDepth(pp->hp)+1;
            // 统计回溯时hp指针的总数量
            if(dep>max){
                // 赋值
                max=dep;
            }
        }
        // 如果是原子，因为原子节点一定没有hp指针，所以直接进入下一循环
        if(pp->tag==ATOM){
            continue;
        }
    }
    return max;
}
int main(){
     如图可知有六个小结点，创建广义表
    GList p;
    GList list1=(GList)malloc(sizeof(Node));
    GList list2=(GList)malloc(sizeof(Node));
    GList list3=(GList)malloc(sizeof(Node));
    GList list4=(GList)malloc(sizeof(Node));
    GList list5=(GList)malloc(sizeof(Node));
    GList list6=(GList)malloc(sizeof(Node));
    p=list1;
    list1->tag=LIST;
    list1->tp=NULL;
    list1->hp=list2;
    list2->tag=ATOM;
    list2->tp=list3;
    list2->atom='a';
    list3->tag=LIST;
    list3->tp=NULL;
    list3->hp=list4;
    list4->tag=ATOM;
    list4->tp=list5;
    list4->atom='b';
    list5->tag=ATOM;
    list5->tp=list6;
    list5->atom='c';
    list6->tag=ATOM;
    list6->tp=NULL;
    list6->atom='d';
    int len=GListDepth(p);
    printf("%d\n",len);
    return 0;
}

?