[자료구조 C++] 배열을 이용한 Unsorted Type List 정렬되지 않은 리스트 소스 구현

안녕하세요 블로그 주인장 양햄찌입니다. 

오늘은 간만에 자료구조 관련 포스팅을 진행해보려고 해요.

오늘 살펴볼 자료주고는 LIST입니다. 

 

LIST란 무엇일까?

리스트는 목록이라는 뜻이죠!!

리스트~~

목록의 예를 들어볼까요? 우리가 핸드폰에 흔히 저장되어 있는 전화번호 목록! 또는 성적리스트, 출석부 등등..

즉 한 줄로 늘어 쭈루룩 세우는걸 목록이라고 해요. 

이렇게 앞과 뒤가 연속적으로 이어지는 관계를 선형적 관계라고 합니다. (Linear Relationship) 물론 맨 처음은 이어질게 없으니까 마찬가지 이유로 첫번째 요소와 마지막 요소는 이어지지 않고 unique할 수 있겠죠.

 

우리는, 우리가 알고 있는 이러한 '리스트'의 자료 저장 특성을 고려해서 코드로 구현해보려고 해요.

 

먼저 리스트는 정렬 여부에 따라서 아래처럼 두 가지로 나눌 수 있습니다.

◆정렬되지 않은 리스트 (Unsorted List)

◆정렬된 리스트 (Sorted List)

 

여기서 정렬이라 하는 것은 우리가 관심있는 key attribute에 따라서 정렬해 놓는 것을 말합니다. 이 키라고 하는 것은 하나의 attribute가 아니라 여러 attributes가 될 수 있어요. 속성 하나로 매겨주는게 아니라 여러 개의 속성으로서 key를 만들 수 있다는 말!

 

오늘은 배열을 이용해서 가장 기본적인 Unsorted List를 구현해볼거예요.

참고로 STL에서 제공하는 list는 배열기반이 아닌 이중연결리스트로 구현이 되어있습니다. 이중연결리스트는 이후에 또 다뤄볼거예요~

4 Kinds of ADT Operations - 추상자료형 기능 4가지 관점으로 정리하기 

전화번호를 전화번호부에 저장하듯이, 데이터를 리스트 형태로 저장하려면 어떤 기능이 필요한지 먼저 그림을 그려볼까요? 일단 특징을 기준으로 잡을 수 있게 전화번호목록을 만든다 가정하고 생각해봅시다.

 

ADT Operations 특징에 따라 필요한 기능들을 꾸려볼게요. 스스로 생각해보기~!

 

■ Constructor - 생성자

C++이기 때문에 LIST라는 클래스를 만들면 당연히 생성자가 필요할거예요.

 

■ Transformer - 변환자

현재 들어있는 데이터 값을 수정하는 그런 기능들을 말합니다.

- 전화번호 추가

- 전화번호 삭제

- 전화번호 수정

- 전화번호 초기화

 

■ Observer - 관찰자

데이터를 변경하는 거 없이, 데이터를 확인할 수 있는 기능을 말해요. 상태던 값이던..

- 전화번호 검색

- 총 몇 개의 전화번호가 저장되어 있는지 

- 전화번호가 꽉 찼는지 체크 (꽉찼으면비워주거나 삭제해줘야 다른걸 추가할 수 있을테니!) 

 

■ Literator - 반복자

검색도 뭔가 정보를 알아야 검색할 수 있죠?  뭔가 떠오르지 않을 때 우리 스크롤 쭉 내리면서 하나하나 찾잖아요.

전화번호 목록에 들어있는 사람들을 하나 하나씩 전부 다 볼 수 있도록,

즉 데이터를 연속적으로 접근 할 수 있게 끔 해주는데 필요한 기능을 말합니다. 

 

Generic Data Type으로 구현하자

고런데!! 리스트라는 건 전화번호부에만 한정되어 있지 않아요!! 성적리스트의 경우 이 data가 전화번호가 아닌 성적이 되어야겠죠. 전화번호부 리스트, 성적리스트, 도서리스트 등등 이런 것들을 각기 다 따로 만들면 리스트가 너무 많아지겠죠. 활용성도 떨어져요. 그래서 리스트를 구현할 때 Generic Data Type(제네릭 데이터타입)을 사용합니다.

