数据结构上机习题9：有向图与有向路径

#pragma once
#include<stdio.h>
#include<stdlib.h>
#define StackSize 100
typedef int DataType;   //栈元素类型定义
typedef struct{
    DataType stack[StackSize];
    int top;
}SeqStack;
//将栈初始化为空栈只需要把栈顶指针top置为
void InitStack(SeqStack *S){
    S->top=0;//把栈顶指针置为0
}
//判断栈是否为空，栈为空返回1，否则返回0
int StackEmpty(SeqStack S){
    if(S.top==0)
        return 1;
    else
        return 0;
}
//取栈顶元素。将栈顶元素值返回给e，并返回1表示成功；否则返回0表示失败。
int GetTop(SeqStack S,DataType *e){
    if(S.top<=0){       //在取栈顶元素之前，判断栈是否为空
        printf("栈已经空!\n");
        return 0;
    }else{
        *e=S.stack[S.top-1];    //在取栈顶元素
        return 1;
    }
}
//将元素e进栈，元素进栈成功返回1，否则返回0
int PushStack(SeqStack *S,DataType e){
    if(S->top>=StackSize){  //在元素进栈前，判断是否栈已经满
        printf("栈已满，不能进栈！\n");
        return 0;
    }else{
        S->stack[S->top]=e; //元素e进栈
        S->top++;   //修改栈顶指针
        return 1;
    }
}
//出栈操作。将栈顶元素出栈，并将其赋值给e。出栈成功返回1，否则返回0
int PopStack(SeqStack *S,DataType *e){
    if(S->top<=0){  //元素出栈之前，判断栈是否为空
        printf("栈已经没有元素，不能出栈!\n");
        return 0;
    }else{
        S->top--;   //先修改栈顶指针，即出栈
        *e=S->stack[S->top]; //将出栈元素赋值给e
        return 1;
    }
}
//求栈的长度，即栈中元素个数，栈顶指针的值就等于栈中元素的个数
int StackLength(SeqStack S){
    return S.top;
}
//清空栈的操作
void ClearStack(SeqStack *S){
    S->top=0;
}

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include"SeqStack.h"
typedef char VertexType[4];
typedef char InfoPtr;
typedef int VRType;
#define MaxSize 50  //最大顶点个数
typedef enum{DG,DN,UG,UN}GraphKind; //图的类型：有向图、有向网、无向图和无向网
//边结点的类型定义
typedef struct ArcNode{
    int adjvex;     //弧指向的顶点的位置
    InfoPtr *info;  //弧的权值
    struct ArcNode *nextarc;    //指示下一个与该顶点相邻接的顶点
}ArcNode;
//头结点的类型定义
typedef struct VNode{
    VertexType data;    //用于存储顶点
    ArcNode *firstarc;  //指示第一个与该顶点邻接的顶点
}VNode,AdjList[MaxSize];
//图的类型定义
typedef struct{
    AdjList vertex;  //头结点
    int vexnum,arcnum;  //图的顶点数目与弧的数目
    GraphKind kind; //图的类型
}AdjGraph;
//求图G中从顶点u到顶点v的一条简单路径
void BriefPath(AdjGraph G,int u,int v){
    int k,i;
    SeqStack S;
    ArcNode *p;
    int visited[MaxSize];
    int parent[MaxSize];    //存储已经访问顶点的前驱顶点
    InitStack(&S);
    for(k=0;k<G.vexnum;k++)
        visited[k]=0;   //访问标志初始化
    PushStack(&S,u);    //开始顶点入栈
    visited[u]=1;       //访问标志置为1
    while(!StackEmpty(S)){  //广度优先遍历图，访问路径用parent存储
        PopStack(&S,&k);
        p=G.vertex[k].firstarc;
        while(p!=NULL){
            if(p->adjvex==v){   //如果找到顶点v
                parent[p->adjvex]=k;        //顶点v的前驱顶点序号是k
                printf("the path from %s to %s is:",G.vertex[u].data,G.vertex[v].data);
                i=v;
                do{         //从顶点v开始将路径中的顶点依次入栈
                    PushStack(&S,i);
                    i=parent[i];
                }while(i!=u);
                PushStack(&S,u);
                while(!StackEmpty(S)){ //从顶点u开始输出u到v中路径的顶点
                    PopStack(&S,&i);
                    printf("%s ",G.vertex[i].data);
                }
                printf("\n");
            }else if(visited[p->adjvex]==0){    //如果未找到顶点v且邻接点未访问过，则继续寻找
                visited[p->adjvex]=1;
                parent[p->adjvex]=k;
                PushStack(&S,p->adjvex);
            }
            p=p->nextarc;
        }
    }
}
//返回图中顶点对应的位置
int LocateVertex(AdjGraph G,VertexType v){
    int i;
    for(i=0;i<G.vexnum;i++)
        if(strcmp(G.vertex[i].data,v)==0)
            return i;
    return -1;
}
//采用邻接表存储结构，创建无向图N
void CreateGraph(AdjGraph *G){
    int i,j,k,w;
    VertexType v1,v2;                   /*定义两个顶点v1和v2*/
    ArcNode *p;
    printf("please enter node and line: ");
    scanf("%d,%d",&(*G).vexnum,&(*G).arcnum);
    printf("enter %d node:",G->vexnum);
    for(i=0;i<G->vexnum;i++)            /*将顶点存储在头结点中*/
    {
        scanf("%s",G->vertex[i].data);
        G->vertex[i].firstarc=NULL;     /*将相关联的顶点置为空*/
    }
    printf("please two nodes of the line:\n");
    for(k=0;k<G->arcnum;k++)            /*建立边链表*/
    {
        scanf("%s%s",v1,v2);
        i=LocateVertex(*G,v1);
        j=LocateVertex(*G,v2);
        /*j为入边i为出边创建邻接表*/
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=j;
        p->info=(InfoPtr*)malloc(sizeof(InfoPtr));
        /*将p指向的结点插入到边表中*/
        p->nextarc=G->vertex[i].firstarc;
        G->vertex[i].firstarc=p;
        /*i为入边j为出边创建邻接表*/
        p=(ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex=i;
        p->info=NULL;
        p->nextarc=G->vertex[j].firstarc;
        G->vertex[j].firstarc=p;
    }
    (*G).kind=UG;
}
//销毁无向图G
void DestroyGraph(AdjGraph *G){
    int i;
    ArcNode *p,*q;
    for(i=0;i<G->vexnum;++i)        /*释放图中的边表结点*/
    {
        p=G->vertex[i].firstarc;    /*p指向边表的第一个结点*/
        if(p!=NULL)                 /*如果边表不为空，则释放边表的结点*/
        {
            q=p->nextarc;
            free(p);
            p=q;
        }
    }
    (*G).vexnum=0;                  /*将顶点数置为0*/
    (*G).arcnum=0;                  /*将边的数目置为0*/
}
//图G的邻接表的输出
void DisplayGraph(AdjGraph G){
    int i;
    ArcNode *p;
    printf("the number of node is %d",G.vexnum);
    for(i=0;i<G.vexnum;i++)
        printf("%s ",G.vertex[i].data);
    printf("\nthe number of line is:%d\n",2*G.arcnum);
    for(i=0;i<G.vexnum;i++)
    {
        p=G.vertex[i].firstarc;
        while(p)
        {
            printf("(%s,%s) ",G.vertex[i].data,G.vertex[p->adjvex].data);
            p=p->nextarc;
        }
        printf("\n");
    }
}
void main(){
    AdjGraph G;
    CreateGraph(&G);        /*采用邻接表存储结构创建图G*/
    DisplayGraph(G);        /*输出无向图G*/
    BriefPath(G,0,4);       /*求图G中从顶点a到顶点e的简单路径*/
    DestroyGraph(&G);       /*销毁图G*/
    system("pause");
}