List

@Category

-List의 정의

-List의 종류

-ADT와 List, 그 opeartion과 domain

-UnsortedType

-SortedType

-Big (o) 정도...?

 

@List의 정의

리스트의 필수요소로 리스트의 정의를 설명하자면,

 

Linear relationship을 가져야한다.

 

Linear relationship =

Each element except the first has a unique predecessor, and each element except the last has unique successor

 

@List의 종류

Unsorted List와 Sorted List가 있다.

 

1. Unsorted List

리스트 상의 데이터에 순서가 없다. 그 순서는 alphabetical이 될 수도 있고, numerical 하게 increasing order or decreasing order가 될 수도 잇다.

 

2. Sorted List

리스트 상의 데이터에 순서가 있다.

 

@ADT와 리스트, 그 operation과 domain

ADT와 리스트가 무슨 관계를 가질까?

 

여러 자료구조 중에서 어떤 리스트가 있다고 가정해보자 , User는 이 리스트의 모든것을 알 필요는 없다.

 

따라서, 추상화하여 abstract한 class로 작성한다. 이를 Abstract data type이라 한다.

 

그렇다면 이 class에는 prototype만 declaration 한다는 것인데,

 

어떤 domain과 operation을 선언해야 할까?

1.operation의 종류

#Constructor

#Transformer

#Observer

#Iterator

 

각각의 method를 소개하기전에 각각의 분류에 어떤 메소드(operation)가 들어가야 할 지 고민해보자.

 

#Constructor

생성자, 무엇을 생성하는것일까?

바로 이 자료형, List를 생성하는것이다.

아규먼트가 주어지지 않는다면 기본생성자로 모든 data가 Null하게 생성할수도 있겠다.

또한, 주어진 boolean인자로 boolean이 0이라면 위에서 설명한것과 같이 Null하게, 1이라면 모든 data를 RAND함수를 호출하여 랜덤하게 집어넣을 수 도 있겠다. 그저 생성자가 List의 data를 초기화 한다는 생각이 들면 ok

list();

 

#Transformer

List를 변화시키는게 무엇이 있을까? 당연히 값을 집어넣거나 빼는것이다.

그런데 그 내부를 고민해보면, 값을 집어넣거나 빼는 방식에도 차이가 있다.

일단 집어넣는것은 static한 list에 맨 마지막이나 맨 앞에 집어넣어야한다.(Unsorted의 경우)

그리고 빼는것은 그 자리를 그저 빈공간으로도 둘 수 있지만, 빈 공간으로 두지않고, list의 형태를 유지할 수 있도록

그 자리를 비우고, last의 data를 그 자리로 가져올 수 있다.

void DeleteItem(arguments);
void InsertItem(arguments);

#Observer

지금 list의 length가 얼마나 될까?

지금 list가 꽉 찼을까?

어떤 특정 index의 data 값이 내가 argument로 넣은 data 값과 같은가?

bool IsFull(arguments);
int LengthIs(arguments);
int(class) RetriveItem(arguments);

(특정 index의 data값이 무엇인가? -> 이게 왜 없는지는 다음과 같이 생각해 볼 수 있다.)

밑의 iterator를 봐도 알겠지만, User는 list의 특정 index에 접근할 수 없고, 특정 index가 있는지조차

알 수 없게 해야한다. 따라서 3번부터 5번의 data를 불러오고자 하는 행위는 애초에 성립할 수가 없다.

따라서 0번부터 3번의 list data를 불러올려면

for(int i=0;i<3;i++)

getItem(i); 가 아닌

for(int i=0;i<3;i++)

getitem(); 인 것이다.

#Iterator

인덱스에 접근할 수 없으니,

position을 가장 앞으로 옮기는 함수와, 순차적으로 값을 반환하는 함수가 있을 수 있겠다.

void ResetList();
void GetNextItem(ItemType& item);

나도 안다, 뭔가 찜찜하게, 있어야 할 함수가 없는것처럼 보이기도하고, 이 함수가 굳이 필요한가 싶기도 한 이 기분...

