티스토리 뷰

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

뇌를 자극하는 알고리즘 1. 리스트 - Circle Double Linked List

ProjectKMS 2010. 10. 1. 00:27

코드


CDDL.h

#ifndef CDLL_H
#define CDLL_H

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

typedef int ElementType;

typedef struct tagNode{
	ElementType Data;
	struct tagNode *PrevNode;
	struct tagNode *NextNode;
} Node;

Node* CDLL_CreateNode(ElementType NewData); // 노드 생성
void CDLL_DestroyNode(Node* Node); // 노드 파괴
void CDLL_AppendNode(Node** Head, Node* NewNode); // 노드를 추가하는 함수 - 링크드 리스트 젤 끝(tail)에 추가
void CDLL_InsertAfter(Node* Current, Node* NewNode); // Current 노드 뒤에 NewNode를 삽입하는 함수
void CDLL_InsertNewHead(Node** Head, Node* NewHead); 
				// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void CDLL_RemoveNode(Node** Head, Node* Remove);	// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
Node* CDLL_GetNodeAt(Node* Head, int Location); // Location 번째의 노드(0번부터 시작)를 찾아 그 주소를 리턴하는 함수
			
int CDLL_GetNodeCount(Node* Head);


// Vitamin Quiz 추가 함수 
void CDLL_InsertBefore(Node **Head, Node* Current, Node* NewNode);// Current 노드 앞에 NewNode를 삽입하는 함수
void CDLL_DestroyAllNodes(Node **List); // 모든 노드를 한번에 제거하는 함수

// Vitamin Quiz 추가 함수 
void CDLL_PrintReverse(Node* Head); // 더블 링크드 리스트를 역순으로 출력하는 함수

#endif

------------------------------------------------------------------------------------------------------------
CDDL.cpp 

#include "CDLL.h"


