旅行商dlg.cpp

tsp问题的小软件

// 旅行商Dlg.cpp : implementation file
//

#include "stdafx.h"
#include "旅行商.h"
#include "旅行商Dlg.h"
//#include "struct.h"
#include "stdlib.h"
#include "math.h"
#include "dos.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#define PI 3.14

int PreAnalyse=0;//预分析判断0为否
/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About
	paths L;
	linklist closed;
	int number=0;//open 和closed表中节点总数
	int Count=0;//城市数目
	char StartNode;


//获取路径
void Getpath(paths &p,CString temp);
void InitPath(paths  &p);
void InitOpen(linklist  &p);
void InsertOpen(linklist &l,linklist p);
void InitClosed(linklist  &l);
linklist selectmin(linklist &p);
int GetAvg(linklist node);
void GetCount(paths p,char letter);
int ExistFather(linklist closed,linklist temp);
//void PrintPath(linklist closed,linklist omin);
//void Print(linklist temp);
int GetLength(char letter1,char letter2);

struct posarray{
	char name;
	int  x;
	int  y;
//	struct posarray *next;
};//*array,posarray;
	struct posarray *array;
int locpos(char letter);
void GetArrayName();

typedef struct pnode{
	char name;
	int id;
	int fid;
	int x;
	int y;
	int num;//第几个子节点
	struct pnode *next;
}*picnode,pnode;
picnode piclink;

void InitPiclink(picnode &plink);
void InsertPlink(picnode node);

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg dialog

CMyDlg::CMyDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CMyDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CMyDlg)
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CMyDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CMyDlg)
	DDX_Control(pDX, IDC_BTOUTFILE, m_outresult);
	DDX_Control(pDX, IDC_LISTOUT, m_lstout);
	DDX_Control(pDX, IDC_DRAW, m_drawpic);
	DDX_Control(pDX, IDC_BTSAVE, m_btsave);
	DDX_Control(pDX, IDC_BTEXCUTE, m_btexcute);
	DDX_Control(pDX, IDC_EDIT1, m_edtinput);
	DDX_Control(pDX, IDC_BTCLEAR, m_btclear);
	DDX_Control(pDX, IDC_BTINPUT, m_btinput);
	DDX_Control(pDX, IDC_LIST1, m_lstfile);
	DDX_Control(pDX, IDC_BTOPENFILE, m_btopen);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CMyDlg, CDialog)
	//{{AFX_MSG_MAP(CMyDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BTOPENFILE, OnBtopenfile)
	ON_BN_CLICKED(IDC_BTCLEAR, OnBtclear)
	ON_BN_CLICKED(IDC_BTINPUT, OnBtinput)
	ON_BN_CLICKED(IDC_BTSAVE, OnBtsave)
	ON_BN_CLICKED(IDC_BTEXCUTE, OnBtexcute)
	ON_BN_CLICKED(IDC_DRAW, OnDraw)
	ON_BN_CLICKED(IDC_BTOUTFILE, OnBtoutfile)
	ON_BN_CLICKED(IDC_DRAWPIC, OnDrawpic)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyDlg message handlers

BOOL CMyDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CMyDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CMyDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CMyDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CMyDlg::OnBtopenfile() 
{
	// TODO: Add your control notification handler code here
	CString FilePathName;
	char szFilters[]="文法文件 (*.txt)|*.txt|All Files (*.*)|*.*||";
	CFileDialog dlg(TRUE, "txt", "*.txt",
      OFN_FILEMUSTEXIST| OFN_HIDEREADONLY, szFilters, this);
	int count;

	if(dlg.DoModal()==IDOK)
	{
		PreAnalyse=0;//必须预分析
		this->Invalidate();
		FilePathName=dlg.GetPathName();
		CStdioFile InFile;
		InFile.Open(FilePathName,CFile::modeRead);
		CString temp;
		m_lstfile.ResetContent();
		do
		{
			InFile.ReadString(temp);
			if(temp=="") 
				break;
			count=m_lstfile.GetCount();
			m_lstfile.InsertString(count,temp);
		}while(true);
		InFile.Close();
	}
}

void CMyDlg::OnBtclear() 
{
	// TODO: Add your control notification handler code here
	m_lstfile.ResetContent();
	PreAnalyse=0;//必须预分析
	this->Invalidate();
}

void CMyDlg::OnBtinput() 
{
	// TODO: Add your control notification handler code here
	CString str;
	m_edtinput.GetWindowText(str);
	int count;
	count=m_lstfile.GetCount();
	m_lstfile.InsertString(count,str);
	PreAnalyse=0;//必须预分析
	this->Invalidate();
}

void CMyDlg::OnBtsave() 
{
	// 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_lstfile.GetCount(); i++)
		{
			m_lstfile.GetText(i,temp);
			temp += "\n";
			OutFile.WriteString(temp);
			
		}
		OutFile.Close();
	}
}

void CMyDlg::OnBtexcute() 
{
	// TODO: Add your control notification handler code here
	//从列表框中获取总路径数目，赋给路径数组path
	if(PreAnalyse==0)
		MessageBox("没有预分析");
	else{
		paths q;
		m_lstout.ResetContent();
		m_lstout.InsertString(0,"本程序由DK剑客编制");
		m_lstout.InsertString(1,"2007年元月8日。。。");
		m_lstout.InsertString(2," ");
	
		q=L;
		StartNode='A';
		visitor(q,StartNode);
	}
}


