[자료구조 프로그래밍 연습문제] 연결 리스트 (linked list) invert 함수, 원형 연결 리스트 (circular linked list)

linked list

 

A. 교재 4.5절에 설명된 Program 4.16: Inverting a singly linked list의 함수 invert를 고려하자. 리스트 p가 있을 때 q = invert(p); 를 호출하면 <그림 1>처럼 리스트의 링크가 방향이 바뀐다. 교재의 invert를 수행하면서 그 동작과정을 확인하기 위한 프로그램을 아래와 같이 작성하고 invert의 실행 과정을 확인 및 설명하시오.

<그림 1>

• main 함수에서 노드 2개로 구성된 리스트 L2를 생성한 후, 생성한 리스트를 출력한다 (각 노드의 주소, 데이터 필드 값, link 필드 값을 출력한다.)
• 생성한 리스트에 대해 invert 함수를 호출한다.
• invert에서 while loop이 매회 수행된 직후마다 다음 회를 수행하기 전에 변수 trail, middle, lead의 값과 각 노드의 데이터 필드 값 및 link 필드 값을 출력한다. (즉, while loop가 모두 k번 수행된다면 이 출력을 k회 하게 된다.)
• main에서 invert가 return한 포인터가 가리키는 리스트를 출력한다. (각 노드의 주소, 데이터 필드 값, link 필드 값을 출력한다.)
• main에서 노드 1개로 구성된 리스트 L1을 생성한 후, 위의 과정을 수행한다.
• main에서 empty 리스트 L0를 생성한 후, 위의 과정을 수행한다.

invert의 실행 과정 확인 및 설명 :
출력된 값을 보고 그 시점의 리스트의 변화 상태를 (육필 또는 워드 등으로) 그림으로 그려서 설명한다.

 

이전 리스트(<L2>, <L1>, <L0>)와 문제 1번 변화 과정 :

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

// typedef struct listNode* listPointer;
typedef struct listNode {
	char data;
	listNode* link;
} listNode;

listNode* create2()
{
	listNode* first;
	listNode* second;

	first = (listNode*)malloc(sizeof(first));
	second = (listNode*)malloc(sizeof(second));
	second->link = NULL;
	second->data = 20;
	first->data = 10;
	first->link = second;
	return first;
}

void printList(listNode* first)
{
	printf("The list contains : \n");
	listNode* curr = first;
	if (curr == NULL) {
		printf("빈 리스트 입니다.\n");
	}
	while (curr != NULL) {
		printf("노드 주소 : %p / ", curr);
		printf("데이터 값 : %d / ", curr->data);
		printf("link 값 : %p \n", curr->link);
		curr = curr->link;
	}
	printf("\n");
}

listNode* invert(listNode* lead)
{
	listNode* middle;
	listNode* trail;
	middle = NULL;
	printf("<Inverting ...> \n\n");
	while (lead) {
		trail = middle;
		middle = lead;
		lead = lead->link;
		middle->link = trail;

		printf("trail : %p / middle : %p / lead : %p \n", trail, middle, lead);
		printList(middle);
	}
	return middle;
}

int main()
{
	listNode* L2 = create2();
	printf("<L2>\n");
	printList(L2);
	printf("\n");

	listNode* inverted_L2 = invert(L2);
	printf("\n");

	printf("<inverted L2>\n");
	printList(inverted_L2);

	listNode* L1 = (listNode*)malloc(sizeof(L1));
	L1->data = 1;
	L1->link = NULL;
	printf("<L1>\n");
	printList(L1);
	printf("\n");

	listNode* inverted_L1 = invert(L1);
	printf("\n");

	printf("<inverted L1>\n");
	printList(inverted_L1);

	listNode* L0 = NULL;
	printf("<L0>\n");
	printList(L0);
	printf("\n");

	listNode* inverted_L0 = invert(L0);
	printf("\n");

	printf("<inverted L0>\n");
	printList(inverted_L0);

	return 0;
}

 

 

