[230503] 자료구조 과제5: 순환(recursion)

자료구조 7주차 : 순환

과제4의 Node클래스와 LinkedList클래스를 바탕으로 추가함수를 구현하는 과제

[20230414] 자료구조 과제4: LinkedList클래스 (tistory.com)

[20230414] 자료구조 과제4: LinkedList클래스

 

※문제설명

• 지난 과제에서 구현한 Node 클래스와 LinkedList 클래스가 있다. Node클래스의 경우는 기존 코드 외setData() 함수가 추가되었다(내용은 코드를 참고)
• 그리고LinkedList 클래스에는 기존에 있던size(), display(), reverse(), 및mergeTwoLists()가 삭제되었고 다섯 가지의 함수가 추가된다. 클래스 LinkedList의 다음과 같은 추가 함수들을 정의하라. 
• 모든 함수의 경우 LinkedListRecursion_Student.cpp에 제공된 함수만 사용하라. (그 외의 함수를 사용할 시 감점)
• 함수가 순환 방식으로 구현되지 않은 경우, 점수를 부여하지 않는다

※구현할 함수  

• intsizeRecursive(Node* curr): 객체(LinkedList)의 사이즈를 반환하는 기존의 size() 함수를 순환 호출 방식으로 변환한 함수이다.
• void displayRecursive(Node* curr): 기존의 display() 함수를 순환 호출 방식으로 변환한 함수이다. void displaySup(const char* str = “List”) 에 의해 호출된다 (코드 참고).
• void insertRecursive(Node* curr, int newData): 객체(LinkedList)에서 pos 번째에 매개변수 n을 삽입(추가)하는 기존의 insert 함수와 다르게 data가 오름차순으로 노드가 정렬된 객체(LinkedList)에서 알맞는 자리에 newData의 값을 가진 새로운 노드(Node)를 삽입(insert)한다. 

• void clearRecursive(Node* curr): 객체(LinkedList)가 공백상태가 될 때까지 Node들을 삭제하는 기존의 clear() 함수를 순환 호출 방식으로 변환한 함수이다.
• void reverseRecursive(int start, int end): 객체(LinkedList)의 노드들의 data가 역순이 되도록 바꾸는 함수이다. 이 또한 순환 호출 방식으로 구현하라. 이때 노드들 자체의 순서를 바꿀 필요는 없고 노드의 data값을 바꾸어서 역순으로 만들어라.

• ** 만약 노드의 data를 바꾸는 방식이 아닌 노드 자체의 순서를 바꾸는 방식으로 void reverseRecursive2(int start, int end)를 추가 구현하는 경우에는 추후 중간 고사 시험 점수에 추가 5점을 부여한다.

 

※출력 화면

---

• 전체 코드

 

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
#include <string>
using namespace std;

inline void error(char* str) {
	fprintf(stderr, "%s\n", str);
	exit(1);
};

class Node {
	Node* link; // pointer to next node
	int		data; // data field of 'this' node

public:
	Node(int val = 0) : data(val), link(NULL) { }
	Node* getLink() { return link; }
	void setLink(Node* next) { link = next; }
	void display() { printf(" <%2d>", data); }
	int getData() { return data; }
	void setData(int newData) { data = newData; } // newly added function

	// insert new node (n) next to current node
	void insertNext(Node* n) {
		if (n != NULL) {
			n->link = link;
			link = n;
		}
	}

	// remove next node from current node
	Node* removeNext() {
		Node* removed = link;
		if (removed != NULL)
			link = removed->link;
		return removed;
	}
};

class LinkedList {
	Node	org;	// head node (not head pointer!)

public:
	LinkedList() : org(0) { }
	~LinkedList() { clearRecursive(getHead()); }

	Node* getHead() { return org.getLink(); }
	bool isEmpty() { return getHead() == NULL; }

	// return node in position 'pos' from the list
	Node* getEntry(int pos) {
		Node* n = &org;
		for (int i = -1; i < pos; i++, n = n->getLink())
			if (n == NULL) break;
		return n;
	}

	// insert new node (n) in position 'pos'
	void insert(int pos, Node* n) {
		Node* prev = getEntry(pos - 1);
		if (prev != NULL)
			prev->insertNext(n);
	}

	// remove a node in position 'pos'
	Node* remove(int pos) {
		Node* prev = getEntry(pos - 1);
		return prev->removeNext();
	}

	// display function that calls displayRecursive to print all data of nodes in the linked list
	void displaySup(const char* str = "List") {
		printf("%s", str);
		printf("[list size %2d] : ", sizeRecursive(getHead()));

		displayRecursive(getHead());
		printf("\n");
	}

	// 1. calculate size of linked list by recursion
	int sizeRecursive(Node* curr) {
		if (curr == NULL) return 0;
		return 1 + sizeRecursive(curr->getLink());
	}

