가자미의 개발이야기
C언어로 원형 연결 리스트 만들기 본문
개념
-마지막 노드가 첫번째 노드와 연결된 리스트.
-이전 노트 탐색이 편리.(연결 리스트는 매번 처음부터 탐색해야 됨)
※원형 연결리스트는 헤드노드 대신에 헤드포인터를 사용해 구현해 볼 것임.
헤더파일
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
#ifndef _CIRCULARLIST_
#define _CIRCULARLIST_
typedef struct CircularListNodeType
{
int data;
struct CircularListNodeType* pLink;
}CircularListNode;
typedef struct CircularListType
{
int currentElementCount;
CircularListNode* pLink; //Head Pointer
}CircularList;
CircularList* createCircularList();
void deleteCircularList(CircularList* pList);
int addCLElement(CircularList* pList, int position, CircularListNode element);
int removeCLElement(CircularList* pList, int position);
void clearCircularList(CircularList* pList);
int getCircularListLength(CircularList* pList);
CircularListNode* getCLElement(CircularList* pList, int position);
void displayCircularList(CircularList* pList);
#endif
#ifndef _COMMON_LIST_DEF_
#define _COMMON_LIST_DEF_
#define TRUE 1
#define FALSE 2
#endif
|
cs |
함수정의 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "circularlist.h"
int addCLElement(CircularList* pList, int position, CircularListNode element)
{
int ret = FALSE;
int i = 0;
CircularListNode* pPreNode = NULL, * pNewNode = NULL, * pLastNode = NULL;
if (pList != NULL) {
if (position >= 0 && position <= pList->currentElementCount) {
pNewNode = (CircularListNode*)malloc(sizeof(CircularListNode)); //새로운 노드 메모리 할당
if (pNewNode == NULL) {
printf("오류, 메모리할당 addCLElement()\n");
return ret;
}
*pNewNode = element;
pNewNode->pLink = NULL;
//포지션에 따라 노드 연결
if (position == 0) { //첫번째 자리에 노드 삽입할 경우
if (pList->currentElementCount == 0) { //노드가 하나도 없을 경우 원형 연결
pList->pLink = pNewNode;
pNewNode->pLink = pNewNode;
}
else {
pLastNode = pList->pLink;
while (pLastNode->pLink != pList->pLink) { //라스트노드가 마지막 위치에 해당하도록 루프
pLastNode = pLastNode->pLink;
}
pList->pLink = pNewNode; //처음 노드에 새 노드를 연결
pNewNode->pLink = pLastNode->pLink; //원래 노드를 새 노드 링크로 연결
pLastNode->pLink = pNewNode; //마지막노드를 새 노드로 연결
}
}
else {
pPreNode = pList->pLink;
for (i = 0; i < position - 1; i++) { //포저션 앞 위치까지 이동
pPreNode = pPreNode->pLink;
}
pNewNode->pLink = pPreNode->pLink;
pPreNode->pLink = pNewNode; //중간에 노드 삽입
}
pList->currentElementCount++;
ret = TRUE;
}
else {
printf("오류, 위치 인덱스-[%d] addCLElement()\n", position);
}
}
return ret;
}
int removeCLElement(CircularList* pList, int position)
{
int ret = FALSE;
int i = 0, arrayCount = 0;
CircularListNode* pPreNode = NULL, * pDelNode = NULL, * pLastNode = NULL;
if (pList != NULL) {
arrayCount = getCircularListLength(pList);
if (position >= 0 && position < arrayCount) {
if (position == 0) {
pDelNode = pList->pLink;
if (arrayCount == 1) { //노드가 하나 일 때,
free(pDelNode);
pList->pLink = NULL;
}
else {
pLastNode = pList->pLink;
while (pLastNode->pLink != pList->pLink) { //마지막 자리에 마지막 노드를 위치시키는 루프
pLastNode = pLastNode->pLink;
}
pLastNode->pLink = pDelNode->pLink; //원형 순환
pList->pLink = pDelNode->pLink;
free(pDelNode);
}
}
else { //포지션이 0이 아닐때
pPreNode = pList->pLink;
for (i = 0; i < position - 1; i++) {
pPreNode = pPreNode->pLink;
}
pDelNode = pPreNode->pLink;
pPreNode->pLink = pDelNode->pLink;
free(pDelNode);
}
pList->currentElementCount--;
ret = TRUE;
}
else {
printf("오류, 위치 인덱스-[%d] removeCLElement()\n", position);
}
}
return ret;
}
CircularListNode* getCLElement(CircularList* pList, int position) {
int i = 0;
CircularList* pNode = NULL;
if (pList != NULL) {
if (position >= 0 && position < pList->currentElementCount) {
pNode = pList->pLink;
for (i = 0; i < position; i++) {
pNode = pNode->pLink;
}
}
}
return pNode;
}
CircularList* createCircularList() {
CircularList* pReturn = NULL;
int i = 0;
pReturn = (CircularList*)malloc(sizeof(CircularList));
if (pReturn != NULL) {
memset(pReturn, 0, sizeof(CircularList));
}
else {
printf("오류, 메모리할당 createCircularList()\n");
return NULL;
}
return pReturn;
}
void displayCircularList(CircularList* pList)
{
int i = 0;
if (pList != NULL) {
printf("현재 원소의 개수: %d\n", pList->currentElementCount);
for (i = 0; i < pList->currentElementCount; i++) {
printf("[%d], %d\n", i, getCLElement(pList, i)->data);
}
}
else {
printf("원소가 없습니다.\n");
}
}
int getCircularListLength(CircularList* pList)
{
int ret = 0;
if (pList != NULL) {
ret = pList->currentElementCount;
}
return ret;
}
void deleteCircularList(CircularList* pList)
{
int i = 0;
if (pList != NULL) {
clearCircularList(pList);
free(pList);
}
}
void clearCircularList(CircularList* pList)
{
if (pList != NULL);
}
|
cs |
'Computer Science > 자료구조' 카테고리의 다른 글
| [자료구조] C언어로 배열 스택 구현하기 (0) | 2021.02.10 |
|---|---|
| [자료구조] 연결리스트로 다항식 구현하기 (0) | 2021.02.10 |
| C언어로 링크드리스트(연결리스트) 만들기 (0) | 2021.02.04 |
| C언어로 구현한 리스트 자료구조(ArrayList) (0) | 2021.02.03 |
| 알고리즘 분석 기준 (0) | 2021.01.29 |
'Computer Science/자료구조' Related Articles
more