// 노드 생성 함수
Node* CDLL_CreateNode(ElementType NewData){

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

	NewNode->Data = NewData; // 매개변수로 넘긴 데이터를 저장하고

	// SLL->DLL 로 변경하면서 새로 생긴 부분 //	
	NewNode->PrevNode = NULL; // 이전의 노드를 가리키는 PrevNode를 NULL로 초기화
	//////////////////////////////////////////
	NewNode->NextNode = NULL; // 가리키는 다음 노드를 뜻하는 NewtNode는 NULL로

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

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

// 노드를 추가하는 함수 - 링크드 리스트 젤 끝(tail)에 추가
void CDLL_AppendNode(Node** Head, Node* NewNode){
	// Head의 이중 포인터 선언 
	// - Head를 싱글 포인터로 선언시 Head가 가리키는 주소값의 바꿀수 없다.
	// - 이중포인터로 선언시 Node* 타입의 헤드의 주소를 넘기므로서 Head가 가리키는 Node의 변경이 가능
		
	// Head Node가 NULL이라면 - 현재 생성된 링크드 리스트가 없다.
	// 따라서 추가할 노드가 head이자 tail이다.
	if( (*Head) == NULL){		
		*Head = NewNode;
		// DLL -> CDLL 로 변경하면서 새로 생긴 부분 //

		(*Head)->PrevNode = NewNode; // NewNode->PrevNode = NewNode
		(*Head)->NextNode = NewNode;
		// 환형 링크드 리스트의 경우 Head의 PrevNode가 Tail, Tail의 NextNode가 Head 이므로
		// 처음 링크드 리스트에 노드가 추가 될시 그 노드의 PrevNode, NextNode는 자기 자신을 가리킨다.

		//////////////////////////////////////////////

		printf("New Node Inserted <Head Node> : NewNode's Data = %d\n", NewNode->Data);
	}
	else{ // 이미 만들어진 링크드 리스트가 있다면 기존 Tail의 뒤에 노드 추가
		// DLL -> CDLL 로 변경하면서 변경된 부분 //		
		
		Node* Tail = (*Head)->PrevNode;
		
		Tail->NextNode->PrevNode = NewNode; // Head 노드가 새로운 Tail인 NewNode를 가리키게 하고
		Tail->NextNode = NewNode; // 기존의 Tail 노드는 새로운 Tail인 NewNode를 가리키게 하고

		NewNode->PrevNode = Tail; // 기존의 Tail을 새로운 Tail인 NewNode의 PrevNode로
		NewNode->NextNode = (*Head); // 새로운 Tail인 NewNode의 NextNode는 Head가 된다.
		
		//////////////////////////////////////////////

		printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
		
	}
}

// Current 노드 뒤에 NewNode를 삽입하는 함수
void CDLL_InsertAfter(Node* Current, Node* NewNode){
	NewNode->NextNode = Current->NextNode;

	// SLL->DLL 로 변경하면서 새로 생긴 부분 //	
	NewNode->PrevNode = Current;

	// DLL -> CDLL 로 변경된 부분 //
	Current->NextNode->PrevNode = NewNode;
	// CDLL로 바뀌면서 Current의 NextNode가 NULL인 경우가 없어짐.
	Current->NextNode = NewNode;
	////////////////////////////////

	///////////////////////////////////////////

	printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
}

// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void CDLL_InsertNewHead(Node** Head, Node* NewHead){
	if( (*Head) == NULL){ // Head가 존재하지 않을시 새로운 노드가 Head
		*Head = NewHead;

		// DLL -> CDLL 로 변경된 부분 //
		(*Head)->PrevNode = NewHead; // NewNode->PrevNode = NewNode
		(*Head)->NextNode = NewHead;
		// 환형 링크드 리스트의 경우 Head의 PrevNode가 Tail, Tail의 NextNode가 Head 이므로
		// 처음 링크드 리스트에 노드가 추가 될시 그 노드의 PrevNode, NextNode는 자기 자신을 가리킨다.
		////////////////////////////////

		// CDLL_AppendNode 함수와 중복되는 부분이니 함수 CDLL_AppendNode 함수 호출로 처리해도 될듯..
		printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
	else{ // 기존의 Head가 존재시		
		NewHead->NextNode = (*Head);// 새로운 노드의 NextNode가 기존의 Head가 되고 

		// DLL -> CDLL 로 추가된 부분 //
		NewHead->PrevNode = (*Head)->PrevNode;
		(*Head)->PrevNode->NextNode = NewHead;
		////////////////////////////////

		// SLL->DLL 로 변경하면서 새로 생긴 부분 //
		(*Head)->PrevNode = NewHead;
		///////////////////////////////////////////
		(*Head) = NewHead; // 새로운 노드가 Head가 된다.	
		printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
}


// 노드 제거 - 제거할 노드의 메모리 해제 기능까지 자체 추가.
void CDLL_RemoveNode(Node** Head, Node* Remove){
	if( (*Head) == Remove){ // 제거할 Remove노드가 Head가 가리키는 노드와 같을시
		
			// DLL -> CDLL 로 변경된 부분 //
			// Head가 제거되므로 Tail의 링크와 Head의 NextNode의 링크가 변경되어야 한다.
			(*Head)->PrevNode->NextNode = Remove->NextNode;
			(*Head)->NextNode->PrevNode = Remove->PrevNode;
			////////////////////////////////
			
			*Head = Remove->NextNode; // Head노드가 가리킬 새로운 Node는 기존의 Head의 NextNode

			
			Remove->PrevNode = NULL; // 삭제대상의 PrevNode, NextNode를 NULL로
			Remove->NextNode = NULL; // 삭제되므로 연결고리를 끊는다.
			///////////////////////////////////////////
		
	}
	else{
		// SLL->DLL 로 변경하면서 새로 생긴 부분 //
		// SLL의 경우 삭제대상 Node의 바로 앞 노드까지 이동을 해서(Loop문으로) 기존 노드들의 연결상태를 바꿔야 했지만
		// DLL 삭제대상의 PrevNode, NextNode의 연결고리를 따라가면 기존 노드들의 연결상태를 쉽게 바꿀수 있다.
		Node* Temp = Remove;

		// DLL -> CDLL 로 변경된 부분 //
		Remove->PrevNode->NextNode = Temp->NextNode;
		// 삭제대상의 바로 앞의 노드가 가리키는 NextNode를 삭제대상 뒤의 노드로 변경

		// Remove 노드의 NextNode가 없을시의 상황은 고려하지 않는다.
		Remove->NextNode->PrevNode = Temp->PrevNode; // 삭제대상 뒤의 노드도 링크 상태를 변경해주어야 함.
		// 삭제대상 바로 뒤의 노드의 PrevNode가 삭제대상의 PrevNode를 가리킴
		////////////////////////////////

		Remove->PrevNode = NULL;
		Remove->NextNode = NULL; // 연결 고리 해제
		///////////////////////////////////////////
	}
	printf("A Node Is Removed             : Removed Node's Data = %d \n", Remove->Data);
	CDLL_DestroyNode(Remove); // 삭제할 노드의 메모리 해제!
}

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

	// DLL -> CDLL 로 변경된 부분 //

	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;
	}

	// 환형 연결리스트에서는 Current = Current->NextNode 가 NULL이 되는 경우는 없으므로
	// 탐색이 실패하는 경우에 대한 예외처리를 삭제하였다. 
	// ex) 총 노드 개수가 5개(노드번호 : 0,1,2,3,4)이면 0번노드는 5번노드가 될수도 있고 10번 노드가 될 수도 있다.
	// 링크드 리스트가 아에 존재하지 않을 경우에 대한 예외처리를 추가하였다.
	if(Current == NULL){
		printf("Doesn't Exist Current Linked List\n");
		return NULL;
	}
	return Current;
	////////////////////////////////
	
}