	// 2. display data fields of nodes in the list by recursion
	void displayRecursive(Node* curr) {
		if (curr == NULL) return;
		curr->display();
		return displayRecursive(curr->getLink());
	}

	// 3. insert new node (n) in the right position by recursion
	void insertRecursive(Node* curr, int newData) {
		if (curr->getLink()->getData() > newData) {
			curr->insertNext(new Node(newData));
			return;
		}
		return insertRecursive(curr->getLink(), newData);
	}

	// 4. clear all nodes in the linked list by recursion
	void clearRecursive(Node* curr) {
		if (curr->getLink() == NULL) {
			remove(0);
			return;
		}
		remove(0);
		//delete remove(0) 왜 안됨?
		return clearRecursive(curr->getLink());
	}

	// 5. reverse data of all nodes in the linked list by recursion
	void reverseRecursive(int start, int end) {
		if (end == 0) return;
		Node* curr = getHead();
		Node* next = curr->getLink();
		for (int i = 0; i < end; i++, curr = curr->getLink(), next = next->getLink()) {
			int temp = curr->getData();
			curr->setData(next->getData());
			next->setData(temp);
		}
		return reverseRecursive(0, end - 1);
	}


	void reverseRecursive2(int start, int end) {
		if (end == 0) return;
		Node* curr = getHead(); //100
		Node* next = curr->getLink(); //90
		org.setLink(next);		//Head -> 90 : //노드가 항상 맨앞을 가르키기 위한 코드
		next->insertNext(curr);		//맨앞 노드들을 swap할때는 Head노드를 고려해야 하기때문에 반복문 밖에서 실행해 주었다. 

		for (int i = 0; i < end - 1; i++) {
			next->setLink(curr->getLink()); //90->80
			next = curr->getLink(); //80
			next->insertNext(curr); //90->100
		}

		return reverseRecursive2(0, end - 1);
	}
};

int main()
{
	LinkedList* list1 = new LinkedList();

	list1->insert(0, new Node(100));
	list1->insert(0, new Node(90));
	list1->insert(0, new Node(80));
	list1->insert(0, new Node(70));
	list1->insert(0, new Node(60));
	list1->insert(0, new Node(40));
	list1->insert(0, new Node(30));
	list1->insert(0, new Node(20));
	list1->insert(0, new Node(10));
	//cout << list1->sizeRecursive(list1->getHead());

	list1->displaySup("List1(        initial        )");
	list1->insertRecursive(list1->getHead(), 50);
	list1->displaySup("List1(      after insert     )");
	list1->reverseRecursive(0, list1->sizeRecursive(list1->getHead()) - 1);
	list1->displaySup("List1(     after reverse     )");
	list1->reverseRecursive2(0, list1->sizeRecursive(list1->getHead()) - 1);
	list1->displaySup("List1(     after reverse2    )");
	list1->clearRecursive(list1->getHead());
	list1->displaySup("List1(      after clear      )");

	return 0;
}

 

---

 

int sizeRecursive(Node* curr)
// 1. calculate size of linked list by recursion

int sizeRecursive(Node* curr) {
    if (curr == NULL) return 0;
    return 1 + sizeRecursive(curr->getLink());
}

현재의 노드가 NULL노드가 아니라면 return값에 1을 더하고 반환값이 정수형인 자기자신함수를 호출한다. 
헤드노드가 가르키고 있는 노드를 매게변수로 받으면 마지막 노드까지 차례대로 호출되면서 return값이 1씩 더해져 최종리턴값은 노드의 갯수가 된다.  

 

void displayRecursive(Node* curr)
// 2. display data fields of nodes in the list by recursion

void displayRecursive(Node* curr) {
    if (curr == NULL) return;
    curr->display();
    return displayRecursive(curr->getLink());
}

현재의 노드가 NULL노드가 아니라면 현재노드의 data를 출력하는 함수를 호출하고 return값은 현재노드가 가르키고 있는 노드를 전달해준다. 

 

void insertRecursive(Node* curr)
// 3. insert new node (n) in the right position by recursion

void insertRecursive(Node* curr, int newData) {
    if (curr->getLink()->getData() > newData) {
        curr->insertNext(new Node(newData));
        return;
    }
    return insertRecursive(curr->getLink(), newData);
}

이문제에서는 insertNext라는 함수를 사용할 것이기 때문에 if문을 설정해 줄때에는 현재의 노드의 데이터와 newData의 대소를 검사하는게 아닌 다음노드의 데이터와 newData를 검사해야 한다.  다음 노드가 newData보다 크다면 그 노드이전에 newData를 삽입한다. 
**이 코드는 0번째 노드를 검사하지 않기때문에 추가하는 노드가 맨 앞에 와야하는 경우에는 사용할 수 없다. 

 

 

 

void clearRecursive(Node* curr)
// 4. clear all nodes in the linked list by recursion

