/*
?*?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