HW06
문제1. 클래스 설계
-
강의 자료 16쪽을 보면 단순 연결 리스트에 사용하는 Node 클래스가 있습니다. 교재 232쪽을 보면 클래스 설계에 대해 저자가 의견을 서술하였습니다.
-
이와 다른 방법으로, 아래와 같이 단순한 노드 클래스, 또는 구조체를 선호하기도 합니다.
struct Node {
int data;
Node* link;
};- 두 방법의 차이점을 생각하고, 어떤 방식의 설계하고 싶은지 선택하여 이유를 함께 서술하세요.
Note. 지금 선택하는 방법은 공부하며 언제든 바뀔 수 있습니다. 정답이 있지 않으니 이유를 충분히 서술해 보세요.
답)
노드 클래스와 구조체의 특징을 각각 살펴보면,
노드 클래스는 data field와 link field를 private인 멤버 변수로 가지게 된다.
그러므로 클래스 외부에서 직접 접근할 수 없다. 대신 멤버함수로 간접적으로 접근 가능하다.
구조체는 기본적으로 public으로 선언되기 때문에 data field와 link field 둘 다 외부에서 직접 접근이 가능하다. 하지만 생성자와 소멸자가 없다는 단점이 있다.
둘 중의 한 방법을 사용한다면 나는 구조체를 사용할 것 같다.
물론 클래스를 쓰게 된다면 유지보수가 쉽고 코드를 재사용할 때 편하겠지만, 아직 초보자인 나로써는 정보를 하나의 구조체로 묶어서 보는 것이 더 가독성이 좋게 느껴지기때문이다. 그리고 구조체를 사용하면 쉬운 접근으로 코드가 더 간결해진다는 게 큰 장점이라고 생각된다.
2. 연습문제 1, 2
1. 단순 연결 리스트에 정수가 저장되어 있다. 단순 연결 리스트의 모든 데이터 값을 더한 합을 출력하는 프로그램을 작성하라.
풀이)
int main()
{
LinkedList list; //연결리스트의 객체 list 선언
int n; // 노드 전체 갯수를 담을 변수 n 선언
std::cout << "노드의 전체 갯수를 입력해주세요 : ";
std::cin >> n; //n에 저장
for (int i = 0; i < n; i++) { //노드의 갯수만큼 데이터 값 입력받기
int data; //데이터를 담을 변수 선언
std::cout << i+1 << "번 노드의 데이터 값을 입력해주세요 : ";
std::cin >> data; //data에 저장
list.insert(i, new Node(data)); //연결리스트의 새로운 노드 생성
}
int sum = 0; //합계를 저장할 변수 sum 선언
Node* current = list.getHead(); //리스트의 헤드를 저장할 노드형의 변수의 주소를 저장할 current 생성
while (current != NULL) { //current가 마지막 노드가 아닐 때
sum += current->getData(); //current는 data값을 가리켜서 sum에 더한다
current = current->getLink(); //current가 다음 노드로 가게 한다
}
std::cout << "노드들의 합계는 " << sum << "입니다." << std::endl;
}
답)
int main()
{
LinkedList list;
int n;
std::cout << "노드의 전체 갯수를 입력해주세요 : ";
std::cin >> n;
for (int i = 0; i < n; i++) {
int data;
std::cout << i+1 << "번 노드의 데이터 값을 입력해주세요 : ";
std::cin >> data;
list.insert(i, new Node(data));
}
int sum = 0;
Node* current = list.getHead();
while (current != NULL) {
sum += current->getData();
current = current->getLink();
}
std::cout << "노드들의 합계는 " << sum << "입니다." << std::endl;
}
2. 단순 연결 리스트에서 특정한 데이터 값을 갖는 노드의 개수를 계산하는 함수를 작성하라.
풀이)
int main()
{
LinkedList list; //연결리스트의 객체 list 선언
int n; // 노드의 전체 갯수를 담을 변수 n 선언
std::cout << "노드의 전체 갯수를 입력해주세요 : ";
std::cin >> n; //n에 전체 갯수 저장
for (int i = 0; i < n; i++) { //n개만큼의 노드에 데이터 생성
int data;
std::cout << i + 1 << "번 노드의 데이터 값을 입력해주세요 : ";
std::cin >> data;
list.insert(i, new Node(data));
}
int num; //특정 값을 저장할 변수 num생성
std::cout << "알고 싶은 값을 입력해주세요 : ";
std::cin >> num; //num에 저장
int count = 0; //특정 값이 나오는 횟수를 저장할 변수 count 선언
Node* current = list.getHead(); //current는 list의 첫번째 노드를 가리킨다
while (current != NULL) { //current가 마지막 노드를 가리키는게 아니라면
if (current->getData() == num) { //특정 값과 current가 가리키는 data필드값이 같다면 count + 1을 해라
count++;
}
current = current->getLink(); //current를 다음 노드를 가리키게 한다
}
std::cout << num << "의 갯수는 " << count << "개 입니다." << std::endl;
}
답)
int main()
{
LinkedList list;
int n;
std::cout << "노드의 전체 갯수를 입력해주세요 : ";
std::cin >> n;
for (int i = 0; i < n; i++) {
int data;
std::cout << i + 1 << "번 노드의 데이터 값을 입력해주세요 : ";
std::cin >> data;
list.insert(i, new Node(data));
}
int num;
std::cout << "알고 싶은 값을 입력해주세요 : ";
std::cin >> num;
int count = 0;
Node* current = list.getHead();
while (current != NULL) {
if (current->getData() == num) {
count++;
}
current = current->getLink();
}
std::cout << num << "의 갯수는 " << count << "개 입니다." << std::endl;
}
전체 코드
#include <iostream>
#include <iomanip>
class Node {
Node* link; // 다음 노드를 가리키는 포인터 변수 , 링크 필드
int data; // 노드의 데이터 필드
public:
Node(int val = 0) : data(val), link(NULL) {} // 생성자?
Node* getLink() {
return link;
}
void setLink(Node* next) {
link = next;
}
int getData() {
return data;
}
void display() {
std::cout << "<" << std::setw(2) << data << ">";
}
bool hasData(int val) {
return data == val;
}
//자신의 다음에 새로운 노드 n을 삽입하는 함수
void insetNext(Node* n) {
if (n != NULL) {
n->link = link;
link = n;
}
}
//자신의 다음 노드를 리스트에서 삭제하는 함수
Node* removeNext() {
Node* removed = link;
if (removed != NULL) {
link = removed->link;
return removed;
}
}
};
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; }
//pos번째 항목을 반환함
Node* getEntry(int pos) {
Node* n = &org;
for (int i = 1; i < pos; i++, n = n->getLink())
if (n == NULL) break;
return n;
}
//리스트의 어떤 위치에 항목 삽입
void insert(int pos, Node* n) {
Node* prev = getEntry(pos - 1);
if (prev != NULL)
prev->insetNext(n);
}
//리스트의 어떤 위치의 항목 삭제
Node* remove(int pos) {
Node* prev = getEntry(pos - 1);
return prev->removeNext();
}
//탐색함수
Node* find(int val) {
for(Node *p = getHead(); p != NULL; p = p-> getLink())
if (p -> hasData(val)) return p;
return NULL;
}
//리스트의 pos번째 노드를 다른 노드로 교체
void replace(int pos, Node* n) {
Node* prev = getEntry(pos - 1);
if (prev != NULL){
delete prev->removeNext();
prev->insetNext(n);
}
}
//리스트의 항목 개수를 반환
int size() {
int count = 0;
for (Node* p = getHead(); p != NULL; p = p->getLink())
count++;
return count;
}
//화면에 보기 좋게 출력
void diplay() {
std::cout << "[전체항목 수 = " << std::setw(2) << size() << "] : ";
for (Node* p = getHead(); p != NULL; p = p->getLink())
p->display();
std::cout << std::endl;
}
};
int main()
{
LinkedList list;
int n;
std::cout << "노드의 전체 갯수를 입력해주세요 : ";
std::cin >> n;
for (int i = 0; i < n; i++) {
int data;
std::cout << i + 1 << "번 노드의 데이터 값을 입력해주세요 : ";
std::cin >> data;
list.insert(i, new Node(data));
}
int sum = 0;
Node* current = list.getHead();
while (current != NULL) {
sum += current->getData();
current = current->getLink();
}
std::cout << "노드들의 합계는 " << sum << "입니다." << std::endl;
int num;
std::cout << "알고 싶은 값을 입력해주세요 : ";
std::cin >> num;
int count = 0;
current = list.getHead();
while (current != NULL) {
if (current->getData() == num) {
count++;
}
current = current->getLink();
}
std::cout << num << "의 갯수는 " << count << "개 입니다." << std::endl;
}