c언어 데이터마이닝

https://github.com/kimdonwon/DataMining

c언어 데이터마이닝 정리

1. 링크드 리스트 사용

typedef struct Item {
	char *Name;
	int Hit;
	int distance_fromEntrance;
	struct Item *rlink;
	struct Item *llink;
	struct related_ItemList_Header *related;
	}Item;
	typedef struct Item_Header {
	struct Item *head;
	struct Item *rear;
	}Item_Header;

구조체를 사용해서 리스트 구성함
rlink는 다음 Item의 주소값
llink는 전 Item의 주소값

{
	Item *temp = (Item*)malloc(sizeof(Item));
	temp->Name = point_B->Name;
	temp->Hit = point_B->Hit;
	temp->distance_fromEntrance = 10;
	temp->related = temp->llink = temp->rlink = NULL;
	I->head = temp;
	I->rear = temp;
	return temp;
	}

이런식으로 첫 번째  데이터를 추가함

	I->rear->rlink = temp;
	temp->llink = I->rear;
	I->rear = temp;

두 번째 데이터를 추가할 땐 rear를 사용함

구조가
Item -> 1a -> 2b -> 3c ->4d ....
이렇게 되어있고
각각의 아이템마다 연관 상품이 저장되어 있다.
1a -> 2b->3c...
2b->1a->4d ...
이렇게 각각의 아이템마다 연관 상품이 저장되어 있음.
-> 주소값을 다루기 때문에 잘못 설계하면 데이터가 꼬이는 일이 있었음 (2번이나 다시 만들었다.)

2. 다익스트라 알고리즘

1. 0 노드부터 다른 노드들의 거리를 담을 리스트를 만듬
2. 리스트에 거리를 저장함
3. 리스트에서 최소 거리를 찾음
4. 최소 거리에 있는 노드에 들어가 0노드부터의 거리를 갱신함
5. 2~4 반복

//다익스트라 알고르즘에 사용될 리스트 생성

Item_distanceList_Header *idh = (Item_distanceList_Header*)malloc(sizeof(Item_distanceList_Header));

idh->all_checked = 0;

idh->head = idh->rear = NULL;

Item *i = I->head;

int count = 0;

while (i != NULL) {

count++;

i = i->rlink;

}

related_ItemList *rl = target_Item->related->head;

Item_distanceList *temp = (Item_distanceList*)malloc(sizeof(Item_distanceList));

temp->name = target_Item->Name;

temp->distance = 0;

temp->found = 1;

temp->possible = 0;

temp->rlink = temp->llink = NULL;

idh->head = idh->rear = temp;

// 다익스트라 알고리즘에 사용될 리스트에 초기 데이터를 넣어줌

while (rl != NULL) {

Item_distanceList *temp = (Item_distanceList*)malloc(sizeof(Item_distanceList));

temp->name = rl->item->Name;

temp->distance = rl->distance;

temp->found = 0;

temp->possible = 0;

temp->rlink = temp->llink = NULL;

idh->rear->rlink = temp;

temp->llink = idh->rear;

idh->rear = temp;

rl = rl->rlink;

}

// 제일 처음 최소 거리를 찾아줌

Item_distanceList *point_rl = idh->head->rlink;

Item_distanceList *temp_rl = idh->head->rlink;

while (point_rl != NULL) {

if (temp_rl->distance > point_rl->distance)temp_rl = point_rl;

point_rl = point_rl->rlink;

}

point_rl = idh->head->rlink;

// 최소 거리에 있는 노드를 기준으로 최소 거리를 찾아줌

while (point_rl != NULL) {

temp_rl = distance_update(idh, temp_rl, I);

if (temp_rl == idh->head)break;

point_rl = point_rl->rlink;

}

-> 생각보다 쉽게 해결함

다익스트라 알고리즘

다익스트라 알고리즘

그래프에서 하나의 노드를 기준으로 전체 노드의 최단거리를 구함

1. 처음 0번 노드에 연결된 노드들의 거리를 받음
2. 0번 노드에 연결된 것들 중 최소 거리의 노드를 구함
3. 최소 거리 노드를 이용하여 새로운 거리를 구함
반복
Ex. a에서 b로 바로 가면 7, a에서 c를 갔다가 b를 가면 3 -> a에서 b의 거리를 7에서 3으로 바꿈

배열을 사용하면 순차적으로 진행하기 때문에 시간복잡도는 N^2로 느리다.
힙(우선순위 큐)를 사용하면 최소 거리의 노드를 구하는 식이 LogN으로 단축된다.
즉 시간복잡도는 N*LogN으로 단축된다.

pair 

서로 다른 두개의 자료형을 저장하는 자료구조
-> 우선순위 큐에 pair 형식으로 데이터를 넣어줌

소스코드
https://github.com/kimdonwon/Algorithm/tree/master/Algorithm/src/Algorithm