排序算法比较.doc

一 排序算法比较1. 问题描述对直接插入排序,直接选择排序,冒泡排序,快速排序,堆排序五种排序算法进行比较.要求: 1.被排序的对象由计算机随机生成,分别取长度为500,20000,1000000 2.算法中增加比较移动次数和比较次数的统计功能,并统计在排序同一组随机数时每种排序算法的运行时间,及占用内存情况. 3.对实验的结果进行比较2.设计思路 这是一个算法性能评价程序,重点在于算法性能的评价上.实现某一功能可能有很多方法,判断一个算法好坏的标准主要有时间复杂度和空间复杂度.在当今系统资源相对充足的计算机系统中,时间复杂度变成了头等问题. 对于每一个排序算法都应该有两个返回值:比较次数和移动次数.但在C语言中只能有一个函数返回值,故这里采用指针传递地址的方式通过形参的地址从而可以修改实参值.这样一来,在每个排序算法参数列表中,除了含被排序指针对象外,另外加两个整型变量指针,用于传递算法执行过程中的比较次数和移动次数.取一定长度的对象,由计算机产生一定量的伪随机数后,主函数,调用各个排序函数,但由于排序对象也是指向一维数组的指针,在调用一次排序算法后,通过形参对指针的改变,被排序对象已经是有序的了.当再一次用其他排序算法后,有可能比较次数和移动次数达到最大或最小.无论是哪种情况都是不好的,这样一来,就失去了算法复杂度的比较意义了.为了避免这种情况的出现本程序采用在排序前新建一个数组,将保存随机数的数组复制到该数组,让排序算法对该数组进行排序.这样就不会改变原始对象的随机性.在统计排序算法运行时间时采用新建两个time_t对象，排序开始前接收一次系统时间，排序结束后接收一次系统时间，二者的差值即为排序算法所运行的时间。3.数据结构设计本程序中考虑的内容是排序对象，排序的依据是关键字之间的大小比较。故在每个节点类型定义中，至少得包含关键字key这一项。被排序对象由一个个节点构成，一个排序对象包含一系列指向一串节点的指针，指针对象长度。具体说明如下：typedef structKeyType key;/关键字int other;/数据DataType;/节点类型typedef structDataType r1000000;int length;/排序对象的大小Sqlist;/排序对象类型4.功能函数设计（1）直接插入排序函数StrightInsertSort()直接插入排序将待排序对象分为有序部分和无序部分，进行排序时逐次顺序提取无序部分的对象同有序部分的最后一个对象做比较，如果该对象大于有序部分最后一个对象，则将该对象插入到此位置，否则依次向左比较，直至找到插入位置。（2） 直接选择排序函数Selectsort()该排序算法首先在所有的n个带排序对象中找到最小的对象，将其与第1个对象做交换后，在后n-1个对象中继续找到最大对象，找到后将其与第2个对象交换。直至将所有的对象找到并插入适当位置即可。(3)冒泡排序函数BubbleSort() 在每一趟冒泡排序中，依次比较相邻两个关键字的大小。若为反序，则交换。经过一趟冒泡后最大的关键字已经到达最后了。若按这种方法进行n-1趟冒泡，排序既能完成。(4)堆排序函数Heapsort() 对排序的算法思想很简单，就是每次把关键字调整为堆，取出堆顶元素与最后一个元素交换，同时令堆的大小减一，把剩下的元素重新调整为堆，重复此过程，直到只剩下一个元素为止。(5)快速排序函数 将带排序记录的第一个记录作为分区标准，将小于其的元素放在左边，将大于其的元素放在右边，中间放所选记录，为一趟快速排序。然后对两个子序列如此排序，直至所有记录有序。5.程序代码#include stdafx.h#includestdio.h#includestdlib.h#includetime.h#include windows.h#include psapi.h#include iostreamusing namespace std;#pragma once#pragma comment(lib,Psapi.lib)typedef int KeyType;typedef structKeyType key;int other;DataType;typedef structDataType r1000000;int length;Sqlist;void copy(Sqlist *a,Sqlist *b);/复制int GetMemory() ;/得到系统开销状况void SrandNum(Sqlist *s,int num);/生成随机数void StrightInsertSort(Sqlist *s,long *compare,long *exchange);/直接插入排序void BubbleSort(Sqlist *s,long *compare,long *exchange);/冒泡排序void Quicksort(Sqlist *s,int low,int high,long *compare,long *exchange);/递归形式的快速排序void Selectsort(Sqlist *s,long *compare,long *exchange);/直接选择排序void Heapsort(Sqlist *s,long *compare,long *exchange);/堆排序void out(Sqlist *s);/输出排序结果int _tmain(int argc, _TCHAR* argv)/主函数int i,num;long *compare,*exchange;/记录比较及交换次数compare=(long *)malloc(sizeof(long);/开辟空间exchange=(long *)malloc(sizeof(long);Sqlist *s,*tmp;s=(Sqlist *)malloc(sizeof(Sqlist);tmp=(Sqlist *)malloc(sizeof(Sqlist);printf(请输入生成的随机数的数目：n);cinnum;SrandNum(s, num);/生成随机数time_t start,end;/start，end分别记录开始及结束时系统时间/printf(n生成的随机数如下：n);/out(s);printf(直接插入排序情况：n); /直接插入排序 copy(s,tmp);*compare=*exchange=0;start=clock(); StrightInsertSort(tmp,compare,exchange);end=clock(); printf( 排序运行时间%dmsn,end-start);printf(比较次数：%d 交换次数：%d,*compare,*exchange);/printf(n排序结果如下n);/out(tmp);printf(nn冒泡排序情况：n); /冒泡排序 copy(s,tmp);*compare=*exchange=0;start=clock(); BubbleSort(tmp,compare,exchange);end=clock(); printf( 排序运行时间%dmsn,end-start);printf(比较次数：%d 交换次数：%d,*compare,*exchange);/printf(n排序结果如下n);/out(tmp); printf(nn快速排序情况：n); /快速排序 copy(s,tmp);*compare=*exchange=0;start=clock(); Quicksort(tmp,1,tmp-length,compare,exchange);end=clock(); printf( 排序运行时间%dmsn,end-start);printf(比较次数：%d 交换次数：%d,*compare,*exchange);/printf(n排序结果如下n);/out(tmp);printf(nn直接选择排序情况：n); /直接选择排序 copy(s,tmp);*compare=*exchange=0;start=clock(); Selectsort(tmp,compare,exchange);end=clock(); printf( 排序运行时间%dmsn,end-start);printf(比较次数：%d 交换次数：%d,*compare,*exchange);/printf(n排序结果如下n);/out(tmp); printf(nn堆排序情况：n); /堆排序 copy(s,tmp);*compare=*exchange=0;start=clock(); Heapsort(tmp,compare,exchange);end=clock(); printf( 排序运行时间%dmsn,end-start);printf(比较次数：%d 交换次数：%d,*compare,*exchange);/printf(n排序结果如下n);/out(tmp);return 0;void copy(Sqlist *a,Sqlist *b)/将a复制到b中int i;for(i=1;ilength ;i+)b-r i.key=a-r i.key ;b-length =a-length ;void SrandNum(Sqlist *s,int num) /生成num个随机数保存到s中int i;time_t t;srand(unsigned)time(&t); /新建时间种子for(i=1;iri.key=rand(); /生成随机数s-length=num;void StrightInsertSort(Sqlist *s,long *compare,long *exchange)/直接插入排序int i,j;*compare=*exchange=0;for(i=2;ilength ;i+)s-r 0=s-r i; /复制到前哨站(*compare)+;(*exchange)+;j=i-1;while(s-r 0.key r j.key )/当前数据的关键字大于前哨站的关键字，则后移(*compare)+;(*exchange)+;s-r j+1=s-r j;j-; s-r j+1=s-r 0; /插入到正确的位置 (*exchange)+;void BubbleSort(Sqlist *s,long *compare,long *exchange)/冒泡排序int i,j;for(i=1;ilength-1;i+)for(j=2;jlength-i;j+) /进行n-1趟冒泡if(s-rj.keyrj-1.key)s-r0.key=s-rj.key;s-rj.key=s-rj-1.key;s-rj-1.key=s-r0.key;(*exchange)+=3;(*compare)+;int Quicksort1(Sqlist *s,int low,int high,long *compare,long *exchange) /一趟快速排序/交换顺序表s中的记录，使轴值到达其最终位置，并返回轴值的位置/此时，在轴值之前的数字都小于它，在轴值后面的数字都大于它int pivotkey;s-r0=s-rlow; /以子表的第一个记录作为轴值支点pivotkey=s-rlow.key; /取轴值的关键字(*exchange)+=2;while(lowhigh)(*compare)+;while(lowr high.key=pivotkey)high-;(*compare)+=2;s-r low=s-rhigh;/将比轴值记录小的交换到低端(*exchange)+;while(lowr low.keyrhigh=s-r low;/将比轴值记录大的交换到高端(*exchange)+;s-r low=s-r 0;/轴值到达其最终位置(*exchange)+; return low;/返回轴值最终所在位置void Quicksort(Sqlist *s,int low,int high,long *compare,long *exchange)/递归形式的快速排序int pivotloc;if(lowhigh)(*compare)+;pivotloc=Quicksort1(s,low,high,compare,exchange);/将待排序序列一分为二Quicksort(s,low,pivotloc-1,compare,exchange);/将小于轴值的序列实现递归排序Quicksort(s,pivotloc+1,high,compare,exchange);/将大于轴值的序列实现递归排序void Selectsort(Sqlist *s,long *compare,long *exchange)/直接选择排序int i,j,t;DataType tmp;for(i=1;ilength ;i+)/做s-length-1趟排序(*compare)+;for(j=i+1,t=i;jlength ;j+)/在i开始的length-i+1条记录中选取关键字最小的记录(*compare)+;if(s-rt.keys-rj.key)(*compare)+;t=j;/t中存放关键字最小的记录的下标(*exchange)+;tmp=s-r t; /将关键字最小的记录与第i条记录交换s-r t=s-r i;s-r i=s-r t;(*exchange)+=3;void HeapAdjust(Sqlist *s,int n,int m,long *compare,long *exchange)/对第n个结点为跟的子树筛选，使其成为大顶堆int i=n,j;DataType rc;rc=s-r n;(*exchange)+;for(j=2*i;j=m;j*=2)/沿着关键字较大的孩子向下搜索if(jr j.keyr j+1.key)j=j+1;/j为较大孩子的坐标(*compare)+=2;(*exchange)+;if(rc.key s-r j.key )break;/rc应插在i位置上(*compare)+;s-r i=s-r j;i=j;/使i结点满足堆定义(*exchange)+=2;s-r i=rc; /插入(*exchange)+;void Heapsort(Sqlist *s,long *compare,long *exchange)/堆排序int i;DataType tmp;for(i=s-length /2;i0;i-) /将数据建成堆(*compare)+;HeapAdjust(s,i,s-length,compare,exchange);for(i=s-length ;i1;i-)tmp=s-r 1; /将堆顶元素与堆底元素交换，将最大元素一道最后s-r 1=s-r i;s-r i=tmp;(*compare)+;(*exchange)+=3;HeapAdjust(s,1,i-1,compare,exchange);void out(Sqlist *s)/输出结果int i;for(i=1;ilength ;i+)printf(%d ,s-r i.key );6.运行测试（1）.排序正确性验证将主函数做适当调整，在排序前输出待排序的数字，待排序完成后输出排序结果。调整后的主函数如下：int _tmain(int argc, _TCHAR* argv)int i,num;long *compare,*exchange;/记录比较及交换次数compare=(long *)malloc(sizeof(long);/开辟空间exchange=(long *)malloc(sizeof(long);Sqlist *s,*tmp;s=(Sqlist *)malloc(sizeof(Sqlist);tmp=(Sqlist *)malloc(sizeof(Sqlist);printf(请输入生成的随机数的数目：n);cinnum;SrandNum(s, num);/生成随机数time_t start,end;/start，end分别记录开始及结束时系统时间printf(n生成的随机数如下：n);out(s);printf(直接插入排序情况：n); /直接插入排序 copy(s,tmp);printf(n生成的随机数如下：n);out(tmp);*compare=*exchange=0;start=clock(); StrightInsertSort(tmp,compare,exchange);end=clock(); printf(n排序后结果如下：n);out(tmp);printf(nn冒泡排序情况：n); /冒泡排序 copy(s,tmp);printf(n生成的随机数如下：n);out(tmp);*compare=*exchange=0;start=clock(); BubbleSort(tmp,compare,exchange);end=clock(); printf(n排序后结果如下：n);out(tmp); printf(nn快速排序情况：n); /快速排序 copy(s,tmp);printf(n排序前如下：n);out(tmp);*compare=*exchange=0;start=clock(); Quicksort(tmp,1,tmp-length,compare,exchange);end=clock(); printf(n排序后结果如下：n);out(tmp);printf(nn直接选择排序情况：n); /直接选择排序 copy(s,tmp);printf(n排序前如下：n);out(tmp);*compare=*exchange=0;start=clock(); Selectsort(tmp,compare,exchange);end=clock(); printf(n排序后结果如下：n);out(tmp); printf(nn堆排序情况：n); /堆排序 copy(s,tmp);printf(n排序前如下：n);out(tmp);*compare=*exchange=0;start=clock(); Heapsort(tmp,compare,exchange);end=clock(); printf(n排序后结果如下：n);out(tmp);return 0;用随机生成函数分别生成5个，10个对排序算法的正确性进行验证，验证运行结果如下：观察运行结果，证明每次排序前待排序对象复制正确，复制前后一致，排序结果正确。(2) 排序性能比较用程序代码中的主函数，输入生成的随机数的数目，对排序算法进行比较：这是一个长度为5678的五种排序算法比较次数和移动次数的统计可以看出，直接插入排序的比较次数和冒泡排序的比较次数基本相同，在8130000左右，直接选择排序的比较次数最多，大概为直接插入排序（冒泡排序的2倍），冒泡排序的交换次数也最多，快速排序和堆排序的比较次数和交换次数较少，算法明显优于其他排序算法。而通过运行时间的分析可以得到快速排序和堆排序较快，直接选择排序和直接插入排序相差不大，冒泡排序最满。观察结果除如上结论为还可以看出快速排序比堆排序更好。（当对87654组对象进行排序时，快速排序运行时间（51ms）堆排序比较次数（1403682），快速排序交换次数（851286）堆排序比较次数（3714052）. 由此可知，在这五种排序算法中，快速排序最优，其次是堆排序，直接选择排序及直接插入排序次之，最差的是冒泡排序。其中比较次数最多的为直接选择排序，移动次数最多的为冒泡排序。二 迷宫遍历1.问题描述 用递归和非递归的方向，分别实现迷宫路径的求解。2.设计思路递归方法思路，从起点开始搜索周围的位置，如果某位置能够走通，以该点为起点，递归。非递归方法，起点首先入栈，从起点搜索周围的位置，如果能够走通某位置，则将该位置入栈，以该点为起点，继续探索，否则出栈，返回上一位置。3.数据结构设计在进行递归遍历时，只需要标记该位置能同否走通即可。因此只需定义二维数组。另外设计一个结构体，包含x，y用于表示探索的方向。其定义如下typedef structint x,y;/纵，横坐标及方向item;item move4=0,1,1,0,0,-1,-1,0;在进行非递归遍历时，除了需要迷宫数组及探索方向数组外，还需要一个标识迷宫走通路径的 数组，用该数组标识，走通的路径。4.功能函数设计递归迷宫路径path()首先，判断是否到达终点，如果到达，即返回。否则，朝四个方向探索。在进行递归时，首先判断该点是否能够走通，如果能走通，以该点 为起点递归，直至找到能够到达终点的路径。.设置字体颜色为红色或者蓝色textcolor()textcolor1() 使用函数GetStdHandle()得到当前句柄，然后调用函数SetConsoleTextAttribute()即可以将字体颜色设置为红色或者蓝色。.随机初始化迷宫函数Srand_Maze() 每次进行迷宫初始化前，新进时间种子，生成随机数初始化迷宫.非递归寻找迷宫路径函数mazepath()首先将入口点入栈，当栈不为空时，进入循环。出栈后，判断该点是否还有方向可以探索，如果进行探索，如果该点能够走通，入栈，然后判断是否到达终点，如果到达，将迷宫走通路径保存到标识数组里。否则探索下一个方向。5.程序代码递归方法代码：#include stdafx.h#includestdio.h#includetime.h#includestdlib.h#include algorithm#include windows.h#define m 6#define n 8typedef structint x,y;/纵，横坐标及方向item;item move4=0,1,1,0,0,-1,-1,0;int step=0;int path(int mazem+2n+2,item move,int x,int y)int i;step+;mazexy=step;if(x=m&y=n)/到达终点，返回return 1;for(i=0;i4;i+)/分别朝四个方向探索if(mazex+movei.xy+movei.y=0)/如果该点能够走通if(path(maze,move,x+movei.x,y+movei.y)/以x+movei.x,y+movei.y为出发点递归return 1;step-;mazexy=0;return 0;void Srand_Maze(int mazem+2n+2)time_t t;int i,j;for(i=0;i=7;i+)for(j=0;j=9;j+)mazeij=1;/迷宫及其边界区域全部设为1，0表示能够走通，1不能走通srand(unsigned)time(&t); /新建时间种子for(i=1;i=6;i+)for(j=1;j=8;j+)mazeij=rand()%2;/生成迷宫int textcolor() HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);/获取当前句柄 return SetConsoleTextAttribute(hd, FOREGROUND_RED);/设置字体的颜色为红色int textcolor1()HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);/获取当前句柄 return SetConsoleTextAttribute(hd, FOREGROUND_BLUE);/设置字体颜色为蓝色int _tmain(int argc, _TCHAR* argv)int mazem+2n+2,mark;step=0;for(;)step=0;/重置Srand_Maze(maze);/生成迷宫textcolor(); for(int i=0;i8;i+)/输出生成的迷宫 for(int j=0;j10;j+) printf(%d ,mazeij); printf(n); printf(n); mark=path( maze,move,1,1);/寻找路径 if(mark=1)/如果找到路径，输出 textcolor(); printf(输出结果！n); for(int i=0;i8;i+) for(int j=0;j1|i=1&j=1)textcolor1();printf(*t);elsetextcolor();printf(%dt,mazeij); printf(n); break; scanf(%d,&mark);return 0;非递归方法：#include stdafx.h#includestdio.h#includestdlib.h#includetime.h#include windows.hint textcolor() HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);/得到当前句柄 return SetConsoleTextAttribute(hd, FOREGROUND_RED);/设置为红色int textcolor1()HANDLE hd = GetStdHandle(STD_OUTPUT_HANDLE);/得到当前句柄 return SetConsoleTextAttribute(hd, FOREGROUND_BLUE);/设置为蓝色#define m 6#define n 8#define MaxSize 100typedef structint x,y,d;/纵，横坐标及方向DataType;typedef structDataType dataMaxSize;int top;SeqStack,*pSeqStack;typedef structint x,y;item;pSeqStack Init_SeqStack()/初始化空栈 pSeqStack s;s=(pSeqStack)malloc(sizeof(SeqStack);/开辟空间if(s)s-top =-1;return s;int Empty_SeqStack(pSeqStack s)/判断栈空if(s-top =-1)return 1;elsereturn 0;int Push_SeqStack(pSeqStack s,DataType x)/入栈if(s-top =MaxSize-1)return 0;/栈满，不能入栈elses-top +;/移动栈顶s-data s-top =x;/接收数据return 1;int Pop_SeqStack(pSeqStack s,DataType *x)/出栈if(Empty_SeqStack(s)return 0;/栈空，不能出栈else*x=s-data s-top ;/传出数据s-top -;/移动栈顶return 1;void Destory_SeqStack(pSeqStack *s)/销毁栈if(*s)free(*s);/释放*s=NULL;return ;int mazepath(int mazem+2n+2,int markm+2n+2,item move,int x0,int y0)pSeqStack s;DataType temp;int x,y,d,i,j;temp.x =x0;temp.y =y0;temp.d =-1;s=Init_SeqStack();/初始化栈if(!s)printf(n初始化栈失败！);return 0;Push_SeqStack(s,temp);/入栈while(!Empty_SeqStack(s)/当栈不空Pop_SeqStack(s,&temp);/出栈x=temp.x ;y=temp.y ;d=temp.d +1;while(d4)/当还有方向可以探索i=x+moved.x;j=y+moved.y;if(mazeij=0)/如果该点能够走通temp.x=x;temp.y=y;temp.d=d;Push_SeqStack(s,temp);/入栈x=i;y=j;mazeij=-1;if(x=m&y=n)/如果到达终点while(!Empty_SeqStack(s)/当栈不空marktemp.x temp.y =1;/标识此点能走通 Pop_SeqStack(s,&temp);/出栈Destory_SeqStack(&s);/销毁栈return 1;else d=0;else d+;Destory_SeqStack(&s);return 0;void Init_Maze(int mazem+2n+2,int markm+2n+2)/初始化迷宫，及标识数组int i,j;for(i=0;i=7;i+)for(j=0;j=9;j+)if(i=0|i=7|j=0|j=9)mazeij=1; markij=0;void Srand_Maze(int mazem+2n+2,int markm+2n+2)/通过随机数生成迷宫time_t t;int i,j;srand(unsigned)time(&t); /新建时间种子for(i=1;i=6;i+)for(j=1;j=8;j+)mazeij=rand()%2;markij=0;void Out_Maze(int mazem+2n+2)/输出生成的迷宫int i,j;for(i=0;i=7;i+)for(j=0;j=9;j+)printf(%d ,mazeij);printf(n);int _tmain(int argc, _TCHAR* argv)int i,j,k,mazem+2n+2,markm+2n+2;item move4=0,1,1,0,0,-1,-1,0;for(;)/直至生成一个有走通路径的迷宫，输出该迷宫走通的路径，终止循环 Init_Maze(maze,mark); Srand_Maze(maze,mark); Out_Maze(maze); printf(n); k=mazepath(maze,mark,move,1,1); textcolor1(); /if(k=0) /printf(无法走通！); if(k=1)/如果找到走通路径输出 printf(n下面输出走出迷宫的路径：n);mark11=mark68=1;for(i=0;i=7;i+) for(j=0;j=9;j+)if(markij=1)textcolor1(); printf(*t);elsetextcolor();printf(%dt,mazeij); printf(n); if(k=1) break;scanf(%d,&k);return 0;6.运行与测试递归方法运行结果截图非递归方法运行结果截图：三.马的遍历1.问题描述设计程序完成如下要求：在中国象棋棋盘上，对任一位置上放置的一个马，均能选择一个合适的路线，使得该棋子能按中国象棋规则不重复地走过棋盘上每一个位置。要求：.依次输出所走过的各位置的坐标。.最好能画出棋盘的图形形式，并在其上动态地标注行走过程。2.设计思路在以输入坐标作为起始点的马的遍历的过程中，自该点依次向其8个方向探索，找到8个方向中其中下一次探索方向最少的方向，再以改点为起始点继续向下探索。直至所有的位置已经遍历。输出马的遍历的结果。实现该求解算法需要解决以下一些问题。.试探方向当马位于棋盘上某一个位置(x,y)时，在一般情况下，其可以到达的位置有8个方向，为了表示新的位置点的坐标，可以采用当前位置(x,y)加上x和y方向增量的方式表示，定义增量数组。Struct direct_increment int dx; int dy;direct_increment direct_way8=1,2,2,1,2,-1,-1,2,-1,-2,-2,-1,-2,1,1,-2;这样，可以方便由某一点(x,y)求出按特定方向到达新点的(x1,y1)坐标：x1=x+direct_wayi.dx;y1=y+direct_wayi.dy;.防止重复走某点，避免死循环在向前探索过程中，会遇到某些点无法再向前继续搜索的情形，此时还存在某些点没有遍历，搜索会会推到上一个走过的位置，选择此位置的下一个新方向继续搜索。因此，在每一步向前所搜索的过程中，需要对当前位置所试探的方向做一个标记，标记出在当前位置，此方向已经走过，对即将试探的位置点作方向标记，防止从新的位置向其前驱结点搜索，陷入死循环；同时在回退之前，对棋盘上已放弃位置走过标记要清除。3.数据结构设计每个位置点应包含改点是否访问信息，及其下一位置的8个方向是否访问的信息。故该程序每个棋盘位置点的数据结构如下 ：struct Elemchar c;/棋盘上点信息,0为没有走过，1为走过int mark_direct8;/标记棋盘上各点8个方向可走情况，0为可走，1为不可走;而在定义棋盘是为处理问题方便将棋盘结构定义为12*12的。这样，对于棋盘上任何一点的遍历探索方向都有8个方向，便于问题的处理。 Elem chessboard1212;/定义棋盘结构 4.功能函数设计. .初始化棋盘函数init_chessboard() 首先，将棋盘的所有点标识为边界。然后在非边界区域标识没有走过标识。.检测点是否位于棋盘区域check_pos