骑士周游算法分析--用双向链表实现.txt

数据结构 之骑士周游算法

注意：此算法需已经在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[i][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[i][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[i][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