[Exercises 1]
/*
Even though the multidimensional array is provided as a standard data object in C++,
다차원 배열이 C++ 표준 데이터 객체로 제공되고 있지만,
it is often useful to define your own class for multidimensional arrays.
다차원 배열을 직접 정의하는 것이 실용적일 때가 많다.
This gives a more robust class that:
직접 정의할 경우 아래와 같은 기능을 제공하는 탄탄한 클래스가 된다:
(a) Performs range checking
(a) 범위를 확인한다
(b) Does not require the index set in each dimension to consist of consectuive integers starting at 0
(b) a[0][0][0][0][1]과 같이 각 차원마다 인덱스를 부여하지 않아도 된다.
(c) Allows array assignment
(c) 배열을 배정받는 것을 허용한다.
(d) Allows initialization of an array with another array
(d) 다른 배열을 통한 초기화가 가능해진다
(e) Selects the range in each dimension of the array during runtime
(e) 각 차원의 범위를 실행시간동안 선택한다.
(f) Allows dynamic modification of the range and size of the array
(f) 배열의 범위와 크기를 동적으로 할당 가능하다
(g) Provides a mechanism to determine the size of an array
(g) 배열의 크기를 구할 수 있게 된다
Implement a class mdArray that stores floating point elements and provides the functionality specified above.
부동소수점 요소를 저장하고 위에서 설명한 기능들을 갖는 mdArray 클래스를 구현한다.
You will need to define two pointer data members corresponding to one-dimensional arrays which will be dynamically created:
구현하기 위해서는 각각 동적으로 할당될 일차원 배열을 나타내는 두 개의 포인터 데이터 멤버가 필요할 것이다.
the array of elements, and an array that stores the upper and lower bounds of each dimension.
요소들이 나열된 배열과 각 차원의 범위를 저장하고 있는 배열.
Additional data members may be required.
다른 데이터 멤버들이 필요할 수도 있다.
*/
#include <iostream>
using namespace std;
class mdArray;
class Int;
class Iterator;
class mdArray
{
friend Int; //배열 반환을 위한 class
friend Iterator; //for문 중첩을 위한 class
private:
const int dim; //몇차원 배열인지
int *size; //size[0]*size[1]*...*size[dim-1] 배열
struct Address
{
int level;
//마지막 레벨(dim-1)은 데이터 배열을 가리키고, 그 위 상위레벨에서는 다음 Address 배열을 가리킨다
void *next;
};
Address *top;
public:
class Iterator
{
private:
int *location;
mdArray *arr;
friend Int;
public:
Iterator(mdArray *arr, int *loc = NULL) :arr(arr)
{
location = new int[arr->dim];
for (int i = 0; i != arr->dim; i++)
location[i] = (loc != NULL ? loc[i] : 0);
}
Iterator(const Iterator &itr) :arr(itr.arr)
{
location = new int[arr->dim];
for (int i = 0; i != arr->dim; i++)
location[i] = itr.location[i];
}
~Iterator()
{
delete[]location;
}
//다음 원소를 가리키게 된다
Iterator &operator++()
{
if (location[0] >= arr->size[0])
return (*this);
bool carry = false; //(차원의) 받아 올림이 있는지
int i = arr->dim - 1;
do
{
//어차피 다시 while문으로 돌아온다는 것은 carry가 true라는 의미로 ++해야한다
location[i]++;
if (location[i] >= arr->size[i] && i >= 1)
{
//i가 0일 경우 0으로 만들지 않는다(이러면 begin과 중복)
//중복되면 컴파일 에러
location[i] -= arr->size[i];
carry = true;
i--;
}
else
carry = false;
} while (i >= 0 && carry);
return (*this);
}
Iterator &operator=(const Iterator &itr)
{
arr = itr.arr;
location = new int[itr.arr->dim];
for (int i = 0; i != arr->dim; i++)
location[i] = itr.location[i];
return (*this);
}
Iterator &operator++(int)
{
++(*this);
return (*this);
}
bool operator!=(const Iterator &itr)
{
if (itr.arr->dim != arr->dim)
return true;
for (int i = 0; i != arr->dim; i++)
if (itr.location[i] != location[i])
return true;
return false;
}
Int operator *();
};
mdArray(int dim, int *array_size) :dim(dim)
{
size = new int[dim];
for (int i = 0; i < dim; i++)
size[i] = array_size[i];
top = new Address;
top->level = 0;
initialize_address(top);
}
mdArray(const mdArray &arr) :dim(arr.dim)
{
size = new int[dim];
for (int i = 0; i < dim; i++)
size[i] = arr.size[i];
top = new Address;
top->level = 0;
initialize_address(top);
}
//address를 초기화하는 함수
void initialize_address(Address *current)
{
if (!current)
return;
if (current->level == dim - 1)
{
current->next = new int[size[current->level]];
return;
}
current->next = new Address[size[current->level]];
for (int i = 0; i != size[current->level]; i++)
{
(static_cast<Address *>(current->next) + i)->level = current->level + 1;
initialize_address(static_cast<Address *>(current->next) + i);;
}
}
void delete_address(Address *current)
{
if (!current)
return;
for (int i = 0; current->level < dim - 1 && i < size[current->level]; i++)
delete_address(static_cast<Address *>(current->next) + i);
delete[]current->next;
}
Int operator[](const int index);
~mdArray()
{
delete_address(top);
delete[]size;
}
Iterator begin()
{
int *arr = new int[dim];
for (int i = 0; i != dim; i++)
arr[i] = 0;
Iterator temp(this, arr);
delete[]arr;
return temp;
}
Iterator end()
{
int *arr = new int[dim];
arr[0] = size[0];
for (int i = 1; i < dim; i++)
arr[i] = 0;
Iterator temp(this, arr);
delete[]arr;
return temp;
}
};
class Int
{
private:
void *data;
int level;
mdArray *array;
public:
Int(int index, int _level = 0, void *_data = NULL, mdArray *_array = NULL) :level(_level), data(_data), array(_array)
{
if (_level < 1 || index >= array->size[_level - 1])
{
data = NULL;
return;
}
if (level == array->dim)
{
//이제 data에 우리의 int 자료형을 저장하게 해야 한다
data = static_cast<void*>((static_cast<int*>(static_cast<mdArray::Address *>(data)->next) + index));
}
else
{
//그렇지 않을 경우 data에 그냥 다음 addr을 넣어준다
data = static_cast<void*>(static_cast<mdArray::Address *>(static_cast<mdArray::Address *>(data)->next) + index);
}
}
Int(const Int &i) :data(i.data), level(i.level), array(i.array)
{
}
operator int()
{
if (data)
return *static_cast<int*>(data);
return 0;
}
Int &operator=(const int &a)
{
if (data)
*static_cast<int*>(data) = a;
return *this;
}
Int operator[](const int index)
{
if (!data)
return 0;
return Int(index, level + 1, data, array);
}
};
Int mdArray::operator[](const int index)
{
return Int(index, 1, static_cast<void*>(top), this);
}
Int mdArray::Iterator::operator*()
{
Int start = arr->operator[](location[0]);
for (int i = 1; i <= arr->dim - 1; i++)
{
start = start.operator[](location[i]);
}
return start;
}
int main(void)
{
int size[] = { 2, 3, 4 };
mdArray arr(3, size);
mdArray::Iterator itr = arr.begin();
for (int i = 0; itr != arr.end(); itr++, i++)
(*itr) = i;
for (itr = arr.begin(); itr != arr.end(); itr++)
cout << *itr << endl;
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 4; k++)
{
arr[i][j][k] = (i + 1)*(j + 1)*(k + 1) + arr[i][j][k];
}
}
}
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 4; k++)
{
cout << i << " " << j << " " << k << " " << arr[i][j][k] << endl;
}
}
}
return 0;
}
[Exercises 2]
/*
How many values can be held by each of the arrays a[n], b[n][m], c[n][2][3]
a[n], b[n][m], c[n][2][3] 배열들은 각각 몇개의 요소를 저장할 수 있는가?
*/
a[n]: n개
b[n][m]: n*m개
c[n][2][3]: n*2*3개, 즉 6*n개
[Exercises 3]
/*
Obtain an addressing formula for the element a[i(1)][i(2)], ..., [i(n)] in an array declared as a[u1][u2],...,[u(n)].
a[u1][u2],...,[u(n)]의 a[i(1)][i(2)], ..., [i(n)]번째 요소의 주소값을 반환하는 공식을 구해라.
Assume a column-major representation of the array with one word per element and alpha the address of a[0][0],...[0].
(이 부분은 해석하기 조금 난해했습니다) 한 단어로 이루어진 각 요소들이(+a[0][0],...,[0]의 주소와 함께) 열 단위로 정렬되어있다고 가정한다.
In a column-major representation, a two-dimensional array is stored sequentially by columns rather than by rows.
열 단위로 정렬되어있을 때, 이차원 배열은 행이 아니라 열끼리 연속적으로 저장된다.
*/
열 단위로 정렬되어 있을 때, A[0][i]의 주소는 x+i*upper0
임의 원소 A[i][j]의 주소는 x+j*upper0+i
a[i][j][k]의 위치를 찾아내기 위해서 우선 a[0][0][k]의 주소를 구하면 x+upper0*upper1*k+upper0*j+i
일반화하면,
A[i(0)][i(1)]...[i(n-1)]의 주소는 x+i(n-1)*upper0*upper1*...*upper(n-2)+i(n-2)*upper0*upper1*...*upper(n-3)+i(n-3)*upper0*upper1*...*upper(n-4)+...i1*upper0+i0
[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서,
*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.
*1번 문제는 http://itguru.tistory.com/204에 있는 코드입니다. 설명이 상세히 잘 되어있습니다.
'C++ > Fundamentals of Data Structures in C++(Horowitz)' 카테고리의 다른 글
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.8 연습문제 1~4 (0) | 2017.08.03 |
|---|---|
| C++ Fundamentals of Data Structures(C++ 자료구조론) 2.6 연습문제 (0) | 2017.07.31 |
| 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.3 연습문제 1~6 (0) | 2017.07.28 |