단순연결리스트

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

typedef struct list_node *list_pointer;

/*

단순연결 리스트에서 노드를 표현하는 구조체 선언

- 맴버변수 두 개를 가진다.

- 하나는 노드에 저장될 정수형 데이터, 다른 하나는 다음 순서에 올 노드의 주소값

*/

typedef struct list_node 

{

int data; //노드에 저장될 데이터 (정수 데이터를 저장)

list_pointer link; //다음 순서의 노드를 가르키는 링크 값(주소값) 링크 값. 리스트의 한개의 노드는 data와 link로 구성됨.

}list_node;

/*

단순 연결리스트에 새로운 노드를 추가하는 함수

- list_pointer *target_list : 새로생성한 노드가 추가될 대상(Target)이 되는 리스트

- list_pointer position : 새로운 노드가 위치할 위치값 (target_list의 일부 노드, 해당 노드앞에 새로 생성한 노드가 연결)

- int data : 노드에 삽입하고자 하는 데이터

*/

void insert(list_pointer *target_list, list_pointer &position, int data){

//새로운 노드 i 를 생성 (malloc 함수를 통한 동적 메모리 할당)

list_pointer new_node = (list_pointer)malloc(sizeof(list_node)); 

//메모리 공간 부족으로 인해 메모리할당을 실패한 경우 프로그램 종료

if(!new_node || new_node == NULL)

{

printf("The memory is full\n");

exit(1);

}

//새로 생성한 노드에 삽입하고자 하는 데이터를 저장

new_node->data = data;

/*

새로생성한 노드가 추가될 대상(Target) 리스트에 대해서

공백리스트인 경우와 그렇지 않은 경우에 대한 분기를 나눔

*/

if(*target_list == NULL)

{

/*공백리스트인 경우*/

new_node->link = NULL; //새로 추가된 노드 뒤에 아무것도 없으므로 link 필드에 NULL 삽입

*target_list = new_node; //새로 생성한 노드가 첫 번째 노드가 되도록 

//대상 리스트(target_list)의 주소값을 새로 추가한 노드의 위치값으로 수정

}

else

{

/*공백리스트인 경우*/

new_node->link = position->link; //새로생성한 노드의 다음 노드로 position의 다음 노드를 지정

position->link = new_node; //position의 다음 노드로 새로 생성한 노드를 지정

}

}//insert() ======

/*

연결리스트의 특정 노드를 삭제하기 위한 함수

- list_pointer *target_list : 노드가 삭제될 대상(Target)이 되는 리스트

- list_pointer font_position : 삭제할 노드의 앞에 위치한 노드 위치값

- list_pointer end_position : 삭제할 노드의 위치값

*/

void deleted(list_pointer *target_list, list_pointer font_position, list_pointer delete_position)

{

if(font_position == NULL || delete_position == NULL) 

*target_list=(*target_list)->link;

else 

font_position->link = delete_position->link;

//동적메모리 영역(heap영역)에 할당받은 메모리 공간을 시스템에 반환

free(delete_position);

/*

왜 이렇게 작성된 것인지 그 이유를 알아야 한다.

단순 연결리스트는 노드간의 이동이 한쪽으로 (단방향으로) 밖에 안된다.

따라서 삭제하고자 하는 노드의 위치값은 물론, 그 삭제할 노드의 앞에 있는 노드에 대한 주소값이 있어야 한다.

예를 들어서

[1] -> [2] -> [3] -> null 가 있다고 가정합시다.

[2]를 삭제한다고 가정할 때

[1]의 link 값에 [3]의 주소를 대입해야 합니다.

따라서 삭제할 노드 [2]의 주소값과 (free로 메모리 반환을 해야하므로)

[1]과 [3]을 연결하기 위해 [1]의 주소값이 필요합니다. ([2]이전 노드의 주소값 필요)

*/

}//deleted()=====

