Contents

#include <stdio.h>
#include <stdlib.h>

#define MAXVEX 100                      //最大顶点数,应由用户定义
#define INFINITY 65535                  //用65535来代表∞

typedef char VertexType;                //顶点类型应用户定义
typedef int  EdgeType;                  //边上的权值应由用户定义
typedef int InforType;                  //信息的类型由用户定义

typedef struct EdgeNode                //边表结点
{
    int adjvex;                        //邻接点域,存储该顶点对应的下标
    EdgeType weight;                   //用于存储权值,对于非网图可以不需要
    struct EdgeNode *next;             //链域,指向下一个邻接点
}EdgeNode;

typedef struct VertexNode              //顶点表结点
{
    VertexType data;                   //顶点域,存储顶点信息
    EdgeNode *firstedge;               //边表头指针  建立边表
}VertexNode;

typedef struct GraphAdjlist
{
    VertexNode adjlist[MAXVEX];        //建立顶点表
    int numVertex, numEdge;            //图中当前顶点数和边数
}GraphList;

int Locate(GraphList *g, char ch) //不改变原数据,所以用一级指针{

    int i;
    for(i = 0; i < MAXVEX && ch != g->adjlist[i].data; i++)
        ;
    if(i >= MAXVEX)
    {
        printf("There is no this vertex !\n");
        return -1;
    }
    return i;
}

//建立图的邻接表结构
void CreatGraphList(GraphList *g){

    EdgeNode *e;//用于后面的建立边链表
    EdgeNode *f;
    int i, k;
    printf("输入顶点数和边数:\n");
    scanf("%d,%d", &(g->numVertex), &(g->numEdge));
    for(i = 0; i < g->numVertex; i++)
    {
        printf("请输入顶点%d: \n", i);//例如(V0, v1),(v0,v2),(v0,v3)
        g->adjlist[i].data = getchar();             //输入顶点信息
        g->adjlist[i].firstedge = NULL;             //将边表置为空表
        while(g->adjlist[i].data == '\n')                //吃回车
            g->adjlist[i].data = getchar();
    }
    //建立边表
    for(k = 0; k < g->numEdge; k++)
    {
        printf("输入边(vi,vj)上的顶点序号:\n");
        char p, q;
        scanf("%c %c", &p, &q);
        getchar();//吃回车
        int m = Locate(g, p);
        int n = Locate(g, q);
        if(m == -1 || n == -1)
            return ;
        //向内存申请空间，生成边表结点
        e = (EdgeNode *)malloc(sizeof(EdgeNode));
        if(!e) {printf("malloc() error !\n"); return ;}
        e->adjvex = n;//储存邻接点的下标
        e->next = g->adjlist[m].firstedge;//链表的头插法
        g->adjlist[m].firstedge = e;

        f = (EdgeNode *)malloc(sizeof(EdgeNode));
        if(!e) {printf("malloc() error !\n"); return ;}
        f->adjvex = m;//储存邻接点的下标
        f->next = g->adjlist[n].firstedge;//链表的头插法
        g->adjlist[n].firstedge = f;
    }
}
//邻接表的深度递归算法
void DFS(GraphList g, int i){

    EdgeNode *p;
    visited[i] = true;
    printf("%c ", g->adjlist[i].data);  //打印顶点，也可以其他操作
    p = g->adjlist[i].firstedge;
    while(p)                            //有邻接点,就是有邻接边
    {
        if(!visited[p->adjvex])         //未访问
        {
            DFS(g, p->adjvex);          //访问邻接点
        }
        p = p->next;
    }
}
//邻接表的深度遍历操作
void DFSTraverse(GraphList g){

    int i;
    for(i = 0; i <g.numVertex; i++)
        visited[i] = false;
    for(i = 0; i < g.numVertex; i++)
    {
        if(!visited[i])
            DFS(g, i);
    }

}

void printGraph(GraphList *g){

    int i = 0;
    while(g->adjlist[i].firstedge != NULL && i < MAXVEX)
    {
        printf("顶点: %c", g->adjlist[i].data);
        EdgeNode *e = NULL;
        e = g->adjList[i].firstedge;
        while(e != NULL)
        {
            printf("%d  ", e->adjvex);
            e = e->next;
        }
        i++;
        printf("\n");
    }
}

int main(){

    GraphList g;
    CreatGraph(&g);
    print(&g);
    return 0;
}