旅行商dlg.cpp

tsp问题的小软件

	int length,i;
	length=temp.GetLength();
//	cout<<"length :"<<length<<endl;
	char *str,*stopstr;
	str=(char *)malloc(length-5);
	paths lp;
	lp=(paths)malloc(sizeof(path));
	lp->hnode=temp[1];//'A';
	lp->tnode=temp[3];//'b';

	GetCount(P,temp[1]);
	GetCount(P,temp[3]);

	for(i=5;i<length-1;i++)
	{
		str[i-5]=temp.GetAt(i);
	}
	str[i]='\0';
	lp->length=strtol(str,&stopstr,10);//取数
	lp->next=P->next;
	P->next=lp;
}


void InitPath(paths  &p)
{   //构造一个空的链表。
	
	p=(paths)malloc(sizeof(path));
	p->next=NULL;
}

void InitOpen(linklist  &p)
{   //构造一个空的链表。
	
	p=(linklist)malloc(sizeof(link));
	p->next=NULL;
}

void InsertOpen(linklist &l,linklist p)
{
	linklist ls;
	ls=l;
	while(ls->next!=NULL)
	{
		if(p->fvalue<=ls->next->fvalue)
		{
			p->next=ls->next;
			ls->next=p;
			return ;
		}
		ls=ls->next;
	}
	p->next=NULL;
	ls->next=p;
}

void InitPiclink(picnode &plink)
{
	plink=(picnode)malloc(sizeof(pnode));
	plink->next=NULL;
}

void InsertPlink(picnode node)
{
	node->next=piclink->next;
	piclink->next=node;
}

picnode GetFather(int id)
{
	picnode picl;
	picl=piclink->next;
	while(picl!=NULL)
	{
		if(picl->id==id)
			return picl;
		picl=picl->next;
	}
	return NULL;
}

void InitClosed(linklist  &l)
{   //构造一个空的链表。
	
	l=(linklist)malloc(sizeof(link));
	l->next=NULL;
}



void InsertClosed(linklist &l,linklist p)
{
	p->next=l->next;
	l->next=p;
}


linklist selectmin(linklist &p)
{
	linklist q;
	q=p->next;
	if(q==NULL)
	{
		return NULL;
	}
	p->next=q->next;	
	return q;
}

//*
int GetAvg(linklist curnode)
{
	linklist p,tempnode;
	paths pl;
	int sumlength=0,length,snodelength=0;
	int j=0,flag=0,numpath=0;
	char *str;
	int num,i=0;
	tempnode=(linklist)malloc(sizeof(link));
	tempnode=curnode;
	num=curnode->level;
	if(num==0)
		num=1;
	str=(char *)malloc(num);
//	cout<<" 已用节点: "<<endl;
	if(curnode->id==0)//判断是否为起始节点
	{
		pl=L->next;
		while(pl!=NULL)
		{
			if(pl->hnode==StartNode || pl->tnode==StartNode)
			{
				numpath++;
				snodelength+=pl->length;
			}
			pl=pl->next;
		}
	}
	if(curnode->level==Count)//对回到起点的判断
		return 0;
	while(tempnode->fid!=0)
	{
		p=closed->next;
		while(p!=NULL && tempnode->fid!=0)
		{
			if(tempnode->fid==p->id)
			{
				str[i++]=p->node;
		//		cout<<p->node<<endl;
				tempnode=p;
				break;
			}
			p=p->next;
		}
	}
	str[i]='\0';
	pl=L->next;
	while(pl!=NULL)
	{
		flag=0;
		for(j=0;j<i;j++)
		{
			if(pl->hnode==str[j] || pl->tnode==str[j])
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			length=pl->length; //GetLength(pl->hnode,pl->tnode);
			sumlength+=length;
			numpath++;
		}
		pl=pl->next;
	}//
	sumlength+=snodelength;//如果是头节点则必须重新加上由起始节点扩展的距离和
//	cout<<"sumlength  "<<sumlength<<endl;
	return (Count-curnode->level)*sumlength/numpath;
}
/*

	
int GetAvg(linklist curnode)
{
	paths pl;
	pl=L->next;
	int sumlength=0,numpath=0;
	while(pl!=NULL)
	{
		sumlength+=pl->length;
		numpath++;
		pl=pl->next;
	}
	return (Count-curnode->level)*sumlength/numpath;
}
*/
void GetCount(paths p,char letter)
{
	paths l;
	int flag=0;
	l=p->next;
	while(l!=NULL)
	{
		if(l->hnode==letter || l->tnode==letter)
		{
			flag=1;
			break;
		}
		l=l->next;
	}
	if(flag==0)
	{
		Count++;
	}
}


