4번문제 ADT
- void add(const E& data); 멤버 함수는 string 타입 name과 int 타입 score라는 멤버 변수를 가진 GameEntry라는 클래스와 int, double 등 일반 자료형에 대해서 모두 내림차순 정렬할 수 있어야 한다.
- GameEntry 클래스는 선언 시 생성자를 통해 멤버 변수를 초기화한다.
- 이전 3번문제와 마찬가지로 head와 tail을 사용한다. -> 동일하게 데이터를 갖지않는 sentinel nodes를 사용하려고 했었다. 근데 sentinel node의 멤버 변수들에 대해 초기화를 시켜주지 못해서(data가 없어야하는데..) 이와 같은 문제로 MacOS에선 되는데, WSL에선 되지 않았다.....
main 함수(제공)
// 아래와 같이 main함수에서 여러분이 작성한 list.h와 gameentry.h 파일을
// include 하여 주어진 동작을 실행하게 됩니다.
// *** 주의! 아래의 내용을 변경할 경우 오답처리될 수 있습니다. **
#include <iostream>
#include <string>
#include <sstream>
#include "list.h"
#include "gameentry.h"
using namespace std;
void handleInteger()
{
int maxEntry;
cin >> maxEntry;
LinkedList<int> list(maxEntry);
int score;
while (true) {
cin >> score;
if (score < 0)
break;
list.add(score);
}
list.printReverse();
cout << list.length() << endl;
}
void handleGameEntry()
{
int maxEntry;
cin >> maxEntry;
LinkedList<GameEntry> list(maxEntry);
string name;
int score;
while (true) {
cin >> name;
if (name == "quit")
{
break;
}
cin >> score;
list.add(GameEntry(name, score));
}
list.print();
cout << list.length() << endl;
}
int main(void)
{
handleInteger();
handleGameEntry();
return 0;
}sentinel node 사용시 해결하지 못한 점
새로운 Node 생성 시 data와 prev, next를 초기화해주는데,
그럼 head와 tail에도 data를 넣어야한다.
-> 그럼 head와 tail을 위한 생성자가 따로 있던가 LinkedList의 생성자에서 head와 tail을 따로 만들어주고 초기화까지 하면?..
-> 하다가 그냥 sentinel node 사용하지 않는 것으로 노선 변경
list.h
head, tail 에도 data 사용
#ifndef ASSIGNMENT_LIST_H
#define ASSIGNMENT_LIST_H
template <typename E>
class LinkedList;
template <typename E>
class Node {
private:
E data;
Node<E>* next;
Node<E>* prev;
friend class LinkedList<E>;
public:
Node(const E& _data) : data(_data), next(nullptr), prev(nullptr) {}
};template <typename E>를 통해 임의의 자료형 E에 대해 모두 처리할 수 있다. GameEntry 클래스의 인스턴스 또한 처리가 가능하다.
Node의 생성자에서 data를 넣어주고, next, prev를 nullptr로 초기화해준다.
이러지 않으면 끊임없이 자기참조가 일어나더라.
template <typename E>
class LinkedList {
public:
LinkedList(int max) : maxEntry(max) {}
void add(const E& data);
int length();
void print();
void printReverse();
private:
int maxEntry;
int dataCount = 0;
Node<E>* head;
Node<E>* tail;
};int dataCount는 ADT에 없었지만,
length() 멤버 함수 + maxEntry 기능 구현의 편의성을 위해 넣었다.
template<typename E>
void LinkedList<E>::add(const E &data) {
Node<E>* newNode = new Node<E>(data);
if(dataCount == 0) {
head = tail = newNode;
newNode->next = tail;
newNode->prev = head;
dataCount++;
} else if (dataCount ==1){
if(head->data >= newNode->data){
head->next = newNode;
tail = newNode;
tail->prev = head;
tail->next = nullptr;
}else{
newNode->next = tail;
head = newNode;
tail->prev = newNode;
head->prev = nullptr;
}
dataCount++;
}else{
Node<E> *currentNode = head; // 첫 번째 데이터 노드부터 시작
while (currentNode != nullptr) {
if (newNode->data >= currentNode->data) {
if (currentNode == head) {
// 새로운 데이터가 큰 경우
newNode->next = head;
head->prev = newNode;
newNode->prev = nullptr;
head = newNode;
}else {
// 중간에 삽입하는 경우
newNode->next = currentNode;
newNode->prev = currentNode->prev;
currentNode->prev->next = newNode;
currentNode->prev = newNode;
}
dataCount++;
break;
}
//끝까지 감
if (currentNode == tail) {
tail -> next = newNode;
newNode->prev = tail;
tail = newNode;
dataCount++;
break;
}
currentNode = currentNode->next;
}
}
if(dataCount > maxEntry) {
// 리스트가 가득 찬 경우 마지막 노드 제거
Node<E>* lastNode = tail;
tail = lastNode->prev;
tail->next = nullptr;
// delete lastNode;
dataCount--;
}
}가장 중요하고, 헷갈렸던 add 함수 부분.
일단 template<>를 통해 template specialization을 적용하였다.
노드를 넣는 경우의 수를 잘 생각해봐야한다.
maxEntry 기능을 구현하기 위해 일단 추가한 후 tail을 마지막에 수정해줬다(끊어줬다).
template <typename E>
int LinkedList<E>::length() {
return dataCount;
}
template <typename E>
void LinkedList<E>::print() {
Node<E>* currentNode = head;
while (currentNode != nullptr) {
std::cout << currentNode->data << " ";
currentNode = currentNode->next;
}
std::cout << std::endl;
}
template <typename E>
void LinkedList<E>::printReverse() {
Node<E>* currentNode = tail;
while (currentNode != nullptr) {
std::cout << currentNode->data << " ";
currentNode = currentNode->prev;
}
std::cout << std::endl;
}
#endif //ASSIGNMENT_LIST_H
gameentry.h
연산자 오버로딩 사용
class GameEntry {
public:
GameEntry(const std::string &_name, int _score);
std::string name;
int score;
friend std::ostream& operator<<(std::ostream& os, const GameEntry& gameEntry);
friend bool operator>=(const GameEntry& gameEntry1, const GameEntry& gameEntry2);
};
GameEntry::GameEntry(const std::string &_name, int _score) {
name = _name;
score = _score;
}GameEntry 클래스의 생성자와 friend 키워드
매개변수와 멤버 변수의 이름을 _로 구분했다.
friend 키워드를 사용해야 오버로딩에 대한 준비가 끝난다.
bool operator>=(const GameEntry& gameEntry1,const GameEntry& gameEntry2){
if(gameEntry1.score == gameEntry2.score){
if(gameEntry1.name >= gameEntry2.name) {
return true;
} else{
return false;
}
}else if(gameEntry1.score >= gameEntry2.score){
return true;
}else{
return false;
}
}>= 연산자 오버로딩
>= 연산자의 인수로 GameEntry 클래스의 자료형이 들어왔을 때에만 동작한다.
*int, double 등 다른 자료형에서는 동작하지 않는다.
이름 또한 내림차순으로 정렬해야하는데,
C++에서는 기본 비교 연산자가 문자열 비교도 해준다.
std::ostream& operator<<(std::ostream& os, const GameEntry& gameEntry)
{
os << "[" << gameEntry.name << "]" << gameEntry.score;
return os;
}
LinkedList의 멤버함수 print()와 printReverse()에서 정렬된 노드의 data를 하나씩 출력할 때
연산자 <<를 사용한다. 이때 <<를 GameEntry 클래스 자료형에 대해서만
"[이름] 점수" 형태로 출력하도록 오버로딩 해준다.
후기
sentinel 노드를 사용하다가 애를 많이 먹었는데, tail의 next가 순환참조가 일어났었다.
왜 일어났는지 알아보고, sentinel node를 사용해서 못했던 부분을 더 해봐야겠다...
근데 사용하지 않으니 일단 더 쉽고 빠르게 되긴 했다.
교수님 교안에서는 왜 sentinel node를 사용한 예시를 주셨던 걸까?
#sentinel node 사용의 장점?
