judlg.cpp

一个简单的聚类程序。有点像Kmeans,但又不是kmeans。不过演示用还是可以的。数据输入有些费力

// juDlg.cpp : implementation file
//

#include "stdafx.h"
#include "ju.h"
#include "juDlg.h"
#include <math.h>
#include <iostream.h>
#include<fstream.h>

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

///////////////////////////变量//

int total;
clu* c_head;
clu* c_end;
int dai;
int lei;

/////////////////函数//
void cen(clu *a){
	double sumx,sumy;
	int i;
	po *temp;
	sumx=0;
	sumy=0;
	temp=a->head;

	for(i=0;i<a->num;i++){
	sumx=sumx+temp->x;
	sumy=sumy+temp->y;
	temp=temp->next;}
	
	a->centre.x=sumx/a->num;
	a->centre.y=sumy/a->num;
	
}


void combine(clu *a,clu *b){
	clu *temp;
	temp=c_head;
	a->num=a->num+b->num;
	while(temp->next!=b){
		temp=temp->next;}


	if(b->next ==NULL) temp->next=NULL;
	else temp->next=b->next;

	a->end->next=b->head;
	a->end=b->end;
	cen(a);
	total--;

	delete b;	
}



double distance(clu* a,clu* b){
	double d;
	d=(a->centre.x-b->centre.x)*(a->centre.x-b->centre.x)+(a->centre.y-b->centre.y)*(a->centre.y-b->centre.y);
	d=sqrt(d);
	return d;

}

double distance2(po *a,po *b)
{	double d;
	d=(a->x-b->x)*(a->x-b->x)+(a->y-b->y)*(a->y-b->y);
	d=sqrt(d);
	return d;

}


po* ma(clu* a,po *b){
int i;
double d=0;
po *temp,*temp2;

temp=a->head;
for(i=1;i<=a->num;i++){
	if(temp->d_next==NULL)	
		{if (d<=distance2(b,temp)) {	
			d=distance2(b,temp);
			temp2=temp;
		}}
		temp=temp->next;
}
return temp2;
}

po* mahead(clu* a,po *b){
int i;
double d=0;
po *temp,*temp2;

temp=a->head;
for(i=1;i<=a->num;i++){
		
		if (d<=distance2(b,temp)) {	
			d=distance2(b,temp);
			temp2=temp;
		}
		temp=temp->next;
}
return temp2;
}







void dpoint(clu *a){
	int i;
	po* temp;
	if(a->num==1){		
		a->d_head=a->head;
		a->d_end=a->end;}
	else if(a->num<=dai){
		a->d_head=a->head;
		a->d_end=a->end;
		temp=a->d_head;
		for(i=1;i<=a->num;i++){
			temp->d_next=temp->next;
			temp=temp->next;		
			}
		}

	else {
		a->d_head=mahead(a,&(a->centre));
		a->d_end=a->d_head;
		a->d_end->d_next=a->d_head;
		for(i=2;i<=dai;i++){
			a->d_end->d_next=ma(a,a->d_end);
			a->d_end=a->d_end->d_next;
			a->d_end->d_next=a->d_head;
			}	
		a->d_end->d_next=NULL;
	}



}

void cleard(clu* a){
po *temp;
int i;
temp=a->head;
for(i=1;i<=a->num;i++) {
temp->d_next=NULL;
temp=temp->next;
}

}

void cure(){
	clu* temp;
	clu* temp2;
	po* p1;
	po* p2;
	clu* c1;
	clu* c2;
	int i,l;

	double d=999999999999999;
	temp=c_head->next;
	for (i=1;i<=total-1;i++){temp2=temp->next;
		for(l=i+1;l<=total;l++){
			p1=temp->d_head;
			p2=temp2->d_head;
			

			while (p1!=NULL){
				while(p2!=NULL){
					if(d>distance2(p1,p2))
					{	d=distance2(p1,p2);
						c1=temp;
						c2=temp2;
				
					}
				p2=p2->d_next;
				}
			
			p1=p1->d_next;
				
			}
				
		temp2=temp2->next;
		
		}
		
	temp=temp->next;
	}




combine(c1,c2);
cleard(c1);
dpoint(c1);


}