하지만 Abstract하게 User에게 편의성을 제공해주는 측면에서 내가 생각한것보다 남이 생각한것이 맞다고 가정한다면

위의 구성요소를 조금은 외울 필요가 있다.

Constructor는 그 자체이고, Observer로는 isfull, lengthis, retriveitem(일치여부), Transformer로는 insert,delete, #iterator로는 reset,getnext 가 있다는것을 1 3 2 2로 기억해두자.

 

2. Domain의 종류

length, currentPos, info[MAX_ITEMS] 가 있겠다. (요것도 좀 외우자.)

 

이쯤에서 generic data type에 대해서 알고 가야한다.

리스트에 들어가있는 datatype은 int일까? 혹은 char일까? 이를 모르기에 class로 composite data type을 작성한다.

그리고 이 class와 다른 class의 대소비교는 그 안의 내부 data를 모르면 불가능하기에, 그 private한 data에 접근할 수 있도록 이 class의 내부에 compareTo를 작성하여 비교한다.

(CompareTo 메소드는 ItemType 내부에!)

 

@UnsortedType

#Abstract Data Type "UnsortedType"

#pragma once
#include "ItemType.h"
class UnsortedType
{
public:
	//constructor
	UnsortedType();
	//Transformer
	void InsertItem(const ItemType& item);
	void DeleteItem(const ItemType& item);
	//Observer
	bool IsFull() const;
	int LengthIs() const;
	bool RetriveItem(const ItemType& item);
	//Iterator
	void ResetList();
	const ItemType& GetNextItem();
private:
	int length;
	int currentPos;
	ItemType info[MAX_ITEMS];
};

#Encapsulated generic data type "ItemType" (not abstract)

#pragma once
#define MAX_ITEMS 5
enum RelationType
{
	LESS,
	GREATER,
	EQUAL
};
class ItemType
{
public:
	RelationType ComparedTo(const ItemType&) const;
	void Print() const;
	void Initialize(int number);
private:
	int value;
};

#Implementation of "UnsortedType"

#include <iostream>
#include "UnsortedType.h"
using namespace std;

//Constructor
UnsortedType::UnsortedType()
//Pre: None.
//Post: List is Empty
{
	length = 0;
}

//Transformer
void UnsortedType::InsertItem(const ItemType& item)
//Pre: List has been initialized. List is not full
//item is not in list
//Post: item is in the list
{
	if (!IsFull())
	{
		info[length - 1] = item;
		length++;
	}
	else
	{
		cout << "List is full to InsertItem !" << endl;
		exit(1);
	}
}
void UnsortedType::DeleteItem(const ItemType& item)
//Pre: item's key has been initialized.
//An element in the list has a key that matches item's
//Post: No element in the list has a key that matches item's
{
	int location = 0;
    
  
	while (item.ComparedTo(info[location]) != EQUAL)
	{
		location++;
	} // location은 지금 현재 compare했을 때, 같은 지점을 가리킴
    
    //내 생각으론, 이렇게 코드를 짜는게 낫다.
	//for (location = 0;location < length;location++)
	//{
	//	if (item.ComparedTo(info[location]) == EQUAL)
	//	{
	//		break;
	//	}
	//}
	//if (location == length)
	//{
	//	cout << "There is no items like that" << endl;
	//	exit(1);
	//}

	info[location] = info[length - 1];
	length--;
	// 현재 List의 Last가 garbage값을 갖고 있을텐데 우짜지

}
//Observer
bool UnsortedType::IsFull() const
//Pre: List has been initialized.
//Post: Function value == (list is full).
{
	return (length == MAX_ITEMS); // 이러한 기법에 주의하자. if를 통해서 bool값을 반환하는 것이 아닌, 방법
}
int UnsortedType::LengthIs() const
{
	return length;
}
bool UnsortedType::RetriveItem(const ItemType& item)
{
	int location = 0;
	//내 생각의 흐름으론 이렇게 짜는게 낫다.
	//for (location = 0;location < length;length++)
	//{
	//	if (item.ComparedTo(info[location]) == EQUAL)
	//		return true;
	//}
	//if (location == length)
	//	return false;
    
    //아래 기법이 textbook의 기법인데, 꽤나 중요해 보인다.
    //판단척도를 여러 객체화하였다.
    
	bool found = false; // 일단은 못 찾았다/
	bool moreToSearch;
	moreToSearch = (location < length);
	while (moreToSearch && !found)
	{
		switch (item.ComparedTo(info[location]))
		{
		case LESS:
		case GREATER:
			location++;
			moreToSearch = (location < length);
			break;
		case EQUAL:
			found = true;
			break;
		}
	}
	return found;
}
//Iterator
void UnsortedType::ResetList()
{
	currentPos = 0;
}
const ItemType& UnsortedType::GetNextItem()
{
	currentPos++;
	return info[currentPos - 1];
 }

