자료구조
원형 연결리스트(CLinkedList) - C++
귀건
2020. 9. 2. 00:00
728x90
반응형
후기. 연결리스트와 유사한 점이 많다보니, 연결리스트 이후에 짤 때 큰 어려움은 없었다.
이전 자료구조들을 template로 짰는데 단순하게 int 형으로만 테스트를 진행해서 이번에는 float형으로도 되는지 확인해봤다. string은 class라 그런지 안되는데 이유를 찾아볼 필요가 있을 것 같다. C에서도 문자열 처리는 어려웠는데 C++에서도 마찬가지인듯 싶다.
4학년 늘그막에 다시 복습을 하는 내가 초심을 잃지 않길..
CLinkedList.h
#ifndef CLINKEDLIST_H
#define CLINKEDLIST_H
template
<typename T>
class List
{
private:
typedef struct Node_
{
T data;
Node_* next;
}Node;
int numOfData;
Node* tail;
Node* cur;
Node* before;
public:
List()
{
numOfData = 0;
tail = nullptr;
cur = nullptr;
before = nullptr;
}
void LInsert(T data);
void LInsertFront(T data);
bool LFirst(T& pdata);
bool LNext(T& pdata);
T LRemove();
const int LCount()
{
return numOfData;
}
};
#endif
CLinkedList.cpp
#include "CLinkedList.h"
template
<typename T>
void List<T>::LInsert(const T data) //꼬리에 삽입
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->data = data;
if (tail == nullptr)
{
tail = NewNode;
NewNode->next = tail;
}
else
{
NewNode->next = tail->next;
tail->next = NewNode;
tail = NewNode;
}
numOfData++;
}
template
<typename T>
void List<T>::LInsertFront(const T data) // 머리 == 꼬리 + 1 에 삽입
{
Node* NewNode = (Node*)malloc(sizeof(Node));
NewNode->data = data;
if (tail == nullptr)
{
tail = NewNode;
NewNode->Next = tail;
}
else
{
NewNode->next = tail->next;
tail->next = NewNode;
}
numOfData++;
}
template
<typename T>
bool List<T>::LFirst(T& pdata)
{
if (tail->next == nullptr)
{
return false;
}
else
{
before = tail;
cur = tail->next;
pdata = cur->data;
return true;
}
}
template
<typename T>
bool List<T>::LNext(T& pdata)
{
if(tail == nullptr)
{
return false;
}
before = cur;
cur = cur->next;
pdata = cur->next->data;
return true;
}
template
<typename T>
T List<T>::LRemove()
{
//예외 1 삭제할 노드가 tail 인 경우
Node* dnode = cur;
T rdata = cur->data;
if (cur == tail)
{
if (cur->next != cur)
{
before->next = dnode->next;
tail = before;
}
else //예외 2 노드가 하나만 남은 경우(노드가 하나가 남은 경우에는 cur이 tail임)
{
tail = nullptr;
}
}
before->next = dnode->next;
cur = before;
free(dnode);
numOfData--;
return rdata;
free(dnode);
}
main.cpp
#include <iostream>
using namespace std;
#include "CLinkedList.cpp"
int main()
{
List<int> CList;
cout << CList.LCount() << endl;
for (int i = 0; i < 10; i++)
{
CList.LInsert(i);
}
cout << CList.LCount() << endl;
int a;
for (int i = 0; i < 10; i++)
{
CList.LFirst(a);
cout << a << " ";
CList.LRemove();
cout << CList.LCount() << endl;
}
List<float> CListF;
for (int i = 0; i < 10; i++)
{
CListF.LInsert(i + 0.1);
}
float b;
for (int i = 0; i < 10; i++)
{
CListF.LFirst(b);
cout << b << " ";
CListF.LRemove();
cout << CListF.LCount() << endl;
}
return 0;
}
728x90
반응형