[1번]
[listNode.h]
/*
단순 연결리스트를 위한 Node 클래스
프로그램 6.5와 6.6에서 구현한 연결 리스트를 이용한 리스트 클래스를 화장하여
다음의 연산들을 추가하고 동작을 확인하라
(1) 연결 리스트의 모든 노드의 순서를 반대로 바꾸는 연산을 구혆하라
(2) 다른 리스트 객체 that의 노드 정보를 현재 리스트에 병합하는 다음 연산을 구현하라
이 연산 후 that 리스트는 공백 리스트가 되어야 한다.
*/
#include <iostream>
using namespace std;
class Node
{
private:
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()
{
cout << "<" << data << "> ";
}
bool hasData(int val)
{
return data == val;
}
//자신의 다음에 새로운 노드 n을 삽입하는 함수
void insertNext(Node *n)
{
if (n != NULL)
{
n->link = link;
link = n;
}
}
//자신의 다음 노드를 리스트에서 삭제하는 함수
Node *removeNext()
{
Node *removed = link;
if (removed != NULL)
link = removed->link;
return removed;
}
};
[LinkedList.h]
/*
단순 연결리스트 클래스
*/
#include "listNode.h"
class LinkedList
{
private:
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->insertNext(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;
}
//리스트의 어떤 위치에 항목 삽입
void replace(int pos, Node *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 display()
{
cout << "[전체 항목 수 = " << size() << "] : ";
for (Node *p = getHead(); p != NULL; p = p->getLink())
p->display();
cout << endl;
}
//모든 데이터 값을 더한 합을 출력하는 함수
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))
cnt++;
return cnt;
}
//연결리스트의 모든 노드의 순서를 반대로 바꾸는 연산
void reverse()
{
int count = 0;
for(int i=0; i<size(); i++)
{
Node *p=remove(size()-1); //마지막 노드를 삭제하고
insert(count++, p); //count번째에 입력, count는 계속 늘어난다
}
}
//다른 리스트 객체 that의 노드 정보를 현재 리스트에 병합하는 다음 연산을 구현하라
void merge(LinkedList *that)
{
while(!that->isEmpty()) //that의 노드가 존재하지 않을 때까지
{
Node *p = that->remove(0); //that을 삭제하고
insert(size(), p); //삭제된 노드를 입력
}
}
};
[LinkedList.cpp]
/*
단순 연결리스트 테스트 프로그램
*/
#include "LinkedList.h"
int main(void)
{
LinkedList list;
LinkedList list2;
list.insert(0, new Node(10));
list.insert(0, new Node(20));
list.insert(1, new Node(30));
list.insert(list.size(), new Node(40));
list.insert(2, new Node(50));
list2.insert(0, new Node(20));
list2.insert(0, new Node(30));
list2.insert(0, new Node(40));
cout << "list: ";
list.display();
cout << "list2: ";
list2.display();
cout << "list와 list2를 합친 결과" << endl;
list.merge(&list2);
cout << "list: ";
list.display();
cout << "list2: ";
list2.display();
cout << "list ";
list.sum();
cout << "list 내 90을 갖고 있는 노드의 수: " << list.count(90) << endl;
cout << "list 역순: ";
list.reverse();
list.display();
list.remove(2);
list.remove(list.size() - 1);
list.remove(0);
list.replace(1, new Node(90));
list.display();
cout << "list 내 90을 갖고 있는 노드의 수: " << list.count(90) << endl;
list.clear();
list.display();
return 0;
}
[2번]
[CircularList.h]
/*
프로그램 6.5와 6.6에서 구현한 LinkedLIst 클래스를 참고하여 원형 연결 리스트 클래스 CircularList를 구현하고 동작을 테스트해라
*/
#include <iostream>
using namespace std;
struct Node
{
int data;
Node *link;
Node(int temp)
{
data = temp;
link = NULL;
}
};
class CircularList
{
private:
Node *head; //앞에 노드를 가리키는 포인터
Node *tail; //끝 노드를 가리키는 포인터
public:
CircularList()
{
head = tail = NULL;
}
~CircularList()
{
clear(); //소멸자
}
void clear()
{
while (!isEmpty())
delete remove(0);
}
Node *getHead()
{
return head;
}
bool isEmpty()
{
return getHead() == NULL;
}
//리스트의 어떤 위치에 항목 삽입
void insert(int pos, Node *n)
{
if (pos == 0) //head에 입력
{
if (head == NULL) //head가 비어있다면
{
head = n;
tail = n;
n->link = tail;
return;
}
else if (head != NULL) //head가 비어있지 않는다면
{
n->link = head;
head = n;
tail->link = n;
return;
}
}
//head 이외의 곳에 입력한다면
int index = 0;
Node *current = head;
while (index > pos - 1)
{
current = current->link;
index++;
}
n->link = current->link;
current->link = n;
}
//리스트의 어떤 위치의 항목 삭제
Node *remove(int pos)
{
if (isEmpty()) //리스트가 비어있다면
{
return NULL;
}
if (pos == 0) //첫번째 요소를 삭제한다면
{
if (head == tail) //데이터가 하나일때
{
head = tail = NULL;
return NULL;
}
else //데이터가 여러개일 때
{
Node *del = head;
head = head->link;
tail->link = head;
return del;
}
}
//head 말고 다른 요소를 삭제할 경우
int index = 0;
Node *temp = NULL;
Node *current = head;
while (index < pos)
{
if (current->link == NULL)
{
return NULL;
}
if (index == pos - 1)
temp = current;
current = current->link;
index++;
}
temp->link = current->link;
if (current == tail) //만약 삭제된 곳이 tail이였다면
tail = temp; //tail을 초기화
return current;
}
int size()
{
Node *current = head;
int index = 1;
if (!isEmpty())
current = current->link;
while (current != head)
{
index++;
current = current->link;
}
return index;
}
//화면에 보기 좋게 출력
void display()
{
if (size() == 1) //size()가 1을 반환했다는 것은 리스트가 비었다는 뜻
{
cout << "[전체 항목 수= 0]: " << endl;
return;
}
cout << "[전체 항목 수 = " << size() << "] : ";
Node *current = head;
cout << "<" << current->data << "> ";
current = current->link;
while (current != head)
{
cout << "<" << current->data << "> ";
current = current->link;
}
cout << endl;
}
};
[CircularList.cpp]
#include "CircularList.h"
int main(void)
{
CircularList list;
list.insert(0, new Node(10));
list.insert(0, new Node(20));
list.insert(1, new Node(30));
list.insert(list.size(), new Node(40));
list.insert(2, new Node(50));
list.display();
list.remove(2);
list.remove(list.size() - 1);
list.remove(0);
list.display();
list.clear();
list.display();
return 0;
}
[3번]
[polyNode.h]
/*
p(x)=10x^100+6과 같이 최고차상의 차수가 매우 크고 대부분 항의 계수가 0인 다항식을 희소다항식이라고 하자
이러한 다항식을 구현하기 위해 배열을 사용하면 메모리의 낭비가 심하다.
따라서 희소 다항식은 연결 리스트를 이용하여 구현한 것이 좋다.
*/
#include <iostream>
using namespace std;
class Node
{
private:
float coef; //계수
int exp; //지수
Node *link;
public:
Node(float c = 0, int e = 0) :coef(c), exp(e), link(NULL)
{
}
Node *getLink()
{
return link;
}
void setLink(Node *next)
{
link = next;
}
void display()
{
cout << coef << " x^" << exp << " + ";
}
//자신의 다음에 새로운 노드 n을 삽입하는 함수
void insertNext(Node *n)
{
if (n != NULL)
{
n->link = link;
link = n;
}
}
//자신의 다음 노드를 리스트에서 삭제하는 함수
Node *removeNext()
{
Node *removed = link;
if (removed != NULL)
link = removed->link;
return removed;
}
friend class polyList;
};
[polyList.h]
/*
다항식 링크드 리스트
*/
#include "polyNode.h"
class polyList
{
private:
Node org;
public:
polyList() : org(0)
{
}
~polyList()
{
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->insertNext(n);
}
//리스트의 어떤 위치의 항목 삭제
Node *remove(int pos)
{
Node *prev = getEntry(pos - 1);
return prev->removeNext();
}
//리스트의 항목 개수 반환
int size()
{
int count = 0;
for (Node *p = getHead(); p != NULL; p = p->getLink())
count++;
return count;
}
void Add(polyList *that)
{
polyList temp;
int count = 0;
Node *p = getHead();
Node *t = that->getHead();
while (p != NULL && t != NULL)
{
if (p->exp == t->exp)
{
temp.insert(count++, new Node(p->coef + t->coef, p->exp));
p = p->getLink();
t = t->getLink();
}
else if (p->exp > t->exp)
{
temp.insert(count++, new Node(p->coef, p->exp));
p = p->getLink();
}
else
{
temp.insert(count++, new Node(t->coef, t->exp));
t = t->getLink();
}
}
for (;p != NULL; p = p->getLink())
temp.insert(count++, new Node(p->coef, p->exp));
for (;t != NULL; t = t->getLink())
temp.insert(count++, new Node(t->coef, t->exp));
cout << "A+B =(" << temp.size() << "항)= ";
temp.display();
}
void input()
{
int count, e;
float c;
cout << "희소 다항식의 항의 개수를 입력하세요: ";
cin >> count;
cout << "각 항의 계수와 지수 입력(최고차항부터 " << count << "개)" << endl;
for (int i = 0; i < count; i++)
{
cout << i + 1 << "번째 항: 계수 지수 = ";
cin >> c >> e;
insert(i, new Node(c, e));
}
}
//화면에 보기 좋게 출력
void display()
{
int count = 1;
if (size() == 0)
{
cout << "다항식이 존재하지 않습니다" << endl;
return;
}
else
{
for (Node *p = getHead(); p != NULL; p = p->getLink())
{
p->display();
}
cout << endl;
}
}
};
[polyList.cpp]
#include "polyList.h"
int main(void)
{
polyList A, B, C;
A.input();
B.input();
cout << "A=(" << A.size() << "항) = ";
A.display();
cout << "B=(" << B.size() << "항) = ";
B.display();
A.Add(&B);
return 0;
}
개발환경:Visual Studio 2017
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
[참고] C++로 쉽게 풀어쓴 자료구조
'C++ > C++로 쉽게 풀어쓴 자료구조' 카테고리의 다른 글
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 7 (13) | 2017.10.07 |
|---|---|
| C++로 쉽게 풀어쓴 자료구조 7장 연습문제 (0) | 2017.10.07 |
| C++로 쉽게 풀어쓴 자료구조 6장 연습문제 (0) | 2017.10.03 |
| C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 5 (25) | 2017.10.01 |
| C++로 쉽게 풀어쓴 자료구조 연습문제 4-8 (0) | 2017.09.27 |