ai.txt

使用C语言编写程序

#include <iostream>
using namespace std;
#include<fstream>

#define maxsize 200
int max_depth=4; //查找深度界限
char goal[9]={'1','2','3','8','0','4','7','6','5'};//目标状态
int key=0;
ofstream outfile1("D:\\result.txt");
ofstream outfile2("D:\\open.txt");

struct Node			//状态数据结构
{	char data[10];	//第一位操作符，后九位位状态位
	int code;
	int depth;
	int father;
};

struct Stack		//open表数据结构
{	Node d[maxsize];
	int top;
};


//open栈的操作声明
void InitStack(Stack &s);
void ClearStack(Stack &s);
int empty(Stack &s);
int Full(Stack &s);
void Push(Stack &s, Stack &L,Node &p);
void Pop (Stack &s,Node &p);
void print(Stack &s);

//close表的操作声名
void InitList(Stack &L);
void Insert(Stack &L,Node &p);
int search(Stack &L,int code);

//操作部分声名
int Right(Stack &s,Stack &L,Node &p);
int Left(Stack &s,Stack &L,Node &p);
int Up(Stack &s,Stack &L,Node &p);
int Down(Stack &s,Stack &L,Node &p);
void printWay(Stack &L,Node &q);
int judge(Stack &s);
void print(Node &p);

void main()
{	Stack open;
	InitStack(open);
	ClearStack(open);
	Stack close;
	InitList(close);
	Node first;
	first.data[0]=0;
	cout<<"请输入初始状态："<<endl;
	for(int i=1;i<10;i++)
		cin>>first.data[i];
	first.depth=0;
	first.code=key++;
	first.father=0;
	outfile1<<"您输入的状态为："<<endl;
	print(first);
	outfile1<<"解的过程为："<<endl;
	Push(open,close,first);
	int flag=judge(open);
		if(flag==1)
		{	printWay(close,first);
			goto end;
		}	
	while(!empty(open))
	{	Node child;
		Pop(open,child);
		
		while(child.depth>max_depth)
		{	Insert(close,child);
			Pop(open,child);
		}
		Insert(close,child);
		Left(open,close,child);
		flag=judge(open);
		if(flag==1)
		{	printWay(close,open.d[open.top]);
			print(first);
			goto end;
		}
		Up(open,close,child);
		flag=judge(open);
		if(flag==1)
		{	printWay(close,open.d[open.top]);
			print(first);
			goto end;
		}
		Right(open,close,child);
		flag=judge(open);
		if(flag==1)
		{	printWay(close,open.d[open.top]);
			print(first);
			goto end;
		}			
		
		Down(open,close,child);
		flag=judge(open);
		if(flag==1)
		{	printWay(close,open.d[open.top]);
			print(first);
			goto end;
		}
		
		print(open);
		
	}
	if(empty(open))
		cout<<"没有找到合适的解"<<endl;

	end:cout<<"程序结束！"<<endl;
}


//open栈的操作实现
void InitStack(Stack &s)
{	s.top=-1;
}

void ClearStack(Stack &s)
{	s.top=-1;
}

int empty(Stack &s)
{	return (s.top==-1);
}

int Full(Stack &s)
{	return (s.top==maxsize-1);
}

void Push(Stack &s,Stack &L, Node &p)
{	if(s.top==maxsize-1)  
	  {		cout<< "Stack overflow!" <<endl;
			exit(1);
      }
	int fg,t=0,v=0;
	for(fg=s.top;fg>-1;fg--)
	{	for(int i=1;i<10;i++)
		{	if(s.d[fg].data[i]!=p.data[i])
			{	t++;
				break;
			}
			
		}
	}
	for(fg=L.top;fg>-1;fg--)
	{	for(int i=1;i<10;i++)
		{	if(L.d[fg].data[i]!=p.data[i])
			{	v++;
				break;
			}
			
		}
	}
	if((t==((s.top)+1))&&(v==((L.top)+1)))
	{
      s.top++;
      for(int i=0;i<10;i++)
	  {	s.d[s.top].data[i]=p.data[i];
	  }
	  s.d[s.top].depth=p.depth;
	  s.d[s.top].code=p.code;
	  s.d[s.top].father=p.father;
	}
	
}

void Pop(Stack &s,Node &p)
{	if(s.top==-1)
	{	cout<<"Stack is empty."<<endl;
		exit(1);
	}
	for(int i=0;i<10;i++)
	{	p.data[i]=s.d[s.top].data[i];
	}
		p.depth=s.d[s.top].depth;
		p.father=s.d[s.top].father;
		p.code=s.d[s.top].code;
	s.top--;
	
}

