티스토리 뷰

Programming/뇌를 자극하는 알고리즘

뇌를 자극하는 알고리즘 - 6. 탐색 : 순차 탐색(Sequential Search) - 전진이동법(Move To Front Method), 전위법(Transpose Method)

ProjectKMS 2010. 10. 20. 23:40

구현소스

LinkedList.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <stdio.h>
#include <stdlib.h>

typedef int Element;

typedef struct tagNode{
	struct tagNode *NextNode;
	Element Data;
} Node;

Node* SLL_CreateNode(Element NewData); // 노드 생성

void SLL_DestroyNode(Node* Node); // 노드 파괴

void SLL_AppendNode(Node** Head, Node* NewNode); // 노드를 추가하는 함수 - 링크드 리스트 젤 끝(tail)에 추가

void SLL_RemoveNode(Node** Head, Node* Remove);	// 노드 제거 - 제거할 노드의 메모리 해제 기능

Node* SLL_GetNodeAt(Node* Head, int Location); // Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수

void SLL_DestroyAllNodes(Node **List); // 모든 노드를 한번에 제거하는 함수

int SLL_GetNodeCount(Node* Head); // 전체 노드의 개수를 리턴하는 함수.

void SLL_PrintAll(Node* List); // 전체 노드의 데이터를 프린트
#endif

---------------------------------------------------------------------------
LinkedList.cpp

#include "LinkedList.h"

// 노드 생성 함수
Node* SLL_CreateNode(Element NewData){

	Node* NewNode = (Node*)malloc(sizeof(Node));
	// 새로운 노드를 생성하고

	NewNode->Data = NewData; // 매개변수로 넘긴 데이터를 저장하고
	NewNode->NextNode = NULL; // 가리키는 다음 노드를 뜻하는 NewtNode는 NULL로

	return NewNode; // 생성한 노드의 주소를 리턴
}

// 생성한 노드를 메모리 해제시키는 함수
void SLL_DestroyNode(Node* Node){
	
	free(Node);
}

// 노드를 추가하는 함수 - 링크드 리스트 젤 끝(tail)에 추가
void SLL_AppendNode(Node** Head, Node* NewNode){
	// Head의 이중 포인터 선언 
	// - Head를 싱글 포인터로 선언시 Head가 가리키는 주소값의 바꿀수 없다.
	// - 이중포인터로 선언시 Node* 타입의 헤드의 주소를 넘기므로서 Head가 가리키는 Node의 변경이 가능
		
	// Head Node가 NULL이라면 - 현재 생성된 링크드 리스트가 없다.
	// 따라서 추가할 노드가 head이자 tail이다.
	if( (*Head) == NULL){		
		*Head = NewNode;
		//printf("New Node Inserted <Head Node> : NewNode's Data = %d\n", NewNode->Data);
	}
	else{ // 이미 만들어진 링크드 리스트가 있다면
		  // tail을 찾아서 tail의 NewxNode에 NewNode를 연결해야 한다.
		
		Node* Tail = (*Head); // Head가 가리키는 Node의 주소로 Tail 을 초기화
		while(Tail->NextNode !=NULL){ // Tail의 NewNode가 NULL이라면 Loop문 탈출 - 즉, Tail을 찾았다면 루프문 탈출
			Tail = Tail->NextNode;
			// Tail이 가리키는 Node를 Tail->NextNode 로 변경.
		}
		// Loop문 수행시 Tail은 링크드 리스트의 마지막 노드를 가리키게 됨
		Tail->NextNode = NewNode;
		//printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
		
	}
}

// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
void SLL_RemoveNode(Node** Head, Node* Remove){
	if( (*Head) == Remove){ // 제거할 Remove노드가 Head가 가리키는 노드와 같을시
		*Head = Remove->NextNode; // Head노드가 가리킬 새로운 Node는 기존의 Head의 NextNode
	}
	else{
		Node* Current = *Head;
		
		while(Current != NULL && Current->NextNode!= Remove){
			// Current가 Tail에 도달하거나 Remove의 바로 앞 노드일시 Loop 탈출
			Current = Current->NextNode;
		}
		if(Current != NULL) // Current가 Remove 바로 앞 노드 가리킬시
			Current->NextNode = Remove->NextNode ; // Remove의 NextNode를 Current의 NextNode가 가리키게됨.
		else{ // 제거할 노드가 없을시
			printf("Error - 제거할 노드가 존재하지 않습니다!\n");
			return ;
			// 예외 처리
		}
	}
	//printf("A Node Is Removed             : Removed Node's Data = %d \n", Remove->Data);
	SLL_DestroyNode(Remove); // 삭제할 노드의 메모리 해제!
}

// 전체 노드의 개수를 조사해 그 수를 리턴하는 함수
int SLL_GetNodeCount(Node* Head){
	int Node_Count = 0;
	Node* Current = Head;

	while(Current != NULL){
		// ex) 2개의 노드 존재시
		// - 첫번째 루프 - 조건만족 : Current가 1번노드로 이동하고 Count는 1
		// - 두번째 루프 - 조건만족 : Current가 2번노드(NULL)로 이동하고 Count는 2
		// - 세번째 루프 - 루프탈출 : Count 는 2
		Current = Current->NextNode;
		Node_Count++;
	}

	return Node_Count;
}

// Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수
Node* SLL_GetNodeAt(Node* Head, int Location){
	Node* Current = Head;
	int Temp_Location = Location;

	while(Current!=NULL && (--Location) >= 0){
		// Current가 Tail에 도달 하거나
		// Location이 나타내는 수만큼 노드 이동 연산이 끝났을시 Loop 탈출
		
		// ex) 0번노드 1번노드 2번노드 존재시
		// Location = 1이고 Head는 0번노드를 가리킴
		// - 루프 첫번째
		// Location은 0이 되고 Current = Current->NextNode 수행하고 Current는 1번노드를 가리킴
		// - 루프 두번째 Location이 -1이 되어 loop 탈출 - 따라서 Current는 Location번째 노드를 가리키게 됨
		Current = Current->NextNode;
	}

	// 대충 예외처리
	if(Current!=NULL) // 옳바르게 탐색이 수행됐을시
		return Current;
	else{ // 탐색에 실패했을시
		printf("Error - %d번 노드가 존재하지 않음.\n",Temp_Location);
		return NULL;
	}
}

// 모든 노드를 한번에 제거하는 함수
void SLL_DestroyAllNodes(Node **List){	
	int i;
	int Count = SLL_GetNodeCount(*List); // 전체 노드의 갯수를 얻은 후
	Node* Current;

	for(i=0 ; i< Count ; i++){
		Current = SLL_GetNodeAt(*List,0);
		// 0번째 노드를 삭제하게 되면 그 다음 노드가 0번 노드가 되고.. 이런식으로 반복되기 때문에
		// 이걸 현재 노드의 개수만큼 수행하면 모든 노드가 삭제된다.
		SLL_RemoveNode(List, Current);
	}
}

// 전체 노드의 데이터를 프린트
void SLL_PrintAll(Node* List){
	int i=0;
	int Count = SLL_GetNodeCount(List);
	Node* Current = List;


	printf("- Current Linked List State -\n");
	
	
	if(Count){
		for(i=0;i < Count; i++){
			printf("%d -> ", Current->Data);
			Current = Current->NextNode;
		}
		printf("\n");
	}
	else{
		printf("Doesn't Exist Current Linked List\n");
	}
	printf("\n");
}

---------------------------------------------------------------------------
SequentialSearch.h

#ifndef SEQUENTIAL_SEARCH_H
#define SEQUENTIAL_SEARCH_H

#include "LinkedList.h"
// 순차탐색

// 전진이동법 - 탐색된 데이터를 데이터 집합의 가장 앞에 위치시키는 방법

// 전진이동법 - 링크드 리스트
Node* SLL_MoveToFront(Node** Head, Element Target);
// 전진이동법 - 배열
Element ARR_MoveToFront(Element Arr[], Element Target, int size);

