[C++ 자료구조론] 2장 배열

추상 데이타 타입과 C++ 클래스

• 명세와 구현을 구별하고 사용자로 부터 ADT의구현을 은닉하기 위해 클래스(class) 제공
• 클래스 구성
  • 클래스 이름
  • 데이터 멤버 (멤버 변수)
  • 멤버 함수
  • 💡 프로그램 접근 레벨 : public, private, protected
    • public : 프로그램 어디에서도 접근
    • private : 같은 클래스 내, friend로 선언된 함수나 클래스에 의해 접근
    • protected : 같은 클래스 내, 서브클래스, friend에 의해서만 접근

 

데이터 추상화와 캡슐화

• 데이터 멤버
  • 모두 private 또는 protected로 선언해 캡슐화
• 멤버 함수
  • 외부에서 접근할 것은 public으로 선언하고 나머지는 private이나 protected로 선언
  • 멤버 함수의 구현은 inline 함수로 처리할 수도 있음 → 속도 good
• 클래스 연산의 명세와 구현의 분리
  • 헤더 화일에 함수 프로토타입(함수 이름, 인자 타입, 결과 타입)을 정의하고
  • 소스 화일에 함수 구현

클래스 객체 멤버들에 대한 접근/기동

#include <iostream>
#include "Rectangle.h"

main() {
    Rectangle r, s;    // r과 s는 Class Rectangle의 객체들이다.
    Rectangle *t = &s; // t는 클래스 객체 s에 대한 포인터이다.
    .
    .
    // 클래스 객체의 멤버를 접근하기 위해서는 점(.)을 사용한다.
    // 포인터를 통해 클래스 객체의 멤버를 접근하기 위해서는 ->를 사용한다.
    if (r.GetHeight()*r.GetWidth() > t->GetHeight() * t->GetWidth())
        cout << " r ";
    else cout << " s ";

    cout << "has the greater area" << endl;
}

 

생성자 contructor와 파괴자 destructor

생성자

💡 한 객체의 데이타 멤버들을 초기화

• 클래스 객체가 만들어질 때 자동적으로 실행 → 객체가 선언될 때
• 해당 클래스의 공용 멤버 함수로 선언
• 공용 멤버 함수로 선언
• 생성자 이름은 클래스의 이름과 동일

// 코드 오류 고치기
Rectangle::Rectangle(int x, int y, int h, int w) {
    xLow = x; yLow = y;
    height = h; width = w;
}

Rectangle r(1,3,6,6);
Rectangle *s = new Rectangle(0,0,3,4);
Rectangle t // 컴파일 시간 오류! default constructor가 필요함

// 이렇게 고치세요
Rectangle::Rectangle (int x = 0, int y = 0, int h = 0, int w = 0)
: xLow(x), yLow(y), height(h), width(w)
{ }

💡 default constructor 구현

Rectangle::Rectangle() { xLow = 0; yLow = 0; height = 1; width = 1; }

파괴자(소멸자)

💡 객체가 없어지기 직전 데이타 멤버들을 삭제

• 클래스 객체가 범위를 벗어나거나 삭제될 때 자동적으로 기동
• 해당 클래스의 public 멤버로 선언
• 이름은 클래스 이름과 동일, 단 앞에 틸다(~) 붙임
• 반환 타입이나 반환 값을 명기해서도 안되고 인자를 받아서도 안됨
• 삭제되는 객체의 한 데이타 멤버가 다른 객체에 대한 포인터인 경우
  • 포인터에 할당된 기억장소는 반환
  • 지시되는 객체는 삭제되지 않음 → 명시적으로 수행하는 파괴자를 정의해야 됨
• constuctor가 있으면 반드시 destructor가 있어야 함. why? 메모리 누수

 

연산자 다중화 operator overloading

• 특정 데이터 타입을 위한 연산자를 구현하는 정의 허용

💡 연산자 다중화 헤더 적기
bool Rectangle::operator<(const Rectangle&);
bool Rectangle::operator==(const Rectangle&);

💡 클래스 Rectangle의 전용 데이터 멤버에 접근하기 위해 friend 선언하기  
friend ostream& operator<<(ostream&, Rectangle&);

실습 코드

• Class Rectangle을 위한 연산자 다중화

// rectangle.h  
#ifndef RECTANGLE\_H  
#define RECTANGLE\_H  
using namespace std;

class Rectangle {  
public:  
Rectangle(int, int, int, int); // constructor  
Rectangle(); // 기본 생성자  
~Rectangle(); // destructor  
void Print();  
int Area();  
bool LessThan(Rectangle&); // true 면적이 작으면  
bool EqualSize(Rectangle&); // true 면적이 동일하면  
bool Equal(Rectangle&); // Equal ( true) 교재의 모든 멤버가 동일하면  
int GetHeight();  
int GetWidth();

bool operator<(Rectangle&); // 면적이 작으면 true  
bool operator==(Rectangle&); // 면적이 같으면true  
//클래스 Rectangle의 전용 데이터 멤버에 접근하기 위해 friend 선언  
friend ostream& operator<<(ostream&, Rectangle&);

private:  
int xLow, yLow, height, width;  
};  
#endif