void print(Stack &s)
{	int t=s.top,count=0;;
	while(t!=-1)
	{	for(int i=1;i<10;i++)
		{	outfile2<<s.d[t].data[i]<<" ";
			count++;
			if(count==3)
			{	outfile2<<endl;
				count=0;
			}
		}
	
		outfile2<<s.d[t].depth<<endl;
		outfile2<<s.d[t].code<<endl;
		outfile2<<endl;
		t--;
	}
	outfile2<<endl;
	outfile2<<endl;
}

//close表的操作实现
void InitList(Stack &L)
{	L.top=0;
}
void Insert(Stack &L,Node &p)
{	for(int i=0;i<10;i++)
		L.d[L.top].data[i]=p.data[i];
	L.d[L.top].depth=p.depth;
	L.d[L.top].code=p.code;
	L.d[L.top].father=p.father;
	L.top++;
}

int search(Stack &L,int code)
{	int count=0,tmp;
	for(int i=(L.top--);i>=0;i--)
	{	if(L.d[i].code==code)
		{	for(int j=1;j<10;j++)
			{	outfile1<<L.d[i].data[j]<<" ";
				count++;
				if(count==3)
				{	outfile1<<endl;
					count=0;
				}
			}
			tmp=L.d[i].father;
			return tmp;
		}
	}
	return 0;
}


//操作部分的实现
int Left(Stack &s,Stack &L,Node &p)
{	int i,mid,j,dep;
	if((p.data[1]=='0')||(p.data[4]=='0')||(p.data[7]=='0'))
		return 0;
	Node tmp;
	tmp.data[0]='1';
	for(i=1;i<10;i++)
	{	tmp.data[i]=p.data[i];
		if(p.data[i]=='0')
			j=i;
	}
	mid=tmp.data[j-1];
	tmp.data[j-1]=tmp.data[j];
	tmp.data[j]=mid;
	dep=p.depth;
	tmp.depth=++dep;
	tmp.code=key++;
	tmp.father=p.code;
	Push(s,L,tmp);
	return 1;
}

int Up(Stack &s,Stack &L,Node &p)
{	int i,mid,j,dep;
	if((p.data[1]=='0')||(p.data[2]=='0')||(p.data[3]=='0'))
		return 0;
	Node tmp;
	tmp.data[0]='2';
	for(i=1;i<10;i++)
	{	tmp.data[i]=p.data[i];
		if(p.data[i]=='0')
			j=i;
	}
	mid=tmp.data[j-3];
	tmp.data[j-3]=tmp.data[j];
	tmp.data[j]=mid;
	dep=p.depth;
	tmp.depth=++dep;
	tmp.code=key++;
	tmp.father=p.code;
	Push(s,L,tmp);
	return 1;
}

int Down(Stack &s,Stack &L,Node &p)
{	int i,mid,j,dep;
	if((p.data[7]=='0')||(p.data[8]=='0')||(p.data[9]=='0'))
		return 0;
	Node tmp;
	tmp.data[0]='4';
	for(i=1;i<10;i++)
	{	tmp.data[i]=p.data[i];
		if(p.data[i]=='0')
			j=i;
	}
	mid=tmp.data[j+3];
	tmp.data[j+3]=tmp.data[j];
	tmp.data[j]=mid;
	dep=p.depth;
	tmp.depth=++dep;
	tmp.code=key++;
	tmp.father=p.code;
	Push(s,L,tmp);
	return 1;
}

int Right(Stack &s,Stack &L,Node &p)
{	int i,mid,j,dep;
	if((p.data[3]=='0')||(p.data[6]=='0')||(p.data[9]=='0'))
		return 0;
	Node tmp;
	tmp.data[0]='3';
	for(i=1;i<10;i++)
	{	tmp.data[i]=p.data[i];
		if(p.data[i]=='0')
			j=i;
	}
	mid=tmp.data[j+1];
	tmp.data[j+1]=tmp.data[j];
	tmp.data[j]=mid;
	dep=p.depth;
	tmp.depth=++dep;
	tmp.code=key++;
	tmp.father=p.code;
	Push(s,L,tmp);
	return 1;
}

int judge(Stack &s)
{	
	Node p;
	for(int i=0;i<10;i++)
	{	p.data[i]=s.d[s.top].data[i];
	}
		p.depth=s.d[s.top].depth;
		p.code=s.d[s.top].code;
		p.father=s.d[s.top].father;
	for(i=1;i<10;i++)
		if(p.data[i]!=goal[i-1])
		return 0;
	return 1;
}

void print(Node &p)
{	int count=0;
	for(int i=1;i<10;i++)
	{	outfile1<<p.data[i]<<" ";
		count++;
		if(count==3)
		{	outfile1<<endl;
			count=0;
		}
	}

}

void printWay(Stack &L,Node &q)
{	int pt,i,ct; 
	pt=q.father;
	print(q);
	while(pt!=0)
	{	outfile1<<"<----"<<endl;
		ct=search(L,pt);
		pt=ct;
	}
	outfile1<<"<----"<<endl;
}