程序代码:
//求最长简单回路
#include <stdio.h>
#include <stdlib.h>
FILE *fin, *fout;//定义输入输出文件指针为全局变量
char buffer;//定义缓冲区
int data;//存放当前获取的数字
/*****************图的存储结构 邻接表***************/
struct Arc
{
int v;//向量表中的下标值
struct Arc *next;
};
struct Graph
{
struct Arc *vex_array;//顶点向量表
int vex_num;//顶点数
int arc_num;//边条数
};
/**************************************************/
/**************** 全局函数 ************************/
void get_char();
void get_sym();
void initial_graph(struct Graph **G);
int search_index(struct Graph *G, int elem);
void traverse(struct Graph *G, int *symbol, int index, int *count);
void way(struct Graph *G);
/**************************************************/
int main()
{
if( (fin=fopen("D:\\input.txt", "r")) == NULL )
{
printf("读取文件失败!\n");
exit(-1);
}
if( (fout=fopen("D:\\output.txt", "w")) == NULL )
{
printf("写文件失败!\n");
exit(-1);
}
struct Graph *G=NULL;//定义指向图的指针变量
initial_graph(&G);
way(G);
return 0;
}
void way(struct Graph *G)
{
int *symbol = (int *) malloc ((G->vex_num+1)*sizeof(int));//定义标志位 判断是否访问过
for(int i=0; i<=G->vex_num; ++i )
{
symbol[i] = 0;//全部初始化为 没有访问过
}
symbol[1] = 1;
int count = 1;//统计有多少点在一条线上
for(struct Arc *p=G->vex_array[1].next; p!=0; p=p->next)
{
if( !symbol[p->v] )
{
symbol[p->v] = ++count;
if( count == G->vex_num )
{
break;
}
traverse(G, symbol, p->v, &count);
if( count == G->vex_num )
{
break;
}
symbol[p->v] = 0;
--count;
}
}
//判断最后一个点是否和开始一个点相连接
--count;
p = G->vex_array[1].next;
while(p)
{
if( p->v == symbol[G->vex_num] )
{
++count;
}
p = p->next;
}
if( count == G->vex_num )
{
printf("\t找到\n");
for(i=1; i<=G->vex_num; ++i )
{
printf("%d ",symbol[i]);
}
}
}
void traverse(struct Graph *G, int *symbol, int index, int *count)
{
for(struct Arc *p=G->vex_array[index].next; p!=0; p=p->next)
{
if( !symbol[p->v] )
{
symbol[p->v] = ++(*count);
if( *count == G->vex_num )
{
return;
}
traverse(G, symbol, p->v, count);
if( *count == G->vex_num )
{
return;
}
symbol[p->v] = 0;
--(*count);
}
}
}
void get_char()
{
if( !feof(fin) )
{
fscanf(fin,"%c", &buffer);
putchar(buffer);
}
return;
}
/*获取一个有用的数字*/
void get_sym()
{
data = 0;//重新置零
get_char();//获取一个符号
while( buffer==10 || buffer==9 || buffer==' ' )
{//过滤掉文件中的换行符 和 空格
get_char();
}
while(buffer!=10 && buffer!=9 && buffer!=' ')
{
data = data*10 + buffer - '0';
get_char();
}
}
/*初始化图*/
void initial_graph(struct Graph **G)
{
int i;
*G = (struct Graph*) malloc (sizeof(struct Graph));
if( NULL==(*G) )
{
printf("\t内存不足!\n");
exit(-1);
}
get_sym();
(*G)->vex_num = data;//初始化顶点数量
get_sym();
(*G)->arc_num = data;//初始化弧的数量
//分配比顶点个数多一个单位的长度空间 使用的时候零号单元不使用
(*G)->vex_array = (struct Arc*) malloc (((*G)->vex_num+1)*sizeof(struct Arc*));
for( i=0; i<=(*G)->arc_num; ++i )
{
(*G)->vex_array[i].v = i;
(*G)->vex_array[i].next = NULL;
}
int v1_site, v2_site, v1, v2;
for( i=1; i<=(*G)->arc_num; ++i)
{
get_sym();
v1 = data;//弧尾的值
v1_site = search_index(*G, v1);//弧尾在顶点向量表中的下标值
get_sym();
v2 = data;//弧头的值
v2_site = search_index(*G, v2);//弧头在顶点向量表中的下标值
//判断弧是否合法
if( !v1_site || !v2_site )
{
printf("\t顶点信息录取有误!\n");
exit(-1);
}
struct Arc *p=NULL;
p = (struct Arc*) malloc (sizeof(struct Arc));
p->v = v2;
p->next = (*G)->vex_array[v1].next;
(*G)->vex_array[v1].next = p;
p = (struct Arc*) malloc (sizeof(struct Arc));
p->v = v1;
p->next = (*G)->vex_array[v2].next;
(*G)->vex_array[v2].next = p;
}
return;
}
/*查找顶点在顶点向量表中的下标值*/
int search_index(struct Graph *G, int elem)
{
int i=0;
G->vex_array[0].v = elem;
for(i=G->vex_num; elem != G->vex_array[i].v; --i );//找到则停止
return i;
}
图片附件: 游客没有浏览图片的权限,请
登录 或
注册