/**//*
    标题：<<系统设计师>>应试编程实例-[图程序设计]
    作者：成晓旭
    时间：2002年09月06日(16:30:00-17:16:00)
          完成图的创建函数、顺序遍历函数
    时间：2002年09月08日(21:30:00-22:35:00)
          完成图的深度优先遍历函数[非堆栈、堆栈实现]
*/
#include    "stdio.h"
#include    "stdlib.h"

//如:FROMHEAD = 1，则用头插法;否则:则用尾插法
#define     FROMHEAD 1
/**//*
    如:HASHEAD 被定义，则各顶点的邻接点链中<带起始顶点>;
    否则:各顶点的邻接点链中<不带起始顶点>;
*/
#define        NODE_NUM        5
#ifdef HASHEAD
    //<带起始顶点>
    int GraphNode[NODE_NUM][3] = ...{...{1,’A’,4},...{2,’B’,4},...{3,’C’,5},...{4,’D’,5},...{5,’E’,3}};
    int ConnectTable[] = ...{0,1,2,3,1,0,2,3,2,0,1,3,4,3,0,1,2,4,4,2,3};
#else
    //<不带起始顶点>
    int GraphNode[NODE_NUM][3] = ...{...{1,’A’,3},...{2,’B’,3},...{3,’C’,4},...{4,’D’,4},...{5,’E’,2}};
    int ConnectTable[] = ...{1,2,3,0,2,3,0,1,3,4,0,1,2,4,2,3};
#endif

