SortedList in Linked Structures

생성일: 2021년 10월 16일 오전 12:13

ADT Unsorted List Operations

Transformers

• MakeEmpty
• InsertItem
• DeleteItem

Observers

• IsFull
• LengthIs
• RetrieveItem

Iterators

• ResetList
• GetNextItem

구현

SortedType.h

#pragma once
template <class ItemType>
struct NodeType;

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

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

//정의
template <class ItemType>
SortedType<ItemType>::SortedType()
{
	length = 0;
	listData = nullptr;
	currentPos = nullptr;
}

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

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

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

template <class ItemType>
bool SortedType<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 SortedType<ItemType>::LengthIs() const
{
	return length;
}

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

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

	while (moreToSearch && !found)
	{
		if (location->info < item)
		{
			location = location->next;
			moreToSearch = (location != nullptr);
		}
		else if (location->info == item)
		{
			found = true;
			item = location->info;
		}
		else
		{
			moreToSearch = false;
		}
	}
}

template <class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
	NodeType<ItemType>* newNode;
	NodeType<ItemType>* predLoc;
	NodeType<ItemType>* location;
	bool moreToSearch;

	location = listData;
	predLoc = nullptr;
	moreToSearch = (location != nullptr);

	//넣을 자리 찾기
	while (moreToSearch)
	{
		if (location->info < item)
		{
			predLoc = location;
			location = location->next;
			moreToSearch = (location != nullptr);
		}
		else
			moreToSearch = false;
	}
	
	//알맞은 자리에 새 노드를 넣고 앞의 노드와 뒤의 노드 연결하기
	newNode = new NodeType<ItemType>;
	newNode->info = item;
	
	if (predLoc == nullptr)	//넣어야할 위치가 첫번째 자리 일 때
	{
		newNode->next = listData;
		listData = newNode;
	}
	else
	{
		newNode->next = location;
		predLoc->next = newNode;
	}
	length++;
	
}

template <class ItemType>
void SortedType<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))
			location = location->next;

		tempLocation = location->next;
		location->next = (location->next)->next;
	}

	delete tempLocation;
	length--;
}

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

template <class ItemType>
void SortedType<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"
#include "SortedType.h"

using namespace std;

int main()
{
	cout << "Sorted List test" << endl;
	SortedType<int> mySortedList;
	mySortedList.InsertItem(4);
	mySortedList.InsertItem(1);
	mySortedList.InsertItem(3);
	mySortedList.InsertItem(2);
	cout << "Length : " << mySortedList.LengthIs() << endl;

	int num;
	mySortedList.GetNextItem(num);
	cout << num << endl;
	mySortedList.GetNextItem(num);
	cout << num << endl;
	mySortedList.GetNextItem(num);
	cout << num << endl;
	mySortedList.GetNextItem(num);
	cout << num << endl;

	cout << "Delete test" << endl;
	num = 2;
	mySortedList.DeleteItem(num);
	mySortedList.ResetList();
	mySortedList.GetNextItem(num);
	cout << num << endl;
	mySortedList.GetNextItem(num);
	cout << num << endl;
	mySortedList.GetNextItem(num);
	cout << num << endl;

}