实验报告(华容道)

数据结构（华容道）实验报告实验名称：华容道学生姓名：班级：学号：日期：一、实验目的可以输入华容道游戏的起始布局，求出求解结果。二、程序分析2.1存储结构链式存储结构2.2程序流程对于此类问题的求解，一般都是通过搜索空间的方法获得可行解法。这里采用广度优先搜索。理论上讲，广度优先算法得到的第一个解，一定是一个搜索步数最少的解（如有解存在），这正好是华容道游戏的需要。广度优先搜索算法一般通过队列存储结构实现。由当前布局状态判断哪些棋子可以移动，每移动一个棋子，得到一个新的布局状态，若不是最终解且该布局以前没有出现过，则入队。显然算法在设计细节时需要考虑移动棋子的算法，以及如何判断新的布局状态是否出现过。2.3关键算法分析算法1：MemoryPool::MemoryPool(unsignedintsize){if(size=100)throwsizeshouldbegreaterthan100.;m_Base=newchar[size];if(!m_Base)thrownoenoughmemory.;m_PoolSize=size;m_Frist=NULL;InsertFreeBlock(m_Base,size-2*sizeof(BlockBorder));}voidMemoryPool::InsertFreeBlock(void*p,intsize){FreeBlockHead*s=(FreeBlockHead*)p;s-BlockLength=size;p=(char*)p+size+sizeof(BlockBorder);((BlockBorder*)p)-BlockLength=size;if(m_Frist)m_Frist-prior=s;s-next=m_Frist;s-prior=NULL;m_Frist=s;}voidMemoryPool::DeleteFreeBlock(FreeBlockHead*p){if(!p-next&&!p-prior){m_Frist=NULL;}elseif(!p-next&&p-prior){p-prior-next=NULL;}elseif(!p-prior){p-next-prior=NULL;m_Frist=p-next;}else{p-next-prior=p-prior;p-prior-next=p-next;}}voidMemoryPool::SetUsedBorder(void*p,intsize){((BlockBorder*)p)-BlockLength=-size;p=(char*)p+sizeof(BlockBorder)+size;((BlockBorder*)p)-BlockLength=-size;}void*MemoryPool::Allocate(intsize){if(m_Frist==NULL)returnNULL;FreeBlockHead*p=m_Frist;while(p&&p-MemorySize()size)p=p-next;if(!p)returnNULL;if(p-MemorySize()=size+sizeof(FreeBlockHead)+sizeof(BlockBorder)){DeleteFreeBlock(p);SetUsedBorder(p,p-BlockLength);return(char*)p+sizeof(BlockBorder);}else{intnewsize=p-MemorySize()-size-2*sizeof(BlockBorder);DeleteFreeBlock(p);InsertFreeBlock(p,newsize);SetUsedBorder((char*)p+p-BlockSize(),size);return(char*)p+p-BlockSize()+sizeof(BlockBorder);}}BlockBorder*MemoryPool::GetCurrentBlock(void*p){return(BlockBorder*)((char*)p-sizeof(BlockBorder));}BlockBorder*MemoryPool::GetPreBlock(void*p){char*cp=(char*)GetCurrentBlock(p);if(cp==m_Base)returnNULL;else{intlen=*(int*)(cp-sizeof(BlockBorder));cp-=2*sizeof(BlockBorder)+(len0?-len:len);return(BlockBorder*)p;}}BlockBorder*MemoryPool::GetNextBlock(void*p){BlockBorder*bp=GetCurrentBlock(p);char*cp=(char*)bp+bp-BlockSize();return(cp==m_Base+m_PoolSize)?NULL:(BlockBorder*)cp;}voidMemoryPool::Free(void*p){BlockBorder*currentBlock=GetCurrentBlock(p);BlockBorder*nextBlock=GetNextBlock(p);if(nextBlock&&nextBlock-Free()){intsize=nextBlock-BlockSize();DeleteFreeBlock((FreeBlockHead*)nextBlock);InsertFreeBlock(currentBlock,currentBlock-MemorySize()+size);}BlockBorder*preBlock=GetPreBlock(p);if(preBlock&&preBlock-Free()){DeleteFreeBlock((FreeBlockHead*)preBlock);InsertFreeBlock(preBlock,preBlock-MemorySize()+currentBlock-BlockSize());}else{InsertFreeBlock(currentBlock,currentBlock-MemorySize());}}MemoryPool::~MemoryPool(){coutm_Fristendl;coutsize:m_Frist-MemorySize()endl;if(m_Base)delete[]m_Base;}[1]算法功能（1）每个状态布局的结构定义structG{chargrid[5][4];//当前状态的布局charfather[5][4];//到达当前状态的前一个状态布局};booloperator(constG&a,constG&b){returnmemcmp(a.grid[0],b.grid[0],20)0;}（2）棋子移动考虑到一些棋子一次可能有两种移动方式，设计MOVE函数返回移动方式的数目，参数NEWG指针指向为移动后的状态数组，每个元素为一种移动后的布局。intMove(G&g,inti,intj,G*newg){if(g.grid[i][j]=='0')return0;if((g.grid[i][j]=='C'||g.grid[i][j]=='H')&&i!=0&&g.grid[i-1][j]=='B'&&g.grid[i-1][j+1]=='B'){GetNextG(&newg[0],&g,sizeof(G));inth=1;if(g.grid[i][j]=='C')h=2;Slide(newg[0].grid,g.grid,i,j,-1,0,h,2);return1;}if(g.grid[i][j]=='C'&&i3&&g.grid[i+2][j]=='B'&&g.grid[i+2][j+1]=='B'||g.grid[i][j]=='H'&&i4&&g.grid[i+1][j]=='B'&&g.grid[i+1][j+1]=='B'){GetNextG(&newg[0],&g,sizeof(G));inth=1;if(g.grid[i][j]=='C')h=2;Slide(newg[0].grid,g.grid,i,j,1,0,h,2);return1;}if((g.grid[i][j]=='C'||g.grid[i][j]=='G')&&j!=0&&g.grid[i][j-1]=='B'&&g.grid[i+1][j-1]=='B'){GetNextG(&newg[0],&g,sizeof(G));intw=1;if(g.grid[i][j]=='C')w=2;Slide(newg[0].grid,g.grid,i,j,0,-1,2,w);return1;}if(g.grid[i][j]=='C'&&j2&&g.grid[i][j+2]=='B'&&g.grid[i+1][j+2]=='B'||g.grid[i][j]=='G'&&j3&&g.grid[i][j+1]=='B'&&g.grid[i+1][j+1]=='B'){GetNextG(&newg[0],&g,sizeof(G));intw=1;if(g.grid[i][j]=='C')w=2;Slide(newg[0].grid,g.grid,i,j,0,1,2,w);return1;}if(g.grid[i][j]=='H'&&j!=0&&g.grid[i][j-1]=='B'){GetNextG(&newg[0],&g,sizeof(g));Slide(newg[0].grid,g.grid,i,j,0,-1,1,2);intnum=1;if(j1&&g.grid[i][j-2]=='B'){GetNextG(&newg[1],&g,sizeof(G));Slide(newg[1].grid,g.grid,i,j,0,-2,1,2);num++;}returnnum;}//。。。其他情况的处理不做阐述}[2]代码逻辑1.初始化布局队列2.初始化布局集合3.当前布局入队4.若队列不为空（1）布局出队作为当前布局对于当前布局每个棋子：（2）若棋子可移动，则：进行移动，产生新布局。（3）若布局是最终结果，则打印移动结果（4）若布局在之前集合中不存在，则：a.设置该布局的上一步布局标志b.该布局入队c.该布局如集合2.4其他3.程序运行结果分析运行的结果显示了华容道移动的步骤以及最后完成的状态。4.总结本课程设计实现了华容道游戏的求解方法。求解过程采用广度优先搜索最优解的方法。该方法可以用于求解多种类似问题。在实际应用中，若最终结果的状态是唯一的，如三姐魔方问题，还可以采用双向广度优先搜索，即从起始状态和最终状态同时进行双向广度优先搜索，从起始状态开始遍历心得状态，从最终状态遍历产生该状态的前一个状态。每遍历一个新的状态，就在另一个方向上的所有状态中查找，若找到，则两个方向上的遍历路径有了链接，这就是最优解之一。4.1实验的难点和关键点对于“曹操”只有上下左右任意一个方向上的两个位置都为‘B’才可以移动。对于竖立的将领，上下任意一个方向一个‘B’就可以移动动。且若两个‘B’为上下相邻，则棋子可以移动一个位置也可以移动两个位置。此外，若左右任意一个方向上的两个位置都为‘B’也可以移动。4.2心得体会1巩固和加深了对数据结构的理解，提高综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培养独思考，深入研究，分析问题、解决问题的能力。源码（C++vs环境可运行）：#includestdafx.h#includeiostream#includeset#includestack#includequeu