[C언어로 쉽게 풀어쓴 자료구조] Chapter 7 - 연결 리스트 2

// 원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 것
// 장점 : 하나의 노드에서 다른 모든 노드로의 접근이 가능

 

// 원형 연결 리스트 테스트 프로그램
#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct ListNode {
    element data;
    struct ListNode *link;
} ListNode;

// 원형 연결 리스트 처음에 삽입하는 함수
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; // 새로 삽입된 노드는 기존에 헤드가 가리키던 노드를 가리킨다.
        head->link = node; // head는 새로 삽입된 노드를 가리킨다.
    }
    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;
        head->link = node;
        head = node; // 새로 삽입된 노드가 헤드가 된다.
    }
    return head;
}

// 리스트의 항목 출력
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->\n", p->data);
}

int main()
{
    ListNode *head = NULL;

    head = insert_last(head, 20);
    print_list(head);
    head = insert_last(head, 30);
    print_list(head);
    head = insert_last(head, 40);
    print_list(head);
    head = insert_first(head, 10);
    print_list(head);
    return 0;
}

/*출력값
20->20->
20->30->
20->30->40->
10->20->30->40->
*/

 

// 멀티 플레이어 게임 (게임 순서 차례대로 출력)

// 멀티 플레이어 게임
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef char element[100];
typedef struct ListNode {
    element data;
    struct ListNode *link;
} ListNode;

ListNode* insert_first(ListNode* head, element data)
{
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    strcpy(node->data, data); // strcpy : string copy 문자열 복사 함수
    if (head == NULL){
        head = node;
        node->link = head;
    }
    else {
        node->link = head->link;
        head->link = node;
    }
    return head;
}

int main()
{
    ListNode *head = NULL;

    head = insert_first(head, "KIM");
    head = insert_first(head, "PARK");
    head = insert_first(head, "LEE");

    ListNode* p = head;
    for (int i = 0; i < 10; i++ ){
        printf("현재 차례=%s \n", p->data);
        p=p->link;
    }
    return 0;
}

/*출력값
현재 차례=KIM
현재 차례=LEE
현재 차례=PARK
현재 차례=KIM
현재 차례=LEE
현재 차례=PARK
현재 차례=KIM
현재 차례=LEE
현재 차례=PARK
현재 차례=KIM
*/

 

// 이중 연결 리스트

/*
이중 연결 리스트 : 하나의 노드가 선행 노드와 후속 노드에 대한 두개의 링크를 가지는 리스트
장점 : 링크가 양방향 이므로 양방향으로 검색이 가능
단점 : 공간을 많이 차지하고 코드가 복잡해진다는 것

실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합한 상태를 사용한다.

head pointer : 리스트의 첫 번째 노드를 가리키는 포인터
head node : 별도의 데이터를 가지고 있지 않은 특별한 노드 // 단지 삽입과 삭제 알고리즘을 간편하게 구현하기 위해서 존재
(head node의 data field에는 아무런 정보를 담고 있지 않다.)
*/

// 이중 연결 리스트 프로그램
#include <stdio.h>
#include <stdlib.h>

typedef int element;
typedef struct DListNode {
    element data;
    struct DListNode* llink; // 왼쪽 링크 필드
    struct DListNode* rlink; // 오른쪽 링크 필드
} DListNode;

// 이중 연결 리스트를 초기화
void init(DListNode* phead)
{
    phead->llink = phead;
    phead->rlink = phead;
}

// 이중 연결 리스트에서 삽입함수
// 새로운 데이터를 노드 before의 오른쪽에 삽입
void dinsert(DListNode *before, element data)
{
    DListNode *newnode = (DListNode *)malloc(sizeof(DListNode));
    newnode->data = data;
    newnode->llink = before; // before<=new 연결
    newnode->rlink = before->rlink; // new => after 연결
    before->rlink->llink = newnode; // new <= after 연결
    before->rlink = newnode; // before => new 연결
}

// 이중 연결 리스트에서 삭제함수
void ddelete(DListNode* head, DListNode* removed)
{
    if(removed == head) return;
    removed->llink->rlink = removed->rlink; // before => after 연결
    removed->rlink->llink = removed->llink; // after => before 연결
    free(removed);
}

// 이중 연결 리스트의 노드를 출력
void print_dlist(DListNode* phead)
{
    DListNode* p;
    for (p = phead->rlink; p != phead; p = p->rlink){
        printf("<-| |%d| |-> ", p->data);
    }
    printf("\n");
}

int main()
{
    DListNode* head = (DListNode *)malloc(sizeof(DListNode));
    init(head);
    printf("추가 단계 \n");
    for (int i = 0; i < 5; i++){
        dinsert(head,i);
        print_dlist(head);
    }
    printf("삭제 단계 \n");
    for (int i = 0; i< 5; i++){
        print_dlist(head);
        ddelete(head, head->rlink);
    }
    free(head);
    return 0;
}

/*출력값
추가 단계
<-| |0| |->
<-| |1| |-> <-| |0| |->
<-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |4| |-> <-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
삭제 단계
<-| |4| |-> <-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |3| |-> <-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |2| |-> <-| |1| |-> <-| |0| |->
<-| |1| |-> <-| |0| |->
<-| |0| |->
*/

 

 

// 연결리스트로 구현한 스택 (linked stack)

// 연결 리스트로 구현한 스택
// 장점 : 크기 제한이 되지 않는다. (동적 메모리 할당을 하므로)
// 단점 : 삽입이나 삭제를 하는데 시간이 오래 걸린다. (삽입 : 동적 메모리 할당 필요 / 삭제 : 동적 메모리 해제)
// 공백 상태 : top == NULL
// 포화 상태 : 없음 (동적 메모리만 할당 된다면 무제한)
// linked stack

#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; // 항상 false => 포화상태 없음
}

// 삽입 함수
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; // top-- 와 같은 의미
        free(temp); // 동적 데이터 반환으로 삭제
        return data;
    }
}

// 피크 함수
element peek(LinkedStackType *s)
{
    if (is_empty(s)) {
        fprintf(stderr, "스택이 비어있음\n");
        exit(1);
    }
    else {
        return s->top->data;
    }
}

int main()
{
    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;
}

/*출력값
1->NULL
2->1->NULL
3->2->1->NULL
2->1->NULL
1->NULL
NULL
*/

 

 

// 연결 리스트로 구현한 큐 (linked queue)

// linked queue

#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; // front와 rear 모두 새로 삽입된 노드를 가리켜야 함
	}
	else { 		// 큐가 공백이 아니면
		q->rear->link = temp;  // 1. rear의 링크 필드가 삽입된 temp를 가리키도록.
		q->rear = temp; // 2. 새로 삽입된 temp가 rear가 되도록.
	}
}
// 삭제 함수
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;
}

/*출력값
1->NULL
1->2->NULL
1->2->3->NULL
2->3->NULL
3->NULL
NULL
*/