/*===================骑士周游算法--用链栈实现===================*/
#include<stdio.h>
#include <malloc.h>
#define LEN sizeof(struct stack)
struct stack
{int row;
int col;
int dir;
struct stack *next;
struct stack *prior;
};
struct stack*head = (struct stack*)malloc(LEN);
struct stack*q=head;

void push(int i,int j,int v)
{
struct stack *p=(struct stack*)malloc(LEN);
p->row=i;
p->col=j;
p->dir=v;
p->next=q;
q=p;
}

void pop()
{struct stack *temp;
temp=q->prior;
free(q);
q=temp;

}
void start()
{ int y,z,v=0;
int i,j;
int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};
int c[6][6];
for(i=0;i<6;i++)
{for(j=0;j<6;j++)
c[j]=0;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0;
while(account<35)
{
while(v<8)
{
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0)
{ push(y,z,v+1);
account++;
c[y][z]=account;
y=i;
z=j;
v=0;
}
else v++;
}
if(v==8&&account>0&&account!=35)
{
y=q->row;
z=q->col;
v=q->dir;
pop();

c[y][z]=0;
account--;
}
}
c[y][z]=36;
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf("%4d",c[j]);
}
printf("\n");
}
}

void main()
{printf("\n");
start();
}

/*=====================================================*/
/*=======================骑士周游算法--用数组实现==============*/
#include<stdio.h>
#include<conio.h>
#include <malloc.h>
#define LEN sizeof(struct stack)

int stack[36][3];
int top=0;
void push(int i,int j,int k)
{ stack[top][0]=i;
stack[top][1]=j;
stack[top][2]=k;
top++;
}
void pop()
{top--;
}

void start()
{ int y,z,v=0;
int i,j;
int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};
int c[6][6];
for(i=0;i<6;i++)
{for(j=0;j<6;j++)
c[j]=0;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0;
while(account<35)
{
while(v<8)
{
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0)
{ push(y,z,v+1);
account++;
c[y][z]=account;
y=i;
z=j;
v=0;
}
else v++;
}
if(v==8&&account>0&&account!=35)
{
y=q->row;
z=q->col;
v=q->dir;
pop();
// y=stack[top][0];
// z=stack[top][1];
// v=stack[top][2];
c[y][z]=0;
account--;
}
}
c[y][z]=36;
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf("%4d",c[j]);
}
printf("\n");
}
}

void main()
{printf("\n");
start();
}

/*=====================================================*/
/*========================骑士周游算法--用双向链表实现==========*/

#include<stdio.h>
#include <malloc.h>
#define LEN sizeof(struct stack)
struct stack
{int row;
int col;
int dir;
struct stack *next;
struct stack *prior;
};
struct stack*head = (struct stack*)malloc(LEN);
struct stack*q=head;

void push(int i,int j,int v)
{
struct stack *p=(struct stack*)malloc(LEN);
p->row=i;
p->col=j;
p->dir=v;
q->next=p;
p->prior=q;
q=p;
}

void pop()
{struct stack *temp;
temp=q->prior;
free(q);
q=temp;

}
void start()
{ int y,z,v=0;
int i,j;
int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};
int c[6][6];
for(i=0;i<6;i++)
{for(j=0;j<6;j++)
c[j]=0;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0;
while(account<35)
{
while(v<8)
{
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0)
{ push(y,z,v+1);
account++;
c[y][z]=account;
y=i;
z=j;
v=0;
}
else v++;
}
if(v==8&&account>0&&account!=35)
{
y=q->row;
z=q->col;
v=q->dir;
pop();

c[y][z]=0;
account--;
}
}
c[y][z]=36;
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf("%4d",c[j]);
}
printf("\n");
}
}

void main()
{printf("\n");
start();
}

/*=====================================================*/
/*======================算法分析==========================*/
/*======================骑士周游算法分析--用链栈实现=============*/
算法思想：
主要用链栈实现，即用单链表来实现栈结构。
与双向链表实现区别仅在于push和pop操作
#include<stdio.h>
#include<conio.h>
#include <malloc.h>
#include <stdio.h>
#define LEN sizeof(struct stack)

struct stack
{int row;
int col;
int dir;
struct stack *next;
};

struct stack*head = (struct stack*)malloc(LEN);
struct stack*q=head;

void push(int i,int j,int v)
{
struct stack *p=(struct stack*)malloc(LEN);
p->row=i;
p->col=j;
p->dir=v;
p->next=q;
q=p;
}

void pop()
{struct stack *temp;
temp=q->next;
free(q);
q=temp;
}

void start()
{ int y,z,v=0;
int i,j;
int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};
int c[6][6];
for(i=0;i<6;i++)
{for(j=0;j<6;j++)
c[j]=0;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0;
while(account<35)
{
while(v<8)
{
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0)
{ push(y,z,v+1);
account++;
c[y][z]=account;
y=i;
z=j;
v=0;
}
else v++;
}
if(v==8&&account>0&&account!=35)
{
y=q->row;
z=q->col;
v=q->dir;
pop();
// y=stack[top][0];
// z=stack[top][1];
// v=stack[top][2];
c[y][z]=0;
account--;
}
}
c[y][z]=36;
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf("%4d",c[j]);
}
printf("\n");
}
}

void main()
{printf("\n");
start();
}

程序运行结果：
input y:1
input z:2
36 21 12 27 30 19
11 26 1 20 13 28
22 35 14 29 18 31
25 10 23 2 7 4
34 15 8 5 32 17
9 24 33 16 3 6

input y:3
input z:2
26 21 12 35 32 19
11 36 25 20 13 34
24 27 22 33 18 31
7 10 1 16 3 14
28 23 8 5 30 17
9 6 29 2 15 4

