骑士周游算法     /*===================骑士周游算法--用链栈实现===================*/#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:1input z:236 21 12 27 30 1911 26 1 20 13 2822 35 14 29 18 3125 10 23 2 7 434 15 8 5 32 179 24 33 16 3 6input y:3input z:226 21 12 35 32 1911 36 25 20 13 3424 27 22 33 18 317 10 1 16 3 1428 23 8 5 30 179 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:1input z:236 21 12 27 30 1911 26 1 20 13 2822 35 14 29 18 3125 10 23 2 7 434 15 8 5 32 179 24 33 16 3 6input y:3input z:226 21 12 35 32 1911 36 25 20 13 3424 27 22 33 18 317 10 1 16 3 1428 23 8 5 30 179 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:1input z:236 21 12 27 30 1911 26 1 20 13 2822 35 14 29 18 3125 10 23 2 7 434 15 8 5 32 179 24 33 16 3 6input y:3input z:226 21 12 35 32 1911 36 25 20 13 3424 27 22 33 18 317 10 1 16 3 1428 23 8 5 30 179 6 29 2 15 4=====================================================================http://www.08090.com/c/sr/showart.asp?art_id=29&cat_id=2  

评论