// 전위법 - 탐색된 데이터를 이전 항목과 교환

// 전위법 - 링크드 리스트
Node* SLL_Transpose(Node** Head, Element Target);
// 전위법 - 배열
Element ARR_Transpose(Element Arr[], Element Target, int size);

#endif

---------------------------------------------------------------------------
SequentialSearch.cpp

#include "SequentialSearch.h"

// 순차탐색 - 전진이동법 - Linked List
Node* SLL_MoveToFront(Node** Head, Element Target)
{
	Node* Current  = (*Head);
	Node* Previous = NULL;
	Node* Match    = NULL;

	while(Current != NULL)
	{
		if(Current->Data == Target)
		{
			Match = Current;
			// 전진이동과정
			if(Previous != NULL)
			{ // 이전 노드가 NULL일시 탐색 대상은 Head Node이므로 노드의 링크 변경이 불필요하다.
				Previous->NextNode = Match->NextNode;

				Match->NextNode = (*Head);
				(*Head) = Match;
			}

			break;
		}
		Previous = Current; 
		Current  = Current->NextNode;
	}

	return Match;

}

// 순차탐색 - 전진이동법 - Array
Element ARR_MoveToFront(Element Arr[], Element Target, int size)
{
	int i;

	for(i=0 ; i<size; i++)
	{
		if(Arr[i] == Target)
			break;
	}

	if( i == size )
	{
		printf("Not Exist Data : %d", Target);
		return 0;
	}
	else
	{
		printf("Searching : Arr[%d] == %d\n", i, Target);		
		if(i>0) // 만약에 찾던 Target이 Arr의 0번 index에 있을시 전진이동을 하지 않아도 된다.
		{
			int j;
			Element *temp_Arr = (Element*) malloc(sizeof(Element) * size);
			// 데이터 백업을 위한 임시 배열 선언
			temp_Arr[0] = Arr[i]; // 임시 배열의 0번 Data를 Target Data로 만들고

			for(j=1; j < size ; j++)
			{	
				if(j <= i)
					temp_Arr[j] = Arr[j-1];
				else
					temp_Arr[j] = Arr[j];
				// ex) Target = 48 일때
				//              0   1   2   3   4   5    6    7   8   9
				// Arr[]      = 71,  5, 13,  1,  2, 48, 222, 136,  3, 15
				  
				// temp_Arr[] = 48, 71,  5, 13,  1,  2, 222, 136,  3, 15
				

				// 48이 있는 5번 index를 기준으로 j가 이 값보다 작거나 같을땐 temp_Arr[j] = Arr[j-1]
				//                                j가 이 값보다 클때에는 temp_Arr[j] = Arr[j]                           
			}

			for(j=0; j<size; j++) // 완성된 백업 데이터를 다시 copy하고
				Arr[j] = temp_Arr[j];

			free(temp_Arr); // 임시배열은 메모리 해제.
		}

		return 1;
	}

}

// 전위법 - 링크드 리스트
Node* SLL_Transpose(Node** Head, Element Target)
{
	Node* Current   = (*Head);
	Node* PPrevious = NULL; // 이이전 노드
	Node* Previous  = NULL; // 이전노드
	Node* Match     = NULL; // Target과 Data가 일치하는 Node
	while(Current!=NULL)
	{
		if(Current->Data == Target)
		{
			Match = Current;
			if(Previous != NULL) 
				// Previous가 NULL일시 찾고자하는 Match는 Head와 같으므로 별개의 링크 조작이 필요없다.
			{
				if(PPrevious != NULL)
					PPrevious->NextNode = Current;
				else // 이이전의 Node가 NULL이라면 Current는 Head Node가 된다.(Match는 2번째 노드라는 애기)
					(*Head) = Current;

				Previous->NextNode = Current->NextNode;
				Current->NextNode = Previous;
			}
			break;
		}

		if(Previous!=NULL)
			PPrevious = Previous;

		Previous = Current;
		Current = Current->NextNode;
	}

	return Match;
}
// 전위법 - 배열
Element ARR_Transpose(Element Arr[], Element Target, int size)
{
	int i;

	for(i=0; i<size ; i++)
	{
		if(Arr[i] == Target)
			break;
	}

	if( i == size )
	{
		printf("Not Exist Data : %d", Target);
		return 0;
	}
	else
	{
		printf("Searching : Arr[%d] == %d\n", i, Target);		

		if(i>0)
		{
			Element temp;
			temp = Arr[i];
			Arr[i] = Arr[i-1];
			Arr[i-1] = temp;
		}
		return 1;
	}

}