// rectangle.cpp  
#include  
#include "rectangle.h"  
using namespace std;

Rectangle::Rectangle(int x = 0, int y = 0, int h = 0, int w = 0)  
: xLow(x), yLow(y), height(h), width(w) { }  
Rectangle::Rectangle()  
: xLow(0), yLow(0), height(0), width(0) { }  
Rectangle::~Rectangle() { }

void Rectangle::Print() {  
cout << "xLow: " << xLow << ", yLow: " << yLow << ", height: " << height << ", width: " << width << "\\n";  
}

// 면적값을 산출하여 반환하기  
int Rectangle::Area() {  
return height \* width;  
// return GetHeight() \* GetWidth();  
}

// (Area()) 사각형의 면적이 작은 경우 작은 사각형으로 결정  
bool Rectangle::LessThan(Rectangle& s) {  
return Area() < s.Area();  
}

// (Area()) 사각형의 면적이 같은 경우  
bool Rectangle::EqualSize(Rectangle& s) {  
return Area() == s.Area();  
}

// 위치, 넓이, 높이 모두 같아야 동일한 사각형으로 결정  
bool Rectangle::Equal(Rectangle& s) {  
if (this == &s) return true; // this는 클래스 객체 자신을 가리키는 포인터  
return (xLow == s.xLow) && (yLow == s.yLow) && (height == s.height) && (width == s.width);  
}

int Rectangle::GetHeight() { return height; }  
int Rectangle::GetWidth() { return width; }

ostream& operator<<(ostream& os, Rectangle& s) {  
// ostream 버퍼에 넣어서 한 번에 출력  
os << "xLow: " << s.xLow << ", yLow: " << s.yLow << ", height: " << s.height << ", width: " << s.width << "\\n";  
return os;  
}

// (Area()) 사각형의 면적이 작은 경우 작은 사각형으로 결정  
bool Rectangle::operator<(Rectangle& s){  
return Area() < s.Area();  
}

// (Area()) 사각형의 면적이 같은 경우  
bool Rectangle::operator==(Rectangle& s) {  
return Area() == s.Area();  
}

 

ADT로서의 자료구조

💡 배열 Array : <인덱스,값>의 쌍 집합 
💡 다항식 Polynomial : 순서쌍 <지수, 계수>의 집합 
💡 희소행렬 Sparse Matrix : <행, 열, 값>의 쌍 집합 
💡 스택 Stack : top에서 모든 삽입과 삭제가 일어나는 순서 리스트 
💡 큐 Queue : rear에서 삽입이 일어나고 front에서 삭제가 일어나는 순서 리스트

다항식 polynomial

• 계수 coefficient
• 지수 exponent
• 변수 variable
• 차수 degree : 0이 아닌 제일 큰 지수

실습 코드

// poly.h  
#ifndef POLY\_H  
#define POLY\_H  
using namespace std;

class Polynomial; // 전방참조

class Term {  
friend class Polynomial; // Polynomial에서 Term의 데이타 멤버에 접근 가능  
friend ostream& operator<<(ostream&, Polynomial&);  
friend istream& operator>>(istream&, Polynomial&);  
private:  
float coef; // coefficient 계수  
int exp; // exponent 지수  
};

class Polynomial {  
public:  
Polynomial(); // construct a polynomial p(x) = 0.  
Polynomial operator+(Polynomial&); // 다항식의 합을 반환  
void NewTerm(const float, const int);  
friend ostream& operator<<(ostream&, Polynomial&);  
friend istream& operator>>(istream&, Polynomial&);  
private:  
Term\* termArray; // 0이 아닌 항의 배열, 각 원소는 term 타입, 동적 할당  
int capacity; // termArray의 크기, 1로 초기화  
int terms; // 0이 아닌 항의 수, 0으로 초기화  
};  
#endif

// poly.cpp  
#include  
#include "poly.h"  
using namespace std;

istream& operator>> (istream& is, Polynomial& p) {  
// #terms and (coefficoent, exponent)의 pair들을 읽어들인다.  
// 높은 차수의 항부터 입력되어 저장된다고 가정한다.  
int noofterms; float coef; int exp;  
is >> noofterms;  
for (int i = 0; i < noofterms; i++) {  
is >> coef >> exp; // 계수와 지수 pair를 읽어들인다.  
p.NewTerm(coef, exp);  
}  
return is;  
}

ostream& operator<< (ostream& os, Polynomial& p) {  
for (int i = 0; i < p.terms; i++) {  
if (p.termArray\[i\].exp > 1) {  
if (p.termArray\[i\].coef == 1)  
os << "x^" << p.termArray\[i\].exp;  
else if (p.termArray\[i\].coef == -1)  
os << "-x^" << p.termArray\[i\].exp;  
else  
os << p.termArray\[i\].coef << "x^" << p.termArray\[i\].exp;  
} else if (p.termArray\[i\].exp == 1) {  
if (p.termArray\[i\].coef == 1)  
os << "x";  
else if (p.termArray\[i\].coef == -1)  
os << "-x";  
else  
os << p.termArray\[i\].coef << "x";  
} else  
os << p.termArray\[i\].coef;

if (i < p.terms - 1) {
    if (p.termArray[i + 1].coef > 0)
        os << " +";
    else
        os << "  ";
}

}  
return os;

}

