반응형
이 장은 한마디로 링크 손실이 없어야 한다.
원형 연결 리스트
마지막 노드가 첫 번째 노드를 가리키는 리스트 즉, 마지막 노드의 링크필드가 널(NULL)이 아니라 첫 번째 노드 주소가 되는 리스트이다. 장점은 노드의 삽입과 삭제가 단순 연결 리스트보다는 용이해진다. 삭제나 삽입시에는 항상 선행 노드를 가리키는 포인터가 필요함을 기억하자.
원형 연결 리스트 프로그램
#include <stdio.h>
#include <stdlib.h>
typedef int element;
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
// 리스트의 항목 출력
void print_list(ListNode* head)
{
ListNode* p;
if (head == NULL) return;
p = head->link;
do {
printf("%d->", p->data);
p = p->link;
} while (p != head);
printf("%d->", p->data); // 마지막 노드 출력
}
ListNode* insert_first(ListNode* head, element data)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = data;
if (head == NULL) {
head = node;
node->link = head;
}
else {
node->link = head->link; // (1)
head->link = node; // (2)
}
return head; // 변경된 헤드 포인터를 반환한다.
}
ListNode* insert_last(ListNode* head, element data)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
node->data = data;
if (head == NULL) {
head = node;
node->link = head;
}
else {
node->link = head->link; // (1)
head->link = node; // (2)
head = node; // (3)
}
return head; // 변경된 헤드 포인터를 반환한다.
}
// 원형 연결 리스트 테스트 프로그램
int main(void)
{
ListNode *head = NULL;
// list = 10->20->30->40
head = insert_last(head, 20);
head = insert_last(head, 30);
head = insert_last(head, 40);
head = insert_first(head, 10);
print_list(head);
return 0;
}
원형 연결 리스트 활용
1. 컴퓨터에서 여러 응용 프로그램을 하나의 CPU를 이용하여 실행할 때에 필요하다. 현재 실행 중인 모든 응용 프로그램은 원형 연결 리스트에 보관되며 운영 체제는 원형 연결 리스트에 있는 프로그램의 실행을 위해 고정된 시간 슬롯을 제공한다. 운영 체제는 모든 응용 프로그램이 완료될 때까지 원형 연결 리스트를 계속 순회한다.
2. 멀티 플레이어 게임 모든 플레이어는 원형 연결 리스트에 저장되며 한 플레이어의 기회가 끝나면 포인터를 앞으로 움직여서 다음 플레이어의 순서가 된다.
3. 원형 연결 리스트는 원형 큐를 만드는데도 사용할 수 있다. 우리는 4장에서 배열을 사용하여 원형 큐를 구현하엿지만 원형 연결 리스트를 이용하여 원형 큐를 구현할 수 있다는 것은 너무 명백하다. 원형 큐에서는 두 개의 포인터, front와 rear가 있어야 한다.
멀티 플러어 게임
#include <stdio.h>
#include <stdlib.h>
typedef char element[100];
typedef struct ListNode { // 노드 타입
element data;
struct ListNode *link;
} ListNode;
typedef struct CListType {
ListNode *head;
} CListType;
// 리스트의 항목 출력
void print_list(CListType* L)
{
ListNode* p;
if (L->head == NULL) return;
p = L->head->link;
do {
printf("%s->", p->data);
p = p->link;
} while (p != L->head);
printf("%s->", p->data); // 마지막 노드 출력
}
void insert_first(CListType* L, element data)
{
ListNode *node = (ListNode *)malloc(sizeof(ListNode));
strcpy(node->data, data);
if (L->head == NULL) {
L->head = node;
node->link = L->head;
}
else {
node->link = L->head->link; // (1)
L->head->link = node; // (2)
}
}
// 원형 연결 리스트 테스트 프로그램
int main(void)
{
CListType list = { NULL };
insert_first(&list, "KIM");
insert_first(&list, "PARK");
insert_first(&list, "CHOI");
ListNode* p = list.head;
for (int i = 0; i< 10; i++) {
printf("현재 차례=%s \n", p->data);
p = p->link;
}
return 0;
}
이중 연결 리스트
단순 연결 리스트에서는 후속 노드를 찾기는 쉽지만, 선행 노드를 찾으려면 구조상 아주 어렵다. 이중 연결 리스트는 이러한 문제점을 해결하기 위하여 만들어진 자료구조이다. 단점으로는 공간을 많이 차지하고 코드가 복잡해진다는 것이다.
mp3 재생 프로그램
현재 항목에서 이전 항목이나 다음 항목으로 쉽게 이동할 수 있는 자료구조를 사용하여야 한다. 우리는 이중 연결 리스트를 이용하여서 음악을 저장하고 사용자의 명령에 맞추어 곡을 선택하는 프로그램을 작성해 본 것이다.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef char element[100];
typedef struct DListNode { // 이중연결 노드 타입
element data;
struct DListNode* llink;
struct DListNode* rlink;
} DListNode;
DListNode* current;
// 이중 연결 리스트를 초기화
void init(DListNode* phead)
{
phead->llink = phead;
phead->rlink = phead;
}
// 이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead)
{
DListNode* p;
for (p = phead->rlink; p != phead; p = p->rlink) {
if (p == current)
printf("<-| #%s# |-> ", p->data);
else
printf("<-| %s |-> ", p->data);
}
printf("\n");
}
// 노드 newnode를 노드 before의 오른쪽에 삽입한다.
void dinsert(DListNode *before, element data)
{
DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
strcpy(newnode->data, data);
newnode->llink = before;
newnode->rlink = before->rlink;
before->rlink->llink = newnode;
before->rlink = newnode;
}
// 노드 removed를 삭제한다.
void ddelete(DListNode* head,
DListNode* removed)
{
if (removed == head) return;
removed->llink->rlink = removed->rlink;
removed->rlink->llink = removed->llink;
free(removed);
}
// 이중 연결 리스트 테스트 프로그램
int main(void)
{
char ch;
DListNode* head = (DListNode *)malloc(sizeof(DListNode));
init(head);
dinsert(head, "Mamamia");
dinsert(head, "Dancing Queen");
dinsert(head, "Fernando");
current = head->rlink;
print_dlist(head);
do {
printf("\n명령어를 입력하시오(<, >, q): ");
ch = getchar();
if (ch == '<') {
current = current->llink;
if (current == head)
current = current->llink;
}
else if (ch == '>') {
current = current->rlink;
if (current == head)
current = current->rlink;
}
print_dlist(head);
getchar();
} while (ch != 'q');
// 동적 메모리 해제 코드를 여기에
}
연결 리스트로 구현한 스택
#include <stdio.h>
#include <malloc.h>
typedef int element;
typedef struct StackNode {
element data;
struct StackNode *link;
} StackNode;
typedef struct {
StackNode *top;
} LinkedStackType;
// 초기화 함수
void init(LinkedStackType *s)
{
s->top = NULL;
}
// 공백 상태 검출 함수
int is_empty(LinkedStackType *s)
{
return (s->top == NULL);
}
// 포화 상태 검출 함수
int is_full(LinkedStackType *s)
{
return 0;
}
// 삽입 함수
void push(LinkedStackType *s, element item)
{
StackNode *temp = (StackNode *)malloc(sizeof(StackNode));
temp->data = item;
temp->link = s->top;
s->top = temp;
}
void print_stack(LinkedStackType *s)
{
for (StackNode *p = s->top; p != NULL; p = p->link)
printf("%d->", p->data);
printf("NULL \n");
}
// 삭제 함수
element pop(LinkedStackType *s)
{
if (is_empty(s)) {
fprintf(stderr, "스택이 비어있음\n");
exit(1);
}
else {
StackNode *temp = s->top;
int data = temp->data;
s->top = s->top->link;
free(temp);
return data;
}
}
// 피크 함수
element peek(LinkedStackType *s)
{
if (is_empty(s)) {
fprintf(stderr, "스택이 비어있음\n");
exit(1);
}
else {
return s->top->data;
}
}
// 주 함수
int main(void)
{
LinkedStackType s;
init(&s);
push(&s, 1); print_stack(&s);
push(&s, 2); print_stack(&s);
push(&s, 3); print_stack(&s);
pop(&s); print_stack(&s);
pop(&s); print_stack(&s);
pop(&s); print_stack(&s);
return 0;
}
연결 리스트로 구현한 큐
#include <stdio.h>
#include <stdlib.h>
typedef int element; // 요소의 타입
typedef struct QueueNode { // 큐의 노드의 타입
element data;
struct QueueNode *link;
} QueueNode;
typedef struct { // 큐 ADT 구현
QueueNode *front, *rear;
} LinkedQueueType;
// 큐 초기화 함수
void init(LinkedQueueType *q)
{
q->front = q->rear = 0;
}
// 공백 상태 검출 함수
int is_empty(LinkedQueueType *q)
{
return (q->front == NULL);
}
// 포화 상태 검출 함수
int is_full(LinkedQueueType *q)
{
return 0;
}
// 삽입 함수
void enqueue(LinkedQueueType *q, element data)
{
QueueNode *temp = (QueueNode *)malloc(sizeof(QueueNode));
temp->data = data; // 데이터 저장
temp->link = NULL; // 링크 필드를 NULL
if (is_empty(q)) { // 큐가 공백이면
q->front = temp;
q->rear = temp;
}
else { // 큐가 공백이 아니면
q->rear->link = temp; // 순서가 중요
q->rear = temp;
}
}
// 삭제 함수
element dequeue(LinkedQueueType *q)
{
QueueNode *temp =q-> front;
element data;
if (is_empty(q)) { // 공백상태
fprintf(stderr, "스택이 비어있음\n");
exit(1);
}
else {
data = temp->data; // 데이터를 꺼낸다.
q->front = q->front->link; // front를 다음노드를 가리키도록 한다.
if (q->front == NULL) // 공백 상태
q->rear = NULL;
free(temp); // 동적메모리 해제
return data; // 데이터 반환
}
}
void print_queue(LinkedQueueType *q)
{
QueueNode *p;
for (p= q->front; p != NULL; p = p->link)
printf("%d->", p->data);
printf("NULL\n");
}
// 연결된 큐 테스트 함수
int main(void)
{
LinkedQueueType queue;
init(&queue); // 큐 초기화
enqueue(&queue, 1); print_queue(&queue);
enqueue(&queue, 2); print_queue(&queue);
enqueue(&queue, 3); print_queue(&queue);
dequeue(&queue); print_queue(&queue);
dequeue(&queue); print_queue(&queue);
dequeue(&queue); print_queue(&queue);
return 0;
}
관심이 있으신 분들에게 유용한 정보였길 바라며
다음은 7장 연습문제 해설을 가져오도록 하겠습니다.
반응형