// 전체 노드의 개수를 얻는 함수
int CDLL_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++;
		// DLL -> CDLL 로 변경된 부분 //
		// 환형연결리스트에서는 Current->NextNode의 결과가 NULL이 되는 경우는 없으므로 적절한 break문을 추가
		if(Current == Head)
			break;
		////////////////////////////////	
	}

	return Node_Count;
}

// Vitamin Quiz 추가 함수

// Current 노드 앞에 NewNode를 삽입하는 함수
void CDLL_InsertBefore(Node **Head, Node* Current, Node* NewNode){
	if( (*Head) == Current ) // Current와 Head가 같다면 - 즉 헤드 노드 앞에 삽입하려고 할시 
		CDLL_InsertNewHead(Head,NewNode); // SLL_InsertNewHead 함수 호출!
	
	else{
		Current->PrevNode->NextNode = NewNode;
		// Current의 앞노드의 NextNode를 NewNode로
		NewNode->PrevNode = Current->PrevNode;
		// NewNode의 Prev를 기존 Current의 Prev노드로
		NewNode->NextNode = Current;
		// NewNode의 Next를 Current로
		Current->PrevNode = NewNode;
		// Current의 Prev는 NewNode로
		printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
	}
}

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

	for(i=0 ; i< Count ; i++){
		Current = CDLL_GetNodeAt(*List,0);
			// 0번째 노드를 삭제하게 되면 그 다음 노드가 0번 노드가 되고.. 이런식으로 반복되기 때문에
			// 이걸 현재 노드의 개수만큼 수행하면 모든 노드가 삭제된다.
		CDLL_RemoveNode(List, Current);		
	}
	// CDLL 추가 부분 //
	*List = NULL; 
	// 바로 위의 이 코드를 쓰지 않으니, 모든 노드를 제거하고 새로 생성할때 런타임 에러가 생김
	// - 원인은 대략적으로 짐작이 가는데.. 아무래도 마지막 하나 남은 node를 제거할때 Head가 가리키는 곳이 이미 사라진 0번node
	//  를 가리켜서 그런거 같은데.. ㅡㅡ;;;;; 
	//  에휴..ㅠ
	//  사실 이 삭제가 제대로 작동하고 있는지, 메모리 누수가 발생하고 있는지
	//  의문이 가득한데 파헤치려고 하니 골아프다.. 메모리 누수 정보를 확인할 수 있는 방법..뭐 없을까
	//  링크만 끊기고 사실 node는 존재하는게 아닐까 아아 ...
	////////////////////
}


// 노드의 데이터를 역순으로 출력하는 함수
void CDLL_PrintReverse(Node* Head){
	// DLL -> CDLL 로 변경된 부분 //
	Node* Tail = Head->PrevNode;
	int Count = CDLL_GetNodeCount(Head); 
	int i;

	// Tail노드에서 다시 Head로 이동(->PrevNode)
	printf("*** 노드의 데이터를 역순으로 출력 *** \n");
		
	while(Tail != NULL){
		printf("%d <-> ",Tail->Data);
		Tail = Tail->PrevNode;
		if(Tail == Head)
			break;
	}
	/* 이렇게 써도 됨. 노드의 개수만큼 PrevNode만큼 이동하면 Head노드의 데이터까지 출력 가능
	for(i=0;i<Count;i++){
		printf("%d <-> ",Tail->Data);
		Tail = Tail->PrevNode;	
	}
	*/
	printf("\n");
	///////////////////////////////
}


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

#include "CDLL.h"

void Print_State_Of_CDLL(Node* List){
	int i=0;
	int Count = CDLL_GetNodeCount(List);
	Node* Current = List;

	printf("-----------------------------\n");
	printf("- Current Linked List State -\n");
	printf("-----------------------------\n");
	
	if(Count){
		for(i=0;i < Count*2; i++){


//////////////// 환형 연결리스트의 연결상태가 옳바른지 파악하기 위해 노드개수의 * 2만큼 출력되게 만듬.



			printf("%d <-> ", Current->Data);
			Current = Current->NextNode;
		}
		printf("\n");
	}
	else{
		printf("Doesn't Exist Current Linked List\n");
	}

}