Delete와 Insert의 알고리즘을 좀 봐둘 필요가 있다.

UnsortedType에서 delete의 경우는 argument로 주어진 item을 찾아서 빼고, 맨 뒤(last)의 item을 그 자리에 갖다 넣었다.(당연히 length--)Insert의 경우엔 argument로 주어진 item을 그저 맨 뒤에 넣었다. (당연히 length++)

 

@SortedType

ADT나 GDT는 생략하겠다.

딜리트 인서트 리트라이브

#Implementation of "SortedType"

1. Implementation of InsertItem

void SortedType::InsertItem(const ItemType& item)
{
	int location = 0;
	bool moreToSearch = (location < length); // 이 구문을 주의할것. 언제나 true인것은 아니기에
	while (moreToSearch)
	{
		switch (item.ComparedTo(info[location]))
		{
		case LESS:
		case EQUAL:
			moreToSearch = false;
			break;
		case GREATER:
			moreToSearch = location < length;
			location++;
		}
	}
	for (int i = length;i > location;i--)
	{
		info[i] = info[i - 1];
	}
	info[location] = item;
	length++;
}

moreToSearch는 자주 나오는 boolean값이라 생각하자,

while()

{

switch()

}

를 자주 이용한다는 것 또한 기억할것.

인서트 알고리즘은 sorted니까 item이 들어갈 index를 찾고, 그 공간을 한칸씩 뒤로 밀어서 공간을 창출하고,

그 공간에 item을 집어넣는다.

 

2.Implementation of DeleteItem

void SortedType::DeleteItem(const ItemType& item)
{
	int location = 0;
	bool moreToSearch = (location < length);
	while (moreToSearch)
	{
		switch (item.ComparedTo(info[location]))
		{
		case EQUAL:
			moreToSearch = false;
			break;
		case LESS:
		case GREATER:
		default:
			moreToSearch = (location < length);
			location++;
		}
	}

	if (!(location < length))
	{
		cout << "There is no item like this" << endl;
	}
	else
	{
		for (int i = location;i < length-1;i++)
		{
			info[i] = info[i + 1];
		}
		length--;
	}
}

딜리트할 item이 어디있는지 찾고, 그 공간을 비우고, 한칸씩 앞으로 당긴다.

 

3.Implementation of RetriveItem by binary search

bool SortedType::RetriveItem(const ItemType& item) const
{
	int midpoint;
	int first = 0;
	int last = length - 1;
	bool moreToSearch = (first <= last);
	bool found = false;
	while (moreToSearch && !found)
	{
		midpoint = (first+last)/2;
		switch (item.ComparedTo(info[midpoint]))
		{
		case EQUAL:
			found = true;
			break;
		case LESS:
			last = midpoint - 1;
			moreToSearch = (first <= last);
			break;
		case GREATER:
			first = midpoint + 1;
			moreToSearch = (first <= last);
			break;
		}

		return found;
	}
}

moreToSearch가 first <= last 로 정의되어있는것과, while argument의 &&를 사용한것을 주의한다.

찾거나, 더이상 찾을게 없으면, 이라는 구문이다.