자료구조 6주차 : 포인터(동적메모리)와 연결 리스트
교수님이 제시해주신 스켈레톤 코드를 채워넣는 과제였다.
※문제설명
- 우리에게 Node 클래스와 LinkedList 클래스가 주어졌다
- 기본적인 이론 지식을 기반으로 Node와 LinkedList의 기본 연산들을 구현하라
- 이와 더불어 추가 적인 연산을 하는 멤버 함수들인 reverse()와 mergeTwoLists()를 구현하라.
※구현할 코드
Node 클래스
⦁ Node* 형 link (기본 제공)
⦁ int 형data (기본 제공)
⦁ 기본 생성자
⦁ Node* getLink(): 객체(Node)의 link 변수가 point하는 객체(메모리 주소)를 반환한다.
⦁ void setLink(Node* next): 객체(Node)의 link를 매개변수 next로 설정한다.
⦁ void display(): 객체(Node)의 data를 출력한다. (예: <10> / 맨 마지막 출력화면을 참고).
⦁ int getData(): 객체(Node)의 data를 반환한다.
⦁ void insertNext(Node* n): 매개변수 n을 객체(Node)의 다음 노드(link)로 설정한다.
⦁ Node* removeNext(): 객체(Node)의 다음 노드(link)를 삭제한다.
OutputPrintStack 클래스
⦁ Node형 org (기본 제공)
⦁ 기본 생성자 및 소멸자
⦁ void clear(): 객체(LinkedList)가 공백상태가 될 때까지 Node들을 삭제한다.
⦁ Node* getHead(): 제일 처음 노드를 반환한다.
⦁ bool isEmpty(): 객체(LinkedList)가 공백상태인지 확인한다. 공백상태이면 true 아니면 false를 리턴한다.
⦁ Node* getEntry(int pos): 객체(LinkedList)에서 pos번째 Node를 반환한다.
⦁ void insert(int pos, Node* n): 객체(LinkedList)에서 pos 번째에 매개변수 n을 삽입(추가)한다.
⦁ Node* remove(int pos): 객체(LinkedList)에서 pos번째 Node를 삭제한다.
⦁ int size(): 객체(LinkedList)의 사이즈(총 Node 수)를 반환한다.
⦁ void display(const char* str = “List” ): 객체(LinkedList)의 Node데이터를 출력한다. (맨 마지막 출력화면을 참고).
⦁ void reverse(): 객체(LinkedList)를 역순으로 바꾼다.
⦁ LinkedList* mergeTwoLists(LinkedList* list2): 객체(LinkedList)와 매개변수 list2의 Node들을 순회하며 노드의 data가 큰 순서대로 정렬된 별도의 LinkedList를 반환한다
※출력 화면
- 전체 코드
//Visual Studio: 프로젝트 -> 속성 -> C/C++ -> 언어 -> 준수모드: 아니요(/permissive)
#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() { cout << " <" << data << ">"; }
int getData() { return data; }
void setData(int n) { data = n; } //Data swap을 위해 정의한 함수
// 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() { clear(); }
void clear() { while (!isEmpty()) delete remove(0); }
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();
}
// return size of list
int size() {
int count = 0;
for (Node* p = getHead(); p != NULL; p = p->getLink()) count++;
return count;
}
// display data fields of nodes in the list
void display(const char* str = "List") {
cout << str;
cout << "[list size " << size() << "] : ";
for (Node* p = getHead(); p != NULL; p = p->getLink()) p->display();
cout << endl;
}
// reverse list
void reverse() {
Node prev(NULL), temp(NULL), curr(NULL);
curr.setLink(getHead()); //현재노드를 head가 가르키는 곳으로 설정
while (curr.getLink()) {
temp.setLink(curr.getLink()->getLink()); //temp = curr->link
curr.getLink()->setLink(prev.getLink()); //curr->link = prev;
prev.setLink(curr.getLink()); //prev = curr
curr.setLink(temp.getLink());
}
org.setLink(prev.getLink());
}
void DataSwap(Node* curr, Node* next) {
int temp = curr->getData();
curr->setData(next->getData());
next->setData(temp);
}
// return new list that have data fields of two lists in descending order
LinkedList* mergeTwoLists(LinkedList* list2) {
LinkedList* list3 = new LinkedList();
for (int i = 0; i < size(); i++) {
list3->insert(i, new Node(getEntry(i)->getData()));
}
for (int i = size(), j = 0; j < list2->size(); i++, j++) {
list3->insert(i, new Node(list2->getEntry(j)->getData()));
}
//내림차순 버블정렬
for (int i = 0; i < list3->size(); i++) {
Node* next = list3->getHead()->getLink();
for (Node* q = list3->getHead(); next != NULL; q = q->getLink(), next = next->getLink()) {
if (q->getData() < next->getData()) {
DataSwap(q, next);
}
}
}
return list3;
}
};
int main()
{
LinkedList* list1 = new LinkedList(), * list2 = new LinkedList();
LinkedList* list3;
list1->insert(0, new Node(80));
list1->insert(0, new Node(50));
list1->insert(0, new Node(40));
list1->insert(0, new Node(10));
list1->display("List1( before )");
list1->reverse();
list1->display("List1(after reverse)");
list2->insert(0, new Node(70));
list2->insert(1, new Node(60));
list2->insert(2, new Node(30));
list2->insert(3, new Node(20));
list2->display("List2( now )");
list3 = list1->mergeTwoLists(list2);
list3->display("List3( List1+List2 )");
list1->clear();
list2->clear();
list1->display("List1( end )");
list2->display("List2( end )");
return 0;
}
class Node { }
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() { cout << " <" << data << ">"; } int getData() { return data; } void setData(int n) { data = n; } //Data swap을 위해 정의한 함수 // 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 { }
class LinkedList { Node org; // head node (not head pointer!) public: LinkedList() : org(0) { } ~LinkedList() { clear(); } void clear() { while (!isEmpty()) delete remove(0); } 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(); } // return size of list int size() { int count = 0; for (Node* p = getHead(); p != NULL; p = p->getLink()) count++; return count; } // display data fields of nodes in the list void display(const char* str = "List") { cout << str; cout << "[list size " << size() << "] : "; for (Node* p = getHead(); p != NULL; p = p->getLink()) p->display(); cout << endl; } // reverse list void reverse() { Node prev(NULL), temp(NULL), curr(NULL); curr.setLink(getHead()); //현재노드를 head가 가르키는 곳으로 설정 while (curr.getLink()) { temp.setLink(curr.getLink()->getLink()); //temp = curr->link curr.getLink()->setLink(prev.getLink()); //curr->link = prev; prev.setLink(curr.getLink()); //prev = curr curr.setLink(temp.getLink()); } org.setLink(prev.getLink()); } void DataSwap(Node* curr, Node* next) { int temp = curr->getData(); curr->setData(next->getData()); next->setData(temp); } // return new list that have data fields of two lists in descending order LinkedList* mergeTwoLists(LinkedList* list2) { LinkedList* list3 = new LinkedList(); for (int i = 0; i < size(); i++) { list3->insert(i, new Node(getEntry(i)->getData())); } for (int i = size(), j = 0; j < list2->size(); i++, j++) { list3->insert(i, new Node(list2->getEntry(j)->getData())); } //내림차순 버블정렬 for (int i = 0; i < list3->size(); i++) { Node* next = list3->getHead()->getLink(); for (Node* q = list3->getHead(); next != NULL; q = q->getLink(), next = next->getLink()) { if (q->getData() < next->getData()) { DataSwap(q, next); } } } return list3; } };
-reverse() :void reverse() { Node prev(NULL), temp(NULL), curr(NULL); curr.setLink(getHead()); //현재노드를 head가 가르키는 곳으로 설정 while (curr.getLink()) { temp.setLink(curr.getLink()->getLink()); //temp = curr->link curr.getLink()->setLink(prev.getLink()); //curr->link = prev; prev.setLink(curr.getLink()); //prev = curr curr.setLink(temp.getLink()); } org.setLink(prev.getLink()); }
단순연결리스트를 역순으로 바꾸기 위해서는 노드를 순서대로 탐색하면서 각 노드의 다음 노드를 가르키는 포인터를 현재노드의 이전 노드를 가르키도록 바꿔주어야 한다.
그러기 위해 이전노드를 저장하는 previous, 현재노드를 저장하는 current, 다음노드를 저장하는 temp변수를 선언해주었다. data영역은 NULL로 설정해주었다.
`반복문을 시작하기 전에 현재노드를 head()로 지정
`현재노드가 끝이 아닐때 까지 while문 반복
(1) 현재노드의 다음노드를 temp변수로 지정
(2) 현재노드의 다음노드를 이전노드를 가르키도록 변경
(3) prev변수를 현재노드로 업데이트한다.
(4) 현재노드를 temp로 업데이트한다.
`반복문이 끝난 뒤 업데이트 된 head를 반환한다.
`노드를 3~4개 정도 그려보면 이해가 쉽다.
-mergeTwoLists() :main함수를 보면 list1객체 안의 함수를 호출하고 있다. 그리고 매개변수로 받는 list2를 list3으로 반환해야한다.
그래서 일단 list1과 list2를 list3으로 합쳐주고 버블정렬을 사용하였다.LinkedList* mergeTwoLists(LinkedList* list2) { LinkedList* list3 = new LinkedList(); for (int i = 0; i < size(); i++) { list3->insert(i, new Node(getEntry(i)->getData())); } for (int i = size(), j = 0; j < list2->size(); i++, j++) { list3->insert(i, new Node(list2->getEntry(j)->getData())); } //버블정렬 알고리즘() {...} } return list3; }(1)반환할 list3의 포인터를 선언하고 클래스를 동적할당하였다.
(2)list1, list2의 Data값을 복사하여 Node를 만드는 for문을 각각 만들었다. 두번째 for문에서는 매개변수로 받은 포인터를 활용해서 list2에 접근해야 한다.
내림차순 버블정렬: (시간복잡도가 O(n^2)이지만 교수님께서 제시하신 노드의 수가 많지않아서 간단할 알고리즘을 선택하였다.)//내림차순 버블정렬 for (int i = 0; i < list3->size(); i++) { Node* next = list3->getHead()->getLink(); for (Node* q = list3->getHead(); next != NULL; q = q->getLink(), next = next->getLink()) { if (q->getData() < next->getData()) { DataSwap(q, next); } } }첫번째 for문을 수행할 때마다 맨 끝부터 정렬된다.
(1)두번째 반복문을 실행하기 전에 next노드를 list3의 두번째 노드를 가르키도록 초기화한다.
(2)현재노드 q와 next노드의 데이터 값을 비교하고, Swap함수를 이용해 정렬한다.
(3)q와 next노드를 다음노드로 이동한다.
Swap() :void DataSwap(Node* curr, Node* next) { int temp = curr->getData(); curr->setData(next->getData()); next->setData(temp); }노드의 순서를 바꿔주는 Swap함수가 아니라 데이터의 값만 바꿔주는 Swap함수를 구현하였다.
변경해야하는 데이터가 많아진다면 이 방법은 바람직하지 않지만 이 문제에서는 복잡하게 Link를 바꿔줄 필요없이 원하는 결과를 얻을 수 있다.
*replace() :void replace(int pos, NodeToList* n) { NodeToList* prev = getEntry(pos - 1); if(prev != NULL) { delete prev->removeNext(); prev->insertNext(n); } }리스트의 pos번째 노드를 다른 노드로 교체하는 함수
(1)현재노드르 삭제한다. (=이전노드가 다음노드를 가르킴)
(2)다음노드의 뒤에 n을 삽입한다.
'학교생활!' 카테고리의 다른 글
| [230520] 고급C++프로그래밍: 과제3 (0) | 2023.05.31 |
|---|---|
| [230503] 자료구조 과제5: 순환(recursion) (0) | 2023.05.07 |
| [230325]컴퓨터 구조: Bit-Level Representations and Manipulations in C (0) | 2023.04.07 |
| [230402]고급C++프로그래밍: 구조체 과제 (0) | 2023.04.07 |
| [230330]자료구조 과제3: Print (0) | 2023.04.02 |
