//我在书上的代码调用了下，请问还有那些地方要做改动更好点呢？
#define maxvex 100
typedef char vertextype;
#include <iostream.h>
#include <malloc.h>
int visited[maxvex];

typedef struct edgenode
{int adjvex;/*顶点域*/
 int value; /*变的权值*/
  struct edgenode *next ;/* 链域*/
}arcnode;

typedef struct vexnode
{ vertextype data;/*数据域*/
 arcnode *firstarc;/*链域指向链表中第一个结点*/
}vheadnode;

typedef struct adjlist1
{int n,e;
 vheadnode adjlist[maxvex];
}adjlist;

typedef struct vertex
{
    int adjvex;
    vertextype data;
}vtype;
typedef struct graph
{
    int n,e;
    vtype vexs[maxvex];
    int edges[maxvex][maxvex];
}adjmatix;

int creatematix(adjmatix &g)
{int i,j,k,w;
vertextype b,t;
cout<<"顶点数(n)和边数(e):";
cin>>g.n>>g.e;
for(i=0;i<g.n;i++)
{cout<<"  序号为"<<i<<"的顶点信息:";
cin>>g.vexs[i].data;
g.vexs[i].adjvex=i;
}
for(i=0;i<g.n;i++)
for(j=0;j<g.n;j++)
g.edges[i][j]=0;
for(k=0;k<g.e;k++)
{cout<<" 序号为  "<<k<<"的边=>";
cout<<"起点 重点 权值";
cin>>b>>t>>w;
i=0;
while(i<g.n &&g.vexs[i].data!=b)
i++;
if(i>=g.n)
{cout<<"输入起点不存在！"<<endl;
return(0);
}
j=0;
while(j<g.n &&g.vexs[j].data!=t)
j++;
if(j>=g.n)
{cout<<"输入重点不存在！"<<endl;
return (0);
}
g.edges[i][j]=w;
}
return(1);
}

int createadjlist(adjlist *&g)
{int i,b,t,w;
arcnode *p,*q;
g=(adjlist *)malloc(sizeof(adjlist));
cout<<"顶点数（n），边数（e）：";
cin>>g->n>>g->e;
for(i=0;i<g->n;i++)
{cout<<" 序号为  "<<i<<"的顶点信息：";
cin>>g->adjlist[i].data;
g->adjlist[i].firstarc=NULL;
}
for(i=0;i<g->e;i++)
{
    cout<<"   序号为"<<i<<"边=>";
    cout<<"起点序号 重点序号 权值";
    cin>>b>>t>>w;
    if(b<0 ||b>g->n)
    {cout<<"输入的起点序号不存在！"<<endl;
    return (0);
    }
    if(t<0 ||t>g->n)
    {cout<<"输入的重点序号不存在！"<<endl;
    return (0);
    }
    p=(arcnode *)malloc(sizeof(arcnode));
    p->value=w;p->adjvex=t;
    p->next=g->adjlist[b].firstarc;
    g->adjlist[b].firstarc=p;
    q=(arcnode *)malloc(sizeof(arcnode));
    q->value=w;q->adjvex=b;
    q->next=g->adjlist[t].firstarc;
    g->adjlist[t].firstarc=q;
}
return (1);
}
void matolist (adjmatix g,adjlist *&G)
{int i,j;
arcnode *p;
G=(adjlist *)malloc(sizeof(adjlist));
for(i=0;i<g.n;i++)
{G->adjlist[i].firstarc=NULL;
G->adjlist[i].data=g.vexs[i].data;
}
for(i=0;i<g.n;i++)
for(j=g.n-1;j>=0;j--)
if(g.edges[i][j]!=0)
{p=(arcnode *)malloc(sizeof(arcnode));
p->value=g.edges[i][j];p->adjvex=j;
p->next=G->adjlist[i].firstarc;
G->adjlist[i].firstarc=p;
}
G->n=g.n;G->e=g.e;
}

void dispadjlist (adjlist *g)
{
    int i;
    arcnode *p;
    cout<<"图的邻接表表示如下："<<endl;
    for(i=0;i<g->n;i++)
    {
        cout<<"["<<i<<","<<g->adjlist[i].data<< "]=>";
        p=g->adjlist[i].firstarc;
        while (p!=NULL)
        {
            cout<<"("<<p->adjvex<<","<<p->value<<")->";
            p=p->next;
        }
        cout<<"^\n";
    }
}
void DFS(adjlist *g,int vi)
{arcnode *p;
visited[vi]=1;
cout<<vi<<" ";
p=g->adjlist[vi].firstarc;
while(p!=NULL)
{if(visited[p->adjvex]==0)
DFS(g,p->adjvex);
p=p->next;
}
}
void BFS(adjlist *g,int vi)
{int i,v,visited[maxvex];
int    qu[maxvex],front =0,rear=0;
arcnode *p;
for(i=0;i<g->n;i++)
visited[i]=0;
visited[vi]=1;
cout<<vi<<" ";
rear=(rear=1)%maxvex;
qu[rear]=vi;
while(front!=rear)
{front=(front+1)%maxvex;
v=qu[front];
p=g->adjlist[v].firstarc;
while(p!=NULL)
{if(visited[p->adjvex]==0)
{visited[p->adjvex]=1;
cout<<p->adjvex<<" ";
rear=(rear+1)%maxvex;
qu[rear]=p->adjvex;
}
p=p->next;
}
}
}
void main()
{   int vi;
    int path[maxvex],u=1,v=4,d=3,i,j;
    adjmatix g;
    adjlist *G;
    g.n=5;
    g.e=6;
    int a[maxvex][maxvex]={
        {0,1,0,1,0},
        {1,0,1,0,0},
        {0,1,0,1,1},
        {1,0,1,0,1},
        {0,0,1,1,0}};
        vertextype b[]={'a','b','c','d','e'};
        for(i=0;i<g.n;i++)
            for(j=0;j<g.n;j++)
                g.edges[i][j]=a[i][j];
            for(i=0;i<g.n;i++)
                g.vexs[i].data=b[i];
            matolist(g,G);
            for(i=0;i<g.n;i++)
                visited[i]=0;
            cout<<endl;
            dispadjlist(G);
        
            cout<<endl;
            cout<<"请输入vi的值：";
            cin>>vi;
            cout<<"广度优先搜索后输出为："<<endl;
            BFS(G,vi);
            cout<<endl;
            cout<<"深度优先搜索后输出为："<<endl;
            cout<<endl;
            DFS(G,3);
            cout<<endl;

}