#include"stdio.h"
#include"stdlib.h"
#define maxsize 100
typedef struct node//邻接表节点
{
int date; //顶点位置
node *next;
int info; //存储边的相关信息
}node;
typedef struct
{
char top01;
node *next;
}head;
typedef struct
{
int topnum,arcnum;//顶点数,边数
head *top;//顶点表
}Graph;
int visit[maxsize];
typedef struct
{
int date[maxsize];
int front,rear;
}queue;
int enqueue(queue &s,int n)//入队
{
if((s.rear+1)%maxsize==s.front)
{
printf("队满\n");exit(0);
}
else
{
s.date[s.rear]=n;
s.rear=(s.rear+1)%maxsize;
}
}
int dequeue(queue &s,int &date) //出队
{
if(s.rear==s.front)
return 0;
else
{
date=s.date[s.front];
s.front=(s.front+1)%maxsize;
}
}
int queueEmpty(queue &s)//判断队空
{
if(s.front==s.rear)
return 0;
else
return 1;
}
int init(Graph &s)//初始化邻接表节点
{
char a[2];
printf("请输入顶点数和边数\n");
scanf("%d%d",&s.topnum,&s.arcnum);
s.top=new head[s.topnum];
printf("请输入顶点表内容\n");
for(int i=0;i<s.topnum;i++)
{
s.top[i].next=NULL;
scanf("%s",a);
s.top[i].top01=a[0];
}
}
int locate(Graph g,char a)
{
int i;
for(i=0;i<g.topnum;i++)
{
if(g.top[i].top01==a)
return i;
}
if(i==g.topnum+1)
{
printf("输入错误,程序结束\n");
exit(0);
}
}
int creat(Graph &g)//创建带权值无向网--邻接表
{
node *p1,*p2;
int i,j,k;char m,n,a[2];
printf("请分别输入所有组边连接的两个顶点及权值\n");
for(int z=0;z<g.arcnum;z++ )
{
scanf("%s",a);m=a[0];
scanf("%s",a);n=a[0];
scanf("%d",&k);
i=locate(g,m);j=locate(g,n);
p1=new node;p1->info=k;p1->date=i;p1->next=g.top[j].next;g.top[j].next=p1;
p2=new node;p2->info=k;p2->date=j;p2->next=g.top[i].next;g.top[i].next=p2;
}
}
int printf01(Graph g)
{
int i;node *p;
for(i=0;i<g.topnum;i++)
{
p=g.top[i].next;
printf("|%d %c|\t",i,g.top[i].top01);
while(p)
{
printf("%d\t",p->date);
p=p->next;
}
printf("\n");
}
}
int broad(Graph g,int v,queue &s) //广度优先遍历
{
int u;
node *p=NULL;
printf("%c\t",g.top[v].top01);visit[v]=1;
enqueue(s,v);
while(queueEmpty(s))
{
dequeue(s,u);p=g.top[u].next;
while(p)
{
if(visit[p->date]==0)
{
printf("%c\t",g.top[p->date].top01);visit[p->date]=1;enqueue(s,p->date);
}
p=p->next;
}
}
}
int broad01(Graph g,queue &s) //非连通图广度优先遍历
{
int i;
for(i=0;i<g.topnum;i++)
visit[i]=0;
queueEmpty(s);
for(i=0;i<g.topnum;i++)
if(!visit[i])
broad(g,i,s);
}
int main()
{
Graph g;queue s;
init(g);
creat(g);
printf("\n邻接表为\n");
printf01(g);
printf("\n广度优先遍历为\n");
broad01(g,s);
}
代码功能归根结底不是别人帮自己看或讲解或注释出来的;而是被自己静下心来花足够长的时间和精力亲自动手单步或设断点或对执行到某步获得的中间结果显示或写到日志文件中一步一步分析出来的。
提醒:再牛×的老师也无法代替学生自己领悟和上厕所!
单步调试和设断点调试(VS IDE中编译连接通过以后,按F10或F11键单步执行,按Shift+F11退出当前函数;在某行按F9设断点后按F5执行停在该断点处。)是程序员必须掌握的技能之一。