int ExistFather(linklist close,linklist temp)
{
	linklist p;
	char letter;
	letter=temp->node;
	
	while(temp->id!=0)
	{
		p=close->next;
		while(p!=NULL)
		{
			if(temp->fid==p->id)
			{
				if(letter==p->node)
					return 1;
				else
					temp=p;
				break;
			}
			p=p->next;
		}
	}
	return 0;
}


int GetLength(char letter1,char letter2)
{
	paths pl;
	pl=L->next;
	while(pl!=NULL)
	{
		if((pl->hnode==letter1 && pl->tnode==letter2) || (pl->hnode==letter2 && pl->tnode==letter1))
		{
			return pl->length;
		}
		pl=pl->next;
	}
	return NULL;
}

void CMyDlg::visitor(paths P, char schar)
{
	//获得ID号为IDC_DRAWBOX的控件的CWnd指针
	//并使用它获得相应的设备环境
	CWnd *pWnd = GetDlgItem(IDC_DRAWPIC);
	CDC  *pDC  = pWnd->GetDC();
	//获得该控件的矩形区域
	::GetClientRect(pWnd->m_hWnd, conRect);
	//将索引值为NULL_BRUSH库存对象选进设备环境
	pDC->SelectStockObject(NULL_BRUSH);
	//设置视口原点
	pDC->SetViewportOrg(conRect.right/2, conRect.bottom/2);

	CRect rect;

	linklist lopen,omin,otemp,snode,open;
	linklist close;
	paths pathp;
	pathp=P;
//	otemp=(linklist)malloc(sizeof(link));
	snode=(linklist)malloc(sizeof(link));
	int suc=0;
//	int pathcount=0;

	InitOpen(lopen);
	InitClosed(closed);
	InitPiclink(piclink);

	open=lopen;
	close=closed;
	snode->node=schar;
	snode->fid=0;
	snode->id=0;
	snode->level=0;
	snode->flag=0;
	snode->gvalue=0;
	snode->hvalue=Count*GetAvg(snode);//
	snode->fvalue=snode->gvalue+snode->hvalue;
	snode->next=NULL;
	open->next=snode;
	
	int childnum=0;
	picnode picn,pictemp;
	int R=50;
	int r=8;
	picn=(picnode)malloc(sizeof(pnode));
	picn->name=schar;
	picn->id=0;
	picn->fid=0;
	picn->x=0;
	picn->y=10-(conRect.bottom-conRect.top)/2;
	picn->num=0;

	CString character;
		
	InsertPlink(picn);
//	picn->next=NULL;
//	piclink->next=picn;
	pDC->Ellipse(picn->x-r,picn->y-r,picn->x+r,picn->y+r);
	rect.top=picn->y-8;
	rect.bottom=picn->y+8;
	rect.left=picn->x-5;
	rect.right=picn->x+10;
	character.Format("%c",picn->name);
	pDC->DrawText(character,rect,0);

	rect.top=picn->y-8;
	rect.bottom=picn->y+8;
	rect.left=picn->x-30;
	rect.right=picn->x-8;
	character.Format("%d",snode->fvalue);
	pDC->DrawText(character,rect,0);
	Sleep(200);
//	pWnd->ReleaseDC(pDC);
	m_lstout.InsertString(m_lstout.GetCount(),"                   扩展节点信息");
	m_lstout.InsertString(m_lstout.GetCount(),"编号   节点   父编号   层次   f值    g值    h值");

	while(open->next!=NULL && suc==0)
	{
		omin=selectmin(open);
		//generateclo(omin,newclo);
	//	DeleteOpen(closed,omin);
		omin->flag=1;
		InsertClosed(close,omin);
		if(omin->node==snode->node && omin->level!=0)
		{
			suc=1;
			break;
		}
		else
		{
			pathp=P;
			childnum=0;
			while(pathp!=NULL )    //extend(newclo);
			{
				if(pathp->hnode==omin->node)
				{
					otemp=(linklist)malloc(sizeof(link));
					otemp->node=pathp->tnode;
				}
				else if(pathp->tnode==omin->node)
				{
					otemp=(linklist)malloc(sizeof(link));
					otemp->node=pathp->hnode;
				//	otemp->fid=newclo->id;
				}
				else 
				{
					pathp=pathp->next;
					continue;
				}
				otemp->id=++number;
				otemp->fid=omin->id;
				otemp->flag=0;
				otemp->level=omin->level+1;
				otemp->gvalue=omin->gvalue+pathp->length;
				otemp->hvalue=GetAvg(otemp);
				otemp->fvalue=otemp->gvalue+otemp->hvalue;

			
				if(otemp->level!=Count)
				{
					if(!ExistFather(closed,otemp))
					{
						open=lopen;
						Print(otemp);

						picn=(picnode)malloc(sizeof(pnode));
						pictemp=(picnode)malloc(sizeof(pnode));
						pictemp=GetFather(otemp->fid);
						picn->id=otemp->id;
						picn->fid=otemp->fid;
						picn->name=otemp->node;
						picn->x=pictemp->x+R*pow(-1,childnum)*tan(PI*(childnum+1)/12);
						picn->y=pictemp->y+R;
						pDC->Ellipse(picn->x-r,picn->y-r,picn->x+r,picn->y+r);
						rect.top=picn->y-8;
						rect.bottom=picn->y+8;
						rect.left=picn->x-5;
						rect.right=picn->x+10;
						character.Format("%c",picn->name);
						pDC->DrawText(character,rect,0);
							rect.top=picn->y-8;
							rect.bottom=picn->y+8;
							rect.left=picn->x-25;
							rect.right=picn->x-8;
							character.Format("%d",otemp->fvalue);
							pDC->DrawText(character,rect,0);

						Sleep(200);
						pDC->MoveTo(pictemp->x,pictemp->y);
						pDC->LineTo(picn->x,picn->y);
						Sleep(500);

						InsertPlink(picn);
					//	free(pictemp);
				
						childnum++;
						InsertOpen(open,otemp);//不在父辈节点中出现
					}
					else
					{
						--number; 
						free(otemp);
					}
				}
				else if(otemp->node==schar)
				{
					open=lopen;
					Print(otemp);
					picn=(picnode)malloc(sizeof(pnode));
						pictemp=(picnode)malloc(sizeof(pnode));
						pictemp=GetFather(otemp->fid);
						picn->id=otemp->id;
						picn->fid=otemp->fid;
						picn->name=otemp->node;
						picn->x=pictemp->x+R*pow(-1,childnum)*tan(PI*(childnum+1)/12);
						picn->y=pictemp->y+R;
						pDC->Ellipse(picn->x-r,picn->y-r,picn->x+r,picn->y+r);
						rect.top=picn->y-8;
						rect.bottom=picn->y+8;
						rect.left=picn->x-5;
						rect.right=picn->x+10;
						character.Format("%c",picn->name);
						pDC->DrawText(character,rect,0);
							rect.top=picn->y-8;
							rect.bottom=picn->y+8;
							rect.left=picn->x-25;
							rect.right=picn->x-8;
							character.Format("%d",otemp->fvalue);
							pDC->DrawText(character,rect,0);

						Sleep(200);
						pDC->MoveTo(pictemp->x,pictemp->y);
						pDC->LineTo(picn->x,picn->y);
						Sleep(500);
						InsertPlink(picn);

					//	free(pictemp);

					childnum++;
					InsertOpen(open,otemp);//最后一个是起始点
				}
				else
				{
					--number;
					free(otemp);
				}

				pathp=pathp->next;
			}//while
		}//if-else
		open=lopen;
		close=closed;
	}//while
	if(suc==1)
	{
		PrintPath(closed,omin);
	}
	pWnd->ReleaseDC(pDC);
}

