[자료구조] 추상 자료형(ADT)

자료형이란 그간 배워온 int, float 등을 말한다. 추상 자료형은 자료형(Data Type)에 Abstract(추상) 이라는 단어가 붙은 자료형으로 구현에 초점이 맞춰진 것이 아닌 기능에 대한 설명을 대략(추상)적으로 정리한 자료형이다. 따라서 ADT는 특정 언어의 문법이 아니다. (가령 이름없는 함수 lambda는 파이썬 고유의 문법이다.)

 

 

추상 자료형

/*
class MyArray 
{
public:
	MyArray(int size);

	~MyArray(); 

	float Retrieve(int i);

	void Store(int i, float x);

private:
	float* arr_ = 0;
	int size_ = 0;
}
어떻게 사용할 지 감이 옴. -> Abstract
*/

함수 이름만 보고도 대충 어떻게 작동할 지 감이 올 것이다. 그러나 실제 구현은 아무것도 되어있지 않다. 즉 MyArray를 추상적으로 적어놨다라고 보면 된다. 

 

 

추상 자료형은 코딩 협업에 가장 이상적인 형태이다. 개발자 a는 개발자 b가 구현한 함수 b-1에 대해 모든 것을 자세히 알 필요가 없다. 다만 input값이 무엇인지 그리고 이떄 ouput되는 값이 무엇인지만 파악하면 충분하다. 이러한 관점에서 해당 자료구조는 굉장히 유용하다. 

 

 

 

 

 

 

번외로 실제 각 함수 구현부는 다음과 같이 생겨먹었다

 

using namespace std;
#include <cstring>
#include <iostream>
#include "MyString.h"
// 비어 있는 MyString() 생성
MyString::MyString()
{
	str_ = nullptr;
	size_ = 0;
}

// 맨 뒤에 널 캐릭터'\0'가 들어 있는 문자열로부터 초기화
MyString::MyString(const char* init)
{
	// 크기(size_) 결정
	size_ = 0;
	while (init[size_] != '\0')
		size_++;

	str_ = new char[size_];
	memcpy(str_, init, size_);
}

// MyString의 다른 instance로부터 초기화
MyString::MyString(const MyString& str)
{
	// 기본 복사 생성자는 포인터 주소만 복사하기 때문에 
	// 소멸시 오류 발생
	// 여기서는 새로 메모리를 할당 받아서 복사
	size_ = str.size_; //멤버 변수
	str_ = new char[size_];
	memcpy(str_, str.str_, size_);
}

MyString::~MyString()
{
	if (str_ != nullptr)
	{
		delete[] str_;
		str_ = nullptr;
		size_ = 0;
	}

}

bool MyString::IsEmpty()
{
	return Length() == 0;
}

bool MyString::IsEqual(const MyString& str) // 편의상 참조& 사용
{
	// 힌트: str.str_, str.size_ 가능
	if (this->size_ != str.size_) 
		return false;
	for (int i = 0; i < size_; i++)
	{
		if (str_[i] != str.str_[i])
			return false;
	}
	return true;
}

int MyString::Length()
{
	return size_;
}

void MyString::Resize(int new_size)
{
	// 메모리 재할당과 원래 갖고 있던 내용 복사
	if (new_size != size_)
	{
		char* new_str = new char[new_size];
		for (int i = 0; i < (new_size < size_ ? new_size : size_); i++)
		{
			new_str[i] = str_[i];
		}
		delete[] str_;
		str_ = new_str;
		size_ = new_size;
	}
}

// 인덱스 start위치의 글자부터 num개의 글자로 새로운 문자열 만들기
MyString MyString::Substr(int start, int num)
{
	// 복사할 인덱스: start, start + 1, ... , start + num - 1
	// assert(start + num - 1 < this->size_); // 문제를 단순하게 만들기 위해 가정

	MyString temp;
	temp.Resize(num);
	for (int i = 0; i < num; i++)
	{
		temp.str_[i] = this->str_[start + i];
	}

	return temp;
}

MyString MyString::Concat(MyString app_str)
{
	MyString temp;
	temp.Resize(size_ + app_str.size_);

	memcpy(temp.str_, str_, size_);
	memcpy(&temp.str_[size_], app_str.str_, app_str.size_);

	return temp;
}

MyString MyString::Insert(MyString t, int start)
{
	assert(start >= 0);
	assert(start <= this->size_);

	MyString temp;
	temp.Resize(size_ + t.size_);

	for (int i = 0; i < start; i++)
	{
		temp.str_[i] = this->str_[i];
	}
	for (int i = start; i < start + t.size_; i++)
	{
		temp.str_[i] = t.str_[i - start];
	}
	for (int i = start + t.size_; i < size_ + t.size_; i++)
	{
		temp.str_[i] = str_[i - t.size_];
	}
	return temp;
}

int MyString::Find(MyString pat)
{
	for (int start = 0; start < Length() - pat.Length(); start++)
	{
		for (int j = 0; j < pat.Length(); j++)
		{
			if (str_[start + j] != pat.str_[j])
				break;
			if (j == pat.Length() - 1)
				return start; 
		}
	}
	return -1;
}

void MyString::Print()
{
	for (int i = 0; i < size_; i++)
		cout << str_[i];
	cout << endl;
}

개발자b가 직접 구현한 내용을 개발자a가 꼭 알아야 되나 싶은 거다... 물론 이 상황에서 개발자 a와 b는 모두 나다.ㅜㅜ