---------------------------------------------------------------------------
main.cpp

#include "SequentialSearch.h"

int main()
{
	Node* Head = NULL;
	Element Arr[10] = {71, 5, 13, 1, 2, 48, 222, 136, 3, 15};
	int i=0;

	SLL_AppendNode(&Head, SLL_CreateNode(71));
	SLL_AppendNode(&Head, SLL_CreateNode(5));
	SLL_AppendNode(&Head, SLL_CreateNode(13));
	SLL_AppendNode(&Head, SLL_CreateNode(1));
	SLL_AppendNode(&Head, SLL_CreateNode(2));
	SLL_AppendNode(&Head, SLL_CreateNode(48));
	SLL_AppendNode(&Head, SLL_CreateNode(222));
	SLL_AppendNode(&Head, SLL_CreateNode(136));
	SLL_AppendNode(&Head, SLL_CreateNode(3));
	SLL_AppendNode(&Head, SLL_CreateNode(15));

	SLL_PrintAll(Head);

	if(SLL_MoveToFront(&Head, 48)!=NULL)
		printf("--- After Sequential Search Move to Front method: 'Data = 48' Node ---\n"); 
	SLL_PrintAll(Head);

	for(i=0;i<2;i++)
	{
		if(SLL_Transpose(&Head, 1)!=NULL)
			printf("--- After Sequential Search Transpose method: 'Data = 1' Node ---\n"); 
		SLL_PrintAll(Head);
	}

	printf("- Current Array -\n");
	for(i=0; i < sizeof(Arr)/sizeof(Element);i++)
		printf("%d ", Arr[i]);
	printf("\n");

	
	if( ARR_MoveToFront(Arr,2,sizeof(Arr)/sizeof(Element)) )
	{		
		printf("- After Sequential Search Move to Front method: Data = 2 -\n");
		for(i=0; i < sizeof(Arr)/sizeof(Element);i++)
			printf("%d ", Arr[i]);
		printf("\n");
	}
	
	if( ARR_Transpose(Arr,13,sizeof(Arr)/sizeof(Element)) )
	{		
		printf("- After Sequential Search Move to Front method: Data = 13 -\n");
		for(i=0; i < sizeof(Arr)/sizeof(Element);i++)
			printf("%d ", Arr[i]);
		printf("\n");
	}

	if( ARR_Transpose(Arr,13,sizeof(Arr)/sizeof(Element)) )
	{		
		printf("- After Sequentail Search Move to Front method: Data = 13 -\n");
		for(i=0; i < sizeof(Arr)/sizeof(Element);i++)
			printf("%d ", Arr[i]);
		printf("\n");
	}

	SLL_DestroyAllNodes(&Head);
	return 0;
}

---------------------------------------------------------------------------

실행 결과


'Programming > 뇌를 자극하는 알고리즘' 카테고리의 다른 글

뇌를 자극하는 알고리즘 - 6. 탐색 : 이진 탐색 트리(Binary Search Tree)  (0) 2010.10.22
뇌를 자극하는 알고리즘 - 6. 탐색 : 이진 탐색(Binary Search)  (0) 2010.10.21
뇌를 자극하는 알고리즘 - 5. 정렬 : Quick Sort - qsort함수의 활용  (0) 2010.10.13
뇌를 자극하는 알고리즘 - 4. 트리 : Expression Tree  (0) 2010.10.13
뇌를 자극하는 알고리즘(Data Structures In C) - 5. 정렬 : Quick Sort  (0) 2010.10.13