[Exercises 1]
/*
Write a C++ function length to count the number of nodes in a chain.
체인에 있는 노드의 갯수를 세는 함수를 작성한다
*/
#include <iostream>
using namespace std;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next)
{
}
int getData()
{
return data;
}
friend class Chain;
friend ostream &operator<<(ostream &os, Chain &c); //ChainNode의 getData가 필요하므로
};
class Chain
{
private:
ChainNode *first;
public:
Chain()
{
first = NULL;
}
ChainNode *getFirst() //처음 노드를 반환
{
return first;
}
ChainNode *Insert(ChainNode *x, int i) //노드 추가
{
if (first) //기존 노드들 사이에 추가
{
ChainNode *temp = new ChainNode(i, x->link);
x->link = temp; //x가 temp를 가르키도록
return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
}
else //기존 노드가 없을 경우
{
first = new ChainNode(i);
return first;
}
}
int Length()
{
int len = 0;
ChainNode *temp = first;
while (temp != NULL) //NULL을 가리킬 때까지
{
temp = temp->link;
len++;
}
return len;
}
friend ostream &operator<<(ostream &os, Chain &c);
};
ostream &operator<<(ostream &os, Chain &c)
{
ChainNode *temp = c.first;
while (temp != NULL)
{
os << temp->getData();
if (temp->link != NULL) //마지막 -> 출력 방지
cout << "->";
temp = temp->link; //다음으로 이동
}
return os;
}
int main(void)
{
Chain chain;
ChainNode *CN = chain.getFirst();
for (int i = 0; i < 10; i++)
CN=chain.Insert(CN, i + 1);
cout << chain << endl;
cout << "현재 체인에 있는 노드의 수: " << chain.Length() << endl;
return 0;
}
[Exercises 2]
/*
Let x be a pointer to an arbitrary node in a chain
x가 체인의 임의의 노드라고 한다.
Write a C++ function to delete this node from the chain
x를 제거하는 함수를 작성한다.
If x==first, then first should be reset to point to the new first node in the chain
x가 처음 노드를 가리킨다면 first 포인터는 기존의 first의 다음 노드를 가리키도록 ㅎ해야 한다.
*/
#include <iostream>
using namespace std;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next)
{
}
int getData()
{
return data;
}
ChainNode *Link()
{
return link;
}
friend class Chain;
friend ostream &operator<<(ostream &os, Chain &c); //ChainNode의 getData가 필요하므로
};
class Chain
{
private:
ChainNode *first;
public:
Chain()
{
first = NULL;
}
ChainNode *getFirst() //처음 노드를 반환
{
return first;
}
ChainNode *Insert(ChainNode *x, int i) //노드 추가
{
if (first) //기존 노드들 사이에 추가
{
ChainNode *temp = new ChainNode(i, x->link);
x->link = temp; //x가 temp를 가르키도록
return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
}
else //기존 노드가 없을 경우
{
first = new ChainNode(i);
return first;
}
}
int Length()
{
int len = 0;
ChainNode *temp = first;
while (temp != NULL) //NULL을 가리킬 때까지
{
temp = temp->link;
len++;
}
return len;
}
void Delete(ChainNode *x)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
if (x == first)
first = first->link; //다음 노드를 가리킨다
else
{
ChainNode *temp = first;
while (temp->link != x)
{
temp = temp->link; //x 전 노드를 찾아간다
}
temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다
}
delete x;
}
friend ostream &operator<<(ostream &os, Chain &c);
};
ostream &operator<<(ostream &os, Chain &c)
{
ChainNode *temp = c.first;
while (temp != NULL)
{
os << temp->getData();
if (temp->link != NULL) //마지막 -> 출력 방지
cout << "->";
temp = temp->link; //다음으로 이동
}
return os;
}
int main(void)
{
Chain chain;
int num;
ChainNode *CN = chain.getFirst();
for (int i = 0; i < 10; i++)
CN = chain.Insert(CN, i + 1);
cout << chain << endl;
ChainNode *del = chain.getFirst();
cout << "몇 번째 노드를 삭제하시겠습니까? ";
cin >> num;
for (int i = 1; i < num; i++)
del = del->Link();
chain.Delete(del);
cout << chain << endl;
return 0;
}
[Exercises 3]
/*
Write a C++ function to delete every other node beginning with node first
홀수 번째 노드를 삭제하는 함수를 작성해라
*/
#include <iostream>
using namespace std;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next)
{
}
int getData()
{
return data;
}
ChainNode *Link()
{
return link;
}
friend class Chain;
friend ostream &operator<<(ostream &os, Chain &c); //ChainNode의 getData가 필요하므로
};
class Chain
{
private:
ChainNode *first;
public:
Chain()
{
first = NULL;
}
ChainNode *getFirst() //처음 노드를 반환
{
return first;
}
ChainNode *Insert(ChainNode *x, int i) //노드 추가
{
if (first) //기존 노드들 사이에 추가
{
ChainNode *temp = new ChainNode(i, x->link);
x->link = temp; //x가 temp를 가르키도록
return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
}
else //기존 노드가 없을 경우
{
first = new ChainNode(i);
return first;
}
}
int Length()
{
int len = 0;
ChainNode *temp = first;
while (temp != NULL) //NULL을 가리킬 때까지
{
temp = temp->link;
len++;
}
return len;
}
void Delete(ChainNode *x)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
if (x == first)
first = first->link; //다음 노드를 가리킨다
else
{
ChainNode *temp = first;
while (temp->link != x)
{
temp = temp->link; //x 전 노드를 찾아간다
}
temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다
}
delete x;
}
void alternateDelete(void)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
else
{
ChainNode *temp = first;
Delete(temp);
temp = first; //first가 다음 노드를 가리켰으므로 first는 결국 원래 2번째 노드
while (temp->link != NULL) //다음 노드가 존재할 때까지
{
if ((temp->link->link) == NULL) //마지막 하나 남았을 떼
{
delete[](temp->link);
temp->link = NULL;
break;
}
Delete(temp->link);
temp = temp->link; //2개 건너뛴다
}
}
}
friend ostream &operator<<(ostream &os, Chain &c);
};
ostream &operator<<(ostream &os, Chain &c)
{
ChainNode *temp = c.first;
while (temp != NULL)
{
os << temp->getData();
if (temp->link != NULL) //마지막 -> 출력 방지
cout << "->";
temp = temp->link; //다음으로 이동
}
return os;
}
int main(void)
{
Chain chain;
int num;
ChainNode *CN = chain.getFirst();
for (int i = 0; i < 10; i++)
CN = chain.Insert(CN, i + 1);
cout << chain << endl;
chain.alternateDelete();
cout << "홀수번째 노드 삭제" << endl;
cout << chain << endl;
return 0;
}
[Exercises 4]
/*
Let x=(x1, x2, ..., xn) and y=(y1, y2, ..., ym) be two chains.
x=(x1, x2, ..., xn) 과 y=(y1, y2, ..., ym)가 두개의 체인이라고 가정한다.
Write a C++ function to merge the two chains together to obtain the chain z=(x1, y1, x2, y2, ..., xn) if m<=n and z=(x1, y1, x2, y2, ..., ym) if m>n
m<=n일 경우 z=(x1, y1, x2, y2, ..., xn) 체인이 되도록하고, m>n일 경우z=(x1, y1, x2, y2, ..., ym) 체인이 되도록 하는 merge 함수를 작성한다.
Following the merge, x and y should represent empty chains because each node initially in x or y is now in z.
합치고 난 다음에는 x 와 y 체인은 비어있어야 한다(기존에 있던 노드들이 모두 z에 있기 때문에)
No additional nodes may be used.
추가적인 노드들은 사용불가능하다.
*/
#include <iostream>
using namespace std;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next)
{
}
int getData()
{
return data;
}
ChainNode *Link()
{
return link;
}
friend class Chain;
friend ostream &operator<<(ostream &os, Chain &c); //ChainNode의 getData가 필요하므로
};
class Chain
{
private:
ChainNode *first;
public:
Chain()
{
first = NULL;
}
ChainNode *getFirst() //처음 노드를 반환
{
return first;
}
int getData()
{
return first->data;
}
ChainNode *Insert(ChainNode *x, int i) //노드 추가
{
if (first) //기존 노드들 사이에 추가
{
ChainNode *temp = new ChainNode(i, x->link);
x->link = temp; //x가 temp를 가르키도록
return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
}
else //기존 노드가 없을 경우
{
first = new ChainNode(i);
return first;
}
}
int Length()
{
int len = 0;
ChainNode *temp = first;
while (temp != NULL) //NULL을 가리킬 때까지
{
temp = temp->link;
len++;
}
return len;
}
void Delete(ChainNode *x)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
if (x == first)
first = first->link; //다음 노드를 가리킨다
else
{
ChainNode *temp = first;
while (temp->link != x)
{
temp = temp->link; //x 전 노드를 찾아간다
}
temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다
}
delete x;
}
void alternateDelete(void)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
else
{
ChainNode *temp = first;
Delete(temp);
temp = first; //first가 다음 노드를 가리켰으므로 first는 결국 원래 2번째 노드
while (temp->link != NULL) //다음 노드가 존재할 때까지
{
if ((temp->link->link) == NULL) //마지막 하나 남았을 떼
{
delete[](temp->link);
temp->link = NULL;
break;
}
Delete(temp->link);
temp = temp->link; //2개 건너뛴다
}
}
}
friend ostream &operator<<(ostream &os, Chain &c);
friend void Merge(Chain &x, Chain &y, Chain &z);
};
ostream &operator<<(ostream &os, Chain &c)
{
ChainNode *temp = c.first;
while (temp != NULL)
{
os << temp->getData();
if (temp->link != NULL) //마지막 -> 출력 방지
cout << "->";
temp = temp->link; //다음으로 이동
}
return os;
}
void Merge(Chain &x, Chain &y, Chain &z)
{
ChainNode *CN = z.getFirst();
int idx1 = 0, idx2 = 0;
int length1 = x.Length(); //길이를 저장 Delete하면 할 수록 x.Length()는 줄어들기 때문
int length2 = y.Length();
while (idx1 < length1 && idx2 < length2)
{
CN = z.Insert(CN, x.getData());
idx1++;
x.Delete(x.getFirst());
CN = z.Insert(CN, y.getData());
idx2++;
y.Delete(y.getFirst());
}
if (idx1 < length1)
{
while (idx1 < x.Length())
{
CN = z.Insert(CN, x.getData());
idx1++;
x.Delete(x.getFirst());
}
}
else if (idx2 < length2)
{
while (idx2 < y.Length())
{
CN = z.Insert(CN, y.getData());
idx2++;
y.Delete(y.getFirst());
}
}
}
int main(void)
{
Chain x, y, z;
ChainNode *CN1=x.getFirst();
ChainNode *CN2 = y.getFirst();
for (int i = 0; i < 5; i++)
CN1 = x.Insert(CN1, i + 1);
cout << "x: " << x << endl;
for (int i = 0; i < 5; i++)
CN2 = y.Insert(CN2, (i + 2) * 2);
cout << "y: " << y << endl;
Merge(x, y, z);
cout << "z: " << z << endl;
return 0;
}
[Exercises 5]
/*
Let x=(x1, x2, ..., xn) and y=(y1, y2, ..., ym) be two chains
x=(x1, x2, ..., xn) 과 y=(y1, y2, ..., ym)가 두개의 체인이라고 가정한다.
Assume that in each chain the nodes are in nondecreasing order of their data field values.
각각의 체인에 노드들은 오름차순으로 정렬되어있다고 가정한다
Write a C++ function to merge the two chains to botain a new chain z in which the nodes are also in this order.
두 개의 체인을 합치되 똑같이 오름차순으로 정렬되어있는 z를 만들어내는 함수를 구현한다.
Following the merge, x and y should represent empty chains because each node initially in x or y is now in z.
합치고 난 다음에는 x 와 y 체인은 비어있어야 한다(기존에 있던 노드들이 모두 z에 있기 때문에)
*/
#include <iostream>
using namespace std;
class ChainNode
{
private:
int data;
ChainNode *link;
public:
ChainNode(int element = 0, ChainNode *next = NULL) :data(element), link(next)
{
}
int getData()
{
return data;
}
ChainNode *Link()
{
return link;
}
friend class Chain;
friend ostream &operator<<(ostream &os, Chain &c); //ChainNode의 getData가 필요하므로
};
class Chain
{
private:
ChainNode *first;
public:
Chain()
{
first = NULL;
}
ChainNode *getFirst() //처음 노드를 반환
{
return first;
}
int getData()
{
return first->data;
}
ChainNode *Insert(ChainNode *x, int i) //노드 추가
{
if (first) //기존 노드들 사이에 추가
{
ChainNode *temp = new ChainNode(i, x->link);
x->link = temp; //x가 temp를 가르키도록
return x->link; //위치를 반환해야 그 다음 위치에 값을 대입
}
else //기존 노드가 없을 경우
{
first = new ChainNode(i);
return first;
}
}
int Length()
{
int len = 0;
ChainNode *temp = first;
while (temp != NULL) //NULL을 가리킬 때까지
{
temp = temp->link;
len++;
}
return len;
}
void Delete(ChainNode *x)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
if (x == first)
first = first->link; //다음 노드를 가리킨다
else
{
ChainNode *temp = first;
while (temp->link != x)
{
temp = temp->link; //x 전 노드를 찾아간다
}
temp->link = x->link; //x 다음을 temp와 연결시켜 자연스럽게 x가 없어지도록 한다
}
delete x;
}
void alternateDelete(void)
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
else
{
ChainNode *temp = first;
Delete(temp);
temp = first; //first가 다음 노드를 가리켰으므로 first는 결국 원래 2번째 노드
while (temp->link != NULL) //다음 노드가 존재할 때까지
{
if ((temp->link->link) == NULL) //마지막 하나 남았을 떼
{
delete[](temp->link);
temp->link = NULL;
break;
}
Delete(temp->link);
temp = temp->link; //2개 건너뛴다
}
}
}
void ascendingSort() //버블Sort 이용
{
if (first == NULL)
{
cout << "체인은 비어있다" << endl;
return;
}
else
{
ChainNode *End = 0; //마지막 노드 다음 노드 즉 NULL
ChainNode *current; //현재 가리키고 있는 노드
ChainNode *next; //다음에 가리킬 노드
ChainNode *previous; //이전에 가리킨 노드
while (first->link != End) //끝이 아닐 때까지
{
current = first; //현재는 처음을 가리키고
next = first->link;
previous = 0;
while (next != End) //현재 노드가 마지막 노드가 아닐 때까지
{
if (current->data > next->data) //현재가 더 크면
{
if (previous) //그 전 노드가 존재한다면
previous->link = next; //바꾼다
else
first = next;
//바꾼다
current->link = next->link;
next->link = current;
previous = next;
next = current->link;
}
else //오름차순이 맞다면 그냥 다음 노드로 넘어간다
{
previous = current;
current = next;
next = next->link;
}
}
End = current; //현재 노드가 마지막 노드가 되게 한다
}
}
}
friend ostream &operator<<(ostream &os, Chain &c);
friend void Merge(Chain &x, Chain &y, Chain &z);
};
ostream &operator<<(ostream &os, Chain &c)
{
ChainNode *temp = c.first;
while (temp != NULL)
{
os << temp->getData();
if (temp->link != NULL) //마지막 -> 출력 방지
cout << "->";
temp = temp->link; //다음으로 이동
}
return os;
}
void Merge(Chain &x, Chain &y, Chain &z)
{
ChainNode *CN = z.getFirst();
int idx1 = 0, idx2 = 0;
int length1 = x.Length(); //길이를 저장 Delete하면 할 수록 x.Length()는 줄어들기 때문
int length2 = y.Length();
while (idx1 < length1 && idx2 < length2)
{
CN = z.Insert(CN, x.getData());
idx1++;
x.Delete(x.getFirst());
CN = z.Insert(CN, y.getData());
idx2++;
y.Delete(y.getFirst());
}
if (idx1 < length1)
{
while (idx1 < length1)
{
CN = z.Insert(CN, x.getData());
idx1++;
x.Delete(x.getFirst());
}
}
else if (idx2 < length2)
{
while (idx2 < length2)
{
CN = z.Insert(CN, y.getData());
idx2++;
y.Delete(y.getFirst());
}
}
z.ascendingSort(); //추가
}
int main(void)
{
Chain x, y, z;
ChainNode *CN1 = x.getFirst();
ChainNode *CN2 = y.getFirst();
for (int i = 0; i < 5; i++)
CN1 = x.Insert(CN1, 15-i);
cout << "기존 x: " << x << endl;
x.ascendingSort();
cout << "오름차순한 x: " << x << endl;
for (int i = 0; i < 4; i++)
CN2 = y.Insert(CN2, 20-(3*i));
cout << "기존 y: " << y << endl;
y.ascendingSort();
cout << "오름차순한 y: " << y << endl;
Merge(x, y, z);
cout << "합친 결과 z: " << z << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서, http://penguinsw.egloos.com/2603514
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*InsertNode 함수는 http://penguinsw.egloos.com/2603514를 참고했습니다. 반환형을 void로 하려고 노력을 많이 해봤지만 아쉽게도 실패해서 링크처럼 ChainNode*을 반환형으로 사용했습니다.
*6번 문제는 더블링크드리스트에서도 풀 문제이기 때문에 생략했습니다
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 4.4 CircularList(원형리스트) (0) | 2017.08.20 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 4.3 연습문제 (0) | 2017.08.19 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 후위표기법 예제 (2) | 2017.08.15 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.5 미로 예제 (4) | 2017.08.13 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 3.4 연습문제 (2) | 2017.08.13 |