B. circularly linked list의 invert를 수행하는 cinvert 함수를 구현하고자 한다. circularly linked list p가 있을 때 q = cinvert(p); 를 호출하면 <그림 2>처럼 리스트의 링크가 방향이 바뀐다. 교재의 invert 함수는 리스트를 invert하는 과정에서 별도의 노드를 할당하여 사용하지 않았다. 교재의 invert처럼 별도의 노드를 할당하여 사용하지 않고 cinvert의 구현이 가능한가? 가능하다면 그 방법을 설명하고, 불가능하다면 왜 invert 대상 리스트 이외에 새 노드의 할당이 반드시 필요한지 설명하시오. 자신이 설명한대로 cinvert를 구현하여 노드가 2개인 리스트, 1개인 리스트, empty 리스트 각각에 대해 main에서 cinvert 호출 전에 리스트를 출력하고 호출 후 반환된 포인터가 가리키는 리스트를 출력하여 구현한 cinvert의 정확성을 보이시오.

 

알고리즘 설명 :

listNode* cinvert(listNode* lead)
{
	listNode* temp = lead;
	listNode* middle;
	listNode* trail;
	middle = NULL;
	printf("<Inverting ...> \n\n");
	while (lead) {
		trail = middle;
		middle = lead;
		lead = lead->link;
		middle->link = trail;

		printf("trail : %p / middle : %p / lead : %p \n", trail, middle, lead);
		printList(middle);

		if (temp == lead) {
			lead->link = middle;
			break;
		}
	}
	return middle;
}

새로운 노드를 추가하지 않고, 첫 포인터를 temp라는 임시 포인터에 저장하여, 해당 포인터를 가리키는 노드가 나오면, 그 노드의 포인터가 원래 리스트의 마지막 노드에 해당하는 현재 middle 노드를 가리키도록 설정할 수 있다.

 

실행화면 :

cinvert 함수 호출 후 출력되는 결과에 의하면, 원형 리스트가 invert 되었음을 확인할 수 있다.

<inverted L2>와 <inverted L1>, <inverted L0> 참고

정확성 동작 여부 : 정확

 

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

// typedef struct listNode* listPointer;
typedef struct listNode {
	char data;
	listNode* link;
} listNode;

listNode* create2()
{
	listNode* first;
	listNode* second;

	first = (listNode*)malloc(sizeof(first));
	second = (listNode*)malloc(sizeof(second));
	second->data = 20;
	first->data = 10;
	first->link = second;
	second->link = first;
	return first;
}

void printList(listNode* first)
{
	printf("The list contains : \n");
	listNode* temp = first;
	listNode* curr = first;
	if (curr == NULL) {
		printf("빈 리스트 입니다.\n");
	}
	while (curr != NULL) {
		printf("노드 주소 : %p / ", curr);
		printf("데이터 값 : %d / ", curr->data);
		printf("link 값 : %p \n", curr->link);
		if (curr->link != temp) {
			curr = curr->link;
		}
		else {
			break;
		}
	}
	printf("\n");
}

listNode* cinvert(listNode* lead)
{
	listNode* temp = lead;
	listNode* middle;
	listNode* trail;
	middle = NULL;
	printf("<Inverting ...> \n\n");
	while (lead) {
		trail = middle;
		middle = lead;
		lead = lead->link;
		middle->link = trail;

		printf("trail : %p / middle : %p / lead : %p \n", trail, middle, lead);
		printList(middle);

		if (temp == lead) {
			lead->link = middle;
			break;
		}
	}
	return middle;
}

int main()
{
	listNode* L2 = create2();
	printf("<L2>\n");
	printList(L2);
	printf("\n");

	listNode* inverted_L2 = cinvert(L2);
	printf("\n");

	printf("<inverted L2>\n");
	printList(inverted_L2);

	listNode* L1 = (listNode*)malloc(sizeof(L1));
	L1->data = 1;
	L1->link = L1;
	printf("<L1>\n");
	printList(L1);
	printf("\n");

	listNode* inverted_L1 = cinvert(L1);
	printf("\n");

	printf("<inverted L1>\n");
	printList(inverted_L1);

	listNode* L0 = NULL;
	printf("<L0>\n");
	printList(L0);
	printf("\n");

	listNode* inverted_L0 = cinvert(L0);
	printf("\n");

	printf("<inverted L0>\n");
	printList(inverted_L0);

	return 0;
}