void clearRecursive(Node* curr) {
    if (curr->getLink() == NULL) {
        remove(0);
        return;
    }
    remove(0);
    //delete remove(0) 
    return clearRecursive(curr->getLink());
}

**원래라면 remove(0)함수가 반환하는 0번째 노드를delete해줘야 하지만 그 과정에서 생기는 오류를 해결하지 못하였다... 때문에 이 코드는 메모리 누수가 생긴다.ㅜㅜ

remove()의 문제가 아니라 이미 메모리해제된 노드를 가지고 다음 순환함수의 매개변수로 사용할려고 한 것이 문제가 된 것이였다. 
*20230529 수정

void clearRecursive(Node* curr) {
    if (curr->getLink() == NULL) {
        remove(0);
        return;
    }
    Node* next = curr->getLink();
    delete remove(0);
    return clearRecursive(next);
}

next노드 포인터를 만들어서 해결

 

void clearRecursive(Node* curr)
// 5. reverse data of all nodes in the linked list by recursion

void reverseRecursive(int start, int end) {
		if (end == 0) return;
		Node* curr = getHead();
		Node* next = curr->getLink();
		for (int i = 0; i < end; i++, curr = curr->getLink(), next = next->getLink()) {
			int temp = curr->getData();
			curr->setData(next->getData());
			next->setData(temp);
		}
		return reverseRecursive(0, end - 1);
	}

내가 짠 reverse함수의 알고리즘은 1번재 오는 노드를 swap을 이용해 맨 뒤로 보내는 과정을 반복하는 것이다. 
그러기 위해 for문을 이미 정렬된 맨 마지막 노드를 제외하기 위해 종료 조건을 i < end; 라고 설정해 주었다. 
end값을 하나씩 줄이기 위해 순환함수의 매개변수로 end를 하나씩 빼 주었다. 
for문 안에서는 6주차 과제와 비슷하게 Data를 swap해 주었다. 
첫번째 for문 실행 : 20 10 30 40 50 60 70 80 90 100
두번째 for문 실행 : 20 30 10 40 50 60 70 80 90 100
세번째 for문 실행 : 20 30 40 10 50 60 70 80 90 100

첫번째 함수를 실행 : 20 30 40 50 60 70 80 90 / 10 
두번재 함수를 실행: 30 40 50 60 70 80 90 / 20 10 
.
.
.
마지막 함수를 실행:  / 100 90 80 70 60 50 40 30 20 10 

 

void clearRecursive2(Node* curr)
// 5. reverse all nodes in the linked list by recursion

void reverseRecursive2(int start, int end) {
		if (end == 0) return;
		Node* curr = getHead(); //100
		Node* next = curr->getLink(); //90
		org.setLink(next);		//Head -> 90 : //노드가 항상 맨앞을 가르키기 위한 코드
		next->insertNext(curr);		//맨앞 노드들을 swap할때는 Head노드를 고려해야 하기때문에 반복문 밖에서 실행해 주었다. 

		for (int i = 0; i < end - 1; i++) {
			next->setLink(curr->getLink()); //90->80
			next = curr->getLink(); //80
			next->insertNext(curr); //90->100
		}

		return reverseRecursive2(0, end - 1);
	}

대략적인 알고리즘은  reverseRecursive함수와 똑같고 달라진것은 노드 전체를 바꾸는 것 뿐이다. 
 Head노드를 항상 맨앞을 가리키는 노드로 유지하기 위해서 for문 밖에서 맨 처음 swap을 실행해주었다. 
org.setLink(next);  :  Head -> 90 -> 80 -> 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10
next->insetNext(curr);  :  Head -> 90 -> 100 -> 80 -> 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10

for문 안에서는
 (1) next가 가르키는 다음 노드를 이전 노드로 바꾸고 : Head -> 90 -> 80 -> 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10
 (2) 포인터 next를 현재노드가 가르키고 있는 노드(80)를 가르키게 함 
 (3) 바뀐 next뒤에 현재노드를 추가한다. : Head -> 90 -> 80 -> 100 -> 70 -> 60 -> 50 -> 40 -> 30 -> 20 -> 10

이 과정을 end가 0이 될때 까지 반복하면 노드가 하나씩 뒤로 정렬되면서 뒤집어진다. 


**solution 코드
내 코드는 순환함수의 특징을 잘 사용하지 못한 코드같다.  함수가 호출되면서 스택에 쌓이는 것을 활용해 밑의 내용과 같은 코들르 작성할 수있다.. 
[c++] reverseRecursive (tistory.com)

[c++] reverseRecursive

 

 

 

 

배운 점, 느낀 점

과제를 풀수록 점점 코드가 복잡해지는 것을 느낀다 

예외를 놓치거나 메모리를 관리하는 것에 있어서 더 섬세하게 신경써야 겠다고 생각했다.