Polynomial::Polynomial() :capacity(1), terms(0) {  
termArray = new Term\[capacity\];  
}

// 새로운 항을 termArray 끝에 첨가  
void Polynomial::NewTerm(const float theCoeff, const int theExp) {  
if (terms == capacity) {  
//termArray의 크기를 두 배로 확장  
capacity *= 2;  
Term_ temp = new Term[capacity]; // 새로운 배열  
copy(termArray, termArray + terms, temp);  
delete[] termArray; // 그전 메모리를 반환  
termArray = temp;  
}  
termArray[terms].coef = theCoeff;  
termArray[terms++].exp = theExp;  
}

// a(x)(즉 \*this)와 b(x)를 항별로 더하여 c(x)를만드는 함수  
// 전체 실행 시간 : O(m+n)  
Polynomial Polynomial::operator+(Polynomial& 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(b.termArray\[bPos\].coef, b.termArray\[bPos\].exp);  
return c;

}

 

희소 행렬

• <행, 열, 값> 3원소 쌍 집합
• 0 아닌 원소수 / 전체 원소수 << 1.0인 경우 0 아닌 원소만 저장해 시간과 공간을 절약할 수 있다.
• 표현 방법
  • 첫 번째 행부터 3원소 쌍들을 열 순서로 저장
    • 한 행에서 모든 3원소 쌍들은 열 인덱스가 오름차순
  • 연산 종료를 보장하기 위해 행렬의 행과 열의 수와 0이아닌 항의 수를 알아야 한다.
  • rows : 행의 수
  • cols : 열의 수
  • capacity : smArray의 크기
  • terms : 0이 아닌 항의 총 수

 

행렬의 전치

Transpose

• 가장 단순한 형태의 알고리즘
• 구현
  • for (열 j에 있는 모든 원소에 대해) :
  • 원소(i, j, 값)을 원소(j, i, 값)으로 저장
• 실행 시간 : O(terms • cols) = O(rows • cols • cols)

for (int j = 0; j < columns; j++)  
for (int i = 0; i < rows; i++)  
b[j][i] = a[i][j];

SparseMatrix SparseMatrix::Transpose()  
{ // *this의 전치행렬을 반환한다.  
SparseMatrix b(cols,rows,terms); //b.smArray의 크기는 terms 이다.

if(terms > 0) { //0이 아닌 행렬
    int currentB=0;
    for ( int c = 0 ; c < cols ; c++ )//열별로 전치
         for ( int i = 0 ; i < terms ; i++ )
             //열 c로부터 원소를 찾아 이동시킨다.
             if(smArray[i].col == c) {
                 b.smArray[currentB].row = c;
                 b.smArray[currentB].col = smArray[i].row;
                 b.smArray[currentB++].value = smArray[i].value;
             }
 }
 return b;

}

FastTranspose

• Traspose에서 메모리를 조금 더 사용하고 실행 시간을 개선한 알고리즘
• for (열 j에 있는 모든 원소에 대해) 원소(i, j, 값)을 원소(j, i, 값)으로 저장
• 구현
  • 먼저 행렬 *this의 각 열에 대한 원소 수를 구함
  • 전치 행렬 b의 각 행의 원소 수를 결정
  • 이 정보에서 전치행렬 b의 각행의 시작위치 구함
  • 원래 행렬 a에 있는 원소를 하나씩 전치 행렬 b의 올바른 위치로 옮김
• 실행시간 : O(terms + cols)

SparseMatrix SparseMatrix::FastTranspose()
{ // *this의 전치를 O(terms+cols) 시간에 반환한다.
    SparseMatrix b(cols,rows,terms);
    if(terms >0)
    { //0이 아닌 행렬
         int *rowSize = new int[cols];
         int *rowStart = new int[cols];

         // compute rowSize[i] =b 의 행 i에 있는 항의 수를 계산
         fill(rowSize,rowSize + cols , 0); //초기화
         for ( i = 0 ; i < terms ; i++ ) rowSize[smArray[i].col]++;

         //rowStart[i] =b의 행 i의 시작점
         rowStart[0] = 0;
         for ( i = 1 ; i < cols ; i++ ) rowStart[i] = rowStart[i-1] + rowSize[i-1];

        for ( i = 0 ; i < terms ; i++ )
         { // *this를 b로 복사
             int j = rowStart[smArray[i].col];
             b.smArray[j].row = smArray[i].col;
             b.smArray[j].col = smArray[i].row;
             b.smArray[j].value = smArray[i].value;
             rowStart[smArray[i].col]++;
         }
         delete[] rowSize;
         delete[] rowStart;
    }
     return b;
}