马踏棋盘 栈 链表 按照老师的要求的。大家来下载吧· 但是计算算法比较冗余,计算不较慢。 #include <iostream> #include "conio.h" using namespace std; #define edgetype int #define vextype int #define MAX 8 typedef struct node { int vextex;//序号 struct node *next; }edgenode; typedef struct { int vextex; int x,y; edgenode *link; }vexnode; const int px[8]={1,2,2,1,-1,-2,-2,-1}; const int py[8]={2,1,-1,-2,-2,-1,1,2}; const int L=8,H=8; vexnode ga[L*H]; //图 int visited[L*H]={0}; typedef struct /*顺序栈的结构体类型定义*/ { int stack[L*H]; int top; }seqstack; seqstack s; void setnull(seqstack *s) /*置空栈-由于c语言的数组下标是从0开始的,所以置 空栈操作时将栈顶指针放在下标为0之前,即-1处。*/ {s->top=-1;} int empty(seqstack *s) /*判断当前栈是否为空栈*/ { if(s->top<0) return 1; else return 0; } int push(seqstack *s,int x) /*把元素x压入栈s中*/ { if(s->top>L*H-1) { printf("stack overflow!\n"); /*发生上溢*/ return 0; } else { s->stack[++s->top] = x; /*栈顶指针上移,数据元素入栈*/ return 1; } } int pop(seqstack *s) /*弹出当前栈s的栈顶元素*/ { if(s->top<0) { printf("stack empty!\n"); /*栈空,返回空值*/ return NULL; } else { s->top--; return(s->stack[s->top+1]); }/*由于return语句的特点,必须先使top减1,然后再执行return语句。而此时栈顶元素的表示应该为s->top+1.*/ } void init() { int n; for (int i=0;i<H;i++) { for (int j=0;j<L;j++) { n=L*i+j; ga[n].vextex=n; ga[n].x=j; ga[n].y=i; ga[n].link=NULL; } } printf("\n"); for (i=0;i<L*H;i++) //列出邻接链表 { edgenode *p; for (int k=0;k<MAX;k++) { int tx=ga[i].x+px[k]; int ty=ga[i].y+py[k]; if(tx<0||ty<0||tx>=L||ty>=H) continue; //出界了 else //采用前插法 { p=(edgenode*)malloc(sizeof(edgenode)); p->vextex=ty*L+tx; p->next=ga[i].link; ga[i].link=p; // printf("%d ",ga[i].link->vextex); } } } for (i=0;i<L*H;i++) { printf("%d ",ga[i].vextex); if (!((i+1)%L)) { printf("\n"); } } } void show() //打印邻接表 { int i; printf("\n"); for (i=0;i<L*H;i++) { printf("%d->",ga[i].vextex); edgenode *p; p=(edgenode*)malloc(sizeof(edgenode)); p=ga[i].link; while (p!=NULL) { printf("%d ",p->vextex); p=p->next; } printf("\n"); } } int HFS(int n) { edgenode *p; //printf("(Top:%d)",s.top); //printf("%d->",n); push(&s,ga[n].vextex); //结点入栈 p=ga[n].link; visited[n]=1; while (p!=NULL) { if (!visited[p->vextex]) { //printf("%d,",p->vextex); if(HFS(p->vextex)) return 1; } p=p->next; } if (s.top==L*H-1) //找到 { return 1; } visited[s.stack[s.top]]=0; pop(&s); if (empty(&s)) { return 0; } return 0; } void showanswer() { int rank[L*H]; for (int i=L*H-1;i>=0;i--) { rank[pop(&s)]=i+1; } for (i=0;i<L*H;i++) { if (i%L==0&&i) { printf("\n"); } printf("%d ",rank[i]); } } int main() { int n; for (n=0;n<H*L;n++) { memset(visited,0,sizeof(visited)); init(); show(); setnull(&s); if (HFS(n)) { printf("\nStar From %d:\n",n); printf("answer:\n"); showanswer(); } else printf("\nNo Answer!\n\n"); getch(); } return 0; }
- 粉丝: 17
- 资源: 27
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助