二维空间坐标的dbscan聚类算法

实现二维空间坐标的聚类，对处于平面的二维点群进行分类

/*
 * dbscan.cpp
 *
 *  Created on: 2013-3-18
 *      Author: Administrator
 */

#include “../head/dbscan.h“
#include “../head/datastruct.h“
#include 
#include 
#include 
using namespace std;
//导入数据
DataStruct* CDBscan::load_data（char filepath[]）
{
	FILE *fp;
	DataStruct *head *p *q;
	double x y;
	fp = fopen（filepath “r“）;
	//判断文件句柄
	if（fp == NULL）
	{
		cout<<“打开文件失败“<		exit（0）;
	}
	//
	q = NULL;
	while（fscanf（fp“%lf %lf\n“ &x &y） != EOF）
	{
		//为头节点申请空间
		p = （DataStruct *）malloc（sizeof（DataStruct））;
		if（p == NULL）
		{
			cout<<“申请内存空间失败“<			exit（0）;
		}
		p->x = x;
		p->y = y;
		p->cluster_flag = -1;
		p->next = q;
		q = p;
	}
	printf（“数据导入成功\n“）;
	return q;
}
//初始化Eps返回数据个数
int CDBscan::init_eps（DataStruct *head）
{
	DataStruct *p = head *q;
	int notenum=0 n=0;
	double eps;
	while（p != NULL）
	{
		q = head;
		p->link_head = NULL;
		while（q != NULL）
		{
			eps = euclideanDistance（p q）;
			//将得到的值插入到距离链表中
			p->link_head = insert_data（p->link_head sqrt（eps））;
			q = q->next;
			n++;
			if（n == 4）
				break;
		}
		p = p->next;
		notenum++;
	}
	printf（“notenum = %d\n“ notenum）;
	return notenum;
}
//获得eps
double CDBscan::get_eps（DataStruct *head int k int notenum）
{
	Eps *p;
	int i = 0 j = 0;
	double eps;
	while（head != NULL）
	{
		p = head->link_head;
		while（p != NULL）
		{ 
			i++;
			if（i == k）
			{
				eps = p->eps;
				break;
			}
			else
				p = p->next;
		}
		j++;
		if（j == notenum）
			break;
		head = head->next;
	}
	return eps;
}
//插入每个点的距离数据
Eps* CDBscan::insert_data（Eps *head double data）
{
	Eps *p=NULL *q=NULL *pre=NULL;
	//申请内存空间
	p = （Eps*）malloc（sizeof（Eps））;
	if（p == NULL）
	{
		printf（“申请内存失败\n“）;
		exit（0）;
	}
	p->eps = data;
	//进行排序插入
	if（head == NULL）//说明是第一个节点
	{
		p->next = head; 
		head = p;
	}
	else//进行从小到大排列
	{
	    q = head;
		while（q != NULL）
		{
			//插入节点
			if（p->eps <= q->eps）
			{
				break;
			}
			else
			{
				pre = q;
				q = q->next;
			}
		}
		//看是否是第一个节点
		if（head == q）
		{
			p->next = head;
			head = p;
		}
		//不是第一个节点
		else
		{
			pre->next = p;
			p->next = q;
		}
	}
	return head;
}
//计算欧式距离
double CDBscan::euclideanDistance（DataStruct *point1 DataStruct *point2）
{
	return sqrt（ （（point1->x） - （point2->x）） * （（point1->x） - （point2->x）） + 
		（（point1->y） - （point2->y）） * （（point1->y） - （point2->y）） ）;
}

//标记核心点并删除离散点
DataStruct* CDBscan::core_point（DataStruct *head int k double eps）
{
	DataStruct *p_head *q_head *p *pre *temp;
	int n = 0;
	double temp_eps;
	//
	pre = p_head = head; 
	while（p_head）
	{
		q_head = head;
		n = 0;
		//检索和每个点的关系
		while（q_head）
		{
			temp_eps = euclideanDistance（p_head q_head）;
			if（temp_eps <= eps）
				n++;
			q_head = q_head->next;

		}//end while
		//标记为核心点
		if（n >= k）
		{
			//标记为和核心点
			p_head->cluster_flag = 0;
			//保存前驱节点
			pre

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-03-19 21:16  dbscan\
     文件        9834  2012-05-04 11:24  dbscan\2008-09-11-GPS.plt
     文件     1444064  2012-05-04 11:24  dbscan\2009-4-26.plt
     文件     1444108  2013-03-19 19:48  dbscan\2009-4-26.txt
     文件        4489  2013-03-18 16:26  dbscan\dbscan.dsp
     文件         518  2013-03-18 14:19  dbscan\dbscan.dsw
     文件       50176  2013-03-19 20:38  dbscan\dbscan.ncb
     文件       50688  2013-03-19 20:38  dbscan\dbscan.opt
     文件         246  2013-03-19 19:21  dbscan\dbscan.plg
     目录           0  2013-03-19 19:21  dbscan\Debug\
     文件      299079  2013-03-19 19:21  dbscan\Debug\dbscan.exe
     文件      415840  2013-03-19 19:21  dbscan\Debug\dbscan.ilk
     文件       49661  2013-03-19 19:21  dbscan\Debug\dbscan.obj
     文件     2013820  2013-03-19 19:08  dbscan\Debug\dbscan.pch
     文件     1115136  2013-03-19 19:21  dbscan\Debug\dbscan.pdb
     文件       12915  2013-03-19 17:17  dbscan\Debug\main.obj
     文件       91136  2013-03-19 19:21  dbscan\Debug\vc60.idb
     文件      110592  2013-03-19 19:21  dbscan\Debug\vc60.pdb
     目录           0  2013-03-19 14:36  dbscan\head\
     文件         395  2013-03-18 13:55  dbscan\head\datastruct.h
     文件         874  2013-03-19 14:36  dbscan\head\dbscan.h
     文件      166430  2012-05-04 11:24  dbscan\OZI__20080620082025.plt
     文件       62964  2012-05-04 11:24  dbscan\PLT2008-5-17.plt
     目录           0  2013-03-19 19:21  dbscan\src\
     文件        9834  2012-05-04 11:24  dbscan\src\2008-09-11-GPS.plt
     文件        5971  2013-03-19 19:21  dbscan\src\dbscan.cpp
     文件        1088  2013-03-19 17:17  dbscan\src\main.cpp