[Exercises 1]
/*
Use the six operations defined in this section for an ordered list to arrive at an ADT specification for such a list
이번 섹션에 언급된 여섯가지의 연산을 이용해 정렬된 리스트의 ADT를 작성해본다
*/
//ADT를 작성할 때는 추상적으로 작성해야하지만 어쩌다보니 클래스를 정의하였다.(물론 문법적으로 틀린부분이 있을 수 있습니다)
class orderedList
{
private:
int *arr;
int length;
public:
orderedList(int n):length(n)
{
arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = 0; //0으로 전부 초기화
}
int GetLength() //(1) Find the length, n, of the list(리스트의 길이를 반환)
{
return length;
}
void Print() //(2) Read the list from left to right(리스트의 처음부터 끝까지 출력)
{
for (int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
}
int GetElement(int i) //(3) Retrieve the ith element, 0<=i<n(i번째 데이터 반환)
{
return arr[i];
}
void StoreElement(int i, int newElement) //(4) Store a new value into the ith position, 0<=i<n(i번째 칸에 데이터를 입력)
{
arr[i] = newElement;
}
void AddElement(int i, int newElement) //(5) Insert a new element at the position i, 0<=i<n, causing elements numbered i, i+1, ..., n-1 to become numbered i+1, i+2, ... n
//i번째 칸에 데이터를 입력하되 이미 데이터가 있는 경우 i번째 데이터를 덮어쓰지 않고 한칸씩 미뤄서 리스트의 크기가 +1 되도록 한다
{
int *newArr;
if (arr[i] != 0)
{
int newSize = length + 1;
newArr = new int[newSize]; //한칸씩 늘리고
for (int j = i; j < newSize - 1; j++)
arr[i + 1] = arr[i]; //한칸씩 미룬다
for (int i = 0; i < newSize - 1; i++)
newArr[i]=arr[i];
newArr[i] = newElement;
}
else
{
arr[i] = newElement;
}
}
void DeleteElement(int i) //(6) Delete the element at position i, 0<=i<n, causing elements numbered i+1, ..., n-1 to become numbered i, i+1, ..., n-2
////i번째 칸에 데이터를 삭제하되 i번째 데이터부터 한칸씩 땡겨서 삭제시킨다. 결과적으로 리스트의 크기가 -1 되도록 한다
{
if (arr[i] == 0)
return;
else
{
for (int j = i; j < length; j++)
arr[j] = arr[j + 1]; //한칸씩 땡긴다
int newSize = length - 1;
int *newArr = new int[newSize];
for (int i = 0; i < newSize; i++)
newArr[i] = arr[i];
}
}
};
[Exercises 2]
/*
If a=(a0, ..., an-1) and b=(b0, ..., bm-1) are ordered lists,
a0~an-1까지의 데이터를 갖는 a 리스트와 b0~bm-1까지의 데이터를 갖는 b리스트가 정렬된 리스트들이라면
then a<b if ai=bi for 0<=i<j and aj<bj, or, if ai=bi, for 0<=i<n and n<m.
0<=i<j의 조건에서 ai=bi와 aj<bj의 조건이 동시에 만족하거나 0<=i<n과 n<m의 조건이 동시에 만족할 때 ai=bi이면 a<b이다.
Write a function that returns -1, 0, or +1, depending upon whether a<b, a=b, or a>b.
a<b일 때 -1, a=b일 때 0, a>b일 때 1을 반환하는 함수를 작성한다
*/
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
class orderedList
{
private:
int *arr;
int length;
public:
orderedList(int n) :length(n)
{
arr = new int[n];
for (int i = 0; i < n; i++)
arr[i] = 0; //0으로 전부 초기화
}
int GetLength() //(1) Find the length, n, of the list(리스트의 길이를 반환)
{
return length;
}
void Print() //(2) Read the list from left to right(리스트의 처음부터 끝까지 출력)
{
for (int i = 0; i < length; i++)
cout << arr[i] << " ";
cout << endl;
}
int GetElement(int i) //(3) Retrieve the ith element, 0<=i<n(i번째 데이터 반환)
{
return arr[i];
}
void StoreElement(int i, int newElement) //(4) Store a new value into the ith position, 0<=i<n(i번째 칸에 데이터를 입력)
{
arr[i] = newElement;
}
void sort() //정렬
{
for (int i = 0; i < length; i++)
{
for (int j = i + 1; j < length; j++)
{
if (arr[j] < arr[i])
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int Compare(orderedList &b)
{
int result = 0;
for (int i = 0; i < length; i++)
if (arr[i] == b.arr[i])
result++;
if (result == 0)
{
cout << "동일한 수가 없으므로 비교 불가" << endl;
return -1000;
}
else
{
if (length < b.length)
return -1;
else if (length == b.length)
return 0;
else
return 1;
}
}
};
int main(void)
{
orderedList a(10), b(12);
srand((unsigned)time(NULL));
for (int i = 0; i < a.GetLength(); i++)
a.StoreElement(i, rand() % 20 + 1);
a.sort();
cout << "a 리스트: ";
a.Print();
cout << endl;
for (int i = 0; i < b.GetLength(); i++)
b.StoreElement(i, rand() % 20 + 1);
b.sort();
cout << "b 리스트: ";
b.Print();
cout << endl;
cout << "두 리스트를 비교했을 때: " << a.Compare(b) << endl;
return 0;
}
[Exercises 3]
/*
Modify function Add so that it reduces the size of c.termArray to c.terms prior to termination
함수를 종료하기 전에 c.termArray의 크기를 c.terms로 줄이도록 Add 함수를 수정해라.
*/
#include <iostream>
using namespace std;
class Polynomial; //forward declaration
class Term
{
friend Polynomial;
private:
float coef;
int exp;
};
class Polynomial
{
private:
Term *termArray; //array of nonzero terms
int capacity;
int terms; //number of nonzero terms
public:
Polynomial()
{
capacity = 1;
terms = 0;
termArray = new Term[capacity];
}
void NewTerm(const float theCoeff, const int theExp)
{
//Add a new term to the end of termArray
if (terms == capacity)
{
//double capacity of termArray
capacity *= 2;
Term *temp = new Term[capacity]; //new array
copy(termArray, termArray + terms, temp);
delete[]termArray; //deallocate old memory
termArray = temp;
}
termArray[terms].coef = theCoeff;
termArray[terms++].exp = theExp;
}
Polynomial Add(Polynomial b)
{
//Return the sum of the polynomials *this and b
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < terms) && (bPos < b.terms))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef + b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
//add in remaining terms of *this
for (;aPos < terms; aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
//add in remaining terms of b(x)
for (;bPos < b.terms;bPos++)
c.NewTerm(termArray[bPos].coef, b.termArray[bPos].exp);
//추가된 부분
Term *temp = new Term[c.terms]; //new array
copy(c.termArray, c.termArray + c.terms, temp);
delete[]termArray;
c.termArray = temp;
return c;
}
};
[Exercises 4]
/*
Write C++ functions to input and output polynomials represented as in this section.
이번 섹션에 표현된 다항식을 입력하고 출력하는 함수를 작성한다
Your function should overload the << and >> operators.
이 함수들은 <<, >> 연산자를 오버로드 시켜야한다
*/
#include <iostream>
using namespace std;
class Polynomial; //forward declaration
class Term
{
friend Polynomial;
friend ostream &operator<<(ostream &os, const Polynomial &c); //Term 클래스의 멤버 변수 참조 위해
private:
float coef;
int exp;
};
class Polynomial
{
private:
Term *termArray; //array of nonzero terms
int capacity;
int terms; //number of nonzero terms
public:
Polynomial()
{
capacity = 1;
terms = 0;
termArray = new Term[capacity];
}
void NewTerm(const float theCoeff, const int theExp)
{
//Add a new term to the end of termArray
if (terms == capacity)
{
//double capacity of termArray
capacity *= 2;
Term *temp = new Term[capacity]; //new array
copy(termArray, termArray + terms, temp);
delete[]termArray; //deallocate old memory
termArray = temp;
}
termArray[terms].coef = theCoeff;
termArray[terms++].exp = theExp;
}
Polynomial Add(Polynomial b)
{
//Return the sum of the polynomials *this and b
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < terms) && (bPos < b.terms))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef + b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
//add in remaining terms of *this
for (;aPos < terms; aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
//add in remaining terms of b(x)
for (;bPos < b.terms;bPos++)
c.NewTerm(termArray[bPos].coef, b.termArray[bPos].exp);
Term *temp = new Term[c.terms]; //new array
copy(c.termArray, c.termArray + c.terms, temp);
delete[]termArray;
c.termArray = temp;
return c;
}
//입출력
friend ostream &operator<<(ostream &os, const Polynomial &c);
friend istream &operator>>(istream &is, Polynomial &c);
};
ostream &operator<<(ostream &os, const Polynomial &c)
{
for(int i=0; i<c.terms; i++)
os << c.termArray[i].coef << "x^(" << c.termArray[i].exp << ") " << " + ";
os << endl;
return os;
}
istream &operator>>(istream &is, Polynomial &c)
{
float coef;
int exp;
int newTerms;
cout << "입력할 개수: ";
is >> newTerms;
for (int i = 0; i < newTerms; i++)
{
cout << "계수, 지수 입력: ";
is >> coef >> exp;
c.NewTerm(coef, exp);
}
return is;
}
int main(void)
{
Polynomial p1;
cin >> p1;
cout << "입력한 다항식: " << p1 << endl;
return 0;
}
[Exercises 5]
/*
Write a C++ function that multiplies two polynomials represented as in this secition.
이 섹션에서 표현한 두 다항식을 곱하는 함수를 작성한다.
*/
#include <iostream>
using namespace std;
class Polynomial; //forward declaration
class Term
{
friend Polynomial;
friend ostream &operator<<(ostream &os, const Polynomial &c); //Term 클래스의 멤버 변수 참조 위해
private:
float coef;
int exp;
};
class Polynomial
{
private:
Term *termArray; //array of nonzero terms
int capacity;
int terms; //number of nonzero terms
public:
Polynomial()
{
capacity = 1;
terms = 0;
termArray = new Term[capacity];
}
void NewTerm(const float theCoeff, const int theExp)
{
//Add a new term to the end of termArray
if (terms == capacity)
{
//double capacity of termArray
capacity *= 2;
Term *temp = new Term[capacity]; //new array
copy(termArray, termArray + terms, temp);
delete[]termArray; //deallocate old memory
termArray = temp;
}
termArray[terms].coef = theCoeff;
termArray[terms++].exp = theExp;
}
Polynomial Add(Polynomial b)
{
//Return the sum of the polynomials *this and b
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < terms) && (bPos < b.terms))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef + b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
//add in remaining terms of *this
for (;aPos < terms; aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
//add in remaining terms of b(x)
for (;bPos < b.terms;bPos++)
c.NewTerm(termArray[bPos].coef, b.termArray[bPos].exp);
Term *temp = new Term[c.terms]; //new array
copy(c.termArray, c.termArray + c.terms, temp);
delete[]termArray;
c.termArray = temp;
return c;
}
Polynomial Multiplication(Polynomial b) //곱셈
{
Polynomial c;
c.NewTerm(0, 0);
for (int i = 0; i < terms; i++)
{
Polynomial temp;
for (int j = 0; j < b.terms; j++)
{
temp.NewTerm(termArray[i].coef*b.termArray[j].coef, termArray[i].exp+b.termArray[j].exp); //계수는 곱하고, 지수는 더하고
}
/*
cout << endl << "temp: " << temp << endl;
cout << "c: " << c << endl;
*/
c = c.Add(temp);
}
for (int i = 0; i < c.terms; i++)
{
for (int j = i + 1; j < c.terms; j++)
{
if (c.termArray[i].exp == c.termArray[j].exp) //같은 지수일 떄 계수를 더하는 for문
{
c.termArray[i].coef += c.termArray[j].coef;
c.termArray[j].coef = 0;
}
}
}
return c;
}
//입출력
friend ostream &operator<<(ostream &os, const Polynomial &c);
friend istream &operator>>(istream &is, Polynomial &c);
};
ostream &operator<<(ostream &os, const Polynomial &c)
{
for (int i = 0; i<c.terms; i++)
if(c.termArray[i].coef!=0)
os << c.termArray[i].coef << "x^(" << c.termArray[i].exp << ") " << "+" ;
os << endl;
return os;
}
istream &operator>>(istream &is, Polynomial &c)
{
float coef;
int exp;
int newTerms;
cout << "입력할 개수: ";
is >> newTerms;
for (int i = 0; i < newTerms; i++)
{
cout << "계수, 지수 입력: ";
is >> coef >> exp;
c.NewTerm(coef, exp);
}
return is;
}
int main(void)
{
Polynomial p1, p2;
for (int i = 0; i < 2; i++)
{
p1.NewTerm(i + 1, i + 1);
}
cout << "p1 다항식: " << p1 << endl;
for (int i = 1; i < 3; i++)
{
p2.NewTerm(i, i);
}
cout << "p2 다항식: " << p2 << endl;
Polynomial p3 = p1.Multiplication(p2);
cout << "p1*p2: " << p3 << endl;
return 0;
}
[Exercises 6]
/*
Write a c++ function that evaluates a polynomial at a value x0 using the representation of this section
이 섹션에서 표현한 다항식에 x0를 대입했을 때의 결과값을 반환하는 함수를 작성하시오
*/
#include <iostream>
using namespace std;
class Polynomial; //forward declaration
class Term
{
friend Polynomial;
friend ostream &operator<<(ostream &os, const Polynomial &c); //Term 클래스의 멤버 변수 참조 위해
private:
float coef;
int exp;
};
class Polynomial
{
private:
Term *termArray; //array of nonzero terms
int capacity;
int terms; //number of nonzero terms
public:
Polynomial()
{
capacity = 1;
terms = 0;
termArray = new Term[capacity];
}
void NewTerm(const float theCoeff, const int theExp)
{
//Add a new term to the end of termArray
if (terms == capacity)
{
//double capacity of termArray
capacity *= 2;
Term *temp = new Term[capacity]; //new array
copy(termArray, termArray + terms, temp);
delete[]termArray; //deallocate old memory
termArray = temp;
}
termArray[terms].coef = theCoeff;
termArray[terms++].exp = theExp;
}
Polynomial Add(Polynomial b)
{
//Return the sum of the polynomials *this and b
Polynomial c;
int aPos = 0, bPos = 0;
while ((aPos < terms) && (bPos < b.terms))
{
if (termArray[aPos].exp == b.termArray[bPos].exp)
{
float t = termArray[aPos].coef + b.termArray[bPos].coef;
if (t)
c.NewTerm(t, termArray[aPos].exp);
aPos++;
bPos++;
}
else if (termArray[aPos].exp < b.termArray[bPos].exp)
{
c.NewTerm(b.termArray[bPos].coef, b.termArray[bPos].exp);
bPos++;
}
else
{
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
aPos++;
}
}
//add in remaining terms of *this
for (;aPos < terms; aPos++)
c.NewTerm(termArray[aPos].coef, termArray[aPos].exp);
//add in remaining terms of b(x)
for (;bPos < b.terms;bPos++)
c.NewTerm(termArray[bPos].coef, b.termArray[bPos].exp);
Term *temp = new Term[c.terms]; //new array
copy(c.termArray, c.termArray + c.terms, temp);
delete[]termArray;
c.termArray = temp;
return c;
}
Polynomial Multiplication(Polynomial b) //곱셈
{
Polynomial c;
c.NewTerm(0, 0);
for (int i = 0; i < terms; i++)
{
Polynomial temp;
for (int j = 0; j < b.terms; j++)
{
temp.NewTerm(termArray[i].coef*b.termArray[j].coef, termArray[i].exp + b.termArray[j].exp); //계수는 곱하고, 지수는 더하고
}
c = c.Add(temp);
}
return c;
}
float Eval(float x) //x 대입했을 때 결과값
{
float result = 0;
for (int i = 0; i<terms; i++)
{
float temp = 1; //곱셈이므로 temp는 1
for (int j = 0; j < termArray[i].exp; j++)
temp *= x; //지수 계산
result += (temp*termArray[i].coef);
}
return result;
}
//입출력
friend ostream &operator<<(ostream &os, const Polynomial &c);
friend istream &operator>>(istream &is, Polynomial &c);
};
ostream &operator<<(ostream &os, const Polynomial &c)
{
for (int i = 0; i<c.terms; i++)
if (c.termArray[i].coef != 0)
os << c.termArray[i].coef << "x^(" << c.termArray[i].exp << ") " << "+";
os << endl;
return os;
}
istream &operator>>(istream &is, Polynomial &c)
{
float coef;
int exp;
int newTerms;
cout << "입력할 개수: ";
is >> newTerms;
for (int i = 0; i < newTerms; i++)
{
cout << "계수, 지수 입력: ";
is >> coef >> exp;
c.NewTerm(coef, exp);
}
return is;
}
int main(void)
{
Polynomial p1;
for (int i = 0; i < 2; i++)
{
p1.NewTerm(i + 1, i + 1);
}
cout << "P1 다항식: " << p1 << endl;
cout << "p1 다항식에 2를 대입할 경우: " << p1.Eval(2) << endl;
return 0;
}
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.4 연습문제 (0) | 2017.07.29 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.3 연습문제 7~9 (0) | 2017.07.28 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.2 연습문제 (0) | 2017.07.25 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.1 연습문제 (0) | 2017.07.25 |
| C++ Fundamentals of Data Structures(C++ 자료구조론) 1.7 연습문제 (6) | 2017.07.22 |