티스토리 뷰

뇌를 자극하는 알고리즘

2016/03/21

애니멀14 2016. 3. 21. 20:10

1. 링크드 리스트.

1. 링크드 리스트 클래스.

#include "20160321.h"

Node* CreateNode(ElementType NewData)
{
#ifdef	CPP
	Node* NewNode = new Node;
#else
	Node* NewNode = (Node*)malloc(sizeof(Node));
#endif
	memset(NewNode, 0, sizeof(Node));

	NewNode->Data = NewData;
	NewNode->NextNode = NULL;

	return NewNode;

}

void DestroyNode(Node* Node)
{
#ifdef	CPP
	delete Node;
#else
	free(Node);
#endif
	Node = NULL;		//댕글린 포인터 해제.

}

void AppendNode(Node** Head, Node* NewNode)
{
	if (NULL == (*Head))
		*Head = NewNode;
	else
	{
		Node* Tail = (*Head);

		while (NULL != Tail->NextNode)
			Tail = Tail->NextNode;

		Tail->NextNode = NewNode;
	}
}

void InsertAfter(Node* Current, Node* NewNode)
{
	NewNode->NextNode = Current->NextNode;
	Current->NextNode = NewNode;

}

void InsertNewHead(Node** Head, Node* NewHead)
{
	if (NULL == (*Head))
		(*Head) = NewHead;
	else
	{
		NewHead->NextNode = (*Head);
		(*Head) = NewHead;
	}

}

void RemoveNode(Node** Head, Node* Remove)
{
	if ((*Head) == Remove)
		(*Head) = Remove->NextNode;
	else
	{
		Node* Current = (*Head);

		while (NULL != Current && Current->NextNode != Remove)
			Current = Current->NextNode;

		if (NULL != Current)
			Current->NextNode = Remove->NextNode;
	}
}

Node* GetNodeAt(Node* Head, int nLocation)
{
	Node* Current = Head;

	while (NULL != Current && 0 <= (--nLocation))
		Current = Current->NextNode;

	return Current;

}

int GetNodeCount(Node* Head)
{
	int nCount = 0;

	Node* Current = Head;

	while (NULL != Current)
	{
		Current = Current->NextNode;
		nCount++;
	}
	return nCount;

}

2. 메인 클래스.

#include "20160321.h"

#ifdef	CPP
using namespace std;
#endif

void main(void)
{
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	for (int i = 0; i < 5; ++i)
	{
		NewNode = CreateNode(i);
		AppendNode(&List, NewNode);
	}

	NewNode = CreateNode(-1);
	InsertNewHead(&List, NewNode);

	NewNode = CreateNode(-2);
	InsertNewHead(&List, NewNode);

	system("pause");
	system("cls");

	int nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef	CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	Current = GetNodeAt(List, 5);
	NewNode = CreateNode(3000);

	InsertAfter(Current, NewNode);

	system("pause");
	system("cls");

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef	CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	Current = GetNodeAt(List, 2);

	RemoveNode(&List, Current);
	DestroyNode(Current);

	system("pause");
	system("cls");

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef	CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	NewNode = CreateNode(2000);

	AppendNode(&List, NewNode);

	system("pause");
	system("cls");

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef	CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, 0);

		if (NULL != Current)
		{
			RemoveNode(&List, Current);
			DestroyNode(Current);
		}
	}
	
}

 

2. 더블 링크드 리스.

1. 더블 링크드 리스트 클래스.

#include "20160321.h"

Node* CreateNode(ElementType NewData)
{
#ifdef CPP
	Node* NewNode = new Node;
#else
	Node* NewNode = (*Node)malloc(sizeof(Node));
#endif
	NewNode->Data = NewData;
	NewNode->PrevNode = NULL;
	NewNode->NextNode = NULL;

	return NewNode;

}

void DestroyNode(Node* Node)
{
#ifdef CPP
	delete Node;
#else 
	free(Node);
#endif
	Node = NULL;

}

void AppendNode(Node** Head, Node* NewNode)
{
	if (NULL == (*Head))
		(*Head) = NewNode;
	else
	{
		Node* Tail = (*Head);

		while(NULL != Tail->NextNode)
			Tail = Tail->NextNode;

		Tail->NextNode = NewNode;
		NewNode->PrevNode = Tail;
	}

}

void InsertAfter(Node* Current, Node* NewNode)
{
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	if (NULL != Current->NextNode)
		Current->NextNode->PrevNode = NewNode;
	Current->NextNode = NewNode;

}

void InsertNewHead(Node** Head, Node* NewHead)
{
	if (NULL == (*Head))
		(*Head) = NewHead;
	else
	{
		NewHead->NextNode = (*Head);
		(*Head) = NewHead;
	}

}