void CMyDlg::OnDraw() 
{
	// TODO: Add your control notification handler code here
	//获得ID号为IDC_DRAWBOX的控件的CWnd指针
	//并使用它获得相应的设备环境
//	this->Invalidate();
	CWnd *pWnd = GetDlgItem(IDC_STATIC);
	CDC  *pDC  = pWnd->GetDC();
	//获得该控件的矩形区域
	::GetClientRect(pWnd->m_hWnd, conRect);
	//将索引值为NULL_BRUSH库存对象选进设备环境
	pDC->SelectStockObject(NULL_BRUSH);
	//设置视口原点
	pDC->SetViewportOrg(conRect.right/2, conRect.bottom/2);

	PreAnalyse=1;

	int count,numi;
	CString temp;
	InitPath(L);
	Count=0;//全局变量初始化
	number=0;
	count=m_lstfile.GetCount();
	for(numi=0;numi<count;numi++)
	{
		m_lstfile.GetText(numi,temp);
		Getpath(L,temp);
	}

	int x0,y0,R;
	
	array=(posarray *)malloc(sizeof(posarray)*Count);
	GetArrayName();

	CRect rect;
	CString character;
	R=(conRect.bottom-conRect.top)/2;
	if((conRect.right-conRect.left)<(conRect.bottom-conRect.top))
		R=(conRect.right-conRect.left)/2;
	x0=0;//conRect.right/2;
	y0=0;//-R-conRect.bottom/2
	R-=10;//
//	case CIRCLE://绘制圆形
//		pDC->Circle(23,32,5);
//	Circle(50,50,R);
//	Circle(R-R*sin(2*PI*(double)4/(double)5),R+10-R*(int)cos(2*PI*(double)4/(double)5),5);

	int r=8;
	for(int i=0;i<Count;i++)
	{
//		array[i].name=Name[i];
		array[i].x=x0-R*sin(2*PI*(double)i/(double)Count);
		array[i].y=y0-R*cos(2*PI*(double)i/(double)Count);
	//	Circle(array[i].x,array[i].y,5);
		pDC->Ellipse(array[i].x-r,array[i].y-r,array[i].x+r,array[i].y+r);
		rect.top=array[i].y-8;
		rect.bottom=array[i].y+8;
		rect.left=array[i].x-8;
		rect.right=array[i].x+8;
		character.Format("%c",array[i].name);
		pDC->DrawText(character,rect,0);
		Sleep(200);
	}
//	pWnd->ReleaseDC(pDC);
//	pDC->MoveTo(array[0].x,array[0].y);
//	pDC->LineTo(array[1].x,array[1].y);
//	CWnd *pnd = GetDlgItem(IDC_STATIC);
//	CDC  *pC  = pWnd->GetDC();
	paths p;
	CString strlength;
	int midx,midy;
	p=L->next;
	int j=0,k=0;
	while(p!=NULL)
	{
		k=locpos(p->hnode);
		j=locpos(p->tnode);

	//	m_lstout.InsertString(m_lstout.GetCount(),str);
		pDC->MoveTo(array[k].x,array[k].y);
		pDC->LineTo(array[j].x,array[j].y);

		midy=(array[j].y+array[k].y)/2;
		rect.top=midy-8;
		rect.bottom=midy+8;
		midx=(array[j].x+array[k].x)/2;
		rect.left=midx-8;
		rect.right=midx+8;
		strlength.Format("%d",p->length );
		pDC->DrawText(strlength,rect,0);
		Sleep(500);
		p=p->next;
	}
//	str.Format("%c %c %c %c %c ",array[0].name,array[1].name,array[2].name,array[3].name,array[4].name);
//	m_lstout.InsertString(m_lstout.GetCount(),str);

	pWnd->ReleaseDC(pDC);

}


void CMyDlg::Circle(int x, int y, int r)
{
	CWnd *pWnd = GetDlgItem(IDC_STATIC);
	CDC  *pDC  = pWnd->GetDC();
	pDC->Ellipse(x-r,y-r,x+r,y+r);
	pWnd->ReleaseDC(pDC);
}

int locpos(char letter)
{
	for(int i=0;i<Count;i++)
	{
		if(array[i].name==letter)
			return i;
	}
	return NULL;
}

void GetArrayName()
{
	paths p;
	p=L->next;
	int i=0,j,flag=0;
	while(p!=NULL)
	{
		flag=0;
		for(j=0;j<i;j++)
		{
			if(array[j].name==p->hnode )
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			array[i].name =p->hnode;
			i++;
		}
		flag=0;
		for(j=0;j<i;j++)
		{
			if(array[j].name==p->tnode )
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			array[i].name =p->tnode;
			i++;
		}
		p=p->next;
	}
}

void CMyDlg::PrintPath(linklist close, linklist omin)
{
	linklist p;
	char letter;
	int length,sumlength=0;
	CString str;
	letter=omin->node;
	m_lstout.InsertString(m_lstout.GetCount(), "                 搜索结果");
	while(omin->fid!=0)
	{
		p=closed->next;
		while(p!=NULL && omin->fid!=0)
		{
			if(omin->fid==p->id)
			{
				length=GetLength(omin->node,p->node);
				sumlength+=length;
				str.Format("%c<----%c    length: %d",omin->node,p->node,length);
				m_lstout.InsertString(m_lstout.GetCount(),str);
				omin=p;
				break;
			}
			p=p->next;
		}
	}
	length=GetLength(omin->node,p->next->node);
	sumlength+=length;
	str.Format("%c<----%c    length: %d",omin->node,p->next->node,length);
	m_lstout.InsertString(m_lstout.GetCount(),str);
	str.Format("路径总距离:     %d",sumlength);
	m_lstout.InsertString(m_lstout.GetCount(), str);
}

void Getpath(paths &P,CString temp)
{