/* ------------------------------------------------------ */
/* PROGRAM euler : */
/* This porgram accepts a multi-graph and finds an */
/* Euler Trail if possible. */
/* */
/* Copyright Ching-Kuang Shene July/30/1989 */
/* ------------------------------------------------------ */
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
#define ALWAYS 1
#define YES 1
#define NO 0
#define SUCCESS 1
#define FAIL -1
/* ------------------------------------------------------ */
/* types and external variables */
/* ------------------------------------------------------ */
typedef struct node Node; /* trail node (linked list) */
struct node { /* a node consists of ... */
int vertex; /* a vertex number field */
Node *next; /* and a next node ptr */
};
int connect[MAXSIZE][MAXSIZE]; /* the connection matrix */
int deg[MAXSIZE]; /* degree array */
int n; /* number of vertices */
Node *trail; /* pointer to Euler trail */
/* ------------------------------------------------------ */
/* function prototypes */
/* ------------------------------------------------------ */
void read_in(void);
Node *euler(void);
int prepare(Node **, Node **);
int find_next(Node **);
void find_trail(int, Node **, Node **);
void display(void);
/* ------------------------------------------------------ */
void main(void)
{
printf("\nEuler Trail Program");
printf("\n===================\n");
read_in(); /* get data */
trail = euler(); /* compute Euler Trail */
display(); /* display result */
}
/* ------------------------------------------------------ */
/* FUNCTION read_in : */
/* This function reads in the connection matrix and */
/* then compute the degree array. */
/* ------------------------------------------------------ */
void read_in(void)
{
int i, j;
char line[100];
gets(line); /* get in number of vertices*/
n = atoi(line);
for (i = 0; i < n; i++) { /* clear the connection mtx*/
deg[i] = 0;
for (j = 0; j < n; j++)
connect[i][j] = 0;
}
gets(line); /* get 1st line of edge set */
sscanf(line, "%d%d", &i, &j);
while (i != 0 && j != 0) { /* end of file ? */
if (i != j) { /* a loop ? */
connect[i-1][j-1]++; /* increase edge cnt*/
connect[j-1][i-1]++;
deg[i-1]++; /* increase degree count */
deg[j-1]++;
}
else /* ignore all self loops */
printf("\n*** ERROR *** A loop found. Data ignored");
gets(line); /* get next edge */
sscanf(line, "%d%d", &i, &j);
}
}
/* ------------------------------------------------------ */
/* FUNCTION euler : */
/* This is the main working routine of this program. */
/* It calls prepare() to initialize various data field and*/
/* some checks. Then compute the Euler Trail loop by loop*/
/* ------------------------------------------------------ */
Node *euler(void)
{
Node *current; /* processing cursor */
Node *head, *tail; /* bound a partial trail */
Node *p1, *p2; /* working pointer variables*/
int VTX;
if (prepare(&head, &tail) == FAIL) /* prepare data */
return NULL; /* if fail, return NULL */
current = tail; /* start from the tail */
while (ALWAYS)
if ((VTX = find_next(¤t)) != FAIL) {
find_trail(VTX, &p1, &p2);
p2->next = current->next; /* join the trail*/
current->next = p1;
current = p1; /* step to next node */
}
else
break;
return head; /* return the trail list */
}
/* ------------------------------------------------------ */
/* FUNCTION prepare : */
/* This function checks to see if there are more two */
/* odd degree vertices. It reject a graph with more than */
/* two odd degree vertices. Then it builds a preliminary */
/* trail list consisting of one node (if all vertices are */
/* even), or two nodes (for the two odd degree vertices). */
/* ------------------------------------------------------ */
int prepare(Node **first, Node **last)
{
Node *p1, *p2;
int no, odd_no, i;
int odd[2];
for (no = odd_no = i = 0; i < n; i++) /* test odd deg*/
if (deg[i] % 2 != 0) {
odd_no++;
if (no < 2)
odd[no++] = i;
}
if (odd_no > 2) { /* more than two odd deg VTX*/
printf("\n*** ERROR *** too many odd degree vertices.");
return FAIL;
}
if (odd_no == 2) { /* exactly two odd VTX */
p1 = (Node *) malloc(sizeof(Node)); /* get mem. */
p2 = (Node *) malloc(sizeof(Node));
connect[odd[0]][odd[1]]--; /* just remove this */
connect[odd[1]][odd[0]]--; /* odd degree edge */
deg[odd[0]]--;
deg[odd[1]]--;
p1->vertex = odd[0]; /* these two vertices are */
p1->next = p2; /* the must for first step */
p2->vertex = odd[1]; /* thus put them into the */
p2->next = NULL; /* trail list */
*first = p1; /* return this list */
*last = p2;
}
else { /* all vertices are even */
p1 = (Node *) malloc(sizeof(Node)); /* get mem. */
p1->vertex = 0; /* it is the only one node */
p1->next = NULL; /* in the trail list */
*first = *last = p1;/* return the trail list */
}
return SUCCESS;
}
/* ------------------------------------------------------ */
/* FUNCTION find_next : */
/* Given a pointer to some vertex which has already */
/* been put into trail list, this function scans the trail*/
/* list in order to find a vertex with non-zero degree. */
/* ------------------------------------------------------ */
int find_next(Node **p)
{
for (;(*p)!=NULL && deg[(*p)->vertex]==0; (*p)=(*p)->next)
;
return ((*p) == NULL) ? FAIL : (*p)->vertex;
}
/* ------------------------------------------------------ */
/* FUNCTION find_trail : */
/* Given a vertex, this function computes a trail */
/* starting from the given vertex and returns the trail */
/* list found. */
/* ------------------------------------------------------ */
void find_trail(int start, Node **head, Node **tail)
{
Node *first, *last, *ptr;
int p, i, done;
first = last = NULL; /* no node in list currently*/
p = start; /* p is a moving vertex */
done = NO;
while (ALWAYS) {
for (i = 0; i < n && !connect[p][i]; i++)
; /* find a VTX adjacent to p */
if (i < n) { /* p->i is possible */
connect[p][i]--, connect[i][p]--;
deg[p]--, deg[i]--;
没有合适的资源?快使用搜索试试~ 我知道了~
C语言名题精选百则源程序
共131个文件
c:119个
in1:4个
in2:4个
2星 需积分: 15 21 下载量 184 浏览量
2013-05-27
20:37:40
上传
评论
收藏 134KB RAR 举报
温馨提示
《C语言名题精选百则》(技巧篇)收集了100则C语言程序设计题,共分9类。第一类比较简单,主要希望读者了解到《C语言名题精选百则》(技巧篇)的题目、解法与其他书籍之间的差异;第二至六类分别是关于数字、组合数学或离散数学、查找、排序、字符串等方面的题目;第七类列出了一些不太容易归类的题目,如Buffon丢针问题、Dijkstra的三色旗问题等;第八类则收录了一些有趣的、娱乐性的题目,如魔方阵等;第九类题目相对较难,且多数是程序设计的名题。
资源推荐
资源详情
资源评论
收起资源包目录
C语言名题精选百则源程序 (131个子文件)
EULER.C 9KB
HEAPMERG.C 9KB
LOG_DUP.C 8KB
LIMITS.C 7KB
BUCKET.C 7KB
ARITH.C 6KB
PREFIX.C 6KB
LIFE.C 6KB
CLASSIFY.C 6KB
SHORTEST.C 6KB
MAXVISIT.C 6KB
KNIGHT.C 6KB
STREDIT.C 6KB
STABLE.C 6KB
CONTAIN.C 5KB
MATMUL_S.C 5KB
N_QUEEN1.C 5KB
HAMILTON.C 5KB
QSORT_L.C 5KB
MAXSET.C 5KB
FACTLOG.C 4KB
MATMUL.C 4KB
MAGIC_SE.C 4KB
POLISH.C 4KB
MAXSQR2.C 4KB
PRODSEQ.C 4KB
DISTSEQ.C 4KB
QSORT.C 4KB
KNAPSACK.C 4KB
N_QUEENR.C 4KB
INF_SRCH.C 4KB
MAX_REPS.C 4KB
HEAPSORT.C 3KB
MEDIAN2.C 3KB
MEDIAN1.C 3KB
FIB_MT.C 3KB
1TO1.C 3KB
KMP.C 3KB
BM.C 3KB
FACTLOG2.C 3KB
1ST&2ND.C 3KB
CNR_LOG.C 3KB
MONO_MAX.C 3KB
MAXSUM1.C 3KB
HANOI_I.C 3KB
LCS.C 3KB
PAR_GEN.C 3KB
MAXSQR.C 3KB
HEAP_NEW.C 3KB
RH_SEQ.C 3KB
TURNS.C 3KB
PARCOUNT.C 3KB
VOTING.C 3KB
RECT.C 3KB
M_SORT.C 3KB
GRAYCODE.C 3KB
INTPART.C 2KB
BALANCE.C 2KB
DIAMETER.C 2KB
SETPART.C 2KB
TRENTE.C 2KB
M_SEARCH.C 2KB
SINK.C 2KB
LOT_DUP.C 2KB
LIS.C 2KB
X_ATOI.C 2KB
MAGIC_O.C 2KB
DOMINATR.C 2KB
FIXSUM.C 2KB
MAGIC_DE.C 2KB
FLAG.C 2KB
SUBSEQ.C 2KB
EX_FIB.C 2KB
KSUBSET.C 2KB
L_SIEVE.C 2KB
SEARCH3.C 2KB
MAXPROD.C 2KB
BINSERT.C 2KB
INTPART#.C 2KB
B_SEARCH.C 2KB
H_SEQ.C 2KB
QSORT_I.C 2KB
TWOSQUAR.C 2KB
BUFFON.C 2KB
SIEVE.C 2KB
PRIME1.C 2KB
MAXCOVER.C 2KB
FACTOR.C 2KB
UNIQUE.C 2KB
MINDIST.C 2KB
DIRECT.C 2KB
GIVENSUM.C 2KB
EQ_COUNT.C 2KB
PERMUT_R.C 2KB
HEADTAIL.C 2KB
SHELL.C 2KB
UGLY.C 2KB
CHANGE.C 2KB
LEXICAL.C 2KB
ISEARCH.C 2KB
共 131 条
- 1
- 2
资源评论
- smallsjzhou2013-06-04资源还可以参考。
joker_wqz
- 粉丝: 3
- 资源: 18
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功