반응형
원형 연결 리스트 (Circular Linked List)
Main.h
#include <stdio.h>
#include "CLinkedList.h"
int main(void)
{
// 원형 연결 리스트의 생성 및 초기화
List list;
int data, i, nodeNum;
ListInit(&list);
// 리스트에 5개의 데이터를 저장
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsertFront(&list, 2);
LInsertFront(&list, 1);
// 리스트에 저장된 데이터를 연속 3회 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
for (i = 0; i < LCount(&list) * 3 - 1; i++) {
if (LNext(&list, &data))
printf("%d ", data);
}
}
printf("\n");
// 2의 배수를 찾아서 모두 삭제
nodeNum = LCount(&list);
if (nodeNum != 0)
{
LFirst(&list, &data);
if (data % 2 == 0)
LRemove(&list);
for (i = 0; i < nodeNum - 1; i++)
{
LNext(&list, &data);
if (data % 2 == 0)
LRemove(&list);
}
}
// 현재 데이터 1회 출력
if (LFirst(&list, &data))
{
printf("%d ", data);
for (i = 0; i < LCount(&list) - 1; i++)
{
if (LNext(&list, &data))
printf("%d ", data);
}
}
return 0;
}
CLinkedList.h
#ifndef __C_LINKED_LIST_H__
#define __C_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node* next;
} Node;
typedef struct _CLL
{
Node* tail;
Node* cur;
Node* before;
int numOfData;
} CList;
typedef CList List;
void ListInit(List* plist);
void LInsert(List* plist, Data data); // 꼬리에 노드를 추가.
void LInsertFront(List* plist, Data data); // 머리에 노드를 추가.
int LFirst(List* plist, Data* pdata);
int LNext(List* plist, Data* pdata);
Data LRemove(List* plist);
int LCount(List* plist);
#endif
CLinkedList.c
구현해보기
#ifdef _MSC_YER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"
void ListInit(List* plist)
{
}
void LInsert(List* plist, Data data)
{
}
void LInsertFront(List* plist, Data data)
{
}
int LFirst(List* plist, Data* pdata)
{
}
int LNext(List* plist, Data* pdata)
{
}
Data LRemove(List* plist)
{
}
int LCount(List* plist)
{
}
구현
#ifdef _MSC_YER
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
#include <stdlib.h>
#include "CLinkedList.h"
void ListInit(List* plist)
{
plist->tail = NULL;
plist->cur = NULL;
plist->before = NULL;
plist->numOfData = 0;
}
void LInsertFront(List* plist, Data data) // 새 노드를 머리에 저장
{
Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
newNode->data = data; // 새 노드에 데이터 저장
if (plist->tail == NULL) // 첫 번째 노드라면,
{
plist->tail = newNode; // tail이 새 노드를 가리키게 한다.
newNode->next = newNode; // 새 노드 자신을 가리키게 한다.
}
else // 두 번째 이후의 노드라면,
{
newNode->next = plist->tail->next; // 새 노드와 4가 저장된 노드 연결
plist->tail->next = newNode; // 2가 저장된 노드와 새 노드 연결
}
(plist->numOfData)++;
}
void LInsert(List* plist, Data data) // 새 노드를 꼬리에 저장
{
Node* newNode = (Node*)malloc(sizeof(Node)); // 새 노드 생성
newNode->data = data; // 새 노드에 데이터 저장
if (plist->tail == NULL) // 첫 번째 노드라면,
{
plist->tail = newNode; // tail이 새 노드를 가리키게 한다.
newNode->next = newNode; // 새 노드 자신을 가리키게 한다.
}
else // 두 번째 이후의 노드라면,
{
newNode->next = plist->tail->next; // 새 노드와 4가 저장된 노드 연결
plist->tail->next = newNode; // 2가 저장된 노드와 새 노드 연결
plist->tail = newNode; // LInsertFront 함수와의 유일한 차이점
}
(plist->numOfData)++;
}
int LFirst(List* plist, Data* pdata)
{
if (plist->tail == NULL) // 저장된 노드가 없다면
return FALSE;
plist->before = plist->tail; // before가 꼬리를 가리키게 한다.
plist->cur = plist->tail->next; // cur이 머리를 가리키게 한다.
*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환.
return TRUE;
}
int LNext(List* plist, Data* pdata)
{
if (plist->tail == NULL) // 저장된 노드가 없다면
return FALSE;
plist->before = plist->cur; // before가 다음 노드를 가리키게 한다.
plist->cur = plist->cur->next; // cur이 다음 노드를 가리키게 한다.
*pdata = plist->cur->data; // cur이 가리키는 노드의 데이터 반환.
return TRUE;
}
Data LRemove(List* plist)
{
Node* rpos = plist->cur;
Data rdata = rpos->data;
if (rpos == plist->tail) // 삭제 대상을 tail이 가리킨다면
{
if (plist->tail == plist->tail->next) // 그리고 마지막 남은 노드라면
plist->tail = NULL;
else
plist->tail = plist->before;
}
plist->before->next = plist->cur->next; // before의 next를 cur 다음과 연결
plist->cur = plist->before; // cur를 before로 이동(이전 데이터로 이동)
free(rpos);
(plist->numOfData)--;
return rdata;
}
int LCount(List* plist)
{
return plist->numOfData;
}
반응형