/*=====================================================*/
/*=================骑士周游算法分析--用数组实现==================*/
算法思想:
用一个二维的数组stack[36][3]充当栈的作用,用来记录36个位置的行,列,以及方向.设置全程标量top,用来指向当前位置.用push()和pop()函数分别实现压栈和出栈.
start()函数则是具体实现骑士周游算法的函数.具体思想见注释.
#include<stdio.h>
#include<conio.h>
#include <stdio.h>
int stack[36][3];//设置一个全程的数组
int top=0;//设置全程的变量top.
//push()函数用来表示压栈操作
void push(int i,int j,int k)
{ stack[top][0]=i;
stack[top][1]=j;
stack[top][2]=k;
top++;
}
//pop（）函数用来表示出栈操作
void pop()
{top--;
}
//start()函数用来具体执行骑士周游的算法
void start()
{ int y,z,v=0;
int i,j;
int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};//设置8个方向
int c[6][6];//设置一个二维数组，用来打印出周游的具体路线
for(i=0;i<6;i++)
{for(j=0;j<6;j++)
c[j]=0;
}//初始化数组
printf("input y:");
scanf("%d",&x);
printf("input z:");
scanf("%d",&y);//由用户输入初始起跳位置
int account=0;//设置一个计数器，用来清楚的显示骑士走的路线
while(account<35)
{
while(v<8)
{
i=x+move[v][0];
j=y+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0)
{ push(x,y,v+1);//若一个位置可走，则把前一个位置及下一个要走的方向压栈
account++;
c[x][y]=account;
x=i;
y=j;
v=0;
}
else v++;//若一个位置走不通，则换一个方向再试
}
if(v==8&&account>0&&account!=35)//加入8个方向全已经走过，则弹出刚进
栈的那个元素。

{ pop();
// y=q->row;
// z=q->col;
// v=q->dir;
x=stack[top][0];
y=stack[top][1];
v=stack[top][2];
c[x][y]=0;//由于已经把c[x][y]上的元素弹出，则把该位置清零。
　　　　　　　　account--;
}
}
c[x][y]=36;//把最后一个元素置为36。
for(i=0;i<6;i++)//打印周游路线
{
for(j=0;j<6;j++)
{
printf("%4d",c[j]);
}
printf("\n");
}
}

void main()
{printf("\n");
start();
}

程序运行结果：
input y:1
input z:2
36 21 12 27 30 19
11 26 1 20 13 28
22 35 14 29 18 31
25 10 23 2 7 4
34 15 8 5 32 17
9 24 33 16 3 6

input y:3
input z:2
26 21 12 35 32 19
11 36 25 20 13 34
24 27 22 33 18 31
7 10 1 16 3 14
28 23 8 5 30 17
9 6 29 2 15 4

/*=====================================================*/
/*=================骑士周游算法分析--用双向链表实现===============*/
注意：此算法需已经在tubor c++ 中通过，但在vc++有些问题，主要在struct stack*head = (struct stack*)malloc(LEN);
struct stack*q=head;这两条语句的定义上
算法分析：
此算法主要用双向链表来存储和删除位置元素，其他部分与数组实现的算法一样，不再赘述。
#include<stdio.h>
#include <malloc.h>
#define LEN sizeof(struct stack)
//定义一个结构变量
struct stack
{int row;
int col;
int dir;
struct stack *next;
struct stack *prior;
};
struct stack*head = (struct stack*)malloc(LEN);//定义一个头指针，使得能形成整个链表
struct stack*q=head;//定义一个指向结构体的指针，总是用来指向当前结点
//压栈操作，每压一个，连入双向链表中
void push(int i,int j,int v)
{
struct stack *p=(struct stack*)malloc(LEN);
p->row=i;
p->col=j;
p->dir=v;
q->next=p;
p->prior=q;
q=p;
}
//出栈操作，清空当前元素
void pop()
{struct stack *temp;
temp=q->prior;
free(q);
q=temp;

}
void start()
{ int y,z,v=0;
int i,j;
int move[8][2]={2,1,1,2,1,-2,2,-1,-2,1,-1,2,-1,-2,-2,-1};
int c[6][6];
for(i=0;i<6;i++)
{for(j=0;j<6;j++)
c[j]=0;
}
printf("input y:");
scanf("%d",&y);
printf("input z:");
scanf("%d",&z);
int account=0;
while(account<35)
{
while(v<8)
{
i=y+move[v][0];
j=z+move[v][1];
if(i>=0&&i<=5&&j>=0&&j<=5&&c[j]==0)
{ push(y,z,v+1);
account++;
c[y][z]=account;
y=i;
z=j;
v=0;
}
else v++;
}
if(v==8&&account>0&&account!=35)
{
y=q->row;
z=q->col;
v=q->dir;
pop();

c[y][z]=0;
account--;
}
}
c[y][z]=36;
for(i=0;i<6;i++)
{
for(j=0;j<6;j++)
{
printf("%4d",c[j]);
}
printf("\n");
}
}

void main()
{printf("\n");
start();
}
程序运行结果：
input y:1
input z:2
36 21 12 27 30 19
11 26 1 20 13 28
22 35 14 29 18 31
25 10 23 2 7 4
34 15 8 5 32 17
9 24 33 16 3 6

input y:3
input z:2
26 21 12 35 32 19
11 36 25 20 13 34
24 27 22 33 18 31
7 10 1 16 3 14
28 23 8 5 30 17
9 6 29 2 15 4


=====================================================================
http://www.08090.com/c/sr/showart.asp?art_id=29&cat_id=2