statelist.cpp

八数码小游戏

#include "StdAfx.h"
#include ".\statelist.h"


CStateList::CStateList(void)
{
	first = NULL;
}

// destructor: free all space of the list
CStateList::~CStateList(void)
{
	CStateNode* next;
	while (first)
	{
		next = first->link;
		delete first;
		first = next;
	}
}

// same function with destructor
void CStateList::Free()
{
	CStateNode* next;
	while (first)
	{
		next = first->link;
		delete first;
		first = next;
	}
}

// delete the first element and return it
CState* CStateList::HeadDelete()
{
	CState* s;
	CStateNode* sn = first;
	s = sn->state;
	first = first->link;
	delete sn;
	return s;
}

/* insert an element.
   must ensure a non-decreasing order */
void CStateList::OrderInsert(CState* s)
{
	CStateNode* node = new CStateNode(s);
	CStateNode* sn = first;
	CStateNode* prev = NULL;
	while (sn && sn->state->g + sn->state->h < s->g + s->h)
	{
		prev = sn;
		sn = sn->link;
	}

	if (sn == first)
	{
		node->link = first;
		first = node;
	}
	else
	{
		node->link = sn;
		prev->link = node;
	}
}

// insert an element as the first
void CStateList::HeadInsert(CState* s)
{
	CStateNode* node = new CStateNode(s);
	node->link = first;
	first = node;
}

/* search an element.
   if found, give its address to res, and return true
   else, return false */
bool CStateList::Search(CState* s, CState*& res)
{
	CStateNode* sn = first;
	CState* cs;

/*	// this searching method is time consuming
	while (sn && ::Distance(sn->state, s) > 0)
		sn = sn->link;
	
*/
	// this new method may be better
	int g = s->g;
	while (sn)
	{
		cs = sn->state;
		
		if (cs->g != g)
			goto cont;

		for (int i = 0; i < 3; i++)
			for (int j = 0; j < 3; j++)
				if (cs->num[i][j] != s->num[i][j])
					goto cont;

		break;

cont:
		sn = sn->link;
	}

	if (!sn)
		return false;
	
	res = sn->state;
	return true;
}

// sort the list into a non-decreasing order
void CStateList::Sort()
{
	if (!first || !first->link)
		return;
	CStateNode *i, *j, *m, *n;
	for (i = first->link, j = first; i; )
	{
		int t = i->state->g + i->state->h;

		m = first;
		while (m != i && m->state->g + m->state->h <= t)
		{
			n = m;
			m = m->link;
		}

		//Insert as the first element.
		if (m == first)
		{
			j->link = i->link;
			i->link = first;
			first = i;
			i = j->link;
		}
		else
		{
			//No need to move elements, just advance pointers i and j to next.
			if (i == m)
			{
				i = i->link;
				j = j->link;
			}
			else
			{
				//The most common state.
				j->link = i->link;
				i->link = n->link;
				n->link = i;
				i = j->link;
			}
		}
	}
}