일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- Machine Learning
- deep learning
- 회귀
- AI
- 분류
- PCA
- GPT-4
- 지도학습
- regression
- OpenAI
- ChatGPT
- gpt
- 티스토리챌린지
- 오블완
- 머신러닝
- LG Aimers
- supervised learning
- LLM
- Classification
- 딥러닝
- LG Aimers 4th
- LG
- 해커톤
Archives
- Today
- Total
SYDev
[Data Structure] Chapter 05: 원형, 양방향 연결 리스트 본문
Data Structure & Algorithm/Data Structure
[Data Structure] Chapter 05: 원형, 양방향 연결 리스트
시데브 2023. 8. 12. 12:49단순 연결 리스트의 개념을 확장한 원형, 양방향 연결 리스트를 구현해보자.
자료구조를 구현할 때, 먼저 그림으로 그려보고 구조를 파악하는 것이 상당히 도움이 되었다.
원형 연결 리스트(Circular Linked List)
- 원형 연결 리스트의 기본 구조와 내부 함수는 다음과 같이 도식화할 수 있다.
파일명: 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
#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 LInsert(List * plist, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
if(plist -> tail == NULL)
{
newNode -> next = newNode;
plist -> tail = newNode;
}
else
{
newNode -> next = plist -> tail -> next;
plist -> tail -> next = newNode;
plist -> tail = newNode;
}
(plist -> numOfData)++;
}
void LInsertFront(List * plist, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
if(plist -> tail == NULL)
{
newNode -> next = newNode;
plist -> tail = newNode;
}
else
{
newNode -> next = plist -> tail -> next;
plist -> tail -> next = newNode;
}
(plist -> numOfData)++;
}
int LFirst(List * plist, Data * pdata)
{
if(plist -> tail == NULL) //tail이 NULL이 아니면 비어있을 수가 없는 구조
return FALSE;
plist -> before = plist -> tail;
plist -> cur = plist -> tail -> next;
*pdata = plist -> cur -> data;
return TRUE;
}
int LNext(List * plist, Data * pdata)
{
if(plist -> tail == NULL) //tail이 NULL이 아니면 비어있을 수가 없는 구조
return FALSE;
plist -> before = plist -> cur;
plist -> cur = plist -> cur -> next;
*pdata = plist -> cur -> data;
return TRUE;
}
Data LRemove(List * plist)
{
Node * rpos = plist -> cur;
Data rdata = rpos -> data;
if(rpos == plist -> tail)
{
if(rpos -> next = rpos)
{
plist -> tail = NULL;
}
else
plist->tail = plist->before;
}
plist->before->next = plist->cur->next;
plist->cur = plist->before;
free(rpos);
(plist -> numOfData)--;
return rdata;
}
int LCount(List * plist)
{
return plist -> numOfData;
}
파일명: CLinkedListMain.c
#include <stdio.h>
#include "CLinkedList.h"
int main(void)
{
// List의 생성 및 초기화 /////////////////////////////
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; 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);
}
}
printf("\n\n");
return 0;
}
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
1 3 5
문제 05-1
- 직원 정보를 등록할 수 있다. 직원 정보는 사번과 이름으로 구성
- 직원은 등록된 순서대로 당직을 선다.
- 직원의 이름과 하나의 숫자를 이용해서 당직자를 확인
파일명: Employee.h
#ifndef __EMPLOYEE_H__
#define __EMPLOYEE_H__
typedef struct __employee
{
char name[30];
int num;
} Employee;
#endif
파일명: WhoDuty.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "CLinkedList.h"
#include "Employee.h"
void WhoIsOnDuty(List * plist, char * name, int day);
int main(void)
{
// List의 생성 및 초기화 /////////////////////////////
List list;
ListInit(&list);
int i;
Data data;
data = (Employee*)malloc(sizeof(Employee));
strcpy(data->name,"상영");
data->num = 1;
LInsert(&list, data);
data = (Employee*)malloc(sizeof(Employee));
strcpy(data->name,"민수");
data->num = 2;
LInsert(&list, data);
data = (Employee*)malloc(sizeof(Employee));
strcpy(data->name,"현규");
data->num = 3;
LInsert(&list, data);
data = (Employee*)malloc(sizeof(Employee));
strcpy(data->name,"상호");
data->num = 4;
LInsert(&list, data);
//민수가 당직을 하고 7일 뒤 당직
WhoIsOnDuty(&list, "민수", 10);
//상호가 당직을 하고 3일 뒤 당직
WhoIsOnDuty(&list, "상호", 3);
printf("\n\n");
return 0;
}
void WhoIsOnDuty(List * plist, char * name, int day)
{
Employee * pemp = (Employee*)malloc(sizeof(Employee));
LFirst(plist, &pemp);
while(1)
{
if(strcmp(pemp->name , name) == 0)
break;
else
LNext(plist, &pemp);
}
Employee * pemp1 = pemp;
for(int i=0; i<day; i++)
{
LNext(plist, &pemp);
printf("%s ",pemp -> name);
}
printf("\n");
printf("%s가 당직을 선 후로 %d일 뒤 당직: %s \n", pemp1->name, day, pemp->name);
}
현규 상호 상영 민수 현규 상호 상영 민수 현규 상호
민수가 당직을 선 후로 10일 뒤 당직: 상호
상영 민수 현규
상호가 당직을 선 후로 3일 뒤 당직: 현규
나머지 헤더파일과 함수구현 파일은, 헤더파일에 Employee.h 헤더파일 선언문 추가에 typedef Data 변경을 제외하고 동일하다.
양방향 연결 리스트(Doubly Linked List)
- 원형 연결 리스트의 기본 구조와 내부 함수는 다음과 같이 도식화할 수 있다.
파일명: DBLinkedList.h
#ifndef __DB_LINKED_LIST_H__
#define __DB_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
struct _node * prev;
} Node;
typedef struct _DLinkedList
{
Node * head;
Node * cur;
int numOfData;
} DBLinkedList;
typedef DBLinkedList List;
void ListInit(List * plist);
void LInsert(List * plist, Data data);
int LFirst(List * plist, Data * pdata);
int LNext(List * plist, Data * pdata);
int LPrevious(List * plist, Data * pdata);
int LCount(List * plist);
#endif
파일명: DBLinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include "DBLinkedList.h"
void ListInit(List * plist)
{
plist -> head = NULL;
plist -> numOfData = 0;
}
void LInsert(List * plist, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
if(plist -> head == NULL)
{
newNode -> prev = NULL;
newNode -> next = NULL;
plist -> head = newNode;
}
else
{
newNode -> next = plist -> head;
plist -> head -> prev = newNode;
plist -> head = newNode;
newNode -> prev = NULL;
}
(plist -> numOfData)++;
}
int LFirst(List * plist, Data * pdata)
{
if(plist -> head == NULL)
return FALSE;
plist -> cur = plist -> head;
*pdata = plist -> cur -> data;
return TRUE;
}
int LNext(List * plist, Data * pdata)
{
if(plist -> cur -> next == NULL)
return FALSE;
else
{
plist->cur = plist->cur->next;
*pdata = plist->cur->data;
return TRUE;
}
}
int LPrevious(List * plist, Data * pdata)
{
if(plist -> cur -> prev == NULL)
return FALSE;
else
{
plist->cur = plist->cur->prev;
*pdata = plist->cur->data;
return TRUE;
}
}
int LCount(List * plist)
{
return plist -> numOfData;
}
파일명: DBLinkedListMain.c
#include <stdio.h>
#include "DBLinkedList.h"
int main(void)
{
List list;
int data;
ListInit(&list);
LInsert(&list, 1);
LInsert(&list, 2);
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsert(&list, 6);
LInsert(&list, 7);
LInsert(&list, 8);
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
while(LPrevious(&list, &data))
printf("%d ", data);
printf("\n\n");
}
return 0;
}
8 7 6 5 4 3 2 1 2 3 4 5 6 7 8
문제 05-2
- head와 tail에 dummy node가 있는 양방향 연결 리스트를 구현해보자.
- 똑같이 그림 그려서 구현했지만, 이번에는 생략하겠다.
파일명: DBDLinkedList.h
#ifndef __DBD_LINKED_LIST_H__
#define __DBD_LINKED_LIST_H__
#define TRUE 1
#define FALSE 0
typedef int Data;
typedef struct _node
{
Data data;
struct _node * next;
struct _node * prev;
} Node;
typedef struct _dbDLinkedList
{
Node * head;
Node * tail;
Node * cur;
int numOfData;
} DBDLinkedList;
typedef DBDLinkedList List;
void ListInit(List * plist);
void LInsert(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
파일명: DBDLinkedList.c
#include <stdio.h>
#include <stdlib.h>
#include "DBDLinkedList.h"
void ListInit(List * plist)
{
plist -> head = (Node*)malloc(sizeof(Node));
plist -> tail = (Node*)malloc(sizeof(Node));
plist -> head -> next = plist -> tail;
plist -> tail -> prev = plist -> head;
plist -> numOfData = 0;
}
void LInsert(List * plist, Data data)
{
Node * newNode = (Node*)malloc(sizeof(Node));
newNode -> data = data;
plist -> tail -> prev -> next = newNode;
newNode -> prev = plist -> tail -> prev;
plist -> tail -> prev = newNode;
newNode -> next = plist -> tail;
(plist -> numOfData)++;
}
int LFirst(List * plist, Data * pdata)
{
if(plist -> head -> next == plist -> tail)
return FALSE;
plist -> cur = plist -> head -> next;
*pdata = plist -> cur -> data;
return TRUE;
}
int LNext(List * plist, Data * pdata)
{
if(plist -> cur -> next == plist -> tail)
return FALSE;
plist -> cur = plist -> cur -> next;
*pdata = plist->cur->data;
return TRUE;
}
Data LRemove(List * plist) //연속 호출 불가능!!
{
Node * rpos = plist -> cur;
Data rdata = rpos -> data;
rpos -> next -> prev = rpos -> prev;
rpos -> prev -> next = rpos -> next;
plist -> cur = rpos -> prev;
free(rpos);
(plist -> numOfData)--;
return rdata;
}
int LCount(List * plist)
{
return plist -> numOfData;
}
파일명: DBDLinkedListMain.c
#include <stdio.h>
#include <stdlib.h>
#include "DBDLinkedList.h"
int main(void)
{
List list;
int data;
ListInit(&list);
LInsert(&list, 1);
LInsert(&list, 2);
LInsert(&list, 3);
LInsert(&list, 4);
LInsert(&list, 5);
LInsert(&list, 6);
LInsert(&list, 7);
LInsert(&list, 8);
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
printf("\n\n");
}
if(LFirst(&list, &data))
{
if(data%2 == 0)
LRemove(&list);
while(LNext(&list, &data))
{
if(data%2==0)
LRemove(&list);
}
}
if(LFirst(&list, &data))
{
printf("%d ", data);
while(LNext(&list, &data))
printf("%d ", data);
printf("\n\n");
}
free(list.head);
free(list.tail);
return 0;
}
1 2 3 4 5 6 7 8
1 3 5 7
참고자료
- 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11
'Data Structure & Algorithm > Data Structure' 카테고리의 다른 글
[Data Structure] Chapter 07: 큐(Queue) (0) | 2023.08.16 |
---|---|
[Data Structure] Chapter 06: 스택(Stack) (0) | 2023.08.15 |
[Data Structure] Chapter 04: 연결 리스트의 이해와 구현 (0) | 2023.08.11 |
[Data Structure] Chapter 03: 추상 자료형과 배열 기반 리스트 (0) | 2023.08.09 |
C언어에서의 구조체와 typedef (0) | 2023.08.08 |