무슨 말이냐! 데이터는 뭐가 될지 모르니 범용데이터라 가정하고 기능들만 모아놓은 거죠.

우리는 이 데이터를 Item이라 하고, 이 타입을 ItemType으로 소스코드를 작성해보도록 합시다.

전화번호부에서는 Item이 전화번호가 되는거고, 성적리스트에서는 Item이 성적이 되는거고 이렇게 때에 따라 데이터를 다르게 사용할 수 있다면 이러한 자료들을 저장하는 LIST를 구현해놓으면 여기저기 상황에서 활용할 수 있어요.

 

ItemType 클래스 구현하기

ItemType 클래스를 우리가 필요한 기능을 바탕으로 정의해봅시다.

가장 기본적인 값이 필요합니다. 값은 문자열이 될수도 있고, 정수가 될 수 있고 여러 타입이 될 수 있겠지만 오늘 예시로는 int타입이 기본값이라 생각하고 작성할게요. 다양한 타입을 그때그때 사용하시려는 분은 template을 이용한 코드로 살짝만 바꿔주면 되겠죠?  

 

먼저 아이템을 정렬하거나 특정 아이템을 찾으려면 아이템 간의 비교 연산이 필요해요.

또 아이템에 대한 출력기능은 당연히 있어야겠죠.

전화번호 초기화 기능을 위해서 아이템을 초기화하는 기능도 포함되어야 합니다. 

 

ItemType 기능 정리

- 생성자 ItemType()

- 비교기능 ComparedTo

- 출력기능 Print

- 초기화 기능 Initialize 

 

[ItemType 클래스 구현]

enum RelationType { LESS, GREATER, EQUAL };
class ItemType
{
private:
	int value;
public:
	ItemType();
	RelationType ComparedTo(ItemType) const;
	void Print(std::ostream&) const;
	void Initialize(int);
};

요렇게 필요한 기능을 구현해줬어요. 

 

[ItemType.cpp]

아이템타입 클래스의 멤버함수들을 프로토타입에 맞게 정의해줍시다.

#include "ItemType.h"
using namespace std;
ItemType::ItemType()
{
	value = 0;
}
RelationType ItemType::ComparedTo(ItemType Item) const
{
	if (value < Item.value)
		return LESS;
	else if (value > Item.value)
		return GREATER;
	else 
		return EQUAL;
}
void ItemType::Print(std::ostream& out) const
{
	out << value;
}
void ItemType::Initialize(int number)
{
	value = number;
}

소스는 보시면 바로 이해할 수 있을 정도로 어렵지 않아요 :) 

사실 내가 구현하고자 하는 바가 명확히 되어있으면 코드 작성은 어렵지 않죠~!

 

▼포스팅에 사용된 헤더파일과 소스파일 내려받기~!

ItemType.h

0.00MB

ItemType.cpp

0.00MB

Unsorted List ADT specification - 정렬되지 않은 리스트 ADT 명세서 

이제 위에서 우리가 작성했던 전화번호부목록을 전화번호부 목록에 특정하지 말고 아이템 목록이라고 보편적인 데이터가 대입될 수 있도록 생각합시다. '전화번호부 추가'가 아닌, '아이템 추가' 이렇게요!

■ Constructor - 생성자

- 생성자 UnsortedType()

 

■ Transformer - 변환자

- 아이템 추가 PutItem(ItemType Item) 

- 아이템 삭제 DeleteItem(ItemTyp item)

- 아이템들 비우기 MakeEmpty()

 

■ Observer - 관찰자

- 아이템 검색 GetItem(ItemType item, Boolean& found)

- 아이템 개수 GetLength()

- 아이템리스트가 꽉 찼는지 체크 IsFull()

 

■ Literator - 반복자

- ResetList()

- GetNextItem(ItemType& item)

리스트 반복을 위해 인덱스를 -1로 초기화 해놓는 작업과 

리스트의 다음 요소에 접근하기 위한 기능으로 세분화했어요

제네릭 타입에 대한 LIST에 대한 기능들은 이 정도로 정리해볼 수 있어요 

 

