[자료구조/Week 6] HW06

문제

1. 클래스 설계

   노드 클래스를 단순하게 만들고 연결 관계를 포함한 노드 처리 연산을 리스트 클래스에서 구현하는 방법과 노드 클래스에서 가능한 많은 기능을 구현하고 리스트 클래스에서 이들을 사용하는 방법의 차이점은 이렇게 정리할 수 있다.

   첫 번째 방법은 리스트 클래스의 구현을 간단하게 할 수 있다. 노드 클래스는 단순해져서 가독성이 높아지며, 노드 처리 연산의 구현에 대한 책임이 리스트 클래스로 넘어가므로 유지보수성이 좋아진다. 또한, 리스트 클래스에 다양한 기능을 추가하기도 쉬우므로, 유연성이 높아진다는 장점이 있다. 반면에 두 번째 방법은, 노드 클래스에서 다양한 기능을 지원할 수 있다는 점에서 첫 번째 방법과 다르다. 이는 노드 클래스의 객체를 만들 때 필요한 정보가 적어지므로 객체 생성에 대한 부담이 줄어들고, 객체 간의 연결 관계를 쉽게 구현할 수 있다. 또한, 리스트 클래스의 복잡도를 줄일 수 있으므로 성능이 향상될 수 있다는 장점이 있다.

   나는 두 번째 방법을 선택하여 노드 클래스와 리스트 클래스를 설계하고 싶다. 리스트 클래스를 간결하고 복잡하지 않게 만들고 싶기 때문이다. 노드 클래스 설계를 아직 많이 시도해보지는 않았지만 자료구조의 지난 과제를 했던 경험을 바탕으로 클래스에서 연산과 같은 기능을 미리 구현해 두면 그 클래스를 이용할 때 편의성을 느꼈기 때문이다.

 

2. 교재 연습문제 1, 2

1. 단순 연결 리스트에 정수가 저장되어 있다. 단순 연결 리스트의 모든 데이터 값을 더한 합을 출력하는 프로그램을 작성하라.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        this->link = NULL;
    }
};

class LinkedList {
public:
    Node* head;
    LinkedList() {
        this->head = NULL;
    }
    void addNode(int data) {
        Node* new_node = new Node(data);
        if (this->head == NULL) {
            this->head = new_node;
            return;
        }
        Node* curr = this->head;
        while (curr->link != NULL) {
            curr = curr->link;
        }
        curr->link = new_node;
    }
    int sumList() {
        int sum = 0;
        Node* curr = this->head;
        while (curr != NULL) {
            sum += curr->data;
            curr = curr->link;
        }
        return sum;
    }
};

int main() {
    LinkedList list;
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.addNode(4);
    cout << "모든 데이터의 총합: " << list.sumList() << endl;
    return 0;
}

 

2. 단순 연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수를 계산하는 함수를 작성하라.

#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* link;
    Node(int data) {
        this->data = data;
        this->link = NULL;
    }
};

class LinkedList {
public:
    Node* head;
    LinkedList() {
        this->head = NULL;
    }
    void addNode(int data) {
        Node* new_node = new Node(data);
        if (this->head == NULL) {
            this->head = new_node;
            return;
        }
        Node* curr = this->head;
        while (curr->link != NULL) {
            curr = curr->link;
        }
        curr->link = new_node;
    }
    int countNodes(int target) {
        int count = 0;
        Node* curr = this->head;
        while (curr != NULL) {
            if (curr->data == target) {
                count++;
            }
            curr = curr->link;
        }
        return count;
    }
};

int main() {
    LinkedList list;
    list.addNode(1);
    list.addNode(2);
    list.addNode(3);
    list.addNode(2);
    list.addNode(4);
    
    int n;
    cout << "찾고자 하는 데이터: ";
    cin >> n;
    cout << "이 데이터 값을 가진 노드의 개수: " << list.countNodes(n) << endl;
    return 0;
}