song.cpp

来自「1)自选存储结构,输入含n个顶点（用字符表示顶点）和e 条边的图G； (2」· C++ 代码 · 共 374 行

// song.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include "stdio.h" 
typedef int datatype; /*假定线性表元素的类型为整型*/ 
#define maxsize 1024 /*假定线性表的最大长度为1024*/ 
#define max 10
# define n 100 /* 图的顶点最大个数 */ 
typedef char VEXTYPE; /* 顶点的数据类型 */ 
typedef float ADJTYPE; /* 权值类型 */ 
typedef struct 
{ VEXTYPE vexs[n] ; /* 顶点信息数组 */ 
ADJTYPE arcs[n][n] ; /* 边权数组 */ 
int num; /* 顶点的实际个数 */ 
}GRAPH; 

/***********************置空图**********************/ 
void GraphInit(GRAPH *L) 
{ 
L->num=0; 
} 

/***********************求结点数**********************/ 
int GraphVexs(GRAPH *L) 
{ 
return(L->num); 
} 

/***********************创建图**********************/ 
void GraphCreate(GRAPH *L) 
{ int a[max],b[max];
int i,j; 
int c[max];
for(i=0;i<max;i++)
{a[i]=0;
b[i]=0;
c[i]=0;}
GraphInit(L); 
printf("请输入顶点数目(小于十个顶点)："); 
scanf("%d",&L->num); 
printf("请输入各顶点的信息(单个符号）："); 
for(i=0;i<L->num;i++) 
{ 
fflush(stdin); 
scanf("%c",&L->vexs[i]); 
} 
printf("请输入边权矩阵的信息："); 
for(i=0;i<L->num;i++) 
{ 
for(j=0;j<L->num;j++) 
{
scanf("%f",&L->arcs[i][j]); 
if(L->arcs[i][j]!=0)
{a[i]++;
b[j]++;}

} 
} 
for (i=0;i<L->num;i++)
c[i]=a[i]+b[i];
printf("图已经创建完毕！\n"); 
for(i=0;i<L->num;i++)
printf("第%d个顶点的度是%d",i+1,c[i]);
} 

/***********************图的输出**********************/ 
void GraphOut(GRAPH L) 
{ 
int i,j; 
printf("\n图的顶点数目为：%d",L.num); 
printf("\n图的各顶点的信息为：\n"); 
for(i=0;i<L.num;i++) 
printf("%c ",L.vexs[i]); 
printf("\n图的边权矩阵的信息为：\n"); 
for(i=0;i<L.num;i++) 
{ 
for(j=0;j<L.num;j++) 
{ 
printf("%6.2f ",L.arcs[i][j]); 
} 
printf("\n"); 
} 
printf("图已经输出完毕！\n"); 
} 

/***********************1.图的深度周游**********************/ 
void DFS(GRAPH g,int qidian,int mark[]) 
//从第qidian个点出发深度优先周游图g中能访问的各个顶点 
{ 
int v1; 
mark[qidian]=1; 
printf("%c ",g.vexs[qidian]); 
for(v1=0;v1<g.num;v1++) 
{ 
if(g.arcs[qidian][v1]!=0&&mark[v1]==0) 
DFS(g,v1,mark); 
} 
} 
/***********************1.图的深度周游**********************/ 
void GraphDFS(GRAPH g) 
//深度优先周游图g中能访问的各个顶点 
{ 
int qidian,v,v1,mark[maxsize]; 
printf("\n深度周游："); 
printf("\n请输入起点的下标："); 
scanf("%d",&qidian); 
for(v=0;v<g.num;v++) 
{ 
mark[v]=0; 
} 
for(v=qidian;v<g.num+qidian;v++) 
{ 
//printf("v=%d ",v); 
v1=v%g.num; 
if(mark[v1]==0) 
DFS(g,v1,mark); 
} 
} 
typedef int DATATYPE; //队列元素的数据类型 
typedef struct 
{ 
DATATYPE data[maxsize]; //队中元素 
int front,rear; //队头元素下标、队尾元素后面位置的下标 
} SEQQUEUE; 
/*****************************************************************************/ 
void QueueInit(SEQQUEUE *sq) 
//将顺序循环队列sq置空（初始化） 
{ 
sq->front=0; 
sq->rear=0; 
} 
/*****************************************************************************/ 
int QueueIsEmpty(SEQQUEUE sq) 
//如果顺序循环队列sq为空，成功返回1，否则返回0 
{ 
if (sq.rear==sq.front) 
return(1); 
else 
return(0); 
} 
/*****************************************************************************/ 
int QueueFront(SEQQUEUE sq,DATATYPE *e) 
//将顺序循环队列sq的队头元素保存到e所指地址，成功返回1，失败返回0 
{ 
if (QueueIsEmpty(sq)) 
{ printf("queue is empty!\n");return 0;} 
else 
{ *e=sq.data[(sq.front)]; return 1;} 
} 
/*****************************************************************************/ 
int QueueIn (SEQQUEUE *sq,DATATYPE x) 
//将元素x入队列sq的队尾，成功返回1，失败返回0 
{ 
if (sq->front==(sq->rear+1)%maxsize) 
{ 
printf("queue is full!\n"); 
return 0; 
} 
else 
{ 
sq->data[sq->rear]=x; 
sq->rear=(sq->rear+1)%maxsize; 
return(1); 
} 
} 
/*****************************************************************************/ 
int QueueOut(SEQQUEUE *sq) 
//将队列sq队首元素出队列，成功返回1,失败返回0 
{ 
if (QueueIsEmpty(*sq)) 
{ 
printf("queue is empty!\n"); 
return 0; 
} 
else 
{ 
sq->front=(sq->front+1)%maxsize; 
return 1; 
} 
} 
/***********************2.图的广度周游**********************/ 
void BFS(GRAPH g,int v,int mark[]) 
//从v出发广度优先周游图g中能访问的各个顶点 
{ 
int v1,v2; 
SEQQUEUE q; 
QueueInit(&q); 
QueueIn(&q,v); 
mark[v]=1; 
printf("%c ",g.vexs[v]); 
while(QueueIsEmpty(q)==0) 
{ 
QueueFront(q,&v1); 
QueueOut(&q); 
for(v2=0;v2<g.num;v2++) 
{ 
if(g.arcs[v1][v2]!=0&&mark[v2]==0) 
{ 
QueueIn(&q,v2); 
mark[v2]=1; 
printf("%c ",g.vexs[v2]); 
} 
} 
} 
} 
/***********************2.图的广度周游**********************/ 
void GraphBFS(GRAPH g) 
//深度优先周游图g中能访问的各个顶点 
{ 
int qidian,v,v1,mark[maxsize]; 
printf("\n广度周游："); 
printf("\n请输入起点的下标："); 
scanf("%d",&qidian); 
for(v=0;v<g.num;v++) 
{ 
mark[v]=0; 
} 
for(v=qidian;v<g.num+qidian;v++) 
{ 
v1=v%g.num; 
if(mark[v1]==0) 
BFS(g,v1,mark); 
} 
} 
/************************3.查找*********************/


void search(GRAPH L)
{int t,i,j;
 char m;
	printf("请输入您要查找的顶点信息:");
    scanf("%c",&m);  
	for(i=0;i<L.num;i++)
	
	if(L.vexs[i]==m){
		t=i;
		for(i=t;i<L.num;i++)
	 L.vexs[i]=L.vexs[i+1];
	 //L->num=L->num-1;
//	}

	for(i=0;i<L.num;i++)
	for(j=t;j<L.num;j++)
	 L.arcs[i][j]=L.arcs[i][j+1];
	for(i=t;i<L.num;i++)
	for(j=0;j<L.num;j++)
	 L.arcs[i][j]=L.arcs[i+1][j];
	L.num=L.num-1;

 printf("\n查找后图的顶点数目为：%d",L.num); 
printf("\n查找后图的各顶点的信息为：\n"); 
for(i=0;i<L.num;i++) 
printf("%c ",L.vexs[i]); 
printf("\n图的边权矩阵的信息为：\n"); 
for(i=0;i<L.num;i++) 
{ 
for(j=0;j<L.num;j++) 
{ 
printf("%6.2f ",L.arcs[i][j]); 
} 
printf("\n"); 
} 
printf("图已经输出完毕！\n"); 
	 }
//  
if (i==L.num)
		printf("没有找到您想查找的顶点");





}
/**********************4.连通性***********************/
int panduan(GRAPH L,int v)
{ 
//int a[L.num];
int mark[max];
int v1,v2,t; 
SEQQUEUE q; 
QueueInit(&q); 
QueueIn(&q,v);
//a[0]=v;
//t=1;

mark[v]=1; 
//printf("%c ",L.vexs[v]); 
t=1;
while(QueueIsEmpty(q)==0) 
{ 
QueueFront(q,&v1); 
QueueOut(&q); 
for(v2=0;v2<L.num;v2++) 
{ 
if(L.arcs[v1][v2]!=0&&mark[v2]==0) 
{ 
QueueIn(&q,v2); 
//a[t]=v2;
//t++;
mark[v2]=1; 
//printf("%c ",g.vexs[v2]); 
t++;
} 
} 
} 

 return t;
} 

void liantong(GRAPH L)
{int j;

//for(i=0;i<L.num;i++)
// panduan(GRAPH L, L.vexs[i],int mark[]);

for(j=0;j<L.num;j++){
 //   if(L.vexs[i]!=L.vexs[j])
//	  if(L.arcs[i][j]!=0)
	if (panduan(L,j)<L.num)
	 printf("否");

	

if(j==L.num)
 printf("yes");
}
//	break;

}




/***********************主函数**********************/ 

void main() 
{ GRAPH tu;
 GraphCreate(&tu); 
 GraphOut(tu);
  int ch2;

printf("\t\t******************************************************\n");
printf("\t\t*          1-------深度优先遍历                      *\n");
printf("\t\t*          2-------广度优先遍历                      *\n");
printf("\t\t*          3-------查找顶点x                         *\n");
printf("\t\t*          4-------是否连通                          *\n");
//printf("\t\t*          5-------退出                              *\n");
printf("\t\t******************************************************\n");
printf("\t\t请选择菜单号(1--4):");
scanf("%d",&ch2);     getchar();

switch(ch2)
{
case 1: GraphDFS(tu); break;
case 2: GraphBFS(tu); break;
case 3: search(tu)  ; break;
case 4: liantong(tu); break;
//case 5: return;
}
//main();
/*printf("\n输入10退出：");
  char aa[10];
scanf("%s",&aa);
if(aa=="exit")

return;
else
main();*/
}