void dmin(){
	double dismin;
	int m,n;
	clu* a,*b;
	clu* mina,*minb;
	m=n=1;
	dismin=99999999999999;
	a=c_head->next;
	b=c_head->next->next;
	
	for(m=1;m<=total-1;m++){
		for(n=m+1;n<=total;n++){
			if (dismin>distance(a,b)){
				dismin=distance(a,b);
				mina=a;
				minb=b;
				}	
			b=b->next;
		}
	a=a->next;
	b=a->next;
	}
	combine(mina,minb);

}
void clear1(clu* a){
	po* temp1,*temp2;
	int n;
	temp1=a->head;
	for(n=1;n<=a->num;n++){
	temp2=temp1;
	temp1=temp1->next;
	delete temp2;
	
	}
}

void clear2(){
clu* temp1,*temp2;
int n;
temp1=c_head->next;
for (n=1;n<=total;n++){
	temp2=temp1;
	temp1=temp1->next;
	clear1(temp2);
	delete temp2;


}



total=0;
c_head=new clu;
c_end=c_head;

}


















/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

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()

/////////////////////////////////////////////////////////////////////////////
// CJuDlg dialog

CJuDlg::CJuDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CJuDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CJuDlg)
	m_y = 0.0f;
	m_total = 0;
	m_x = 0.0f;
	m_lei = 2;
	m_dai = 2;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CJuDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CJuDlg)
	DDX_Text(pDX, IDC_EDIT2, m_y);
	DDV_MinMaxFloat(pDX, m_y, 0.f, 5.e+006f);
	DDX_Text(pDX, IDC_EDIT4, m_total);
	DDV_MinMaxInt(pDX, m_total, 0, 50000);
	DDX_Text(pDX, IDC_EDIT3, m_x);
	DDV_MinMaxFloat(pDX, m_x, 0.f, 5.e+006f);
	DDX_Text(pDX, IDC_EDIT5, m_lei);
	DDV_MinMaxInt(pDX, m_lei, 0, 50000);
	DDX_Text(pDX, IDC_EDIT6, m_dai);
	DDV_MinMaxInt(pDX, m_dai, 1, 10);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CJuDlg, CDialog)
	//{{AFX_MSG_MAP(CJuDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_BUTTON1, OnButton1)
	ON_BN_CLICKED(IDC_BUTTON3, OnButton3)
	ON_BN_CLICKED(IDC_BUTTON2, OnButton2)
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CJuDlg message handlers

BOOL CJuDlg::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
	//////
	
	c_head=new clu;
	c_end=c_head;
	dai=2;
	lei=2;



	













	/////
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CJuDlg::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 CJuDlg::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 CJuDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}

void CJuDlg::OnButton1() 
{

clu* c_temp;
po* p_temp;

total++;

c_temp=new clu;
c_end->next=c_temp;

p_temp=new po;
c_temp->head=p_temp;
c_temp->end=p_temp;
c_temp->next = NULL;
c_temp->num=1;
p_temp->next = NULL;
c_temp->centre.x=m_x;
c_temp->centre.y=m_y;


UpdateData(TRUE);
p_temp->x=m_x;
p_temp->y=m_y;
m_total=total;
UpdateData(FALSE);

c_end=c_temp;



		
}


void CJuDlg::OnButton2() 
{ int i,n;
clu* temp;
po* tempp;

	while(total>500){		
	dmin();	
	}
	dai=m_dai;
	temp=c_head->next;
	for(i=1;i<=total;i++){
		dpoint(temp);
		temp=temp->next;
	}
temp=c_head->next;
lei=m_lei;

for(;total>lei;){
		cure();
		
			
	}



	UpdateData(TRUE);
	m_total=total;
	UpdateData(FALSE);
ofstream fout("result.txt");
temp=c_head->next;

for(i=1;i<=total;i++)
{
	fout<<"第"<<i<<"类:"<<endl;	
	tempp=temp->head;
	for(n=1;n<=temp->num;n++){
		fout<<tempp->x<<","<<tempp->y<<endl;
		tempp=tempp->next;		
	}	
	tempp=temp->d_head;
	fout<<"  代表点:"<<endl;
	while(tempp!=NULL){
	
	fout<<tempp->x<<","<<tempp->y<<endl;
	tempp=tempp->d_next;

	}




fout<<endl;
temp=temp->next;
}



fout.close();
clear2();
}


void CJuDlg::OnButton3() 
{
clear2();
	

	UpdateData(TRUE);
	m_total=total;
	UpdateData(FALSE);
	
}