当前位置:首页 >> 信息与通信 >>

欧拉回路代码


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

struct street
{
int x, y; /* ending junctions */
int number; /* numbe

r of the street */

int nextx, nexty; /* single linked lists started by junctions[i] */

int prev, next; /* index of previous and next street in the solution */
}
streets[2048];

int junctions[64]; /* index of unused street going to junction with smallest number */

int path(int junction, int *start_street, int *end_street) /* returns ending junction */
{
int street, s;

street = -1;

for(;;)
{
if((s = junctions[junction]) == -1)
{
if(street == -1)
*start_street = -1;

*end_street = street;

return junction;
}

if(streets[s].next == -1) /* unused street */
{
if(street == -1)
{
streets[s].prev = -2;
*start_street = s;
}
else
{
streets[s].prev = street ;
streets[street].next = s;
}

streets[s].next = -2;

junctions[junction] = (streets[s].x == junction)
? streets[s].nextx : streets[s].nexty;

junction = (streets[s].x != junction) ?
streets[s].x : streets[s].y;

street = s;
}
else
{
junctions[junction] = (streets[s].x == junction) ?
streets[s].nextx : streets[s].nexty;
}
}
}

int number_cmp(const void *a, const void *b)
{
return ((struct street *)a)->number - ((struct street *)b)->number;
}

#define min(a, b) (((a) < (b)) ? (a) : (b))

void print(int start_street)
{
int s;

printf("%d", streets[start_street].number);

for(s = streets[start_street].next; s != start_street; s = streets[s].next)
printf(" %d", streets[s].number);

printf("\n");
}

void main()
{
int count, junction, start_street, street, i, s, e, ss;

for(;;)
{
count = 0;

for(;;)
{
scanf("%d%d", &streets[count].x, &streets[count].y);
if(!streets[count].x || !streets[count].y) break;

scanf("%d", &streets[count++].number);
}

if(!count) break;

junction = min(streets[0].x, streets[0].y);

qsort(streets, count, sizeof(streets[0]), number_cmp);

memset(junctions, -1, sizeof(junctions));

for(i = count - 1; i >= 0; i--)
{
streets[i].nextx = junctions[streets[i].x];
junctions[streets[i].x] = i;

streets[i].nexty = junctions[streets[i].y];
junctions[streets[i].y] = i;

streets[i].prev = -1;
streets[i].next = -1;
}

if(path(junction, &start_street, &e) != junction)
goto fail;

streets[start_street].prev = e;
streets[e].next = start_street;

street = start_street;

do
{
again:
if(path(junction, &s, &e) != junction)
goto fail;

if(s != -1 && e != -1)
{
ss = streets[street].prev;

streets[s].prev = ss;
streets[ss].next = s;

streets[street].prev = e;
streets[e].next = street;

goto again;
}

street = streets[street].prev;

junction = (streets[street].x != junction) ?
streets[street].x : streets[street].y;
}
while(street != start_street);

print(start_street);

continue;

fail:
printf("Round trip does not exist.\n");
}
}

相关文章:
欧拉回路的判定_设计文档
软件设计文档 I 文档管理信息表项目名称 版本 内容 关键字 参考文档 创建时间 创建人 最新发布日期 欧拉回路判定 编写代码 欧拉回路 数据结构课本(C 语言版) 文档...
欧拉回路解题实例分
欧拉回路解题实例分_计算机软件及应用_IT/计算机_专业资料。题目意思: 给你一个...代码: [cpp] <SPAN style="FONT-SIZE: 18px">#include<iostream> #include...
欧拉回路
一、欧拉回路 所谓欧拉回路与哥尼斯堡 7 桥问题相联系的. 在哥尼斯堡 7 桥...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 欧拉回路的算法...
欧拉回路的算法演示
欧拉回路的算法演示_数学_自然科学_专业资料。欧拉图中欧拉回路的算法,演示,及分析...求欧拉回路,Fleury算法的... 6页 1下载券 欧拉回路代码 2页 免费 第19讲 ...
欧拉回路
欧拉回路代码 2页 免费 欧拉回路性质与应用探究 25页 免费 欧拉回路与二分图匹配...(来自某未署名的大牛的 word) 1、基本概念: 、基本概念: (1)定义 欧拉通路...
欧拉回路
欧拉回路_军事/政治_人文社科_专业资料。三、欧拉回路 1、欧拉路:在无孤立顶点...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 欧拉回路的算法...
求欧拉回路的Fleury算法
求​欧​拉​回​路​的​F​l​e​u​r​y​算​法 暂无评价|0人阅读|0次下载|举报文档 求​欧​拉​回​路​的​F...
欧拉回路设计报告
欧拉回路设计报告_交通运输_工程科技_专业资料。你值得拥有。合肥学院 计算机科学与技术系课程设计报告 2012 ~2013 学年第 二 学期 课学学专指业导班教生姓 程...
欧拉回路
欧拉回路 const maxn=100; var g:array[1..maxn,1..maxn] of longint; ...欧拉回路代码 2页 免费 欧拉回路与中国邮递员问... 3页 免费 第19讲 欧拉回路...
求欧拉回路,Fleury算法的C语言实现[1]
欧拉回路代码 暂无评价 4页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出...欧拉(Euler)通路/回路 1、基本概念: 、基本概念: (1)定义 欧拉通路 (欧拉迹...
更多相关标签:
欧拉回路 | 欧拉回路算法 | 题目1027 欧拉回路 | 欧拉通路和欧拉回路 | 求欧拉回路 | 欧拉回路 c | 欧拉回路判断 | 有向图欧拉回路 |