생성일: 2021년 10월 16일 오전 12:13
#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;
}
#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;
}