//邻接表中图各顶点结构类型定义
#define    gVertexNode    struct    gVertexNode
gVertexNode
...{
    int    order;                //顶点在图中的序号
    int    data;                //顶点的数据域
    gVertexNode *link;        //指向顶点的下一个邻接顶点节点的指针
};
//邻接表中图各顶点的遍历头节点结构类型定义
#define    gHeadNode    struct    gHeadNode
gHeadNode
...{
    int    vcount;                //邻接链表的节点数目[即当前顶点的邻接顶点个数]
    //int    order;                //顶点在图中的序号
    int    data;            //顶点的数据域
    gVertexNode *firstnode;    //指向邻接表的首顶点节点的指针
};
/**//*
    创建以邻接表方式存储的图
    参数描述：
    gHeadNode    HeadNode    图的邻接存储的头节点数组
    int            max：图的顶点个数
    int            fromhead：插入邻接占点的方式
                    fromhead=1    头插入方式
                    fromhead=0    尾插入方式
*/
void    CreateGraph(gHeadNode HeadNode[],int max,int fromhead)
...{
    gVertexNode *p,*tail;    //当前顶点节点及邻接表当前节点的邻接链表的尾节点
    int    i,j,k;    //i,j为循环计数器,k为当前顶点的邻接顶点数目
    for(i=0;i<max;i++)
    ...{
        HeadNode[i].vcount = GraphNode[i][2];
        HeadNode[i].data = GraphNode[i][1];
        HeadNode[i].firstnode = NULL;
        //printf(" 顶点[%c]有[%d]个邻接点！ ",HeadNode[i].data,HeadNode[i].vcount);
    }
    for(i=0,k=0;i<max;i++)
    ...{
        for(j=0;j<HeadNode[i].vcount;j++)
        ...{
            //创建图的顶点节点
            p = (gVertexNode *)malloc(sizeof(gVertexNode));
            if(p==NULL)
            ...{
                exit(1);
            }
            else
            ...{
                //图的新顶点赋值
                p->order = GraphNode[ConnectTable[k+j]][0];
                p->data  = GraphNode[ConnectTable[k+j]][1];
                p->link  = NULL;
                if(fromhead)
                ...{//新节点放在最前面<紧接头节点的后面>头插法
                    p->link = HeadNode[i].firstnode;
                    HeadNode[i].firstnode = p;
                }
                else
                ...{//新节点放在最后面<紧接最后一个表节点的后面>尾插法
                    if(HeadNode[i].firstnode == NULL)
                    ...{//插入第一个节点
                        HeadNode[i].firstnode = p;
                        tail = p;
                    }
                    else
                    ...{//插入非第一个节点[直接接到最后一个节点之后]
                        tail->link = p;
                        tail = p;
                    }
                }

            }
        }
        //移动关联表计数位置“指针”
        k = k + HeadNode[i].vcount;
    }
}
/*
    顺序访问图中的各个节点[以创建的邻接表的头节点数组前后顺序]
    参数描述：
    gHeadNode    HeadNode    图的邻接存储的头节点数组
    int            max：图的顶点个数
*/
void    Sequence_Journey(gHeadNode HeadNode[],int max)
{
    gVertexNode *p;
    int i;
    printf("以创建的邻接表的头节点数组前后顺序访问的图： ");
    for(i=0;i<max;i++)
    {
        p = HeadNode[i].firstnode;
        //printf(" 顶点[%c]的[%d]个邻接点： ",HeadNode[i].data,HeadNode[i].vcount);
        while(p != NULL)
        {
            printf("顶点[%d][%c] ",p->order,p->data);
            p = p->link;
        }
        printf(" ");
    }
}
//图的[深度优先遍历]算法<非堆栈实现算法>
void    nsDeepthFirst_Journey(gHeadNode HeadNode[],int max)
{
    gVertexNode *p;        //顶点
    int    visited[NODE_NUM];    //0：未访问        1：已访问
    int    i;
    printf("图的[深度优先遍历]结果<非堆栈实现>: ");
    for(i=0;i<max;i++)        //设置所有的顶点未访问标志
        visited[i] = 0;
    for(i=0;i<max;i++)
    {
        p = HeadNode[i].firstnode;    //指向当前访问顶点
        //printf("顶点[%d][%c] ",p->order,p->data);
        while(p != NULL)    //如果顶点有邻接顶点
       {
            if(visited[p->order] == 0)
            {//当前顶点的邻接顶点还未访问
                printf("顶点[%d][%c] ",p->order,p->data);
                visited[p->order] = 1;
            }
            p = p->link;        //移向下一个顶点
        }
    }
}
//图的[深度优先遍历]算法<堆栈实现算法>
void    DeepthFirst_Journey(gHeadNode HeadNode[],int max)
{
    gVertexNode *p;        //顶点
    gVertexNode *vstack[NODE_NUM+1];    //顶点堆栈
    int    visited[NODE_NUM+1];    //0：未访问        1：已访问
    int    i,top;        //循环计数器和堆栈指针
    printf("图的[深度优先遍历]结果<堆栈实现>: ");
    for(i=0;i<=max;i++)        //设置所有的顶点未访问标志
        visited[i] = 0;
    for(i=0;i<max;i++)
    {
        top = 1;
        vstack[top] = HeadNode[i].firstnode;//将本次访问的起始节点进栈，以便将来正确返回
        while(top != 0)    //堆栈不为空
       {
            p = vstack[top];    //取堆栈中的栈顶元素
            while((p != NULL) && (visited[p->order] == 1))    //还有邻接顶点，且已被访问
                p = p->link;
            if(p == NULL)    //当前顶点没有邻接顶点，或有，但都已经被访问过
                top--;    //完成退栈
            else
           {//否则，则访问之
                printf("顶点[%d][%c] ",p->order,p->data);
                visited[p->order] = 1;
                vstack[++top] = p;    //访问顶点进栈
            }
        }
    }
}
int main(int argc, char* argv[])
{
    gHeadNode HeadNodeArray[NODE_NUM];
    int    InsertMode = -1;
    while(InsertMode != 0 && InsertMode != 1)
   {
       printf("请输入顶点的插入方式[0尾插入法:/1:头插入法]");
        scanf("%d",&InsertMode);
    }
    CreateGraph(HeadNodeArray,NODE_NUM,InsertMode);
    Sequence_Journey(HeadNodeArray,NODE_NUM);
    //nsDeepthFirst_Journey(HeadNodeArray,NODE_NUM);
    DeepthFirst_Journey(HeadNodeArray,NODE_NUM);
    printf(" 应用程序运行结束！ ");
    return 0;
}