티스토리 뷰

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

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

ProjectKMS 2010. 9. 29. 15:49
코드

SSL.h

#ifndef SLL_H
#define SLL_H

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

typedef int ElementType;

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

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

int SLL_GetNodeCount(Node* Head);


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


#endif


SLL.cpp



#include "SLL.h"


// 노드 생성 함수
Node* SLL_CreateNode(ElementType 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);
		
	}
}

// Current 노드 뒤에 NewNode를 삽입하는 함수
void SLL_InsertAfter(Node* Current, Node* NewNode){
	NewNode->NextNode = Current->NextNode;
	Current->NextNode = NewNode;
	printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
}

// 새로운 노드를 Head로 만드는 함수(-링크드 리스트 맨 앞에 노드를 삽입하는 함수)
void SLL_InsertNewHead(Node** Head, Node* NewHead){
	if( (*Head) == NULL){ // Head가 존재하지 않을시 새로운 노드가 Head
		*Head = NewHead;
		printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->Data);
	}
	else{ // 기존의 Head가 존재시		
		NewHead->NextNode = (*Head);// 새로운 노드의 NextNode가 기존의 Head가 되고 
		(*Head) = NewHead; // 새로운 노드가 Head가 된다.	
		printf("New Head Inserted <Head Node> : NewNode's Data = %d \n", NewHead->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); // 삭제할 노드의 메모리 해제!
}

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

// Vitamin Quiz 추가 함수

// Current 노드 앞에 NewNode를 삽입하는 함수
void SLL_InsertBefore(Node **Head, Node* Current, Node* NewNode){
	Node* Temp_Cur = *Head;
	if( (*Head) == Current ) // Current와 Head가 같다면 - 즉 헤드 노드 앞에 삽입하려고 할시 
		SLL_InsertNewHead(Head,NewNode); // SLL_InsertNewHead 함수 호출!
	
	else{
		while(Temp_Cur != NULL && Temp_Cur->NextNode!= Current)
			Temp_Cur = Temp_Cur->NextNode; 
		// Remove 함수의 loop를 그대로 활용하여 Temp_Cur가 Current 노드의 앞의 노드를 가리키게 한다음

		Temp_Cur ->NextNode = NewNode; // Temp_Cur의 NextNode는 NewNode 가 되고
		NewNode->NextNode = Current;   // NewNode의 NextNode는 Current가 되도록.
		printf("New Node Inserted             : NewNode's Data = %d \n", NewNode->Data);
	}
}

// 모든 노드를 한번에 제거하는 함수
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);
	}
}


main.cpp



#include "SLL.h"

void Print_State_Of_SLL(Node* List){
	int i=0;
	int Count = SLL_GetNodeCount(List);
	Node* Current = List;

	printf("-----------------------------\n");
	printf("- Current Linked List State -\n");
	printf("-----------------------------\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");
	}

}

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 = SLL_CreateNode(i);
		// Node* SLL_CreateNode(ElementType NewData)
		SLL_AppendNode(&List,NewNode);	
		//void SLL_AppendNode(Node** Head, Node* NewNode)
	}

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


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

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

	Current = SLL_GetNodeAt(List,2);
	// Node* SLL_GetNodeAt(Node* Head, int Location)
	NewNode = SLL_CreateNode(22);
	SLL_InsertAfter(Current, NewNode);

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

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


	NewNode = SLL_CreateNode(222222);
	Current = SLL_GetNodeAt(List,2);
	SLL_InsertBefore(&List,Current,NewNode);
	// void SLL_InsertBefore(Node **Head, Node* Current, Node* NewHead)
	Print_State_Of_SLL(List); // 추가된 노드들의 데이터 출력

	

	

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

	Current = SLL_GetNodeAt(List,0);
	SLL_RemoveNode(&List,Current);
	// void SLL_RemoveNode(Node** Head, Node* Remove)
	Print_State_Of_SLL(List);

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

	printf("- 예외 처리 확인 -\n");
	Current = SLL_GetNodeAt(List,12);
	
	printf("******  Vitamin Quiz 확인 ******\n");
	printf("*******  모든 노드 삭제 ********\n");
	printf("********************************\n");

	SLL_DestroyAllNodes(&List);
	Print_State_Of_SLL(List);
	

	return 0;
}


실행결과











            



                    

  



  



  



  




                    


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

  

    

      뇌를 자극하는 알고리즘 - 3. 큐 : 순환 큐  (0)
      2010.10.05
    

    

      뇌를 자극하는 알고리즘 2. 스택 - Linked List Stack  (0)
      2010.10.02
    

    

      뇌를 자극하는 알고리즘 2. 스택 - ArrayStack  (1)
      2010.10.02
    

    

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

    

      뇌를 자극하는 알고리즘 1. 리스트 - Double Linked List  (0)
      2010.10.01