UnsortedList in Linked Structures

생성일: 2021년 10월 15일 오후 10:50

ADT Unsorted List Ooperations

Transformers

• MakeEmpty
• InsertItem
• DeleteItem

Observers

• IsFull
• LengthIs
• RetrieveItem

Iterators

• ResetList
• GetNextItem

구현

UnsortedType.h

#pragma once

template <class ItemType>
struct NodeType;

template <class ItemType>
class UnsortedType
{
public:
	UnsortedType();
	~UnsortedType();
	void MakeEmpty();
	bool IsFull() const;
	int LengthIs() const;
	void RetrieveItem(ItemType& item, bool& found);
	void InsertItem(ItemType item);
	void DeleteItem(ItemType item);
	void ResetList();
	void GetNextItem(ItemType& item);

private:
	NodeType<ItemType>* listData;
	int length;
	NodeType<InsertItem>* currentPos;
};

//정의

template <class ItemType>
UnsortedType<ItemType>::UnsortedType()
{
	length = 0;
	listData = nullptr;
	currentPos = nullptr;
}

template <class ItemType>
UnsortedType<ItemType>::~UnsortedType()
{
	MakeEmpty();
}

template <class ItemType>
void UnsortedType<ItemType>::MakeEmpty()
{
	NodeType<ItemType>* tempPtr;

	while (listData != nullptr)
	{
		tempPtr = listData;
		listData = listData->next;
		delete tempPtr;
	}
	length = 0;
}

template <class ItemType>
bool UnsortedType<ItemType>::IsFull() const
{
	NodeType<ItemType>* location;
	try
	{
		location = new NodeType<ItemType>;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception)
	{
		return true;
	}
}

template <class ItemType>
int UnsortedType<ItemType>::LengthIs() const
{
	return length;
}

template <class ItemType>
void UnsortedType<ItemType>::RetrieveItem(ItemType& item, bool& found)
{
	bool moreToSearch;
	NodeType<ItemType>* location;

	location = listData;
	found = false;
	moreToSearch = (location != nullptr);

	//반복문을 돌면서 item과 같은 값을 찾는다. location이 null이면 반복문 멈춘다.
	while (moreToSearch && !found)
	{
		if (item == location->info)
		{
			found = true;
			item = location->info;
		}
		else
		{
			location = location->next;
			moreToSearch = (location != nullptr);
		}
	}
}

template <class ItemType>
void UnsortedType<ItemType>::InsertItem(ItemType item)
{
	NodeType<ItemType>* location;

	location = new NodeType<ItemType>;
	location->info = item;
	location->next = listData;
	listData = location;
	length++;
}

template <class ItemType>
void UnsortedType<ItemType>::DeleteItem(ItemType item)
{
	NodeType<ItemType>* location = listData;
	NodeType<ItemType>* tempLocation;	//지울 노드

	//첫 번째 노드를 확인
	if (item == listData->info) 
	{
		tempLocation = location;
		listData = listData->next;
	}
	else 
	{
		while (!(item == (location->next)->info))	//다음 노드의 info와 item이 같은지 확인
			location = location->next;

		//다음 노드의 info가 찾고 있던 item과 같았을 때
		tempLocation = location->next;
		location->next = (location->next)->next;
	}

	delete tempLocation;
	length--;

	// 이 함수의 단점 : list안에 지우고자 할 Item이 무조건 있어야 함 why? 끝까지 못찾으면 location->next 가 nullptr이 됨 => nullptr의 info에 접근 => 에러 발생
	// location->next가 nullptr일 때 조건문으로 예외 처리를 해주면 해결 가능 할 듯
}

template <class ItemType>
void UnsortedType<ItemType>::ResetList()
{
	currentPos = nullptr;
}

template <class ItemType>
void UnsortedType<ItemType>::GetNextItem(ItemType& item)
{
	if (currentPos == nullptr)
		currentPos = listData;
	else
		currentPos = currentPos->next;

	item = currentPos->info;
}

Main.cpp

#include <iostream>
#include "StackType.h"
#include "QueType.h"
#include "UnsortedType.h"

using namespace std;

int main()
{
	
	UnsortedType<char> myUnsortedList;
	myUnsortedList.InsertItem('A');
	myUnsortedList.InsertItem('B');
	myUnsortedList.InsertItem('C');

	cout <<"Length : " << myUnsortedList.LengthIs() << endl;

	cout << "Delete test" << endl;

	char check = 'B';
	myUnsortedList.DeleteItem(check);
	cout << "Length : " << myUnsortedList.LengthIs() << endl;
	
	char test;
	myUnsortedList.GetNextItem(test);
	cout << test << endl;
	myUnsortedList.GetNextItem(test);
	cout << test << endl;

}