/*

인자로 받은 연결리스트의 순서를 역순으로 정렬하는 함수

역순으로 정렬된 새로운 연결리스트를 반환

- list_pointer target_list : 역순으로 정렬할 대상(Target)이 되는 리스트

*/

list_pointer invert(list_pointer target_list)

{

list_pointer temp = NULL; //연결리스트를 임시로 저장할 임시 리스트 선언

list_pointer result = NULL; //역순으로 정렬된 연결리스트를 저장할 리스트 선언

//아래 반복문은 target_list가 NULL이 아닐때까지(노드가 존재하는 한) 반복동작한다.

while(target_list != NULL)

{

/*이 부분이 어렵습니다.*/

temp  = result; //이전에 처리한 결과를 temp에 임시저장

result  = target_list; //result에 순서가 앞으로 당겨진 target_list의 위치값을 지정

target_list  = target_list->link; //target_list가 다음 순서의 노드를 가르키도록 지정 (target_list의 순서를 앞으로 당기기)

result->link = temp; //result의 다음 순서로 이전에 처리했던 result를 연결

}

/*

위 반복문에 대한 동작을 순차적으로 기재하면 아래와 같습니다.

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

연결리스트가 우측과 같이 되어있다고 가정합니다 : [1] -> [2] -> [3] -> null

** 반복문 동작 전 상태**

target : [1] -> [2] -> [3] -> null

result : null

temp : null

**1회 동작시 각 객체의 상태**

target : [2] -> [3] -> null

result : [1] -> null

temp : null

**2회 동작시 각 객체의 상태**

target : [3] -> null

result : [2] -> [1] -> null

temp : [1] -> null

**3회 동작시 각 객체의 상태**

target : null

result : [3] -> [2] -> [1] -> null

temp : [2] -> [1] -> null

1. temp 변수는 이전 result의 값을 임시로 저장하는 용도로 사용됩니다.

2. target의 노드를 가르키는 위치는 매번 반복문 동작시 좌측에서부터 우측으로 1칸씩 이동합니다.

3. result에는 target의 좌측에 있는 노드부터 우측의 노드의 순서대로 하나씩 역순으로 쌓입니다.

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

*/

return result;

}//invert()=====

/*

연결리스트에 사입된 모든 노드의 데이터를 콘솔에 출력하는 함수

- list_pointer target_list 출력하고자 하는 대상이 되는 연결리스트

*/

void print(list_pointer target_list)

{

printf("The list contains: ");

//target_list가 NULL이 아닐때 까지 반복동작

//(모든 노드를 순환할 때 까지 반복동작)

while(target_list != NULL)

{

printf("%d ",target_list->data); //target_list에 대한 현재 노드의 데이터를 출력

target_list = target_list->link;   //target_list가 다음 노드를 가르키도록 지정

}

printf("\n");

}//print()=====

void main()

{

list_pointer ptr=NULL;  //ptr을 널 값으로 초기화

printf("리스트의 첫번째 노드로 10을 삽입\n");

insert(&ptr,ptr,10);

print(ptr);

printf("\n리스트의 첫번째 노드 뒤에 20을 삽입\n");

insert(&ptr,ptr,20);//삽입

print(ptr);  //첫번째 노드 부분을 출력

printf("\n리스트의 첫번째 노드 뒤에 30을 삽입\n");

insert(&ptr,ptr,30);  //삽입

print(ptr);

printf("\n리스트의 두번째 노드 뒤에 40을 삽입\n");

insert(&ptr, ptr->link,40);//간접참조 연산자를 -> 이용하여 삽입

print(ptr);

printf("\n리스트를 역순으로 만듬\n");

ptr=invert(ptr);

print(ptr);

printf("\n리스트의 두번째 노드 삭제\n");

deleted(&ptr,ptr,ptr->link);//2010버전에서 함수기능이 강화되어 delete 에러, deleted로 변경 함.

print(ptr);

printf("\n리스트의 첫번째 노드 삭제\n");

deleted(&ptr,NULL,ptr);

print(ptr);

}