数据结构课程设计-马踏棋盘

PAGEPAGE7目录TOC\o"1-2"\h\z\u1前言 12需求分析 12.1任务和要求 12.2运行环境 12.3开发工具 13分析和设计 13.1系统分析及设计思路 13.2主要数据结构及算法 23.3函数流程图 24具体代码实现 95课程设计总结 165.1程序运行结果 165.2设计结论 16参考文献 18致谢 18

1前言编写一个C语言程序，作为国际象棋中的马踏遍棋盘的演示程序。在这里，我们用一个main函数通过调用其他一些分功能函数来实现求并且输出马踏遍棋盘的行走路线。2需求分析2.1任务和要求将马随机放在国际象棋的8×8棋盘的某个方格中，马按照走棋的规则进行移动。每个方格只进入一次，走遍棋盘的全部64个方格。编写算法，求出马的行走路线，并按求出的行走路线，将1,2,…,64依次填入一个8×8的方阵，并输出。要求：画出算法的流程图，分析算法的时间复杂度。2.2运行环境（1）WINDOWS2000/XP系统（2）VisualC++6.0编译环境或TC编译环境2.3开发工具C语言3分析和设计3.1系统分析及设计思路根据需求分析可知，我们所设计的程序要达到让马从任意一起点出发都不重复地遍历所有的8×8棋格的功能。按照需求，并考虑到程序的可读性，我们按顺序共设计了以下六大模块：定义头文件和宏定义模块：这是C程序必不可少的一个部分，通过头文件来调用程序所需库函数，而通过宏定义进行宏替换。(2)数据类型定义模块：该模块定义了全局数据结构，它们的作用域为从定义开始到本源文件结束，以便于让后面很多函数都可以用到它们，而不必再重新定义。(3)探寻路径函数模块：按照马的行走规则对棋盘进行遍历，寻找马的行走路径，每次仅访问一个棋格，保证每个棋格都访问到且每个棋格仅访问一次。(4)输出路径函数模块：对探寻路径函数模块中保存下来的顺序进行输出，输出格式按照棋盘8×8的方阵格式。(5)起始坐标函数模块：将马的起始位置坐标与棋盘坐标联系起来，通过调用探寻路径函数和输出路径函数达到预期效果。(6)主程序模块：主要是完成棋盘初始化，输入，调用等任务进而来完成马踏棋盘问题。另外，一般来说，当马位于（i,j）时，可以走下列8个位置之一：（i-2,j+1)(i-1,j+2)(i+1,j+2)(i+2,j+1)(i+2,j-1)(i+1,j-2)(i-1,j-2)(i-2,j-1)这8个可能的位置可以用两个一维数组存放，利用一维数组表示马在棋盘内新位置。但是，如果(x,y)靠近棋盘的边缘，上述位置可能超出棋盘范围，成为不允许的位置。3.2主要数据结构及算法（1)定义头文件和宏定义#include<stdio.h> #defineMAXSIZE100 #defineN8（2）数据类型定义intboard[8][8];定义棋盘；intHtry1[8]={1,-1,-2,2,2,1,-1,-2}；intHtry2[8]={2,-2,1,1,-1,-2,2,-1};Htry1[8]和Htry2[8]分别表示马各个出口位置相对当前位置的横坐标和纵坐标的增量数组；structStack { inti; intj; intdirector; }stack[MAXSIZE]; inttop=-1;这里是定义栈类型，其中i是横坐标，j是纵坐标，director是存储方向，stack[MAXSIZE]表示定义一个栈数组，top=-1表示栈指针，可以存储棋盘上的信息以及栈中元素移动情况。(3)探寻路径函数定义一个TryPath(inti,intj)函数来探寻马的行走路径，此函数通过while（top>-1）语句将程序控制在栈不为空的情况下进行循环，在while循环中，首先通过一个双重for循环记录下当前位置的下一个位置的可行路径条数，在通过一个双重for循环将前面可行路径条数从小到大排序存储在数组中，最后通过一个for循环来向8个方向进行探寻。(4)输出路径函数定义一个Display()函数来按照棋盘格式输出马的探寻路径，此函数通过一个双重for循环来实现的，外循环控制横坐标的增加，内循环控制纵坐标的增加。（5）起始坐标函数定义一个InitLocation(intxi,intyi)函数将马的行走路径与棋盘坐标联系起来达到预期效果，此函数是通过栈将马的起始位置与棋盘坐标联系起来的，并且调用了TryPath(inti,intj)函数和Display()函数。(6)主函数在main()函数中，我们通过一个双重for循环控制棋盘的横纵坐标完成了对棋盘的初始化，在通过一个三个表达式都为空的for循环来控制输入正确的横纵坐标，直到输入正确才跳出循环在执行下面的语句，最后通过调用InitLocation(intxi,intyi)函数完整了整个马踏棋盘问题。时间复杂度分析：在main()函数中，棋盘初始化的时间复杂度为O（N^2)，接着经过一个for循环，其时间复杂度为O（1），再往下调用InitLocation(x-1,y-1)函数时，要经过一个while(top>-1)，在while循环中还有双重for循环，因此时间复杂度比较大，故总的时间复杂度也比较大。3.3函数流程图（1）主函数流程图开始开始inti,j;inti,j;printf("******printf("***********马踏棋盘***********\n\n");i<Ni<NNJ<NJ<NNi++Yi++board[i][j]=0;j++printf("Pleaseprintf("Pleaseinputimportpoint(1<=x<=8and1<=y<=8)\n\n");printf("请输入起始位置的横坐标x=");printf("请输入起始位置的横坐标x=");123123scanf("%d",&x);printf("\n");scanf("%d",&x);printf("\n");printf("输入起始位置的纵坐标y=");printf("输入起始位置的纵坐标y=");scanf("%d",&scanf("%d",&y);printf("\n")x>=1&&x<=8&&y>=1&&y<=8x>=1&&x<=8&&y>=1&&y<=8Yprintf("Yourinputisworng!!!\n");Nprintf("Yourinputisworng!!!\n");printf("beginwith%dboard:\n\n",8*(x-1)+y);printf("beginwith%dboard:\n\n",8*(x-1)+y);InitLocation(x-1,y-1);InitLocation(x-1,y-1);return0;return0;结束结束图3.1main函数流程图（2）探寻路径函数流程图661 h=0h=0h<8Nh<8Y min=9; min=9;k=0k=0k<8k<8NYmin>a[k]min>a[k]Ymin=a[k];d[h]=k;s=k;min=a[k];d[h]=k;s=k;k++a[s]=9;h++a[s]=9;h++director=stack[top].director;director=stack[top].director;top>=63top>=63return(1);find=0;h=director+1h=director+1h<8Nh<8i=stack[top].i+Htry1[d[h]];Yi=stack[top].i+Htry1[d[h]];54235423h++j=stack[top].j+Htry2[d[h]];h++j=stack[top].j+Htry2[d[h]];(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8NNNfind=1; break;find=1; break;find=1Nstack[top].director=director;top++;Ystack[top].director=director;top++;stack[top].i=i; stack[top].j=j; stack[top].j=j;stack[top].i=i; stack[top].j=j; stack[top].j=j;stack[top].director=-1;board[i][j]=top+1;stack[top].director=-1;board[i][j]=top+1;board[stack[top].i][stack[top].j]=0board[stack[top].i][stack[top].j]=0;top--;图3.2探寻路径函数流程图（3）输出路径函数流程图inti,j;inti,j;i=0i=0i<Ni<NNYI++j=0I++j=0j<Nj<NNprintf("\t%d",board[i][j]);printf("\t%d",board[i][j]);j++j++printf("\n\n");printf("\n\n");图3.3输出路径函数流程图（4）坐标函数流程图inti，j;inti，j;TryPath(x,y)TryPath(x,y) NYPrintf("无解"）；Dispaly();Printf("无解"）；Dispaly();图3.4坐标函数流程图4具体代码实现 //定义头文件和宏定义 #include<stdio.h> #defineMAXSIZE100 #defineN8 //数据类型定义 intboard[8][8];//定义棋盘 intHtry1[8]={1,-1,-2,2,2,1,-1,-2}; //存储马各个出口位置相对当前位置行下标的增量数组 intHtry2[8]={2,-2,1,1,-1,-2,2,-1}; //存储马各个出口位置相对当前位置列下标的增量数组 structStack//定义栈类型 { inti;//横坐标 intj;//纵坐标 intdirector;//存储方向 }stack[MAXSIZE];//定义一个栈数组 inttop=-1;//栈指针 //探寻路径函数模块 intTryPath(inti,intj) { intfind,director,number,min;//定义几个临时变量 inti1,j1,h,k,s;//定义几个临时变量 inta[8],b1[8],b2[8],d[8];//定义几个临时数组 while(top>-1)//栈不空时循环 { for(h=0;h<8;h++)//用数组a[8]记录当前位置的下一个位置的可行路径的条数 { number=0; i=stack[top].i+Htry1[h]; j=stack[top].j+Htry2[h]; b1[h]=i; b2[h]=j; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置 { for(k=0;k<8;k++) { i1=b1[h]+Htry1[k]; j1=b2[h]+Htry2[k]; if(board[i1][j1]==0&&i1>=0&&i1<8&&j1>=0&&j1<8) //如果找到下一位置 number++;//记录条数 } a[h]=number;//将条数存入数组a[8]中 } } for(h=0;h<8;h++)//根据可行路径条数小到大按下表排序放入数组d[8]中 { min=9; for(k=0;k<8;k++) if(min>a[k]) { min=a[k]; d[h]=k;//将下表存入数组d[8]中 s=k; } a[s]=9; } director=stack[top].director; if(top>=63)//如果走完整个棋盘返回1 return(1); find=0;//表示没有找到下一个位置 for(h=director+1;h<8;h++)//向八个方向进行探寻 { i=stack[top].i+Htry1[d[h]]; j=stack[top].j+Htry2[d[h]]; if(board[i][j]==0&&i>=0&&i<8&&j>=0&&j<8)//如果找到下一位置 { find=1;//表示找到下一个位置 break; } } if(find==1)//如果找到下一个位置进栈 { stack[top].director=director;//存储栈结点的方向 top++;//栈指针前移进栈 stack[top].i=i; stack[top].j=j; stack[top].director=-1;//重新初始化下一栈结点的尝试方向 board[i][j]=top+1;//标记棋盘 } else//否则退栈 { board[stack[top].i][stack[top].j]=0;//清除棋盘的标记 top--;//栈指针前移退栈 } } return(0); }//输出路径函数模块 voidDisplay() { inti,j; for(i=0;i<N;i++) { for(j=0;j<N;j++) printf("\t%d",board[i][j]);//输出马儿在棋盘上走过的路径 printf("\n\n"); } printf("\n"); } //起始坐标函数模块 voidInitLocation(intxi,intyi) { intx,y;//定义棋盘的横纵坐标变量 top++;//栈指针指向第一个栈首 stack[top].i=xi;//将起始位置的横坐标进栈 stack[top].j=yi;//将起始位置的纵坐标进栈 stack[top].director=-1;//将起始位置的尝试方向赋初值 board[xi][yi]=top+1;//标记棋盘 x=stack[top].i;//将起始位置的横坐标赋给棋盘的横坐标 y=stack[top].j;//将起始位置的纵坐标赋给棋盘的纵坐标 if(TryPath(x,y))//调用马儿探寻函数，如果马儿探寻整个棋盘返回1否则返回0 Display();//输出马儿的行走路径 else printf("无解"); } //主程序模块 intmain() { intx,y; inti,j; printf("**************马踏棋盘**************\n\n");for(i=0;i<N;i++)//初始化棋盘 for(j=0;j<N;j++) board[i][j]=0; for(;;) { printf("Pleaseinputimportpoint(1<=x<=8and1<=y<=8)\n\n"); printf("请输入起始位置的横坐标x="); scanf("%d",&x);//输入起始位置的横坐标 printf("\n"); printf("输入起始位置的纵坐标y="); scanf("%d",&y);//输入起始位置的纵坐标 printf("\n"); if(x>=1&&x<=8&&y>=1&&y<=8)break; printf("Yourinputisworng!!!\n"); } printf("beginwith