实验报告(华容道).docx

文档介绍：数据结构(华容道)实验报告实验名称:华容道学生姓名:班级:学号:日期:一、实验目的可以输入华容道游戏的起始布局,求出求解结果。二、,一般都是通过搜索空间的方法获得可行解法。这里采用广度优先搜索。理论上讲,广度优先算法得到的第一个解,一定是一个搜索步数最少的解(如有解存在),这正好是华容道游戏的需要。广度优先搜索算法一般通过队列存储结构实现。由当前布局状态判断哪些棋子可以移动,每移动一个棋子,得到一个新的布局状态,若不是最终解且该布局以前没有出现过,则入队。显然算法在设计细节时需要考虑移动棋子的算法,以及如何判断新的布局状态是否出现过。:MemoryPool::MemoryPool(unsignedintsize){ if(size<=100)throw"sizeshouldbegreaterthan100."; m_Base=newchar[size]; if(!m_Base)throw"noenoughmemory."; 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*siz