void RemoveNode(Node** Head, Node* Remove)
{
	if ((*Head) == Remove)
	{
		(*Head) = Remove->NextNode;

		if (NULL != (*Head))
			(*Head)->PrevNode = NULL;

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;
	}
	else
	{
		Node* Temp = Remove;

		if (NULL != Remove->PrevNode)
			Remove->PrevNode->NextNode = Temp->NextNode;

		if (NULL != Remove->NextNode)
			Remove->NextNode->PrevNode = Temp->PrevNode;
		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;
	}

}

Node* GetNodeAt(Node* Head, int nLocation)
{
	Node* Current = Head;

	while(NULL != Current && 0 <= (--nLocation))
		Current = Current->NextNode;

	return Current;

}

int GetNodeCount(Node* Head)
{
	unsigned int nCount = 0;

	Node* Current = Head;

	while (NULL != Current)
	{
		Current = Current->NextNode;
		nCount++;
	}
	return nCount;

}

2. 메인 클래스.

#include "20160321.h"

#ifdef CPP
using namespace std;
#endif

void main(void)
{
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	for (int i = 0; i < 5; ++i)
	{
		NewNode = CreateNode(i);
		AppendNode(&List, NewNode);
	}

	int nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	system("pause");
	system("cls");

	Current = GetNodeAt(List, 2);
	NewNode = CreateNode(3000);
	InsertAfter(Current, NewNode);

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	system("pause");
	system("cls");

	NewNode = CreateNode(2000);
	AppendNode(&List, NewNode);

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	system("pause");
	system("cls");

	NewNode = CreateNode(1000);
	InsertNewHead(&List, NewNode);

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

}

 

3. 순환 링크드 리스트.

1. 순환 링크드 리스트 클래스.

#include "20160321.h"

Node* CreateNode(ElementType NewData)
{
#ifdef CPP
	Node* NewNode = new Node;
#else
	Node* NewNode = (*Node)malloc(sizeof(Node));
#endif
	NewNode->Data = NewData;
	NewNode->PrevNode = NULL;
	NewNode->NextNode = NULL;

	return NewNode;

}

void DestroyNode(Node* Node)
{
#ifdef CPP
	delete Node;
#else
	free(Node);
#endif
	Node = NULL;

}

void AppendNode(Node** Head, Node* NewNode)
{
	if (NULL == (*Head))
	{
		(*Head) = NewNode;
		(*Head)->NextNode = (*Head);
		(*Head)->PrevNode = (*Head);
	}
	else
	{	
		Node* Tail = (*Head)->PrevNode;

		Tail->NextNode->PrevNode = NewNode;
		Tail->NextNode = NewNode;

		NewNode->NextNode = (*Head);
		NewNode->PrevNode = Tail;
	}

}

void InsertAfter(Node* Current, Node* NewNode)
{
	NewNode->NextNode = Current->NextNode;
	NewNode->PrevNode = Current;

	Current->NextNode->PrevNode = NewNode;
	Current->NextNode = NewNode;

}

void RemoveNode(Node** Head, Node* Remove)
{
	if ((*Head) == Remove)
	{
		(*Head)->PrevNode->NextNode = Remove->NextNode;
		(*Head)->NextNode->PrevNode = Remove->PrevNode;

		(*Head) = Remove->NextNode;

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;
	}
	else
	{
		Node* Temp = Remove;

		Remove->PrevNode->NextNode = Temp->NextNode;
		Remove->NextNode->PrevNode = Temp->PrevNode;

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL;
	}
}

Node* GetNodeAt(Node* Head, int nLocation)
{
	Node* Current = Head;

	while (NULL != Current && 0 <= (--nLocation))
		Current = Current->NextNode;
	return Current;

}

int GetNodeCount(Node* Head)
{
	unsigned int nCount = 0;

	Node* Current = Head;

	while (NULL != Current)
	{
		Current = Current->NextNode;
		nCount++;

		if (Current == Head)
			break;
	}
	return nCount;

}

2. 메인 클래스.

#include "20160321.h"

#ifdef CPP
using namespace std;
#endif

void main(void)
{
	Node* List = NULL;
	Node* NewNode = NULL;
	Node* Current = NULL;

	for (int i = 0; i < 5; ++i)
	{
		NewNode = CreateNode(i);
		AppendNode(&List, NewNode);
	}

	int nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	system("pause");
	system("cls");

	Current = GetNodeAt(List, 2);
	NewNode = CreateNode(2000);
	InsertAfter(Current, NewNode);

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount * 2; ++i)
	{
		Current = GetNodeAt(List, i);
#ifdef CPP
		cout << "List[" << i << "] : " << Current->Data << endl;
#else
		printf("List[%d] : %d\n", i, Current->Data);
#endif
	}

	system("pause");
	system("cls");

	nCount = GetNodeCount(List);

	for (int i = 0; i < nCount; ++i)
	{
		Current = GetNodeAt(List, i);

		if (NULL != Current)
		{
			RemoveNode(&List, Current);
			DestroyNode(Current);
		}
	}

}

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

2016/03/23  (0) 2016.03.23
2016/03/22  (0) 2016.03.22
공유하기 링크
댓글
공지사항