Unsorted List

UnsortedList

장점 : 넣을 때 그냥 뒤에 넣으면 되서 간단함. 

단점 : 찾을 때 하나하나 크기 비교하면서 찾아야함. 

 

Operations

<Observers>

- IsFull

- LengthIs

- RetrieveItem

 

<Transformers>

- Make Empty

- InsertItem

- DeleteItem

 

<Iterators>

- ResetList

- GetNextItem

class UnsortedType

UnsortedType()

처음 생성하면 빈 리스트.

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

 

bool IsFull() 

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

 

int LengthIs()

int UnsortedType::LengthIs(){
	return length
    }

 

void RetrieveItem(ItemType& item, bool Found)

현재 위치 표시할 location. moreToSearch는 리스트 끝까지 한 번 돌아라.

아직 item을 못 찾았고, 리스트 끝까지 확인 안했을 때 item과 리스트 원소를 비교해보자. 

원소가 item과 다르면 (작거나 크거나) 위치를(location) 뒤로 한 칸 보내고 다시 확인하자.

이 때 location이 달라지니 moreToSearch에 반영해줘야한다.

찾던 원소를 발견하면 item에 원소를 저장한다.  

void UnsortedType::RetrieveItem(ItemType &item, bool found){
	int location = 0;
    bool moreToSearch = (location < length);    //한 바퀴 돌아라
    found = false;
    
    while(!found && moreToSearch){
    	switch(item.ComparedTo(info[location]){
        	case Less :                              //unsortedList니까 모든 원소 검사해야함.
            case Greater :                              // Less,Greater 한 번에 쓴거
            	location++;
                moreToSearch = (location < length);   //반복문 돌면서 location 달라지니까 반영해줘야함
                break;
            case Equal:
            	found = true;
            	item = info[location];
                break;
                }
            }
        }

 

InsertItem(ItemType newItem)

unsortedList니까 맨 뒤에 넣어주기만 하고 length+1

void UnsortedType::InsertItem(ItemType newItem){
	info[length] = newItem;
    length++;
    }

 

DeleteItem(ItemType item)

리스트를 돌면서 item이 있는지 확인한다. 리스트 원소가 item 이 아니면 위치를 하나씩 뒤로 옮긴다.

리스트에서 item 을 찾으면 그 자리에 리스트 맨 뒤에 있던 원소를 넣고 length -1

void UnsortedType::DeleteItem(ItemType item){
	int location = 0;
    while(item.ComparedTo(info[location])){
    	location++;
    }
    info[location] = info[length-1];
    length--;
    }

근데 이러면 리스트에 item이 없을 때 location이 계속 증가하는 문제가 생김. 따라서 item이 없는 경우까지 고려해야함.

 

ResetList()

currentPos는 리스트의 제일 처음 원소를 가리키는 놈이다.

void UnsortedType::ResetList(){
	currentPos = -1;
    }

 

GetNextItem()

현 위치에서 바로 다음 원소를 item에 저장한다.

void UnsortedType::GetNextItem(ItemType &item) {
    currentPos++;
    item = info[currentPos];
}