HW6-리스트 연습문제(chapter6)

1. 클래스 설계 & struct

struct Node {

    int data;

    Node* link;

}; 와 같이 Node 클래스를 설계를 설계하는 방법이 있는데 나는 class로 Node를 구현하는 것이 더 좋다고 생각한다. struct는 더 간단하고 직관적으로 Node객체나 연산 등을 수행할 수 있지만 클래스에서 제공하는 private, protected, public 등의 접근제어지시자를 사용할 수 없기 때문이다. 즉 int data나 Node *link와 같은 데이터 멤버에 대한 외부의 접근을 막는 것을 방지할 수 없다는 단점이 존재해서 사용시, 그 데이터멤버가 변경될 수 있다는 위험이 있다고 생각한다. 따라서 class로 설계하는 것이 객체지향 프로그래밍의 관점에서 더 유용하다고 생각한다. 또한 노드 클래스에서 많은 기능을 구현하고, 리스트 클래스에서 이들을 사용함으로써 리스트 클래스의 복잡도를 줄이는 방법을 선호한다. 이는 리스트 클래스를 사용하는 임의의 사용자가 간단한 인터페이스만을 사용할 수 있도록 할 수 있기 때문이다. 즉 노드 클래스에 변경된 내용이 있더라도 사용자가 기존과 동일한 방법으로 사용할 수 있기 때문에 (간단) 효율적이라고 생각한다.

2. 연습문제 1, 2

#pragma once
#include <iostream>
class Node {
	Node* link;//다음 노드를 가리키는 포인터 변수
	int data;//노드의 데이터 필드
public:
    Node(int val = 0) :data(val), link(NULL) {}
    int getdata() { return data; }
    Node* getLink() { return link; }
    void setLink(Node* next) {
        link = next;
    }
    void display() { printf(" <%2d>", data); }
    bool hasData(int val) {
        return data == val;
    }

    void insertNext(Node* n) {
        if (n != NULL) {
            n->link = link;//노드 n의 링크필드가 이전노드 link가 가리키는 후속노드를 가리키게함
            link = n;//이전노드 link는 노드n을 가리키게 함
        }
    }
    Node* removeNext() {
        Node* removed = link;//이전노드의 주소를 removed변수에 복사
        if (removed != NULL)
            link = removed->link;//이전노드 링크가 removed변수(이전노드가 원래 가졌던 링크필드)가 그 후속노드를 가리키게 함
        return removed;//삭제된 removed노드 반환
    }
};

#include <iostream>
#include "Node.h"
using namespace std;
class LinkedList {
	Node org;//헤드노드
public:
	LinkedList() :org(0) {}
	~LinkedList() { clear(); }
	void clear() { while (!isempty()) delete remove(0); }
	Node* gethead() { return org.getLink(); }
	bool isempty() { return gethead() == NULL; }
	Node* getentry(int pos) {//pos번째 항목을 반환
		Node* n = &org;
		for (int i = -1; i < pos; i++, n = n->getLink()) {//i=-1부터 시작해서 pos전까지 n노드의 다음노드링크들을 가져오기
			if (n == NULL) break;
		}
		return n;
	}
	void insert(int pos, Node* n) { //pos위치에 항목 삽입
		Node* prev = getentry(pos - 1);
		if (prev != NULL) prev->insertNext(n);
	}
	Node* remove(int pos) {//pos위치 항목 삭제
		Node* prev = getentry(pos - 1);//getentry로 pos위치의 선행노드 가져오기
		return prev->removeNext();//선행노드의 다음 노드 삭제하기
	}
	Node* find(int val) {
		for (Node* p = gethead(); p != NULL; p = p->getLink()) {
			if (p->hasData(val)) return p;
		}
		return NULL;
	}
	void replace(int pos, Node* n) {//pos위치의 노드를 다른 노드n으로 교체
		Node* prev = getentry(pos - 1);
		if (prev != NULL) {
			delete prev->removeNext();
			prev->insertNext(n);
		}
	}
	int size() {
		int count = 0;
		for (Node* p = gethead(); p != NULL; p = p->getLink()) {
			count++;
		}
		return count;
	}
	void sum() { //단순 연결 리스트의 모든 데이터 값을 더한 합
		int add = 0;
		cout << "전체 항목의 합 = ";
		for (Node* p = gethead(); p != NULL; p = p->getLink())
			add += p->getdata();
		cout << add << endl;
	}
	int count(int val) {//단순 연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수
		int cnt = 0;
		for (Node* p = gethead(); p != NULL; p = p->getLink())
			if (p->hasData(val))//val이라는 값을 p가 가진다면 노드 개수 cnt를 증가
				cnt++;
		return cnt; 
	}
	void display() {
		cout << "전체 항목의 수=" << size() << endl;
		for (Node* p = gethead(); p != NULL; p = p->getLink()) {
			p->display();
		}
		cout << "\n";
	}
};

#include "LinkedList.h"
#include <iostream>
int main() {
    LinkedList list;
    list.insert(0, new Node(10));
    list.insert(0, new Node(20));
    list.insert(1, new Node(30));//20 30 10
    list.insert(list.size(), new Node(40));//20 30 10 40
    list.insert(2, new Node(50));//20 30 50 10 40
    list.display();
    list.sum();
    cout << "리스트에서 특정값 50을 갖는 노드의 수: " << list.count(50) << endl;
    list.remove(2);//20 30 10 40
    list.remove(list.size() - 1);//20 30 10
    list.remove(0);//30 10
    list.replace(1, new Node(90));//30 90
    list.display();
    cout << "리스트에서 특정값 50을 갖는 노드의 수: " << list.count(50) << endl;
    list.clear();
    list.display();
}