实验报告(华容道).docx

《实验报告(华容道).docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构（华容道）实验报告实验名称：华容道学生姓名：班级：学号：日期：一、实验目的可以输入华容道游戏的起始布局，求出求解结果。二、程序分析2.1存储结构链式存储结构2.2程序流程对于此类问题的求解，一般都是通过搜索空间的方法获得可行解法。这里采用广度优先搜索。理论上讲，广度优先算法得到的第一个解，一定是一个搜索步数最少的解（如有解存在），这正好是华容道游戏的需要。广度优先搜索算法一般通过队列存储结构实现。由当前布局状态判断哪些棋子可以移动，每移动一个棋子，得到一个新的布局状态，若不是最终解且该布局以前没有

2、出现过，则入队。显然算法在设计细节时需要考虑移动棋子的算法，以及如何判断新的布局状态是否出现过。2.3关键算法分析算法1：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

3、,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->prio

4、r=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->

5、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;whil

6、e(p&&p->MemorySize()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(B

7、lockBorder);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));}B

8、lockBorder*MemoryPool::GetPreBlock(void*p){char*cp=(char*)GetCurrentBlock(p);if(cp==m_Base)returnNULL;else{intlen=*(int*)(cp-sizeof(BlockBorder));cp-=2*sizeof(BlockBorder)+(len<0?-len:len);return(BlockBorder*)p;}}Bl