생성일: 2021년 10월 29일 오후 11:36
기존의 Linked Sorted List를 Circular 형식으로 몇 개의 함수를 재구성 하였다.
listData변수가 가장 마지막 노드를 가리키게 하고 마지막 노드는 첫번째 노드를 가르키게 한다.
//Linked Sorted List의 일부 함수들을 Circular Linked List로 재구성 한 것 => 이 코드 자체로 컴파일 되지 않는다.
//일부의 함수만 정의되어 있다.
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>
struct NodeType
{
ItemType info;
NodeType* next;
};
template<class ItemType>
void FindItem(NodeType<ItemType>* listData,
ItemType item,
NodeType<ItemType>*& location,
NodeType<ItemType>*& predLoc,
bool& found)
// Pre: List is not empty.
{
bool moreToSearch = true;
location = listData->next; //listData가 제일 끝을 가리키고 있기 때문에 제일 첫 노드를 가리키기도록 location 설정
predLoc = listData;
found = false;
while (moreToSearch && !found)
{
if (item < location->info)
moreToSearch = false;
else if (item == location->info)
found = true;
else
{
predLoc = location;
location = location->next;
moreToSearch = (location != listData->next); //다시 제일 처음 노드가 되기 전까지 반복문 수행
}
}
}
template<class ItemType>
void SortedType<ItemType>::InsertItem(ItemType item)
{
NodeType<ItemType>* newNode;
NodeType<ItemType>* predLoc;
NodeType<ItemType>* location;
bool found;
newNode = new NodeType<ItemType>;
newNode->info = item;
if (listData != NULL)
{
FindItem(listData, item, location, predLoc, found);
newNode->next = predLoc->next;
predLoc->next = newNode;
// If this is last node in list, reassign listData.
if (listData->info < item)
listData = newNode;
}
else // Inserting into an empty list.
{
listData = newNode;
newNode->next = newNode;
}
length++;
}
template<class ItemType>
void SortedType<ItemType>::DeleteItem(ItemType item)
{
NodeType<ItemType>* location;
NodeType<ItemType>* predLoc;
bool found;
FindItem(listData, item, location, predLoc, found);
if (predLoc == location) // Only node in list?
listData = NULL;
else
{
predLoc->next = location->next;
if (location == listData) // Deleting last node in list?
listData = predLoc;
}
delete location;
length--;
}