//打印扩展节点的过程
void CMyDlg::Print(linklist temp)
{

	CString str;
	str.Format("%4d%6c%6d%6d%8d%8d%8d",temp->id, 
		temp->node,temp->fid,temp->level,temp->fvalue,
		temp->gvalue,temp->hvalue);
	m_lstout.InsertString(m_lstout.GetCount(),str);
}

void CMyDlg::OnBtoutfile() 
{
	// TODO: Add your control notification handler code here
	CString FilePathName;
	char szFilters[]="文法文件 (*.txt)|*.txt|All Files (*.*)|*.*||";
	CFileDialog dlg(FALSE, "txt", "*.txt",
       OFN_HIDEREADONLY | OFN_OVERWRITEPROMPT, szFilters, this);
	if(dlg.DoModal()==IDOK)
	{
		FilePathName=dlg.GetPathName();
		CStdioFile OutFile;
		OutFile.Open(FilePathName,CFile::modeCreate | CFile::modeWrite);
		CString temp;
		for(int i = 0; i < m_lstout.GetCount(); i++)
		{
			m_lstout.GetText(i,temp);
			temp += "\n";
			OutFile.WriteString(temp);
			
		}
		OutFile.Close();
	}
}

void CMyDlg::OnDrawpic() 
{
	// TODO: Add your control notification handler code here
	CWnd *pWnd = GetDlgItem(IDC_DRAWPIC);
	pWnd->UpdateWindow();
	this->Invalidate();
}