[230503] 자료구조 과제5: 순환(recursion)
자료구조 7주차 : 순환
과제4의 Node클래스와 LinkedList클래스를 바탕으로 추가함수를 구현하는 과제
[20230414] 자료구조 과제4: LinkedList클래스 (tistory.com)
[20230414] 자료구조 과제4: LinkedList클래스
자료구조 6주차 : 포인터(동적메모리)와 연결 리스트 교수님이 제시해주신 스켈레톤 코드를 채워넣는 과제였다. ※문제설명 우리에게 Node 클래스와 LinkedList 클래스가 주어졌다 기본적인 이론 지
daybreakfrontline21.tistory.com
※문제설명
- 지난 과제에서 구현한 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 recursionint 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 recursionvoid 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 recursionvoid 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 recursionvoid 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 recursionvoid 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 recursionvoid 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
void reverseRecursive2(int start, int end) { if (start >= end) return; Node* prev = getEntry(start); Node* curr = prev->getLink(); Node* next = curr->getLink(); reverseRecursive2(start + 1, end); if (next == NULL) { Node* head = getHead(); org.setLink(curr
daybreakfrontline21.tistory.com
배운 점, 느낀 점
과제를 풀수록 점점 코드가 복잡해지는 것을 느낀다
예외를 놓치거나 메모리를 관리하는 것에 있어서 더 섬세하게 신경써야 겠다고 생각했다.