촉촉한초코칩
09. 리스트 본문
09-1 선형 리스트
리스트 : 데이터를 순서대로 나열한 (줄지어 늘어놓은) 자료구조
- 선형 리스트 (linear list), 연결 리스트 (linked list)
- 리스트의 데이터 : 노드(node), 요소(element)
- 각각의 노드 : 데이터와 다음 노드를 가리키는 포인터를 가지고 있다.
- 첫번째 노드 : 머리 노드(head node), 마지막 노드 : 꼬리 노드(tail node)
- 하나의 노드에 대해 바로 앞에 있는 노드 : 앞쪽 노드 (predecessor node), 바로 뒤에 있는 다음 노드 : 다음 노드 (successor node)
배열로 선형 리스트 만들기
- 다음 노드 꺼내기 : 1만큼 큰 인덱스를 갖는 요소에 접근하기
- 노드 삽입, 삭제 과정 : 모든 요소를 하나씩 뒤로 밀거나 앞으로 당겨야 한다.
- > 쌓이는 데이터의 크기를 미리 알아야 하며, 데이터의 삽입/삭제에 따라 데이터를 모두 옮겨야 하므로 효율이 좋지 않다.
09-2 포인터로 연결 리스트 만들기
연결 리스트에 대해 데이터를 삽입할 때 노드용 객체를 만들고, 삭제할 때 노드용 객체를 없애면 데이터를 밀고 당기는 문제를 해결할 수 있다.
* 노드 구조
typedef struct __node {
Member data; //데이터
struct __node *next; //다음 노드를 가리키는 포인터
} Node;* 자기 참조(self-referential) 형
- 자기 자신과 같은 자료형의 객체를 가리키는 데이터를 가지고 있는 자료구조
- 멤버 next : 해당 노드의 다음 노드를 가리키는 포인터
- 다음 노드를 갖지 않는 꼬리 노드는 next에 널(NULL)값을 대입한다.
//포인터로 만든 연결 리스트 (헤더)
#ifndef __LinkedList
#define __LinkedList
#include "Member.h"
//노드
typedef struct __node {
Member data; //데이터
struct __node *next; //뒤쪽 포인터(다음 노드에 대한 포인터)
} Node;
//연결 리스트
typedef struct {
Node *head; //머리 노드에 대한 포인터
Node *crnt; //선택한 노드에 대한 포인터 (검색한 노드를 선택하고 삭제하는 용도로 사용)
} List;
//연결 리스트 초기화
void Initialize(List *list);
//함수 compare로 x와 같은 노드 검색
Node *search(List *list, const Member *x, int compare(const Member *x, const Member *y));
//머리에 노드 삽입
void InsertFront(List *list, const Member *x);
//꼬리에 노드 삽입
void InsertRear(List *list, const Member *x);
//머리 노드 삭제
void RemoveFront(List *list);
//꼬리 노드 삭제
void RemoveRear(List *list);
//선택한 노드 삭제
void RemoveCurrent(List *list);
//모든 노드 삭제
void Clear(List *list);
//선택한 노드의 데이터 출력
void PrintCurrent(const List *list);
//선택한 노드의 데이터를 출력 (줄 바꿈 문자 포함)
void PrintLnCurrent(const List *list);
//모든 노드의 데이터를 리스트 순서대로 출력
void Print(const List *list);
//연결 리스트 종료
void Terminate(List *list);
#endif//포인터로 만든 연결 리스트 (소스)
#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "LinkedList.h"
//노드를 동적으로 생성
//Node형 객체를 만들고 만든 객체의 포인터를 반환한다.
static Node *AllocNode(void) {
return calloc(1, sizeof(Node));
}
//n이 가리키는 노드의 각 멤버에 값 설정
//n으로 전달받은 포인터가 가리키는 Node형 객체에 x가 가리키는 값을 대입
//n의 next에 세번째 매개변수로 전달받은 next 대입
static void SetNode(Node *n, const Member *x, const Node *next) {
n->data = *x; //데이터
n->next = next; //뒤쪽 데이터
}
//연결 리스트 초기화
//머리 노드에는 빈 연결 리스트를 만든다.
void Initialize(List *list) {
list->head = NULL; //머리 노드
list->crnt = NULL; //선택한 노드
}
연결 리스트가 비어있는지 확인하는 방법
list->head == NULL노드가 1개인 연결 리스트를 판단하는 방법
- 머리 노드는 리스트의 꼬리 노드이기도 하다.
- 따라서 list->head가 가리키는 노드 뒤쪽 포인터 next가 널값인지 확인하면 1개인지 판단할 수 있다.
list->head->next == NULL노드가 2개인 연결 리스트 판단하기
- list->head가 가리키는 노드 A의 next는 노드 B를 가리킨다.
- 꼬리 노드 B의 next는 널 값을 가지고 있으므로 A의 다음 노드가 null인지 확인해서 판단한다.
list->head->next->next == NULL
//노드 A의 데이터 : list->head->data
//노드 B의 데이터 : list->head->next->data머리 노드인지 판단하기
- 자료형이 Node *형인 변수 p는 리스트의 노드 중 하나를 가리킨다.
p == list->head //p가 가리키는 노드가 머리 노드인지 확인한다.꼬리 노드인지 판단하기
- 자료형이 Node *형인 변수 p는 리스트의 노드 중 하나를 가리킨다.
p->next == NULL //p가 가리키는 노드가 꼬리 노드인지 확인한다.
검색 수행하는 search 함수
- 어떤 조건을 만족하는 노드를(검색할 노드) 만날 때까지 머리 노드부터 검색한다.
- 반환하는 값 : 찾은 노드에 대한 포인터 > 검색에 실패하면 널을 반환한다.
- 종료 조건
- 검색 조건을 만족하는 노드를 찾지 못하고 꼬리 노드를 지나가기 직전인 경우
- 검색 조건을 만족하는 노드를 찾은 경우
//compare 함수를 사용해 x를 검색한다.
//list : 검색 대상인 연결 리스트를 가리키는 포인터
//x : 검색하는 키 값을 저장한 데이터를 가리키는 포인터
//compare : 두번째 매개변수 x가 가리키는 객체와 연결 리스트의 노드와 데이터를 비교하는 함수를 가리키는 포인터
검색에 성공하면 0을 반환한다.
Node *search(List *list, const Member *x, int compare(const Member *x, const Member *y)) {
//스캔하고 있는 노드를 가리키는 변수 ptr을 list->head로 초기화
//ptr이 가리키는 노드는 list->head가 가리키고 있는 머리 노드이다.
Node *ptr = list->head;
//ptr값이 널이 아니면 루프 if문을 실행한다.
//ptr 값이 널이면 스캔할 노드가 없음을 의미하므로 while문을 빠져나온다.
while(ptr != NULL) {
//스캔하고 있는 노드의 데이터 (ptr->data)와 x가 가리키는 데이터를 비교한다.
if(compare(&ptr->data, x) == 0) { //키 값이 같은 경우
//같은 경우 list->crnt에 ptr을 대입하고 찾은 노드에 대한 포인터인 ptr을 반환한다.
list->crnt = ptr;
return ptr; //검색 성공
}
ptr = ptr->next; //다음 노드 선택
}
return NULL; //검색 실패
}
머리/꼬리에 노드를 삽입하는 InsertFront, InsertRear 함수
- InsertRear 함수는 먼저 리스트가 비어 있는지 아닌지(list->head == NULL) 확인하고 작업을 수행한다.
//머리에 노드 삽입
void InsertFront (List *list, const Member *x) {
//삽입 전에 머리 노드에 대한 포인터를 ptr에 대입한다.
Node *ptr = list->head;
//삽입할 노드를 AllocNode 함수로 만들고 삽입할 노드를 가리키도록 list->head에 삽입할 노드를 넣는다.
list->head = list->crnt = AllocNode();
//SetNode 함수를 호출하여 값을 설정한다. 삽입한 후, 머리 노드의 다음을 가리키는 포인터 값을 ptr에 업데이트한다.
SetNode(list->head, x, ptr);
}
//꼬리에 노드 삽입
void InsertRear (List *list, const Member *x) {
if(list->head == NULL) //리스트가 비어 있는 경우
InsertFront(ist, x); //머리에 삽입
else { //비어 있지 않은 경우
Node *ptr = list->head;
//꼬리 노드를 찾는다.
//머리 노드를 가리키도록 초기화한 ptr이 가리키는 노드를 계속해서 다음 노드를 가리키도록 업데이트한다. (노드를 처음부터 차례대로 스캔)
//이때 ptr이 가리키는 노드는 꼬리 노드 F이다.
while(ptr->next != NULL)
ptr = ptr->next;
//삽입할 노드를 AllocNode 함수로 만든다.
//삽입하기 전의 꼬리 노드의 다음 포인터 ptr->next 가리키는 노드에 삽입한 후 꼬리 노드를 대입한다.
ptr->next = list->crnt = AllocNode();
//SetNode 함수를 호출해 꼬리 노드 값을 설정하고 다음 노드에는 null을 대입해 꼬리 노드가 어떤 노드도 가리키지 않도록 한다.
SetNode(ptr->next x, NULL);
}
}
머리/꼬리 노드를 삭제하는 RemoveFront, RemoveRear 함수
- RemoveFront 함수는 리스트가 비어 있지 않은 경우(list->head != NULL)에만 삭제를 실행한다.
만약 리스트에 노드가 1개만 있어도 오류 없이 삭제할 수 있다.
삭제하기 전의 머리 노드 = 꼬리노드 이므로 다음 노드를 가리키는 list->head->next의 값은 널이다.
널을 list->head에 대입하면 리스트는 빈 상태가 된다. - RemoveRear 함수는 리스트에 노드가 몇 개 있는지에 따라 그 경우에 해당하는 작업을 수행한다.
//머리 노드를 삭제하는 함수
void RemoveFront(List *list) {
if(list->head != NULL) {
//두번쨰 노드에 대한 포인터 값을 대입하기
Node *ptr = list->head->next;
//머리 노드 삭제
free(list->head);
//머리 노드에 ptr 값을 넣는다.
list->head = list->crnt = ptr;
}
}
//꼬리 노드를 삭제하는 함수
void RemoveRear (List *list) {
//리스트에 노드가 1개인 경우, 머리 노드를 삭제하는 것과 동일하므로 RemoveFront 함수를 수행한다.
if(list->head != NULL) {
if((list->head)->next == NULL)
RemoveFront(list);
else {
//꼬리 노드와 꼬리노드로부터 두번째 노드를 찾는다.
Node *ptr = list->head;
//현재 스캔하고 있는 노드의 '앞에 있는 노드'를 가리키는 변수 pre를 추가한다.
Node *pre;
//while문이 종료하면 pre는 업데이트된 꼬리 노드를, ptr은 메모리 해제된 꼬리 노드를 가리키게 된다.
while(ptr->next != NULL) {
pre = ptr;
ptr = ptr->next;
}
//꼬리 노드부터 두번째 노드의 다음을 가리키는 포인터에 널을 대입하고
pre->next = NULL;
//꼬리 노드 메모리 해제
free(ptr);
list->crnt = pre;
}
}
}
선택한 노드를 삭제하는 RemoveCurrent 함수
- 현재 선택한 노드(list->crnt)가 가리키는 노드를 삭제한다.
- 만약, 선택한 노드가 머리 노드인 경우 > RemoveFront 함수 수행한다.
//선택한 노드를 삭제하는 함수
void RemoveCurrent(List *list) {
if(list->head != NULL) {
if(list->crnt == list->head)
RemoveFront(list);
else {
//선택한 노드의 앞 노드를 찾는다.
Node *ptr = list->head;
//머리노드부터 스캔 시작
//선택한 노드 ptr의 다음 노드를 가리키는 포인터 ptr->next가 list->crnt와 같을 때까지 반복
//while문이 종료하면 ptr은 삭제하기 위해 선택한 노드의 앞쪽 노드를 가리키게 된다.
while(ptr->next != list->crnt)
ptr = ptr->next;
//삭제하기 위해 선택한 노드의 다음 노드 포인터 list->crnt->next를 ptr의 다음 노드에 대입한다.
//ptr의 다음 노드 포인터가 가리키는 노드가 삭제할 노드의 다음 노드로 업데이트 된다.
ptr->next = list->crnt->next;
//삭제할 노드 메모리 해제
free(list->crnt);
lit->crnt = ptr;
}
}
}
//모든 노드 삭제
//연결 리스트가 head == NULL이 될 때까지 머리 요소 삭제 작업을 반복한다.
void Clear(List *list) {
while(list->head != NULL)
RemoveFront(list);
list->crnt = NLLL;
}
//선택한 노드의 데이터 출력
void PrintCurrent (const List * list) {
if(list->crnt == NULL)
printf("선택한 노드가 없습니다.");
else
PrintMember(&list->crnt->data);
}
//선택한 노드의 데이터 출력 (줄바꿈 문자 포함)
void PrintLnCurrent (const List *list) {
PrintCurrent(list);
putchar('\n');
}
//모든 노드의 데이터를 리스트 순으로 출력
void Print(const List *list) {
if(list->head == NULL)
puts("노드가 없습니다.");
else {
Node *ptr = list->head;
puts("모두 보기");
while(ptr != NULL) {
PrintLnMember(&ptr->data);
ptr = ptr->next;
}
}
}
//연결 리스트를 종료하는 함수
void Terminate(List *list) {
Clear(list);
}
자기 참조 구조체와 typedef 선언
- 자기 참조 구조체 : 자기 자신과 같은 자료형의 객체를 가리키는 포인터, (struct __node)를 멤버로 가지고 있다.
- struct __node에 대해 typedef로 Node라고 이름을 다시 정의한다.
- 이때, 멤버 next를 struct __node가 아닌 Node *으로 선언하면 아직 Node형의 typedef 선언이 종료되지 않았으므로 에러가 난다.
//노드
typedef struct __node {
Member data; //데이터
struct __node *next; //struct __node형 객체를(다음 노드) 가리키는 포인터
} Node;
연결 리스트(Linkedlist)를 사용한 프로그램
#include <stdio.h>
#include "Member.h"
#include "LinkedList.h"
//메뉴
typdef enum {
TERMINATE, INS_FRONT, INS_REAR, RMV_FRONT, RMV_REAR, PRINT_CRNT,
RMV_CRNT, SRCH_NO, SRCH_NAME, PRINT_ALL, CLEAR
} Menu;
//메뉴 선택
Menu SelectMenu (void) {
int i, ch;
char *mstring[] = {
"머리에 노드 삽입", "꼬리에 노드 삽입", "머리 노드 삭제",
"꼬리 노드 삭제", "선택한 노드 출력", "선택한 노드 삭제",
"번호로 검색", "이름으로 검색", "모든 노드 출력", "모든 노드 삭제", };
do {
for(i = TERMINATE; i < CLEAR; i++) {
printf("(%2d) %-18.18s ", i+1, mstring[i]);
if((i%3) == 2)
putchar('\n');
}
printf("(0) 종료 : ");
scanf("%d", &ch);
} while(ch < TERMINATE || ch > CLEAR);
return(Menu)ch;
}
//메인
int main(void) {
Menu menu;
List list;
Initialize(&list); //연결 리스트 초기화
do {
Member x;
switch(menu = SelectMenu()) {
//머리에 노드 삽입
case INS_FRONT :
x = ScanMember("머리에 삽입", MEMBER_NO | MEMBER_NAME);
InsertFront(&list, &x);
break;
//꼬리에 노드 삽입
case INS_REAR:
x = ScanMember("꼬리에 삽입", MEMBER_NO | MEMBER_NAME);
InsertRear(&list, &x);
brek;
//머리 노드 삭제
cae RMV_FRONT:
RemoveFront(&list);
break;
//꼬리 노드 삭제
case RMV_REAR:
RemoveRear(&list);
break;
//선택한 노드 데이터 출력
case PRINT_CRNT:
PrintLnCurrent(&list);
break;
//선택한 노드 삭제
case RMV_CRNT:
RemoveCurrent(&list);
break;
//번호로 검색
case SRCH_NO:
x = ScanMember("검색", MEMBER_NO);
if(search(&list, &x, MemberNoCmp) != NULL)
PrintLnCurrent(&list);
else
puts("그 번호의 데이터가 없습니다.");
break;
//이름으로 검색
case SRCH_NAME:
x = ScanMember("검색", MEMBER_NAME);
if(search(&list, &x, MemberNameCmp) != NULL)
PrintLnCurrent(&list);
else
puts("그 이름의 데이터가 없습니다.");
break;
//모든 노드의 데이터 출력
case PRINT_ALL:
Print(&list);
break;
//모든 노드 삭제
case CLEAR:
Clear(&list);
break;
}
} while(menu != TERMINATE);
Terminate(&list); //연결 리스트 종료
return 0;
}
09-3 커서로 연결 리스트 만들기
커서로 연결 리스트 만들기
- 연결 리스트 단점 : 삭제, 삽입을 수행할 때마다 노드용 객체를 위한 메모리 영역을 만들고 해제해야 하는 과정 필요
> 데이터의 개수가 크게 바꾸지 않고 데이터 개수의 최대값을 미리 알 수 있다고 가정하여 배열로 만들어서 사용한다. - 배열의 커서에 해당하는 값 : 다음 노드에 대한 포인터가 아니라 다음 노드가 들어 있는 요소의 인덱스에 대한 값
* 이때, 포인터 역할을 하는 인덱스를 커서(cursor)라고 한다.
* 꼬리 노드 커서는 -1로 한다.
ex) 노드 A의 커서 3 : A의 다음 노드 B가 인덱스 3인 위치에 저장되어 있음을 말한다. - 이와 같은 방법을 사용하면 노드의 삽입, 삭제 시 요소를 옮길 필요가 없어진다.
- 배열의 크기를 넘어 노드를 추가하는 경우에 대한 처리는 하지 않는다.
- 커서의 자료형 Index : 단순한 정수 값을 가진다. (int형과 동일하게 정의)
- 노드의 자료형 Node : 연결 릿트의 노드를 의미하는 구조체이다. 커서 next의 자료형은 커서의 자료형인 Index이다.
- 연결 리스트를 관리하는 구조체 List : 구조체 List는 연결 리스트를 관리하는 구조체이다.
/* 커서에 의한 선형 리스트(헤더) */
#ifndef ___ArrayLinkedList
#define ___ArrayLinkedList
#include "Member.h"
#define Null –1 /* 빈 커서 */
typedef int Index; /* 커서 형 */
/*--- 노드 ---*/
typedef struct {
Member data; /* 데이터 */
Index next; /* 뒤쪽노드 */
Index Dnext; /* 프리 리스트의 뒤쪽노드 */
} Node;
/*--- 선형(연결) 리스트 ---*/
typedef struct {
Node *n; /* 리스트 본체(배열) */
Index head; /* 머리노드 */
Index max; /* 사용 중인 꼬리 레코드 */
Index deleted; /* 프리 리스트의 머리노드 */
Index crnt; /* 주목노드 */
} List;
/*--- 선형 리스트를 초기화(가장 큰 요솟수는 size) ---*/
void Initialize(List *list, int size);
/*--- 함수 compare에 의해 x와 같은 것으로 판단되는 노드를 검색 ---*/
Index search(List *list, const Member *x,
int compare(const Member *x, const Member *y));
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List *list, const Member *x);
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List *list, const Member *x);
/*--- 머리노드를 삭제 ---*/
void RemoveFront(List *list);
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(List *list);
/*--- 선택한 노드 삭제 ---*/
void RemoveCurrent(List *list);
/*--- 모든 노드를 삭제 ---*/
void Clear(List *list);
/*--- 선택한 노드의 데이터 출력 ---*/
void PrintCurrent(const List *list);
/*--- 선택한 노드의 데이터 출력 (줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const List *list);
/*--- 모든 노드의 데이터 출력 ---*/
void Print(const List *list);
/*--- 선형 리스트 종료 ---*/
void Terminate(List *list);
#endif/* 커서에 의한 선형 리스트(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "Member.h"
#include "ArrayLinkedList.h"
/*--- 삽입할 레코드의 인덱스를 구한 다음 반환 ---*/
static Index GetIndex(List *list)
{
if (list->deleted == NULL) /* 삭제할 레코드가 없는 경우 */
return ++(list->max);
else {
Index rec = list->deleted;
list->deleted = list->n[rec].Dnext;
return rec;
}
}
/*--- 지정된 레코드를 삭제 리스트에 등록한다. ---*/
static void DeleteIndex(List *list, Index idx)
{
if (list->deleted == NULL) { /* 삭제할 레코드가 없는 경우 */
list->deleted = idx;
list->n[idx].Dnext = NULL;
}
else {
Index ptr = list->deleted;
list->deleted = idx;
list->n[idx].Dnext = ptr;
}
}
/*--- n이 가리키는 노드의 각 멤버에 값을 설정 ----*/
static void SetNode(Node *n, const Member *x, Index next) {
n->data = *x; /* 데이터 */
n->next = next; /* 뒤쪽노드에 대한 포인터 */
}
/*--- 선형 리스트를 초기화(가장 큰 요소수는 size) ---*/
void Initialize(List *list, int size) {
list->n = calloc(size, sizeof(Node));
list->head = NULL; /* 머리노드 */
list->crnt = NULL; /* 주목노드 */
list->max = NULL;
list->deleted = NULL;
}
/*--- 함수 compare 의해 x와 같은 노드를 검색 ---*/
Index search(List *list, const Member *x, int compare(const Member *x, const Member *y)) {
Index ptr = list->head;
while (ptr != NULL) {
if (compare(&list->n[ptr].data, x) == 0) {
list->crnt = ptr;
return ptr; /* 검색 성공 */
}
ptr = list->n[ptr].next;
}
return NULL; /* 검색 실패 */
}
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(List *list, const Member *x) {
Index ptr = list->head;
list->head = list->crnt = GetIndex(list);
SetNode(&list->n[list->head], x, ptr);
}
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(List *list, const Member *x) {
if (list->head == NULL) /* 비어있는 경우 */
InsertFront(list, x); /* 머리에 삽입 */
else {
Index ptr = list->head;
while (list->n[ptr].next != NULL)
ptr = list->n[ptr].next;
list->n[ptr].next = list->crnt = GetIndex(list);
SetNode(&list->n[list->n[ptr].next], x, NULL);
}
}
/*--- 머리노드를 삭제 ---*/
void RemoveFront(List *list) {
if (list->head != NULL) {
Index ptr = list->n[list->head].next;
DeleteIndex(list, list->head);
list->head = list->crnt = ptr;
}
}
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(List *list) {
if (list->head != NULL) {
if (list->n[list->head].next == NULL) /* 노드가 하나만 있으면 */
RemoveFront(list); /* 머리노드를 삭제 */
else {
Index ptr = list->head;
Index pre;
while (list->n[ptr].next != NULL) {
pre = ptr;
ptr = list->n[ptr].next;
}
list->n[pre].next = NULL;
DeleteIndex(list, ptr);
list->crnt = pre;
}
}
}
/*--- 선택한 노드 삭제 ---*/
void RemoveCurrent(List *list) {
if (list->head != NULL) {
if (list->crnt == list->head) /* 머리노드를 주목하고 있으면 */
RemoveFront(list); /* 머리노드를 삭제 */
else {
Index ptr = list->head;
while (list->n[ptr].next != list->crnt)
ptr = list->n[ptr].next;
list->n[ptr].next = list->n[list->crnt].next;
DeleteIndex(list, list->crnt);
list->crnt = ptr;
}
}
}
/*--- 모든 노드를 삭제 ---*/
void Clear(List *list) {
while (list->head != NULL) /* 텅 빌 때까지 */
RemoveFront(list); /* 머리노드를 삭제 */
list->crnt = NULL;
}
/*--- 선택한 노드의 데이터를 출력 ---*/
void PrintCurrent(const List *list) {
if (list->crnt == NULL)
printf("주목노드가 없습니다.");
else
PrintMember(&list->n[list->crnt].data);
}
/*--- 선택한 노드의 데이터를 출력(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const List *list) {
PrintCurrent(list);
putchar('\n');
}
/*--- 모든 노드의 데이터를 출력 ---*/
void Print(const List *list) {
if (list->head == NULL)
puts("노드가 없습니다.");
else {
Index ptr = list->head;
puts("【 모두 보기 】");
while (ptr != NULL) {
PrintLnMember(&list->n[ptr].data);
ptr = list->n[ptr].next; /* 뒤쪽노드 */
}
}
}
/*--- 선형 리스트 종료 ---*/
void Terminate(List *list) {
Clear(list); /* 모든 노드를 삭제 */
free(list->n);
}
배열의 비어 있는 요소 처리하기 : p372-373
프리 리스트
- 삭제한 여러 레코드를 관리 > 사용하지 않는 빈 배열 문제 해결
- 프리 리스트 (free list) : 삭제한 레코드를 관리하기 위해 사용하는 자료구조
- 노드용 구조체 Node와 연결 리스트를 과니하는 구조체 List에 포인터 버전에 없는 멤버를 추가한다.
- 프리 리스트 변화 과정 : p374-376
//노드 구조체 Node에 추가한 멤버
Dnext //프리 리스트의 다음 노드를 가리키는 커서
//연결 리스트를 관리하는 구조체 List에 추가한 멤버
deleted //프리 리스트의 머리 노드를 가리키는 커서
max //배열의 가장 꼬리 쪽에 들어 있는 노드의 레코드 번호를 의미한다.
배열 커서로 연결 리스트 만들기
/* 배열 커서에 의한 선형(연결) 리스트의 사용 예 */
#include <stdio.h>
#include "Member.h"
#include "ArrayLinkedList.h"
/*--- 메뉴 ---*/
typedef enum {
TERMINATE, INS_FRONT, INS_REAR, RMV_FRONT, RMV_REAR, PRINT_CRNT,
RMV_CRNT, SRCH_NO, SRCH_NAME, PRINT_ALL, CLEAR
} Menu;
/*--- 메뉴 선택 ---*/
Menu SelectMenu(void) {
int i, ch;
char *mstring[] = {
"머리에 노드를 삽입", "말미에 노드를 삽입", "머리노드를 삭제",
"꼬리노드를 삭제", "주목노드를 출력", "주목노드를 삭제",
"번호로 검색", "이름으로 검색", "모든 노드를 출력",
"모든 노드를 삭제",
};
do {
for (i = TERMINATE; i < CLEAR; i++) {
printf("(%2d) %-18.18s ", i + 1, mstring[i]);
if ((i % 3) == 2)
putchar('\n');
}
printf("( 0) 종료 : ");
scanf("%d", &ch);
} while (ch < TERMINATE || ch > CLEAR);
return (Menu)ch;
}
/*--- 메인 ---*/
int main(void) {
Menu menu;
List list;
Initialize(&list, 30); /* 선형 리스트 초기화 */
do {
Member x;
switch (menu = SelectMenu()) {
/* 머리에 노드를 삽입 */
case INS_FRONT:
x = ScanMember("머리에 삽입", MEMBER_NO | MEMBER_NAME);
InsertFront(&list, &x);
break;
/* 말미에 노드를 삽입 */
case INS_REAR:
x = ScanMember("꼬리에 삽입", MEMBER_NO | MEMBER_NAME);
InsertRear(&list, &x);
break;
/* 머리노드를 삭제 */
case RMV_FRONT:
RemoveFront(&list);
break;
/* 꼬리노드를 삭제 */
case RMV_REAR:
RemoveRear(&list);
break;
/* 선택한 노드의 데이터를 출력 */
case PRINT_CRNT:
PrintLnCurrent(&list);
break;
/* 선택한 노드를 삭제 */
case RMV_CRNT:
RemoveCurrent(&list);
break;
/* 번호로 검색 */
case SRCH_NO:
x = ScanMember("검색", MEMBER_NO);
if (search(&list, &x, MemberNoCmp) != NULL)
PrintLnCurrent(&list);
else
puts("그 번호의 데이터가 없습니다.");
break;
/* 이름으로 검색 */
case SRCH_NAME:
x = ScanMember("검색", MEMBER_NAME);
if (search(&list, &x, MemberNameCmp) != NULL)
PrintLnCurrent(&list);
else
puts("그 이름의 데이터가 없습니다.");
break;
/* 모든 노드의 데이터를 출력 */
case PRINT_ALL:
Print(&list);
break;
/* 모든 노드를 삭제 */
case CLEAR:
Clear(&list);
break;
}
} while (menu != TERMINATE);
Terminate(&list); /* 선형 리스트의 뒤처리 */
return 0;
}
09-4 원형 이중 연결 리스트
원형 리스트 (circular list)
- 선형 리스트의 꼬리 노드가 머리 노드를 가리키는 것
- 고리 모양으로 나열된 데이터를 저장할 때 알맞은 자료구조이다.
- 원형 리스트와 선형 리스트의 차이점 : 꼬리 노드의 다음 노드를 가리키는 포인터가 널(NULL)이 아니라 머리 노드의 포인터이다.
빈 원형 리스트 판단하는 방법
list->head == NULL
노드가 1개인 원형 리스트를 판단하는 방법
- 노드가 1개라면 머리 노드의 다음 포인터를 자기 자신인 머리 노드를 가리킨다.
list->head->next == list->head
머리 노드인지 판단하는 방법
- Node *형 변수 p : 리스트에 있는 어떤 노드를 가리키고 있음
p == list->head //p가 가리키고 있는 노드가 머리 노드인지 확인한다.
꼬리 노드인지 판단하는 방법
- Node *형 변수 p : 리스트에 있는 어떤 노드를 가리키고 있음
p->next == list->head
이중 연결 리스트 (doubly linked list)
- 선형 리스트의 단점 : 다음 노드는 찾기 쉽지만, 앞쪽 노드는 찾을 수 없음
- 각 노드에는 다음 노드에 대한 포인터와 앞쪽의 노드에 대한 포인터가 주어진다.
typedef struct __node {
Member data; //데이터
struct __node *prev; //앞쪽 노드에 대한 포인터
struct __node *next; //다음 노드에 대한 포인터
} Dnode;
머리 노드인지 판단하는 방법
- Dnode *형 변수 p : 리스트의 어떤 노드를 가리킴
p == list->head
p->prev == NULL
꼬리 노드인지 판단하는 방법
p->next == NULL
원형 이중 연결 리스트 (circular doubly linked list)
/* 원형 이중연결 리스트(헤더) */
#ifndef ___CircDblLinkedList
#define ___CircDblLinkedList
#include "Member.h"
/*--- 노드를 나타내는 구조체 Dnode ---*/
typedef struct __node {
Member data; /* 데이터 */
struct __node *prev; /* 앞쪽노드에 대한 포인터 */
struct __node *next; /* 뒤쪽노드에 대한 포인터 */
} Dnode;
/*--- 원형 이중연결 리스트 관리하는 구조체 Dlist ---*/
typedef struct {
Dnode *head; /* 머리 dummy 노드에 대한 포인터 */
Dnode *crnt; /* 선택한 노드에 대한 포인터 */
} Dlist;
/*--- 리스트를 초기화 ---*/
void Initialize(Dlist *list);
/*--- 주목노드의 데이터를 나타냄 ---*/
void PrintCurrent(const Dlist *list);
/*--- 주목노드의 데이터를 나타냄(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const Dlist *list);
/*--- 함수 compare로 x와 같은 노드를 검색 ---*/
Dnode *search(Dlist *list, const Member *x,
int compare(const Member *x, const Member *y));
/*--- 모든 노드의 데이터를 리스트 순서로 나타냄 ---*/
void Print(const Dlist *list);
/*--- 모든 노드의 데이터를 리스트 순서 거꾸로 나타냄 ---*/
void PrintReverse(const Dlist *list);
/*--- 주목노드를 하나 뒤쪽으로 나아가도록 ---*/
int Next(Dlist *list);
/*--- 주목노드를 하나 앞쪽으로 되돌아가도록 ---*/
int Prev(Dlist *list);
/*--- p가 가리키는 노드 바로 뒤에 노드를 삽입 ---*/
void InsertAfter(Dlist *list, Dnode *p, const Member *x);
/*--- 머리에 노드를 삽입 ---*/
void InsertFront(Dlist *list, const Member *x);
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(Dlist *list, const Member *x);
/*--- p가 가리키는 노드를 삭제 ---*/
void Remove(Dlist *list, Dnode *p);
/*--- 머리노드를 삭제 ---*/
void RemoveFront(Dlist *list);
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(Dlist *list);
/*--- 주목노드를 삭제 ---*/
void RemoveCurrent(Dlist *list);
/*--- 모든 노드를 삭제 ---*/
void Clear(Dlist *list);
/*--- 원형 이중연결 리스트의 뒤처리 ---*/
void Terminate(Dlist *list);
#endif/* 원형 이중 연결 리스트(소스) */
#include <stdio.h>
#include <stdlib.h>
#include "CircDblLinkedList.h"
/*--- 하나의 노드를 동적으로 생성 ---*/
//Dnode형 객체를 생성하고 해당 객체의 포인터 반환
static Dnode *AllocDNode(void) {
return calloc(1, sizeof(Dnode));
}
/*--- 노드의 각 멤버에 값을 설정 ----*/
//Dnode형 객체의 멤버 값 설정
//n에 전달받은 Dnode형 객체 포인터를 통해 멤버 값 설정
static void SetDNode(Dnode *n, const Member *x, const Dnode *prev,
const Dnode *next) {
n->data = *x; /* 데이터 */
n->prev = prev; /* 앞쪽노드에 대한 포인터 */
n->next = next; /* 뒤쪽노드에 대한 포인터 */
}
/*--- 리스트가 비어있는가? ---*/
//더미 노드의 뒤쪽 포인터 list->head->next가 더미 노드인 list->head를 가리키면 비어 있는 상태라고 판단한다.
//비어 있는 상태의 리스트는 list->head, 더미 노드의 앞쪽 포인터인 list->head->prev, 더미 노드의 뒤쪽 포인터인 list->head->next의 3개 모두 더미 노드를 가리킨다.
//리스트가 비어있는 경우 함수 반환값 : 1, 아닌 경우 : 0
static int IsEmpty(const Dlist *list) {
return list->head->next == list->head;
}
/*--- 리스트를 초기화 ---*/
//비어 있는 상태의 노드 1개를 만들어서 리스트를 초기화한다. (더미 노드)
void Initialize(Dlist *list) {
Dnode *dummyNode = AllocDNode(); /* 더미 노드를 만듦 */
//더미 노드의 앞쪽 포인터 prev와 뒤쪽 포인터 next 모드 자기 자신(더미노드)을 가리키도록 설정한다.
list->head = list->crnt = dummyNode;
dummyNode->prev = dummyNode->next = dummyNode;
}
/*--- 선택한 노드의 데이터를 출력 ---*/
//list->crnt가 가리키는 노드의 데이터를 출력한다.
void PrintCurrent(const Dlist *list) {
if (IsEmpty(list))
printf("주목노드가 없습니다.");
else
PrintMember(&list->crnt->data);
}
/*--- 선택한 노드의 데이터를 출력(줄바꿈 문자 붙임) ---*/
void PrintLnCurrent(const Dlist *list) {
PrintCurrent(list);
putchar('\n');
}
/*--- 함수 compare로 x와 같은 노드를 선형 검색 ---*/
//머리노드(더미 노드의 다음 노드)부터 뒤쪽 포인터를 이용해 순서대로 스캔한다.
//검색을 시작하는 노드 위치 : list->head->next가 가리키는 노드
Dnode *search(Dlist *list, const Member *x, int compare(const Member *x, const Member *y)) {
Dnode *ptr = list->head->next;
while (ptr != list->head) {
if (compare(&ptr->data, x) == 0) {
list->crnt = ptr; //crnt는 찾은 노드(ptr)를 가리키도록 설정한다.
return ptr; /* 검색 성공 */
}
ptr = ptr->next;
}
//노드를 찾지 못하고 한바퀴 돌아 다시 더미 노드로 돌아오면(ptr == head) 검색에 실패한 것.
return NULL; /* 검색 실패 */
}
/*--- 모든 노드의 데이터를 리스트 순으로 출력 ---*/
//list->head->next부터 스캔하기 시작해 뒤쪽 포인터를 찾아가며 각 노드의 데이터를 출력한다.
//다시 head로 돌아오면(ptr == head) 스캔을 종료한다.
void Print(const Dlist *list) {
if (IsEmpty(list))
puts("노드가 없습니다.");
else {
Dnode *ptr = list->head->next;
puts("【 모두 보기 】");
while (ptr != list->head) {
PrintLnMember(&ptr->data);
ptr = ptr->next; /* 뒤쪽노드에 주목 */
}
}
}
/*--- 모든 노드의 데이터를 리스트 순서 거꾸로 출력 ---*/
void PrintReverse(const Dlist *list) {
if (IsEmpty(list))
puts("노드가 없습니다.");
else {
Dnode *ptr = list->head->prev;
puts("【 모두 보기 】");
while (ptr != list->head) {
PrintLnMember(&ptr->data);
ptr = ptr->prev; /* 앞쪽노드에 주목 */
}
}
}
/*--- 선택한 노드를 하나 뒤쪽으로 나아가도록 ---*/
//선택한 노드의 다음 노드로 진행시키는 함수
//리스트가 비어 있지 않고 선택한 노드의 다음 노드가 있는 경우에만 동작한다.
int Next(Dlist *list) {
if (IsEmpty(list) || list->crnt->next == list->head)
return 0; /* 나아갈 수 없음 */
list->crnt = list->crnt->next;
return 1; //다음 노드로 진행하는 데 성공
}
/*--- 선택한 노드를 하나 앞쪽으로 되돌아가도록 ---*/
//선택한 노드의 바로 앞쪽 노드로 되돌아가게 하는 함수
int Prev(Dlist *list) {
if (IsEmpty(list) || list->crnt->prev == list->head)
return 0; /* 되돌아갈 수 없음 */
list->crnt = list->crnt->prev;
return 1;
}
/*--- p가 가리키는 노드를 삭제 ---*/
//p->prev와 p->next 사이에 있는 노드를 삭제한다.
//1. 노드 A의 뒤쪽 포인터 p->prev->next가 가리키는 노드가 C(p->next)가 되도록 업데이트한다.
//2. 노드 C의 앞쪽 포인터 p->next->prev가 가리키는 노드가 A(p->prev)가 되도록 업데이트한다. 그리고 p가 가리키는 메모리 영역을 해제한다.
//3. 선태한 노드가 삭제한 노드의 앞쪽 노드 A를 가리킬 수 있도록 crnt를 업데이트한다.
void Remove(Dlist *list, Dnode *p) {
p->prev->next = p->next;
p->next->prev = p->prev;
list->crnt = p->prev; /* 삭제한 노드의 앞쪽노드에 주목 */
free(p);
if (list->crnt == list->head)
list->crnt = list->head->next;
}
/*--- 머리노드를 삭제 ---*/
//Remove 함수를 사용해 포인터 list->head->next가 가리키는 머리 노드를 삭제한다.
//이때 더미노드를 삭제하면 안되므로 list->head가 가리키는 더미노드가 아닌 그 다음 노드 list->head->next를 삭제한다.
void RemoveFront(Dlist *list) {
if (!IsEmpty(list))
Remove(list, list->head->next);
}
/*--- 꼬리노드를 삭제 ---*/
void RemoveRear(Dlist *list) {
if (!IsEmpty(list))
Remove(list, list->head->prev);
}
/*--- 주목노드를 삭제 ---*/
void RemoveCurrent(Dlist *list) {
if (list->crnt != list->head)
Remove(list, list->crnt);
}
/*--- 모든 노드를 삭제 ---*/
//삭제가 끝나면 선택한 노드에 대한 포인터 list->crnt가 가리키는 노드는 더미 노드 list->head로 업데이트한다.
void Clear(Dlist *list) {
while (!IsEmpty(list)) /* 텅 빌 때까지 */
RemoveFront(list); /* 머리노드를 삭제 */
}
/*--- 원형 이중 연결 리스트의 뒤처리 ---*/
void Terminate(Dlist *list) {
Clear(list); /* 모든 노드를 삭제 */
free(list->head); /* 더미 노드를 삭제 */
}
/*--- 포인터 p가 가리키는 노드 바로 뒤에 노드를 삽입 ---*/
//노드를 삽입한 위치 : p가 가리키는 노드와 p->next가 가리키는 노드의 사이
//1. 새로 삽입할 노드를 만들고 만든 노드의 앞쪽 포인터가 가리키는 노드(B), 뒤쪽 포인터가 가리키는 노드(C)를 설정한다.
//2. B의 뒤쪽 포인터 p->next와 C의 앞쪽 포인터 p->next->prev 모두 새로 삽입한 노드인 ptr(노드 D)을 가리키도록 업데이트
//3. 선택한 노드 list->crnt가 삽입한 노드를 가리키도록 업데이트한다.
//이때, 리스트 머리에 더미 노드가 있어 '비어 있는 리스트에 삽입하는 경우'와 '리스트 머리에 삽입하는 경우'는 따로 처리하지 않아도 된다.
//더미 노드만 있는 리스트에 노드 삽입하는 과정 (삽입하기 전에 crnt, head는 모두 더미 노드를 가리키고 있다.)
// 1. 만든 노드의 앞쪽 포인터와 뒤쪽 포인터는 더미 노드를 가리킨다.
// 2. 더미 노드의 뒤쪽 포인터와 앞쪽 포인터가 가리키는 노드는 A이다.
// 3. 선택한 노드가 가리키는 노드는 A이다.
void InsertAfter(Dlist *list, Dnode *p, const Member *x) {
Dnode *ptr = AllocDNode();
Dnode *nxt = p->next;
p->next = p->next->prev = ptr;
SetDNode(ptr, x, p, nxt);
list->crnt = ptr; /* 삽입한 노드에 주목 */
}
/*--- 머리에 노드를 삽입 ---*/
//더미 노드의 바로 뒤에 삽입한다.
//list->head가 가리키는 더미 노드 뒤에 노드를 삽입한다.
void InsertFront(Dlist *list, const Member *x) {
InsertAfter(list, list->head, x);
}
/*--- 꼬리에 노드를 삽입 ---*/
void InsertRear(Dlist *list, const Member *x) {
InsertAfter(list, list->head->prev, x);
}
* 원형 이중 연결 리스트에서 p가 가리키는 노드의 위치 판단하는 방법
- 원형 이중 연결 리스트에서 Dnode *형의 포인터 p가 리스트의 어떤 노드를 가리키는 경우 p가 가리키는 노드 위치를 판단하려면 다음 식을 사용한다.
p->prev == list->head //p가 가리키는 노드가 머리 노드인지 확인
p->prev->prev == list->head //p가 가리키는 노드가 두번째 노드인지 확인
p->next == list->head //p가 가리키는 노드가 꼬리 노드인지 확인
p->next->next == list->head //p가 가리키는 노드가 두번째 노드인지 확인
원형 이중 연결 리스트를 사용한 프로그램
/* 원형 이중 연결 리스트를 사용하는 프로그램 */
#include <stdio.h>
#include "Member.h"
#include "CircDblLinkedList.h"
/*--- 메뉴 ---*/
typedef enum {
TERMINATE, INS_FRONT, INS_REAR, RMV_FRONT, RMV_REAR, PRINT_CRNT,
RMV_CRNT, SRCH_NO, SRCH_NAME, PRINT_ALL, NEXT, PREV, CLEAR
} Menu;
/*--- 메뉴 선택 ---*/
Menu SelectMenu(void) {
int i, ch;
char *mstring[] = {
"머리에 노드를 삽입", "꼬리에 노드를 삽입", "머리 노드를 삭제",
"꼬리 노드를 삭제", "선택한 노드를 출력", "선택한 노드를 삭제",
"번호로 검색", "이름으로 검색", "모든 노드를 출력",
"선택한 노드를 뒤쪽으로", "선택한 노드를 앞쪽으로", "모든 노드를 삭제",
};
do {
for (i = TERMINATE; i < CLEAR; i++) {
printf("(%2d) %-22.22s ", i + 1, mstring[i]);
if ((i % 3) == 2)
putchar('\n');
}
printf("(0) 종료 : ");
scanf("%d", &ch);
} while (ch < TERMINATE || ch > CLEAR);
return (Menu)ch;
}
/*--- 메인 ---*/
int main(void) {
Menu menu;
Dlist list;
Initialize(&list); /* 원형 이중 연결 리스트를 초기화 */
do {
Member x;
switch (menu = SelectMenu()) {
/* 머리에 노드를 삽입 */
case INS_FRONT:
x = ScanMember("머리에 삽입", MEMBER_NO | MEMBER_NAME);
InsertFront(&list, &x);
break;
/* 꼬리에 노드를 삽입 */
case INS_REAR:
x = ScanMember("꼬리에 삽입", MEMBER_NO | MEMBER_NAME);
InsertRear(&list, &x);
break;
/* 머리 노드를 삭제 */
case RMV_FRONT:
RemoveFront(&list);
break;
/* 꼬리 노드를 삭제 */
case RMV_REAR:
RemoveRear(&list);
break;
/* 선택한 노드의 데이터를 출력 */
case PRINT_CRNT:
PrintLnCurrent(&list);
break;
/* 선택한 노드를 삭제 */
case RMV_CRNT:
RemoveCurrent(&list);
break;
/* 번호로 검색 */
case SRCH_NO:
x = ScanMember("검색", MEMBER_NO);
if (search(&list, &x, MemberNoCmp) != NULL)
PrintLnCurrent(&list);
else
puts("그 번호의 데이터가 없습니다.");
break;
/* 이름으로 검색 */
case SRCH_NAME:
x = ScanMember("검색", MEMBER_NAME);
if (search(&list, &x, MemberNameCmp) != NULL)
PrintLnCurrent(&list);
else
puts("그 이름의 데이터가 없습니다.");
break;
/* 모든 노드의 데이터를 출력 */
case PRINT_ALL:
Print(&list);
break;
/* 선택한 노드 다음으로 진행 */
case NEXT:
Next(&list);
break;
/* 선택한 노드 앞쪽으로 진행 */
case PREV:
Prev(&list);
break;
/* 모든 노드를 삭제 */
case CLEAR:
Clear(&list);
break;
}
} while (menu != TERMINATE);
Terminate(&list); /* 원형 이중 연결 리스트 종료 */
return 0;
}'Algorithm' 카테고리의 다른 글
| 11. 해시 (0) | 2023.06.08 |
|---|---|
| 10. 트리 (0) | 2023.06.08 |
| 08. 문자열 (0) | 2023.05.25 |
| [미해결] 2023 인하대학교 프로그래밍 경진대회(IUPC) (A-모비스) (0) | 2023.05.21 |
| [백준] 25305(커트라인) c언어 (0) | 2023.05.21 |
'Algorithm' Related Articles
more