UnsortedType 클래스 구현하기

위에 열심히 정리한 기능을 토대로 클래스를 만들어봅시다.

#include "ItemType.h" 
#define MAX_ITEMS 20 
class UnsortedType
{	
private:
	int length;
	ItemType info[MAX_ITEMS]; //<= 배열로 구현!
	int currentPos;
public:
	UnsortedType();		//Constructor
	bool IsFull() const;
	int LengthIs() const;
	void GetItem(ItemType& item, bool& found);
	void PutItem(ItemType item);
	void DeleteItem(ItemType item);
	void ResetList();
	void GetNextItem(ItemType& item);
};

하나씩 구현해볼까요?

 

♣ UnsortedType()

처음 리스트를 생성했을 때 당연히 아이템의 개수는 0이겠죠. 0으로 개수를 맞춰줍시다. 

UnsortedType::UnsortedType()
{
	length = 0;
}

 

♣ IsFull()

꽉찾는지 체크해주는건 현재 리스트 개수가 MAX개수랑 같은지 비교해주면 돼요.

bool UnsortedType::IsFull() const
{
	return (length == MAX_ITEMS);
}

값 변경 없이 단순 비교후 트루 폴스만 리턴해주는거니 값 변형을 제한하기 위해 const를 붙여줬어요.

 

♣ LengthIs()

int UnsortedType::LengthIs() const
{
	return length;
}

길이 리턴해주는 것도 뭐... length만 반환해주는거니.. 

 

♣ GetItem(ItemType& item, bool& found)

중요한 부분이 나왔습니다. 아이템을 찾는거예요! 아이템은 인자로 받아서 해당 리스트에 저장된 배열중 같은 게 있는지 처음부터 돌면서 찾아야겠죠?? 즉 임시 location을 0으로 잡은 다음 없을 경우 1로 가서 찾고 또 없을 경우 2로 가서 찾고.. 

ItemType UnsortedType::GetItem(ItemType item, bool& found)
{
	int location = 0;
	found = false;
    
	while ((location < length) && !found) //찾지 못하면 현재 아이템 개수만큼 돌음
	{
		switch (item.ComparedTo(info[location]))
		{
		case LESS:
		case GREATER: 
        		location++; break;
		case EQUAL: 
        		found = true; item = info[location]; break; //찾으면 빠져나옴
		}
	}
}

인수로 받은 데이터가 리스트의 현재 위치에 있는 아이템과 같지 않을 경우(즉 크거나 작을 경우) 그 뒤에 저장된 데이터로 인덱스를 옮겨가서 다시 비교해야해요. 

 

♣ PutItem(ItemType item)

아이템 추가일 경우 우리가 이미 가지고 있는 아이템의 개수를 아니까(length) 배열 마지막에 추가로 저장해주기만 하면 되겠죠? 

void UnsortedType::PutItem(ItemType item)
{
	info[length] = item;
	length++;
}

추가한 다음에는 물론 length도 하나 늘려주는 걸 잊지 맙시다

미리 말하자면 마지막에 넣어주기만 하면 되기 때문에 Unsorted list 삽입 기능의 경우 시간복잡도가 O(1)이 됩니다.

데이터를 뽑는건 O(n)이 되네요? 위의 검색에서 짐작하셨겠지만, 순차적으로 돌면서 데이터를 찾아야 하기 때문이예요.

 

UnsortedType.h

0.00MB

UnsortedType.cpp

0.00MB

앞에서부터 쭉 차례대로 구현해봤는데요, 사실 소스를 보면 크게 어렵지 않죠~! 

함수 소스 하나하나 설명하면서 작성하는건 의미가 덜한 것 같아.. 여러분들이 체크하실 수 있도록 파일로 작성해서 올려놓았어요. 소스를 확인하기 전에 스스로 구현하고자 하는 자료구조를 추상화 해보고, 체크하기 전 스스로 소스를 작성해 보도록 합시다~! 고민한만큼 밑거름으로 삼으실 수 있을거예요. 오늘 포스팅은 여기까지입니다. 도움이 되셨다면 공감 좋아요 :)