int main(){
	int i =0;
	int Count = 0;

	Node*    List = NULL; // Head 노드
	Node* Current = NULL;
	Node* NewNode = NULL;

	// 노드 5개 추가
	for(i=0;i<5;i++){
		NewNode = CDLL_CreateNode(i);
		// Node* CDLL_CreateNode(ElementType NewData)
		CDLL_AppendNode(&List,NewNode);	
		//void CDLL_AppendNode(Node** Head, Node* NewNode)
	}

	// 노드 2개 추가 - 링크드 리스트 맨 앞으로 넣음
	NewNode = CDLL_CreateNode(18);
	CDLL_InsertNewHead(&List,NewNode);
	NewNode = CDLL_CreateNode(28);
	CDLL_InsertNewHead(&List,NewNode);
	// void CDLL_InsertNewHead(Node** Head, Node* NewHead)


	// 추가된 노드들의 데이터 출력
	Print_State_Of_CDLL(List);

	
	// 2번째 노드 뒤에 새 노드 삽입
	printf("--------------------------------\n");
	printf("- 2번 노드 뒤에 새 노드를 삽입 -\n");
	printf("--------------------------------\n");

	Current = CDLL_GetNodeAt(List,2);
	// Node* CDLL_GetNodeAt(Node* Head, int Location)
	NewNode = CDLL_CreateNode(22);
	CDLL_InsertAfter(Current, NewNode);

	NewNode = CDLL_CreateNode(33);
	CDLL_InsertAfter(Current, NewNode);
	//void CDLL_InsertAfter(Node* Current, Node* NewNode)
	// 추가된 노드들의 데이터 출력
	Print_State_Of_CDLL(List);

	// Vitamin Quiz 확인 - 특정 노드 앞에 노드 삽입
	// 2번째 노드 앞에 새 노드 삽입
	printf("******  Vitamin Quiz 확인 ******\n");
	printf("* 2번 노드 앞에 새 노드를 삽입 *\n");
	printf("********************************\n");


	NewNode = CDLL_CreateNode(222222);
	Current = CDLL_GetNodeAt(List,2);
	CDLL_InsertBefore(&List,Current,NewNode);
	// void CDLL_InsertBefore(Node **Head, Node* Current, Node* NewHead)
	Print_State_Of_CDLL(List); // 추가된 노드들의 데이터 출력

	

	

	// 노드 삭제
	printf("-----------------\n");
	printf("- 0번 노드 삭제 -\n");
	printf("-----------------\n");

	Current = CDLL_GetNodeAt(List,0);
	CDLL_RemoveNode(&List,Current);
	// void CDLL_RemoveNode(Node** Head, Node* Remove)
	Print_State_Of_CDLL(List);

	printf("-----------------\n");
	printf("- 5번 노드 삭제 -\n");
	printf("-----------------\n");
	Current = CDLL_GetNodeAt(List,5);
	CDLL_RemoveNode(&List,Current);
	// void CDLL_RemoveNode(Node** Head, Node* Remove)
	Print_State_Of_CDLL(List);

	printf("- 예외 처리 확인 -\n");
	Current = CDLL_GetNodeAt(List,12);
	printf(" Current = CDLL_GetNodeAt(List,12) \n");
	printf(" Current->data = %d\n", Current->Data);
	printf("\n");

	printf("*******  Vitamin Quiz 확인 *******\n");
	printf("*******  데이터 역순 출력 ********\n");
	printf("**********************************\n");
	CDLL_PrintReverse(List);
	
	
	
	printf("******  Vitamin Quiz 확인 ******\n");
	printf("*******  모든 노드 삭제 ********\n");
	printf("********************************\n");
	CDLL_DestroyAllNodes(&List);
	Print_State_Of_CDLL(List);
	
	return 0;
}


--------------------------------------------------------------------------------------------
 
실행 결과


 

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

뇌를 자극하는 알고리즘 - 3. 큐 : 순환 큐  (0) 2010.10.05
뇌를 자극하는 알고리즘 2. 스택 - Linked List Stack  (0) 2010.10.02
뇌를 자극하는 알고리즘 2. 스택 - ArrayStack  (1) 2010.10.02
뇌를 자극하는 알고리즘 1. 리스트 - Double Linked List  (0) 2010.10.01
뇌를 자극하는 알고리즘 1. 리스트 - Single Linked List  (4) 2010.09.29