Data structure
[C언어로 쉽게 풀어쓴 자료구조] Chapter 7 - 연결 리스트 2
MoveForward
2022. 2. 22. 01:09
// 원형 연결 리스트 : 마지막 노드가 첫 번째 노드를 가리키는 것
// 장점 : 하나의 노드에서 다른 모든 노드로의 접근이 가능
// 원형 연결 리스트 테스트 프로그램
#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
*/